Sequences (1): permutations & combinations

# Addition & Multiplication Principles

# Addition principle

Completing a project can include $n$ class method,$a_i(1 \le i \le n)$ Represents the first $i$ The number of class methods. Then there are a total of $S=a_1+a_2+\cdots +a_n$ different methods.

# multiplication principle

It takes minutes to complete a project $n$ steps,$a_i(1 \le i \le n)$ Represents the first $i$ The number of different methods for each step. Then there are a total of $S = a_1 \times a_2 \times \cdots \times a_n$ different methods.

# Basics of permutations and combinations

# number of permutations

from $n$ any of the different elements $m$（$m\leq n$，$m$ with $n$ are all natural numbers, the same below) elements are arranged in a column in a certain order, which is called from $n$ extracted from different elements $m$ an arrangement of elements; starting from $n$ extracted from different elements $m$($m\leq n$) The number of all permutations of elements is called from $n$ extracted from different elements $m$ The number of permutations of elements, using symbols $\mathrm A_n^m$(or $\mathrm P_n^m$) means.

The calculation formula for permutation is as follows:

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

$n!$ represent $n$ The factorial of $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$。

The formula can be understood like this:$n$ personal choice $m$ Come and line up ($m \le n$). The first position can be selected $n$ , the second position can be selected $n-1$ , and so on, the first $m$ (the last one) can be selected $n-m+1$ one, get:

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

Full arrangement:$n$ Everyone comes and lines up. The captain is $n$. The first position can be selected $n$ , the second position can be selected $n-1$ , and so on:

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

Total permutations are a special case of permutations.

# number of combinations

from $n$ any of the different elements $m$($m\leq n$) elements form a set, called from $n$ extracted from different elements $m$ a combination of elements; from $n$ extracted from different elements $m$($m\leq n$) The number of all combinations of elements is called from $n$ extracted from different elements $m$ The number of combinations of elements. use symbols $\mathrm C_n^m$ to express.

Combination number calculation formula

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

How to understand the above formula? we consider $n$ personal $m$($m \le n$) come out, don’t line up, don’t care about the order $C_n^m$. If you care about arrangement, then yes $A_n^m$, if you don’t care, then you have to get rid of the duplications, so how many duplications are there? Also selected $m$ Individuals, they still need to "completely arrange" $A_n^m$, so we get:

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

Combination numbers are also commonly used $\displaystyle \binom{n}{m}$ means, read as "$n$ choose $m$”, that is $\displaystyle \mathrm C_n^m=\binom{n}{m}$. In fact, the latter is clear in meaning, beautiful and concise, so it is now commonly used in mathematics circles. $\displaystyle \binom{n}{m}$ mark instead of $\mathrm C_n^m$。

Combinatorial numbers are also called "binomial coefficients", and the following binomial theorem will explain the connection.

In particular, it is stipulated that when $m>n$ when,$\mathrm A_n^m=\mathrm C_n^m=0$。

# binomial theorem

Before entering the advanced chapter on permutations and combinations, we first introduce a theorem closely related to combinatorial numbers - the binomial theorem.

The binomial theorem states the coefficients of an expansion:

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

The proof can be done using mathematical induction, using $\displaystyle \binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}$ Make a generalization.

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

Let n be a positive integer,$x_i$ is a real number,

$$(x_1 + x_2 + \cdots + x_t)^n = \sum_{\text{Non-negative integer solution that satisfies}n_1 + \cdots + n_t=n\text{}} \binom{n}{n_1n_2\cdots n_t} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}$$

of which $\binom{n}{n_1,n_2,\cdots ,n_t}$ is a polynomial coefficient, and its properties are also very similar:

$$\sum{\binom{n}{n_1n_2\cdots n_t}} = t^n$$

# Advanced Arrangement and Combination

Next we introduce some variations of permutations and combinations.

# Number of permutations of multisets | Number of multicombinations

Please make sure to distinguish Multiple combinations with Number of combinations of multisets! The two are completely different concepts!

Multiset refers to a generalized set containing repeated elements. Set $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ Expressed by $n_1$ a $a_1$，$n_2$ a $a_2$，…，$n_k$ a $a_k$ A multiset consisting of$S$ The total number of permutations is

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

It is equivalent to removing the number of permutations of the same elements. Specifically, you can think of you as having $k$ Plant different balls, and the number of each type of balls is $n_1,n_2,\cdots,n_k$, and $n=n_1+n_2+\ldots+n_k$. this $n$ The total number of permutations of balls is Number of permutations of multisets. The number of permutations of a multiset is often called Multiple combinations. We can express the above formula using the symbols of multiple combinatorial numbers:

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

It can be seen that$\displaystyle \binom{n}{m}$ Equivalent to $\displaystyle \binom{n}{m,n-m}$, but the latter is more cumbersome, so it is not used.

