Catalan Number

THEOREM: The $n$th Catalan number $C_n$ is the number of solutions of the system

and is equal to $\displaystyle\frac{1}{n+1}\binom{2n}{n}$.

• $\mathcal{C}_n$ is the set of all solutions of the system
  • $\boldsymbol{x_i \mapsto 1 – 2x_i}$: a bijection from $\mathcal{C}_n$ to the ballot sequences of length $2n$ // $\boldsymbol{|\mathcal{C}_n| = C_n}$
• $\mathcal{T}_n$: the set of all T-routes from $(1,2)$ to $(2n, 1)$ above the x-axis//?$\boldsymbol{|C_n| = |\mathcal{T}_n|}$
• A map$\boldsymbol{f: \mathcal{C}_n \to \mathcal{T}_n}$ Given a solution $(x_1, x_2, \dots, x_{2n}) \in \mathcal{C}_n$,
  • Let $P_i = \left(i, 1 + 1 – 2x_1 + \cdots + 1 – 2x_i\right)$ for all $i = 1,2, \dots, 2n$
  • $1 + 1 – 2x_1 + \cdots + 1 – 2x_i > 0$ for $i = 1,2, \dots, 2n$
  • $P_1 = (1, 1 + 1 – 2x_1) = (1,2)$;
    $P_{2n} = (2n, 1)$
  • $P_i – P_{i-1} = (1, 1 – 2x_i) \in {(1,1), (1,-1)},\ i = 2, \dots, 2n$
  • $P_1, P_2, \dots, P_{2n}$ is a T-route above the x-axis
• A map$\boldsymbol{g: \mathcal{T}_n \to \mathcal{C}_n}$: Given a T-route $(1,2)$ to $(2n, 1)$ above the x-axis, say $\{P_i(u_i, v_i): i \in [2n]\}$,
  • $(u_1, v_1) = (1,2), (u_{2n}, v_{2n}) = (2n, 1)$
  • $x_1 = \frac{2 – v_1}{2} = 0$
  • $x_i = \frac{1 – (v_i – v_{i-1})}{2} \in \{0,1\},\ i = 2, \dots, 2n$
  • $x_1 + x_2 + \cdots + x_{2n} = \frac{2n + 1 – v_{2n}}{2} = n$
  • $x_1 + x_2 + \cdots + x_i = \frac{i + 1 – v_i}{2} \leq \frac{1}{2},\ i = 1,2, \dots, 2n$
• $A = P_1 = (1,2)$: $a = 1, \alpha = 2$;
  $B = P_{2n} = (2n, 1)$: $b = 2n, \beta = 1$
  • $\displaystyle |\mathcal{C}_n| = \frac{(2n-1)!}{(n-1)!n!} – \frac{(2n-1)!}{(n+1)!(n-2)!} = \frac{(2n)!}{n!(n+1)!} = \frac{1}{n+1}\binom{2n}{n}$

Combinations of Sets

DEFINITION: Let $A = \{a_1, \dots, a_n\}$ and let $r \in \{0,1, \dots, n\}$. An $r$-combination of $A$ is simply an $r$-subset of $A$. // for simplicity, we may use $A = [n]$

• $\{a_{i_1}, \dots, a_{i_r}\}$ with $1 \leq i_1 < i_2 < \dots < i_r \leq n$

THEOREM: For all $n \in \mathbb{Z}^+$ and $r \in \{0,1, \dots, n\}$, the number of $r$-combinations of an $n$-element set is $\binom{n}{r} = \frac{n!}{r!(n-r)!}$.

DEFINITION: Let $A = \{a_1, \dots, a_n\}$ and let $r \geq 0$. An $r$-combination (with repetition) of $A$ is a multiset $\{x_1 \cdot a_1, \dots, x_n \cdot a_n\}$ of $A$ of $r$ elements, where $x_1, \dots, x_n \geq 0$ are integers and $x_1 + \dots + x_n = r$. // for simplicity, we may use $A = [n]$

• $\{a_{i_1}, \dots, a_{i_r}\}$ with $1 \leq i_1 \leq i_2 \leq \dots \leq i_r \leq n$

THEOREM: For all $n \in \mathbb{Z}^+$ and $r \geq 0$, the number of $r$-combinations (with repetition) of an $n$ element set is $\binom{n + r – 1}{r}$.

