Tuesday, April 1, 2014

Generating functions continued

1Generating functions continued¶

1.1Making change¶

What is the number of ways to change \$$n$ into bills of the following denominations: \$1, \$5 and \$10?

The generating function is

$$\begin{align} B(x) & = \sum_{n \geq 0} b(n) \cdot x^n \\ & = \underbrace{(1+x + x^2 + x^3 + \cdots)}_{\text{\$1 bills}} \cdot \underbrace{(1+x^5 + x^{10} + x^{15} + \cdots)}_{\text{\$5 bills}} \cdot \underbrace{(1+x^{10} + x^{20} + x^{30} + \cdots)}_{\text{\$10 bills}} \\ & = \left ( \frac{1}{1-x} \right ) \cdot \left ( \frac{1}{1-x^5} \right ) \cdot \left ( \frac{1}{1-x^{10}} \right ) \end{align}$$

It's not trivial to get $b(n)$ from here. We need to rewrite $B(x)$ so that all the terms have a denominator of $(1-x^{10})$.

For the first term, we use the fact that $(1-x^{10}) = (1+x+x^2 + \cdots + x^9)(1-x)$, and so

$$\frac{1}{1-x} = \frac{1+x+x^2+\cdots+x^9}{1-x^{10}}$$

For the second term, we can use the fact that $(1-y)(1+y) = 1-y^2$ and so $\displaystyle \frac{1+y}{1-y^2} = \frac{1}{1-y}$. If we let $y=x^5$, we have that

$$\frac{1+x^5}{1-x^{10}} = \frac{1}{1-x^5}$$

Thus:

$$B(x) = \left ( \frac{1+x+x^2+\cdots+x^9}{1-x^{10}} \right ) \cdot \left ( \frac{1+x^5}{1-x^{10}} \right ) \cdot \left ( \frac{1}{1-x^{10}} \right ) = \frac{(1+x+x^2+\cdots+x^9)(1+x^5)}{(1-x^{10})^3}$$

Consequently, $b(n)$ is simply the coefficient of $x^n$ in $B(x)$:

$$b(n) = [x^n]\frac{(1+x+x^2+\cdots+x^9)(1+x^5)}{(1-x^{10})^3}$$

It gets a bit messy from here so we're not going to simplify it any further.

1.2Compositions¶

Suppose we want to pick $k$ numbers, $a_1, a_2, \ldots, a_k$, from the set $A$, such that $a_1 + a_2 + \cdots + a_k = n$. Note that repeating numbers are allowed - for example, if $A = \{1, 2\}$, then we could make the number 3 using $1 + 1+ 1$ or $1 + 2$ - and $k$ is not fixed. How many distinct ways of making this sum are there?

Let $g(n)$ be the number of ways of making this sum. The ordinary generating function is then

$$G(x) = \sum_{n \geq 0} g(n) \cdot x^n = \sum_{n \geq 0} \left ( \sum_{k \geq 0} c_k^A(n) \right ) \cdot x^n = \sum_{k \geq 0 } \left ( \sum_{n \geq 0} c_k^A(n) \cdot x^n \right )$$

where $c_k^A$ is the number of compositions with $k$ points using $A$ as our alphabet (i.e., the set from which we can choose numbers).

Note that

$$\sum_{k \geq 0} \underbrace{(x+x^2) \cdots (x+x^2)}_{k \, \text{times}} = \sum_{k \geq 0} (x+x^2)^k = \frac{1}{1-(x+x^2)^k} = \frac{1}{1-x-x^2} \tag{what?}$$

is the generating function for the Fibonacci numbers, shifted by $1+x$^{what? how?}. So $g(n) = g(n-1) + g(n-2)$.

More generally:

$$G^A(x) = \sum_{k \geq 0} \left ( \sum_{i \in A} x^i \right )^k = \frac{1}{1-\sum_{i \in A} x^i}$$

For example, if $A = \{z \in \mathbb Z | z \geq 2\}$, then

$$G^A(x) = \frac{1}{1-\sum_{i \geq 2} x^i} = \frac{1}{1-x^2 \cdot \sum_{i \geq 0} x^i} = \frac{1}{1-x^2\cdot \frac{1}{1-x}} = \frac{1-x}{1-x-x^2}$$

which is the Fibonacci numbers again!

Explanations need improvement

1.3Manipulating generating functions¶

Let $F(x) = \sum_{n \geq 0} f(n) \cdot x^n$ be an ogf. Here are some possible manipulations:

1.3.1Multiplication by $x^k$¶

$$\sum_{n\geq 0}f(n)\cdot x^{n+k} = x^k\sum_{n \geq 0} f(n) \cdot x^n = x^k F(x)$$

1.3.2Shifting by $k$¶

$$\sum_{n \geq 0}f(n + k) x^n = \frac{F(x) - f(0) - f(1)x - f(k-1)x^{k-1}}{x^k}$$

1.3.3Differentiation¶

Let $xD$ be shorthand for $\displaystyle x \cdot \frac{d}{dx}$. Then:

$$xD F(x) = \sum_{n \geq 0} nf(n)x^n$$

$$(xD)^k F(x) = \sum_{n \geq 0} n^k f(n)x^n$$

For example, if $f(n) = 1 \, \forall n$, then $\displaystyle F(x) = \frac{1}{1-x}$. Then, suppose we have some function $H(x)$ which is defined in terms of $f(n)$:

$$H(x) = \sum_{n \geq 0} n^2 \cdot x^n \cdot f(n) = \sum_{n \geq 0} n^2 \cdot x^n \cdot (xD)^2 F(x)$$

To find an explicit expression for $(xD)^2F(x)$, we simply differentiate:

$$\begin{align} (xD) F(x) & = x\frac{d}{dx} (1-x^{-1}) = x(1-x)^{-2} \tag{for the first derivative} \\ \therefore \; (xD)^2 F(x) & = xD \left ( \frac{x}{(1-x)^2} \right ) = \frac{x(1+x)}{(1-x)^3} \tag{for the second derivative} \end{align}$$

1.3.4Products of generating functions¶

$$H(x) \cdot G(x) = \sum_{n \geq 0} \left ( \sum_{k =0}^n h(k) \cdot g(n-k) \right ) x^n$$

For example, if $g(n) = 1 \; \forall n$, then $\displaystyle G(x) = \frac{1}{1-x}$, and so

$$H(x) \cdot G(x) = \sum_{n \geq 0} \left ( \sum_{k =0}^n h(k) \right ) x^n$$

We can use this to calculate $\displaystyle \sum_{k=0}^n k^2$. Let $h(k) = k^2$. Then:

$$H(x) \cdot \frac{1}{1-x} = \sum_{n \geq 0} \left ( \sum_{k=0}^n k^2 \right )x^n$$

If we solve for $H(x)$, we get:

$$H(x) = \sum_{n \geq 0} k^2 x^k = \frac{x(1+x)}{(1-x)^3} \tag{somehow. what?}$$

Now let's try to find the coefficient of $x^n$ in $H(x) \cdot G(x)$:

$$[x^n] H(x) \cdot G(x) = [x^n] \left ( \frac{x(1+x)}{(1-x)^3} \right ) \cdot \left ( \frac{1}{1-x} \right ) = [x^n] \left ( \frac{x(1+x)}{(1-x)^4} \right ) = \binom{n+3}{3}$$

using the fact that the coefficient of $\displaystyle \frac{1}{(1-x)^k}$ is $\displaystyle \binom{n+k-1}{k-1}$ for some reason. Thus:

$$\begin{align} [x^n] \frac{x+x^2}{(1-x)^4} & = [x^n] \frac{x}{(1-x)^4} + [x^n] \frac{x^2}{(1-x)^4}\\ & = [x^{n-1}] \frac{1}{(1-x)^4} + [x^{n-2}] \frac{1}{(1-x)^4} \\ & = \binom{n+2}{3} + \binom{n+1}{3} \tag{using the binomial thing shown earlier} \\ & = \frac{n(n+1)(2n+1)}{6} \end{align} $$

1.4Catalan numbers example¶

Let $c(n)$ be the number of distinct Catalan numbers of length $n$. The recurrence relation is given by

$$c(n+1) = \sum_{j=0}^n c(j) \cdot c(n-j)$$

due to the fact that if we look at the first time we hit the $y$-axis ($x=2j+2$), we have a Dyck walk of length $2j$ on the left side and another of length $2(n-j)$ on the other side. (Expound? Diagram?)

Let $c(n)$ be the number of distinct Catalan numbers of length $n$. The recurrence relation is given by

$$c(n+1) = \sum_{j=0}^n c(j) \cdot c(n-j)$$

due to the fact that if we look at the first time we hit the $y$-axis ($x=2j+2$), we have a Dyck walk of length $2j$ on the left side and another of length $2(n-j)$ on the other side. (Expound? Diagram?)

Thus we have:

$$\begin{align} C(x) & = \sum_{n \geq 0} c(n) \cdot x^n = c(0) + \sum_{n \geq 1} c(n) \cdot x^n \\ & = 1 + \sum_{n \geq 0} c(n+1) \cdot x^{n+1} = 1 + x \cdot \sum_{n \geq 0} c(n+1) \cdot x^n \\ & = 1 + x\cdot \sum_{n \geq 0} \left ( \sum_{j=0}^n C(j) \cdot c(n-j) \right ) x^n \\ & = 1 + x\cdot C(x)^2 \end{align}$$

Using the quadratic formula, we can solve for $C(x)$:

$$C(x) = \frac{1\pm\sqrt{1-4x}}{2x}$$

But wait, there's a $\pm$ there, and there can be only one expression for $C(x)$. Clearly we have to get rid of one of the possibilities. Apparently we can use the base case of $C(0) = 1$ (though I'm not sure where we got this base case from?) to eliminate the $+$ option, so we just have

$$C(x) = \frac{1-\sqrt{1-4x}}{2x}$$