×

zbMATH — the first resource for mathematics

Application of the notion of pseudogenerated two-index sequence and lemmas on substitution. (Russian) Zbl 0733.05004
The two-index sequence \(\{\) P(n,k)\(\}\) is said to be pseudogenerable of order p if there are (in a neighbourhood of zero) two analytic functions \(\phi\) (z) and \(\psi\) (z) such that \(\psi\) (0)\(\neq 0\), \(\phi (0)=\phi '(0)=...=\phi^{(p-1)}(0)=0\), \(\phi^{(p)}(0)\neq 0\), \(\sum^{\infty}_{n=0}P(n,k)z^ n/n!=\psi (z)\phi (z))^ k/k!\) for \(k\geq 0\). Substitution lemma: Let \(\{\) P(n,k)\(\}\) be pseudogenerable with associated \(\phi\) (z) and \(\psi\) (z) and let \(f(t)=\sum^{\infty}_{n=0}a_ n(t^ n/n!)\) be the exponential generating function of the sequence \(\{a_ n\}\). Then \(\psi\) (z)\(\cdot f(\phi (z))\) is the exponential generating function of the sequence \(\{P_ n\}\), where \(P_ n=\sum^{n}_{k=0}P(n,k)\cdot a_ k\), \(n\geq 0\). The author develops a theory based on this lemma which yields in a nice way many well-known identities in combinatorics. In particular, he gives formulas for the convolution of pseudogenerable sequences and for the inverse (relative to convolution) of a pseudogenerable sequence of order 1.
MSC:
05A15 Exact enumeration problems, generating functions
05A19 Combinatorial identities, bijective combinatorics
PDF BibTeX XML Cite