Educational:

Development of the ability to solve combinatorial problems using the method of exhaustive enumeration of options;

Developing the ability to apply mathematical theory in specific situations;

Introducing students to the elements of humanities related to mathematics.

Development of the ability to independently choose a solution method and the ability to justify the choice;

Developing the ability to solve problems using only logical reasoning;

Development of the ability to make a choice of a rational coding method;

Development of communicative and creative abilities of students.

Foster a sense of responsibility for the quality and results of the work performed; Instill a conscious attitude to work;

Create responsibility for the final result.

interactive board; handouts (color stripes: white, blue, red); task cards.

Organizing time. Learning new material. Practical part. Reflection Marking Homework assignment

Organizing time.

Updating the topic and motivation.

50 rubles, 100 rubles, 50 rubles, 100 rubles; 50 rubles, 50 rubles, 100 rubles, 100 rubles (slide No. 2 and No. 3).

Learning new material .

Combinatorics is a branch of mathematics devoted to solving problems of selecting and arranging given elements according to given rules

A common question in combinatorial problems is “ In how many ways ...?" or

« How many options …?»

Solution Flag

Options BSK, BKS, SBK, SKB, KBS, KSB.

Answer: 6 options.

It turns out that not only the Russian flag has these three colors. There are states whose flags have the same colors.

KBS - Luxembourg,

Netherlands.

France SKB

Teacher: Let's find a rule for solving such problems through logical reasoning.

Let's look at the example of colored stripes. Let's take a white stripe - it can be rearranged 3 times, take a blue stripe - it can only be rearranged 2 times, because one of the places is already occupied by a white stripe, take a red stripe - it can only be placed once.

TOTAL: 3 x 2 x 1=6

Basic rule of the work :

Multiplication rule: if the first element in a combination can be chosen in a ways, after which the second element can be chosen in b ways, then the total number of combinations will be equal to a x b . (slide No. 8)

Exercise for the eyes. (slide No. 9)

Exercise "Shapes".

Draw a square, circle, triangle, oval, rhombus with your eyes clockwise, and then counterclockwise.

Practical part

Teacher: Now let's move on to mathematical problems. (we distribute cards with tasks)

One rather famous musketeer has 3 elegant hats, 4 wonderful cloaks and 2 pairs of excellent boots in his wardrobe. How many costume options can he create? (We select one element from three sets, that is, we make a “three”, which means that according to the multiplication rule we get 3 4 2 = 24 costume options.)

There are 11 people on the football team. It is necessary to select a captain and his deputy. In how many ways can this be done? (There are 11 people in total, which means the captain can be chosen in 11 ways, there are 10 players left from which the deputy captain can be chosen. So, the pair of captain and his deputy can be chosen in 11 10 = 110 ways.)

How many different two-digit numbers can be made using the numbers 1, 4, 7, if the numbers are repeated? (You should get a two-digit number - only two positions. In the first position you can put any of the proposed numbers - 3 options for choosing, in the second position, taking into account the possibility of repeating a number, there are also 3 options for choosing. This means that we make up a pair of numbers in 3 3 = 9 ways , i.e. you get 9 numbers.

How many different three-digit numbers can be made from the digits 1, 2, 3, 4, 5, provided that no digit is repeated? (Three-digit number: first position - 5 options for numbers, second position, taking into account the exclusion of repetitions of numbers - 4 options, third position - 3 options. We get 5 4 3 = 60 numbers.)

How many different two-digit numbers can be made from the numbers 0, 1, 2, 3 if the numbers: a) can be repeated; b) cannot be repeated? (a) A two-digit number, like any multi-digit number, cannot begin with 0, therefore, in the first position you can put only 3 of the available 4 digits, 3 choices, in the second position, taking into account repetition, you can put any of the digits - 4 options to choose from. Therefore, it turns out 3 4 = 12 numbers; b) The first position – 3 options, the second position – 3 options, because repetition is excluded. We get 3 3 = 9 numbers.)

The safe code consists of five different numbers. How many different options for creating a cipher? (5 4 3 2 1 = 120 options.) In how many ways can 6 people be seated at a table with 6 cutlery? (6 5 4 3 2 1 = 720 ways.)

6 devices?(6 5 4 3 2 1 = 720 ways.)

(8 7 6 5 4 = 6720 options.)

(The numbers used are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 - a total of 10 digits, excluding by convention 0 and 9 at the beginning of the number, taking into account the possibility of repetition, we get 8 10 10 10 · 10 · 10 · 10 = 8,000,000 numbers.)

Reflection

Teacher: Guys, our lesson is coming to an end. Do you think we have achieved our goal today, why? What was difficult in the lesson, how can you deal with it? Think and give yourself a mark for your work and work, put it yourself, none of the guys will see this mark, try to be honest with yourself. Did you fully participate in the lesson? What needs to be done to get better results?

In addition, students are asked to answer 3 quick questions:

In today's lesson I was... (easy, usually, difficult)

I… (learned and can apply, learned and find it difficult to apply, did not learn)

My self-esteem for the lesson...

You don’t have to sign the answers to the above questions, because their main function is to help the teacher analyze the lesson and its results

Summarizing . Marking

Teacher: I am very glad that many of you worked well today and learned a lot of new things, but I would really like for all of you to work hard at home and not get bad grades in the next lesson.

7. Homework assignment :

1) Create a problem about your class

2) Several countries decided to use symbols for their national flag in the form of 3 horizontal stripes of different widths, different colors - white, blue, red. How many countries can use such symbols, provided that each country has its own flag?

3) a) How many two-digit numbers can be made from the numbers 1, 3, 5, 7, 9?

