Permutations and Combinations

Introduction

Permutations and combinations are fundamental in combinatorics. A permutation refers to selecting a specified number of elements from a given set and arranging them in a specific order; a combination refers to merely selecting a specified number of elements from a given set, without considering the order. The central problem of permutations and combinations is to study the total number of possible arrangements and selections under given conditions. Permutations and combinations are closely related to classical probability theory.

In elementary high school mathematics, permutations and combinations are often solved using methods like listing and enumeration.

Addition & Multiplication Principles

Addition Principle

If a task can be completed in \(n\) different ways, and \(a_i(1 \le i \le n)\) represents the number of methods in the \(i\)-th category, then the total number of different ways to complete the task is \(S=a_1+a_2+\cdots +a_n\).

Multiplication Principle

If a task requires \(n\) steps to complete, and \(a_i(1 \le i \le n)\) represents the number of different methods for the \(i\)-th step, then the total number of different ways to complete the task is \(S = a_1 \times a_2 \times \cdots \times a_n\).

Basics of Permutations and Combinations

Number of Permutations

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

The formula for calculating permutations is as follows:

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

Here, \(n!\) represents the factorial of \(n\), i.e., \(6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6\).

The formula can be understood as follows: \(n\) people choose \(m\) to line up (\(m \le n\)). The first position can be chosen from \(n\) people, the second from \(n-1\), and so on, the \(m\)-th (last) position can be chosen from \(n-m+1\) people, yielding:

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

Full permutation: all \(n\) people line up, the line length is \(n\). The first position can be chosen from \(n\) people, the second from \(n-1\), and so on:

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

Full permutation is a special case of the permutation number.

Number of Combinations

From \(n\) distinct elements, taking \(m \leq n\) elements to form a set is called a combination of taking \(m\) elements from \(n\) distinct elements. The total number of all such combinations is called the number of combinations of taking \(m\) elements from \(n\) distinct elements, denoted by the symbol \(\dbinom{n}{m}\), read as "\(n\) choose \(m\)".

The formula for calculating combinations is:

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

How to understand the above formula? Consider \(n\) people choosing \(m\) (\(m \le n\)) without lining up, i.e., order does not matter. If order mattered, it would be \(\mathrm A_n^m\). Since order does not matter, we must divide out the duplicates. How many duplicates? The same \(m\) chosen people can be arranged 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} \]

The combination number is also commonly denoted as \(\mathrm C_n^m\), i.e., \(\displaystyle \mathrm C_n^m=\binom{n}{m}\). Currently, the mathematical community generally adopts the notation \(\dbinom{n}{m}\) rather than \(\mathrm C_n^m\).

The combination number is also known as the "binomial coefficient", and its connection will be explained in the binomial theorem below.

Specifically, it is defined that when \(m>n\), \(\mathrm A_n^m=\dbinom{n}{m}=0\).

Stars and Bars

Stars and bars is a technique used to find the number of ways to group identical elements, and can also be used to find the number of solutions to a certain type of linear indeterminate equations.

Number of Positive Integer Sums

Problem 1: Given \(n\) identical elements, divide them into \(k\) groups, ensuring each group has at least one element. How many ways are there?

Consider inserting \(k - 1\) dividers into the \(n - 1\) gaps between the \(n\) elements.

Since the elements are identical, the answer is \(\dbinom{n - 1}{k - 1}\).

Essentially, it is finding the number of positive integer solutions to \(x_1+x_2+\cdots+x_k=n\).

Number of Non-Negative Integer Sums

Problem 2: What if each group is allowed to be empty?

Clearly, we cannot directly apply stars and bars now, because many dividers might be inserted into the same gap, making calculation difficult.

We consider transforming the problem into a restricted version like Problem 1 by borrowing \(k\) elements first. Insert dividers into the \(n + k - 1\) gaps among these \(n + k\) elements, yielding the answer:

\[ \binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n} \]

Although this is not directly the original problem, this expression gives the answer to the original problem. It can be understood as follows:

We borrowed \(k\) elements at the beginning to ensure each group has at least one element. After inserting the dividers, we remove these \(k\) borrowed elements from the \(k\) groups. Since the elements are identical, there is a one-to-one correspondence between the transformed case and the original case, so the answers are equal.

Thus, we can derive the stars and bars formula: \(\dbinom{n + k - 1}{n}\).

Essentially, it is finding the number of non-negative integer solutions to \(x_1+x_2+\cdots+x_k=n\) (i.e., requiring \(x_i \ge 0\)).

Number of Integer Sums with Different Lower Bounds

Problem 3: Extending further, if for the \(i\)-th group, at least \(a_i\) elements must be allocated, with \(\sum a_i \le n\)?

Essentially, it is finding the number of solutions to \(x_1+x_2+\cdots+x_k=n\), where \(x_i \ge a_i\).

Analogous to the unrestricted case, we borrow \(\sum a_i\) elements to ensure the \(i\)-th group gets at least \(a_i\) elements. That is, let

\[ x_i^{\prime}=x_i-a_i \]

We obtain 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 \]

Then Problem 3 transforms into Problem 2, and directly applying the stars and bars formula gives the answer:

\[ \binom{n - \sum a_i + k - 1}{n - \sum a_i} \]

Non-Adjacent Selections

From the natural numbers \(1 \sim n\), choose \(k\) numbers such that no two of them are adjacent. The number of such combinations is \(\dbinom {n-k+1}{k}\).

Binomial Theorem

