The permutation and combination questions are lively and interesting, but the questions are diverse and flexible. Therefore, to solve the problem of permutation and combination, we must first carefully examine the questions and find out whether it is a problem of permutation and combination or a problem of combination and arrangement. Secondly, we should grasp the essential characteristics of the problem and adopt reasonable and appropriate methods to deal with it.

check against the authoritative text

1. Principles of classification and counting (addition principle)

Finish one thing, have

Class method, in the 1 class method, there are

There are two different methods, and there are two of them.

Different ways, …, in the first paragraph

Class methods include

There are three different ways to achieve this: * * *:

Different methods.

2. Step-by-step counting principle (multiplication principle)

To accomplish one thing, you need to divide it into

Steps to do 1

There are two different methods in the second step.

Different ways, …, be the first.

Buyou

There are three different ways to achieve this: * * *:

Different methods.

3. The principle of classified counting is different from that of step counting.

The principles and methods of classification and counting are independent of each other, and any method can accomplish this independently.

Each step of the step-by-step counting principle is interdependent, and the method in each step completes one stage of the event, not the whole event.

The general problem-solving process of permutation and combination comprehensive problems is as follows:

1. Examine the questions carefully and find out what to do.

2. What can be done, what needs to be done, is step by step or classification, or step by step and classification at the same time, to determine how many steps to divide and how many categories to divide.

3. Determine whether each step or class is an arrangement problem (order) or a combination problem (disorder), what is the total number of elements, and how many elements are taken out.

4. To solve the synthesis problem of permutation and combination, classes and steps often cross, and some common problem-solving strategies must be mastered.

A. Special elements and special location priority strategy

Example 1. How many five-digit odd numbers can 0, 1, 2, 3, 4, 5 form without being complex?

Solution: Because the penultimate place has special requirements, priority should be given to avoid unqualified molecules occupying these two positions.

* * * at the bottom of the list is

Then the number one * * * got it.

The other positions in the last row of * * * are

Based on the principle of step counting

Position analysis and element analysis are the most common and basic methods to solve the problem of permutation and combination. If element analysis is the main method, special elements should be arranged first, and then other elements should be processed. If job analysis is the main task, the requirements of special posts should be met first, and then other posts should be dealt with. If there are multiple constraints, you often need to consider one constraint and other conditions at the same time.

Exercise: Plant seven different flowers in a row of flowerpots. If two kinds of sunflowers are not planted in the middle or in flowerpots at both ends, how many different ways are there?

2. Binding strategy of adjacent elements

Example 2. Seven people stand in a row, A and B are adjacent, C and D are adjacent. How many different arrangements are there?

Solution: First, the two elements A and B are bound into a whole and regarded as a composite element. At the same time, D can also be regarded as a composite element, and then it is arranged with other elements, and the adjacent elements are arranged by themselves. According to the principle of step by step counting, * * * has been

Different arrangements

The problem that several elements must be arranged together can be solved by binding, that is, adjacent elements need to be merged into one element and then arranged with other elements, and attention should be paid to the arrangement within the merged elements.

Exercise: Someone shot 8 shots, hit 4 shots, and hit 3 shots together. The number of different situations is 20.

3. Interpolation strategy for nonadjacent problems

Example 3. There are four dances, two cross talks and three solo dances in the evening program. If dance programs can't appear continuously, how many kinds will appear?

Solution: There are two steps. The first step is to arrange two cross talks and three solos.

The second step is to insert four dances in the six elements arranged in the first step, including two spaces at the beginning and the end.

Different methods have different program sequences according to the principle of step-by-step counting.

grow

The problem of element separation can be solved by queuing elements without position requirements and then inserting non-adjacent elements in the middle and at both ends.

Exercise: Five programs originally scheduled for a New Year's party in a class have been arranged in the program list, and two new programs have been added before the performance. If the two new programs are inserted into the original program list and the two new programs are not adjacent, the number of different insertion methods is 30.

