Thursday, April 3, 2014

Catalan numbers, EGFs, derangements, Bell numbers

1Generating functions for Catalan numbers¶

Last time, we derived the following generating function for Catalan numbers:

$$C(x) = \sum_{n \geq 0} c(n) x^n = \frac{1-\sqrt{1-4x}}{2x}$$

Now recall that $\displaystyle c(n) = \frac{1}{n+1} \binom{2n}{n}$.

How do we get this from the ogf? Well, we have:

$$\begin{align} 2x \cdot C(x) & = 1 - \sqrt{1-4x} \\ \therefore \; 2x \cdot \sum_{n \geq 0} c(n) \cdot x^n & = 1-\sqrt{1-4x} \\ \therefore \; c(x) & = \frac{[x^{n+1}] (1-\sqrt{1-4x})}{2} \end{align}$$

But what is $\sqrt{1-4x}$? Well, what if we we wrote it as $(1-4x)^{1/2}$? Recall that $(1-4x)^r$ can be expanded using the binomial theorem:

$$(1+y)^r = \sum_{k \geq 0} \binom{r}{k} y^k$$

But this doesn't really work for non-integer values of $r$. So instead, we use the generalised binomial theorem (Newton, 1665):

$$(1+y)^r = \sum_{k \geq 0} \binom{r}{k}y^k \tag{where $\displaystyle \binom{r}{k} = \frac{r(r-1) \cdots (r-k+1)}{k!}$}$$

Then, we can $(1-4x)^{1/2}$ as follows:

$$\begin{align} (1-4x)^{1/2} & = \sum_{k \geq 0} \binom{1/2}{k} (-4x)^k \\ & = \binom{1/2}{0} + \sum_{k \geq 0} \binom{1/2}{k} (-4x)^k \\ & = 1 + \sum_{k \geq 1} \frac{1/2 - 1/2 - 3/2 - 5/2 - \cdots - \frac{(2k-3)}{2}}{k!} \cdot (-1)^k4^kx^k \\ & = 1 - \sum_{n \geq 0} \frac{\frac{(2k-3)}{2} \cdot \frac{(2k-5)}{2} \cdots \frac{5}{2} \cdot \frac{3}{2} \cdot \frac{1}{2} \cdot \left ( -\frac{1}{2} \right )}{k!} \cdot 2^k \cdot 2^k \cdot x^k \\ & = 1 - \sum_{k \geq 1} \frac{(2k-3) \cdots 5\cdot 3 \cdot 1 \cdot 1 \cdot 2^k \cdot x^k}{k!} \\ & = \text{fuck it I don't care} \end{align}$$

Anyway, in the end, you get

$$c(n) = \frac{1}{2} [x^{n+1}] \sum_{k \geq 1} \frac{2}{k} \binom{2k-2}{k-1} x^k = \frac{1}{n+1} \binom{2n}{n}$$

2Manipulating exponential generating functions¶

Let $\displaystyle \hat F = \sum_{n\geq 0}f(n) \frac{x^n}{n!}$. Then:

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

Also:

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

Products:

$$\begin{align} \hat H(x) \cdot \hat G(x) & = \left ( h(0) + h(1) \frac{x^1}{1!} + \frac{h(2)}{2!} x^2 + \cdots \right ) \cdot \left ( g(0) + g(1) \frac{x^1}{1!} + \cdots \right )\\ & = \sum_{n \geq 0} \left ( \sum_{k=0}^n \binom{n}{k} \frac{1}{n!} h(k) g(n-k) \right ) \cdot x^n \tag{since $\binom{n}{k} = \left ( \frac{n!}{k!(n-k)!} \right )$ apparently?} \\ & = \sum_{n\geq 0} \left ( \sum_{k=0}^n \binom{n}{k} h(k)g(n-k) \right ) \frac{x^n}{n!} \\ & = \sum_{k=0}^n h(k) \frac{x^n}{n!} \cdot \frac{g(n-k)x^{n-k}}{(n-k)!} \end{align}$$

Note: it's the product rule which determines which type of generating function would be most useful for your particular problem. For example, OGFs are best for counting unlabelled objects, while EGFs are best for counting labelled objects (which is where the $\binom{n}{k}$ comes from).

2.1Derangements example¶

A derangement is a permutation $\pi$ such that $\pi_i \neq i$ $\forall i$.

Let $d(n)$ be the number of derangements on $[n] = \{1, 2, 3, \ldots, n\}$.

Let $h(n)$ be the number of fixed permutations (i.e., ways of permuting $[n]$ without changing it at all); obviously there is only one way of doing so, thus, $h(n)=1$.

Let $f(n) = n!$, which is the total number of permutations.

Our claim:

$$f(n) = n! = \sum_{k=0}^n \binom{n}{k} \cdot h(k) \cdot d(n-k) = \sum_{k=0}^n \binom{n}{k} d(n-k)$$

We can think of this problem as that of a postman, trying to deliver letters to houses. (Why? Not sure.) In any case, we have:

$$\hat F(x) = \sum_{n \geq 0}f(n) \frac{x^n}{n!} = \sum_{n \geq 0} \left ( \sum_{k=0}^n \binom{n}{k} \cdot h(k) \cdot d(n-k) \right ) \frac{x^n}{n!}$$

So by the product rule (from before), we have:

$$\hat F(x) = \hat H(x) \cdot \hat D(x)$$

Thus we have $\displaystyle \hat D(x) = \frac{\hat F(x)}{\hat H(x)}$. Let's find $\hat H(x)$, using the fact that $h(n) =1$:

$$\hat H(x) = \sum_{n \geq 0} h(n) \cdot \frac{x^n}{n!} = \sum_{n \geq 0} \frac{x^n}{n!} = e^x$$

Now let's find $\hat F(x)$, using the fact that $f(n) = n!$:

$$\hat F(x) = \sum_{n \geq 0} f(n) \frac{x^n}{n!} = \sum_{n \geq 0} \cancel{n!} \cdot \frac{x^n}{\cancel{n!}} = \frac{1}{1-x}$$

Thus we can solve for $\hat D(x)$:

$$\hat D(x) = \frac{\frac{1}{1-x}}{e^x} = \frac{e^{-x}}{1-x}$$

Using this, we can find $d(n)$. We have that

$$\sum_{n \geq 0} d(n) \frac{x^n}{n!} = \frac{e^{-x}}{1-x} = (1+x+x^2+\cdots)\cdot (1-\frac{x^1}{1!} + \frac{x^2}{2!} - \frac{x^3}{3!} + \cdots)$$

Hence:

$$\frac{d(n)}{n!} = [x^n](1+x+x^2+\cdots)\cdot (1-\frac{x^1}{1!} + \frac{x^2}{2!} - \frac{x^3}{3!} + \cdots) = \sum_{k=0}^n \frac{(-1)^k}{k!}$$

Thus we can approximate $d(n)$ as follows:

$$d(n) = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!} \approx n!\cdot e^{-1}$$

