Do falling factorial generating functions have the multiplication property? 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?
 A: 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.
A: Like monomials, falling factorials form a basis spanning the polynomials. Write $x^n=\sum_ku_{nk}(x)_k$ so$$[(x)_n]\sum_ra_r(x)_r\sum_sb_s(x)_s=\sum_{mrs}a_rb_su_{mn}\underbrace{[x^m](x)_r(x)_s}_{\in\Bbb Z},$$where $[f_j]g$ denotes the coefficient of a basis element $f_j$ in $g$. Now we just need to check the $u_{nk}$ are integers. Indeed $u_{nn}=1,\,x^n-(x)_n=\sum_ku_{(n-1)k}(x)_k$ obtains the $u_{nk}$ with $k<n$ as linear combinations over $\Bbb Z$ of the $u_{(n-1)k}$.