4. Double contraction vacancy insertion strategy for scheduling problem.

There are 4.7 people in line, among which, the order of A, B and C must be different.

Solution: (Double Reduction Method) For the arrangement of some elements in a certain order, these elements can be arranged with other elements first, and then the total arrangement number is divided by the total arrangement number between these elements, so that the number of species with different arrangements is:

(Vacancy method) Suppose there are seven chairs, except for three people, A, B and C, there are four people to sit on.

The other three positions have the sitting method of 1, but there is * * *.

This method.

Thinking: Can A, B and C sit down first?

(Insertion method) Arrange Party A, Party B and Party C first, and then insert the other four people in turn, with 1 arrangement method. * * * There is a way.

Sorting problems can be reduced by doubling, and can also be transformed into placeholder interpolation.

Empty model processing

Exercise: 10 people are different in height, with 5 people in each row. The height is required to increase gradually from left to right. How many rows are there?

5. Power search strategy for rearrangement problem

Example 5. Six interns are divided into seven workshops. How many different ways are there?

Solution: There are six steps to complete: there are seven ways to assign the first intern to the workshop, seven ways to assign the second intern to the workshop, and so on, all of which are based on the principle of step-by-step counting.

Different arrangements

The characteristic of the permutation problem that allows repetition is that the elements are taken as the research object, and the elements are not limited by their positions, so the positions of each element can be arranged one by one. Generally speaking, there is no limit to the number of N different elements arranged in M positions, as shown below.

grow

Exercise questions:

1. Five programs originally scheduled for a New Year's party in a class 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 will be 42.

Eight passengers boarded the elevator on the first floor of an eight-story building. How did they get off the elevator on their respective floors?

6. Layout strategy for circular layout problem

Example 6. Eight people sat around the table. How many sitting postures are there?

Solution: The difference between sitting around a table and sitting in a row is that sitting in a circle has no head and tail, so a person is fixed.

Then expand the circle into a straight line from this position. The other seven people have (8- 1)! Seed arrangement method, namely

!

Generally, n different elements are arranged in a circle, and * * has (n- 1)! Seed arrangement method. If m elements are taken out from n different elements for circular arrangement, * * * has

Exercise: Six diamonds of different colors can be worn into several diamond rings 120.

Seven. Direct line strategy for multi-line problem

Example 7.8 There are four people in two rows, with Party A and Party B in the front row and Party C in the back row. How many rows are there?

Solution: Eight people are divided into two rows, which is equivalent to eight people sitting on eight chairs, and the chairs can be arranged in a row. Special elements include

Species, special element C in the last four positions are

Species, the remaining 5 people are randomly arranged in 5 positions.

Species, and then * * *

grow

Generally speaking, the arrangement of elements divided into multiple lines can be reduced to one line and then studied in sections.

Exercise: There are two rows of seats, front row 1 1 and back row 12. Now two people are arranged to sit, and the three seats in the middle of the front row are not allowed to sit, and these two people are not adjacent, so the number of different rows is 346.

Eight. The permutation and combination mixed problem first chooses the back row strategy.

Example 8. There are five different balls in four different boxes, and there is at least one ball in each box. How many different ways are there?

Solution: Step 1, select two composite elements from five balls.

This method. Then put four elements (including a composite element) into four different boxes.

This method, according to the principle of step by step counting, has the following methods.

To solve the problem of permutation and combination mashup, it is the most basic guiding ideology to choose the back row first. Is this method similar to the strategy of binding adjacent elements?

Exercise: There are 6 soldiers in a class, including squad leader 1 and squad leader 1. Now, four people are selected to complete four different tasks, and each person completes one task. Only 1 person is involved in the monitor and team leader, so there are 192 different options.

Nine. The strategy of small group problem first as a whole and then as a part

Example 9. When 1, 2, 3, 4, 5 constitutes a five-digit number without duplicates, how many five-digit numbers are there, and there are exactly two even clips between two odd numbers 1, 5?

