Permutations and Combinations

Introduction

Permutations and combinations are fundamental topics in combinatorics. A permutation selects a specified number of elements from a given set and arranges them; a combination selects a specified number of elements without considering their order. The central problem of permutations and combinations is to study the total number of possible arrangements and selections under given requirements. Permutations and combinations are closely related to classical probability theory.

In elementary high-school mathematics, permutations and combinations are often solved by methods such as listing and enumeration.

Addition and Multiplication Principles

Addition Principle

Suppose a task can be completed in $n$ categories of ways, and $a_i(1 \le i \le n)$ is the number of ways in category $i$. Then there are $S=a_1+a_2+\cdots +a_n$ different ways to complete the task.

Multiplication Principle

Suppose a task consists of $n$ steps, and $a_i(1 \le i \le n)$ is the number of different ways to complete step $i$. Then there are $S = a_1 \times a_2 \times \cdots \times a_n$ different ways to complete the task.

Basics of Permutations and Combinations

Permutations

From $n$ distinct elements, taking any $m$ ($m\leq n$, where $m$ and $n$ are natural numbers, as below) and arranging them in a specified order is called a permutation obtained from $n$ distinct elements by taking $m$ elements. The number of all permutations obtained from $n$ distinct elements by taking $m$ elements ($m\leq n$) is called the number of permutations obtained from $n$ distinct elements by taking $m$ elements, denoted by $\mathrm A_n^m$ (or $\mathrm P_n^m$).

The formula for permutations is

$$\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}$$

$n!$ denotes the factorial of $n$, that is, $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$.

The formula can be understood as follows: choose $n$ people and select $m$ of them ($m \le n$), then line them up. There are $n$ choices for the first position, $n-1$ choices for the second position, and so on; for the $m$-th (last) position, there are $n-m+1$ choices. Thus,

$$\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}$$

A full permutation: all $n$ people line up, so the length of the line is $n$. There are $n$ choices for the first position, $n-1$ choices for the second position, and so on, giving

$$\mathrm A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n!$$

A full permutation is a special case of permutations.

Combinations

Given $n$ distinct elements, with $m \leq n$, a set formed from $n$ elements by selecting $m$ of them is called a combination. The number of all such combinations of $n$ distinct elements with $m \leq n$ selected is called the number of combinations formed from $n$ distinct elements by selecting $m$ elements, denoted by $\dbinom{n}{m}$ and read as “$n$ choose $m$”.

The formula for combinations is

$$\dbinom{n}{m} = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!}$$

How should we understand this formula? Consider choosing $n$ people and selecting $m$ of them ($m \le n$), without lining them up and without caring about their order. If order matters, the number is $\mathrm A_n^m$; if order does not matter, we must divide out the duplicates. How many duplicates are there? The same $m$ people can be arranged in a “full permutation” in $m!$ ways, so

$$\begin{aligned} \dbinom{n}{m} \times m! &= \mathrm A_n^m\\ \dbinom{n}{m} &= \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n-m)!} \end{aligned}$$

Combinations are also commonly denoted by $\mathrm C_n^m$, namely $\displaystyle \mathrm C_n^m=\binom{n}{m}$. Modern mathematics generally uses the notation $\dbinom{n}{m}$ rather than $\mathrm C_n^m$.

Combinations are also called “binomial coefficients”; the binomial theorem below will explain the connection.

In particular, when $m>n$, define $\mathrm A_n^m=\dbinom{n}{m}=0$.

Stars and Bars

Stars and bars is a technique for counting the ways to divide identical elements into groups; it can also be used to count the solutions of a class of linear Diophantine equations.

Number of Sums of Positive Integers

Problem 1: there are $n$ identical elements. Divide them into $k$ groups, with at least one element in each group. How many divisions are there?

Consider inserting $k - 1$ bars into the gaps formed between the $n$ elements; there are $n - 1$ such gaps.

Because the elements are identical, the answer is $\dbinom{n - 1}{k - 1}$.