Before moving to the advanced section of permutations and combinations, we introduce a theorem closely related to combination numbers—the binomial theorem.

The binomial theorem clarifies the coefficients of an expansion:

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

Proof can be done by mathematical induction, using \(\dbinom{n}{k}+\dbinom{n}{k-1}=\dbinom{n+1}{k}\).

The binomial theorem can also be easily extended to the polynomial form:

Let \(n\) be a positive integer, \(x_i\) be real numbers,

\[ (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 the multinomial coefficient, and its properties are similar:

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

Advanced Permutations and Combinations

Next, we introduce some variants of permutations and combinations.

Permutations of Multisets | Multinomial Coefficients

Please be sure to distinguish between multinomial coefficients and combinations of multisets! They are completely different concepts!

A multiset is a generalized set containing repeated elements. Let \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}\) denote a multiset consisting of \(n_1\) copies of \(a_1\), \(n_2\) copies of \(a_2\), …, \(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 essentially divides out the permutations of identical elements. Specifically, you can think of having \(k\) different types of balls, with counts \(n_1,n_2,\cdots,n_k\) respectively, and \(n=n_1+n_2+\ldots+n_k\). The number of full permutations of these \(n\) balls is the permutation number of the multiset. The permutation number of a multiset is often called the multinomial coefficient. We can denote the above expression using the multinomial coefficient symbol:

\[ \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 thus not commonly used.

Combinations of Multisets 1

Let \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}\) denote a multiset consisting of \(n_1\) copies of \(a_1\), \(n_2\) copies of \(a_2\), …, \(n_k\) copies of \(a_k\). Then for an integer \(r(r<n_i,\forall i\in[1,k])\), the number of ways to select \(r\) elements from \(S\) to form a multiset is the combination number of the multiset. This problem is equivalent to finding the number of non-negative integer solutions to \(x_1+x_2+\cdots+x_k=r\), which can be solved using stars and bars, yielding the answer:

\[ \binom{r+k-1}{k-1} \]

Combinations of Multisets 2

Consider this problem: Let \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}\) denote a multiset consisting of \(n_1\) copies of \(a_1\), \(n_2\) copies of \(a_2\), …, \(n_k\) copies of \(a_k\). Then for a positive integer \(r\), find the number of ways to select \(r\) elements from \(S\) to form a multiset.

This restricts the number of each type of element taken. Similarly, we can transform this problem into solving a linear equation with restrictions:

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

Naturally, we think of the inclusion-exclusion principle. The inclusion-exclusion model is as follows:

Universal set: Non-negative integer solutions to \(\displaystyle \sum_{i=1}^kx_i=r\).
Properties: \(x_i\le n_i\).

Let \(S_i\) be the set satisfying property \(i\), and \(\overline{S_i}\) be the set not satisfying property \(i\), i.e., satisfying \(x_i\ge n_i+1\) (transformed into Problem 3 of stars and bars). Then the answer is

\[ \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 from the universal set \(\displaystyle |U|=\binom{k+r-1}{k-1}\) gives the combination number for the multiset:

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

where \(A\) serves to enumerate subsets, satisfying \(|A|=p,\ A_i<A_{i+1}\).

Circular Permutations

All \(n\) people stand in a circle, the total number of arrangements is denoted as \(\mathrm Q_n^n\). Consider an already arranged circle; breaking it at different positions yields different queues. Thus,

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

From this, we obtain the formula for partial circular permutations:

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

Combination Number Properties | Binomial Inferences

Since combination numbers are very important in OI, we introduce some properties of combination numbers here.

\[ \binom{n}{m}=\binom{n}{n-m}\tag{1} \]

This is equivalent to taking the complement of the selected set with respect to the universal set, so the value remains unchanged. (Symmetry)

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

Derived from the definition.

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

Recurrence relation for combination numbers (expressed by Pascal's triangle formula). We can use this formula to derive combination numbers with \(O(n^2)\) complexity.

\[ \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. Setting \(a=b=1\) yields the above.

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

Another special case of the binomial theorem, taking \(a=1, b=-1\). A special case of the formula is when \(n=0\), the answer is \(1\).

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

A formula splitting combination numbers, useful when dealing with certain data structure problems. Known as Vandermonde's Identity.

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

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

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

A formula involving weighted sums, provable by differentiating the polynomial function corresponding to \((4)\).

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

Similar to the above, provable by differentiating the polynomial function.

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

Can be proven by combinatorial analysis considering the \((k+1)\)-subsets of \(S=\{a_1, a_2, \cdots, a_{n+1}\}\), commonly used in identity proofs. Known as the Hockey-stick Identity.

\[ \binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{11} \]

Provable by definition.

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

where \(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} \]

Provable using \((6)\). Known as Li Shanlan's Identity.

Binomial Inversion

Let \(f_n\) denote the number of ways to form a specific structure using exactly \(n\) distinct elements, and \(g_n\) denote the total number of ways to select \(i \geq 0\) elements from \(n\) distinct elements to form the specific structure.

If \(f_n\) is known and we want \(g_n\), then obviously:

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

If \(g_n\) is known and we want \(f_n\), then:

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

The process of obtaining \(f_n\) from known \(g_n\) is called binomial inversion.

Proof

Expand \(g_i\) in the inversion formula:

\[ \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} \]

First sum over \(j\), then over \(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 「Combination Number Properties | Binomial Inferences」:

\[ \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 above 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 「Combination Number Properties | Binomial Inferences」:

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

Q.E.D.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用