How many combinations are 2 out of 10. Combinatorics: basic rules and formulas. Permutations and probability theory

All N elements, and none are repeated, then this is a problem about the number of permutations. The solution can be found simple. The first place in a row can be any of N elements, therefore, there are N options. In second place - any, except the one that has already been used for first place. Therefore, for each of the N options already found, there are (N - 1) second place options, and the total number of combinations becomes N*(N - 1).
The same can be repeated for the remaining elements of the series. For the very last place, there is only one option left - the last remaining element. For the penultimate one there are two options, and so on.
Therefore, for a series of N non-repeating elements, the possible permutations are equal to the product of all integers from 1 to N. This product is called the factorial of N and is denoted N! (read “en factorial”).

In the previous case, the number of possible elements and the number of places in the row coincided, and their number was equal to N. But a situation is possible when there are fewer places in the row than there are possible elements. In other words, the number of elements in the sample is equal to a certain number M, and M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
First, you may want to count the total number of possible ways in which M elements out of N can be arranged in a row. These ways are called arrangements.
Secondly, the researcher may be interested in the number of ways in which M elements can be selected from N. In this case, the order of the elements is no longer important, but any two options must differ from each other by at least one element. Such methods are called combinations.

To find the number of placements of M elements out of N, you can resort to the same method of reasoning as in the case of permutations. There can still be N elements in the first place, N - 1 in the second place, and so on. But for the last place, the number of possible options is not equal to one, but (N - M + 1), since when the placement is completed, there will still be (N - M) unused elements.
Thus, the number of placements of M elements from N is equal to the product of all integers from (N - M + 1) to N, or, what is the same, the quotient N!/(N - M)!.

Obviously, the number of combinations of M elements from N will be less than the number of placements. For every possible combination there is an M! possible placements depending on the order of the elements of this combination. Therefore, to find this quantity, you need to divide the number of placements of M elements from N by N!. In other words, the number of combinations of M elements from N is equal to N!/(M!*(N - M)!).

COMBINATORICS

Combinatorics is a branch of mathematics that studies the problems of selecting and arranging elements from a certain basic set in accordance with given rules. Formulas and principles of combinatorics are used in probability theory to calculate the probability of random events and, accordingly, obtain the laws of distribution of random variables. This, in turn, allows us to study the patterns of mass random phenomena, which is very important for a correct understanding of the statistical patterns that manifest themselves in nature and technology.

Rules for addition and multiplication in combinatorics

Sum rule. If two actions A and B are mutually exclusive, and action A can be performed in m ways, and B in n ways, then one of these actions (either A or B) can be performed in n + m ways.

Example 1.

There are 16 boys and 10 girls in the class. In how many ways can you assign one duty officer?

Solution

Either a boy or a girl can be assigned to duty, i.e. the duty officer can be any of the 16 boys or any of the 10 girls.

Using the sum rule, we find that one duty officer can be assigned in 16+10=26 ways.

Product rule. Let there be k actions required to be performed sequentially. If the first action can be performed in n 1 ways, the second action in n 2 ways, the third in n 3 ways, and so on until the kth action that can be performed in n k ways, then all k actions together can be performed:

ways.

Example 2.

There are 16 boys and 10 girls in the class. In how many ways can two duty officers be appointed?

Solution

Either a boy or a girl can be appointed as the first person on duty. Because There are 16 boys and 10 girls in the class, then you can appoint the first person on duty in 16+10=26 ways.

After we have chosen the first duty officer, we can choose the second one from the remaining 25 people, i.e. 25 ways.

According to the multiplication theorem, two attendants can be selected in 26*25=650 ways.

Combinations without repetition. Combinations with repetitions

A classic problem in combinatorics is the problem of the number of combinations without repetitions, the content of which can be expressed by the question: how many ways Can choose m from n different items?

Example 3.

You must choose 4 out of 10 different books available as a gift. In how many ways can this be done?

Solution

We need to choose 4 books out of 10, and the order of choice does not matter. Thus, you need to find the number of combinations of 10 elements of 4:

.

Consider the problem of the number of combinations with repetitions: there are r identical objects of each of n different types; how many ways Can choose m() from these (n*r) items?

.

Example 4.

The pastry shop sold 4 types of cakes: Napoleons, eclairs, shortbread and puff pastries. In how many ways can you buy 7 cakes?

Solution

Because Among 7 cakes there may be cakes of the same type, then the number of ways in which 7 cakes can be bought is determined by the number of combinations with repetitions of 7 to 4.

.

Placements without repetition. Placements with repetitions

A classic problem in combinatorics is the problem of the number of placements without repetitions, the content of which can be expressed by the question: how many ways Can choose And post By m different places m from n different items?