Solution: Take 1, 5, 2, 4 as a group and queue with 3 * * *.

The method of seed arrangement, and then in the small group * * *

The seed metering method is based on the principle of step-by-step counting.

Seed measurement method.

In the arrangement of small groups, the whole should be followed by the part, and then other strategies should be combined to deal with it.

Exercise questions:

1. It is planned to exhibit 10 different paintings, including watercolor painting 1 painting, 4 oil paintings and 5 Chinese paintings, which are displayed in a row with the same requirements.

Varieties must be connected together, watercolor is not two ends, so the number of varieties displayed is * * *

2.5 boys and 5 girls stand in a row to take pictures, boys are adjacent and girls are adjacent.

grow

X. partition strategy of the same element problem

Example 10. Number of athletes 10, divided into 7 classes, with at least one in each class. How many distribution schemes are there?

Solution: Because there is no difference between 10, put them in a row. Nine gaps are formed between adjacent places. Insert partitions in 6 positions of 9 gaps, and divide the quota into 7 parts, which are allocated to 7 classes correspondingly. Each inserting method corresponds to a segmentation method.

Seed separation method.

N identical elements are divided into m parts (n, m is a positive integer), and each part has at least one element. The m- 1 spacer can be inserted into the n- 1 gap, where n elements are arranged in a row. All the division numbers are

Exercise questions:

1. 10 The same ball is packed in 5 boxes. How many methods are there in each box?

2 .

Find the number of groups of natural number solutions of this equation group.

Eleven. If it is difficult, it goes against the overall elimination strategy.

Example 1 1. It is different to take three numbers from ten numbers 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 to make the sum an even number not less than 10.

How many ways are there?

Solution: If it is difficult to find an even number not less than 10 directly in this problem, you can use the total elimination method. There are five even numbers and five odd numbers in the ten numbers, and the three numbers taken contain three even numbers.

, which only contains 1 even numbers, can be taken as follows

, even the * * *

. Then, 9 kinds of even numbers * * * whose sum is less than 10 are excluded, and the qualified methods are * * *.

For some permutation and combination problems, the direct consideration of the positive side is more complicated, while its negative side is often simpler. We can find its negative side first and then eliminate it from the whole.

Exercise: There are 43 students in our class and 5 students in any class. At least one of them is the chairman, vice-chairman and secretary of the Youth League branch.

How many kinds of pumping methods are there?

Twelve. Partition strategy of average grouping problem

Example 12. Six different books are divided into three piles on average. How many points are there in each pile of two books?

Solution: Read the book in three steps.

This method, but there is a phenomenon of repeated counting. Let's call six books ABCDEF. If the first step takes AB, the second step takes CD, and the third step takes EF, the division is recorded as (AB, CD, EF).

Yes (AB, EF, CD), (CD, AB, EF), (CD, EF, AB) (EF, CD, AB), (EF, AB, CD) * * Yes.

Seed method, and these points are only (AB, CD, EF) points, so * * * has.

Seed separation method.

The equally divided group, in no particular order, is a situation, so it must be divided by.

(

Equal number of groups) to avoid double counting.

Exercise questions:

1 Divide the team of 13 into three groups, one with five teams and the other with four teams. How many points? (

)

2. 10 students are divided into 3 groups, including 4 in one group and 3 in the other two groups. However, the monitor and the vice monitor cannot be in the same group. How many are different?

Grouping method (1540)

3. There are two or six classes in a high school, and now four students are transferred from other places. They should be placed in two classes in this grade, and each class is safe.

Ranked second, the number of different arrangements is _ _ _ _ (

)

Thirteen. Reasonable classification and step-by-step implementation strategy

Example 13. In a concert, there are *** 10 actors, 8 of whom can sing and 5 can dance. Now, we will perform a program with two singers and two dancers. How many ways can you choose them?

