Combination formulas. Elements of combinatorics Possible options for selecting 4 numbers out of 10

First of all, we will analyze the basic concepts of combinatorics - samples and their types: permutations, accommodation and combinations. To know them is necessary for solving a large part of the EGE 2020 in mathematics of both levels, as well as nine-graders for passing fire. Let's start with the example.

Permutations. Counting the number of permutations.

Imagine that you have chosen a profession, which seemingly not related to mathematics, such as interior designer. Imagine that the customer expressed you a request:

"Put 4 books on the shelf so that the burgundy and blue volumes do not stand nearby. Show me everything Options for arrangements. I choose the most preferred. "

What will you do? Most likely, you will start to arrange and show. However, in order not to get confused, not to miss any of the possible options and not repeat, you need to do it on some system.

For example, first, we leave the burgundy volume in the first place, there may be green or orange next to it. If there is a green volume in second place, then it can be either orange and blue or blue and orange. If there is an orange volume in second place, then there can be either green and blue or blue and green. Total, 4 possible options are obtained.

In the first place may be any of the 4 volumes, which means the described procedure must be repeated 3 more times. The case when the blue volume is in the first place, it turns out to be the same reasoning.

And the next two cases differ in that on the remaining three places there should be burgundy and blue volumes, but not near. For example, when the first place is worth the green volume, the orange volume should stand in third place to separate the burgundy and blue volumes that can occupy, respectively, or the second and fourth place, or the fourth and second.

As a result, we had only 12 options for the arrangement of the 4th books on the shelf with a given restriction. Is there a lot or a little? If you spend one minute to move books and the discussion of the resulting option with the customer, then, perhaps, is normal. 12 minutes you can wear books, and talk. (Try to calculate how much the permutations would have the permutations of the 4th books without any restrictions?)

Now imagine that the customer has more books than 4. Well, at least 5. It is clear that the options for the arrangement will be more, and really rearrange them from place to place longer, and get confused and begin to repeat easier ... So rushing in Fight without preparation is no longer worth it. You must first schedule options on paper. For brevity, we will wear out our color volumes and will rearrange their numbers on paper. To make less wrong, first we will write down all the options for the permutation, and then cross out those of them that fall under the restriction. So:

"Arrange 5 books on the shelf so that the 1st and 2nd volumes do not stand near. Show everything Options for permutations. "

We have 5 books (or 5 digits), each of which can stand in the first place. We will make your tablet for each of these 5 cases. In second place may be any of the remaining 4 digits, for each of them we reserve the column in the plate.

In each column, we place a pair of lines in which one of the remaining 3-digit hours is standing in third place, and the two recent numbers change places. So we carefully write out everything Options for permutation. Calculate them total number.

5 (tables) × 4.(column) × 3.(pairs of strings) × 2.(lines) × 1 (option) \u003d. 120 (options).

And finally, cross out from all tables of options containing "12" or "21". These were 6 in the first and second signs and 12 in the remaining 3rd, only 48 options that do not satisfy the restriction. So the customer needs to show 120 - 48 \u003d 72 options for the location of 5 books. It will take more than an hour, even if we spend on a discussion of each option only a minute.

Only where did you see a person who will hire a designer to rearrange five books? Really such tasks arise in libraries where you need to place the books for the convenience of visitors, in large bookstores, where you need to place the books to ensure an increase in demand, etc. That is, where books are not units, and not even dozens, but hundreds and thousands.

Call options permutations are not only for books. This may be necessary for a large number of any objects in almost any field of activity. It means that both designers and people of other professions may need an assistant, and even better tool to facilitate the preparatory stage, analysis of possible results and reducing the volume of unproductive labor. Such tools created and create mathematics scientists, and then give them to society in the form of ready-made formulas. Mathematics did not bypass their attention related to permutations, as well as with accommodation and combinations of different elements. The corresponding formulas are no longer one century. These formulas are very simple, the smaller part of the society "is awarded" in school mathematics lessons. Therefore, everything that was written above is a substantially "invention of a bicycle", to which I had to resort because of the assumption that the interior designer would never need mathematics. Well, give up this assumption. We repeat the mathematical concepts, and then back again to the task of the bookshelf.

Combinatorium The region of mathematics is called, in which questions are studied on how many different combinations subordinate to these or no conditions can be made up of elements of a given set. By constiting a combination, we actually select different elements from this set and combine them into groups according to our needs, so instead of the word "combinations", the word "sample" of the elements often use.

Formula for the number of permutations.

Permutations These samples of elements are called, which differ only by the order of the elements, but not the elements themselves.

If the permutations are made on a set of n. elements their number Determined by the formula
P N. = n.·( n.-1) · ( n.-2) ... 3 · 2 · 1 \u003d n.!

n.! - Designation that is used for a brief record of the work of all natural numbers from 1 to n. inclusive and called " n.-Factor "(translated from English" Factor "-" Multiplier ").

Thus, the total number of permutations of 5 books P 5. \u003d 5! \u003d 1 · 2 · 3 · 4 · 5 \u003d 120, what we got higher. In fact, we derived this formula for a small example. Now I will solve more example.

Task 1..

30 volumes are placed on the bookshelf. In how many ways they can be placed so that at the same time the 1st and 2nd volumes did not stand nearby?

Decision.

