Catalan Numbers

EXAMPLE: The $n$th Catalan number is $C_n = \frac{1}{n+1}\binom{2n}{n}$.

• Catalan number: $C_{n+1} = \sum_{k=0}^n C_k C_{n-k}$, $C_0 = 1$
• Let $C(x) = \sum_{n=0}^\infty C_n x^n$ be the generating function of the sequence of Catalan numbers.
• $\sum_{n=0}^\infty C_{n+1} x^n = \sum_{n=0}^\infty \left(\sum_{k=0}^n C_k C_{n-k}\right) x^n = C(x)^2$
• $x \sum_{n=0}^\infty C_{n+1} x^n = \sum_{n=0}^\infty C_{n+1} x^{n+1} = C(x) – 1$
• $x C(x)^2 = C(x) – 1$
• $C(x) = \frac{1 \pm \sqrt{1-4x}}{2x}$
• $\sqrt{1-4x} = (1-4x)^{\frac{1}{2}} = \sum_{n=0}^\infty \binom{\frac{1}{2}}{n} (-4x)^n = 1 – 2x – 2x^2 – \dots$
• $C(x) = \frac{1 + \sqrt{1-4x}}{2x}$? No, because it gives a negative sequence.
• $C(x) = \frac{1 – \sqrt{1-4x}}{2x} = \frac{1}{2x} \left(1 – \sum_{n=0}^\infty \binom{\frac{1}{2}}{n} (-4x)^n\right) = \sum_{n=0}^\infty \frac{1}{n+1}\binom{2n}{n} x^n$

Counting Permutations with GFs

QUESTION: Let $k > 0, N_1, \dots, N_k \subseteq \mathbb{N}$. For every $n \geq 0$, let $a_n$ be the number of $n$-combinations of $[k]$ with repetition where every $i \in [k]$ appears $N_i$ times.

• $a_n = \left|\{(n_1, \dots, n_k): n_1 \in N_1, \dots, n_k \in N_k, n_1 + \dots + n_k = n\}\right|$
  • $a_n$ is the number of ways of distributing $n$ unlabeled objects into $k$ labeled boxes such that $N_i$ objects are sent to box $i$. (Type 2 distribution problem)

THEOREM: $\sum_{n=0}^\infty a_n x^n = \prod_{i=1}^k \sum_{n_i \in N_i} x^{n_i}$.

• $\prod_{i=1}^k \sum_{n_i \in N_i} x^{n_i} = \sum_{n_1 \in N_1} x^{n_1} \cdot \sum_{n_2 \in N_2} x^{n_2} \dots \sum_{n_k \in N_k} x^{n_k}$
  $= \sum_{n=0}^\infty \left(\sum_{n_1 \in N_1, \dots, n_k \in N_k, n_1+\dots+n_k=n} 1\right) x^n$
  $= \sum_{n=0}^\infty a_n x^n$

EXAMPLE: Let $a_n$ be the # of ways of distributing $n$ identical books to 5 persons such that person 1, 2, 3, and 4 receive $\geq 3$, $\geq 2$, $\geq 4$, $\geq 6$ books, respectively. $a_{20} = ?$

• $a_n = \left|\{(n_1, \dots, n_5): n_1 \geq 3, n_2 \geq 2, n_3 \geq 4, n_4 \geq 6, n_5 \geq 0, n_1 + \dots + n_5 = n\}\right|$
• $N_1 = \{3,4, \dots\}$;
  $N_2 = \{2,3, \dots\}$;
  $N_3 = \{4,5, \dots\}$;
  $N_4 = \{6,7, \dots\}$;
  $N_5 = \{0,1,2 \dots\}$
• $\sum_{n=0}^\infty a_n x^n = \prod_{i=1}^5 \sum_{n_i \in N_i} x^{n_i}$
  $= (x^3 + \dots)(x^2 + \dots)(x^4 + \dots)(x^6 + \dots)(1 + x + \dots)$
  $= \frac{x^3}{1-x} \frac{x^2}{1-x} \frac{x^4}{1-x} \frac{x^6}{1-x} \frac{1}{1-x} = \frac{x^{15}}{(1-x)^5}$
  $= x^{15} \sum_{n=0}^\infty \binom{-5}{n} (-1)^n x^n$
  • $a_{20} = \binom{-5}{5} (-1)^5 = \binom{5+5-1}{5} = 126$

QUESTION: Let $k > 0, N_1, \dots, N_k \subseteq \mathbb{N}$. For every $n \geq 0$, let $a_n$ be the number of $n$-permutations of $[k]$ with repetition where every $i \in [k]$ appears $N_i$ times.

• $a_n = \sum_{n_1 \in N_1, n_2 \in N_2, \dots, n_k \in N_k, n_1+n_2+\dots+n_k=n} \frac{n!}{n_1!n_2!\dots n_k!}$
  • $a_n$ is the number of ways of distributing $n$ labeled objects into $k$ labeled boxes such that $N_i$ objects are sent to box $i$ for all $i \in [k]$. (Type 1 distribution problem)

