[combinatorics] permutation and combination (examples of combinatorial number of multiple sets | three counting models | selection problem | combinatorial problem of multiple sets | nonnegative intege

Arrange and combine reference blogs :

• 【 Combinatorial mathematics 】 Basic counting principle ( The principle of addition | Multiplication principle )
• 【 Combinatorial mathematics 】 Examples of permutation and combination of sets ( array | Combine | Circular arrangement | binomial theorem )
• 【 Combinatorial mathematics 】 Permutation and combination ( Arrange and combine content summary | Select the question | Set arrangement | Set combination )
• 【 Combinatorial mathematics 】 Permutation and combination ( Examples of permutations )
• 【 Combinatorial mathematics 】 Permutation and combination ( Multiset arrangement | Full Permutation of multiple sets | Multiset incomplete permutation The repetition of all elements is greater than the number of permutations | Multiset incomplete permutation The repetition of some elements is less than the number of permutations )
• 【 Combinatorial mathematics 】 Permutation and combination ( The combinatorial number of multiple sets | The repetition of all elements is greater than the number of combinations | The combinatorial number of multiple sets deduction 1 Division line derivation | The combinatorial number of multiple sets deduction 2 Derivation of the number of nonnegative integer solutions of indefinite equations )

One 、 Examples of multiset combinations

---

take

r

r

r It's the same ball , Put it in

k

k

k In different boxes , There is no limit to the number of balls in each box , Find the total number of ways to put the ball ?

There is no difference between balls , Put the ball in the box , The ball has no label , The box has a label , The number of balls in each box is different ;

The number of balls falling into each box is different , It's a different solution ;

hypothesis

n

n

n Boxes , The number of balls in each box is

x

1

,

x

2

,

⋯
 

,

x

k

x_1 , x_2 , \cdots , x_k

x1​,x2​,⋯,xk​ ;

There are indefinite equations :

x

1

+

x

2

+

⋯

+

x

k

=

r

x_1 + x_2 + \cdots + x_k = r

x1​+x2​+⋯+xk​=r

Value :

x

1

,

x

2

,

⋯
 

,

x

k

x_1 , x_2 , \cdots , x_k

x1​,x2​,⋯,xk​ The value of is a nonnegative integer , It can take

0

∼

r

0 \sim r

0∼r Between the value of the ;

This problem can be equivalent to multiple sets

S

=

{

n

1

⋅

a

1

,

n

2

⋅

a

2

,

⋯
 

,

n

k

⋅

a

k

}

,

   

0

≤

r

≤

n

i

≤

+

∞

S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq r \leq n_i \leq +\infty

S={ n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},   0≤r≤ni​≤+∞ Of

r

r

r Combinatorial number ;

N

=

C

(

k

+

r

−

1

,

r

)

N= C(k + r - 1, r)

N=C(k+r−1,r)

Reference resources : 【 Combinatorial mathematics 】 Permutation and combination ( The combinatorial number of multiple sets | The repetition of all elements is greater than the number of combinations | The combinatorial number of multiple sets deduction 1 Division line derivation | The combinatorial number of multiple sets deduction 2 Derivation of the number of nonnegative integer solutions of indefinite equations )

Above

r

r

r It's the same ball , Put it in

k

k

k In different boxes , The number of ways to put the ball is

N

=

C

(

k

+

r

−

1

,

r

)

N = C(k + r - 1, r)

N=C(k+r−1,r)

Two 、 Three counting models

---

Three counting models :

• ① Select the question :
• ② Multiple set combinatorial problem :
• ③ Nonnegative integer solution of the equation :

1. Select the question :

n

n

n Meta set

S

S

S , from

S

S

S Select... From the set

r

r

r Elements ;

according to Whether the element can be repeated , Whether the selection process is orderly , The selection question is divided into four sub types :

	Elements do not repeat	Elements can be repeated
Orderly selection	Set arrangement P ( n , r ) P(n,r) P(n,r)	Multiset arrangement
Unordered selection	Set combination C ( n , r ) C(n,r) C(n,r)	Combination of multiple sets

Select the question :

• Non repeatable elements , Orderly selection , Corresponding Arrangement of sets
• Non repeatable elements , Unordered selection , Corresponding A combination of sets
• Repeatable elements , Orderly selection , Corresponding Arrangement of multiple sets
• Repeatable elements , Unordered selection , Corresponding Combination of multiple sets

2. Multiple set combinatorial problem :

S

=

{

n

1

⋅

a

1

,

n

2

⋅

a

2

,

⋯
 

,

n

k

⋅

a

k

}

,

   

0

≤

n

i

≤

+

∞

S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty

S={ n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},   0≤ni​≤+∞

• Type of elements : Multiple sets contain

  k

  k

  k Different elements ,

• The element represents : Each element is represented as

  a

  1

  ,

  a

  2

  ,

  ⋯
   

  ,

  a

  k

  a_1 , a_2 , \cdots , a_k

  a1​,a2​,⋯,ak​ ,

• Element number : The number of occurrences of each element is

  n

  1

  ,

  n

  2

  ,

  ⋯
   

  ,

  n

  k

  n_1, n_2, \cdots , n_k

  n1​,n2​,⋯,nk​ ,

• The value of the number of elements :$n_i$

  +∞ ;

Combination of the above multiple sets , When The repeatability of all elements

n

i

n_i

ni​ The number of groups is greater than the number of combinations

r

r

r when ,

r

≤

n

i

r \leq n_i

r≤ni​ when , The combination number of multiple sets is

N

=

C

(

k

+

r

−

1

,

r

)

N= C(k + r - 1, r)

N=C(k+r−1,r)

3. Nonnegative integer solutions of indefinite equations :

x

1

+

x

2

+

⋯

+

x

k

=

r

x_1 + x_2 + \cdots + x_k = r

x1​+x2​+⋯+xk​=r

The number of nonnegative integer solutions is :

N

=

C

(

k

+

r

−

1

,

r

)

N= C(k + r - 1, r)

N=C(k+r−1,r)