We define the total number of permutations of 30 elements by the formula P 30.=30!
To calculate the number of "unnecessary" permutations, first we define how many options in which the 2nd volume is located next to the 1st on the right of it. In such permutations, the 1st volume may occupy places from the first to 29th, and the 2nd from the second to the 30s - only 29 places for this pair of books. And with each position of the first two volumes, the remaining 28 books can occupy the remaining 28 places in any order. Options for permutation 28 books P 28.\u003d 28! In total "superfluous" options at the location of the 2nd volume to the right of the 1st will turn out 29 · 28! \u003d 29!.
Similarly, consider the case when the 2nd volume is located next to the 1st, but to the left of it. It turns out the same number of options 29 · 28! \u003d 29!.
So all the "unnecessary" permutations 2 · 29!, And the necessary methods of arrangement of 30! -2 · 29! Calculate this value.
thirty! \u003d 29! · 30; 30! -2 · 29! \u003d 29! · (30-2) \u003d 29! · 28.
So, we need to multiply all the natural numbers from 1 to 29 and multiplied by 28 again.
Answer: 2.4757335 · 10 32.

This is very big number (after two another 32 digits). Even if you spend a second for each permutation, you will need billions of years. Is it worth performing such a requirement of the customer, or is it better to be able to reasonably argue to him and insist on applying additional restrictions?

Rearrangements and probability theory.

More often, the need to count the number of options occurs in the theory of probability. Continue the book theme next task.

Task 2..

On the bookshelf there were 30 volumes. The child dropped books from the shelf, and then put them in random order. What is the probability that he not Put the 1st and 2nd Tom near?

Decision.

First, we define the likelihood of event A, which is that the child put the 1st and 2nd volume nearby.
Elementary event - some placement of books on the shelf. It is clear that the total number all Elementary events will be equal to the total number of all possible permutations P 30.=30!.
The number of elementary events conducive to events A is equal to the number of permutations in which the 1st and 2nd volumes are nearby. We considered such permutations, solving the previous task, and received 2 · 29! permutations.
The probability determines the division of the number of conducive elementary events by the number of all possible elementary events:
P (a) \u003d 2 · 29! / 30! \u003d 2 · 29! / (29! · 30) \u003d 2/30 \u003d 1/15.
Event in - Child not Put the 1st and 2nd volume near - the opposite of the event A, which means its probability P (b) \u003d 1 - p (a) \u003d 1-1 / 15 \u003d 14/15 \u003d 0,9333
Answer:0,9333.

Remark: If it is not clear how the fractions with factoria are reduced, remember that the factorial is a brief record of the work. It can always be painted long and stress repeated multipliers in the numerator and in the denominator.

The answer turned out the number close to one, it means that with such a number of books randomly put two specified volumes next to more difficult than not to deliver.

Accommodation. Counting the number of accommodation.

Now suppose that the customer has many books and it is impossible to place them all on the open shelves. His request is that you need to choose a certain amount of any books and place them beautifully. It turned out beautifully or ugly this is the question of the taste of the customer, i.e. he wants to see again everything Options and make a decision myself. Our task is to calculate the number of all possible accommodation options for books, reasonably convince it and introduce reasonable limitations.

To sort out the situation, let's first assume that "a lot" is 5 books that we have only one regiment, and that only 3 volumes are fitted on it. What do we do?
We choose one of the 5 books and put on the first place on the shelf. We can do this in the 5th way. Now there are two places on the shelf and we have 4 books left. We can choose the second book 4 ways and put next to one of the 5 possible first. Such pairs may be 5 · 4. There are 3 books and one place. One book from 3rd can be chosen by 3 ways and put next to one of the possible 5 · 4 pairs. It turns out 5 · 4 · 3 diverse triples. It means that ways to place 3 books from 5 5 · 4 · 3 \u003d 60.

The figure shows only 4 options for accommodation from 60 possible. Compare pictures. Please note that the placement may differ from each other or only the order of the elements, as the first two groups, or the composition of the elements, as the following.

Formula for the number of accommodation.

Accommodation of n. Elements in m. (places) are called such samples that having m. elements selected from the number of data n. Elements differ from one another or composition of elements, or by the order of their location.

Number of accommodation out n. by m. denotes A. N M. and determined by the formula
A. N M \u003d. n.·( n. - 1) · ( n. - 2) · ... · ( n. − m. + 1) = n.!/(n - m)!

Let's try to calculate for this formula A N N.. Number of accommodation out n. by n..
A N N. = n.·( n.-one)·( n.-2) · ... · ( n.-n. + 1) = n.·( n.-one)·( n.-2) · ... · 1 \u003d n.!
In this way, A N N. = P N. = n.!

Nothing surprising is that the number of accommodation from n. by n. It turned out equal number Rearranged n. Elements, because we used all the set of elements to prepare all the sets, which means they can no longer differ from each other with the composition of the elements, only by the order of their location, and this is the permutation.

Task 3..

How many ways can I arrange 15 volumes on the bookshelf, if you choose them from the available 30 books?

Decision.

We define the total number of accommodation from 30 elements of 15 by the formula
A 30 15. \u003d 30 · 29 · 28 · ... · (30-15 + 1) \u003d 30 · 29 · 28 · ... · 16 \u003d 202843204931727360000.
Answer: 202843204931727360000.

Will you post real books? Good luck! Consider how many lives will need to go through all the options.

Task 4..

How many ways can you arrange 30 books on two shelves, if only 15 volumes are placed on each of them?

Decision.

