×

Left-inversion of combinatorial sums. (English) Zbl 0903.05005

Let \(\kappa\) be any field of characteristic zero; e.g., \(\kappa= \mathbb{R}\) or \(\mathbb{C}\). Consider the algebra \(\kappa [[t]]\) of formal series \(f(t)= \sum_{k\geq 0} f_kt^k\). The notation \([t^k] (\dots)\) for ‘the coefficient of \(t^k\) in the series \((\dots)\)’ is being used; so, \([t^k] f(t)= f_k\) and \(f(t)\) serves for the usual generating function of \((f_k\mid k\in \mathbb{N}_0)\). A Riordan array is a pair \((d(t), h(t))\) of formal series with \(d(t)\) of order 0; it defines the triangular array \((d_{n,k} \mid n,k\in \mathbb{N}_0\) and \(k\leq n)\) of elements in \(\kappa\) according to the rule \(d_{n,k}= [t^n]d(t) (th(t))^k\). For such an array \(\sum^n_{k=0} d_{n,k} f_k=[t^n] d(t)f (th(t))\) holds. An example of a Riordan array is provided by \(d(t)= h(t)= (1-t)^{-1}\). It defines the Pascal triangle. Any series \(f(t)\) of order one has the inverse, i.e. the unique series \(g(t)\) such that \((f\circ g)(t)= t=(g \circ f)(t)\). The coefficients of \(g(t)\) are given by Lagrangian inversion, \(g_n= {1\over n!} \Biggl[\Bigl( {d\over dt} \Bigr)^{n-1} \Bigl({t \over f(t)} \Bigr)^n \Biggr]_{t=0}\) \((n\geq 1)\). Inverting combinatorial sums may be considered a center of attraction in combinatorics [see J. Riordan, Am. Math. Mon. 71, 485-498 (1964; Zbl 0128.01603) or Combinatorial identities (1968; Zbl 0194.00502)]. In this paper the concepts of Riordan array and Lagrange inversion are used to give a new approach to this question. To explain the essence of what is proposed the authors use the relation \(a_n= \sum^{\lfloor {n\over 2} \rfloor}_{k =0} {n \choose 2k} b_k\) with \((b_k\mid k\in \mathbb{N}_0)\) given. To invert this combinatorial sum, take the array \(D=((1-t)^{-1}\), \(t(1-t)^{-2})\) with \(d_{n,k}= [t^n]((1-t)^{-1} (t(1-t)^{-2})^k) ={n \choose 2k}\). As the diagonal elements \(d_{n,n}\) \((n>0)\) are all zero, it is impossible to use Cauchy inversion. However, the following way out is proposed. For the generating functions \(a(t) \) and \(b(t)\) for \((a_k)\) and \((b_k)\), correspondingly, it holds \(a(t)= b(t^2(1-t)^{-2}) (1-t)^{-1}\); it follows \(b(y)= [(1-t)a(t)\mid y =t^2(1-t)^{-2}]\). By Lagrange inversion one obtains \[ b_n=[y^n] b(y)= {1\over 2n} [t^{2n-1}] \bigl((1-t) a'(t)- a(t)\bigr)(1-t)^{2n} =\sum^{2n}_{k=0} (-1)^k {2n \choose k} a_k. \] Using the arrays \(P=\{ {n \choose 2k} \mid n,k\in \mathbb{N}_0\}\) and \(\widetilde P= \{(-1)^k {2n \choose k} \mid n,k\in \mathbb{N}_0\}\) one can check that \(\widetilde PP=I\) and \(P\widetilde PP= P\), showing that \(\widetilde P\) is the ‘left-inverse’ array of \(P\). In this reasoning there is a delicate point, because the used identities \(y=t^2 (1-t)^{-2}\) and \(t= \sqrt y(1-t)\) are not equivalent. According to P. Henrici [Applied and computational complex analysis (1991)] the functional equation \(y=h(t)\) with \(\text{ord} (h(t))=2\) has the two solutions \(t_1(y)= \sqrt y(1+ \sqrt y)^{-1}\) and \(t_2(y)= -\sqrt y\cdot (1-\sqrt y)^{-1}\) belonging to \(\kappa [y^{1/2}]\). Only one of these solutions is chosen to perform the Lagrange inversion.
In this well-written paper the authors justify such a choice of a single solution of a given functional equation and examine the corresponding process of left inversion. Their results (Theorems 2.3 and 2.4) provide a method for inverting combinatorial sums \(a_n= \sum^{\lfloor {n\over s} \rfloor}_{k=0} d_{n,k} b_k\) for Riordan arrays \(\{d_{n,k}\}\) with \(s= \text{ord} (h(t))\geq 1\), which gives left-inverses \(b_n= \sum^{ns}_{k=0} \widetilde d_{n,k} a_k\) (here \(\widetilde d_{n,k}\) denotes the generic element of the inverse array). Several concise examples are given by the authors showing that this approach properly includes inversions treated by J. Riordan [loc. cit.]. Also, this paper extends umbral results by W. A. Al-Salam and A. Verma [Duke Math. J. 37, 361-365 (1970; Zbl 0205.07603)] and by A. Di Bucchianico [PhD Thesis, Rijksunitversiteit Groningen (1991)] to the streched arrays. Everybody interested in combinatorial identities and Lagrange inversion should consult this important paper for further information.

MSC:

05A19 Combinatorial identities, bijective combinatorics
05A15 Exact enumeration problems, generating functions
05A40 Umbral calculus
PDF BibTeX XML Cite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Binomial transform of the centered triangular numbers A005448.

References:

[1] Al-Salam, Versa, Generalized Sheffer polymomials, Duke Math. J., 37, 361-365 (1970) · Zbl 0205.07603
[2] Barnabei, M.; Brini, A.; Nicoletti, G., Recursive matrices and umbral calculus, J. Algebra, 75, 546-573 (1982) · Zbl 0509.05005
[3] Di Bucchianico, A., Polynomials of convolution type, Doctoral Thesis, Rijksuniversiteit Groningen (1991) · Zbl 0765.46027
[4] Chu, W., Inversion techniques and combinatorial identities: strange evaluation of hypergeometric series, Pure Math. Appl., 4, 4, 409-427 (1993) · Zbl 0815.05008
[5] Egorychev, G. P., Integral representation and the computation of combinatorial sums, (Translations of Mathematical Monographs, 59 (1984), AMS: AMS London) · Zbl 0676.05009
[6] Gould, H. W.; Hsu, L. C., Some new inverse series relations, Duke Math. J., 859-891 (1973) · Zbl 0281.05008
[7] Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), Wiley: Wiley Providence, RI · Zbl 0519.05001
[8] Henrici, P., Applied and Computational Complex Analysis (1991), Wiley: Wiley New York
[9] Milne, S., Inversion properties of triangular arrays of numbers, Anal., 1, 1-7 (1981) · Zbl 0481.05008
[10] Riordan, J., Inverse relations and combinatorial identities, Amer. Math. Mon., 71, 485-498 (1964) · Zbl 0128.01603
[11] Riordan, J., Combinatorial Identities (1968), Wiley: Wiley New York · Zbl 0194.00502
[12] Roman, S., The Umbral Calculus (1978), Academic Press: Academic Press New York · Zbl 0375.05007
[13] Shapiro, L. V.; Getu, S.; Woan, W.-J.; Woodson, L., The Riordan group, Discrete Appl. Math., 34, 229-239 (1991) · Zbl 0754.05010
[14] Sprugnoli, R., Riordan arrays and combinatorial sums, Discrete Math., 132, 267-290 (1994) · Zbl 0814.05003
[15] Sprugnoli, R., A unitary approach to combinatorial inversions, (Technical Report 14 (1994), Dipartimento di Sistemi e Informatica, Università di Firenze: Dipartimento di Sistemi e Informatica, Università di Firenze Orlando)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.