CSCE 222 Lecture 24

« previous | Monday, April 4, 2011 | next »

Generating Functions (cont'd)

For $A=\left\{\underbrace {1,\ldots ,1} _{n+1},0,0,\ldots \right\}$, the generating function is truncated form of a geometric series:

$\sum _{k=0}^{n}x^{k}=1+x+\dots +x^{n}={\frac {1-x^{n+1}}{1-x}}$

Now use what we learned in calculus:

$G(x)$	$a_{k}$
$(1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,x^{k}=1+{\binom {n}{1}}\,x+{\binom {n}{2}}\,x^{2}+\dots +x^{n}$	${\binom {n}{k}}$
$(1+ax)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,a^{k}x^{k}=1+{\binom {n}{1}}\,ax+{\binom {n}{2}}\,a^{2}x^{2}+\dots +a^{n}x^{n}$	${\binom {n}{k}}\,a^{k}$
$\left(1+x^{r}\right)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,x^{rk}=1+{\binom {n}{1}}\,x^{r}+{\binom {n}{2}}\,x^{2r}+\dots +x^{rn}$	${\binom {n}{\frac {k}{r}}}$ if $r$ divides $k$; 0 otherwise.
${\frac {1-x^{n+1}}{1-x}}=\sum _{k=0}^{n}x^{k}=1+x+x^{2}+\dots +x^{n}$	1 if $k\leq n$; 0 otherwise
${\frac {1}{1-x}}=\sum _{k=0}^{\infty }x^{k}=1+x+x^{2}+\dots$	$1$
${\frac {1}{1-ax}}=\sum _{k=0}^{\infty }a^{k}x^{k}=1+ax+a^{2}x^{2}+\dots$	$a^{k}$
${\frac {1}{1-x^{r}}}=\sum _{k=0}^{\infty }x^{rk}=1+x^{r}+x^{2r}+\dots$	1 if $r$ divides $k$; 0 otherwise
${\frac {1}{(1-x)^{2}}}=\sum _{k=0}^{\infty }(k+1)x^{k}=1+2x+3x^{2}+\dots$	$k+1$
${\frac {1}{(1-x)^{n}}}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}\,x^{k}=1+{\binom {n}{1}}\,x+{\binom {n+1}{2}}\,x^{2}+\dots$	${\binom {n+k-1}{k}}={\binom {n+k-1}{n-1}}$
${\frac {1}{(1+x)^{n}}}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}\,(-1)^{k}x^{k}=1-{\binom {n}{1}}\,x+{\binom {n+1}{2}}\,x^{2}-\dots$	$(-1)^{k}{\binom {n+k-1}{k}}=(-1)^{k}{\binom {n+k-1}{n-1}}$
${\frac {1}{(1-ax)^{n}}}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}\,a^{k}x^{k}=1+{\binom {n}{1}}\,ax+{\binom {n+1}{2}}\,a^{2}x^{2}+\dots$	${\binom {n+k-1}{k}}a^{k}={\binom {n+k-1}{n-1}}a^{k}$
$\mathrm {e} ^{x}=\sum _{k=0}^{\infty }{\frac {x^{k}}{k!}}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+\dots$	${\frac {1}{k!}}$
$\ln {(1+x)}=\sum _{k=0}^{\infty }{\frac {(-1)^{k+1}}{k}}\,x^{k}=x-{\frac {x^{2}}{2}}+{\frac {x^{3}}{3}}-{\frac {x^{4}}{4}}+\dots$	${\frac {(-1)^{k+1}}{k}}$

Example

$A=\left\{1,1,{\frac {1}{2!}},{\frac {1}{3!}},\ldots \right\}$ has a generating function of:

$\sum _{k=0}^{\infty }{\frac {x^{k}}{k!}}=e^{x}$

Extended Binomial Coefficient

${\binom {-n}{r}}=(-1)^{r}{\binom {n+r-1}{r}}$

Therefore

1. $(1+x)^{-n}=\sum _{k=0}^{\infty }{\binom {-n}{k}}x^{k}=\sum _{k=0}^{\infty }(-1)^{k}{\binom {n+k-1}{k}}x^{k}$
2. $(1-x)^{-n}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}x^{k}$

Applications of Generating Functions

Used to find the number of $r$-combinations from a set with $n$ elements where repetitions are allowed.

Example

Let $A=(a_{0},a_{1},\ldots )$ be a sequence (repetition allowed) with $a_{r}$ $r$-combintations.

$G(x)=\sum _{k=0}^{\infty }a_{k}x^{k}$

Since we can select any number of a particular element of the set when repetitions are allowed. Each element contributes $(1+x+x^{2}+\dots )$ to the product expansion of $G(x)$:

$G(x)=(1+x+x^{2}+\dots )^{n}={\frac {1}{(1-x)^{n}}}=(1-x)^{-n}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}x^{k}$

Example

Proposition. $\sum _{k=0}^{\infty }{\binom {n}{k}}^{2}={\binom {2n}{n}}$

Proof. Since $\textstyle {\binom {2n}{n}}$ is the coefficient of $x^{n}$ in $(1+x)^{2n}$, it must coincide with the coefficient of $x^{n}$ in $(1+x)^{n}(1+x)^{n}=\left[\textstyle {\binom {n}{0}}+{\binom {n}{1}}x+\dots +{\binom {n}{n}}x^{n}\right]^{2}$.

$\textstyle {\binom {n}{0}}{\binom {n}{n}}+{\binom {n}{1}}{\binom {n}{n-1}}+\dots +{\binom {n}{n}}{\binom {n}{0}}$ is the coefficient of $x^{n}$ in $(1+x)^{n}(1+x)^{n}$, so the proposition must be true since $\textstyle {\binom {n}{k}}={\binom {n}{n-k}}$.

Q.E.D.