Keywords: permutation and combination, problem-solving strategies

First, the adjacent problem binding method.

Example 1.7 Students stand in a row. How many different arrangements must A and B have to stand together?

Solution: The problem of arranging two elements together can be solved by "binding". First, A, B and the other five people are arranged as an element. Considering the order of A and B, there are species.

Comments: Generally speaking, individuals stand in a row, one of which is adjacent, which can be solved by "binding" and there are different arrangements.

Second, the non-adjacent problem-null insertion method

Example 2. Seven students stand in a row. When A and B are not adjacent, how many different arrangements are there?

Solution: The method of "inserting space" is generally adopted for the nonadjacent arrangement of A and B, so the total number of nonadjacent arrangements of A and B should be:

Comments: If individuals stand in a row, where individuals are not adjacent, they can be solved by "inserting space". There are two arrangements.

Three. Complex problem-complete exclusion method

When the direct method is difficult to consider, or the classification is unclear or multiple, we can consider the "exclusion method". To solve geometric problems, we must pay attention to the restrictions of geometric figures on its constituent elements.

Example 3. (1996 National College Entrance Examination) There are seven points in the center and vertex of a regular hexagon. How many triangles are there with three of them as vertices?

Solution: There are several ways to find three points from seven points, but the center and vertex of the diagonal of a regular hexagon have three * * * lines, so there are -3 = 32 triangles that meet the conditions.

Fourth, the special factor-priority method.

For permutation and combination application problems with limited conditions, special positions can be given priority, and then other positions can be considered.

Example 4. (1995 Shanghai college entrance examination questions) 1 The teacher and four award-winning students lined up to take pictures as a souvenir. If teachers are not arranged at both ends, there are different arrangements.

Solution: First, consider the arrangement of special elements (teachers). Because the teacher is not arranged at both ends, you can choose a position in the middle three positions, and the arrangements of other students are different, so * * * has = 72 different arrangements.

Example 5. (National College Entrance Examination in 2000) Table Tennis Team 10, 3 players are the main players, and 5 players are sent to participate in the competition. Three main players should be arranged in the first, third and fifth positions, and the other seven should be arranged in the second and fourth positions, so there are different arrangements for playing.

Solution: Because the No.1, No.3 and No.5 positions are special, only the main players can be arranged, and there are two arrangements, while the other seven players choose two positions at No.2 and No.4 positions, so there are = 252 different arrangements for playing.

Five, multivariate problems-classified discussion method

For many elements, many choices can be discussed according to the needs, and finally a total is made.

Example 6. (Beijing Spring Recruitment in 2003) The five programs originally scheduled for a New Year's party have been arranged in the program list, and two new programs have been added before the performance. If these two programs are inserted into the original program list, the number of different insertion methods is (a).

A.42 B.30 C.20 D. 12

Solution: The two new programs can be divided into two situations: 1. Not adjacent: * * There are A62 species; 2. Adjacent: * * There are A2A6 1 species. Therefore, the number of different interpolation methods is: A62 +A22A6 1=42, so A is selected.

Example 7. As shown in the figure, a region is divided into five administrative regions, and now the map is in color, which requires that adjacent regions cannot use the same color. There are four colors to choose from, so how many different coloring methods are there? (Answer with numbers)

Solution: 1 area is adjacent to the other four areas, and every other area is adjacent to three areas, and three or four colors can be painted. There are =24 methods for coloring with three colors and =48 methods for coloring with four colors, so there are 24+48=72 methods for * * *, and 72 should be filled in.

Six, the mixed problem-the first choice and the back row method

For mixed application problems with permutation and combination, the strategy of selecting elements first and then arranging them can be adopted.

Example 8. (2002 Beijing College Entrance Examination) 12 Students went to three different intersections to investigate the traffic volume. If there are 4 students at each intersection, the different allocation scheme will be ().

A. species B.

C. species D.

Solution: This problem belongs to uniform grouping problem. Then 12 students were all divided into three groups * * * There are ways, three different intersections have different distribution schemes * * * There are: kinds, so choose A.