Solution: 10 Among the actors, 5 can only sing, 2 can only dance and 3 are all-around actors. Choose singers as the standard for research.

None of the five people who can only sing was chosen as a singer.

Of the five people who can only sing, only 1 was chosen as the singer.

Almost. Only two of the five people who can only sing chose singers.

Species, according to the principle of classification and counting * * *

Kindness

To solve the problem of constrained permutation and combination, we can classify the elements according to their nature and step by step according to the continuous process of events, so that the standard is clear. The step-by-step level is clear, and once the classification standard is determined, it will run through the process of solving problems.

Exercise questions:

1. Choose 4 boys and 3 girls to participate in a forum. If there must be both boys and girls among these four people, there are 34 different election methods.

2.3 adults and 2 children travel by boat.No. 1 can take up to 3 people, No.2 can take up to 2 people, and No.3 can only take up to 1 person. They can choose two or three boats, but children can't take a boat alone. How many ways can these three people take a boat? (27)

There are also the following classification criteria for this problem:

* Based on whether the three all-around actors choose singers.

* Based on whether the three all-around actors choose dancers.

* According to whether two people who can only dance are selected as dancers, the correct result can be obtained.

Fourteen Modeling strategy

Example 14. There are nine street lamps numbered 1, 2, 3, 4, 5, 6, 7, 8 and 9 on the road. Now we need to turn off three of them, but we can't turn off two or three adjacent lights or two lights at both ends. How many ways can you turn off the lights to meet the requirements?

Solution: Think of this problem as a queuing model, and insert three unlit lamps into five gaps of six lit lamps.

grow

Some difficult permutation and combination problems can be solved intuitively if they can be transformed into very familiar models, such as fill-in-the-blank model, queuing model and boxed model.

Exercise: There are 10 seats in a row * * *. If there are four people, everyone has seats on the left and right. How many different sitting positions are there? ( 120)

Fifteen. Practical exhaustion strategy

Example 15. There are five balls numbered 1, 2,3,4,5 and five boxes numbered 1, 2,3,4,5. Now put five balls in these five boxes. Each box should put a ball. There are exactly two balls with the same number as the box. How many shots are there?

Solution: Take out two of the five balls and check them with boxes.

There are still 3 balls and 3 boxes whose serial numbers can't correspond. According to the actual operation method, if there are 3, 4, 5 balls, 3, 4, 5 boxes and 3 balls in box 4, then balls 4 and 5 have only 1 packaging method. Similarly, when three balls are packed in box 5, there are only 1 packing methods for balls 4 and 5, which are based on the principle of step-by-step counting.

grow

Box 3, Box 4, Box 5

It is not easy to calculate the permutation and combination problem with complex conditions by formulas, and it is often unexpected to use exhaustive method or draw a tree diagram.

Exercise questions:

1. Four people in the same dormitory, each write a New Year card and put it away, and then each takes a New Year card from others. How many different ways are there to distribute the four New Year cards? (9)

2. Coloring an area in a drawing requires that adjacent areas use different colors. There are 4 colors to choose from, so there are 72 different coloring methods.

16. Decomposition and synthesis strategies

How many different even numbers can 16 have? Can 30030 be divisible?

Analysis: First, decompose 30030 into the product of prime factors: 30030 = 2× 3× 5× 7×1×13.

According to the meaning of the question, the even factor must first take 2, and then take some of the other five factors to form a product.

All even factors are:

Exercise: How many pairs of straight lines in different planes can eight vertices of a cube connect?

Solution: First, we choose any four vertices from eight vertices to form a four-body * * * body * * *

, every tetrahedron has

Decomposition and synthesis strategy is one of the most basic problem-solving strategies for permutation and combination problems. Break down a complex problem into several small problems and solve them one by one. Then, according to the decomposed structure of the problem, the problem is synthesized by using the principle of classified counting and the principle of step-by-step counting, so as to get the answer of the problem. This problem-solving strategy is used for every more complicated problem.