• $\mathcal{U}$: the set of all $r$-combinations of $[n]$with repetition
• $\mathcal{V}$: the set of all $r$-combinations of $[n + r – 1]$without repetition
  • Let $U = \{u_1, u_2, \dots, u_r\} \in \mathcal{U}$ and $1 \leq u_1 \leq u_2 \leq \dots \leq u_r \leq n$.
    • $1 \leq u_1 < u_2 + 1 < u_3 + 2 < \dots < u_r + r – 1 \leq n + r – 1$
      • $\{u_1, u_2 + 1, \dots, u_r + r – 1\} \in \mathcal{V}$
      • $f: \mathcal{U} \to \mathcal{V},\ \{u_1, u_2, \dots, u_r\} \mapsto \{u_1, u_2 + 1, \dots, u_r + r – 1\}$
    • $f$ is a bijection. Hence, $|\mathcal{U}| = |\mathcal{V}| = \binom{n + r – 1}{r}$

THEOREM: The number of natural number solutions of the equation $x_1 + x_2 + \dots + x_n = r$ is $\binom{n + r – 1}{r}$.

• $\mathcal{X} = \{(x_1, \dots, x_n): x_1, \dots, x_n \in \mathbb{N}$ and $x_1 + \dots + x_n = r\}$
• $\mathcal{Y}$: the set of all $r$-combinations of $[n]$ with repetition
• $f: \mathcal{X} \to \mathcal{Y},\ (x_1, \dots, x_n) \mapsto \{x_1 \cdot 1, x_2 \cdot 2, \dots, x_n \cdot n\}$
• $f$ is a bijection. Hence, $|\mathcal{X}| = |\mathcal{Y}| = \binom{n + r – 1}{r}$.

Combinations of Multiset

DEFINITION: Let $A = \{n_1 \cdot a_1, \dots, n_k \cdot a_k\}$ be an $n$-multiset. Let $r \in \{0,1, \dots, n\}$. An $r$-combination of $A$ is an $r$-subset (multiset) of $A$.

• $\{x_1 \cdot a_1, x_2 \cdot a_2, \dots, x_k \cdot a_k\}$, where $0 \leq x_i \leq n_i$ for every $i \in [k]$ and $x_1 + x_2 + \dots + x_k = r$.

EXAMPLE: $A = \{1 \cdot a, 2 \cdot b, 3 \cdot c\}$

• $\{1 \cdot b, 2 \cdot c\}$ is a 3-combination of $A$; a 3-subset of $A$

REMARK: understanding combinations of a set with those of a multiset

• For every $r \in \{0,1, \dots, n\}$, an $r$-combination of $A = \{a_1, a_2, \dots, a_n\}$ without repetition is an $r$-combination of $\{1 \cdot a_1, 1 \cdot a_2, \dots, 1 \cdot a_n\}$.
• For every $r \geq 0$, an $r$-combination of $A = \{a_1, a_2, \dots, a_n\}$ with repetition is an $r$-combination of $\{\infty \cdot a_1, \infty \cdot a_2, \dots, \infty \cdot a_n\}$.

Inverse Binomial Transform

DEFINITION: The binomial transform of $\{a_n\}_{n\geq s}$ is a sequence $\{b_n\}_{n\geq s}$ s.t.

DEFINITION: The inverse binomial transform of $\{b_n\}_{n\geq s}$ is a sequence $\{a_n\}_{n\geq s}$ s.t.

QUESTION: Given (1), how to find the sequence $\{a_n\}$?

• Answer: $\{a_n\}$ is the inverse binomial transform of $\{b_n\}$
• Application: determine $\{a_n\}$ via $\{b_n\}$

Combinatorial Proofs

DEFINITION: A combinatorial proof of an identity $L = R$ is

• a double counting proof, showing that $L, R$ count the same set but in different ways:
  • $L = |X| = R$ and $L, R$ count $|X|$ in different ways.
• a bijective proof, which shows a bijection between the sets counted by $L$ and $R$:
  • $L = |X|, R = |Y|$ and there is a bijection $f: X \to Y$.

EXAMPLE: $\binom{n}{i} = \binom{n}{n-i}$

• $X = \{s \in \{0,1\}^n: s$ contains $i$ 0’s$\} = \{s \in \{0,1\}^n: s$ contains $n-i$ 1’s$\}$
  • $\binom{n}{i} = |X|$
  • $\binom{n}{n-i} = |X|$

