From n different elements, any m(m≤n) elements are arranged in a column in a certain order, which is called the arrangement of m elements in n different elements; All permutation numbers of m(m≤n) elements taken from n different elements are called permutation numbers of m elements taken from n different elements, which are represented by symbols A(n, m) or P(n, m).

A(n，m)= n(n- 1)(n-2)……(n-m+ 1)= n！ /(n-m)！ (When n=m, the denominator of the above formula is 0! = 1).

Combination and calculation formula

Taking out any m(m≤n) elements from N different elements and grouping them is called taking out the combination of M elements from N different elements; The number of all combinations of m(m≤n) elements from n different elements is called the number of combinations of m elements from n different elements. Use symbols.

C(n, m) stands for. (c is a combination).

C(n，m)=A(n，m)/m！ =n！ /((n-m)！ *m！ ); C(n，m)=C(n，n-m)；

3. Other permutation and combination formulas

Cyclic permutation number of r elements in n elements =A(n, r)/r=n! /r(n-r)！ .

N elements are divided into K classes, and the number of each class is n 1, n2, ... nk. The total arrangement number of these n elements is

n！ /(n 1！ *n2！ *...*nk！ ).

K-type elements, the number of each class is infinite, and the combined number of M elements is C(m+k- 1, m).

Two Basic Counting Principles and Their Applications

(1) addition principle sum classification counting method

1. addition principle

2. addition principle's collective form

Classification requirements

Each method in each class can accomplish this task independently; The specific methods in the two different methods are different from each other (that is, the classification is not heavy); Any method to accomplish this task belongs to a certain category (that is, classification does not leak)

(2) Multiplication principle and step counting method.

1. Multiplication principle

2. Reasonable step-by-step requirements

One method of any step can't complete this task, and only by continuously completing these n steps can this task be completed; Each step is independent of each other; As long as the methods used in a step are different, the corresponding methods to complete it are also different.

[Example analysis] Selected lectures on permutation and combination thinking methods

1. First, clarify the meaning of the task.

Example 1. From 1, 2, 3, ... and 20 to form a arithmetic progression, and such different arithmetic progression has _ _ _ _ _.

Analysis: First of all, the complex life background or other mathematical background should be transformed into a clear permutation and combination problem.

Let A, B and C be equal, ∴ 2b=a+c, and we know that B is determined by A and C.

And ∵ 2b is an even number, ∴ a, c is an odd number or an even number, that is, two numbers, ..., 1, 3, 5, or 2, 4, 6, 8, ..., 20 are arranged, from which arithmetic progression can be determined.

Example 2. A city has four east-west streets and six north-south streets with the same spacing, as shown in the figure. If it is stipulated that you can only walk in two directions along the route in the picture, how many different ways are there from M to N?

Analysis: The analysis of the actual background can be deepened layer by layer.

(1) From m to n, you must take three steps, five steps to the right and eight steps to * * *.

(2) Whether each step is upward or correct determines the different paths to take.

(3) In fact, when the upward step is decided, the remaining steps can only be moved to the right.

So the task can be described as: choose which three steps to go up from the eight steps, and then you can determine the number of steps.

The answer to this question is: 56.

2. Pay attention to the characteristics of addition principle and multiplication principle, and analyze whether it is classified or step by step, arranged or combined.

Example 3. In a side-by-side field with 10 ridges, choose two ridges to plant two crops, A and B, one for each. In order to facilitate the growth of crops, it is required that the interval between two crops should be no less than 6 ridges, and there are _ _ _ _ different selection methods.

Analysis: The condition of "the distance between A and B crops is not less than 6 ridges" is not easy to be expressed by a formula containing the number of rows and combinations, so the classification method is adopted.

The first category: A is in the first ridge, and B has three choices;

The second category: A is on the second ridge, and B has two choices;

The third category: A is in the third ridge, and B has a choice.

Similarly, the positions of A and B are interchanged, *** 12.

Example 4. Choose 4 pairs of gloves from 6 pairs of gloves with different colors, and one pair of gloves with the same color is _ _ _ _ _ _ _ _.