Example 9. (Beijing College Entrance Examination in 2003) Three vegetables were selected from four kinds of vegetables, namely cucumber, Chinese cabbage, rape and lentil, and planted on three plots of land with different soil qualities, among which cucumber must be planted, and the different planting methods are ().

A.24 kinds of B. 18 kinds of C. 12 kinds of D.6.

Solution: select the back row first and implement it step by step. According to the meaning of the question, the different selection method is C32, and the different arrangement method is A3 1 A22, so the different planting method is A3 1 C32 A22 = 12, so C should be chosen.

Seven. Distribution-baffle separation method for the same elements

Example 10. Send the same book 10 to three student reading rooms numbered 1, 2 and 3, and the number of books allocated to each reading room shall not be less than its number. Try to find out the number of differences. Please use as many methods as possible to solve the problem and consider whether these methods are suitable for more general situations.

This question examines the combination problem.

Solution: Let reading rooms 2 and 3 get 1 book and 2 books in turn; Distribute the remaining seven books and ensure that there is at least one book in each reading room, which is equivalent to inserting two identical "I" (generally regarded as "partition") in six "gaps" between seven identical books. * * * There are 15 insertion methods.

In a word, the way to solve the application problem of permutation and combination can be summarized as follows: clear permutation and grouping, clear addition and multiplication; Orderly arrangement, disorderly combination; Classification is addition, step by step multiplication.

Specifically, there are usually the following methods to solve the application problems of permutation and combination:

(1) takes elements as the main body, that is, meet the requirements of special elements before considering other elements.

(2) Take site selection as the main body, that is, first meet the requirements of special site selection, and then consider other site selection.

(3) Calculate the number of permutations or combinations without considering additional conditions, and then subtract the number of unqualified permutations and combinations.

Strategies for solving permutation and combination problems

Zhang, No.2 Middle School in Anlu City, Hubei Province

The knowledge of permutation and combination is widely used in practice, and mastering the knowledge of permutation and combination can help us solve many practical application problems in production and life. The problem of simultaneous permutation and combination has always been a long-standing problem. Therefore, in order to fully grasp the knowledge of permutation and combination, it is necessary to summarize the law and method of solving problems of permutation and combination.

First of all, talk about the general problem-solving rules of permutation and combination comprehensive problems:

Whether 1) uses "classification counting principle" or "step counting principle" depends on the way we finish a thing. We can use the "classification counting principle" when the classification is completed, and use the "step counting principle" when it needs to be completed step by step; So, how to determine whether it is classified or step by step? "Classification" means that any one of them can complete a given event independently, while "step by step" needs to complete all the steps of a given event. Therefore, to accurately understand the two principles, it is emphasized that several methods to accomplish a thing do not interfere with each other, are independent of each other, cross each other into an empty set, and integrate into a complete set. No matter which method is used, things can be done independently. The principle of step-by-step counting emphasizes that all steps are indispensable, and all steps need to be completed in order to complete this thing.

2) The definitions of permutation and combination are similar, and their difference lies in whether they are related to order.

3) Complex permutation problems are often visualized by experiments, and "tree diagram" and "block diagram" are drawn to seek solutions. Because the correctness of the results is difficult to test, it is often necessary to solve them in different ways to get the test.

4) Classification according to the nature of elements and gradual progress according to the continuity of events are the basic thinking methods to deal with the problem of permutation and combination, and attention should be paid to the meanings of restrictive words such as "at least, at most".

5) The general idea is to select elements (combinations) first, then arrange them, "classify" according to the nature of elements and "step by step" according to the process of events, which is always the basic principle and method to deal with the problem of permutation and combination. Through problem-solving training, pay attention to accumulate and master the basic skills of classification and gradual progress, ensure that each step is independent, and make the classification standard clear, and the level of gradual progress is clear, with no emphasis or omission.

6) When solving the synthesis problem of permutation and combination, we must deeply understand the concept of permutation and combination, be able to classify the problems skillfully, and keep in mind the formula of permutation and combination number and the nature of combination number. The common mistakes are duplication and missing counting.