In essence, this counts the positive-integer solutions of $x_1+x_2+\cdots+x_k=n$.

Number of Sums of Nonnegative Integers

Problem 2: what if the problem is changed so that each group may be empty?

Clearly, stars and bars cannot be applied directly, because many bars may be inserted into one gap, which is very difficult to count.

We create a condition to transform this into the constrained Problem 1. First borrow $k$ elements, then insert bars into the gaps formed by the $n + k$ elements; there are $n + k - 1$ such gaps. The answer is

$$\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}$$

Although this does not directly count the original problem, this expression is its answer. The interpretation is as follows:

At the beginning, we borrow $k$ elements to ensure that each group has at least one element. After inserting the bars, remove the $k$ borrowed elements from the $k$ groups. Since the elements are identical, the transformed cases and the original cases correspond one-to-one, so their answers are equal.

This gives the stars-and-bars formula: $\dbinom{n + k - 1}{n}$.

In essence, this counts the nonnegative-integer solutions of $x_1+x_2+\cdots+x_k=n$ (that is, subject to $x_i \ge 0$).

Number of Integer Sums with Different Lower Bounds

Problem 3: extend the problem one step further. Require group $i$ to receive at least $a_i,\sum a_i \le n$ elements. How many divisions are there?

In essence, this counts the solutions of $x_1+x_2+\cdots+x_k=n$ with $x_i \ge a_i$.

By analogy with the unrestricted case, borrow $\sum a_i$ elements to ensure that group $i$ can receive at least $a_i$ elements. In other words, let

$$x_i^{\prime}=x_i-a_i$$

This gives the new equation:

$$\begin{aligned} (x_1^{\prime}+a_1)+(x_2^{\prime}+a_2)+\cdots+(x_k^{\prime}+a_k)&=n\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-a_1-a_2-\cdots-a_k\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-\sum a_i \end{aligned}$$

where

$$x_i^{\prime}\ge 0$$

Problem 3 is now transformed into Problem 2, so the stars-and-bars formula gives the answer

$$\binom{n - \sum a_i + k - 1}{n - \sum a_i}$$

Non-Adjacent Selections

Among the natural numbers $1 \sim n$, there are $n$ numbers in total. The number of ways to choose $k$ of them so that these $k$ numbers contain no adjacent pair is $\dbinom {n-k+1}{k}$.

Binomial Theorem

Before moving on to advanced permutations and combinations, we first introduce a theorem closely related to combinations: the binomial theorem.

The binomial theorem gives the coefficients in an expansion:

$$(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i$$

It can be proved by mathematical induction, using $\dbinom{n}{k}+\dbinom{n}{k-1}=\dbinom{n+1}{k}$ for the induction.

The binomial theorem can also be readily extended to the multinomial form:

Let $n$ be a positive integer and let $x_i$ be real numbers. Then

$$(x_1 + x_2 + \cdots + x_t)^n = \sum_{满足 n_1 + \cdots + n_t=n 的非负整数解} \binom{n}{n_1,n_2,\cdots,n_t} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}$$

Here $\dbinom{n}{n_1,n_2,\cdots,n_t}$ is a multinomial coefficient, whose properties are quite similar:

$$\sum{\binom{n}{n_1,n_2,\cdots,n_t}} = t^n$$

Advanced Permutations and Combinations

Next we introduce several variants of permutations and combinations.

Multiset Permutations | Multiset Combinations

Be sure to distinguish multiset combinations from combinations of a multiset! They are entirely different concepts!

A multiset is a generalization of a set that may contain repeated elements. Let $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ denote the multiset consisting of $n_1$ copies of $a_1$, $n_2$ copies of $a_2$, …, and $n_k$ copies of $a_k$. The number of full permutations of $S$ is

$$\frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}$$

This is equivalent to dividing by the permutations of identical elements. More concretely, imagine that you have $k$ types of distinct balls, with $n_1,n_2,\cdots,n_k$ balls of each type and $n=n_1+n_2+\ldots+n_k$. The number of full permutations of these $n$ balls is the number of permutations of a multiset. This is often called a multiset combination. We can write the above formula using the notation for multiset combinations:

$$\binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!}$$

It can be seen that $\dbinom{n}{m}$ is equivalent to $\dbinom{n}{m,n-m}$, but the latter is more cumbersome and is therefore not used.

Combinations of a Multiset 1

Let $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ denote the multiset consisting of $n_1$ copies of $a_1$, $n_2$ copies of $a_2$, …, and $n_k$ copies of $a_k$. For an integer $r(r<n_i,\forall i\in[1,k])$, from $S$ select $r$ elements to form a multiset; the number of such ways is called a combination of a multiset. This problem is equivalent to counting the nonnegative-integer solutions of $x_1+x_2+\cdots+x_k=r$, which can be solved by stars and bars. The answer is

$$\binom{r+k-1}{k-1}$$

Combinations of a Multiset 2

Consider the following problem: let $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ denote the multiset consisting of $n_1$ copies of $a_1$, $n_2$ copies of $a_2$, …, and $n_k$ copies of $a_k$. For a positive integer $r$, how many ways are there, from $S$, to select $r$ elements to form a multiset?

This restricts how many copies of each element may be selected. Similarly, we can transform the problem into solving a linear equation with constraints:

$$\forall i\in [1,k],\ x_i\le n_i,\ \sum_{i=1}^kx_i=r$$

This naturally suggests the inclusion-exclusion principle. Its model is:

1. Universal set: the nonnegative-integer solutions of $\displaystyle \sum_{i=1}^kx_i=r$.
2. Property: $x_i\le n_i$.

For property $i$, let the satisfying set be $S_i$; $\overline{S_i}$ is the set not satisfying property $i$, namely the set satisfying $x_i\ge n_i+1$ (which transforms into Problem 3 of stars and bars). The answer is therefore

$$\left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right|$$

By the inclusion-exclusion principle,

$$\begin{aligned} \left|\bigcup_{i=1}^k\overline{S_i}\right| =&\sum_i\left|\overline{S_i}\right| -\sum_{i,j}\left|\overline{S_i}\cap\overline{S_j}\right| +\sum_{i,j,k}\left|\overline{S_i}\cap\overline{S_j}\cap\overline{S_k}\right| -\cdots\\ &+(-1)^{k-1}\left|\bigcap_{i=1}^k\overline{S_i}\right|\\ =&\sum_i\binom{k+r-n_i-2}{k-1} -\sum_{i,j}\binom{k+r-n_i-n_j-3}{k-1}+\sum_{i,j,k}\binom{k+r-n_i-n_j-n_k-4}{k-1} -\cdots\\ &+(-1)^{k-1}\binom{k+r-\sum_{i=1}^kn_i-k-1}{k-1} \end{aligned}$$

Subtracting the above expression from the universal-set size $\displaystyle |U|=\binom{k+r-1}{k-1}$ gives the number of combinations of a multiset:

$$Ans=\sum_{p=0}^k(-1)^p\sum_{A}\binom{k+r-1-\sum_{A} n_{A_i}-p}{k-1}$$

Here A serves as the enumerated subset, satisfying $|A|=p,\ A_i<A_{i+1}$.

Circular Permutations

Arrange all $n$ people around a circle; denote the number of all permutations by $\mathrm Q_n^n$. Consider a fixed circular arrangement. Breaking the circle at different positions produces different queues. Therefore,

$$\mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)!$$

This gives the formula for partial circular permutations:

$$\mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!}$$

Properties of Binomial Coefficients | Binomial Corollaries

Because binomial coefficients are extremely important in OI, we introduce several of their properties here.

$$\binom{n}{m}=\binom{n}{n-m}\tag{1}$$

This is equivalent to taking the complement of the selected set in the universal set, so the value does not change. (Symmetry)

$$\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}\tag{2}$$

A recurrence derived from the definition.

$$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\tag{3}$$

