CSCE 222 Lecture 24

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

Generating Functions (cont'd)

For $A = {\underset{n + 1}{\underset{⏟}{1, \dots, 1}}, 0, 0, \dots}$ , 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 + a x)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} x^{k} = 1 + (\binom{n}{1}) a x + (\binom{n}{2}) a^{2} x^{2} + \dots + a^{n} x^{n}$	$(\binom{n}{k}) a^{k}$
${(1 + x^{r})}^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{r k} = 1 + (\binom{n}{1}) x^{r} + (\binom{n}{2}) x^{2 r} + \dots + x^{r n}$	$(\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 - a x} = \sum_{k = 0}^{\infty} a^{k} x^{k} = 1 + a x + a^{2} x^{2} + \dots$	$a^{k}$
$\frac{1}{1 - x^{r}} = \sum_{k = 0}^{\infty} x^{r k} = 1 + x^{r} + x^{2 r} + \dots$	1 if $r$ divides $k$ ; 0 otherwise
$\frac{1}{(1 - x)^{2}} = \sum_{k = 0}^{\infty} (k + 1) x^{k} = 1 + 2 x + 3 x^{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 - a x)^{n}} = \sum_{k = 0}^{\infty} (\binom{n + k - 1}{k}) a^{k} x^{k} = 1 + (\binom{n}{1}) a x + (\binom{n + 1}{2}) a^{2} x^{2} + \dots$	$(\binom{n + k - 1}{k}) a^{k} = (\binom{n + k - 1}{n - 1}) a^{k}$
$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 = {1, 1, \frac{1}{2!}, \frac{1}{3!}, \dots}$ 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 + x)^{- n} = \sum_{k = 0}^{\infty} (\binom{- n}{k}) x^{k} = \sum_{k = 0}^{\infty} (- 1)^{k} (\binom{n + k - 1}{k}) x^{k}$
$(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}, \dots)$ 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{2 n}{n})$

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

(\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

(\binom{n}{k}) = (\binom{n}{n - k})

.

Q.E.D.

CSCE 222 Lecture 24

Contents

Generating Functions (cont'd)

Example

Extended Binomial Coefficient

Applications of Generating Functions

Example

Example

Navigation menu

CSCE 222 Lecture 24

Generating Functions (cont'd)

Example

Extended Binomial Coefficient

Applications of Generating Functions

Example

Example

Navigation menu

Search