It should be noted that combinatorics is an independent section of higher mathematics (and not a part of terver) and weighty textbooks have been written in this discipline, the content of which, at times, is no easier than abstract algebra. However, a small share of theoretical knowledge will be enough for us, and in this article I will try to analyze the basics of the topic with typical combinatorial problems in an accessible form. 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, a soldering iron and a marsh frog. It is fundamentally important that these objects are enumerable - there are three of them. (discreteness) and it is essential that none of them are alike.
With a lot sorted out, now about the 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
Do not be afraid of obscure terms, especially since some of them are really not very successful. Let's start with the tail of the title - what does " without repetition"? 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, something tastier is better =) Imagine that an apple, a pear and a banana materialized on the table in front of you (if there are any, the situation can be simulated in real). 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.
Well, it was not difficult to list all possible cases here, but what if there are more items? Already with four different fruits, the number of combinations will increase significantly!
Please open reference material (Manual is easy to print) and in paragraph number 2, find the formula for the number of permutations.
No torment - 3 objects can be rearranged in 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 they worked up an appetite in the previous paragraph - in order to eat! =)
a) One fruit can be chosen, obviously, in three ways - take either an apple, or a pear, or a banana. The formal count is based on 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) We list all possible combinations of two fruits:
apple and pear;
apple and banana;
pear and banana.
The number of combinations is easy to check using the same formula:
The entry is understood similarly: “in how many ways can you choose 2 fruits out of three?”.
c) And finally, three fruits can be chosen in a unique way:
By the way, the formula for the number of combinations also makes sense 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 “at least one” condition implies that we are satisfied with 1 fruit (any) or any 2 fruits or all 3 fruits:
ways you can choose at least one fruit.
Readers who have carefully studied the introductory lesson on probability theory already figured something out. But about the meaning of the plus sign later.
To answer the next question, I need two volunteers ... ... Well, since no one wants, then I will call to the board =)
Question three: In how many ways can one fruit be distributed to Dasha and Natasha?
In order to distribute two fruits, you must first select them. According to paragraph "be" of the previous question, this can be done in ways, I will rewrite them again:
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 every 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?
Ways you can choose 1 young man;
ways you can choose 1 girl.
So one young man And one girl can be chosen: 
ways.
When 1 object is selected from each set, then the following principle of 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 - also any of the thirteen, and other young people have a similar choice. Total: possible pairs.
It should be noted that in this example, the "history" of pair formation does not matter; however, if initiative is taken into account, then 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 two young men be chosen And two girls to participate in a KVN skit?
Union AND hints unambiguously that the combinations must be multiplied:
Possible groups of artists.
In other words, each pair of boys (45 unique pairs) can compete with any a couple of girls (78 unique couples). And if we consider the distribution of roles between the participants, then there will be even more combinations. ... I really want to, but still I will refrain from continuing, so as not to instill in you an aversion to student life =).
The multiplication rule applies to more multipliers:
Task 8
How many three-digit numbers are there that are divisible by 5?
Solution: for clarity, we 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 good, because in this case the number ceases to be three-digit.
But in tens place(“in the middle”) you can choose any of the 10 digits: .
By condition, the number must be divisible by 5. The number is divisible by 5 if it ends in 5 or 0. Thus, in the least significant digit, we are satisfied with 2 digits.
Total, there is: three-digit numbers that are divisible by 5.
At the same time, the work is deciphered as follows: “9 ways you can choose a number in hundreds place And 10 ways to select a number in tens place And 2 ways in unit digit»
Or even simpler: each from 9 digits to hundreds place combined with each of 10 digits tens place and with each of two digits units digit».
Answer: 180
And now…
Yes, I almost forgot about the promised commentary to problem No. 5, in which Borya, Dima and Volodya can be dealt one card each in different ways. Multiplication here has the same meaning: in ways you can extract 3 cards from the deck AND in each sample to rearrange them ways.
And now the problem for an independent solution ... now I’ll come up with something more interesting, ... let it be about the same Russian version of blackjack:
Task 9
How many winning combinations of 2 cards are there in a "point" game?
For those who don't know: wins combination 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)
Short solution and answer at the end of the lesson.
By the way, it is not necessary to consider an example primitive. Blackjack is almost the only game for which there is a mathematically justified algorithm that allows you to beat the casino. Those who wish can easily find a lot of information about the optimal strategy and tactics. True, such masters quickly fall into the black list of all establishments =)
It's time to consolidate the material covered with a couple of solid tasks:
Task 10
Vasya has 4 cats at home.
a) In how many ways can the cats be seated in the corners of the room?
b) In how many ways can cats be allowed to roam?
c) in how many ways can Vasya pick up two cats (one on the left, the other on the right)?
We decide: first, it should again be noted that the problem is about different objects (even if the cats are identical twins). This is a very important condition!
a) Silence of cats. This execution is subject to all cats at once
+ their location is important, so there are permutations here:
ways you can seat cats in the corners of the room.
I repeat that when permuting, only the number of different objects and their relative position matters. Depending on his mood, Vasya can seat the animals in a semicircle on the sofa, in a row on the windowsill, etc. - there will be 24 permutations in all cases. For convenience, those who wish can imagine that the cats are multi-colored (for example, white, black, red and striped) and list all possible combinations.
b) In how many ways can cats be allowed to roam?
It is assumed that cats go for a walk only through the door, while the question implies indifference about the number of animals - 1, 2, 3 or all 4 cats can go for a walk.
We consider all possible combinations:
Ways you can let go for a walk one cat (any of the four); 
ways you can let two cats go for a walk (list the options yourself);
ways you can let three cats go for a walk (one of the four sits at home);
way you can release all the cats.
You probably guessed that the obtained values should be summed up:
ways to let cats go for a walk.
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 of the 10th floor. There will be more combinations!
c) In how many ways can Vasya pick up two cats?
The situation involves not only the choice of 2 animals, but also their placement on the hands:
ways you can pick up 2 cats.
The second solution: in ways you can choose two cats And ways to plant every a couple in hand: 
Answer: a) 24, b) 15, c) 12
Well, to clear my conscience, something more specific on the multiplication of combinations .... Let Vasya have 5 extra cats =) 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 an independent solution:
Task 11
3 passengers got into the elevator of a 12-storey building. Everyone, independently of the others, can exit on any (starting from the 2nd) floor with the same probability. In how many ways:
1) Passengers can get off at the same floor (exit order doesn't matter);
2) two people can get off on one floor and a third on another;
3) people can get off at different floors;
4) Can passengers exit the elevator?
And here they often ask again, I clarify: if 2 or 3 people go out on the same floor, then the order of exit does not matter. THINK, use formulas and rules for addition/multiplication combinations. In case of difficulty, it is useful for passengers to give names and reason in what combinations they can get out of the elevator. No need to be upset if something does not work out, for example, point number 2 is quite insidious, however, one of the readers found a simple solution, and once again I express my gratitude for your letters!
Complete solution with detailed comments at the end of the tutorial.
The final paragraph is devoted to combinations that also occur quite often - according to my subjective assessment, in about 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 on 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, the whole set of objects at once, but there is one thing: in this set, one or more elements (objects) are repeated. Meet the next standard:
Task 12
How many different letter combinations can be obtained by rearranging cards with the following letters: K, O, L, O, K, O, L, L, H, I, K?
Solution: in the event that all letters were different, then a trivial formula should be applied, however, it is quite clear that for the proposed set of cards, some manipulations will work "idle", so, for example, if you swap any two cards with the letters "K in any word, it will be the same word. Moreover, physically the cards can be very different: one can be round with a printed letter “K”, the other is square with a drawn letter “K”. But according to the meaning of the problem, even such cards considered the same, since the condition asks about letter combinations.
Everything is extremely simple - in total: 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 - repeats 1 time.
Check: 3 + 3 + 2 + 1 + 1 + 1 = 11, which is what we wanted to check.
According to the formula number of permutations with repetitions:
various letter combinations can be obtained. More than half a million!
For a quick calculation of a large factorial value, it is convenient to use the standard Excel function: we score in any cell =FACT(11) and click Enter.
In practice, it is quite acceptable not to write down 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 repetitions is found in the problem of arranging chess pieces, 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 template task:
Task 13
Alexey goes in for sports, and 4 days a week - athletics, 2 days - strength exercises and 1 day of rest. In how many ways can he schedule his weekly classes?
The formula doesn't work here because it takes into account overlapping permutations (for example, when strength exercises on Wednesday are swapped with strength exercises on Thursday). And again - in fact, the same 2 strength training sessions can be very different from each other, but in the context of the task (in terms 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 the same objects.
Everyone worked hard today, so it's time to refresh yourself:
Task 14
The student cafeteria sells sausages in dough, cheesecakes and donuts. In how many ways can five cakes be purchased?
Solution: immediately pay attention to the typical criterion for combinations with repetitions - according to the condition, not a set of objects as such, 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, of course, are different - because absolutely identical donuts can only be simulated on a computer =) However, the physical characteristics of the pies are not essential in the sense of the problem, and hot dogs / cheesecakes / donuts in their groups are considered the same.
What can be in the sample? First of all, it should be noted that there will definitely be identical pies in the sample (because we choose 5 pieces, and 3 types are offered to choose from). 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 sample does not matter - they just chose 5 pieces and that's it.
We use the formula 
number of combinations with repetitions: 
way you can buy 5 pies.
Bon appetit!
Answer: 21
What conclusion can be drawn from many combinatorial problems?
Sometimes, the most difficult thing is to understand the condition.
A similar example for a do-it-yourself solution:
Task 15
The wallet contains a fairly large number of 1-, 2-, 5- and 10-ruble coins. In how many ways can three coins be taken out of the wallet?
For self-control purposes, answer a couple of simple questions:
1) Can all coins in the sample be different?
2) Name the "cheapest" and the 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 sample is important. And everything would be fine, but a rather unexpected joke is that we can choose any object of the original set as many times as we like. Figuratively speaking, from "the multitude will not decrease."
When does it happen? A 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:
Task 16
How many 4-digit pin codes are there?
Solution: in fact, to solve the problem, it is enough to know the rules of combinatorics: you can choose the first digit of the pin code in ways And ways - the second digit of the pin code And in as many ways - a third And as many - the fourth. Thus, according to the rule of multiplication of combinations, a four-digit pin code can be composed: in ways.
And now with the formula. By condition, we are offered a set of numbers, from which numbers are selected and placed in a certain order, while the numbers in the sample can 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 illusory.
And who said that there is no practical sense in combinatorics? 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 not allowed, and the letters are selected from the set A, B, E, K, M, H, O, R, C, T, U, X (only those Cyrillic letters are used, the spelling of which matches the Latin letters).
How many different license plates can be composed for a region?
Not so, by the way, and a lot. In large regions, this number is not enough, and therefore for them there are several codes for the inscription RUS.
Solution and answer at the end of the lesson. Don't forget to use the rules of combinatorics ;-) …I wanted to brag about being exclusive, but it turned out to be not exclusive =) I looked at Wikipedia - there are calculations, however, without comments. Although for educational purposes, probably, few people solved it.
Our exciting lesson has come to an end, and in the end I want to say that you did not waste your time - for the reason that the combinatorics formulas find another vital practical application: they are found in various tasks on probability theory,
and in tasks on the classical definition 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 in 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 least significant digits can be rearranged in ways.
Note
: because there are few cards, it is easy to list all such options here:
0579
0597
0759
0795
0957
0975
Thus, from the proposed set, you can make:
24 - 6 = 18 four-digit numbers
Answer
: 18
Task 4: Solution: 3 cards can be selected from 36 ways. And
2) The “cheapest” set contains 3 ruble coins, and the most “expensive” set contains 3 ten-ruble coins.
Task 17: Solution: 
ways you can make a digital combination of a license plate, while one of them (000) should be excluded:.
ways you can make a letter combination of a car number.
According to the rule of multiplication of combinations, everything can be composed:
car numbers
(each digital combination combined with each letter combination).
Answer
: 1726272
Math lesson in 5th grade
«
Meet combinatorics"
Lesson topic:
The purpose of the lesson
:
formulate the initial skills of combinatorial problems by enumeration of possible options.Lesson objectives:
Educational:
Development of the ability to solve combinatorial problems by the method of complete enumeration of options;
Developing the ability to apply mathematical theory in specific situations;
Acquaintance of students with the elements of humanitarian knowledge related to mathematics.
Development of the ability to independently choose a method of decision and the ability to justify the choice;
Development of the ability to solve problems through only logical reasoning;
Development of the ability to make a choice of a rational way of coding;
Development of communicative and creative abilities of students.
- To cultivate a sense of responsibility for the quality and result of the work performed; To instill a conscious attitude to work;
- Form responsibility for the final result.
- interactive board; handout (colored 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 choosing and arranging given elements according to given rules
A common question in combinatorial problems is " How many ways …?” or
« How many options …?»
Teacher : Let's go back to the flags problem, solve it using the enumeration of possible options: (slide number 7) KBS KSB BSC BCS SBC SKBAnswer: 6 options. So, when solving this problem, we were looking for a way to enumerate possible options. InIn many cases, it turns out to be useful to construct a picture - a scheme for enumerating options. This, firstly, is visual, and secondly, it allows us to take everything into account, not to miss anything.Decision Flag
Variants of BSK, BKS, SBC, SKB, KBS, KSB.
Answer: 6 options.
The question, the answer to which everyone should know, which of the presented flag options is the state flag of the Russian Federation. (Slide No. 7)It turns out that not only the flag of Russia has these three colors. There are states whose flags have the same colors.
KBS - Luxembourg,
Netherlands.
France SKB
Teacher: Let us find a rule for solving such problems by logical reasoning.
Let's look at the example of colored stripes. Let's take a white strip - it can be rearranged 3 times, take a blue strip - it can be rearranged only 2 times, because one of the places is already occupied by white, take the red strip - it can be put only 1 time.
TOTAL: 3 x 2 x 1=6
The basic rule of the product :
Multiplication rule: if the first element in a combination can be chosen in a ways, then the second element in b ways, then the total number of combinations will be a x b . (slide number 8)
Physical education for the eyes. (slide number 9)
Exercise Shapes.
Draw with your eyes a square, a circle, a triangle, an oval, a rhombus clockwise, and then counterclockwise.
Practical part
Teacher: Now let's move on to the math problems. (hand out task cards)
One rather famous musketeer has in his wardrobe 3 elegant hats, 4 wonderful cloaks and 2 pairs of excellent boots. How many costume options can he make? (We choose one element from three sets, that is, we make up 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 choose a captain and his deputy. In how many ways can this be done? (There are 11 people in total, which means that the captain can be chosen in 11 ways, there are 10 players left, from which you can choose a deputy captain. So, a pair of captain and his deputy can be chosen in 11 10 \u003d 110 ways.)
How many different two-digit numbers can be formed using the numbers 1, 4, 7, if the repetition of numbers is allowed? (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. So, we make a pair of numbers 3 3 = 9 ways , i.e. 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? (A three-digit number: the first position - 5 options for numbers, the second position, taking into account the elimination of repetitions of numbers - 4 options, the 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, only 3 of the available 4 digits, 3 choices can be put in the first position, any of the numbers can be put in the second position, taking into account the repetition - 4 choices. Therefore, it turns out 3 4 \u003d 12 numbers; b) First position - 3 options, second position - 3 options, because repetition is excluded. We get 3 3 = 9 numbers.)
The cipher for the safe consists of five different numbers. How many different ciphers are there? (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 appliances?(6 5 4 3 2 1 = 720 ways.)
(8 7 6 5 4 = 6720 options.)
(The numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 are used - a total of 10 digits, excluding 0 and 9 at the beginning of the number by condition, 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 reached our goal today, why? What was difficult in the lesson, how can you deal with these? 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 invited to answer 3 blitz questions:
In today's lesson, I had ... (easy, usually, difficult)
New material I ... (learned and can apply, learned and find it difficult to apply, did not learn)
My self-assessment for the lesson ...
Answers to the above questions can not be signed, 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 did a good job today, learned a lot of new things, but I would really like all of you to work hard at home and not get twos in the next lesson.
7. Homework assignment :
1) Make a task about your class
2) Several countries have 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, be interested in mathematics, this 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 course of mathematics of a secondary school: lectures 1-4, 5-8. - M .: Pedagogical University "First of September", 2006.
Vilenkin N.Ya. Mathematics. Grade 5: textbook for general education. institutions / N.Ya. Vilenkin et al. - M .: Mnemozina, 2009.
Smykalova E.V. Additional chapters in mathematics for students in grade 5. St. Petersburg: SMIO. Press, 2006.
Grade 5 "Mathematics-5", I.I. Zubareva, A.G. Mordkovich, 2004.
Tasks (cards)
How many variants of seven-digit telephone numbers can be formed if numbers starting with 0 and 9 are excluded from them?
One rather famous musketeer has in his wardrobe 3 elegant hats, 4 wonderful cloaks and 2 pairs of excellent boots. How many costume options can he make?
There are 11 people on the football team. It is necessary to choose a captain and his deputy. In how many ways can this be done?
How many different two-digit numbers can be formed using the numbers 1, 4, 7, if the repetition of numbers is allowed
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 cipher for the safe consists of five different numbers. How many different ciphers are there?
In how many ways can 6 people be seated at a table with 6 appliances?
In the fifth grade, 8 subjects are studied. How many different schedules can be made for Monday if there should be 5 lessons on this day and all lessons are different?Answers
6 5 4 3 2 1 = 720 ways
8 7 6 5 4 = 6720 options
The numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 are used - a total of 10 digits, excluding 0 and 9 at the beginning of the number by condition, taking into account the possibility of repetition, we get 8 10 10 10 10 10 10 = 8,000,000 numbers.
We select one element from three sets, that is, we make up 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 that the captain can be chosen in 11 ways, there are 10 players left, from which you can choose the deputy captain. So, a couple, 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 compose a pair of digits in 3 3 = 9 ways, i.e. you get 9 numbers.
Three-digit number: the first position - 5 options for numbers, the second position, taking into account the exclusion of repetitions of numbers, - 4 options, the 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, only 3 of the available 4 digits, 3 choices can be put in the first position, any of the numbers can be put in the second position, taking into account the repetition - 4 choices. Therefore, it turns out 3 4 \u003d 12 numbers; b) First position - 3 options, second position - 3 options, because repetition is excluded. We get 3 3 = 9 numbers.
5 4 3 2 1 = 120 options.When solving many practical problems, one has to use combinations of elements, choose from a given set those that have certain properties, and place them in a certain order. Such tasks are called combinatorial. The section of mathematics devoted to solving problems of choosing and arranging elements in accordance with given conditions is called combinatorics. The term "combinatorics" comes from the Latin word combina, which in translation into Russian means - "to combine", "to connect".
The selected groups of elements are called connections. If all elements of the connection are different, then we get connections without repetitions, which we will consider below.
Most combinatorial problems are solved using two basic rules − sum rules and product rules.
Task 1.
The All for Tea store has 6 different cups and 4 different saucers. How many cup and saucer options can you buy?
Solution.
We can choose a cup in 6 ways, and a saucer in 4 ways. Since we need to buy a pair of cup and saucer, we can do it in 6 4 = 24 ways (according to the product rule).
Answer: 24.
To successfully solve combinatorial problems, it is also necessary to choose the right formula by which to search for the number of desired compounds. The following diagram will help with this. 
Consider the solution of several problems for different types of connections without repetition.
Task 2.
Find the number of three-digit numbers that can be made from the numbers 1, 2, 3, 4, 5, 6, 7, if the numbers in the number cannot be repeated.
Solution.
To select a formula, we find out that for the numbers that we will compose, the order is taken into account and not all elements are selected at the same time. This means that this connection is an arrangement of 7 elements by 3. Let's use the formula for the number of placements: A 7 3 = 7(7 - 1)(7 - 2) = 7 6 5 = 210 numbers.
Answer: 210.
Task 3.
How many seven-digit phone numbers are there where all digits are different and the number cannot start from zero?
Solution.
At first glance, this task is the same as the previous one, but the difficulty is that you must not take into account those connections that start from zero. So it is necessary to make up all seven-digit phone numbers from the existing 10 digits, and then subtract the number of numbers starting from zero from the resulting number. The formula will look like:
A 10 7 - A 9 6 \u003d 10 9 8 7 6 5 4 - 9 8 7 6 5 4 \u003d 544 320.
Answer: 544 320.
Task 4.
In how many ways can 12 books be arranged on a shelf, of which 5 books are collections of poems, so that the collections stand side by side?
Solution.
First, let's take 5 collections conditionally for one book, because they should stand side by side. Since order is essential in the connection, and all elements are used, this means that these are permutations of 8 elements (7 books + conditional 1 book). Their number is R 8 . Further we will rearrange among themselves only collections of poems. This can be done in 5 ways. Since we need to arrange both collections and other books, we will use the product rule. Therefore, R 8 · R 5 = 8! · 5!. The number of ways will be large, so the answer can be left as a product of factorials.
Answer: 8! · 5!
Task 5.
There are 16 boys and 12 girls in the class. To clean the area near the school, 4 boys and 3 girls are needed. In how many ways can they be chosen from all the students in the class?
Solution.
First, we separately select 4 boys out of 16 and 3 girls out of 12. Since the placement order is not taken into account, the corresponding compounds are combinations without repetitions. Considering the need to select both boys and girls at the same time, we use the product rule. As a result, the number of ways will be calculated as follows:
C 16 4 C 12 3 = (16!/(4! 12!)) (12!/(3! 9!)) = ((13 14 15 16) / (2 3 ) 4)) ((10 11 12) / (2 3)) = 400 400.
Answer: 400 400.
Thus, the successful solution of a combinatorial problem depends on the correct analysis of its conditions, the determination of the type of compounds to be composed, and the choice of an appropriate formula for calculating their number.
Do you have any questions? Don't know how to solve combinatorial problems?
To get the help of a tutor - register.
The first lesson is free!
site, with full or partial copying of the material, a link to the source is required.
In many combinatorial problems, it is difficult to directly find the number of variants of interest to us. However, with some change in the conditions of the problem, you can find the number of options that exceeds the original one by a known number of times. This approach is called multiple count method.
1. How many anagrams does the word CLASS have?
The difficulty is that in this word there are two identical letters C. We will temporarily consider them different and denote C 1 and C 2. Then the number of anagrams will be equal to 5! \u003d 120. But those words that differ from each other only by a permutation of the letters C 1 and C 2, in fact, are the same anagram! Therefore, 120 anagrams are divided into pairs of identical ones, i.e. the desired number of anagrams is 120/2 = 60.
2. How many anagrams does the word CHARADA have?
Counting three letters A as different letters A 1, A 2, A 3, we get 6! anagram. But words that are obtained from each other only by rearranging the letters A 1, A 2, A 3, in fact, are the same anagram. Because there are 3! permutations of the letters A 1, A 2, A 3, obtained initially 6! anagrams are divided into groups of 3! identical, and the number of distinct anagrams is 6!/3! = 120.
3. How many four-digit numbers are there that contain at least one even digit?
Let's find the number of "unnecessary" four-digit numbers, in the record of which there are only odd digits. There are 5 4 = 625 such numbers. But there are 9000 four-digit numbers in total, so the desired number of “necessary” numbers is 9000 - 625 = 8375.
- Find the number of anagrams for the words VERESK, BALAGAN, CITY.
- Find the number of anagrams for the words BAOBAB, BALLAD, TROUBLE, ANAGRAM, MATHEMATICS, COMBINATORICS, DEFENSE.
- In how many ways can 7 visitors be accommodated in three hotel rooms: single, double and quadruple?
- There are two apples, three pears and four oranges in the refrigerator. Every day for nine consecutive days, Petya is given one piece of fruit. In how many ways can this be done?
- From the seven best skiers of the school, a team of three people must be selected to participate in city competitions. In how many ways can this be done?
- Before the exam, the professor promised to give half of the examinees deuces. 20 students came to the exam. In how many ways can he keep his promise?
- How many words can be made with five A's and no more than three B's?
- On sale there is chocolate, strawberry and milk ice cream. How many ways can you buy three ice creams?
- When preparing pizza, various components are added to the cheese, providing one or another taste. Bill has onions, mushrooms, tomatoes, peppers and anchovies at his disposal, all of which, in his opinion, can be added to cheese. How many types of pizza can Bill make?
- A witness of the criminal showdown remembered that the criminals fled in a Mercedes, the number of which contained the letters T, Z, Y and the numbers 3 and 7 (the number is a line in which first three letters go, and then three numbers). How many such numbers exist?
- How many diagonals are in a convex n-gon?
- How much is there n-digit numbers?
- How many ten-digit numbers are there that contain at least two identical digits?
- The dice is thrown three times. Among the possible sequences of outcomes, there are those in which a six fell out at least once. How many?
- How many five-digit numbers have the number 1 in their entry?
- In how many ways can the white and black kings be placed on a chessboard so that they do not attack each other?
- How many divisors does 10800 have?
Abstract on the topic:
Completed by a student of grade 10 "B"
secondary school №53
Glukhov Mikhail Alexandrovich
Naberezhnye Chelny
2002
Content
| From the history of combinatorics _______________________________________________ | 3 |
| Sum rule _________________________________________________ | 4 |
| - | |
| Product rule _____________________________________________ | 4 |
| Examples of tasks __________________________________________________________ | - |
| Intersecting sets ____________________________________________ | 5 |
| Examples of tasks __________________________________________________________ | - |
| Euler circles _________________________________________________ | - |
| Placements without repetitions ______________________________________________ | 6 |
| Examples of tasks __________________________________________________________ | - |
| Permutations without repetitions _______________________________________ | 7 |
| Examples of tasks __________________________________________________________ | - |
| Combinations without repetitions __________________________________________ | 8 |
| Examples of tasks __________________________________________________________ | - |
| Placements and combinations without repetition ______________________________ | 9 |
| Examples of tasks __________________________________________________________ | - |
| Permutations with repetitions | 9 |
| Examples of tasks __________________________________________________________ | - |
| Tasks for independent solution ________________________________ | 10 |
| Bibliography___________________________________ | 11 |
From the history of combinatorics
Combinatorics deals with various types of compounds that can be formed from elements of a finite set. Some elements of combinatorics were known in India as early as the 2nd century BC. BC e. The Nidians were able to calculate numbers, which are now called "combinations". In the XII century. Bhaskara calculated some kinds of combinations and permutations. It is assumed that Indian scientists studied compounds in connection with their use in poetics, the science of the structure of the verse and poetic works. For example, in connection with the calculation of possible combinations of stressed (long) and unstressed (short) syllables of the foot of n syllables. As a scientific discipline, combinatorics was formed in the 17th century. In the book "Theory and Practice of Arithmetic" (1656), the French author A. also devotes an entire chapter to combinations and permutations.
B. Pascal in the "Treatise on the Arithmetic Triangle" and in the "Treatise on Numerical Orders" (1665) expounded the doctrine of binomial coefficients. P. Fermat knew about the connections between mathematical squares and figurative numbers with the theory of compounds. The term "combinatorics" began to be used after the publication by Leibniz in 1665 of the work "Discourse on combinatorial art", in which for the first time a scientific substantiation of the theory of combinations and permutations was given. J. Bernoulli was the first to study placements in the second part of his book "Ars conjectandi" (the art of divination) in 1713. The modern symbolism of combinations was proposed by various authors of educational manuals only in the 19th century.
The whole variety of combinatorial formulas can be derived from two basic statements concerning finite sets - the sum rule and the product rule.
Sum rule
If the finite sets do not intersect, then the number of elements X U Y (or) is equal to the sum of the number of elements of the set X and the number of elements of the set Y.
That is, if there are X books on the first shelf, and Y on the second, then you can choose a book from the first or second shelf in X + Y ways.
Task examples
The student must complete practical work in mathematics. He was offered a choice of 17 topics in algebra and 13 topics in geometry. In how many ways can he choose one topic for practical work?
Solution: X=17, Y=13
According to the sum rule X U Y=17+13=30 topics.
There are 5 cash and clothing lottery tickets, 6 sports lotto tickets and 10 car lottery tickets. In how many ways can one ticket be chosen from a sports lottery or car lottery?
Solution: Since the money and clothing lottery does not participate in the choice, there are only 6 + 10 = 16 options.
product rule
If an element X can be chosen in k ways, and an element Y in m ways, then the pair (X,Y) can be chosen in k*m ways.
That is, if there are 5 books on the first shelf and 10 on the second, then you can choose one book from the first shelf and one from the second in 5 * 10 = 50 ways.
Task examples
The binder has to bind 12 different books in red, green and brown bindings. In how many ways can he do this?
Solution: There are 12 books and 3 colors, so according to the product rule, 12 * 3 = 36 binding options are possible.
How many five-digit numbers are there that read the same from left to right and from right to left?
Solution: In such numbers, the last digit will be the same as the first, and the penultimate - like the second. The third digit will be any. This can be represented as XYZYX, where Y and Z are any digits and X is not zero. So, according to the product rule, the number of digits that are equally read both from left to right and from right to left is 9 * 10 * 10 = 900 options.
Overlapping sets
But it happens that the sets X and Y intersect, then they use the formula
, where X and Y are sets, and is the area of intersection. Task examples20 people know English and 10 - German, 5 of them know both English and German. How many people in total?
Answer: 10+20-5=25 people.
Euler circles are also often used to visually solve the problem. For example:
Out of 100 tourists going on a trip abroad, 30 people speak German, 28 - English, 42 - French. 8 people speak English and German at the same time, 10 people speak English and French, 5 German and French, 3 all three languages. tourists do not speak any language?Solution: Let us express the condition of this problem graphically. Let us designate a circle for those who know English, another circle for those who know French, and a third circle for those who know German.
Three tourists speak all three languages, which means that in the common part of the circles we enter the number 3. 10 people speak English and French, and 3 of them also speak German. Therefore, only English and French are spoken by 10-3=7 people.Similarly, we get that only English and German are spoken by 8-3=5 people, and German and French by 5-3=2 tourists. We enter this data in the relevant parts.
Let us now determine how many people speak only one of the listed languages. 30 people know German, but 5+3+2=10 of them also speak other languages, so only 20 people know German. Similarly, we get that 13 people speak one English, and 30 people speak one French.According to the condition of the problem, there are only 100 tourists. 20 + 13 + 30 + 5 + 7 + 2 + 3 = 80 tourists know at least one language, therefore, 20 people do not speak any of these languages.
Placements without repetition.
How many phone numbers can be made up of 6 digits each so that all digits are distinct?
This is an example of a placement problem with no repetitions. 10 digits of 6 are placed here. And options in which the same numbers are in a different order are considered different.
If an X-set consisting of n elements, m≤n, then an ordered set X containing m elements is called an ordered set X containing m elements.
The number of all arrangements of n elements by m is denoted by
n! - n-factorial (factorial English factor) the product of natural numbers from 1 to any number n Task
In how many ways can 4 boys ask 4 out of 6 girls to dance?
Solution: Two boys cannot invite the same girl at the same time. And the options in which the same girls dance with different boys are considered different, therefore:
360 options are possible.
Permutations without repetition
In the case of n=m (see placements without repetitions) of n elements by m is called a permutation of the set x.
The number of all permutations of n elements is denoted by P n.
Valid for n=m:
Task examples
How many different six-digit numbers can be made from the digits 0, 1, 2, 3, 4.5 if the numbers do not repeat in the number?
1) Find the number of all permutations of these numbers: P 6 =6!=720
2) 0 cannot be in front of the number, so from this number it is necessary to subtract the number of permutations in which 0 is in front. And this is P 5 =5!=120.
P 6 -P 5 \u003d 720-120 \u003d 600
naughty monkey
Yes, clubfoot Mishka
Started to play a quartet
Stop, brothers, stop! -
Monkey shouts, - wait!
How does the music go?
You don't sit like that...
And so, and so transplanted - again the music is not going well.