Method I.
Imagine that the first shelf we fill in the same way as in the previous task. Then placement options from 30 books will be A 30 15. \u003d 30 · 29 · 28 · ... · (30-15 + 1) \u003d 30 · 29 · 28 · ... · 16.
And with each placement of books on the first shelf, we still P 15. \u003d 15! In methods we can arrange books on the second shelf. After all, for the second shelf, we left 15 books by 15 places, i.e. Only permutations are possible.
All ways will be A 30 15 · p 15While the product of all numbers from 30 to 16 will still be multiplied by the product of all numbers from 1 to 15, the product of all natural numbers from 1 to 30, i.e. thirty!
Method II.
Now imagine that we had one long regiment on 30 seats. We put all 30 books on it, and then saw the shelf into two equal parts to satisfy the condition of the task. How many options for the arrangement could be? As much as you can make permutations of 30 books, i.e. P 30. = 30!
Answer: 30!.

It does not matter how you decide the mathematical task. You decide it as imaging your actions in the life situation. It is important not to retreat from logic in your reasoning so that in any case you get the right answer.

Placement and theory of probability.

In the theory of probability, the task on placement is somewhat less common than the tasks of other types of samples, since the placement has more identification features - both the order and composition of the elements, which means less are subject to random choice.

Task 5..

On the bookshelf there is a collection of writings of one author in 6 volumes. The books of the same format are arbitrary. The reader, without looking, takes 3 books. What is the probability that he took the first three volumes?

Decision.

Event A - reader the first three volumes. With regard to the order of choice, he could take them in the 6th way. (This is permutations from the 3rd elements. P 3. \u003d 3! \u003d 1 · 2 · 3 \u003d 6, which is easy to list 123, 132, 213, 231, 312, 321.)
Thus, the number of favorable elementary events is equal to 6.
The total number of possible elementary events is equal to the number of accommodation from 6 to 3, i.e. A. 6 3 \u003d 6 · ... · (6-3 + 1) \u003d 6 · 5 · 4 \u003d 120.
P (a) \u003d 6/120 \u003d 1/20 \u003d 0.05.
Answer: 0,05.

Combination. Counting the number of combinations.

And the last case is all the books of the customer of the same color and one size, but only some of them are placed on the shelf. It would seem that the designer would have no problem, choose so many books from the total number, as you need, and place them on the shelf in an arbitrary order, because the books are externally indistinguishable. But they differ, and significantly! These books are different in content. And the customer may not all be where the tragedies of Shakespeare are located, and where the Detectives of the Rex Stata, on an open shelf or in the closet. Thus, we have a situation where the composition of the elements of the sample is important, but the order of their location is insignificant.

The figure shows two samples from the "Collection of the writings of one author in 5 volumes." The first one will like the customer more, if it often reread the early works of this author, placed in the first three volumes, the second - if more often appeals to the late works placed in the last volumes. We look at both groups equally beautiful (or equally ugly) and it does not matter whether the group will be located as 123 or as 321 ...

Formula for the number of combinations.

Unordered samples are called of n. Elements in m. And indicate FROM N M..
The number of combinations Determined by the formula FROM N M \u003d. n!/(n. - M)! / m!

In this formula, there are two divisors and a symbol is used as a sign of division. / ", which is more convenient for the web page. But division can also be denoted by a colon" : "Or a horizontal line" --- ". In the latter case, the formula looks like an ordinary fraction in which the sequential division is represented by two factors in the denominator. . For those who are more understandable in the form of fractions, all formulas are duplicated at the beginning and at the very end of the page. Viewing solutions to tasks compare my entry with usual for yourself.
In addition, all multipliers and dividers in this formula are works of successive natural numbers, so the fraction is well reduced if it is written in detail in detail. But I miss a detailed abbreviation in tasks, it is easy to check it yourself.

It is clear that for the same source sets from n. elements and identical sample volumes (by m. Elements) The number of combinations should be less than the number of accommodation. After all, when counting accommodation for each selected group, we still take into account all the permutations of the selected m. Elements, and when calculating combinations, do not take into account: With n m = A N M./P M. = n!/(n-M.)!/m!

Task 6..

How many methods can be arranged 15 volumes on the bookshelf, if you choose them out of the external indistinguishable 30 books?

Decision.

We solve this task in the context of the design of the interior designer, so the order of following the same books on the shelf of the 15 selected externally identical books does not matter. It is necessary to determine the total number of combinations of 30 elements of 15 by the formula
FROM 30 15 = 30! /(30 − 15)!/15! = 155117520.
Answer: 155117520.

Task 7..

How many ways can you arrange 30 externally indistinguishable books on two shelves, if only 15 volumes are placed on each of them?

If we answer this question from the point of view of the interior designer, then the order of books on each of the shelves is insignificant. But the customer may be important or no matter how books are distributed among the shelves.
1) For example, if both shelves are near, both are open, both at the same altitude, then the customer can say that it does not matter. Then the answer is obvious - 1 way, since when arranged, all many of the 30 books are used, and no permutations are taken into account.
2) But when one of the shelves is too high, the customer is important which books on it are located. In this case, the answer will be the same as in the previous problem - 15511,7520 methods, because the first shelf is fill in samples-combinations of 30 to 15, and on the second place the remaining 15 books excluding permutations.

So, there are such wording tasks that the answers can be obtained ambiguous. For an accurate solution, additional information is needed that we usually get from the context of the situation. The creators of examination tasks, as a rule, do not allow a double interpretation of the condition of the problem, formulate it is somewhat longer. However, if you have doubts, it is better to apply to the teacher.

Combination and theory of probability.

