Combinatorics is a branch of mathematics that studies questions about how many different combinations, subject to certain conditions, can be made from given objects. The basics of combinatorics are very important for estimating the probabilities of random events, because they allow us to calculate the fundamentally possible number various options developments of events.
Basic formula of combinatorics
Let there be k groups of elements, and i-th group consists of n i elements. Let's select one element from each group. Then total number The N ways in which such a choice can be made is determined by the relation N=n 1 *n 2 *n 3 *...*n k .
Example 1. Let us explain this rule with a simple example. Let there be two groups of elements, and the first group consists of n 1 elements, and the second - of n 2 elements. How many different pairs of elements can be made from these two groups, such that the pair contains one element from each group? Let's say we took the first element from the first group and, without changing it, went through all possible pairs, changing only the elements from the second group. There can be n 2 such pairs for this element. Then we take the second element from the first group and also make all possible pairs for it. There will also be n 2 such pairs. Since there are only n 1 elements in the first group, the total possible options will be n 1 *n 2 .
Example 2. How many three-digit even numbers can be made from the digits 0, 1, 2, 3, 4, 5, 6, if the digits can be repeated?
Solution: n 1 =6 (because you can take any number from 1, 2, 3, 4, 5, 6 as the first digit), n 2 =7 (because you can take any number from 0 as the second digit , 1, 2, 3, 4, 5, 6), n 3 =4 (since any number from 0, 2, 4, 6 can be taken as the third digit).
So, N=n 1 *n 2 *n 3 =6*7*4=168.
In the case when all groups consist of the same number elements, i.e. n 1 =n 2 =...n k =n we can assume that each selection is made from the same group, and the element after selection is returned to the group. Then the number of all selection methods is n k . This method of selection in combinatorics is called samples with return.
Example 3. How many four-digit numbers can be made from the digits 1, 5, 6, 7, 8?
Solution. For each digit of a four-digit number there are five possibilities, which means N=5*5*5*5=5 4 =625.
Consider a set consisting of n elements. In combinatorics this set is called general population.
Number of placements of n elements by m
Definition 1. Accommodation from n elements by m in combinatorics any ordered set from m various elements selected from the population in n elements.
Example 4. Different arrangements of three elements (1, 2, 3) by two will be the sets (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2 ). Placements may differ from each other both in elements and in their order.
The number of placements in combinatorics is denoted by A n m and is calculated by the formula:
Comment: n!=1*2*3*...*n (read: “en factorial”), in addition, it is assumed that 0!=1.
Example 5. How many two-digit numbers are there in which the tens digit and the units digit are different and odd?
Solution: because If there are five odd digits, namely 1, 3, 5, 7, 9, then this task comes down to selecting and placing two of the five different digits in two different positions, i.e. the indicated numbers will be:
Definition 2. Combination from n elements by m in combinatorics any unordered set from m various elements selected from the population in n elements.
Example 6. For the set (1, 2, 3), the combinations are (1, 2), (1, 3), (2, 3).
Number of combinations of n elements, m each
The number of combinations is denoted by C n m and is calculated by the formula:
Example 7. In how many ways can a reader choose two books out of six available?
Solution: The number of methods is equal to the number of combinations of six books of two, i.e. equals:
Permutations of n elements
Definition 3. Permutation from n elements are called any ordered set these elements.
Example 7a. All possible permutations of a set consisting of three elements (1, 2, 3) are: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), ( 3, 2, 1), (3, 1, 2).
The number of different permutations of n elements is denoted by P n and is calculated by the formula P n =n!.
Example 8. In how many ways can seven books by different authors be arranged in one row on a shelf?
Solution: This problem is about the number of permutations of seven different books. There are P 7 =7!=1*2*3*4*5*6*7=5040 ways to arrange the books.
Discussion. We see that the number of possible combinations can be calculated according to different rules (permutations, combinations, placements) and the result will be different, because The calculation principle and the formulas themselves are different. Looking carefully at the definitions, you will notice that the result depends on several factors simultaneously.
Firstly, from how many elements we can combine their sets (how large is the totality of elements).
Secondly, the result depends on the size of the sets of elements we need.
Finally, it is important to know whether the order of the elements in the set is significant to us. Let us explain the last factor using the following example.
Example 9. On parent meeting 20 people are present. How many different options are there for the composition of the parent committee if it must include 5 people?
Solution: In this example, we are not interested in the order of names on the committee list. If, as a result, the same people turn out to be part of it, then in meaning for us this is the same option. Therefore, we can use the formula to calculate the number combinations of 20 elements 5 each.
Things will be different if each committee member is initially responsible for a specific area of work. Then, with the same list composition of the committee, there are possibly 5 within it! options permutations that matter. The number of different (both in composition and area of responsibility) options is determined in this case by the number placements of 20 elements 5 each.
Self-test tasks
1. How many three-digit even numbers can be made from the digits 0, 1, 2, 3, 4, 5, 6, if the digits can be repeated?
2. How many five-digit numbers are there that are read the same from left to right and from right to left?
3. There are ten subjects in the class and five lessons a day. In how many ways can you create a schedule for one day?
4. In how many ways can 4 delegates be selected for a conference if there are 20 people in the group?
5. In how many ways can eight different letters be placed in eight different envelopes, if only one letter is placed in each envelope?
6. A commission consisting of two mathematicians and six economists should be composed of three mathematicians and ten economists. In how many ways can this be done?
To use preview presentations create yourself an account ( account) Google and log in: https://accounts.google.com
Slide captions:
Elements of combinatorics Nikandrova I.A. MBOU "Lyceum 10" Velikie Luki
Examples of combinatorial problems Problems in which one has to make various combinations from a finite number of elements and count the number of combinations are called combinatorial. The branch of mathematics in which such problems are considered is called combinatorics. The word “combinatorics” comes from the Latin combinare - “to connect, combine”
Example 1 From a group of tennis players, which includes four people - Antonov, Grigoriev, Sergeev and Fedorov, the coach selects a couple to participate in competitions. How many options are there for choosing such a pair? AG, AS, AF GS, GF SF This means that there are six options in total. The reasoning method we used is called brute force possible options
Example 2 How many three-digit numbers can be made from the numbers 1, 3, 5, 7, using each of them no more than once in writing the number? To answer the question of the problem, we write down all such numbers. We will write the results obtained in four lines, each of which contains six numbers: 135 137 153 157 173 175 315 317 351 357 371 375 513 517 531 537 571 573 713 715 731 735 751 753
Method two The enumeration of options is illustrated in the diagram. Such a diagram is called a tree of possible options
Method Three The first digit can be selected in four ways. Since after selecting the first digit there will be three left, the second digit can be selected in three ways. Finally, the third digit can be selected in two ways. Consequently, the total number of required numbers is equal to the product 4*3*2, i.e. 24 The combinatorial multiplication rule was used: Let there be n elements and you need to select k elements from them one after another. If the first element can be chosen in n1 ways, after which the second element can be chosen in n2 ways from the remaining ones, then the third element can be chosen in n3 ways from the remaining ones, etc., then the number of ways in which all k elements can be chosen is equal to the product n1 · p2 · p2 · … · pk .
Example 3 There are two roads from city A to city B, three roads from city B to city C, and two roads from city C to the pier. Tourists want to travel from city A through B and C to the pier. In how many ways can they choose a route? Solution: 2*3*2=12
Problems 1. The cafe offers two first courses: borscht, rassolnik, and four second courses: goulash, cutlets, sausages, dumplings. List all two-course meals that a diner may order. Construct a tree of possible options 2. The stadium has four entrances: A, B, C, D. Please indicate all possible ways, in which a visitor can enter through one entrance and exit through another. How many such ways are there? Answer: 12 ways 3. Using the numbers 0,2,4,6, make up all possible three-digit numbers in which the numbers are not repeated.
Problems 4. 9 people participate in a chess tournament. Each of them played one game with each other. How many games were played in total? Answer: 36 games 5. During a meeting, 8 people shook hands. How many handshakes were done? Answer: 28 handshakes 6. 9th grade students decided to exchange photographs. How many photos will this require if there are 24 students in the class? Answer:552 photos
Problems 7. The cafe has three first courses, five second courses and two third courses. In how many ways can a cafe visitor choose a lunch consisting of first, second and third courses? Answer: 30 ways 8. Peter decided to go to the New Year's carnival dressed as a musketeer. At the rental shop, he was offered a choice of items of different styles and colors: five types of trousers, six camisoles, three hats, two pairs of boots. How many different carnival costumes can be made from these items? Answer: 180 suits
Permutations The simplest combinations that can be made from elements of a finite set are permutations. The number of permutations of n elements is denoted by the symbol P n (read “P of n”) For the product of the first n natural numbers use a special notation: n! (read n factorial) 2!=2; 5!=120; 1!=1
Examples of problems Thus, the number of possible permutations of n elements is calculated by the formula: P n = n! Example 1. In how many ways can the 8 participants in the final race be placed on eight treadmills? P 8 =8!=40320 Example 2. How many different four-digit numbers, in which the digits are not repeated, can be made from the digits 0, 2, 4, 6? From the numbers 0,2,4,6 you can get P 4 permutations. From this number we must exclude those permutations that start with 0. We get: P 4 -P 3 =4!-3!=18
Example 3. There are 9 different books, four of them of which - textbooks. In how many ways can these books be arranged on a shelf so that all the textbooks are next to each other? First, we will consider textbooks as one book. Then you need to place not 9, but 6 books on the shelf. This can be done in 6 ways. In each of the resulting combinations, it is possible to perform P 4 permutations of textbooks. This means that the required number of ways to arrange books on a shelf is equal to the product P 6 * P 4 . We get: P 6 *P 4 =6!*4!=720*24=17280
Problems 1. In how many ways can 4 people fit on a four-seater bench? Answer:24 2. The courier must deliver packages to 7 different institutions. How many routes can he choose? Answer: 5040 3. How many six-digit numbers (without repeating numbers) can be made from the numbers: a) 1,2,5,6,7,8; b)0,2,5,6,7,8? Answer: a) 720; b) 600 4. The schedule for Monday has six lessons: algebra, geometry, biology, history, physical education, chemistry. In how many ways can the lesson schedule for this day be made so that two mathematics lessons are next to each other? Answer: 240
Problems 5. Is the number 14 divisible? On: A)168; b)136;c)147;d)132? 6. 7. Answer to 6) :15; 1/90; 1722; 40
Test work Option 1 Option 2 1. Combinatorial problems 2. Methods for solving combinatorial problems 3. Calculate 1. Permutations, formula 2. Combinatorics 3. Calculate
Placements Let there be 4 balls and 3 empty cells. Three balls from this set of balls can be placed in the empty cells in different ways. Choosing different ways the first, second and third balls, we will get different triplets of balls. Each ordered triple that can be composed of four elements is called an arrangement of four elements by three. An arrangement of n elements by k (k
Examples 1. Second grade students study 8 subjects. In how many ways can you create a schedule for one day so that it contains 4 various subjects? In this example we're talking about about placements of 8 elements of 4. We have: 2. How many three-digit numbers (without repeating the digits in the number notation) can be made from the numbers 0,1,2,3,4,5,6? Among these numbers there is the number 0, which cannot begin a three-digit number. That's why:
Problems 1. In how many ways can a family of three people fit in a four-seater compartment if there are no other passengers in the compartment? Answer: 24 2. Of the 30 participants in the meeting, a chairman and a secretary must be selected. In how many ways can this be done? Answer: 870 3. In how many ways can the organizers of the competition determine which of the 15 participants will perform first, second and third? Answer: 2730 4. There are 6 free places for photos on the album page. In how many ways can you put in the empty spaces: a) 2 photographs; b) 4 photographs; c) 6 photos? Answer: 30;360;720
Combinations A combination of n elements by k is any set made up of given n elements. Unlike placements in combinations, it does not matter in what order the elements are specified. Two combinations of elements by k differ from each other by at least one element. Denote Read “C” from n to k" Formula for the number of combinations of n elements to k, where k
Examples 1. Out of 15 members of a tourist group, three people on duty must be selected. In how many ways can this choice be made? Each choice differs from the other by at least one attendant. This means that here we are talking about combinations of 15 elements of 3. We have: 2. From a fruit bowl containing 9 apples and 6 pears, you need to choose 3 apples and 2 pears. In how many ways can such a choice be made? We have:
Tasks 1. There are 7 people in the class successfully doing mathematics. In how many ways can you choose two of them to participate in Mathematical Olympiad? Answer:21 2. Students were given a list of 10 books that are recommended to be read during the holidays. In how many ways can a student choose 6 books from them? Answer: 210 3. There are 16 boys and 12 girls in the class. Four boys and three girls are required to clean the area. In how many ways can this be done? Answer: 400400 4. In the library, the reader was offered a choice of 10 books and 4 magazines from new arrivals. In how many ways can he choose 3 books and 2 magazines from them? Answer: 720
Independent work Option 1 1. In how many ways can 9 competition participants perform in order of priority in the finals? 2. Is the number 40 divisible? n a: a) 410; b) 500; c) 780? 3. Using the numbers 0,3,7,8, make up all possible double figures, in which the numbers are not repeated 4. There are 10 deputies in the City Duma under 30 years of age. In how many ways can three of them be selected to serve on the committee? youth policy? Option 2 1. The courier must deliver pizza to six addresses. How many routes can he choose? 2. Is the number 50 divisible? n a: a) 400; b) 98; c) 510? 3. Using even numbers 0,2,4,6,8, make up all possible three-digit numbers in which the numbers are not repeated 4. There are 9 students in the group who speak well foreign language. In how many ways can four of them be selected to work in practice with foreigners?
Answers Option 1 1. 9!=362880 2. a) no b) yes c) yes 3. 30 70 80 37 73 83 38 78 87 4. 120 Option 2 1. 6!=720 2. a) yes b) yes c) yes 3. 48 numbers 4. 126
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
:
Sign up for 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 next question I need two volunteers... ...Well, since no one wants, 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" previous question, there are ways to do this, 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 in this example the “history” of the pair’s formation 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 large quantity multipliers:
Problem 8
How many three-digit numbers are there that are divisible by 5?
Solution: for clarity, let’s denote given number three stars: ***
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 the task for independent decision... 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 cats are identical twins). This is 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.
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
Listed species combinations are outlined in paragraph No. 5 reference material Basic formulas of combinatorics , however, some of them may not be very clear upon first reading. In this case, it is advisable to first 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, 4 days a week - athletics, 2 days - strength exercises and rests for 1 day. 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 power training may be very different from each other, but in the context of the task (from a schedule point of view) they are considered the same elements.
Two line solution and answer at the end of the lesson.
Combinations with repetitions
Feature This type of combination consists in the fact 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 physical characteristics pies are not significant within the meaning of the problem, and hot dogs/cheesecakes/donuts are considered the same in their groups.
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
There is enough in the wallet a 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 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 form 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 want. Figuratively speaking, “the multitude will not decrease.”
When does this happen? Typical example is a combination lock with several disks, but due to the development of technology, 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... ...if the ATM “eats” the card after the third unsuccessful attempt entering a 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 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 in educational purposes, probably, few people decided.
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 use: they meet in various tasks By 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.
Answer
: 7140
Task 6: Solution: 
ways.
Another solution
: ways you can select two people from the group and and
2) The “cheapest” set contains 3 ruble coins, and the most “expensive” – 3 ten-ruble coins.
Problem 17: Solution: 
ways you can create a digital combination license plate number, and 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