b) How many two-digit numbers can be made from the numbers 1, 3, 5, 7, 9, provided that the numbers should not be repeated

Teacher : So, I was glad to meet you, take an interest in mathematics, it will undoubtedly be reflected in a positive way in your thoughts and actions. The lesson is over. Thanks to all. Goodbye.

Literature:

E.A. Bunimovich, V.A. Bulychev. Probability and statistics in the general education school mathematics course: lectures 1-4, 5 – 8. – M.: Pedagogical University “First of September”, 2006.

Vilenkin N.Ya. Mathematics. 5th grade: textbook for general education. institutions / N.Ya. Vilenkin and others - M.: Mnemosyna, 2009.

Smykalova E.V. Additional chapters on mathematics for 5th grade students. SPb: SMIO. Press, 2006.

5th grade. "Mathematics-5", I.I. Zubareva, A.G. Mordkovich, 2004.

Tasks (cards)

One rather famous musketeer has 3 elegant hats, 4 wonderful cloaks and 2 pairs of excellent boots in his wardrobe. How many costume options can he create?

There are 11 people on the football team. It is necessary to select a captain and his deputy. In how many ways can this be done?

How many different two-digit numbers can be made using the numbers 1, 4, 7, if the numbers are repeated

How many different three-digit numbers can be made from the digits 1, 2, 3, 4, 5, provided that no digit is repeated?

How many different two-digit numbers can be made from the numbers 0, 1, 2, 3 if the numbers: a) can be repeated; b) cannot be repeated?

The safe code consists of five different numbers. How many different options for creating a cipher?

In how many ways can 6 people be seated at a table on which 6 devices?

In the fifth grade, 8 subjects are studied. How many different schedule options can be created for Monday, if there should be 5 lessons on this day and all the lessons are different?

1. How many possible seven-digit phone numbers can be created if you exclude numbers starting with 0 and 9?

Answers

We select one element from three sets, that is, we make a “three”, which means that according to the multiplication rule we get 3 4 2 = 24 costume options.

There are 11 people in total, which means the captain can be selected in 11 ways, leaving 10 players from whom you can choose a deputy captain. So, a pair, the captain and his deputy, can be chosen in 11 10 = 110 ways.

You should get a two-digit number - only two positions. In the first position you can put any of the proposed numbers - 3 choices, in the second position, taking into account the possibility of repeating the number, there are also 3 choices. This means that we make up a pair of numbers in 3 3 = 9 ways, i.e. you get 9 numbers.

Three-digit number: first position - 5 options for numbers, second position, taking into account the exclusion of repetitions of numbers - 4 options, third position - 3 options. We get 5 4 3 = 60 numbers.

(a) A two-digit number, like any multi-digit number, cannot begin with 0, therefore, in the first position you can put only 3 of the available 4 digits, 3 choices, in the second position, taking into account repetition, you can put any of the digits - 4 options to choose from. Therefore, it turns out 3 4 = 12 numbers; b) The first position – 3 options, the second position – 3 options, because repetition is excluded. We get 3 3 = 9 numbers.

5 4 3 2 1 = 120 options.

1. 6 5 4 3 2 1 = 720 ways

2. 8 7 6 5 4 = 6720 options

   The numbers used are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 - a total of 10 digits, excluding by convention 0 and 9 at the beginning of the number, taking into account the possibility of repetition, we get 8 10 10 10 10 10 10 = 8,000,000 numbers.

Class: 5

In this article we will look at one of the lessons in the 5th grade mathematics course, dedicated to introducing combinatorics.

Lesson objectives.

Educational:

Introduce students to a new type of problem (combinatorial problems), methods for solving them - enumerating possible options, constructing a tree of possible options, applying the multiplication rule;

Introduce a new concept - factorial, consolidate it when solving problems, examples, equations.

Educational:

Formation of respect for comrades, the ability to listen and hear the interlocutor

Formation of an attitude towards friendship as one of the most important human values.

Developmental:

Formation of interest in the subject;

Formation of computing skills;

Development of logical thinking;

Developing the ability to prove and substantiate one’s opinion.

During the classes

1. Organizational moment

Teacher: Today we have an unusual lesson. We will solve problems related to one of the most interesting branches of mathematics - combinatorics. In science and in real life, very often we have to solve problems, the main question of which is the question “In how many ways can this be done?” For example:

In how many ways can you grade a student in class?

In how many ways can you assign a class monitor?

In how many ways can you assign two classroom attendants?

When solving such problems, you have to make various combinations from a finite number of elements and count the number of combinations. Such problems are called combinatorial problems, and the branch of mathematics in which such problems are considered is called combinatorics. You will find out what other topic the lesson will be devoted to when we check how you did your homework.

2. Checking homework completion

(In the previous lesson, homework is compiled in such a way that there are exactly 6 tasks. For example, in the textbook by Vilenkin N.Ya. et al. this could be No. 693(a, c), 735(1), 765(a, b, V))

On the board there is a table and cards attached with magnets. On the cards on one side is the answer to the homework assignment, on the other side is the letter.

Teacher: Let's check your homework. Open your notebooks and take your pencils. Find answers to homework numbers.

Students go to the board one at a time, choose a card with the answer and attach it to the cell of the table under the task number. First, the cards are fixed in the cells of the table with the side on which the answer is written up, so that students can check the correctness of their homework. The rest check their answers in their notebooks.

Answer options (located on different sides of the cards). There are deliberately excessive numbers of cards, so that some of the answers are incorrect.

“5” - if everything is correct

“4” - if one error

“3” - 2-3 errors

“2” - more than 3 errors

Teacher: Let's turn the cards over, what word did you get? (FRIENDSHIP). Indeed, today in the lesson we will not only solve mathematical problems, improve calculation skills, but also talk about friendship.

