\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

\renewcommand{\ang}[1]{\left\langle #1 \right\rangle}

\begin{document}

From simple convolution we know that
\begin{eqnarray*}
\langle 1,1,1,1,1,\ldots\rangle	& \iff 	& \frac{1}{1-x} \\
\ang{1,2,3,4,5,\ldots} 	& \iff 	& \frac{1}{(1-x)^2}\\
\ang{1,3,6,10,15,\ldots}& \iff 	& \frac{1}{(1-x)^3}\\
\ang{1,4,10,20,\ldots} 	& \iff 	& \frac{1}{(1-x)^4}
\end{eqnarray*}
and from Pascal's triangle, we know that 
\begin{eqnarray*}
\ang{ {n\choose 0}}  =  \ang{1,1,1,1,1,\ldots} &\iff &\frac{1}{1-x}\\
\ang{ {n\choose 1}}  =  \ang{0,1,2,3,4,5,\ldots}& \iff& \frac{x}{(1-x)^2}\\
\ang{ {n\choose 2}}  =  \ang{0,0,1,3,6,10,15,\ldots}& \iff& 
	\frac{x^2}{(1-x)^3}\\
\ang{ {n\choose 3}}  =  \ang{0,0,0,1,4,10,20,\ldots} & \iff& 
\frac{x^3}{(1-x)^4}\\
\ang{ {n\choose k}}  & \iff & \frac{x^k}{(1-x)^{k+1}}.
\end{eqnarray*}
(We could derive the same result by expanding $x^k/(1-x)^{k+1}$
with the binomial theorem.)

We can compute the generating function of a sequence described by 
an arbitrary polynomial, $\ang{ p(n) }$ where $p(n) = \sum_i p_i n^i$ by
first expressing the polynomial as $p(n) = \sum_i q_i {n\choose i}$ and
then summing the generating functions for each $ {n\choose i}$.

For example, take the sequence $\ang{a_n}$ described by 
$$a_n = n(n+2) = n(n+1) + n = 2{n+1\choose 2} + {n\choose 1}.$$
The generating function is thus
$$ 2\frac{1}{x}\frac{x^2}{(1-x)^3} +  \frac{x}{(1-x)^2} 
	= \frac{3x-x^2}{(1-x)^3}.$$

\newpage
In fact, it is known how to convert from the usual basis of $\{x^n\}_n$ 
for polynomials to the basis of falling factorials $\{ (x)_n\}_n$.  
The coefficients are given exactly by the Stirling numbers of the second kind:
$$ x^n = \sum_{k=1}^n S(n,k) (x)_k.$$
For example, $x^3 = x(x-1)(x-2) + 3x(x-1) + x$, where $S(3,3)=S(3,1)=1$
and $S(3,2)=3$.
This is easily seen combinatorially, since the LHS is clearly the number of 
ways to color an $n$-set with $x$ colors, and the RHS is the same:
for the number $k$ of colors actually used, first partition the set into
color classes, then assign colors in all $(x)_k$ possible ways.
Alternatively we have
$$ x^n = \sum_{k=1}^n S(n,k) {x \choose k}k!.$$

So it is possible to give a ``closed form'' for the generating function
of a sequence described by an arbitrary polynomial $p(n)$.
First write
$$ p(n)=\sum_i p_i n^i=\sum_i p_i \sum_{k=1}^i S(i,k) k! {n\choose k},$$
and then deduce the generating function:
$$ P(x) = \sum_i p_i \sum_{k=1}^i S(i,k) k! \frac{x^{k-1}}{(1-x)^k}.$$

To find generating functions for polynomials of degree 4 or less, 
you really only need to know the non-immediate ($\neq 1$) Stirling numbers
$S(3,2)=3$, $S(4,2)=7$, and $S(4,3) = {4\choose 2} = 6$.
(There is a closed form for $S(n,k)$, based on inclusion-exclusion, 
so we could take the ``closed form'' above even a step further.)

For example, to compute the generating function of the sequence
$\ang{a_n}$ where $a_n = n^4 + 3n^3 -n^2 +5n - 7$, 
use the conversions
\begin{eqnarray*}
n^2 = (n)_2 + (n)_1 & = & 2!{n\choose 2} + {n\choose 1}\\
n^3 = (n)_3 + 3(n)_2 + (n)_1 &=& 3!{n\choose 3}+3\cdot 2!{n\choose 2}
+{n\choose 1}\\
n^4 = (n)_4 + 7(n)_3 + 6(n)_2 + (n)_1 
& = & 4!{n\choose 4} + 7\cdot 3!{n\choose 3}+6\cdot 2!{n\choose 2}+{n\choose 1}
\end{eqnarray*}
to obtain
$$
a_n = 24{n\choose 4} + (42 + 18){n\choose 3} + (12+18-2){n\choose 2} +  
(1+3-1+5){n\choose 1} + (-7){n\choose 0}$$
giving the generating function
$$
A(x) = 24\frac{x^4}{(1-x)^5} + 60\frac{x^3}{(1-x)^4}
	+ 28\frac{x^2}{(1-x)^3} + 8\frac{x}{(1-x)^2} - 7\frac{1}{(1-x)}.
$$
\end{document}


