Counting

Counting well means finding the right bijection or the right correction for overcounting.

1. Combinatorial proof of binomial identities (Prop. 1.1), including Vandermonde (Prop. 1.2).
2. Stars and bars for distributions (Prop. 1.3).
3. Inclusion–exclusion in general form (Thm 1.4), giving derangements (Cor. 1.5) and surjections (Prop. 1.6).
4. Stirling numbers of the second kind (Def. 1.7) and their recurrence (Prop. 1.8).

For $0\le k\le n$:

1. $\binom nk = \binom n{n-k}$;
2. $k\binom nk = n\binom{n-1}{k-1}$;
3. $\sum_{k=0}^n\binom nk = 2^n$ and $\sum_k(-1)^k\binom nk = 0$ ($n\ge1$);
4. $\sum_{j=k}^n\binom jk = \binom{n+1}{k+1}$ (hockey stick).

$\sum_{k=0}^r\binom mk\binom n{r - k} = \binom{m + n}r$. In particular $\sum_k\binom nk^2 = \binom{2n}n$.

The number of solutions of $x_1 + \dots + x_k = n$ in non-negative integers is $\binom{n + k - 1}{k - 1}$; in positive integers it is $\binom{n - 1}{k - 1}$. Equivalently, the number of multisets of size $n$ from $k$ types is $\binom{n + k - 1}n$.

For finite sets $A_1, \dots, A_n$,

Equivalently, the number of elements of a set $X\supseteq\bigcup A_i$ lying in none of the $A_i$ is $\sum_{S\subseteq[n]}(-1)^{|S|}|A_S|$ with $A_\emptyset = X$.

A derangement is a permutation with no fixed point. Their number is

so $\frac{D_n}{n!}\to\frac1e$, and $D_n$ is the nearest integer to $\frac{n!}e$. They satisfy $D_n = (n - 1)(D_{n-1} + D_{n-2})$.

The number of surjections $[n]\to[k]$ is $\sum_{j=0}^k(-1)^j\binom kj(k - j)^n$.

$S(n, k)$ is the number of partitions of $[n]$ into $k$ nonempty unlabelled blocks. Since labelling the blocks gives a surjection onto $[k]$, the number of surjections is $k!S(n, k)$. The Bell number $B_n = \sum_kS(n, k)$ counts all partitions.

$S(n, k) = S(n - 1, k - 1) + kS(n - 1, k)$ for $1\le k\le n$, with $S(0, 0) = 1$. Also $x^n = \sum_kS(n, k)x(x - 1)\cdots(x - k + 1)$.

• Are objects distinct or identical? Do boxes have labels? Is order important?
• Distinct into labelled: $k^n$; surjective: inclusion–exclusion; unlabelled: Stirling.
• Identical into labelled: stars and bars.
• "None of the properties": inclusion–exclusion. Check small cases by brute listing.