3. New material.

Teacher: So, we have already said that today we will learn to solve problems, the main question of which is the question “In how many ways..”.

There are three words “FRIENDSHIP”, “BUSINESS”, “LOVES” (cut pieces of paper with these words - 7 cards for each word). In how many ways can these words be used to form a sentence?

Students offer options, these options are written on the board.

Answer: 6 ways.

Teacher: Which option do you think is correct from the point of view of the Russian language? (Friendship loves business). How do you understand this statement?

Teacher: Here was a complete enumeration of all possible options, or, as they usually say, all possible combinations. Therefore, this is a combinatorial problem. Let's think about how we can write down and formalize the solution to this problem.

1 way. Let's denote the proposed words in capital letters:

FRIENDSHIP – D

LOVES – L

DELO – E (let’s take the second letter of this word)

Then all the methods you named can simply be listed: DLE, DEL, LDE, ICE, EDL, ELD.

It turns out that the solution can be formulated in the form of a model called a tree of possible options. Firstly, it is clear, like any picture, and, secondly, it allows you to take everything into account without missing anything,

Students, under the guidance of the teacher, draw up a diagram:

Method 3 (reasoning)

One of three words can come first: FRIENDSHIP, LOVES, BUSINESS. If the first word is chosen, then the second place can be one of the two remaining words, and the third place can only have one remaining word. So, the total options are: .

Note that the last technique is called multiplication rule.

Each of these three methods has its own advantages and disadvantages (discuss) The choice of solution is yours! Let us note, however, that the multiplication rule allows us to solve a wide variety of problems in one step.

Anya has 3 friends, and she bought each of them a chocolate bar and wants to give them to them for the holiday. In how many ways can she do this?

Solution: Students perform the solution on the board (the solution is performed in 3 ways)

There are 6 people in the company of friends: Andrey, Boris, Vitya, Grisha, Dima, Egor. In the school canteen there are 6 chairs at the table. The friends decided to sit on these 6 chairs differently every day while having breakfast. How many times can they do this without repetition?

Teacher: Which method will we choose? (Students, under the guidance of the teacher, should come to the conclusion that this is the third way - the multiplication rule).

The student draws up the solution on the board.

For convenience of reasoning, we will assume that friends sit down at the table one by one. We will assume that Andrey is the first to sit down at the table. He has 6 chair options. Boris is the second to sit down and independently chooses a chair from the 5 remaining ones. Vitya makes his choice third and he will have 4 chairs to choose from. Grisha will already have 3 options, Dima – 2, Egor – 1. According to the multiplication rule, we get:

The answer is 720 days or almost 2 years.

Teacher: As we see, the conditions of the problems are different, but the solutions are essentially the same. It is convenient, therefore, to introduce the same notation for these answers.

Definition: the product of all natural numbers from 1 to n inclusive is called n - factorial and is denoted by the symbol n!

Sign P! reads “En factorial”, which literally translated from English means “consisting of P multipliers.” Let us note an important feature of this value – its rapid growth.

Calculate:

a) 1!; b) 2!; at 3!; d) 4!; e) 5!; e)10!

They think it's 0! =1 (write)

Task 5.

Teacher: FRIENDSHIP is one of the most important wealth a person can have. It is not for nothing that poems and songs are composed about friendship, proverbs and sayings are written. What proverbs and sayings about friendship do you know?

A friend in need is a friend indeed.
Don't have a hundred rubles, but have a hundred friends.
There is safety in numbers.
Die yourself, but help your comrade.
An old friend is better than two new ones.
Life is hard without a friend.

Well done! It is very important for every person to have good, true friends. Let's solve a few examples using a new concept - factorial, and learn a new proverb about friendship.

Cards with answers are completed with a reserve (there are cards with numbers that are not answers).

Table after filling:

Task 6.

4 friends came to visit Vasya, and they are going to watch a new film. Vasya has a chair in his room and he also brought 4 chairs from the kitchen. He will undoubtedly take the chair himself, and seat his friends on the chairs. Vasya calculated that he could seat his friends in 24 ways.

Teacher: Did Vasya calculate correctly? (Yes, from a mathematical point of view)

Did he do well? (The moral aspect of the problem is discussed)

4. Physical education moment.

Teacher: Now let’s rest a little, and for this we’ll do a physical exercise for a minute. If I read the expression correctly, then you stand up and raise your hands up, and if incorrectly, sit down with your hands at your side.

We got up. Let's start, be careful.

6. Independent work.

Teacher: Well, now that we have had a good rest, let's check what we learned to do today in class. To do this, we will do our own work.

7. Homework.

Come up with, write down the conditions and solutions of 2 combinatorial problems on the topic “Family”. Draw up on A4 sheets, you can make drawings for the tasks.

8. Lesson summary.

Let's summarize the lesson.

What new did you learn? (We received the multiplication rule, examined its geometric model - a tree of options, introduced a new concept - factorial)

What did you like?

What do you remember?

Lesson grades.

Literature:

1. E.A. Bunimovich, V.A. Bulychev. Probability and statistics in the general education school mathematics course: lectures 1-4, 5 – 8. – M.: Pedagogical University “First of September”, 2006.
2. Vilenkin N.Ya. Mathematics. 5th grade: textbook for general education. institutions / N.Ya. Vilenkin and others - M.: Mnemosyna, 2009.
3. Smykalova E.V. Additional chapters on mathematics for 5th grade students. SPb: SMIO. Press, 2006.
4. Mordkovich A.G. Events. Probabilities. Statistical data processing: Additional. Paragraphs for the algebra course 7-9 grades. educational institutions / A.G. Mordkovich, P.V. Semenov. – M.: Mnemosyne, 2006.

