Possible choices are 4 out of 10. Formulas of combinatorics. Permutations. Counting the number of permutations

All N elements, and none is repeated, then this is the problem of the number of permutations. The solution can be found simple. Any of the N elements can take the first place in the row, therefore, N options are obtained. In second place - any, except for the one that has already been used for first place. Therefore, for each of the N choices already found, there are (N - 1) second place choices, and total 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 - 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 by N! (read "en factorial").

In the previous case, the number of possible elements and the number of places in the series coincided, and their number was equal to N. But a situation is possible when there are fewer places in the series than there are possible elements. In other words, the number of elements in the sample is equal to some number M, and M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
First, it may be necessary to count the total number of possible ways in which M elements from N can be arranged in a row. Such ways are called placements.
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 by M elements out of N, one can resort to the same way of reasoning as in the case of permutations. In the first place, there can still be N elements, in the second (N - 1), and so on. But for the last place, the number options is not 1, but (N - M + 1), because when the allocation is completed, there will still be (N - M) unused elements.
Thus, the number of placements over M elements from N is equal to the product of all integers from (N - M + 1) to N, or, equivalently, 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 number, you need to divide the number of placements over M elements from N by N!. In other words, the number of combinations of M elements from N is N!/(M!*(N - M)!).

Friends! Since I already have this dead notebook, I'm using it to ask you a problem that three physicists, two economists, one from the Polytechnic and one from the humanities struggled with yesterday. We broke our whole brain and we constantly get different results. Maybe there are programmers and mathematical geniuses among you, besides, the problem is generally school and very easy, we simply do not derive a formula. 'Cause we dropped out exact sciences and instead, for some reason, we write books and draw pictures. Sorry.

So, backstory.

I was given a new bank card and, as usual, I effortlessly guessed its pin code. But not in a row. I mean, let's say the pin code was 8794, and I called 9748. That is, I triumphantly guessed all the numbers contained in the given four-digit number. Well, yes, not just a number, but just its components at wondered. But the numbers are all true! NOTE - I acted at random, that is, I did not have to put the already known numbers in the right order, I just 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 took it and guessed it). That is, how many combinations of four numbers did I have to choose from? And then, of course, hell began. Our heads exploded all evening, and in the end, everyone came out absolutely different variants answer! I even started to write down 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 of them (in any case, this refuted the answer of the physicist Thresh, who assured me that there were four hundred combinations, but still it’s not quite clearly) - and gave up.

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

Or not, let's reformulate (I'm a humanist, sorry, although I always had a huge weakness for mathematics) to make it clearer and clearer. How not recurring combinations of numbers contained in a series of ordinal numbers from 0 to 9999? ( please do not confuse this with the question "how many combinations not recurring numbers"!!! numbers can be repeated! I mean, 2233 and 3322 are in this case the same combination!).

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

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

Please back up your answers and reasoning with some precise formulas, because yesterday we almost lost our minds. Many thanks in advance to everyone!

P.S. One clever man, programmer, artist and inventor, just very correctly suggested the correct solution to the problem, giving me a few minutes of great mood: " the solution to the problem is this: she has an obsessive-compulsive disorder, the treatment is this: get married and spud tomatoes. If I were in her place, I would be more concerned not with the question “what is the probability”, but with the question “do I fucking pay attention to all these numbers”? In general, there is nothing 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 the ordinal indices of the elements of the set.
Let's consider the algorithm with an example.
For ease of presentation, consider a set of five elements whose indices begin with 1, namely, 1 2 3 4 5.
It is required to generate all combinations of size m = 3.
First, the first combination of the given size m is initialized - 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
Then again we check for i = 3.
1 3 5
Then - check for i = 2.
1 4 5
Then comes the turn 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 PINs in the world's infrastructure, no academic research has yet been conducted on how people actually choose PINs.

University of Cambridge researchers Sören Preibusch and Ross Anderson rectified 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-banking sources and online surveys, the researchers 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. Nevertheless, among the initial data there are both simple combinations and birthdays - that is, with some luck, an attacker can simply guess the coveted 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 on this data, interesting patterns appear - dates, years, repeating numbers, and even PIN codes ending in 69. Based on these observations, scientists built a linear regression model, which evaluates the popularity of each PIN based on 25 factors, such as whether the code is a DDMM date, whether it is an ascending sequence, and so on. These general conditions are met by 79% and 93% of the PIN codes in each of the sets.

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 interviewed more than 1,300 people to assess how real PIN codes differ from those already considered. Given the specifics of the study, the respondents were not asked about the codes themselves, but only about their compliance with any of the above factors (increase, DDMM format, etc.).

It turned out that people really are much more careful in choosing bank PIN codes. Approximately a quarter of respondents use a random PIN generated by a bank. More than a third choose their PIN using their old phone number, number student card, or some other set of numbers that looks random. According to the results, 64% of cardholders use a pseudo-random PIN code, which is much more than 23-27% in previous experiments with non-bank codes. Another 5% use a number 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 a 2% chance of guessing someone else's card PIN.

Factor	Example	rock you	iPhone	Interview
*Dates*
DDMM	2311	5.26	1.38	3.07
DMYY	3876	9.26	6.46	5.54
MMDD	1123	10.00	9.35	3.66
mmyy	0683	0.67	0.20	0.94
YYYY	1984	33.39	7.12	4.95
Total		58.57	24.51	22.76
*Keyboard pattern*
related	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 with 69	6869	0.35	0.57	-
only numbers 0-3	2000	3.49	2.72	-
only numbers 0-6	5155	4.66	5.96	-
recurring couples	2525	2.31	4.11	-
same digits	6666	0.40	6.67	-
descending sequence	3210	0.13	0.29	-
ascending sequence	4567	3.83	4.52	-
Total		15.16	24.85	4.60
*Random set of numbers*		23.17	27.67	63.68

