Arrangement is related to the order of elements, and combination has nothing to do with order. For example, 23 1 and 2 13 are two permutations, and the sum of 2+3+ 1 is a combination.
(1) Two basic principles are the basis of arrangement and combination.
(1) addition principle: There are n ways to do one thing, and finish it. In the first way, there are m 1 different ways, in the second way, there are m2 different ways, ... and in the n ways, there are mn different ways, so there are n = M 1+M2 to complete it.
(2) Multiplication principle: To do one thing, it needs to be divided into n steps. There are m 1 different ways to do the first step, m2 different ways to do the second step, ... and mn different ways to do the nth step, so there are n = m1× m2× m3××××× Mn different ways to do it.
Here, we should pay attention to distinguish between these two principles. If there are n ways to do one thing, it is a classification problem. The first method is independent, so addition principle is used; To do one thing, it needs to be divided into n steps, and the steps are continuous. Only by completing several interrelated steps in succession can it be completed, so the principle of multiplication is used.
There are essential differences between "class" and "step" in completing a thing in this way, so there are also differences between the two principles.
(2) Arrangements and the number of arrangements
(1) arrangement: take any m(m≤n) elements from n different elements and arrange them in a certain order, which is called the arrangement of m elements in n different elements.
From the meaning of arrangement, we know that if two arrangements are the same, not only the elements of the two arrangements must be exactly the same, but also the order of the arrangement must be exactly the same, which tells us how to judge whether the two arrangements are the same.
(2) permutation number formula: take out all permutations of m(m≤n) elements from n different elements.
When m = n, it is a complete permutation PNN = n (n-1) (n-2) ... 3.2.1= n!
(3) Combination and number of combinations
(1) combination: taking any m(m≤n) elements from n different elements and combining them into a group is called taking m elements from n different elements.
From the definition of combination, if the elements in two combinations are exactly the same, they are the same combination regardless of the order of the elements; Only when the elements in two combinations are not exactly the same are they different combinations.
(2) Number of combinations: take out all combinations of m(m≤n) elements from n different elements.
Here we should pay attention to the differences and connections between arrangement and combination. Take any m(m≤n) elements from n different elements, and there is essential difference between "arranging in a column in a certain order" and "combining in a group in any order".
1. Arranging and combining parts is one of the difficulties in middle school mathematics, because
(1) Abstracting several concrete mathematical models from various practical problems requires strong abstract thinking ability;
(2) The restrictive conditions are sometimes obscure, which requires us to accurately understand the key words in the question (especially logical related words and quantifiers);
(3) The calculation method is simple and has little connection with the old knowledge, but it needs a lot of thinking when choosing the correct and reasonable calculation scheme;
(4) Whether the calculation scheme is correct can't be tested by intuitive methods, which requires us to understand the concepts and principles and have strong analytical ability.
Two Basic Counting Principles and Their Applications
(1) addition principle sum classification counting method
1. addition principle
2. addition principle's collective form
3. 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 even number, that is, choose two numbers from the ten numbers 1, 3, 5, ..., 19 or 2, 4, 6, 8, ..., 20 as the arrangement, from which arithmetic progression can be determined, so this question is 2.
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 of the same color from six pairs of gloves;
(2) There are 10 ways to choose a glove from the remaining ten gloves.
(3) Besides the two pairs of gloves mentioned above, there are eight ways to choose one of the eight pairs of gloves;
(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. * * * There are three columns, so =90 kinds.
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: these two people want to be locksmiths and have balls;
The second category: one of these two people has to be a fitter and has seeds;
The third category: neither of them can pretend to be forced, but they have the ball.
So there are 185 kinds of * *.
Example 7. There are six cards printed with 0, L, 3, 5, 7 and 9. If 9 is allowed as 6, how many different three digits can be formed by randomly drawing three cards?
Analysis: Some students think that only the arrangement number of 0, L, 3, 5, 7 and 9 multiplied by 2 is the requirement, but in fact, if there are 9 in the three numbers, it is possible to replace them with 6, so we must classify them.
The extracted three numbers contain 0 and 9, and there is a path;
The extracted three numbers contain 0 but not 9, so there is a way;
The extracted three numbers contain 9 but not 0, so there is a way;
The extracted three numbers contain neither 9 nor 0. There is a way.
And because the number 9 can be used as 6, * * has two methods of × (+)+= 144.
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 * * * has a parking method.
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 is at the forefront and there is a way to stand.
The second category: B is not in the front row, and of course it can't be in the back row, so there is a way to stand.
* * * * station method.
(2) The first category: A at the end and B at the head. There is a way.
The second category: A is at the end of the row and B is not at the head. There is a way.
The third category: B is a pioneer and A is not a pioneer. There is a way.
The fourth category: A is not at the end of the row, and B is not at the head. There is a way.
***+2+=3 12 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.
The first step: there is the possibility of the fifth test;
Step 2: There are genuine products in the first four times.
Step 3: The first four times are possible.
* * * It's possible.
4. Binding and Insertion
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.
Analysis: (1) There is a way.
(2) There are ways.
(3) there is a way.
(4) there is a way.
(5) This problem cannot be interpolated, nor can it be interpolated continuously.
Indirect solution: full arrangement-adjacent to Party A-adjacent to Party B-adjacent to Party D+adjacent to Party A and Party D, * * *-+= 23,040 methods.
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 out of five air formed between four empty guns, that is.
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.
* * * = 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, Party A, Party B and Party C can only stand in one order, so the previous rows are 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.
5. 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) There is one.
(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.