240(B) 180(C) 120(D)60

Analysis: Obviously, this problem should be solved step by step.

(1) There are six ways to choose a pair of gloves with the same color from six gloves, C(6,1) = 6;

(2) Choose a glove from the remaining ten gloves. There are C( 10, 1)= 10 methods.

(3) There are eight ways to choose a glove from eight gloves except the above two pairs of gloves: C(8,1) = 8;

(4) Because the selection has nothing to do with the order, the selection methods in (2) and (3) are repeated once, so there are ***240 kinds.

Example 5. Six people with different heights are arranged in two rows and three columns. Everyone in the first row is shorter than the people behind the same column, so the number of all different arrangements is _ _ _ _ _.

Analysis: As long as two people are selected in each column, there is only one standing method, so the queuing method in each column is only related to the selection method of this person. * * * has three columns, so there are 90 kinds of C (6.2) * C (4.2) * C (2.2) = C.

Example 6. 1 1 Of the workers, five can only be locksmiths, four can only be turners, and the other two can be locksmiths and turners. At present, out of 1 1, four people are chosen as fitters and four as turners. How many different options are there?

Analysis: Using addition principle, first of all, do not weigh or miss points. How to do this? Classification standards must be consistent.

Taking two versatile workers as the classification object, consider taking several of them as locksmiths as the classification standard.

The first category: both of them are locksmiths, C (7,4) = 35;

Category II: One of these two people is a locksmith, and there are 75 kinds of C (6,4 4) * C (5 5,4);

Category III: Neither of them is a fitter, and there are 75 kinds of C (5,4 4) * C (6 6,4).

So there are 185 kinds of * *.

Example 7. There are six cards printed with 0, 1, 3, 5, 7 and 9. If 9 is allowed to be used for 6 purposes, how many different three digits can be formed by randomly drawing three cards?

Analysis: Some students think that it is enough to multiply the arrangement number of 0, 1, 3, 5, 7 and 9 by 2, but in fact, if there are 9 out of 3 numbers, it is possible to replace them with 6, so we must classify them.

The extracted three numbers include 0 and 9, and there are 4*4*2=32 methods;

The extracted three numbers contain 0 but not 9, and there are 6*4=24 methods;

The extracted three numbers contain 9 but not 0, and there are 6*6*2=72 methods;

The extracted three numbers contain neither 9 nor 0, and there are 4×6=24 methods.

*** 152 species.

Example 8. There is a row of 12 parking spaces in the parking lot. Eight cars will be parked today, and the empty parking spaces are required to be connected. Different parking methods are _ _ _ _ _.

Analysis: Take the empty parking space as one element and arrange it with eight cars and nine elements, so there are * * * P(9.8) parking modes.

3. Special elements should be given priority; Special position, priority

Example 9. Six people stood in a row begging.

(1) The number of permutations where A is not at the head and B is not at the end.

(2) The number of rows where A is not at the beginning, B is not at the end, and A and B are not adjacent.

Analysis: (1) First consider the head row and the tail row, but these two requirements affect each other, so consider the classification.

The first category: B in the head, with P (5,5) stop loss method.

The second category: B is not in the front row, of course, he can't be in the back row, and there are 4x4xXP (4,4) stops.

* * * p (5,5)+4x4xp (4,4) = 504 station method.

(2) The first category: A is at the tail, B is at the head, and there is a P (4,4) method.

The second category: A is at the end of the queue and B is not at the head. There are 3xp (4,4) methods.

The third category: B is a pioneer and A is not a pioneer. There is a 4xp (4,4) method.

The fourth category: A is not at the end of the team, and B is not at the head. There is a p (3,3) XP (4,4) method.

* * * p (4 4,4)+3xp (4,4)+4)+p (3 4,4)+p (3,3 3) xp (4 4,4) = 312 species.

Example 10. Six different genuine products and four different defective products of a product are tested one by one until all the defective products are identified. If all the defective products are found in the fifth test, how many possibilities are there in this test method?

Analysis: This question means that the product tested for the fifth time must be defective and the last time, so the fifth test should be completed step by step as a special position.