The recurrence for binomial coefficients (the formula for Pascal's triangle). We can use this formula to derive binomial coefficients in $O(n^2)$ time.

$$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4}$$

This is a special case of the binomial theorem. Taking $a=b=1$ gives the formula above.

$$\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]\tag{5}$$

Another special case of the binomial theorem, obtained by taking $a=1, b=-1$. In the special case $n=0$, the answer is $1$.

$$\sum_{i=0}^k \binom{n}{i}\binom{m}{k-i} = \binom{m+n}{k}\tag{6}$$

An identity for decomposing binomial coefficients, useful in some data-structure problems. It is called Vandermonde's identity.

$$\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{7}$$

This is a special case of $(6)$, obtained by taking $n=k=m$.

$$\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\tag{8}$$

An identity for a weighted sum, which can be proved by differentiating the polynomial corresponding to $(4)$.

$$\sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}\tag{9}$$

Similarly, this can be proved by differentiating the polynomial.

$$\sum_{l=0}^n\binom{l}{k} = \binom{n+1}{k+1}\tag{10}$$

This can be proved by combinatorial analysis: consider $S=\{a_1, a_2, \cdots, a_{n+1}\}$ and count its $k+1$-element subsets one by one. It is often used in identity proofs. It is called the hockey-stick identity.

$$\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{11}$$

This follows directly from the definition.

$$\sum_{i=0}^n\binom{n-i}{i}=F_{n+1}\tag{12}$$

Here $F$ is the Fibonacci sequence.

$$\binom{n+k}{k}^2=\sum_{j=0}^k\binom{k}{j}^2\binom{n+2k-j}{2k}\tag{13}$$

This can be proved using $(6)$. It is called Li Shanlan's identity.

Binomial Inversion

Let $f_n$ denote the number of ways to form a specified structure using exactly $n$ distinct elements, and let $g_n$ denote the total number of ways to form a specified structure by selecting elements from $n$ distinct elements, with $i \geq 0$ selected.

If $f_n$ is known and we seek $g_n$, then clearly

$$g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i$$

If $g_n$ is known and we seek $f_n$, then

$$f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i$$

The process of using known $g_n$ above to find $f_n$ is called binomial inversion.

Proof

Expanding $g_i$ in the inversion formula gives

$$\begin{aligned} f_n &= \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} \left[\sum_{j = 0}^{i} \binom{i}{j} f_j\right] \\ &= \sum_{i = 0}^{n}\sum_{j = 0}^{i}\binom{n}{i}\binom{i}{j} (-1)^{n-i}f_j \end{aligned}$$

Enumerate $j$ first and then $i$:

$$\begin{aligned} f_n &= \sum_{j = 0}^{n}\sum_{i = j}^{n}\binom{n}{i}\binom{i}{j} (-1)^{n-i}f_j \\ &= \sum_{j = 0}^{n}f_j\sum_{i = j}^{n}\binom{n}{i}\binom{i}{j} (-1)^{n-i} \end{aligned}$$

Using formula (11) from “Properties of Binomial Coefficients | Binomial Corollaries”, we obtain

$$\begin{aligned} f_n &= \sum_{j = 0}^{n}f_j\sum_{i = j}^{n}\binom{n}{j}\binom{n - j}{i - j} (-1)^{n-i} \\ &= \sum_{j = 0}^{n}\binom{n}{j}f_j\sum_{i = j}^{n}\binom{n - j}{i - j} (-1)^{n-i} \end{aligned}$$

Let $k = i - j$. Then $i = k + j$, and the expression becomes

$$f_n = \sum_{j = 0}^{n}\binom{n}{j}f_j\sum_{k = 0}^{n - j}\binom{n - j}{k} (-1)^{n-j-k}1^{k}$$

Using formula (5) from “Properties of Binomial Coefficients | Binomial Corollaries”, we obtain

$$f_n = \sum_{j = 0}^{n}\binom{n}{j}f_j[n = j] = f_n$$

This completes the proof.