Combinatorial mathematics Chapter 2 Notes

Two counting rules

 

  notes ： When using the four rules of addition, subtraction, multiplication and division , Note that events must be independent of each other .

Circular arrangement

To transform a circular arrangement into a well-known row arrangement requires a cut between two random adjacent elements , And for a man with n The circular arrangement of elements corresponds to n Two different row arrangements , So the number of permutations is equal to the number of row permutations divided by n.

Necklace arrangement

 

  Rearrangeable

In rearrangement , Elements are not only repeatable but also finite .

When calculating, it is converted to no rearrangement and divided by the redundancy .

Example

 

Multiple full permutations

 

It can be recombined

 

  This model is equivalent to r An indistinguishable ball , Placed in n In a different box , Each box can hold 0 One or more balls

Of course, it can also be seen as n-1 Two different partitions will r The same ball is divided into n Two different areas .

solution 1：

  Add the regroupable elements to the sequence number , It is easy to solve the problem by constructing a non repeated equivalent non duplication combination .

  solution 2： Door frame solution

 

Nonadjacent combinations

 

solution ： By adding with the serial number to construct a new non duplication combination to solve .

 

 

  summary ：