Everything would be fine, but, unfortunately, a significant part of the respondents (23%) chooses a PIN code in the form of a date - and almost a third of them use their date of birth. This makes a significant difference, as almost all (99%) of the respondents answered that they keep various identification cards in their wallet with bank cards, on which this date is printed. If an attacker knows the birthday of the cardholder, then with a competent approach, the probability of guessing the PIN-code soars to 9%.

Top 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 than to guess it. But you can also protect yourself from peeping - even, it would seem, in a 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 make it possible to calculate the fundamentally possible number of different scenarios for the development of events.

Basic combinatorics formula

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

Example 1 Let us explain this rule with a simple example. Let there be two groups of elements, the first group consisting of n 1 elements, and the second - of n 2 elements. How many different pairs of elements can be made from these two groups so that the pair contains one element from each group? Suppose 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 are 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, there will be n 1 *n 2 possible options.

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 \u003d 6 (since you can take any digit from 1, 2, 3, 4, 5, 6 as the first digit), n 2 \u003d 7 (since you can take any digit from 0 as the second digit , 1, 2, 3, 4, 5, 6), n 3 \u003d 4 (since you can take any digit from 0, 2, 4, 6 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 choice is made from the same group, and the element returns to the group after the choice. Then the number of all ways of choosing is equal to n k . This way of choosing in combinatorics is called return samples.

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

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

Number of placements from n elements by m

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

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

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

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

Example 5. How many two-digit numbers are there in which the tens digit and the units digit are different and odd?
Solution: because there are five odd digits, namely 1, 3, 5, 7, 9, then this problem is reduced to choosing and placing two of the five different digits in two different positions, i.e. the given numbers will be:

Definition 2. Combination from n elements by m in combinatorics is called any unordered set from m various elements selected from the general 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 by m

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

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

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

Permutations of n elements

Definition 3. Permutation from n elements is 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 a 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 principle of counting and the formulas themselves are different. Looking closely at the definitions, you can see that the result depends on several factors at the same time.

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

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

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

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

Things will be different if each member of the committee is initially responsible for a certain area of work. Then, with the same payroll of the committee, 5 are possible inside it! options permutations that matter. The number of different (both in terms of composition and area of responsibility) options is determined in this case by the number placements out of 20 elements, 5.

Tasks for self-test
1. How many three-digit even numbers can be made from the numbers 0, 1, 2, 3, 4, 5, 6, if the numbers can be repeated?
Because an even number in the 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 read the same way from left to right and from right to left?
The first place can be any number except 0, i.e. 9 possibilities. The second place can be any number, 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 make a schedule for one day?

4. In how many ways can 4 delegates be chosen for the 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 put into eight different envelopes if only one letter is placed in each envelope?
In the first envelope, you can put 1 of the eight letters, in the second one of the seven remaining letters, in the third one of the six, etc. n = 8! = 1*2*3*4*5*6*7*8 = 40320.
6. From three mathematicians and ten economists it is necessary to make a commission consisting of two mathematicians and six economists. In how many ways can this be done?

COMBINATORICS

Combinatorics is a branch of mathematics that studies the problems of choosing and arranging elements from some basic set in accordance with given rules. Formulas and principles of combinatorics are used in probability theory to calculate the probability random events and, accordingly, obtaining distribution laws random variables. This, in turn, makes it possible to study the laws of mass random phenomena, which is very important for a correct understanding of the statistical laws 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 any 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 one attendant be appointed?

Solution

You can appoint either a boy or a girl on duty, i.e. any of the 16 boys or any of the 10 girls can be on duty.

According to the sum rule, we get that one duty officer can be assigned 16+10=26 ways.

Product rule. Let it be required to perform sequentially k actions. 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 up to 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 attendants be appointed?

Solution

The first person on duty can be either a boy or a girl. Because there are 16 boys and 10 girls in the class, then you can appoint the first duty officer 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.

By the multiplication theorem, two attendants can be chosen in 26*25=650 ways.

Combinations without repetition. Combinations with repetitions

The classical problem of 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 various items ?

Example 3

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

Solution

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

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

Example 4

The pastry shop sold 4 types of cakes: napoleons, eclairs, shortbread and puff. In how many ways can 7 cakes be bought?

Solution

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

Placements without repetition. Placements with repetitions

The classical problem of 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 place on 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 problem, we do not just select photos, but place them on certain pages of the newspaper, and each page of the newspaper should contain no more than one photo. Thus, the problem is reduced to the classical problem of determining the number of placements without repetitions from 12 elements by 4 elements:

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

Also classical problem 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 place on m different places m from n itemsWithredi which there is the same?

Example 6

The boy had left from the set for board game stamps with the numbers 1, 3 and 7. He decided to use these stamps to put five-digit numbers on all books - to compile a catalog. How many different five-digit numbers can the boy make?

Permutations without repetition. Permutations with repetitions

The classical problem of 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 place n various items on the n different places?

Example 7

How many four-letter "words" can be made from the letters of the word "marriage"?

Solution

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 among the selected n elements there are the same (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 be rearranged in n different places if among n objects there are k different types (k< n), т. е. есть одинаковые предметы.