Ball and box model

Many permutation problems , Can be abstracted as : from a In a small ball , Select several , Put it in b In a box , Ask the total number of plans for all the methods

The box Elements in , It's out of order ! This is an axiom , Because that's the definition of a box

such as , In a box (a, b), that , As for how it is sorted [a, b] still [b, a]?
This is not concerned , It's also indiscriminate , All belong to one plan .

The box will have a capacity limit , such as At least 1 individual or Put at most k individual or Put any …

Whether the box is the same or not , Between the boxes There is no order problem !

That is, the same scheme ( namely , The ball has been put into the box ), The order of boxes is independent quantity , There is no box arrangement problem

For small balls , It is divided into : All the balls are the same and All little balls are different

Whether the balls are the same , How to distinguish ?

such as , Yes 2 A different box A, B, There are two balls a, b, requirement : Put all the balls in the box , Each box can hold any

1. If it is : The same ball , namely (a, b identical )
   The overall plan includes : A( 1 individual ), B( 1 individual ), A( 0 individual ), B( 2 individual ),A( 2 individual ), B( 0 individual ), share 3 A plan
   You can find , When the balls are the same , We no longer care about the ball logo , Just pay attention to the number of small balls !!
   Although the ball id Logo has a, b, But in this problem , The logo is cleared , Make no exception
   For example, for : A( 1 individual ), B( 1 individual ), as for A Inside is a still b, No concern , This belongs to yes 1 A plan

2. If it is : Different balls , namely (a, b Different )
   The overall plan includes : A( a), B( b), A( b), B( a), A( 0 individual ), B( ab),A( 2 individual ), B( ab), share 4 A plan
   At this time, the ball has id Marked , But be careful A( ab), There is no order in this , This is the definition of a box

For box , It is divided into : All boxes are the same and All boxes are different

Whether the boxes are the same , How to distinguish ?

such as , Yes 2 A different ball a, b, Yes 2 Boxes A, B. requirement : Put all the balls in the box , Each box can hold any

1. If it is : Same box , namely (A, B identical )
   The overall plan includes : In a box ( a), Another box ( b), In a box ( 0 individual ), Another box ( ab), share 2 A plan
   You can find , At this time, we call it A box , Another box ..., With the box A, B Identification is irrelevant

2. If it is : Different boxes , namely (A, B Different )
   The overall plan includes : A( a), B( b), A( b), B( a), A( 0 individual ), B( ab),A( ab), B( 0 individual ), share 4 A plan
   At this time, the box has id Marked

Linear series

For the same Ball and box model , According to its box is same or Different , It can be determined whether it is Linear

If All boxes are the same , He is Linearly independent . Because all boxes are the same , Any order belongs to a scheme
conversely , All boxes are different , Call it Linear correlation Of . Because the box is different , Its order is important

there order , It's not the order of boxes ( The above mentioned , Ball and box model , There is no order relationship between boxes
there order , yes All the little balls In each box , Sequence of placement

Linear sequence of different boxes

Such as the 3 A different box : B1, B2, B3
Convert it to Linear series , It's simple , Let the linear sequence be : S: [S1, S2, S3]
take B1, B2, B3 The box , Just bijection mapping to [S1, S2, S3] in , Any mapping is ok As long as satisfaction is double shot
Convenience , Direct mapping : B1->S1, B2->S2, B3->S3;
Si, It represents the small ball in the box . ( It could be numerical Same ball , Could be a collection Different balls )
But you have to promise , This set of mapping rules , It works for all schemes ; Different schemes use different mapping rules , This is not allowed

Linear series , In fact, it corresponds to All boxes , But he can write linear Array way
The number of elements in the sequence , Is the number of boxes ; Because each element is a box , So don't pay attention to the order of the child elements inside
namely : Linear series [ab, empty ] and [ba, empty ] Is the same ;

Linear sequence of the same box

