[combinatorics] permutation and combination (set combination, one-to-one correspondence model analysis example)

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 )
• 【 Combinatorial mathematics 】 Permutation and combination ( Example of the number of combinations of multiple sets | Three counting models | Select the question | Multiple set combinatorial problem | Nonnegative integer solutions of indefinite equations )
• 【 Combinatorial mathematics 】 Permutation and combination ( Two counting principles 、 Set arrangement example | Set arrangement 、 Example of circle arrangement )

One 、 Set combination 、 One to one correspondence model analysis example

---

take

2

n

2n

2n Personal share

n

n

n Group , Each group

2

2

2 people , How many ways are there ?

First determine whether the problem is a selection problem , Is the element repeated , Whether the selection is orderly ,

• 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

n

2n

2n personal , People must not repeat , Divide into

n

n

n Group , There is no difference in the grouping here , Equivalent to the division of sets ;

There are also restrictions , Each group can only put

2

2

2 Elements ;

Original simple model , Such as classification ( Add ) , Step by step ( Multiplication ) , Set arrangement , Set combination , Multiset arrangement , Combination of multiple sets , There is no corresponding model , Cannot be used directly ;

It's not a simple selection problem ;

Here we need to consider Groups are different , There is no difference between groups Two cases ;

If there is a difference in grouping , Divide into

n

n

n Group , Put the first

1

1

1 Group , choose

2

2

2 personal , Put it again

2

2

2 Group , choose

2

2

2 personal ,

⋯

\cdots

⋯ The plan is It can be calculated ;

There is no difference in grouping , At this time, we need to observe There are differences in grouping and There is no difference between The difference between :

There is no difference in grouping , Get a way , Then on

n

n

n Groups are arranged in full , Yes

n

!

n!

n! There are two ways to arrange them , The number of schemes with different groups is obtained ;

There will be Number of schemes with different grouping And Grouping does not distinguish the number of schemes Establish a correspondence :

branch

Group

no

Yes

District

other

Fang

case

Count

×

n

!

=

branch

Group

Yes

District

other

Fang

case

Count

Grouping does not distinguish the number of schemes \times n! = Number of schemes with different grouping

branch Group no Yes District other Fang case Count ×n!= branch Group Yes District other Fang case Count

Number of schemes with different grouping It can be calculated , then Divide

n

!

n!

n! , You can get Number of schemes with no difference in grouping ;

There are differences in grouping , according to Step by step processing The plan :

① The first

1

1

1 Step : from

2

n

2n

2n Of the elements , selection

2

2

2 Elements , Yes

C

(

2

n

,

2

)

C(2n , 2)

C(2n,2) Kind of plan ;

② The first

2

2

2 Step : from

2

n

−

2

2n - 2

2n−2 Of the elements , selection

2

2

2 Elements , Yes

C

(

2

n

−

2

,

2

)

C(2n - 2 , 2)

C(2n−2,2) Kind of plan ;

③ The first

3

3

3 Step : from

2

n

−

4

2n - 4

2n−4 Of the elements , selection

2

2

2 Elements , Yes

C

(

2

n

−

4

,

2

)

C(2n - 4 , 2)

C(2n−4,2) Kind of plan ;

⋮

\vdots

⋮

④ The first

n

n

n Step : from

2

n

−

(

2

n

−

2

)

2n - ( 2n - 2 )

2n−(2n−2) Of the elements , selection

2

2

2 Elements , Yes

C

(

2

n

−

(

2

n

−

2

)

,

2

)

C(2n - ( 2n - 2 ) , 2)

C(2n−(2n−2),2) Kind of plan ; That is to say

1

1

1 Kind of plan ;

Permutation and combination formula

• array :

  P

  (

  n

  ,

  r

  )

  =

  n

  !

  (

  n

  −

  r

  )

  !

  P(n,r) = \dfrac{n!}{(n-r)!}

  P(n,r)=(n−r)!n!​

• Combine :

  C

  (

  n

  ,

  r

  )

  =

  P

  (

  n

  ,

  r

  )

  r

  !

  =

  n

  !

  r

  !

  (

  n

  −

  r

  )

  !

  C(n, r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!}

  C(n,r)=r!P(n,r)​=r!(n−r)!n!​

Step by step processing You need to use the multiplication principle , take

n

n

n Multiply the number of schemes in steps :

N

=

C

(

2

n

,

2

)

C

(

2

n

−

2

,

2

)

C

(

2

n

−

4

,

2

)

⋯

C

(

2

n

−

(

2

n

−

2

)

,

2

)

=

2

n

!

2

!

×

(

2

n

−

2

)

!

×

(

2

n

−

2

)

!

2

!

×

(

2

n

−

4

)

!

⋯

(

2

n

−

(

2

n

−

2

)

)

!

2

!

×

(

2

n

−

(

2

n

−

2

)

−

2

)

!

⏟

n

individual

branch

Step

phase

ride

front

after

can

With

about

fall

very

many

rank

ride

=

(

2

n

)

!

(

2

!

)

n

\begin{array}{lcl} N &=& C(2n , 2) C(2n - 2 , 2) C(2n - 4 , 2) \cdots C(2n - ( 2n - 2 ) , 2) \\\\ &=& \begin{matrix} \underbrace{ \cfrac{2n!}{2! \times (2n-2)!} \times \cfrac{(2n-2)!}{2! \times (2n-4)!} \cdots \cfrac{(2n - ( 2n - 2 ))!}{2! \times (2n - ( 2n - 2 ) - 2)!} } \\ n Multiply by steps \end{matrix} Many factorials can be reduced before and after \\\\ &=& \cfrac{(2n)!}{(2!)^n} \end{array}

N​===​C(2n,2)C(2n−2,2)C(2n−4,2)⋯C(2n−(2n−2),2)


2!×(2n−2)!2n!​×2!×(2n−4)!(2n−2)!​⋯2!×(2n−(2n−2)−2)!(2n−(2n−2))!​​n individual branch Step phase ride ​ front after can With about fall very many rank ride (2!)n(2n)!​​

The number of schemes with different grouping is

(

2

n

)

!

(

2

!

)

n

\cfrac{(2n)!}{(2!)^n}

(2!)n(2n)!​ individual ;

according to

branch

Group

no

Yes

District

other

Fang

case

Count

×

n

!

=

branch

Group

Yes

District

other

Fang

case

Count

Grouping does not distinguish the number of schemes \times n! = Number of schemes with different grouping

branch Group no Yes District other Fang case Count ×n!= branch Group Yes District other Fang case Count

The formula ;

Number of schemes with different grouping It can be calculated , then Divide

n

!

n!

n! , You can get Number of schemes with no difference in grouping ;

The end result is

(

2

n

)

!

(

2

!

)

n

n

!

\cfrac{(2n)!}{(2!)^n n!}

(2!)nn!(2n)!​

This problem is not simple to use Original simple model , Such as classification ( Add ) , Step by step ( Multiplication ) , Set arrangement , Set combination , Multiset arrangement , Combination of multiple sets ;

Instead, it will be an Uncomputable model , Corresponding to a computable model , Then calculate the model The repeatability of