LEMMA: $\binom{n}{k}\binom{k}{i} = \binom{n}{i}\binom{n-i}{k-i}$ for any $n,k,i \in \mathbb{N}$ such that $n \geq k \geq i$.

• Let $U = \{u_1, u_2, …, u_n\}$ be a finite set of $n$ elements
• Let $X = \{(A,B): A \subseteq U, |A| = k, B \subseteq A, |B| = i\}$
  • choose $A$ then choose $B$: $|X| = \binom{n}{k}\binom{k}{i}$
  • choose $B$ then choose $A$: $|X| = \binom{n}{i}\binom{n-i}{k-i}$

LEMMA: $\sum_{k=i}^n (-1)^{n-k} \binom{n}{k}\binom{k}{i} =\begin{cases}1 & n = i \\0 & n > i\end{cases}$.

• $\binom{n}{k}\binom{k}{i} = \binom{n}{i}\binom{n-i}{k-i}$ as $n \geq k \geq i \geq 0$
• $\textbf{left} = \sum_{k=i}^n (-1)^{n-k} \binom{n}{i}\binom{n-i}{k-i}$
  $= \binom{n}{i} \sum_{k=i}^n (-1)^{(n-i)-(k-i)} \binom{n-i}{k-i}$
  $= \binom{n}{i} \sum_{j=0}^{n-i} (-1)^{(n-i)-j} \binom{n-i}{j}$
  $= \textbf{right}$

LEMMA: Let $n, s \in \mathbb{N}, s \leq n$. Then $\sum_{k=s}^n \underbrace{\sum_{i=s}^k a_{k,i}}_{\alpha_k} = \sum_{i=s}^n \underbrace{\sum_{k=i}^n a_{k,i}}_{\beta_k}$

THEOREM: Let $\{a_n\}, \{b_n\}$ be two sequences s.t. for all $n \geq s$, $a_n = \sum_{k=s}^n \binom{n}{k} b_k$. Then
$b_n = \sum_{k=s}^n (-1)^{n-k} \binom{n}{k} a_k$$(n \geq s)$.

• $\sum_{k=s}^n (-1)^{n-k} \binom{n}{k} a_k = \sum_{k=s}^n (-1)^{n-k} \binom{n}{k} \sum_{i=s}^k \binom{k}{i} b_i = \sum_{i=s}^n \sum_{k=i}^n (-1)^{n-k} \binom{n}{k} \binom{k}{i} b_i = b_n$

Distribution Problems

The Problem Statement: distributing $n$ objects into $k$ boxes

• Objects may be distinguishable (labeled with$\boldsymbol{1,2, \dots, n}$) or indistinguishable (unlabeled)
• Boxes may be distinguishable (labeled with $1,2, \dots, k$) or indistinguishable (unlabeled)
• What is the number of methods of distributing $n$ objects into $k$?

Type 1

Problem: distributing $n$ labeled objects into $k$ labeled boxes

THEOREM: The # of ways of distributing $n$ labeled objects into $k$ labeled boxes such that $n_i$ objects are placed into box $i$ for every $i \in [k]$ is $N_1 = \frac{n!}{n_1! n_2! \dots n_k!}$.

• $S$: the set of the expected distributing schemes
• $|S| = \binom{n}{n_1} \binom{n-n_1}{n_2} \dots \binom{n-n_1-\dots-n_{k-1}}{n_k} = \frac{n!}{n_1! n_2! \dots n_k!}$

REMARK: $N_1 =$ # of permutations of $\{n_1 \cdot 1, …, n_k \cdot k\}$

Type 2

Problem: distributing $n$ unlabeled objects into $k$ labeled boxes

THEOREM: The number of ways of distributing $n$ unlabeled objects into $k$ labeled boxes is $N_2 = \binom{n + k – 1}{n}$.

• $S$: the set of the expected distributing schemes
• $T = \{(n_1, n_2, …, n_k): n_1 + n_2 + \dots + n_k = n; n_1, n_2, …, n_k \in \mathbb{N}\}$
• $f: T \to S$$(n_1, n_2, …, n_k) \mapsto$ a scheme where $n_i$ objects are put into box $i$
  • $f$ is a bijection. Hence, $|S| = |T| = \binom{n + k – 1}{n}$

REMARK: $N_2 =$ # of $n$-combinations of $\{\infty \cdot 1, …, \infty \cdot k\}$