In the theory of probability, the task for combinations are most often found, because the grouping without the order of interest is more important for indistinguishable elements. If some elements differ significantly among themselves, they are difficult to choose by accident, there are guidelines for non-random selection.

Task 8..

On the bookshelf there is a collection of writings of one author in 6 volumes. Books are equally decorated and arbitrary. The reader takes at random 3 books. What is the probability that he took the first three volumes?

Decision.

Event A - reader the first three volumes. This is the 1st, 2nd and 3rd volume. Excluding order in which he chose books, but only by the final result, he could take them in one way. The number of favored elementary events - 1.
The total number of possible elementary events is equal to the number of groups of 6 to 3 formed without taking into account the procedure for following the elements in the group, i.e. equal to the number of combinations From 6 3. \u003d 6! / 3! / (6 - 3)! \u003d 4 · 5 · 6 / (1 · 2 · 3) \u003d 4 · 5 \u003d 20.
P (a) \u003d 1/20 \u003d 0.05.
Answer: 0,05.

Compare this task with task 5 (for placement). In both tasks, very similar conditions and exactly the same answers. In essence, it is just the same household situation and, accordingly, the same task that can be interpreted one way or another. The main thing is that when calculating elementary events, both favorable and all possible, there was a single understanding of the situation.

Final comments.

For strict output of all formulas (which I did not give here) used two basic rules of combinatorics:

Multiplication rule (rule " and"). According to him, if an element A can be selected n. ways and with any choice a element b can be chosen m. ways then a couple a and B You can choose n · M. ways.

This rule is generalized on an arbitrary length of the sequence.

Completion rule (rule " or"). It claims that if an element A can be selected n. ways, and element b can be chosen m. ways then choose a or B is possible n + M. ways.

These rules are needed to solve problems.

Concept factorial Also applies to zero: 0! = 1 So it is believed that the empty set can be ordered by the only way.

Calculate the factories of large numbers by direct multiplication on the calculator for a very long time, and very large numbers - and on the computer is not fast. But how did you cope with this before the creation of computers and calculators? Even at the beginning of the 18th century, J.Stirling and independently of him, A. Maurra received a formula for an approximate calculation of factorials, which is the more accurate than the more n.. Now this formula is called stirling formula:

Final task.

When solving problems on probability theory using combinatorial methods, it is necessary to carefully analyze the proposed situation in order to correctly select the type of sampling. Try to do this on the example of the next task. Solve it, compare the answer, and then click the button to open my solution.

Task 9..

From aquarium, in which 6 sazans and 4 carp, a sacc of 5 fish caught. What is the likelihood that there are 2 Sazan and 3 carp among them?

Decision.

Elementary event - "in a saccine group of 5 fish." Event A - "Among the 5 caught fish turned out to be 3 carp and 2 Sazan ".
Let be n. - The total number of possible elementary events, it is equal to the number of ways to group 5 fish. Total fish in aquarium 6 + 4 \u003d 10. In the process of catching the sacc of fish outwardly indistinguishable. (We do not know whether we caught the fish named Bachka or by the name of Koska. Moreover, until we pulled out the saccus up and did not look into it, we don't even know Sazan it or carp.) Thus, "catch 5 fish from 10 "means to make a sample type of combination out of 10 to 5.
n. = From 10 5. = 10!/5!/(10 - 5)!
Pulling out the cuckoo and looking into it, we can determine the favorable outcome or not, i.e. Is the catch of two groups - 2 Sazan and 3 carp?
The Sazanov group could form a choice of 6 Sazanov at 2. And anyway, which of them first climbed into the sump, and who is the second, so on. This is a sample type of combination of 6 to 2. Denote by the total number of such samples. m 1. And I calculate it.
m 1. = From 6 2. = 6!/2!/(6 - 2)!
Similarly, the total number of possible groups of 3 carp is determined by the number of combinations of 4 to 3. Denote it m 2..
m 2. = With 4 3. = 4!/3!/(4 - 3)!
Groups of carps and sazans are formed in a saccus independently of each other, so to calculate the number of elementary events conducive to Event A, we use the rule of multiplication ("and" -Evilo) combinatorics. So, the total number of conducive elementary events
m \u003d m 1 · m 2 = From 6 2.· With 4 3.
The probability of events A determine by the formula P (A) \u003d m / N \u003d C 6 2 · C 4 3 / C 10 5
We substitute all the values \u200b\u200bin this formula, sign factorials, reduce the fraction and get the answer:
P (a) \u003d 6! · 4! · 5! · (10 - 5)! / 2! / (6 - 2)! / 3! / (4 - 3)! / 10! \u003d 5/21 ≈ 0.238

Comments.
1) Combinations are usually found in tasks where the process of group formation is observed, and only the result is important. Sasan Bachka without a difference was first he fell into a saccus or last, but it is very important to him, in which group it turned out to be in the end - among those who are in Sachka, or among those who are free.
2) Note, we use the "and rule", because the Union "and" is directly in the description of the event A, for which it is necessary to calculate the likelihood of a joint catch of two groups. However, we apply it only after they were convinced of the independence of the samples. In fact, can't Sazan, swimming toward the saccus, recalculate his fellow people, and tell Karpa: "Your turn, our already two." And will the carp agree to climb into the sacc of Sazan? But if they could agree, it would be impossible to apply this rule. It would be necessary to refer to the concept of a conditional probability.

Answer: 0,238.

Show a decision.

