Left-inversion of combinatorial sums (Q1381817)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Left-inversion of combinatorial sums
scientific article

    Statements

    Left-inversion of combinatorial sums (English)
    0 references
    0 references
    0 references
    0 references
    5 January 1999
    0 references
    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 \textit{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 \textit{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 \textit{W. A. Al-Salam} and \textit{A. Verma} [Duke Math. J. 37, 361-365 (1970; Zbl 0205.07603)] and by \textit{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.
    0 references
    inverting combinatorial sums
    0 references
    Riordan array
    0 references
    Lagrangian inversion
    0 references
    0 references

    Identifiers