Example 5.

Some newspaper has 12 pages. It is necessary to place four photographs on the pages of this newspaper. In how many ways can this be done if no page of the newspaper should contain more than one photograph?

Solution.

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

Thus, 4 photos on 12 pages can be arranged in 11,880 ways.

Also a classic problem in combinatorics is the problem of the number of placements with repetitions, the content of which can be expressed by the question: how many ways Can Youbarmy And post By m different places m from n items,Withready which There is the same?

Example 6.

The boy still had stamps with the numbers 1, 3 and 7 from his board game set. He decided to use these stamps to put five-digit numbers on all the books to create a catalogue. How many different five-digit numbers can a boy create?

Permutations without repetition. Permutations with repetitions

A classic problem in combinatorics is the problem of the number of permutations without repetition, the content of which can be expressed by the question: how many ways Can post n various items on n different places?

Example 7.

How many four-letter “words” can you make from the letters of the word “marriage”?

Solution

The general population is the 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 among the selected n elements there are identical ones (selection with return), the problem of the number of permutations with repetitions can be expressed by the question: In how many ways can n objects located in n different places be rearranged if among n objects there are k different types (k< n), т. е. есть одинаковые предметы.

Example 8.

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

Solution

There is 1 letter "m", 4 letters "i", 3 letters "c" and 1 letter "p", for a total of 9 letters. Therefore, the number of permutations with repetitions is equal to

BACKGROUND SUMMARY FOR THE SECTION "COMBINATORICS"

Friends! Since I already have this dead notebook, I’ll use it to ask you a problem that three physicists, two economists, one from Polytechnic and one from the humanities were struggling with yesterday. We have broken our whole brain and we constantly get different results. Maybe there are programmers and mathematical geniuses among you, besides, the problem is generally a school one and very easy, we simply cannot derive the formula. Because we gave up studying the exact sciences and instead, for some reason, we write books and draw pictures. Sorry.

So, the background.

I was given a new bank card and, as usual, I playfully guessed its PIN code. But not in a row. I mean, let's say the PIN code was 8794, and I said 9748. That is, I triumphantly guessed all the numbers, which were contained in this four-digit number. Well, yes, not the number itself, but just its components I was wondering. But the numbers are all correct! NOTE - I acted at random, that is, I did not have to arrange the already known numbers in the right order, I simply acted in the spirit: here there are four numbers unknown to me, and I believe that among them there may be 9, 7, 4 and 8, and their order is not important. We immediately asked ourselves, how many options did I have?(probably to understand how cool it is that I just took it and guessed). That is, how many combinations of four numbers did I have to choose from? And then, naturally, all hell broke loose. Our heads were exploding all evening, and we all ended up with completely different answers! I even started writing out all these combinations in a notebook in a row as they increased, but at four hundred I realized that there were more than four hundred (in any case, this refuted the answer of the physicist Thrash, who assured me that there were four hundred combinations, but still this is not quite clearly) - and gave up.

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