If you are a graduate school and take an exam, then after studying this section, return (10 for the base and 4 for the profile levels of the EGE 2020 in mathematics), which can be solved using the elements of the combinatorics and without it (for example, to throw coins). Which of the possible ways to solve the task do you like more now?

And if you want to spend a little more in solving the challenges of combinatorics to learn how to quickly determine the type of sampling and find the desired formulas, then go to the page

Combinatorics

The combinatorics is a section of mathematics, which studies the problem of selection and location of elements from some basic set in accordance with the specified rules. Formulas and principles of combinatorics are used in the theory of probabilities to calculate the probability of random events and, accordingly, obtaining the laws of the distribution of random variables. This, in turn, makes it possible to investigate the patterns of mass random phenomena, which is very important for the correct understanding of the statistical patterns that manifest themselves in nature and technology.

Rules of addition and multiplication in combinatorics

Rule amount. If two actions A and in mutually exclude each other, and the Action A can be performed by m in methods, and in n methods, then you can perform one of these actions (or a, or c) n + m methods.

Example 1.

16 boys and 10 girls study in the classroom. How many ways can you assign one attendant?

Decision

On duty can be prescribed either a boy or a girl, i.e. Any of 16 boys can be on duty, or any of 10 girls.

According to the rule, we obtain that one duty can be prescribed 16 + 10 \u003d 26 methods.

The rule of the work. Let it be required to perform successively k actions. If the first action can be performed by N 1 methods, the second effect N 2 methods, the third - n 3 methods and so to the k-th action, which can be performed by N k methods, then all k actions together can be met:

ways.

Example 2.

16 boys and 10 girls study in the classroom. How many ways can you assign two duty officers?

Decision

The first duty can be prescribed either a boy or a girl. Because There are 16 boys and 10 girls in the classroom, then you can assign a first onternal-duty to 16 + 10 \u003d 26 ways.

After we chose the first duty, we can choose from the remaining 25 people, i.e. 25th way.

By the multiplication theorem, two duty can be selected 26 * 25 \u003d 650 methods.

Combination without repetitions. Combination with repetition

The classical problem of combinatorics is the task of the number of combinations without repetitions, the content of which can be expressed by the question: how many methods can choose m is n different items?

Example 3.

You must choose as a gift 4 out of 10 available different books. How many ways can I do this?

Decision

We are out of 10 books to choose 4, and the order of choice does not matter. Thus, it is necessary to find the number of combinations of 10 elements of 4:

.

Consider the task of the number of combinations with repetitions: there are on R identical objects of each of N of various types; how many methods can choose m () from these (N * R) items?

.

Example 4.

The confectionery store sold 4 varieties of cakes: Napoleon, eclairs, sandy and puff. How many ways can you buy 7 cupcakes?

Decision

Because Among the 7 cupcakes there can be pastries of one variety, the number of ways to buy 7 cakes is determined by the number of combinations with repetitions of 7 to 4.

.

Placement without repetitions. Placement with repetition

The classic problem of combinatorics is the task of the number of accommodation without repetitions, the content of which can be expressed by the question: how many methods can choose and place by m Various mesam. m is n different objects?

Example 5.

In some newspaper 12 pages. It is necessary on the pages of this newspaper to place four photos. How many ways can this be done if no newspaper page should contain more than one photo?

Decision.

In this task, we do not just choose photos, and place them on certain pages of the newspaper, and each page of the newspaper should contain no more than one photo. Thus, the task is reduced to the classical task of determining the number of placements without repetitions of 12 elements of 4 elements:

Thus, 4 photos on 12 pages can be positioned 11880 in the methods.

Also, the classical task of combinatorics is the task of the number of placements with repetitions, the content of which can be expressed by the question: how many methods can youb.rATI and place by m Various mesam. m is n objects fromred which there is the same?

Example 6.

The boy remained from a set for desktop games stamps with numbers 1, 3 and 7. He decided with these stamps to apply five-digit numbers to the catalog to all books. How many different five-digit numbers can be a boy?

Rearrangements without repetitions. Rearrangements with repetition

The classic problem of combinatorics is the task of the number of permutations without repetition, the content of which can be expressed by the question: how many methods can place n. valid objects on the n different places?

Example 7.

How much can the four-letter "words" from the letters of the word "marriage"?

Decision

The general set is 4 letters of the word "marriage" (B, P, A, K). The number of "words" is determined by the permutations of these 4 letters, i.e.

For the case when there are the same (sample with the return) among the n elements, the task of the number of permutations with repetitions can be expressed by the question: in how many ways can be rearranged by N items located on N different places, if there are K various types among N objects (k< n), т. е. есть одинаковые предметы.

Example 8.

How many different letters can be made from the letters of the word "Mississippi"?

Decision

Here is 1 letter "M", 4 letters "and", 3 letters "C" and 1 letter "P", only 9 letters. Consequently, the number of rearrangements with repetitions is

Support for the section "Combinatorics"

Friends! Since I have this dead notebook, I use it to ask you a challenge, three physics, two economists, one polytechnic and one humanitarian begged yesterday. We broke the whole brain and we constantly get different results. Maybe among you there are programmers and mathematical geniuses, besides, the task is generally school and very easy, we simply do not displaced the formula. Because we threw classes with accurate sciences and instead for some reason we write books and draw pictures. Sorry.

So, the prehistory.