Dedicated to solving problems of selecting and arranging elements of a certain, usually finite, set in accordance with given rules. For example, how many ways can you choose 6 cards from a deck of 36 cards, or how many ways can you make a queue consisting of 10 people, etc. Each rule in combinatorics determines a way to construct a certain construction made up of elements of the original set and called combination. The main goal of combinatorics is to count the number of combinations that can be made from the elements of the original set in accordance with a given rule. The simplest examples of combinatorial constructions are permutations, placements and combinations.

The birth of combinatorics related to work B. Pascal and P. Fermat on gambling, major contributions were made by Leibniz, Bernoulli, and Euler. Currently, interest in combinatorics is associated with the development of computers. In combinatorics, we will be interested in the possibility of defining quantitatively different subsets of finite sets for calculating probability in the classical way.

To determine the cardinality of the set that corresponds to a particular event, it is useful to understand two rules of combinatorics: the product rule and the sum rule (sometimes called the principles of multiplication and addition, respectively).

Product rule: let from some finite set

1st object can be selected k 1 ways,

2nd object - k 2 ways

n-th object - k n ways. (1.1)

Then an arbitrary set of listed n objects from this set can be selected k 1 , k 2 , …, k n ways.

Example 1. How many three-digit numbers are there with different digits?

Solution. There are ten digits in the decimal system: 0,1,2,3,4,5,6,7,8,9. The first place can be any of the nine digits (except zero). In second place is any of the remaining 9 digits, except the selected one. The last place is any of the remaining 8 digits.

According to the product rule, 9·9·8 = 648 three-digit numbers have different digits.

Example 2. From point There are 3 roads leading to a point, and 4 roads from point to point. In how many ways can you travel from in through ?

Solution. In point there are 3 ways to choose the road to the point, and at the point there are 4 ways to get to the point. According to the principle of multiplication, there are 3x4 = 12 ways to get from a point to point .

Sum rule: if conditions (1.1) are met, any of the objects can be selected k 1 +k 2 +…+k n ways.

Example 3. How many ways are there to select one pencil from a box containing 5 red, 7 blue, 3 green pencils?

Solution. One pencil, according to the sum rule, can be chosen in 5+7+3 = 15 ways.

Example 4. Let him out of town The city can be reached by one air route, two train routes and three bus routes. How many ways can you get from the city? in town ?

Solution. All the conditions of the addition principle are met here, therefore, in accordance with this principle, we get 1+2+3 = 6 ways.

Let's consider an example illustrating the difference between the principles of multiplication and addition.

Example 5. An electronics store sells three brands of televisions and two types of VCRs. The buyer has the option of purchasing either a TV or a VCR. In how many ways can he make one purchase? How many different sets containing a TV and a tape recorder can be purchased in this store if the buyer is going to buy both a TV and a VCR in pairs?

Solution. One TV can be selected in three ways, and a tape recorder in the other two ways. Then a TV or tape recorder can be bought in 3+2=5 ways.

In the second case, one TV can be selected in three ways, after which the VCR can be selected in two ways. Therefore, due to the principle of multiplication, you can buy a TV and VCR in 3 × 2 = 6 ways.

Let us now consider examples in which both rules of combinatorics are applied: both the principle of multiplication and the principle of addition.

Example 6. There are 12 apples and 10 oranges in a basket. Vanya chooses either an apple or an orange. After which Nadya chooses both an apple and an orange from the remaining fruits. How many such choices are possible?

Solution. Vanya can choose an apple in 12 ways, an orange in 10 ways. If Vanya chooses an apple, then Nadya can choose an apple in 11 ways, and an orange in 10 ways. If Vanya chooses an orange, then Nadya can choose an apple in 12 ways, and an orange in 9 ways. Thus, Vanya and Nadya can make their choice in ways.

Example 7. There are 3 letters, each of which can be sent to 6 addresses. In how many ways can this be done?

Solution. In this problem we must consider three cases:

a) all letters are sent to different addresses;

b) all letters are sent to one address;

c) only two letters are sent to one address.

If all letters are sent to different addresses, then the number of such methods is easily found from the principle of multiplication: n 1 = 6×5×4 = 120 ways. If all letters are sent to one address, then there will be such methods n 2 = 6. Thus, it remains to consider only the third case, when only 2 letters are sent to one address. We can select a letter in 3 ways, and we can send it to any selected address in 6 ways. We can send the remaining two letters to the remaining addresses in 5 ways. Therefore, we can send only two letters to one address n 3 =3×6×5=90 ways. Thus, you can send 3 letters to 6 addresses in accordance with the addition principle

ways.

Typically, combinatorics considers an idealized random selection experiment. k elements from n. In this case, the elements: a) are not returned back (selection scheme without returns); b) return back (selection scheme with return).

1. Selection scheme without returns

Accommodation from n elements by k is any ordered set of k elements belonging to n- elemental set. Different arrangements differ from each other either in the order of elements or in composition.

Number of placements from n elements by k denoted and calculated by the formula

(1.2)

Where n! = 1×2×3×…× n, 1! = 1, 0! = 1.

Example 8. 10 people participate in the competition, three of them will take 1st, 2nd, 3rd place. How many different options are there?

Solution. In this case, the order in which the seats are distributed is important. The number of different options is equal

Rearrangement from n elements are called placement of n elements by n. Number of permutations from n elements stand for Pn and calculated using the formula

(1.3)

Example 9. How many ways are there to arrange 10 books on a shelf?

Solution. The total number of arrangement methods is defined as the number of permutations (1.3) of 10 elements and is equal to R 10 = 10! = 3628 800.