Step 1: The fifth test has C(4. 1) possibilities;

Step 2: The first four products have the possibility of C(6. 1).

Step 3: There are P(4.4) possibilities in the first four times.

C(4. 1)* C(6. 1)* P(4.4)

Binding and inserting

Example 1 1. Eight people lined up.

(1) A and B must be adjacent (2) A and B are not adjacent.

(3) Party A and Party B must be adjacent, and Party C must not be adjacent. (4) Party A and Party B must be adjacent, and Party C must be adjacent.

(5) Party A and Party B are not adjacent, and Party B and Party D are not adjacent.

(1) Party A and Party B must be adjacent, that is, Party A and Party B are bound (Party A and Party B can be interchanged), and 7 people are arranged at P(7.7)*2.

(2) Party A and Party B are not adjacent to each other P(8.8)-P(7.7)*2

(3) Party A and Party B must be adjacent to each other, but not to Party C..

1. Party A and Party B must be adjacent to each other and to Party C, P(6.6)*2*2.

Party A and Party B must be adjacent and not adjacent to Party C P(7.7)*2-P(6.6)*2*2.

(4) Party A and Party B must be adjacent, and Party B must be adjacent to P(6.6)*2*2.

(5) Party A and Party B are not adjacent, and Party B and Party D are not adjacent.

P(8.8)-P(7.7)*2*2+P(6.6)*2*2

Example 12. Someone fired eight shots, fired four shots, and fired three shots in a row. How many different situations are there?

Analysis: ∵ Three consecutive hits cannot be adjacent to a single hit, so it is a matter of inserting space. Besides, it doesn't make any difference if you don't fight, so don't count. That is, the arrangement of two of the five air guns formed between the four empty guns, that is, P(5.2).

Example 13. There are ten street lamps numbered 1, 2, 3, ..., 10 on the road. In order to save electricity and see the road clearly, you can turn off three lights, but two or three adjacent lights cannot be turned off at the same time. How many ways can you turn off the lights that meet the requirements?

Analysis: that is, the closed lights cannot be adjacent or at both ends. Because there is no difference between lights, the problem is to choose three empty lights to go out in six spaces that do not include seven lights at both ends.

* * c (6.3) = 20 methods.

4. Indirect counting method. (1) exclusion method

Example 14. Three rows, three columns and nine points. How many triangles can be formed with these points as vertices?

Analysis: Some problems are difficult to solve directly, and indirect methods can be used.

The number of solving methods = the number of combinations of any three points-the number of methods of three points on a straight line * * *,

* * * species.

Example 15. How many tetrahedrons can be formed by taking out four of the eight vertices of a cube?

Analysis: the number of solving methods = the number of combinations of any four points-the number of methods of four points in the * * * plane,

* * *- 12 = 70- 12 = 58.

Example 16. l，2，3，3，4，5，6，7，8，9，9，9，9，9，9， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 10， 1

Analysis: Because cardinality cannot be 1.

(1) 1 must be a real number when 1 is selected.

(2) When 1 is not selected, two of 2-9 are selected as cardinality, real numbers and * * *, where log24=log39, log42 = log93, log23 = log49 and log32 = log94.

So a * * * has 53.

(3) Make up a stage and turn it into a familiar problem.

Example 17. Six people line up and ask A to be in front of B (not necessarily adjacent). How many different ways are there? What if Party A, Party B and Party C are required to be arranged from left to right?

Analysis: (1) Actually, A is in front of B, and A is behind B, which is symmetrical and has the same arrangement number. So there are =360 kinds.

(2) First, consider the full staff arrangement for six people; Secondly, A, B and C can only stand in one order, so the number of rows in front is repeated, ∴ *** 120.

Example 18.5 Men's and women's volleyball teams form a row, and boys are required to follow the order from high to low. How many different methods are there?

Analysis: First of all, regardless of the standing posture requirements of boys, there are * * * kinds; There is only one standing method for boys from high to short from left to right, so the above standing method is repeated several times. So there are =9×8×7×6=3024 species.

