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
Keywords:
exponential generating function