2. Selection scheme with returns

If when choosing k elements from n, the elements are returned back and ordered, then they say that this placements with repetitions .

Number of placements with repetitions:

Example 11. The hotel has 10 rooms, each of which can accommodate four people. How many accommodation options are there for four guests arriving?

Solution. Each subsequent guest out of 4 can be placed in any of the 10 rooms, since an idealized experience is being considered, so the total number of placements, according to the placement formula with repetitions (1.5), is equal to

.

If when choosing k elements from n elements are returned back without further ordering, then this is said to be combinations with repetitions. Number of combinations with repetitions from n elements by k defined:

Example 12. The store sells 10 types of cakes. Another buyer knocked out a check for three cakes. Assuming that any set of goods is equally possible, determine the number of possible orders.

Solution. The number of equally possible orders according to formula (1.6) is equal to

.

Combinatorics is a branch of mathematics. The basic concepts and formulas of combinatorics as a science are applied in all spheres of life.

It is not surprising that it is included in the 11th grade program, as well as in the entrance examinations in many universities in the Russian Federation. Its foundations lie in the applied arts of many spheres of human activity.

Its history goes back more than 6 centuries. The first combinatorial problems appeared in the works of philosophers and mathematicians of the Middle Ages.

Representatives of that scientific world tried to find methods for solving such problems, their basic rules and concepts, and establish unique formulas and equations for those who had not yet encountered them. Such information in our time is called information “for dummies.”

Let's try to understand the aspects of this field of science: what are the elements, properties, rules, methods and its main application in our lives? Of course, it is impossible to cover the entire area in one article. Therefore, all the most basic things will be presented below.

What is combinatorics in mathematics

The essence of this term is given by books of past years: this branch of mathematics dealing with operations on many elements.

On the Internet there are textbooks on computer science and mathematics for children and schoolchildren, collections of materials and problems for beginners, where “entertaining” combinatorics is explained in an accessible way. We need to firmly figure out how to solve such problems.

In elementary grades, problems on this topic are solved in additional clubs, and in schools with in-depth study of mathematics - in main lessons. In addition, combinatorics problems are included in olympiads at all levels.

Basic Concepts

There are several of them:

1. Element– any object or phenomenon included in the desired set.
2. Combination– subsets located in an arbitrary order in the original set.
3. Rearrangement– elements in a set are in a strictly defined order.
4. Accommodation– ordered subsets in the original set.

Product rule

It is one of the basic rules when solving such problems and sounds like this:

When selecting element A fromnmethods and selection of element B frommIn some ways it is true that it is possible to choose a pair A and B at the same timen* mways.

Let's look at specific examples.

Task No. 1.

The box contains 2 balls and 6 jump ropes. How many ways are there to get 1 ball and 1 jump rope?

The answer is simple: 2 * 6 = 12.

Task No. 2.

There are 1 cube, 2 balls, 3 flowers and 4 candies. In how many ways can you draw a cube, a ball, a flower and a candy?

The solution is similar: 1 * 2 * 3 * 4 = 24.

Moreover, the left side can be written much simpler: 4!

! in this case it is not a punctuation mark, but a factorial. Using it, you can calculate more complex options and solve difficult problems (there are different formulas, but more on that later).

Task No. 3.

How many two-digit numbers can be made from 2 digits?

Answer: 2! = 2.

Task No. 4.

How many ten-digit numbers can be made from 10 digits?

Sum Rule

This is also a basic rule of combinatorics.

If A can be chosenntimes, and B -mtimes, then A or B can be chosen (n+ m) once.

Task No. 5.

The box contains 5 red, 3 yellow, 7 green, 9 black pencils. How many ways are there to pull out any 1 pencil?

Answer: 5 + 3 + 7 + 9 = 24.

Combinations with and without repetitions

This term refers to combinations in any order from a set of n by m elements.

The number of combinations is equal to the number of such combinations.

Task No. 6.

The box contains 4 different fruits. In how many ways can you get 2 different fruits at the same time?

The solution is simple:

Where is 4! – a combination of 4 elements.

With repetitions a little more complicated, combinations are calculated using the following formula:

Task No. 7.

Let's take the same case, but on the condition that one fruit is returned to the box.

In this case:

Placements with and without repetitions

This definition means a set of m elements from a set of n elements.

Task No. 8.

From 3 digits, you need to choose 2 to get different two-digit numbers. How many options?

The answer is simple:

But what about with repetitions? Here, each element can be placed several times! In this case, the general formula will look like this:

Task No. 9.

From 12 letters of the Latin alphabet and 10 digits of the natural series, you need to find all the options for composing the automobile region code.

Permutations with and without repetitions

This term refers to all possible combinations of an n element set.

Task No. 10.

How many possible 5-digit numbers can be made from 5 digits? What about six digits from 6 digits? Seven digits out of 7 digits?

The solutions, according to the above formula, are as follows:

But what about with repetitions? If in such a set there are elements of equal importance, then there will be fewer permutations!

Task No. 11.

The box contains 3 identical pencils and one pen. How many permutations can you make?

The answer is simple: 4! / (3! * 1!) = 4.

Combinatorial problems with solutions

Examples of all possible types of problems with solutions were given above. Here we will try to deal with more complex cases encountered in our lives.

Conclusion

It is worth studying this science, since in the age of rapid modernization of technology, specialists will be required who can provide various solutions to certain practical problems.

It should be noted that combinatorics is an independent branch of higher mathematics (and not part of terver) and weighty textbooks have been written on this discipline, the content of which, at times, is no easier than abstract algebra. However, a small portion of theoretical knowledge will be enough for us, and in this article I will try to analyze in an accessible form the basics of the topic with typical combinatorial problems. And many of you will help me ;-)