If boys go from right to left in the order from high to short, there is only one way to stand, and there are 3024 ways to do the same, so there are 6048 ways.

Example 19. Three identical red balls and two different white balls are lined up. How many different ways are there?

Analysis: First, I think that the three red balls are different from each other, and there is a * * * method. Because three red balls occupy the same position, * * * changes, so ***=20 kinds.

Use of baffle

The quota of10 is allocated to eight classes, and each class has at least one quota. How many different distribution methods are there?

Analysis: The position of 10 is regarded as ten elements, and in the nine spaces formed between these ten elements, seven positions are selected to place baffles, so each placement method is equivalent to an allocation method. So * * * 36 kinds.

6. Pay attention to the differences and connections between permutation and combination: all permutations can be regarded as taking the combination first and then making the whole permutation; Similarly, combination, such as adding a stage (sorting), can be transformed into a permutation problem.

Example 2 1. Take out two even numbers and three odd numbers from 0, l and 2.

Analysis: Choose the back row first. In addition, the selection of special element 0 should be considered.

(1) If the selected two even numbers contain 0, there is a seed.

(2) If the selected two even numbers do not contain 0, there is a seed.

Example 22. The elevator has seven passengers and stops at each floor of the 10 building. If three passengers go out from the same floor, the other two go out from the same floor, and the last two go out from different floors, how many different ways are there?

Analysis: (1) Firstly, seven passengers are divided into four groups: three passengers, two passengers, one passenger and one person.

(2) Choose four floors of 10 to go downstairs.

* * * You have seed.

Example 23. Use the numbers 0, 1, 2, 3, 4 and 5 to form a four-digit number without repeating numbers.

How many different four-digit numbers can (1) form?

(2) How many different four-digit even numbers can be formed?

(3) How much can four digits be divided by three?

(4) Arrange the four digits in (1) from small to large, and ask what are the 85 items?

Analysis: (1) has 5*5*4*3=300.

(2) Divided into two categories: bottom 0, with seeds; 0 is not at the bottom, there are seeds.

* * * * species.

(3) First, list four numbers whose addition can be divisible by 3 from small to large, that is, choose first.

0, 1,2,3

0, 1,3,5

0,2,3,4

0,3,4,5

1,2,4,5

The number of their permutations must be divisible by 3, and then there are: 4×()+=96 kinds.

(4) First of all, 1 has =60.

The first two digits are 20 = 12.

The first two digits are 2 1 = 12.

Therefore, item 85 is the smallest number with the first two digits of 23, that is, 230 1.

7. Grouping problem

Example 24. Six different books

(1) Give it to Party A, Party B and Party C, each with two copies. How many different ways are there?

(2) How many different ways are there to divide into three piles, each with two books?

(3) There are three piles, one pile, two piles and three piles. How many different ways are there?

(4) A, B and C, how many different ways are there?

(5) Give it to Party A, Party B and Party C, with one copy for one person, two copies for one person and three copies for the third person. How many different ways are there?

Analysis: (1) moderate.

(2) That is, the order is removed on the basis of (1), and there are seeds.

(3) There are seeds. Because this is an uneven grouping, it contains no order.

(4) There is one kind. Same as (3), because the holdings of A, B and C are certain.

(5) There are seeds.

Example 25. Six people take two different cars, and each car can take up to four people, so the different modes of riding are _ _ _ _ _.

Analysis: (1) Consider dividing 6 people into 2 people and 4 people, and 3 people and 3 people into two groups respectively.

Category I: Divide into groups of 3 people on average. There is a way.

Category II: Divided into 2 persons and 4 persons in each group. There is a way.

(2) Consider getting on two different cars.

Comprehensive ① ②, there are seeds.

Example 26. Five students are assigned to four different science and technology groups to participate in the activities, and each science and technology group has at least one student to participate, so there are _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Analysis: (1) Firstly, five students were divided into two groups, one for each group.

It involves dividing into four groups on average, and there are = groups.

(2) Consider assigning them to four different science and technology groups. There is one kind,

According to (1) and (2), ***=240 species.