I was given a new bank card and I, as usual, the playing gave her PIN code. But not in a row. In the sense, let's say, PIN code was 8794, and I called 9748. That is, I am triumphantly Guess all the numbers guesswhich was kept in this four-digit number. Well yes, Not number, and simple his components of W.wondered. But the numbers are all true! Note - I acted at random, that is, I did not have to arrange already known numbers in the right order, I simply acted in the spirit: here there are four digits unknown me, and I believe that among them there may be 9, 7, 4 and 8, and their order is not important. We immediately wondered, how many options I have (Probably, to understand how cool it is, what I took and guess). That is, from how many combinations of four digits I needed to choose? And here, naturally, hell began. We have exploded the whole evening, and everyone, in the end, came out absolutely different answers! I even started writing all these combinations in a notebook in a row as increasing, but on four hundred realized that there are more than four hundred (in any case, it refuted the response Physics Tresh, who assured me that there are four hundred combinations, but still it is not very definitely) - and surrendered.

Actually, essence of the question. What is the probability of guessing (in any order) of the four numbers contained in the four-digit number?

Or not, we reformulate (I am a humanitarian, sorry, although there has always been a lot of weakness to mathematics) so that it is clearer and clearer. how many do not repeat Combinations of numbers contains in a number of sequence numbers from 0 to 9999? ( please do not confuse it with a question "How many combinations Do not repeatnumbers "!!! Figures can repeat! In the sense, 2233 and 3322 are in this case the same combination !!).

Or more specifically. I need to guess four digit out of ten four times. But not in a row.

Well, or somehow somehow. In general, you need to know how much I had options for a numerical combination, from which there was a PIN code card. Help, good people! Only please help, do not start to write immediately that the options of these 9999 (yesterday everyone came to mind at first), because it is nonsense - after all, in that perspective, which is worried, number 1234, number 3421, number 4312 and so on are The same thing! Well, yes, the numbers can be repeated, because there is a PIN code 1111 or there, for example, 0007. You can imagine the machine number instead of the PIN code. Suppose what is the likelihood of guessing all the unambiguous numbers from which the machine number develops? Or to remove the theory of probability at all - from how many numerical combinations I needed to choose one?

Please reinforce your answers and reasoning with some accurate formulas, because we never fumbled something like this. Thank you very much!

P.S. One smart person, a programmer, an artist and an inventor, just that very true prompted the right solution to the problem, giving me a few minutes of wonderful mood: " solving the problem is: it has an obsessive-compute disorder, treatment is this: married and dip the tomatoes. I would no longer care about the likelihood in her place, and the question "how do I pay attention to all these numbers"? In general, even nothing to add :)

The calculator is designed to generate all combinations from N by m elements.
The number of such combinations as can be calculated using the calculator elements of combinatorics. Permutations, accommodation, combinations.

Description of the generation algorithm under the calculator.

Algorithm

Combinations are generated in lexicographic order. The algorithm works with the sequence indexes of the elements of the set.
Consider the algorithm on the example.
For simplicity, we consider a set of five elements, the indices in which begin with 1, namely, 1 2 3 4 5.
It is required to generate all combinations of size M \u003d 3.
First initializes the first combination of the specified size M - indexes in ascending order
1 2 3
Next, the last element is checked, i.e. i \u003d 3. If its value is less than N - M + i, it is incremented by 1.
1 2 4
The last element is checked again, and again it is incremented.
1 2 5
Now the value of the element is equal to the maximum possible: n - m + i \u003d 5 - 3 + 3 \u003d 5, the previous element with i \u003d 2 is checked.
If its value is less than n - m + i, it is incremented by 1, and for all the elements following it, the value is equal to the value of the previous element plus 1.
1 (2+1)3 (3+1)4 = 1 3 4
Next again checks for i \u003d 3.
1 3 5
Then - check for i \u003d 2.
1 4 5
Then there comes the queue i \u003d 1.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
And further,
2 3 5
2 4 5
3 4 5 - Last combination, since all its elements are N - M + I.

Despite the important role of PIN codes in the global infrastructure, there was still no academic studies on how, in fact, people choose PIN codes.

Researchers from the University of Cambridge Sören Preibusch and Ross Anderson corrected the situation by publishing the world's first quantitative analysis of the complexity of guessing 4-tie banking PIN.

Using data on password leaks from non-bank sources and online questionnaires, scientists found out that users of PIN codes belong much more serious than the choice of passwords for websites: most codes contain a practically random set of numbers. Nevertheless, among the source data there are also simple combinations, and birthdays, - that is, with some luck, an attacker can just guess the cherished code.

The starting point of the study was a set of 4-tie sequences in passwords from the Rockyou base (1.7 million), and the bases of 200 thousand PIN codes from the iPhone screen lock program (the database provided the Daniel Amitay application developer). In the charts built according to these data, interesting patterns are attracted - dates, years, repetitive numbers, and even PIN codes ending in 69. Based on these observations, scientists have built a linear regression model that evaluates the popularity of each PIN code depending on 25 Factors - for example, whether the date code in the DDMM format is whether it is an increasing sequence, and so on. These general conditions correspond to 79% and 93% of PINs in each of the sets.

So, users choose 4-tie codes based on just a few simple factors. If the banking PIN codes were so chosen, 8-9% of them could be guess for only three attempts! But, of course, people are much more careful to bank codes. Due to the absence of any large set of real bank data, the researchers interviewed more than 1,300 people to estimate how real PIN codes differ from the already considered. Considering the specifics of the study, the respondents did not ask about the codes themselves, but only about their compliance with any of the above factors (increasing, DDMM format, etc.).