What are we going to do? In a narrow sense, combinatorics is the calculation of various combinations that can be made from a certain set discrete objects. Objects are understood as any isolated objects or living beings - people, animals, mushrooms, plants, insects, etc. At the same time, combinatorics does not care at all that the set consists of a plate of semolina porridge, a soldering iron and a swamp frog. It is fundamentally important that these objects can be enumerated - there are three of them (discreteness) and the important thing is that none of them are identical.

We've dealt with a lot, now about combinations. The most common types of combinations are permutations of objects, their selection from a set (combination) and distribution (placement). Let's see how this happens right now:

Permutations, combinations and placements without repetition

Don't be afraid of obscure terms, especially since some of them are really not very good. Let's start with the tail of the title - what does “ no repetitions"? This means that in this section we will consider sets that consist of various objects. For example, ... no, I won’t offer porridge with a soldering iron and a frog, it’s better to have something tastier =) Imagine that an apple, a pear and a banana have materialized on the table in front of you (if you have them, the situation can be simulated in reality). We lay out the fruits from left to right in the following order:

apple / pear / banana

Question one: In how many ways can they be rearranged?

One combination has already been written above and there are no problems with the rest:

apple / banana / pear
pear / apple / banana
pear / banana / apple
banana / apple / pear
banana / pear / apple

Total: 6 combinations or 6 permutations.

Okay, it wasn’t difficult to list all the possible cases, but what if there are more objects? With just four different fruits, the number of combinations will increase significantly!

Please open the reference material (it’s convenient to print the manual) and in point No. 2, find the formula for the number of permutations.

No hassle - 3 objects can be rearranged in different ways.

Question two: In how many ways can you choose a) one fruit, b) two fruits, c) three fruits, d) at least one fruit?

Why choose? So we worked up an appetite in the previous point - in order to eat! =)

a) One fruit can be chosen, obviously, in three ways - take either an apple, a pear, or a banana. The formal calculation is carried out according to formula for the number of combinations:

The entry in this case should be understood as follows: “in how many ways can you choose 1 fruit out of three?”

b) Let us list all possible combinations of two fruits:

apple and pear;
apple and banana;
pear and banana.

The number of combinations can be easily checked using the same formula:

The entry is understood in a similar way: “in how many ways can you choose 2 fruits out of three?”

c) And finally, there is only one way to choose three fruits:

By the way, the formula for the number of combinations remains meaningful for an empty sample:
In this way, you can choose not a single fruit - in fact, take nothing and that’s it.

d) In how many ways can you take at least one fruit? The condition “at least one” implies that we are satisfied with 1 fruit (any) or any 2 fruits or all 3 fruits:
using these methods you can select at least one fruit.

Readers who have carefully studied the introductory lesson on probability theory, we’ve already guessed something. But more about the meaning of the plus sign later.

To answer the next question I need two volunteers... ...Well, since no one wants to, then I’ll call you to the board =)

Question three: In how many ways can you distribute one fruit each to Dasha and Natasha?

In order to distribute two fruits, you first need to select them. According to paragraph “be” of the previous question, this can be done in ways, I’ll rewrite them:

apple and pear;
apple and banana;
pear and banana.

But now there will be twice as many combinations. Consider, for example, the first pair of fruits:
You can treat Dasha with an apple, and Natasha with a pear;
or vice versa - Dasha will get the pear, and Natasha will get the apple.

And such a permutation is possible for each pair of fruits.

Consider the same student group that went to the dance. In how many ways can a boy and a girl be paired?

In ways you can select 1 young man;
ways you can choose 1 girl.

Thus, one young man And You can choose one girl: ways.

When 1 object is selected from each set, the following principle for counting combinations is valid: “ every an object from one set can form a pair with every object of another set."

That is, Oleg can invite any of the 13 girls to dance, Evgeny can also invite any of the thirteen, and the rest of the young people have a similar choice. Total: possible pairs.

It should be noted that in this example, the “history” of the formation of the pair does not matter; however, if we take into account the initiative, the number of combinations must be doubled, since each of the 13 girls can also invite any boy to dance. It all depends on the conditions of a particular task!

A similar principle is valid for more complex combinations, for example: in how many ways can you choose two young men? And two girls to participate in a KVN skit?

Union AND clearly hints that the combinations need to be multiplied:

Possible groups of artists.

In other words, each a pair of boys (45 unique pairs) can perform with any a pair of girls (78 unique pairs). And if we consider the distribution of roles between the participants, there will be even more combinations. ...I really want to, but I’ll still refrain from continuing so as not to instill in you an aversion to student life =).

The rule for multiplying combinations also applies to a larger number of multipliers:

Problem 8

How many three-digit numbers are there that are divisible by 5?

Solution: for clarity, let’s denote this number with three asterisks: ***

IN hundreds place You can write any of the numbers (1, 2, 3, 4, 5, 6, 7, 8 or 9). Zero is not suitable, since in this case the number ceases to be three-digit.

But in tens place(“in the middle”) you can choose any of 10 digits: .

According to the condition, the number must be divisible by 5. A number is divisible by 5 if it ends in 5 or 0. Thus, we are satisfied with 2 digits in the least significant digit.

In total, there is: three-digit numbers that are divisible by 5.

In this case, the work is deciphered as follows: “9 ways you can choose a number in hundreds place And 10 ways to choose a number in tens place And 2 ways in units digit»

Or even simpler: “ each from 9 digits to hundreds place combines with each of 10 digits tens place and with each from two digits to units digit».

Answer: 180

And now…

