Both ordinary generating functions and exponential generating functions have the following multiplication property. If $(a_n)$ and $(b_n)$ are sequences of nonnegative integers and $(\Sigma_n a_n x^n)(\Sigma_n b_n x^n) = \Sigma_n c_n x^n$, then $(c_n)$ is always a sequence of nonnegative integers. Similarly if $(a_n)$ and $(b_n)$ are sequences of nonnegative integers and $(\Sigma_n a_n \frac{x^n}{n!})(\Sigma_n b_n \frac{x^n}{n!}) = \Sigma_n c_n \frac{x^n}{n!}$, then $(c_n)$ is always a sequence of nonnegative integers.
My question is, do falling factorial generating functions have the same multiplication property? That is, if $(a_n)$ and $(b_n)$ are sequences of nonnegative integers and $(\Sigma_n a_n (x)_n)(\Sigma_n b_n (x)_n) = \Sigma_n c_n (x)_n$, then is $(c_n)$ always a sequence of nonnegative integers? If not, does anyone know of a counterexample?
Best Answer
Yes, $(c_n)_{n\ge 0}$ will always be a sequence of nonnegative integers. To prove this, you just need to show that for each $n,m\in \mathbb N$, that $(x)_n (x)_m$ can be written as an $\mathbb N$-linear combination of the falling factorials $(x)_k$. Indeed, it is true that $$ (x)_n(x)_m=\sum_{k\ge 0}\binom{n}k\binom{m}kk!\,(x)_{n+m-k}\tag1 $$ To prove this polynomial identity, it suffices to prove it is true whenever $x$ is a positive integer. In that case, the identity is equivalent to $$ \binom{x}{n}\binom{x}{m}=\sum_k \frac{(n+m-k)!}{(n-k)!\,(m-k)!\,k!}\binom{x}{n+m-k} $$ and there is an easy combinatorial proof. Namely, both sides count the number of ways to take a set of size $x$, paint $n$ of the elements red, and $m$ of the elements blue, allowing an element to be painted both colors (the number of such "purple" elements corresponds to $k$).
Using $(1)$, we get that $$ \left(\sum_{i\ge 0}a_i(x)_i\right)\left(\sum_{j\ge 0}b_j(x)_j\right)=\sum_{i,j}a_ib_j(x)_i(x)_j=\sum_{i,j,k}a_ib_j\binom{i}{k}\binom{j}kk!(x)_{i+j-k} $$ Substituting $i+j-n$ for $k$, this becomes $\sum_{i,j,n}a_ib_j\binom{i}{i+j-n}\binom{j}{i+j-n}(i+j-n)!(x)_n$, which implies the following formula for $c_n$: $$ \boxed{c_n=\sum_{i,j}a_ib_j\binom{i}{n-j}\binom{j}{n-i}(i+j-n)!} $$ The sum ranges over all $i,j\ge 0$ for which $i+j\ge n$, but the only terms which contribute positively are those for which $\max(i,j)\le n$. Of course, this is always a positive integer if $a_i$ and $b_j$ are.