Type 3

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

EXAMPLE: Assigning 4 employees $\{a, b, c, d\}$ into 3 unlabeled offices. Each office can contain any number of employees.

• $4\ 0\ 0$: $[abcd\ -\ -]$
• $3\ 1\ 0$: $[abc\ d\ -]\ [abd\ c\ -]\ [acd\ b\ -]\ [bcd\ a\ -]$
• $2\ 2\ 0$: $[ab\ cd\ -]\ [ac\ bd\ -]\ [ad\ bc\ -]$
• $2\ 1\ 1$: $[ab\ c\ d][ac\ b\ d][ad\ b\ c][bc\ a\ d][bd\ a\ c][cd\ a\ b]$

$S_2(n,j)$

1730, Stirling (1692-1770)

DEFINITION: $S_2(n,j)$, the Stirling number of the second kind, is defined as the # of ways of distributing $n$ labeled objects into $j$ unlabeled boxes s.t. no box is empty.

• The number of ways of distributing $n$ labeled objects into $k$ unlabeled boxes is $\sum_{j=1}^k S_2(n,j)$.

THEOREM: $S_2(n,j) = \frac{1}{j!} \sum_{i=0}^{j-1} (-1)^i \binom{j}{i} (j-i)^n$ when $n \geq j \geq 1$.

• $T(n,j)$: the # of ways of distributing $n$ labeled objects into $j$ labeled boxes such that no box is empty
  • $T(n,j) = j! \cdot S_2(n,j)$
• $X$: the set of ways of distributing $n$ labeled objects into $j$ labeled boxes.
  • By the product rule, $|X| = j^n$
• $X_i \subseteq X$: the set of ways where exactly $i$ boxes are used, $i = 1,2, \dots, j$
  • $\{X_1, X_2, \dots, X_j\}$ is a partition of $X$ and $|X_i| = \binom{j}{i} T(n,i)$
  • $j^n = |X| = \sum_{i=1}^j |X_i| = \sum_{i=1}^j \binom{j}{i} T(n,i)$ // $a_j = j^n, b_j = T(n,j), a_j = \sum_{i=1}^j \binom{j}{i} b_i$
  • $T(n,j) = \sum_{i=1}^j (-1)^{j-i} \binom{j}{i} i^n = \sum_{i=0}^{j-1} (-1)^i \binom{j}{i} (j-i)^n$ // inverse binomial transform
• $S_2(n,j) = \frac{1}{j!} \cdot T(n,j) = \frac{1}{j!} \sum_{i=0}^{j-1} (-1)^i \binom{j}{i} (j-i)^n$

Type 4

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

EXAMPLE: # of ways of distributing 4 identical books into 3 identical boxes.

• $4\ 0\ 0$
• $3\ 1\ 0$
• $2\ 2\ 0$
• $2\ 1\ 1$

REMARK: The schemes are determined by $\{n_1, \dots, n_k\}$

Partitions of Integers

DEFINITION: $n = a_1 + a_2 + \dots + a_j$ is called an $n$-partition with exactly $j$ parts if $a_1 \geq a_2 \geq \dots \geq a_j$ are all positive integers.

• $p_j(n) = \left|\left\{\left(a_1, \dots, a_j\right): a_1 + \dots + a_j = n, a_1 \geq a_2 \geq \dots \geq a_j \geq 1 \text{ are integers}\right\}\right|$
  • $p_j(n)$: the # of ways of writing $n$ as the sum of $j$ positive integers.
  • $p_1(n) = 1$, $p_n(n) = 1$

EXAMPLE: The integer 4 has 4 different partitions into $\leq 3$ parts

• $4 = 4$
• $4 = 3 + 1$
• $4 = 2 + 2$
• $4 = 2 + 1 + 1$

REMARK: solution to the type 4 problem $= \sum_{j=1}^k p_j(n)$

THEOREM: For $n \in \mathbb{Z}^+$, $j \in [n]$, $p_j(n + j) = \sum_{i=1}^j p_i(n)$

• Let $S_i =$ the set of $n$-partitions with exactly $i$ parts, $i \in [j]$
• Let $S = \bigcup_{i=1}^j S_i$. Then $|S| = |S_1| + \dots + |S_j| = p_1(n) + \dots + p_j(n)$. // right-hand side
• Let $T =$ the set of $(n+j)$-partitions with exactly $j$ parts. Then $|T| = p_j(n+j)$. // left-hand side
• $f: S \to T\quad (n_1, \dots, n_i) \mapsto (n_1 + 1, \dots, n_i + 1, 1, \dots, 1)$
  • $f$ is bijective
  • $|T| = |S|$

EXAMPLE: determine $p_3(6)$ and $p_4(6)$ with the above theorem

• $p_3(6) = p_3(3+3) = p_1(3) + p_2(3) + p_3(3) = 1 + 1 + 1 = 3$
• $p_4(6) = p_4(2+4) = p_1(2) + p_2(2) + p_3(2) + p_4(2) = 1 + 1 + 0 + 0 = 2$

Computing $p_j(n)$ Recursively

