Counting: Permutations, Combinations and Principles

Combinatorics answers "how many?" without listing. How many passwords of a given form exist, how many ways can tasks be assigned to processors, how many paths cross a grid, how many binary strings avoid a pattern? Counting is the basis of discrete probability (favourable outcomes over total outcomes), of the analysis of algorithms (number of comparisons, number of possible inputs), and of many recurrences.

The topics are the basic principles, permutations and combinations with and without repetition, the binomial theorem, distributions of objects into boxes, inclusion-exclusion, derangements, the pigeonhole principle, and the Catalan numbers.

Here $0 \le r \le n$ in the first row (otherwise the count is 0); in the second row any $r \ge 0$ is allowed.

Example: arrangements of MISSISSIPPI (1 M, 4 I, 4 S, 2 P) $= 11!/(1!\,4!\,4!\,2!) = 34650$.

For any $x, y$ and integer $n \ge 0$:

Standard identities (all for integers $n \ge 0$, with $\binom{n}{r} = 0$ when $r < 0$ or $r > n$):

The coefficient of $x^a y^b$ in $(x + y)^n$ with $a + b = n$ is $\binom{n}{b}$; in $(x + y + z)^n$ the coefficient of $x^a y^b z^c$ is $n!/(a!\,b!\,c!)$.

Stars and bars. The number of solutions of $x_1 + x_2 + \cdots + x_k = n$ in non-negative integers is

Reason: arrange $n$ stars and $k - 1$ bars in a row; the bars cut the stars into $k$ groups, possibly empty. Any arrangement is a choice of $k - 1$ bar positions among $n + k - 1$.

The twelvefold summary (the common cases). For $n\ge1$ and $k\ge1$, distributing $n$ objects into $k$ boxes:

With $S(0,0)=1$ and $S(0,j)=0$ for $j>0$, $S(n, k)$ is the Stirling number of the second kind, the number of ways to partition an $n$-set into $k$ non-empty blocks, with $S(n, k) = k\,S(n-1, k) + S(n-1, k-1)$. $k!\,S(n, k) = \sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n$ is the number of onto functions (see Functions).

For finite sets $A_1, \ldots, A_n$:

The number of elements in none of the sets is $N - |\bigcup A_i|$, where $N$ is the size of the universe. If every intersection of $j$ sets has the same size $s_j$ (the symmetric case), the count of elements in none of them is $\sum_{j=0}^{n} (-1)^j \binom{n}{j} s_j$ with $s_0 = N$.

A derangement is a permutation with no fixed point (no element in its original position). Their number is

Values: $D_1, \ldots, D_6 = 0, 1, 2, 9, 44, 265$. $D_n$ is the nearest integer to $n!/e$ for $n \ge 1$, so the probability that a random permutation is a derangement tends to $1/e \approx 0.3679$. The number of permutations with exactly $r$ fixed points is $\binom{n}{r} D_{n-r}$.

If $N$ objects go into $k$ boxes, some box holds at least $\lceil N/k \rceil$ objects. To guarantee that some box holds at least $r$ objects, $N = k(r - 1) + 1$ objects are needed and enough.

$C_n$ counts: balanced strings of $n$ pairs of parentheses; binary trees with $n$ nodes (structurally distinct); full binary trees with $n + 1$ leaves; ways to parenthesise a product of $n + 1$ factors; lattice paths from $(0, 0)$ to $(n, n)$ with unit right and up steps that never go above the diagonal; triangulations of a convex $(n + 2)$-gon; valid stack-permutation sequences of $n$ pushes and pops. They satisfy $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$.

Lattice paths without the diagonal restriction: from $(0, 0)$ to $(a, b)$ with right and up steps there are $\binom{a + b}{a}$ paths.

From 6 men and 5 women, choose a committee of 4 with at least one woman. Total $\binom{11}{4} = 330$; all-men $\binom{6}{4} = 15$; answer $330 - 15 = 315$. (Adding "choose one woman, then any 3 others" gives $5\binom{10}{3} = 600$, which overcounts.)

Binary strings of length 10 with exactly four 1s: $\binom{10}{4} = 210$. With at least two 1s: $2^{10} - 1 - 10 = 1013$. Strings over $\{a, b, c\}$ of length 5 containing at least one $a$: $3^5 - 2^5 = 211$.

Number of non-negative integer solutions of $x_1 + x_2 + x_3 = 10$ with every $x_i \le 4$. Without bounds: $\binom{12}{2} = 66$. If $x_1 \ge 5$, set $x_1' = x_1 - 5$: $\binom{7}{2} = 21$ solutions; same for $x_2, x_3$. Two variables cannot both be at least 5 unless the third is 0 and both equal 5: $\binom{2}{2} = 1$ for each pair. Three: impossible.

(They are the arrangements of $\{4, 4, 2\}$ and $\{4, 3, 3\}$: $3 + 3 = 6$.)

How many permutations of $1, 2, \ldots, 6$ have none of the patterns "12", "34" or "56" as consecutive entries? Gluing $j$ of the three pairs into blocks leaves $6 - j$ units, so each $j$-fold intersection has $(6 - j)!$ permutations:

Five letters are placed at random into their five addressed envelopes. The number of ways in which no letter is in its correct envelope is $D_5 = 44$; exactly two correct: $\binom{5}{2} D_3 = 10 \cdot 2 = 20$.