Yes, I almost forgot about the promised commentary on problem No. 5, in which Bor, Dima and Volodya can be dealt one card each in different ways. Multiplication here has the same meaning: ways to remove 3 cards from the deck AND in each sample rearrange them in ways.

And now a problem to solve on your own... now I’ll come up with something more interesting... let it be about the same Russian version of blackjack:

Problem 9

How many winning combinations of 2 cards are there when playing "point"?

For those who don’t know: the winning combination is 10 + ACE (11 points) = 21 points and, let’s consider the winning combination of two aces.

(the order of the cards in any pair does not matter)

A short solution and answer at the end of the lesson.

By the way, do not consider the example primitive. Blackjack is almost the only game for which there is a mathematically based algorithm that allows you to beat the casino. Those interested can easily find a wealth of information about optimal strategy and tactics. True, such masters quite quickly end up on the black list of all establishments =)

It's time to consolidate the material covered with a couple of solid tasks:

Problem 10

Vasya has 4 cats at home.

a) in how many ways can cats be seated in the corners of the room?
b) in how many ways can you let cats go for a walk?
c) in how many ways can Vasya pick up two cats (one on his left, the other on his right)?

Let's decide: firstly, you should again pay attention to the fact that the problem deals with different objects (even if the cats are identical twins). This is a very important condition!

a) Silence of cats. Subject to this execution all the cats at once
+ their location is important, so there are permutations here:
using these methods you can place cats in the corners of the room.

I repeat that when permuting, only the number of different objects and their relative positions matter. Depending on Vasya’s mood, she can seat the animals in a semicircle on the sofa, in a row on the windowsill, etc. – in all cases there will be 24 permutations. For convenience, those interested can imagine that cats are multi-colored (for example, white, black, red and tabby) and list all possible combinations.

b) In how many ways can you let cats go for a walk?

It is assumed that cats go for walks only through the door, and the question implies indifference regarding the number of animals - 1, 2, 3 or all 4 cats can go for a walk.

We count all possible combinations:

In ways you can let one cat (any of the four) go for a walk;
ways you can let two cats go for a walk (list the options yourself);
in ways you can let three cats go for a walk (one of the four sits at home);
This way you can release all the cats.

You probably guessed that the resulting values ​​should be summed up:
ways you can let cats go for walks.

For enthusiasts, I offer a complicated version of the problem - when any cat in any sample can randomly go outside, both through the door and through the window on the 10th floor. There will be a noticeable increase in combinations!

c) In how many ways can Vasya pick up two cats?

The situation involves not only choosing 2 animals, but also placing them in each hand:
In these ways you can pick up 2 cats.

Second solution: you can choose two cats using methods And ways to plant every a couple on hand:

Answer: a) 24, b) 15, c) 12

Well, to clear your conscience, something more specific about multiplying combinations... Let Vasya have 5 additional cats =) In how many ways can you let 2 cats go for a walk? And 1 cat?

That is, with each a couple of cats can be released every cat.

Another button accordion for independent solution:

Problem 11

Three passengers boarded the elevator of a 12-story building. Everyone, regardless of the others, can exit on any (starting from the 2nd) floor with equal probability. In how many ways:

1) passengers can get off on the same floor (exit order does not matter);
2) two people can get off on one floor, and a third on the other;
3) people can exit on different floors;
4) can passengers exit the elevator?

And here they often ask again, I clarify: if 2 or 3 people exit on the same floor, then the order of exit does not matter. THINK, use formulas and rules for adding/multiplying combinations. In case of difficulties, it is useful for passengers to give names and speculate in what combinations they can exit the elevator. There is no need to be upset if something doesn’t work out, for example, point No. 2 is quite insidious, however, one of the readers found a simple solution, and I once again express my gratitude for your letters!

Full solution with detailed comments at the end of the lesson.

The final paragraph is devoted to combinations that also occur quite often - according to my subjective assessment, in approximately 20-30% of combinatorial problems:

Permutations, combinations and placements with repetitions

The listed types of combinations are outlined in paragraph No. 5 of the reference material Basic formulas of combinatorics, however, some of them may not be very clear upon first reading. In this case, it is first advisable to familiarize yourself with practical examples, and only then comprehend the general formulation. Go:

Permutations with repetitions

In permutations with repetitions, as in “ordinary” permutations, all the many objects at once, but there is one thing: in this set one or more elements (objects) are repeated. Meet the next standard:

Problem 12

How many different letter combinations can be obtained by rearranging cards with the following letters: K, O, L, O, K, O, L, b, Ch, I, K?

Solution: in the event that all the letters were different, then a trivial formula would have to be applied, but it is completely clear that for the proposed set of cards some manipulations will work “idlely”, for example, if you swap any two cards with the letters “K” " in any word, you get the same word. Moreover, physically the cards can be very different: one can be round with the letter “K” printed on it, the other can be square with the letter “K” drawn on it. But according to the meaning of the task, even such cards are considered the same, since the condition asks about letter combinations.

Everything is extremely simple - only 11 cards, including the letter:

K – repeated 3 times;
O – repeated 3 times;
L – repeated 2 times;
b – repeated 1 time;
H – repeated 1 time;
And - repeated 1 time.

Check: 3 + 3 + 2 + 1 + 1 + 1 = 11, which is what needed to be checked.

According to the formula number of permutations with repetitions:
different letter combinations can be obtained. More than half a million!

To quickly calculate a large factorial value, it is convenient to use the standard Excel function: enter into any cell =FACT(11) and press Enter.

In practice, it is quite acceptable not to write the general formula and, in addition, to omit the unit factorials:

But preliminary comments about repeated letters are required!

Answer: 554400