Not sure if correct

3Bell numbers¶

Let $b(n)$ be the number of ways to partition an $n$-set into parts.

For example, $b(3)=5$, because we have $123$, $1-23$, $2-13$, $3-12$, and $1-2-3$. Similarly, $b(4)=15$.

The recurrence relation is as follows:

$$b(n+1) = \sum_{k=0}^n \binom{n}{n-k} b(k) = \sum_{k=0}^n \binom{n}{k} b(k) \tag{by symmetry of binomials}$$

Here's why. Suppose the number $n+1$ goes into the same partition as $(n-k)$ other numbers. Then, $\displaystyle \binom{n}{n-k}$ represents the number of distinct ways of picking these $n-k$ numbers. Furthermore, I can partition the other $k$ numbers in $b(k)$ ways.

Recall, by the shift rule from last lecture, that

$$\sum_{n \geq 0} b(n+1) \frac{x^n}{n!} = DB(x) \tag{?}$$

Furthermore,

$$\sum_{n \geq 0} b(n+1) \frac{x^n}{n!} = \sum_{n \geq 0} \left ( \sum_{k=0}^n \binom{n}{k} \cdot 1 \cdot b(k) \right ) \frac{x^n}{n!} = \hat B(x) \cdot \sum_{n \geq 0} 1 \cdot \frac{x^n}{n!} = e^x \cdot \hat B(x)$$

Thus, we conclude:

$$D\hat B(x) = e^x \cdot \hat B(x)$$

Solve to get $\hat B(x) = c \cdot \exp(e^x)$. Since $b(0) = 1$, we get $c= 1/e$. The full derivation is left as an exercise because I'm not really following.