## 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

### Citations:

Zbl 0128.01603; Zbl 0194.00502; Zbl 0205.07603
Full Text:

### Online Encyclopedia of Integer Sequences:

Binomial transform of the centered triangular numbers A005448.

### References:

  Al-Salam, Versa, Generalized Sheffer polymomials, Duke Math. J., 37, 361-365 (1970) · Zbl 0205.07603  Barnabei, M.; Brini, A.; Nicoletti, G., Recursive matrices and umbral calculus, J. Algebra, 75, 546-573 (1982) · Zbl 0509.05005  Di Bucchianico, A., Polynomials of convolution type, Doctoral Thesis, Rijksuniversiteit Groningen (1991) · Zbl 0765.46027  Chu, W., Inversion techniques and combinatorial identities: strange evaluation of hypergeometric series, Pure Math. Appl., 4, 4, 409-427 (1993) · Zbl 0815.05008  Egorychev, G. P., Integral representation and the computation of combinatorial sums, (Translations of Mathematical Monographs, 59 (1984), AMS: AMS London) · Zbl 0676.05009  Gould, H. W.; Hsu, L. C., Some new inverse series relations, Duke Math. J., 859-891 (1973) · Zbl 0281.05008  Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), Wiley: Wiley Providence, RI · Zbl 0519.05001  Henrici, P., Applied and Computational Complex Analysis (1991), Wiley: Wiley New York  Milne, S., Inversion properties of triangular arrays of numbers, Anal., 1, 1-7 (1981) · Zbl 0481.05008  Riordan, J., Inverse relations and combinatorial identities, Amer. Math. Mon., 71, 485-498 (1964) · Zbl 0128.01603  Riordan, J., Combinatorial Identities (1968), Wiley: Wiley New York · Zbl 0194.00502  Roman, S., The Umbral Calculus (1978), Academic Press: Academic Press New York · Zbl 0375.05007  Shapiro, L. V.; Getu, S.; Woan, W.-J.; Woodson, L., The Riordan group, Discrete Appl. Math., 34, 229-239 (1991) · Zbl 0754.05010  Sprugnoli, R., Riordan arrays and combinatorial sums, Discrete Math., 132, 267-290 (1994) · Zbl 0814.05003  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.