Another typical example of permutations with repetition occurs in the chess piece placement problem, which can be found in the warehouse ready-made solutions in the corresponding pdf. And for an independent solution, I came up with a less formulaic task:

Problem 13

Alexey goes in for sports, and 4 days a week - athletics, 2 days - strength exercises and 1 day resting. In how many ways can he create a weekly schedule for himself?

The formula doesn't work here because it takes into account coincidental swaps (for example, swapping Wednesday's strength exercises with Thursday's strength exercises). And again - in fact, the same 2 strength training sessions can be very different from each other, but in the context of the task (from the point of view of the schedule) they are considered the same elements.

Two line solution and answer at the end of the lesson.

Combinations with repetitions

A characteristic feature of this type of combination is that the sample is drawn from several groups, each of which consists of identical objects.

Everyone has worked hard today, so it's time to refresh yourself:

Problem 14

The student canteen sells sausages in dough, cheesecakes and donuts. In how many ways can you buy five pies?

Solution: immediately pay attention to the typical criterion for combinations with repetitions - according to the condition, it is not a set of objects as such that is offered for choice, but different kinds objects; it is assumed that there are at least five hot dogs, 5 cheesecakes and 5 donuts on sale. The pies in each group are, of course, different - because absolutely identical donuts can only be simulated on a computer =) However, the physical characteristics of the pies are not significant for the purpose of the problem, and the hot dogs / cheesecakes / donuts in their groups are considered the same.

What might be in the sample? First of all, it should be noted that there will definitely be identical pies in the sample (since we are choosing 5 pieces, and there are 3 types to choose from). There are options here for every taste: 5 hot dogs, 5 cheesecakes, 5 donuts, 3 hot dogs + 2 cheesecakes, 1 hot dog + 2 cheesecakes + 2 donuts, etc.

As with “regular” combinations, the order of selection and placement of pies in the selection does not matter - you just chose 5 pieces and that’s it.

We use the formula number of combinations with repetitions:
You can purchase 5 pies using this method.

Bon appetit!

Answer: 21

What conclusion can be drawn from many combinatorial problems?

Sometimes the hardest thing is to understand the condition.

A similar example for an independent solution:

Problem 15

The wallet contains a fairly large number of 1-, 2-, 5- and 10-ruble coins. In how many ways can three coins be removed from a wallet?

For self-control purposes, answer a couple of simple questions:

1) Can all the coins in the sample be different?
2) Name the “cheapest” and most “expensive” combination of coins.

Solution and answers at the end of the lesson.

From my personal experience, I can say that combinations with repetitions are the rarest guest in practice, which cannot be said about the following type of combinations:

Placements with repetitions

From a set consisting of elements, elements are selected, and the order of the elements in each selection is important. And everything would be fine, but a rather unexpected joke is that we can select any object of the original set as many times as we like. Figuratively speaking, “the multitude will not decrease.”

When does this happen? A typical example is a combination lock with several disks, but due to technological developments, it is more relevant to consider its digital descendant:

Problem 16

How many four-digit PIN codes are there?

Solution: in fact, to resolve the problem, knowledge of the rules of combinatorics is enough: in ways you can select the first digit of the PIN code And ways - the second digit of the PIN code And in as many ways - third And the same number - the fourth. Thus, according to the rule of multiplying combinations, a four-digit pin code can be composed in: ways.

And now using the formula. According to the condition, we are offered a set of numbers, from which the numbers are selected and arranged in a certain order, while the numbers in the sample may be repeated (i.e. any digit of the original set can be used an arbitrary number of times). According to the formula for the number of placements with repetitions:

Answer: 10000

What comes to mind here... ...if the ATM “eats” the card after the third unsuccessful attempt to enter the PIN code, then the chances of picking it up at random are very slim.

And who said that combinatorics has no practical meaning? A cognitive task for all readers of the site:

Problem 17

According to the state standard, a car license plate consists of 3 numbers and 3 letters. In this case, a number with three zeros is unacceptable, and letters are selected from the set A, B, E, K, M, N, O, P, S, T, U, X (only those Cyrillic letters are used whose spelling coincides with Latin letters).

How many different license plates can be created for a region?

Not that many of them, by the way. In large regions there is not enough such quantity, and therefore for them there are several codes for the inscription RUS.

The solution and answer are at the end of the lesson. Don’t forget to use the rules of combinatorics ;-) ...I wanted to show off what was exclusive, but it turned out not to be exclusive =) I looked at Wikipedia - there are calculations there, although without comments. Although for educational purposes, probably, few people solved it.

Our exciting lesson has come to an end, and finally I want to say that you have not wasted your time - for the reason that combinatorics formulas find another vital practical application: they are found in various problems in probability theory,
and in problems involving the classical determination of probability– especially often =)

Thank you all for your active participation and see you soon!

Solutions and Answers:

Task 2: Solution: find the number of all possible permutations of 4 cards:

When a card with a zero is placed in the 1st place, the number becomes three-digit, so these combinations should be excluded. Let zero be in the 1st place, then the remaining 3 digits in the lower digits can be rearranged in different ways.

Note : because Since there are only a few cards, it’s easy to list all the options here:
0579
0597
0759
0795
0957
0975

Thus, from the proposed set we can make:
24 – 6 = 18 four-digit numbers
Answer : 18

Task 4: Solution: in ways you can choose 3 cards out of 36. And
2) The “cheapest” set contains 3 ruble coins, and the most “expensive” – 3 ten-ruble coins.

Problem 17: Solution: using these methods, you can create a digital combination of a car number, while one of them (000) should be excluded: .
using these methods you can create a letter combination of a license plate number.
According to the rule of multiplying combinations, the total can be made:
license plates
(each digital combination is combined with each letter combination).
Answer : 1726272