about Same box Linearization of , Compared with the above Different boxes , A little different
His mapping rules , You can't choose a double shot at will , Nor can all schemes use the same mapping rule
It is : All schemes use the same sort The rules , No longer focus on mapping rules (sort Rules and mapping rules , It doesn't matter. )

Such as the 3 A different box : B1, B2, B3, Its linear sequence is : [S1, S2, S3]
There is one and Different boxes The situation is the same : Si and Bi It's the same !! The only problem is the mapping rules
such as , To determine the Bi -> Sj, be : Bi What is it? , Sj Also what

• If it is Same ball
  be B1, B2, B3 Represents a natural number , natural Si It also means natural number
  take B1, B2, B3 Conduct sort After ordering , That is to say [S1, S2, S3]
  here , Two linear sequences are equal , Equivalent to : Two Si The natural numbers of are equal

• If it is Different balls
  be B1, B2, B3 Represents the collection of small balls
  ( Although the balls are different , but B1, B2, B3 There may still be the same , Because the box may be empty , such as B1, B2 All empty sets ;)
  here , There is still a need for B1, B2, B3 Conduct sort, But the sorting of sets here is special
  The sorting rules are as follows : (1. The empty set is the smallest ) (2. In the set , The smallest ball is the identification of the set The smallest ball , That is, the ball with the smallest subscript )
  such as , The box has : B1 = {a5, a2}B2 = empty B3 = {a6, a1} ( Be careful , B1={a5,a2}, Or you could write it as {a2,a5})
  Its sort After is : [ S1, S2, S3] = [ B2, B3, B1]
  here , Two linear sequences are equal , Equivalent to : Two Si The set of is equal
  Set equal : Two sets form a bijection .

Say more , although All options Use the same sort The rules , But it has nothing to do with the mapping rules
For example, the mapping rule of a scheme is : B1 -> S2, The mapping of another scheme may be : B1 -> S3

summary

Following Linear series , Both are applicable to Same box , Can also be applied to Different boxes

For example, the total number of schemes is n individual , Then there is n A linear sequence
this n A linear sequence , Must be different from each other ; namely , programme and Linear series , Form a double shot

therefore , Define two linear sequences == Equal sign rule , crucial . The following rules :

• The length of the two sequences is the same
• Two elements with the same subscript are the same

here , It also needs to be defined : Elements of two linear sequences == Equal sign rule , The following rules :

Elements of a linear sequence :

• if Same ball , said : Natural number .
  here , Equivalent to : Determine whether the two values are the same

• if Different balls , said : Collection of small balls
  here , Equivalent to : Determine the same of two sets
  The assembly is the same The necessary and sufficient conditions for : (1. The two sets are the same size ) (2. Two sets form a bijection )
  such as : aggregate A{a1, a2}, aggregate B{a2, a1}, These two sets are the same

Ball and box model in , Originally, there is no spatial relationship between boxes !
adopt Linearization , Make it into a Linear series , More intuitive .

More importantly : After linearization , Because it is a one-dimensional array , It is easier to calculate all schemes ( All different sequences , That is, the total number of schemes )

such as , Yes 2 A different ball a, b, Put in 2 Boxes A, B, Any box
It can be seen from the above analysis :

1. If the box is the same , The plan has : In a box ( a), Another box ( b), In a box ( 0 individual ), Another box ( ab), share 2 A plan
   Its linear sequence is : [a, b][ empty , ba] ( Write ba And write ab It's the same , Because it's a set )

2. If the box is different , The plan has : A( a), B( b), A( b), B( a), A( 0 individual ), B( ab),A( 2 individual ), B( 0), share 4 A plan
   Its linear sequence is : [a, b][b, a][ empty , ab][ba, empty ] ( Write ba And write ab It's the same , Because it's a set )

Same box and Different boxes ` The nature and relevance of

Because of the Linearization , Make the research of this problem simple .

nature

** Same box The nature of ( Small balls can be the same , It can be different ): **

In the whole linear sequence All A linear sequence in a set A by : [S1, S2, S3]
Its full arrangement : [S1, S3, S2] [S2, S1, S3] ..., be :

1. The full arrangement , None of them legal Linear series
   because , Legal linear sequence , Must go through sort, None of this is sorted Of , Are not All In the assembly

2. The full arrangement , Can be equivalent to The same linear sequence A
   such as , All linear sequences ( Not necessarily legal ) Yes X individual , Then the legal sequence is : X / (n!) individual (n Number of boxes )

** Different boxes The nature of ( Small balls can be the same , It can be different ): **

In the whole linear sequence All A linear sequence in a set A by : [S1, S2, S3]
Its full arrangement : [S1, S3, S2] [S2, S1, S3] ..., be :

• If S1, S2, S3 Different from each other , be : Fully arrange each linear sequence , All correspond to one scheme
  namely , from A Derived from this 5 It's a full permutation , They are all different schemes ;

• If S1, S2, S3 There is the same in , be : For all linear sets , Conduct unique Deduplication
  such as , [3, 2, 2], Its full arrangement 3! = 6 individual , Conduct unique after , Only : [2, 2, 3][2, 3, 2][3, 2, 2]

There needs to be a The formula , namely : [a, a, b, b, b, c] Its full arrangement unique after , How many ?
For any of them Full Permutation A Come on : A = [x1, x2, x3, x4, x5, x6]
among , There must be 2 individual a, 3 individual b, 1 individual c, Make All = 6!

• such as , a The position is : x2, x4, Then you are A On the basis of , In exchange for x2, x4
  Then we get a new Full Permutation [x1, x4, x3, x2, x5, x6]
  This arrangement , stay x angle Is different ; But in a The angle of the element It's the same , These two permutations , It's the same
  Due to all permutations , All include 2 individual a;
  So for any permutation , There are others 1 Permutation , Repeat ; All It must be 2 Multiple .
  namely , All /= 2 after , At this time, all are arranged , If you look at it alone a Elements , There is no repeated arrangement

• Look again b, For example, he is in A The position in is : x1, x3, x5, Then you are A On the basis of , Arbitrarily arrange this 3 A place
  x1, x5, x3x3, x1, x5 …
  You can get : 3! - 1 = 5 individual , this 5 Permutation , From the single view b The angle of the element , It's exactly the same
  Due to all permutations , All include 3 individual b;
  So for any permutation , There are others 5 Permutation , Repeat ; All It must be 6 Multiple .
  namely , All /= 6 after , At this time, all are arranged , If you look at it alone b Elements , There is no repeated arrangement

• c The elements are only 1 individual , There is no repetition ;

Sum up , All /= 2; All /= 6 after , That is, for all full permutations unique After Number of permutations ;
namely , n Elements , The number of the same elements is : c1, c2, c3, .., cm (c1 + c2 + ... + cm == n)
Then unique After The number of permutations is : n! / c1! / c2! / ... / cm!

relation

In the same Ball and box model Next , Study its identical and Different The connection of the box

from Same box -> Different boxes

about Same box Next , One of its linear sequences A by : [ S1, S2, S3, ..., Sn]
Then they are all arranged n! individual , stay Same box Next , Are equivalent to A

And this n! It's a full permutation , stay Different boxes Next , If it is finished unique The number after operation is y individual
Then this y Permutation , stay Different boxes Next , Are all legal Different linear sequences

namely : Same box Next , A linear sequence , Corresponding Different boxes Under the y A linear sequence !!

so : In the same Ball and box model Next , Different boxes Number of alternatives A certain >= Same box Number of alternatives .

from Different boxes -> Same box

about Different boxes Next , One of its linear sequences A by : [ S1, S2, S3, ..., Sn]

set up A Conduct sorted The sequence after is B

because , A Of unique Full arrangement after (x individual ), stay Different boxes Next , All belong to different linear sequences

And this x Permutation , Its sorted after , Are all B

so , You can also get : In the same Ball and box model Next , Different boxes Number of alternatives A certain >= Same box Number of alternatives .

Multiplication principle

stay Ball and box model in , If the ball is : There are the same little balls , There are different balls . such as : [1, 1, 2, 2, 3]

And Between different balls , No impact .

• Between different balls , Have an impact on .
  such as : $Number\; of\; permutations{A}_a^b$ Look at , He is b A different ball , But this b Pellet Cannot be separated , They influence each other !
  because , For example, a small ball is already The first i Box No , Then another ball You can't put it in The first i In box No !
  If you put this b Separate different balls , Will appear : In a box , There are many small balls , So you can't split

• Between different balls , No influence .
  such as , We allow Different balls It can be put in the same box ; Then there is no correlation between different balls .
  This can be b A different ball , Split it into a single , individualization , Finally, the principle of multiplication .

That is, for a certain Ball and box model Mode, The ball is : [1, 1, 2, 2, 3] (1, 1 It's the same ball , 1, 2 It's a different ball )
If , Between different balls , It can be put in the same box , That is, there is no mutual influence

be , The original question = ( The small ball is 1 1 In the Mode The next plan ) * ( The small ball is 2 2 In the Mode The next plan ) * …

Example

• https://www.acwing.com/file_system/file/content/whole/index/content/6061250/