Generating Functions

Catalan number: $C_{n+1} = \sum_{k=0}^n C_k C_{n-k}$, $C_0 = 1$// there is a new tool to solve it

DEFINITION: The generating function of a sequence $\{a_r\}_{r=0}^\infty$ is $G(x) = \sum_{r=0}^\infty a_r x^r$.

• Generating functions are formal power series; we do not discuss their convergence.

EXAMPLE: generating functions of sequences

• $a_r = 3$, $G(x) = 3(1 + x + \dots + x^r + \dots)$
• $a_r = 2^r$, $G(x) = 1 + 2x + \dots + (2x)^r + \dots$
• $a_r = \binom{n}{r}$, $G(x) = \binom{n}{0} + \binom{n}{1}x + \dots + \binom{n}{n}x^n$

DEFINITION: Let $A(x) = \sum_{r=0}^\infty a_r x^r$, $B(x) = \sum_{r=0}^\infty b_r x^r$.

• $A(x) = B(x)$ if $a_r = b_r$ for all $r = 0,1,2, \dots$

Operations

DEFINITION: Let $A(x) = \sum_{r=0}^\infty a_r x^r$, $B(x) = \sum_{r=0}^\infty b_r x^r$.

• $A(x) + B(x) = \sum_{r=0}^\infty (a_r + b_r) x^r$
• $A(x) – B(x) = \sum_{r=0}^\infty (a_r – b_r) x^r$
• $A(x) \cdot B(x) = \sum_{r=0}^\infty \left(\sum_{j=0}^r a_j b_{r-j}\right) x^r$
• $\lambda \cdot A(x) = \sum_{r=0}^\infty \lambda a_r x^r$ for any constant $\lambda \in \mathbb{R}$
• We say that $B(x)$ is an inverse of $A(x)$ if $A(x)B(x) = 1$.
  • The inverse of $A(x)$ is denoted as $A^{-1}(x)$
  • When $A(x)$ has an inverse, define $\frac{C(x)}{A(x)} = A^{-1}(x) \cdot C(x)$

THEOREM: $A(x) = \sum_{r=0}^\infty a_r x^r$ has an inverse if and only if $a_0 \neq 0$.

EXAMPLE: Let $A(x) = \sum_{r=0}^\infty x^r$. Find $A^{-1}(x)$.

• $a_0 = 1 \neq 0$: $A^{-1}(x)$ exists
• Denote $A^{-1}(x) = \sum_{r=0}^\infty b_r x^r$; $b_0, b_1, \dots$ are undetermined coefficients
• $A(x)A^{-1}(x) = 1$:
  • $(1 + x + x^2 + \dots)(b_0 + b_1 x + b_2 x^2 + \dots) = 1 + 0 \cdot x + 0 \cdot x^2 + \dots$
    • Coefficient of $x^0$: $b_0 = 1$
    • Coefficient of $x^1$: $b_1 + b_0 = 0$
    • Coefficient of $x^2$: $b_2 + b_1 + b_0 = 0$
    • Coefficient of $x^r$: $b_r + b_{r-1} + \dots + b_0 = 0$
      • $b_1 = -1$, $b_2 = 0$, …, $b_r = 0$
      • $A^{-1}(x) = 1 – x$

DEFINITION: $A(x) = \sum_{n=0}^\infty a_n x^n$

• $A'(x) = \sum_{n=1}^\infty n a_n x^{n-1}$
  • $A^{(0)}(x) = A(x)$
  • $A^{(k)}(x) = (A^{(k-1)}(x))’$ for all integers $k \geq 1$
• $\int A(x) dx = \sum_{n=0}^\infty \frac{1}{n+1} a_n x^{n+1} + C$, where $C$ is a constant

THEOREM: Let $A(x) = \sum_{n=0}^\infty a_n x^n$ and $B(x) = \sum_{n=0}^\infty b_n x^n$.

• $(\alpha A(x) + \beta B(x))’ = \alpha A'(x) + \beta B'(x)$
• $(A(x)B(x))’ = A'(x)B(x) + A(x)B'(x)$
• $\left(A^k(x)\right)’ = k A^{k-1}(x) A'(x)$

$(1+\alpha x)^u$

DEFINITION: Let $u \in \mathbb{R}$ and $n \in \mathbb{N}$. The extended binomial coefficient

THEOREM: Let $x$ be a real number with $|x| < 1$ and let $u$ be a real number. Then $(1 + x)^u = \sum_{n=0}^\infty \binom{u}{n} x^n$.

EXAMPLE:

• $(1 – \alpha x)^{-1} = \sum_{n=0}^\infty \alpha^n x^n$ // $\binom{-1}{n} = \frac{(-1)(-1-1)\cdots(-1-n+1)}{n!} = (-1)^n$
• $(1 – \alpha x)^{-u} = \sum_{n=0}^\infty \binom{n + u – 1}{n} \alpha^n x^n$ // $\binom{-u}{n} = \frac{(-u)(-u-1)\cdots(-u-n+1)}{n!} = (-1)^n \binom{n + u – 1}{n}$