Three pairs of straight lines in different planes, eight vertices in a cube can be connected together.

Straight lines on different planes

Seventeen. Conversion strategy

Example 17. 25 people are arranged in a 5×5 square. Now choose 3 people and ask them not to be in the same row or column. How many different options are there?

Solution: The problem is simplified as 9 people arranged in a 3×3 square. Now choose three people from them and ask them not to be in the same row or column. How many ways are there? In this way, each row of 1 person must select 1 person from one of the rows, then cross out the ranks of this person, and so on. The method of selecting three people from a 3×3 square is as follows.

Kindness Then choose 3×3 squares from 5×5 squares to solve the problem. Choose 3 rows and 3 columns from a 5×5 square.

Selection method So there are three people in the 5×5 square matrix who are not in the same row or column.

Selection method.

When dealing with complex permutation and combination problems, we can degenerate a problem into a short problem, and find a solution by solving this short problem, so as to solve the original problem in the next step.

Exercise: The block of a city consists of 12 congruent rectangular areas, where the solid line represents the road. How many shortest paths are there from a to b? (

)

18. Look-up dictionary strategy for numerical ranking problem

Example 18. How many numbers greater than 324 105 can be composed of 6 numbers: 0, 1, 2, 3, 4, 5?

Solution:

The problem of number sorting can be solved by looking up the dictionary, which should look up from high position to low position, find out the numbers that meet the requirements in turn, and find out the total number according to the principle of classification and counting.

Exercise: Use six numbers, 0, 1, 2, 3, 4 and 5, to form a four-digit even number, without repetition, and arrange these numbers from small to large. The number of 7 1 is 3 140.

Nineteen. Tree diagram strategy

Example 19.

People pass the ball to each other, starting with A, as the first pass.

After the second pass, the ball still returns to A's hand, so there are _ _ _ _ different ways to pass the ball.

It is not easy to use for complex permutation and combination problems.

Formula, tree diagram will receive unexpected results.

Exercise: The numbers of people and chairs are 1, 2, 3, 4 and 5 respectively, among which

First, people don't sit.

Chair (

How many different sitting positions are there?

Table strategy for complex classification problems

Example 20. There are five balls in five colors: red, yellow and blue, which are marked with the letters A, B, C, D and E respectively. Now choose five balls from them, requiring all letters and three colors. How many different ways are there to go?

red

1

1

1

2

2

three

yellow

1

2

three

1

2

1

orchid

three

2

1

2

1

1

The pattern after that

Solution:

Some complex classified multiple-choice questions have many conditions to meet, and there are often repeated omissions. Using tabular method can make the classification clear, ensure the conditions to be met in the question type and achieve good results.

Twenty-one: Hotel Legal Strategy

To solve the problem of allowing repeated arrangement, we should pay attention to distinguish two types of elements: one type of elements can be repeated and the other type cannot be repeated. We should regard the unrepeatable elements as "guests" and the repeatable elements as "shops", and then directly solve them by the principle of multiplication.

Seven students compete for five championships, and each champion can only be won by one person. The possible types of champions are.

Analysis: Because the same student can win N championships at the same time, students can be arranged repeatedly. Seven students are seven "shops", and five champions are five "guests". Each "guest" has seven ways of accommodation, and 7 is obtained by the principle of multiplication.

Species.

summary

In this lesson, we review and consolidate several common problem-solving strategies about permutation and combination. Permutation and combination has always been a difficult point in learning. Through the exercises we usually do, it is not difficult to find that the permutation and combination problems have the characteristics of obscure conditions, changeable topics, unique solutions, huge quantities and difficult to verify. Students can only master basic problem-solving strategies skillfully. According to their situation, we can choose different skills to solve the problem. For some complicated problems, we can combine several strategies to simplify the complex and draw inferences from others, so as to lay a solid foundation for the follow-up study.