It turned out that people are really much more carefully choose banking PIN codes. Approximately a quarter of the respondents use a random PIN generated by the Bank. More than a third choose your PIN, using the old phone number, student ticket number, or another set of numbers that looks random. According to the results obtained, 64% of the cardholders use a pseudo-random PIN code, is much more than 23-27% in previous experiments with non-bank codes. Another 5% is used digital pattern (for example, 4545), and 9% prefer the pattern on the keyboard (for example, 2684). In general, an attacker with six attempts (three with an ATM and three with a payment terminal) has less than 2% of the chances of guess the PIN code of someone else's card.

Factor	Example	Rockyou.	iPhone.	Interview
Dates
DMMM.	2311	5.26	1.38	3.07
DMGG	3876	9.26	6.46	5.54
MDD	1123	10.00	9.35	3.66
MMG	0683	0.67	0.20	0.94
Yyyy.	1984	33.39	7.12	4.95
TOTAL		58.57	24.51	22.76
Keyboard pattern
adjacent	6351	1.52	4.99	-
square	1425	0.01	0.58	-
corners	9713	0.19	1.06	-
cross	8246	0.17	0.88	-
diagonal line	1590	0.10	1.36	-
horizontal line	5987	0.34	1.42	-
word	5683	0.70	8.39	-
vertical line	8520	0.06	4.28	-
TOTAL		3.09	22.97	8.96
Digital Pattern
ends on 69.	6869	0.35	0.57	-
only figures 0-3.	2000	3.49	2.72	-
only numbers 0-6.	5155	4.66	5.96	-
repeating couples	2525	2.31	4.11	-
same numbers	6666	0.40	6.67	-
descending sequence	3210	0.13	0.29	-
increasing sequence	4567	3.83	4.52	-
TOTAL		15.16	24.85	4.60
Random set of numbers		23.17	27.67	63.68

All would be good, but, unfortunately, the essential part of the respondents (23%) selects the PIN code in the form of a date, and almost a third of them uses the date of its birth. This significantly changes the case, because almost all (99%) respondents answered that various identity cards are stored in a wallet with bank cards on which this date is printed. If the attacker knows the birthday of the cardholder, then with a competent approach, the probability of guessing a PIN-code takes off to 9%.

100 most popular PIN codes

0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-1103, 1110-1112, 1123, 1201-1203, 1210-1212, 1234, 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.

P.S. In practice, of course, the attacker is much easier to spill your PIN code than guessing it. But and peeping can be defended - even it would seem, in a hopeless position:

All N elements, and none repeats, then this is the task of the number of permutations. The solution can be found easy. In the first place in a row, any of the n elements may be, therefore, it obtains n options. In second place - any, in addition, which has already been used for the first place. Therefore, for each of N already found options, there is (n - 1) of the orders of the second place, and the total number of combinations becomes N * (n - 1).
It can be repeated for the other elements of the series. For the very last place there is only one option - the last remaining element. For the penultimate - two options, and so on.
Consequently, for a number of N non-refining elements of possible permutations is equal to the product of all from 1 to N. This product is called a factorial number N and denotes N! (He read "En Factorial").

In the previous case, the number of possible elements and the number of places of the row coincided, and their number was N. But it is possible that there is a number of less than the possible elements. In other words, the number of elements in the sample is equal to a number m, and M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
First, it may be necessary to count the total number of possible methods that can be built into a number M of elements from N. Such methods are called accommodation.
Secondly, the researcher may be interested in the number of ways that can be chosen by m elements from N. In this case, the order of the elements is no longer important, but any two options should differ in between at least one element. Such methods are called combinations.

To find the number of accommodation for M elements from N, you can resort to the same method of reasoning, as in the case of permutations. In the first place here can still stand N elements, on the second (n - 1), and so on. But for the last place, the amount of possible options is not equal to one, but (n - m + 1), since when the placement is completed, it will remain (n - m) unused elements.
Thus, the number of accommodation for M elements from n is equal to the product of all integers from (n - m + 1) to n, or, that the same, private n! / (N - m)!.

Obviously, the number of combinations according to M elements from N will be less than the number of accommodation. For each possible combination there is m! Possible accommodations depending on the procedure for the elements of this combination. Consequently, to find this amount, you need to divide the number of accommodation for M elements from N on N!. In other words, the number of combinations according to M elements from n is N! / (M! * (N - M)!).

The combinatorics is a section of mathematics, which studies questions about how many different combinations subordinate to those or other conditions can be made up of the specified objects. The basics of combinatorics are very important to assess the probabilities of random events, because It is they who allow you to calculate the fundamentally possible number of different options for the development of events.

Basic formula combinatorics

Let there be k groups of elements, and i-I group Consists of n i elements. Select one element from each group. Then the total number of n methods that such a choice can be made is determined by the ratio n \u003d n 1 * N 2 * N 3 * ... * n k.

Example 1. Let us explain this rule on a simple example. Let there be two groups of elements, and the first group consists of N 1 of the elements, and the second is from N 2 elements. How many different pairs of elements can be made up of these two groups, so that in a pair one element from each group? Suppose we took the first element from the first group and, without changing it, moved all possible pairs, changing only elements from the second group. Such pairs for this element can be made by N 2. Then we take the second element from the first group and also make up all possible couples for it. Such couples will also be N 2. Since in the first group of only N 1 element, all possible options will be N 1 * N 2.