Or not, let’s rephrase it (I’m a humanist, forgive me, although I’ve always had a huge weakness for mathematics) to make it clearer and more precise. How many non-repetitive combinations of numbers contained in the series of ordinal numbers from 0 to 9999? ( please don't confuse this with the question "how many combinations non-repetitive numbers"!!! numbers may be repeated! I mean, 2233 and 3322 are in this case the same combination!!).

Or even more specific. I need to guess one number out of ten four times. But not in a row.

Well, or something else. In general, I need to find out how many options I had for the numerical combination from which the card PIN code was composed. Help, good people! Just please, when helping, don’t immediately start writing that there are 9999 options for these(yesterday this was what came to everyone’s mind at first), because this is nonsense - after all, from the perspective that worries us, the number 1234, the number 3421, the number 4312 and so on are the same thing! Well, yes, the numbers can be repeated, because there is a PIN code 1111 or, for example, 0007. You can imagine a car number instead of a PIN code. Let's say, what is the probability of guessing all the single-digit numbers that make up the car number? Or, to remove the theory of probability altogether - from how many number combinations did I have to choose one?

Please support your answers and reasoning with some precise formulas, because yesterday we almost went crazy. Thank you all very much in advance!

P.S. One smart person, a programmer, artist and inventor, just very correctly suggested the correct solution to the problem, giving me several minutes of great mood: " The solution to the problem is this: she has obsessive-compulsive disorder, the treatment is this: get married and hill tomatoes. If I were her, I would be more concerned not with the question “what is the probability”, but with the question “why am I paying attention to all these numbers”? In general, there’s not even anything to add :)

The calculator below is designed to generate all combinations of n by m elements.
The number of such combinations can be calculated using the Elements of Combinatorics calculator. Permutations, placements, combinations.

Description of the generation algorithm under the calculator.

Algorithm

Combinations are generated in lexicographic order. The algorithm works with ordinal indices of set elements.
Let's look at the algorithm using an example.
For simplicity of presentation, consider a set of five elements, the indices of which begin with 1, namely, 1 2 3 4 5.
It is required to generate all combinations of size m = 3.
The first combination of the given size m is initialized first - indices in ascending order
1 2 3
Next, the last element is checked, i.e. i = 3. If its value is less than n - m + i, then 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 = 5 - 3 + 3 = 5, the previous element with i = 2 is checked.
If its value is less than n - m + i, then it is incremented by 1, and for all 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 we check again for i = 3.
1 3 5
Then check for i = 2.
1 4 5
Then comes the turn of i = 1.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
And further,
2 3 5
2 4 5
3 4 5 - the last combination, since all its elements are equal to n - m + i.

Despite the important role of PIN codes in the world's infrastructure, there has been no academic research into how people actually choose PIN codes.

Cambridge University researchers Sören Preibusch and Ross Anderson have corrected the situation by publishing the world's first quantitative analysis of the difficulty of guessing a 4-digit bank PIN.

Using data on password leaks from non-bank sources and online surveys, scientists found that users take the choice of PIN codes much more seriously than the choice of passwords for websites: most codes contain an almost random set of numbers. However, among the initial data there are also simple combinations and birthdays - that is, with some luck, an attacker can simply guess the treasured code.

The starting point of the study was a set of 4-digit password sequences from the RockYou database (1.7 million), and a database of 200 thousand PIN codes from the iPhone screen lock program (the database was provided by the application developer Daniel Amitay). In the graphs built from this data, interesting patterns emerge - dates, years, repeating numbers, and even PIN codes ending in 69. Based on these observations, scientists built a linear regression model that estimates the popularity of each PIN code depending on 25 factors, such as whether the code is a DDMM date, whether it is an ascending sequence, and so on. 79% and 93% of PIN codes in each set meet these general conditions.

So, users choose 4-digit codes based on just a few simple factors. If bank PIN codes were chosen this way, 8-9% of them could be guessed in just three attempts! But, of course, people are much more attentive to bank codes. In the absence of any large set of real banking data, the researchers surveyed more than 1,300 people to assess how different real PIN codes were from those already considered. Given the specifics of the study, respondents were not asked about the codes themselves, but only about their compliance with any of the above factors (increasing, DDMM format, etc.).

It turned out that people really choose their bank PIN codes much more carefully. About a quarter of respondents use a random PIN generated by the bank. More than a third choose their PIN using an old phone number, student ID number, or another set of numbers that appears random. According to the results, 64% of cardholders use a pseudo-random PIN, which is much higher than the 23-27% in previous experiments with non-bank codes. Another 5% use a digital pattern (eg 4545), and 9% prefer a keyboard pattern (eg 2684). In general, an attacker with six attempts (three with an ATM and three with a payment terminal) has less than 2% chance of guessing the PIN code of someone else's card.

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, it is much easier for an attacker to spy on your PIN code than to guess it. But you can also protect yourself from peeping, even in a seemingly hopeless situation:

Combinatorics is a branch of mathematics that studies questions about how many different combinations, subject to certain conditions, can be made from given objects. The basics of combinatorics are very important for estimating the probabilities of random events, because It is they that allow us to calculate the fundamentally possible number of different options for the development of events.

Basic formula of combinatorics

Let there be k groups of elements, and the i-th group consists of n i elements. Let's select one element from each group. Then the total number N of ways in which such a choice can be made is determined by the relation N=n 1 *n 2 *n 3 *...*n k .

Example 1. Let us explain this rule with a simple example. Let there be two groups of elements, and the first group consists of n 1 elements, and the second - of n 2 elements. How many different pairs of elements can be made from these two groups, such that the pair contains one element from each group? Let's say we took the first element from the first group and, without changing it, went through all possible pairs, changing only the elements from the second group. There can be n 2 such pairs for this element. Then we take the second element from the first group and also make all possible pairs for it. There will also be n 2 such pairs. Since there are only n 1 elements in the first group, the total possible options will be n 1 *n 2 .

Example 2. How many three-digit even numbers can be made from the digits 0, 1, 2, 3, 4, 5, 6, if the digits can be repeated?
Solution: n 1 =6 (because you can take any number from 1, 2, 3, 4, 5, 6 as the first digit), n 2 =7 (because you can take any number from 0 as the second digit , 1, 2, 3, 4, 5, 6), n 3 =4 (since any number from 0, 2, 4, 6 can be taken as the third digit).
So, N=n 1 *n 2 *n 3 =6*7*4=168.

In the case when all groups consist of the same number of elements, i.e. n 1 =n 2 =...n k =n we can assume that each selection is made from the same group, and the element after selection is returned to the group. Then the number of all selection methods is n k . This method of selection in combinatorics is called samples with return.

Example 3. How many four-digit numbers can be made from the digits 1, 5, 6, 7, 8?
Solution. For each digit of a four-digit number there are five possibilities, which means N=5*5*5*5=5 4 =625.

Consider a set consisting of n elements. In combinatorics this set is called general population.

Number of placements of n elements by m

Definition 1. Accommodation from n elements by m in combinatorics any ordered set from m various elements selected from the population in n elements.

Example 4. Different arrangements of three elements (1, 2, 3) by two will be the sets (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2 ). Placements may differ from each other both in elements and in their order.

The number of placements in combinatorics is denoted by A n m and is calculated by the formula:

Comment: n!=1*2*3*...*n (read: “en factorial”), in addition, it is assumed that 0!=1.

Example 5. How many two-digit numbers are there in which the tens digit and the units digit are distinct and odd?
Solution: because If there are five odd digits, namely 1, 3, 5, 7, 9, then this task comes down to selecting and placing two of the five different digits in two different positions, i.e. the indicated numbers will be:

Definition 2. Combination from n elements by m in combinatorics any unordered set from m various elements selected from the population in n elements.

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

Number of combinations of n elements, m each

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

Example 7. In how many ways can a reader choose two books out of six available?

Solution: The number of methods is equal to the number of combinations of six books of two, i.e. equals:

Permutations of n elements

Definition 3. Permutation from n elements are called any ordered set these elements.

Example 7a. All possible permutations of a set consisting of three elements (1, 2, 3) are: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), ( 3, 2, 1), (3, 1, 2).