In short, the basic laws to solve the permutation and combination problem are: classification addition, step-by-step multiplication, clear permutation and grouping, and clear addition and multiplication; Orderly arrangement, disorderly combination; If it is difficult, it will be reversed and indirectly ruled out.

Secondly, while grasping the essential characteristics and laws of problems, we should flexibly use basic principles and formulas to analyze and solve them, and at the same time pay attention to some problem-solving strategies and methods, so that some seemingly complicated problems can be solved easily. Here are several commonly used problem-solving methods and strategies.

First, the "priority arrangement method" of special elements (bits): for the arrangement and combination of special elements (bits), the special is generally considered first, and then others are considered.

Example 1. Use five numbers, 0, 2, 3, 4 and 5, to form a three-digit number. There are no duplicate numbers, and even numbers * * * have ().

A.24 B.30 C.40 D.60

[Resolution] Because the three digits are even, the number at the end must be even, and because 0 can't rank first, 0 is one of the "special" elements and should be given priority. It can be divided into two categories: the last 0 and the last 0: 1) A42 in the last row, and C2 1A38 in the last row.

2. Total elimination method: For negative problems, unqualified ones can be eliminated from the total. For example, in the case of 1, this method can also be used to solve the problem: there is an A53 in the full arrangement of five numbers forming three digits. After arrangement, it is found that 0 can't be ranked first, and numbers 3 and 5 can't be ranked last. These two permutations should be excluded, so there are A53-3A42+C21A31= 30 even numbers.

3. Reasonable classification and accurate step-by-step classification of the constrained permutation and combination problems, and step-by-step classification according to the nature of the elements and the continuous process of things, so that the classification standards are clear, the step-by-step levels are clear, and no weight is missed.

4. Binding method of adjacent problems: When solving the problem of requiring some elements to be adjacent, first consider the whole problem, and "bind" the adjacent elements into a "big" element, and then consider the binding method.

Example 2, there are 8 different books; Among them, there are 3 math books, 2 foreign language books and 3 books on other subjects. If these books are arranged in a row on the bookshelf, and the math books are also arranged together, then there are () ways to arrange the foreign documents together. (Results are expressed in numerical values)

Solution: "Bundle" three math books together as a big book, and "bundle" two foreign language books together as a big book. Together with the other three books, it is regarded as five elements. * * * has the arrangement of A55; The other three math books are arranged in A33, and two foreign language books are arranged in A22. According to the principle of step-by-step counting, * * has a permutation method A55 A33 A22= 1440 (species).

Note: When using the binding method to solve the permutation and combination problem, we must pay attention to the internal order of "binding" large elements.

5. "Interpolation" is used for nonadjacent problems: nonadjacent problems mean that some elements cannot be adjacent and are separated by other elements. To solve this problem, we can arrange other elements first, and then insert the specified non-adjacent elements into the gaps and positions at both ends, so it is called interpolation.

Example 3: Use 1, 2, 3, 4, 5, 6, 7, 8 to form an eight-digit number without repeating numbers. Requirements 1 is adjacent to 2, 2 is adjacent to 4, 5 is adjacent to 6, and 7 is not adjacent to 8. There are eight digits like (). (Answer with numbers)

Solution: Since 1 is required to be adjacent to 2 and 2 to 4, the three numbers 1, 2 and 4 can be bound together to form a big element, and only 2 can be arranged in the middle of this big element, and 1, 4 can be arranged on both sides, so there are A22 arrangement methods in the big element, and then 5 and 6 can be bound into a big element. Arrange these three elements first. * * * has 33 arrangements, then choose two from the gaps formed by the three elements arranged in front and the four positions at both ends of * * *, and insert the numbers 7 and 8 which are not adjacent to each other. * * * There are A42 insertion methods, so the qualified octet * * has A22A3A342 = 288 (species).

Note: When solving nonadjacent problems by interpolation, pay attention to whether the position to be inserted includes both ends.

6. Use "division" to fix the order: For the problem that some elements are arranged in a certain order, you can first arrange these elements together with other elements, and then divide the total arrangement number by the total arrangement number of these elements.

Example 4: Six people line up, and A, B and C line up in the order of "A-B-C". How many kinds of queuing methods are there?