Example 2. How many three-digit even numbers can be made from numbers 0, 1, 2, 3, 4, 5, 6, if the numbers can repeat?
Decision:n 1 \u003d 6 (because as the first digit can be taken any digit of 1, 2, 3, 4, 5, 6), N 2 \u003d 7 (because as a second digit can be taken any digit of 0 , 1, 2, 3, 4, 5, 6), N 3 \u003d 4 (because as a third digit, you can take any digit of 0, 2, 4, 6).
So, n \u003d n 1 * N 2 * N 3 \u003d 6 * 7 * 4 \u003d 168.

In the case when all groups consist of an identical number of items, i.e. N 1 \u003d N 2 \u003d ... n k \u003d n We can assume that each selection is made from the same group, and the element after the selection is returned to the group again. Then the number of all methods of choice is N K. This method of choice in combinatorics is called Sampling with return.

Example 3. How many of all four-digit numbers can be made from numbers 1, 5, 6, 7, 8?
Decision. For each discharge of the four-digit number there are five possibilities, which means N \u003d 5 * 5 * 5 * 5 \u003d 5 4 \u003d 625.

Consider a set consisting of n elements. This set in the combinatorics is called general Consideration.

Number of accommodation from n elements by m

Definition 1. Accommodation out n. Elements in m. in the combinatorics is called any ordered set of m. various elements selected from the general population in n. Elements.

Example 4.Various places of three elements (1, 2, 3) two will be kits (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2 ). The placement may differ from each other both elements and their order.

The number of accommodation in the combinatorics is denoted by A n M and is calculated by the formula:

Comment: n! \u003d 1 * 2 * 3 * ... * n (read: "en factorial"), in addition, it is believed that 0! \u003d 1.

Example 5.. How many two-digit numbers are there, in which the number of dozens and digit of units are different and odd?
Decision: Because odd figures five, namely 1, 3, 5, 7, 9, then this task is reduced to the selection and placement of two different positions of two of five different numbers, i.e. These numbers will be:

Definition 2. Combination of n. Elements in m. in the combinatorics is called any unordered set of m. various elements selected from the general population in n. Elements.

Example 6.. For the set (1, 2, 3), combinations are (1, 2), (1, 3), (2, 3).

The number of combinations from n elements by m

The number of combinations is denoted by C n M and is calculated by the formula:

Example 7.How many ways the reader can choose two books from six available?

Decision:The number of ways is equal to the number of combinations of six two books, i.e. equally:

Permutations from n elements

Definition 3. Perestanovka of n. Elements are called any ordered set These elements.

Example 7A. All sorts of permutations of the 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 from N elements is denoted by P n and is calculated by the formula P n \u003d n!.

Example 8. In how many ways, seven books of different authors can be placed on the shelf in one row?

Decision:this task is about the number of permutations of seven different books. There is P 7 \u003d 7! \u003d 1 * 2 * 3 * 4 * 5 * 6 * 7 \u003d 5040 ways to place books.

Discussion.We see that the number of possible combinations can be calculated by various rules (permutations, combinations, placement), and the result will be different, because The principle of calculation and the formulas themselves are different. Carefully looking at the definitions, it can be noted that the result depends on several factors at the same time.

First, from what amount of elements we can combine their sets (how large the general set of elements).

Secondly, the result depends on what kind of element sets we need.

And the last, it is important to know whether it is essential for us the order of elements in the set. Let us explain the last factor in the following example.

Example 9.At the parent meeting there are 20 people. How many different options are the composition of the parent committee, if 5 people should enter it?
Decision:In this example, we are not interested in the order of surnames in the list of Committee. If the same people will be among its composition, then in meaning for us it is the same option. Therefore, we can take advantage of the formula for counting the number Combinationsof the 20 elements of 5.

Otherwise, things will be faced if each member of the Committee is initially responsible for a certain direction of work. Then, with the same list of the Committee, it is possible 5! Options rearrangedthat matter. The number of different (and in composition, and on the scope of responsibility) is determined in this case by the number accommodation Of the 20 elements of 5.

Tasks for self-test
1. How many three-digit even numbers can be made from numbers 0, 1, 2, 3, 4, 5, 6, if the numbers can repeat?
Because The number is even in third place can stand 0, 2, 4, 6, i.e. Four digits. In second place can stand any of the seven digits. In the first place can stand any of the seven digits besides zero, i.e. 6 opportunities. Result \u003d 4 * 7 * 6 \u003d 168.
2. How many five-digit numbers exist, which are equally read from left to right and right left?
In the first place can stand any digit except 0, i.e. 9 opportunities. In second place may be any digit, i.e. 10 possibilities. In third place can also stand any digit from, i.e. 10 possibilities. The fourth and fifth digits are defined in advance, they coincide with the first and second, therefore, the number of such numbers 9 * 10 * 10 \u003d 900.
3. In the class ten items and five lessons per day. How many ways can be a schedule for one day?

4. how many ways can you choose 4 delegates to the conference if in a group of 20 people?

n \u003d C 20 4 \u003d (20!) / (4! * (20-4)!) \u003d (16! * 17 * 18 * 19 * 20) / ((1 * 2 * 3 * 4) * (16! )) \u003d (17 * 18 * 19 * 20) / (1 * 2 * 3 * 4) \u003d 4845.
5. How many ways can you decompose eight different letters on eight different envelopes if only one letter is put in each envelope?
In the first envelope you can put 1 of eight letters, in the second one of the seven remaining, in the third one of six. N \u003d 8! \u003d 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 \u003d 40320.
6. Of the three mathematicians and ten economists, it is necessary to compile a commission consisting of two mathematicians and six economists. How many ways can this be done?