The number of different permutations of n elements is denoted by P n and is calculated by the formula P n =n!.

Example 8. In how many ways can seven books by different authors be arranged in one row on a shelf?

Solution: This problem is about the number of permutations of seven different books. There are P 7 =7!=1*2*3*4*5*6*7=5040 ways to arrange the books.

Discussion. We see that the number of possible combinations can be calculated according to different rules (permutations, combinations, placements) and the result will be different, because The calculation principle and the formulas themselves are different. Looking carefully at the definitions, you will notice that the result depends on several factors simultaneously.

Firstly, from how many elements we can combine their sets (how large is the totality of elements).

Secondly, the result depends on the size of the sets of elements we need.

Finally, it is important to know whether the order of the elements in the set is significant to us. Let us explain the last factor using the following example.

Example 9. There are 20 people present at the parent meeting. How many different options are there for the composition of the parent committee if it must include 5 people?
Solution: In this example, we are not interested in the order of names on the committee list. If, as a result, the same people turn out to be part of it, then in meaning for us this is the same option. Therefore, we can use the formula to calculate the number combinations of 20 elements 5 each.

Things will be different if each committee member is initially responsible for a specific area of ​​work. Then, with the same list composition of the committee, there are possibly 5 within it! options permutations that matter. The number of different (both in composition and area of ​​responsibility) options is determined in this case by the number placements of 20 elements 5 each.

Self-test tasks
1. How many three-digit even numbers can be made from the digits 0, 1, 2, 3, 4, 5, 6, if the digits can be repeated?
Because An even number in third place can be 0, 2, 4, 6, i.e. four digits. The second place can be any of the seven digits. The first place can be any of the seven digits except zero, i.e. 6 possibilities. Result =4*7*6=168.
2. How many five-digit numbers are there that are read the same from left to right and from right to left?
The first place can be any number except 0, i.e. 9 possibilities. Any number can be in second place, i.e. 10 possibilities. The third place can also be any number from, i.e. 10 possibilities. The fourth and fifth digits are predetermined, they coincide with the first and second, therefore, the number of such numbers is 9*10*10=900.
3. There are ten subjects in the class and five lessons a day. In how many ways can you create a schedule for one day?

4. In how many ways can 4 delegates be selected for a conference if there are 20 people in the group?

n = C 20 4 = (20!)/(4!*(20-4)!)=(16!*17*18*19*20)/((1*2*3*4)*(16! ))=(17*18*19*20)/(1*2*3*4)=4845.
5. In how many ways can eight different letters be placed in eight different envelopes, if only one letter is placed in each envelope?
You can put 1 of the eight letters in the first envelope, one of the remaining seven in the second, one of the six in the third, etc. n = 8! = 1*2*3*4*5*6*7*8 = 40320.
6. A commission consisting of two mathematicians and six economists should be composed of three mathematicians and ten economists. In how many ways can this be done?