Analysis: There are A66 queuing modes regardless of additional conditions, and only one of A33 queuing modes of A, B and C meets the requirements. So there are A66 ÷A33 = 120 eligible permutation methods. (or A63)

Example 5. Four boys and three girls are not equal in height. Now, line them up, from left to right, and ask the girls to line them up from short to high. How many arrangements are there?

Solution: First, four of the seven positions were given to boys, with the arrangement of A74, and the remaining three positions were given to girls, with only one arrangement, so there was the arrangement of A74. (It can also be A77 ÷A33)

7. The problem of arrangement is solved by "straight row": the problem of arranging several elements in several rows can be solved by arranging them in one row.

Example 6. Seven people sit in two rows, three in the first row and four in the second row. How many different sitting positions are there?

Analysis: Seven people can sit in the first two rows at will, and there are no other conditions, so the two rows can be regarded as one row, and there are 77 different sitting methods.

Eight. Item-by-item test method: When the additional conditions in the questions increase and the difficulties are directly solved, the rules are gradually found through experiments.

Example 7. Fill the number 1, 2, 3, 4 in the box with the number 1, 2, 3, 4, and fill 1 in each box. The number of filling methods for different numbers in a square is ().

A.6 B.9 C. 1 1 D.23

Solution: The first box can hold 2 or 3 or 4. If the first box is filled with 2, the second box can be filled with 1 or 3 or 4. If the second box is filled with 1, then the last two boxes have only one method. If the second box is filled with 3 or 4, then there is only one filling method for the last two boxes. There are nine ways to fill in A * * *, choose B.

Nine, the structural model "partition method"

For the complicated arrangement problem, we can design another scenario and build a partition model to solve the problem.

Example 8. How many positive integer solutions does the equation a+b+c+d= 12 have?

Analysis: Establish baffle model: arrange 12 identical balls in a row, insert 3 baffles randomly in the gap between them, and divide the balls into 4 piles. The number of balls in each pile obtained by each division corresponds to a set of positive integer solutions of A, B, C and D, so the number of groups of positive integer solutions of the original equation.

Another example is the number of non-negative integer solutions of equation a+b+c+d= 12, which can be solved by this method.

10. If there are difficulties, use the reverse exclusion method.

For the most or least permutation and combination problem, if the direct answer needs complicated discussion, we can consider the method of "overall impurity removal", that is, deleting the unqualified permutation and combination in the group, so as to calculate the qualified permutation and combination number.

Example 9. Three TV sets are randomly selected from four A-type and five B-type TVs, including at least 1 A-type TV sets and 1 B-type TV sets, so there are () different ways to choose * *.

A. 140 species B.80 species C.70 species D.35

Solution: Among the three stations taken out, there is no extraction method that does not contain a or does not meet the meaning of the question, so the extraction method that meets the meaning of the question is C93-C43-C53=70 (species), so C.

Note: This method is suitable for exercises with clear negative situation and simple calculation.

XI。 Step-by-step exploration method: the problem of complex situation and difficult to find its law needs careful analysis and exploration.

Example: 10, from 1 to 100. If two different numbers are taken at a time to make their sum greater than 100, how many different numbers are taken?

Solution: In the addition of two numbers, the smaller number is the addend,1+100 >; When 100 and 1 are addends, 1, 2 is addend, …, 49 is addend, 50 is addend, but 5 1 is addend, 48 is addend, …, 99.

Twelve. One-to-one correspondence:

For example: 1 1. How many games does it take to make a single-round knockout among 100 players (that is, to quit the competition after failing) to finally win the championship?

Solution: To produce a champion, all players except the champion must be eliminated, that is, 99 players must be eliminated and 1 player must be eliminated, so there are 99 games.

It should be pointed out that the above methods are commonly used to solve the general permutation and combination problems, but they are not absolute. Mathematics is a very flexible course, and there are sometimes many solutions to the same problem. At this time, we should think carefully and choose the best method flexibly. There are also "classification", "arrangement" and "equal probability method" of multivariate problems, so I won't go into details here.