@ @ Basic concept: the principle of incompatibility is also called the principle of exclusion. In combinatorial mathematics, it means that if A 1...An is a finite set, as shown in the following figure, where |A| represents the cardinality of a (the number of elements in a set). For example, in the case of two sets, we can add |A| and |B|, and then subtract the cardinality of their intersection to get the cardinality of their union. Excerpt from Wikipedia

There are n balls in a row, and you have k colors. Each ball is required to be dyed. The colors of two adjacent balls cannot be the same, and each color must be used at least once.

Just like the problem of misplacement, assuming that each color is not restricted to be used at least once, the problem is very simple, and the answer is k (k- 1) n- 1. These schemes are based on i(i=0, 1, 2,? , k) color scheme, then let fi be the number of schemes that just use I colors, and you can get

Stirling number of classical application

Stirling numbers of the first kind are divided into positive and negative numbers, and terms with an absolute value of n yuan are arranged in k circles. Commonly used representations are s(n, k) and so on.

In other words, divide n people into k groups, and circle the number of grouping methods in each group in a specific order. For example, s (4,2) =11:

{A，B}，{C，D}

{A，C}，{B，D}

{A，D}，{B，C}

{A}，{B，C，D}

{A}，{B，D，C}

{B}，{A，C，D}

{B}，{A，D，C}

{C}，{A，B，D}

{C}，{A，D，B}

{D}，{A，B，C}

{D}，{A，C，B}

Given s (n, 0) = 1, s (1, 1) = 1, then s (n, k) = s (n- 1, k-1.

Recursive relation description: considering the nth item, n can form a non-empty cyclic arrangement independently, so that the first n- 1 items form k- 1 non-empty cyclic arrangements, and there is a method in S(n- 1, k- 1); The first n- 1 terms can also be arranged into k non-empty cycles, and the n-th term is inserted to the left of the I-th term. There are (n- 1) (n- 1, k) methods.