# Number of combinations of multisets 1

Set $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ Expressed by $n_1$ a $a_1$，$n_2$ a $a_2$，…，$n_k$ a $a_k$ composed of multisets. So for integers $r(r<n_i,\forall i\in[1,k])$, from $S$ Select $r$ The number of ways that elements can form a multiset is Number of combinations of multisets. This question is equivalent to $x_1+x_2+\cdots+x_k=r$ The number of non-negative integer solutions of can be solved using the plug-and-board method. The answer is

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

# Number of combinations of multisets 2

Consider this question: Suppose $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ Expressed by $n_1$ a $a_1$，$n_2$ a $a_2$，…，$n_k$ a $a_k$ composed of multisets. Then for positive integers $r$, from $S$ Select $r$ The number of ways elements can form a multiset.

This limits the number of elements that can be taken. Likewise, we can transform this problem into a linear equation solution with restrictions:

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

So it is natural to think of the principle of inclusion and exclusion. The model of inclusion and exclusion is as follows:

1. Complete set:$\displaystyle \sum_{i=1}^kx_i=r$ The non-negative integer solution of .
2. Properties:$x_i\le n_i$。

So suppose it satisfies the property $i$ The set is $S_i$，$\overline{S_i}$ Indicates that the attribute is not satisfied $i$ The set of , which satisfies $x_i\ge n_i+1$ collection. Then the answer is

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

According to the principle of inclusion and exclusion, there are:

$$\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}$$

Get the full set $\displaystyle |U|=\binom{k+r-1}{k-1}$ Subtract the above formula to get the number of combinations of multisets

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

where A acts as a subset of the enumeration, satisfying $|A|=p,\ A_i<A_{i+1}$。

# non-adjacent arrangement

$1 \sim n$ this $n$ natural numbers selected $k$ This, this $k$ The combination of any two numbers that are not adjacent is $\displaystyle \binom {n-k+1}{k}$ species.

# misaligned arrangement

Let’s concretize the problem of misalignment and consider this question:

$n$ Different letters, numbered respectively $1,2,3,4,5$, now we need to put these five letters in the numbered $1,2,3,4,5$ In the envelope, the envelope number is required to be different from the letter number. How many different placement methods are there?

Suppose we consider the $n$ envelope, initially we temporarily put the $n$ Put the letter on the $n$ envelopes, and then consider the recursion in two situations:

• front $n-1$ All envelopes were packed incorrectly;
• front $n-1$ One of the envelopes was packed incorrectly, and all the others were packed incorrectly.

For the first case, the front $n-1$ All envelopes were packed incorrectly: because the front $n-1$ All of them have been installed incorrectly, so the second one has been installed incorrectly. $n$ The seal only needs to be exchanged with any of the previous positions. There are a total of $f(n-1)\times (n-1)$ situation.

For the second case, the previous $n-1$ One of the envelopes is not packed incorrectly and the rest are all incorrectly packed: the purpose of considering this situation is that if $n-1$ If one of the envelopes is packed correctly, then we compare the one that is packed correctly with the $n$ By swapping, a fully misaligned arrangement can be obtained.

In other cases, we cannot turn it into a length of $n$ misaligned.

Therefore, the recursive formula for the misalignment arrangement can be obtained as $f(n)=(n-1)(f(n-1)+f(n-2))$。

The first few items of the misaligned sequence are $0,1,2,9,44,265$。

# circular arrangement

$n$ All individuals come to form a circle, and the number of all arrangements is recorded as $\mathrm Q_n^n$. Consider a circle that has been lined up, disconnected from different locations, and turned into different queues.
so there is

$$\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 know the formula for partial circle arrangement:

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

# Properties of combinatorial numbers | Binomial corollary

Here we introduce some properties of combinatorial numbers.

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

It is equivalent to taking the complement of the selected set to the complete set, so the value remains unchanged. (symmetry)

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

A recurrence derived from a definition.

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

The recursive expression of combination numbers (the formula expression of Yang Hui's triangle). We can use this formula to $O(n^2)$ The number of combinations is deduced under the 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. take $a=b=1$ We get the above formula.

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

Another special case of the binomial theorem, it is advisable $a=1, b=-1$. The special case of the formula is to take $n=0$ when the answer is $1$。

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

The formula for splitting a combination is used when dealing with certain data structure problems.

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

This is $(6)$ special case, take $n=m$ That’s it.

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

An expression with weighted sum, by pairing $(3)$ The corresponding derivation of the polynomial function can be proved.

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

Similar to the above equation, it can be proved by derivation of the polynomial function.

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

Consider one by one through combined analysis $S={a_1, a_2, \cdots, a_{n+1}}$ of $k+1$ Subset numbers can be proved and are commonly used in identity proofs.

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

It can be proved by definition.

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

Among them $F$ It is the Fibonacci sequence.