[combinatorics] Introduction to Combinatorics (context of combinatorics | skills of combinatorics | thought of combinatorics 1: one-to-one correspondence)

One 、 Context of Combinatorial Mathematics

---

Combinatorial existence problem : Pigeon nest principle , Remsey Theorem ;

Combination counting problem :

Counting theorem : Principle of tolerance and exclusion , Polya Theorem ;

The count method : Recurrence equation , Generating function , Exponential generating function ;

Counting model : Selection scheme , Solution of indefinite equation , Non descending path problem , Split plan , Release plan ;

Combinatorial enumeration problem : generating algorithm , Combination design ;

Combinatorial optimization problem : Shortest path problem , Minimum spanning tree , network optimization ;

Three important combination ideas :

• One-to-one correspondence
• Mathematical induction
• Upper and lower bounds approximation method

Two 、 Combinatorial mathematics thought 1 : One to one correspondence skills

---

One to one correspondence skills : Count something To Another kind of counting , Another kind of counting has a very obvious result , The number of the two counts is the same ;

Example

1

1

1 :

3

×

3

×

3

3 \times 3 \times 3

3×3×3 The cube , How many times do you need to cut , Can be cut into

27

27

27 A small cube ;

The central cube ,

6

6

6 All the faces are cut out , Must cut

6

6

6 The knife , To get it

6

6

6 Face to face ;

The number of faces of the central cube , And Number of knives cut yes One-to-one correspondence Of ;

Example

2

2

2 :

n

n

n Athletes compete , Elimination system , How many games are needed ;

n

−

1

n-1

n−1 Time , Number of matches And Number of people eliminated One-to-one correspondence ;

3、 ... and 、 Combined counting model And One-to-one correspondence

---

The count method : Counting model And Practical problems Make a correspondence ;

Counting model :

• Select the question
• Nonnegative integer solutions of indefinite equations
• Non descending path problem
• Integer splitting problem
• The problem of putting the ball

The above models are very typical combined counting models , Many practical problems can establish one-to-one correspondence with one of the above models , In this way, the formula and method of the above model can be used , To solve practical problems ;

Refer to the previous study Stirling Number of subsets , 【 Set theory 】Stirling Number of subsets ( Stirling subset number concept | Ball model | Stirling Recursive formula of subset number | Binary relation of division Refinement relation ) Two 、 Ball model ,

A collection of Division problem , Stirling Subset number problem ,
And Ball model Medium The ball has a number , The box has no number ( Different balls are put in the same box ) Number of models
One-to-one correspondence ;