THEOREM: $\sum_{n=0}^\infty \frac{a_n}{n!} x^n = \prod_{i=1}^k \sum_{n_i \in N_i} \frac{x^{n_i}}{n_i!}$.

• $\prod_{i=1}^k \sum_{n_i \in N_i} \frac{x^{n_i}}{n_i!} = \sum_{n_1 \in N_1} \frac{x^{n_1}}{n_1!} \cdot \sum_{n_2 \in N_2} \frac{x^{n_2}}{n_2!} \dots \sum_{n_k \in N_k} \frac{x^{n_k}}{n_k!}$
  $= \sum_{n=0}^\infty \left(\sum_{n_1 \in N_1, n_2 \in N_2, \dots, n_k \in N_k, n_1+\dots+n_k=n} \frac{n!}{n_1!n_2!\dots n_k!}\right) \frac{x^n}{n!}$
  $= \sum_{n=0}^\infty \frac{a_n}{n!} x^n$

EXAMPLE: Find $a_n = \left\{s \in \{1,2,3,4\}^n: s \text{ has an even number of 1s}\right\}$

• $a_n =$ # of $n$-permutations of $\{1,2,3,4\}$ with repetition where 1 appears an even number of times
• $N_1 = \{0,2,4, \dots\}$, $N_2 = N_3 = N_4 = \{0,1,2, \dots\}$
• $\sum_{n=0}^\infty \frac{a_n}{n!} x^n = \left(1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \dots\right) \left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots\right)^3$
  $= \frac{e^x + e^{-x}}{2} \cdot e^{3x}$
  $= \frac{e^{4x} + e^{2x}}{2}$
  $= \frac{1}{2} \sum_{n=0}^\infty \left(\frac{(4x)^n}{n!} + \frac{(2x)^n}{n!}\right)$
• $\frac{a_n}{n!} = \frac{1}{2} \cdot \left(\frac{4^n}{n!} + \frac{2^n}{n!}\right)$
  • $a_n = \frac{4^n + 2^n}{2}$

Stirling Number $S_2(n,j)$

EXAMPLE: Show that $S_2(n,j) = \frac{1}{j!} \sum_{i=0}^j (-1)^i \binom{j}{i} (j-i)^n$ // (Type 3 distribution problem)

• $S_2(n,j) =$ the # of ways of distributing $n$ labeled objects into $j$ unlabeled boxes s.t. no box is empty
• $a_n = T(n,j)$ be the # of ways of distributing $n$ labeled objects into $j$ labeled boxes s.t. no box is empty.
• $a_n = S_2(n,j) \cdot j!$
• $N_1 = N_2 = \dots = N_j = \{1,2, \dots\}$

THEOREM: $\sum_{n=0}^\infty p_j(n) x^n = x^j \prod_{i=1}^j \frac{1}{1-x^i}$ // (Type 4 distribution problem)

• $p_j(n) = p_{j-1}(n-1) + p_j(n-j) \quad (n \geq j)$ // the last entry is 1; otherwise
• $Q_j(x) = \sum_{n=0}^\infty p_j(n) x^n$
  $= \sum_{n=0}^\infty \left(p_{j-1}(n-1) + p_j(n-j)\right) x^n$
  $= \sum_{n=j}^\infty \left(p_{j-1}(n-1) + p_j(n-j)\right) x^n$
  $= \sum_{n=j}^\infty p_{j-1}(n-1) x^n + \sum_{n=j}^\infty p_j(n-j) x^n$
  $= x Q_{j-1}(x) + x^j Q_j(x)$
• $Q_j(x) = \frac{x}{1-x^j} Q_{j-1}(x)= \dots$
  $= \frac{x^{j-1}}{(1-x^j)\dots(1-x^2)} Q_1(x)$
  $= \frac{x^{j-1}}{(1-x^j)\dots(1-x^2)} \frac{x}{1-x}$
  $= x^j \prod_{i=1}^j \frac{1}{1-x^i}$

EXAMPLE: What is the number of ways of distributing 20 unlabeled objects into 5 unlabeled boxes such that no box is empty? That is, $p_5(20) = ?$

• $\sum_{n=0}^\infty p_5(n) x^n = x^5 \prod_{i=1}^5 \frac{1}{1-x^i}$
  $= x^5 \underset{i=1}{{(1 + x + \dots + x^{20} + \dots)}}$
  $\underset{i=2}{{(1 + x^2 + \dots + x^{20} + \dots)}}$
  $\underset{i=3}{{(1 + x^3 + \dots + x^{18} + \dots)}}$
  $\underset{i=4}{{(1 + x^4 + \dots + x^{20} + \dots)}}$
  $\underset{i=5}{{(1 + x^5 + \dots + x^{20} + \dots)}}$
  $= x^5 + x^6 + \dots + 70x^{19} + \boldsymbol{84x^{20}} + \dots$
• $p_5(20) = 84$