Combinatorics is a branch of mathematics that studies problems involving the arrangement or selection of elements from sets.

Groups made up of any objects (any, but of the same nature: letters, numbers, geometric shapes, parts, etc.) are called connections (in sets). The objects themselves from which compounds are made are called elements .

There are three main types of connections: placements, permutations and combinations.

Placements from various (connections) differ from each other either by at least one element or by the order of their arrangement. The number of placements is indicated and calculated by the formula:

Such placements are called placements without repetitions.

EXAMPLE. There are 25 students in the group. They choose a headman, a physical organizer and a trade union leader. What is the number of all possible choices for the group's "triangle"?

Solution. The resulting combinations (i.e. connections) of 25 - and elements of 3 each are placements, since in them not only the composition of the elements of the “triangle” is important, but also the location within it. Hence

Placement with repetitions of elements, each element can contain any element any number of times from 1 to inclusive, or not contain it at all. In other words, each placement with repetitions of elements can consist not only of any, but also any repeated elements. The number of placements with repetitions is calculated by the formula

EXAMPLE 1. It is known that 4 students passed the exam. How many different exam outcomes (score distributions) are possible?

Solution . Number of elements =3("3", "4", "5"); . Consistency, that is, the order of elements, is essential, repetition is inevitable. Hence .

EXAMPLE 2. In how many ways can 10 passengers be distributed among 13 carriages, if for each the only important thing is the carriage number, and not the space occupied in it?

Solution . Let - the number of the carriage chosen by the first passenger, - the number of the carriage chosen by the second passenger, . . . , - the number of the carriage chosen by the tenth passenger. The connection (combination) completely characterizes the distribution of passengers among the cars. Here, each of the numbers can take any integer value from 1 to 13. This means that there will be as many different distributions among the cars as there are similar connections (10 in length) that can be made from elements of the set . Hence .

Permutations from various elements are such compounds, each of which contains all the elements and which They differ from each other only in the order in which the elements are arranged. The number of such permutations from various elements is designated and calculated by the formula:

Since the number of permutations of elements is the same as the number of placements of elements in each, we can write:

EXAMPLE. 5 different car models were selected for testing. In how many ways can they be distributed among five testers?

Solution . The number of ways in which 5 cars can be distributed is equal to the number of combinations of 5 elements of five. Moreover, the combinations themselves differ from each other only in the order of the elements, i.e. permutations apply. Hence .

If among n there are identical elements, then such permutations are called permutations with repetitions . Let there be elements among which are identical, then the number of permutations with repetitions is determined by the formula

If there are two different groups of elements, respectively consisting of identical elements:

EXAMPLE. In what number of ways can 9 citrus fruits be distributed among 9 students if there are 4 tangerines, 3 oranges and 2 lemons?

Solution. Let - tangerines, - oranges and - lemons. Then

Hence .

Combinations from various elements by () in each are called such compounds, of which each contains elements taken from among the given elements, and which differ from each other in at least one element. Number of combinations of various elements in each are designated by a symbol and calculated using the formula:

We are sure that you understand perfectly well that this definition is a definition of the number of combinations without repetitions.

The number of combinations has the following properties:

This property is convenient to use in cases where . For example: .

3. (see first property).

EXAMPLE. For the construction of a dormitory out of 25 students, 3 people are required to be selected. What is the number of all possible choices of this triple?

Solution . The number of possible options is equal to the number of combinations (connections) of 25 elements, 3 in each. Moreover, the combinations differ from each other only in their constituent elements, and the order of their arrangement does not matter. Hence .

Combination with repetitions of the elements, each can contain any element any number of times from 1 to inclusive, or not contain it at all. In other words, each combination with repetitions of these elements, elements in each, can consist not only of different elements, but of any and any repeating elements.

Two combinations of elements are not considered different combinations if they differ from each other only in the order of the elements.

The number of combinations with repetitions is calculated by the formula:

EXAMPLE. How many ways can you create a class schedule of 3 pairs for one day if you study 10 subjects that can be repeated in the schedule? Are schedules considered different if they differ from each other in at least one subject (i.e. the order of subjects in the schedule does not matter)?

Solution. .

Notes.

1. Let us formulate a product rule for combinations of sets: let an element be chosen in different ways. For each selected element

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 i-th group consists of n i elements. Let's select one element from each group. Then total number The N ways in which such a choice can be made is determined by the relation N=n 1 *n 2 *n 3 *...*n k .

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

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

In the case when all groups consist of the same number 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 different and odd?
Solution: because If there are five odd digits, namely 1, 3, 5, 7, 9, then this task comes down to selecting and placing two of the five different digits in two different positions, i.e. the indicated numbers will be:

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

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

Number of combinations of n elements, m each

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

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

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

Permutations of n elements

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

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

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

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

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

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

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

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

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

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

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

Self-test tasks
1. How many three-digit even numbers can be made from the digits 0, 1, 2, 3, 4, 5, 6, if the digits can be repeated?

2. How many five-digit numbers are there that are read the same from left to right and from right to left?

3. There are ten subjects in the class and five lessons a day. In how many ways can you create a schedule for one day?

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

5. In how many ways can eight different letters be placed in eight different envelopes, if only one letter is placed in each envelope?

6. A commission consisting of two mathematicians and six economists should be composed of three mathematicians and ten economists. In how many ways can this be done?

Elements of combinatorics

Combinatorics is the science of arranging elements in a certain order and counting the number of ways of such arrangement.

Combinatorial principle of multiplication If one part of an action can be performed in ways and another in ways, then the entire action can be performed in a number of ways.

Example. Let's say you need to make a set of pens, pencils and rulers. Available:

5 different handles,

7 different pencils,

10 different lines.

In how many ways can the required set be composed?

Solution. The action in this case is to make a set of pen, pencil and ruler; The action is divided into three stages (parts): choose a pen, choose a ruler and choose a pencil. The first part of the action - choosing a pen - can be done in five ways, the second part of the action - choosing a pencil - can be done in seven ways, the third part of the action - choosing a ruler - can be done in ten ways. Then the whole action can be performed

Number of ways. Those. there are possibly 350 variants of this set.

Example. How many sets of lengths of zeros and ones are there?

Solution. The action in this case is to compose a set of lengths from zeros and ones.

The set will be completed if all positions (places) are filled with zeros and ones. The action is divided into parts: fill the first position, the second, etc., fill - y position. The first part of the action - writing the first component - can be done in two ways: you can write 0, or you can write 1, you can also write the second component in two ways, and so on for all the places in the set: at each place you can write either 0 or 1:

Then the entire operation according to the combinatorial principle of multiplication can be performed in a number of ways:

Combinatorial principle of addition. If two actions are mutually exclusive, and one of them can be performed in ways and the other in ways, then both actions can be performed in a number of ways.

Example.

Sampling volume from a set is any sequence of elements of the set.

If the elements in the selection are not repeated, then the selection is called repeatable , otherwise - sampling with repetitions

With non-repetitive sampling, it doesn’t matter how the selection is made: all elements are taken at once, or one by one (one at a time).

The arrangement of selection elements in a certain order is called ordering , and the sample is called ordered, otherwise – disordered.

Let's consider non-repetitive sampling

The arrangement of various elements in a specific order is called rearrangement no repetitions from elements.

For example, on a set of three elements the following permutations are possible: .

The number of different permutations without repetitions of elements is denoted by and is equal to , i.e.

Combination without repetitions of elements by is called an unordered - elemental subset of an - elemental set. The number of combinations without repetitions of elements is equal to:

For example, you need to calculate how many ways you can create a team of three people to be on duty in a group of 30 people. Since the order of people in the brigade is not is fixed and people do not repeat themselves, then we have a case of combinations of 30 elements of 3 without repetitions:

Thus, a team of three people on duty in a group of 30 people can be selected in 4060 different ways.

Accommodation without repetitions of elements by is called an ordered - elemental subset of an -element set.

Theorem.

The number of placements without repetitions of elements is equal to:

Proof. To obtain an ordered -element subset of an -element set, you need to perform two steps: select elements from (this can be done in a number of ways) and then order the selected elements (this can be done in a number of ways). According to the combinatorial principle of multiplication, the entire operation of obtaining an ordered elemental subset of an elemental set can be done in a number of ways.

Properties of combinations without repetitions :

Proof.Since And , then what is asserted is obvious.

2) (no proof).

The values ​​can be found not by calculating the number of combinations formula, but using the so-called Pascal triangle. (Blaise Pascal (1623 – 1662) – French mathematician).

This triangle looks like:

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

The pattern of its construction is as follows: by adding two adjacent numbers, we get the number that is lower between them. The first line is the number of combinations from 1 (), the second line is from 2 ( - from left to right), etc.

Consider a sample with repetitions

Let there be a selection of elements, and the elements from them are identical.

1. The number of different permutations on the elements of such a sample is equal to:

- number of permutations with repetitions on a set of elements

2. Combination with repetitions of elements by - an unordered selection of elements returning from a set containing elements:

- number of different combinations with repetitions of elements according to

3. Placements with repetitions of elements by - arrangement of different balls in different cells

- number of different placements with repetitions

Example . How many different 4-letter words can be made from the symbols?

Solution.In other words, you need to find the number of permutations with repetitions on 4 elements of a sample in which two elements are the same:

Example . How many different permutations can be made from the letters of the word ABAKAN?

Solution.You need to find the number of permutations on a set of 6 elements, among of which there are three elements are the same:

.

Right generalization formula under consideration: the number of different permutations on a set of elements, among which there is

Elements of the first type,

Elements of the second type,

Elements - type

equals:

Example. How many permutations can be obtained from the letters of the word BELL?

Solution.You need to find the number of permutations with repetitions on a set of 8 letters, among which:

letter K is repeated 2 times;

letter O is repeated 3 times;

the letter L is repeated 2 times

letter And it is repeated 1 time.

Thus, .

Example. In how many ways can a set of 5 chocolates be made if there are three types of chocolates, 10 of each type?

Solution.Since when compiling a chocolate set the order of the chocolates is not important, we use the formula of combinations with repetitions for calculation:

Example. In how many ways can 7 people be seated in 9 carriages?

Solution.Since, according to the conditions of the problem, several people can sit in one carriage, and since the seating arrangement depends on who is in which carriage, we use the seating formula with repetitions:

Example. In how many ways can 7 people be seated in 9 carriages, one per carriage?

Solution.Since, according to the conditions of the problem, only one person can sit in one carriage, and since the seating arrangement depends on who is in which carriage, we use the seating formula without repetition:

The same problem can be solved by applying the combinatorial principle of multiplication: the action of seating 7 people is divided into 7 stages: seating the first passenger, seating the second passenger, ..., seating the seventh passenger. The first stage - the placement of the first passenger can be done in 9 ways, the second passenger can also be placed in 9 ways, etc. :

Example. How many different signals can be made from four flags of different colors, if each signal must consist of at least two flags?

Solution. You can create a signal from two flags, from three or from four. The listed situations are mutually exclusive (two flags are not three or four), so let’s calculate how many ways a signal can be generated in each of the listed situations and add up the results.

The action of composing a signal means selecting flags from four and placing them in a certain order. Thus, in each case, you need to perform two steps: the first is to select the checkboxes, the second is to arrange the selected checkboxes in a certain order.

We compose signals from two flags: you can choose two flags out of four in different ways, and you can arrange the selected two checkboxes in a certain order in a number of ways. Thus, according to the combinatorial principle of multiplication, it is possible to create different signals from two flags. ways. This means that you can create different signals from four flags.

Let us now apply the combinatorial principle of addition: everything exists signals from at least two flags.

Example. The car number consists of three letters and three numbers. How many different numbers can be made using 10 numbers and an alphabet of 30 letters.

Obviously, the number of all possible combinations of 10 digits by 4 is 10,000.

The number of all possible combinations of 30 letters by two is equal to .

If we take into account the possibility that letters can be repeated, then the number of repeating combinations is 30 (one repetition possibility for each letter). In total, the total number of two-letter combinations is 900.

If another letter from the alphabet of 30 letters is added to the number, then the number of combinations increases 30 times, i.e. reaches 27,000 combinations.

Finally, because Each letter combination can be associated with a numerical combination, then the total number of license plates is 270,000,000.

E.G. Nikiforova

Most combinatorics formulas use the concept of factorial. The term "factorial" comes from the Latin word factor(“producing”) and denotes a consonant action - a work.

Definition 5.1. Work n first consecutive natural numbers called n-factorial.

Designation: p.

The only formula for calculating factorials that will be used expresses the definition of factorials:

For example: 4! = 1 2 3 4 = 24.

Special cases of the factorial value are specified: 0! = 1 and 1! = 1.

Many creative students try to use their own formulas to calculate the factorial, which leads to errors. It is worth recalling that the factorial of the difference is not equal to the difference of the factorials and, accordingly, you should first perform the action in parentheses, and then take the factorials from the result.

For example: (3 - 2)! = 1! = 1. It is a mistake to perform actions in a different order: 3! - 2! = 1 - 2*3-1-2 = 6- 2 = 4. As we see 4 F 1 and, accordingly, (3 - 2)! F 3! - 2!.

Reduce factorials in fractional expression you can, but also be careful.

If you need to divide the factorial large number by the factorial of another large number, then it is advantageous to write the product of natural numbers in a shortened form. To do this, you need to understand that factorial is just another short form of writing a special product. And one form of recording can be replaced by another, wherever it occurs. For example:

According to the main, beloved property of a fraction, identical factors in the numerator and denominator can be reduced, in whatever form they are expressed, including through factorials. Knowing that inside any work n The first consecutive natural numbers will contain a shorter series of factors, which must be divided into. By reducing the same factors, you can immediately write down only the remaining “tail” of the product, and without the factorial signs.

No longer errors, but difficulties sometimes arise when you have to operate with literal expressions with factorials. In this regard, it is worth considering the following fact. Each factor in the recording of the value of factorials differs from the previous one by one. Therefore, the number appearing in front of the multiplier in such a product p, looks like (p - 1), and preceded by a number of the form (p - 2). So, if necessary n can be written, for example, in this form: n = 1 2 3 ... (p - 2) (p - 1) n = (p - 2)! (p - 1) p.

You need to read the rest of the text and understand the justifications given, but it is not necessary to memorize them. For people who are not involved in mathematics, but only need to use its results to process information in their field of knowledge, a way will be proposed to systematize the basic concepts and formulas of combinatorics, as well as to find the necessary mathematical model for solving a combinatorial problem. However, without understanding the essence of combining different types It will be more difficult to use the scheme for finding solutions to combinatorial problems.

Without giving rigorous evidence, let's see how we can notice patterns when counting the number of combinations of different types. You can combine elements of the original set in two fundamentally different ways: using only various elements or allowing repetition of the same elements in combination. In the first case, having selected an element from the set into a subset, it cannot be reused, since it has already been removed from the original set. With the second selection method, it is allowed that the same element can be used several times. First, let us recall the first method of composing combinations, which does not allow repetition of the same elements in one combination.

Example 5.5

There are four children in the family: Aiya, Borya, Vanya, Galya. They constantly argue with each other over best place in the car, at the cinema, at the table. Parents, tired of the showdown, decided that each next time the children sit differently. How many times will you have to repeat the seating arrangement?

Solution

While there were two children, only two combinations were possible: A - B, B - A.

When Vanya grew up, he could be placed in three places in relation to each of these combinations: on the sides and between the older children.

For the combination A - B, there are three options: B - A - B, A - B - C, A-C - B, and for the combination B - L there are three more options: C - B - L, B - L - C, B - V - L.

There are only two times three new combinations, which corresponds to the action of multiplication 2 3.

When there were four children, then in relation to each of the previous (2 * 3) = = 6 combinations of the fourth child could again be placed on the sides or in one of two places between the eldest three children, i.e. in one of four places. For example, for the combination B - A - B, four new combinations will be obtained:

Thus, instead of each of the previous (2 3) combinations, four new combinations will be obtained. In total, you need to take (2 - 3) times 4, which corresponds to the action of multiplication: (2 3) 4, or you can write 1 * 2-3 * 4 = 4!.

Answer: 24 times.

If a fifth child appears in the family described in the example, then he can be placed in one of five places: two on the sides and three spaces between the older children, i.e. it turns out (1 *2*3* 4) *5 = 5! combinations, etc.

In the example given, we were talking about how differently you can arrange n elements, and received the answer - n combinations. Such combinations are called permutations.

Definition 5.2. Sets that differ from the original set in the order of their elements are called permutations.

Designation: R p.

Statement 5.1. The number of permutations is determined by the formula R p = p.

Now, after justifying the calculation of the number of permutations, it is natural to assume that 0! = 1 and 1! = 1, since a singleton and empty set can be represented (order, don't order) in only one form.

Definition 5.3. Ordered m-element subsets of a given set from n elements are called placements of n elements by t.

Designation: A™, Where p > t.

To justify the derivation of a formula for calculating the number of placements, consider the following example.

Example 5.6

How many different three-digit numbers can be made from the numbers 1, 2, 3, 4, 5 and 6, if the digits in the number cannot be repeated?

Solution

In this problem we're talking about about counting the number of ordered three-element subsets of a set of six elements, i.e. about the number of placements.

You can put any of the six available digits in the first place in the number, while two digits in the number will remain empty. The contenders for second place in each of the six cases will no longer be 6, but 5 remaining digits. In each of the six cases, these will, of course, be different numbers, but it doesn’t matter to us which numbers. In combinatorics it is enough to take into account quantity elements available for selection. As a result, by adding one of the remaining five digits to each of the first six digits, we get 6 times 5 sets of digits, i.e. (6 5) sets. Each of these (6-5) sets has one unused space left on which you can place one of the remaining four numbers. It will turn out (6 5) times but 4 options, i.e. (6-5-4) combinations.

Answer: 120 numbers.

It is easy to see that with this procedure the answer is a product of numbers decreasing by one. In general, when choosing from n elements this work looks like this: n (p - 1) (p - 2) ... . There must be such factors T , according to the number of places in each combination. The last factor in general view It’s more difficult to imagine, but it’s enough to carefully analyze the resulting work. In each factor, the subtrahend is one more than in the previous factor. Since the product actually begins with the subtraction of zero, and everything in the product T differences, then the last minuend is equal to (m - 1). Thus, by processing the information by finding similarities and differences in the resulting expressions, you can get a general answer about the number of combinations for a given sample: n (p - 1) ... [p - (t - 1)].

Statement 5.2. The number of placements is determined by the formulas

Rationale. The first formula contains “almost 77!”, but without the first factors from (77-777)!. In the second formula, the first factors from (77-777) are removed from the factorial! using division.

Comment. L" = R p, if 77 = 777.

If you do not repeat all the reasoning each time, but use the ready-made formula (5.1), then the solution to example 5.6 looks like this: the number of elements in original many n = 6, /7? = 3, the ordering of the elements in the subset is important. Then

Let's consider another, but very similar problem: how many different products of three different factors can be formed by taking the numbers 1, 2, 3, 4, 5, 7 as factors?

The difference in the procedure for composing these combinations is that it is not necessary to take into account the order of the elements in the subsets, since the product does not change when the factors are rearranged. Such combinations are called combinations.

Definition 5.4. An unordered m/7-element subset of a given set of n elements is called a combination of n elements

BY 777.

Designation: C" 7, where p > t.

Statement 5.3. The number of combinations is determined by the formula

Rationale. Unordered subsets of T there will be fewer elements than ordered T-element subsets of the same set, as many times as there are permutations within each set of T fixed elements. A decrease by several times corresponds to the action of division, therefore

For quite a long time and in quite some detail, we considered three types of combinations of the first, non-repetitive method of composing them. To use this information, you need to present it in a compact form. To do this, we once again use such a method of processing information as finding similarities and differences in the three definitions and tabular method presentation of information. Such an analysis of information will allow us to identify three parameters that determine the calculation of the number of combinations without repetitions: the number of elements in the original set p, number of elements in the subset T, the presence of order in subsets. Differences in the composition of combinations are observed in two areas:

• the presence of a coincidence between the number of elements in the set and the number of elements in the subset;
• the difference between subsets from each other in the order in which the elements are written.

Now you can organize the choice of a mathematical model - a formula - to calculate the number of combinations in the form of a table (Table 5.2).

Table 5.2

Selecting formulas for counting combinations without repetitions

This table clearly lacks a combination of “yes and no” answers: the number of elements in the original set and in the subset being compiled is the same and there is no need to take into account the order in which the elements are written in the subset. To a direct question about the number of ways to select five young men from five available young men in a group, without taking into account the order, everyone answers correctly: 1, but errors are very common when using the table superficially and formally.

There is another problem with using a table: the difficulty of determining whether subsets need to be ordered. Initially, not realizing the importance of this issue and not paying due attention to it, in the future many students make mistakes, the reasons for which are related precisely to determining the presence of order in the combinations they make. The material of combinatorics reveals the motive for studying this property of sets and its role. Due to its importance, it is necessary to update knowledge about ordered sets at this stage.

Numbered ordering causes less difficulty in defining it. For example, a line of grandmothers who have their queue number written on their palms, so that when they go away to get some air and rest on a bench, they don’t mix up their line by lining up in front of them. cherished goal in the prescribed manner. Hierarchical ordering causes great difficulties. If the text defines different positions or functions for the selected elements, then this establishes a requirement for orderliness for the combinations made up in the plot.

Help mitigate difficulties in determining hierarchical ordering role playing games. They again implement the technique of presenting themselves as a participant in the events described. For example, here it is worth recalling the organization of classroom hours, namely, school government which future teachers will have to deal with.

Introducing as the presenter class hour proposes to choose a class leader responsible for school duty, for the wall newspaper, for organizing tourist trips, for cultural program, preparation of all kinds subject weeks and writes down a lot of different positions on the board in order to interest students in choosing the most adequate position, suppressing the “just not me” attitude. After the positions are published, the presenter begins to collect proposals, takes into account self-recusals and transitions to more preferred positions. As a result, there may be several columns on the board - lists of surnames, some of which will differ not in the surnames themselves, but only in the order in which they are written in the corresponding column. Next, voting begins, which can collect a different number of votes under the lists of the active class, differing from each other only in the order of recording the same names, but for different positions. The different number of votes convinces us that these were different samples, different combinations, albeit from the same surnames, but ordered differently. In this regard, it is better to pose the question about the ordering of subsets in an algorithm for solving combinatorial problems in the following form: “Can subsets differ from each other not only in content, but also in the order in which elements are written?”

Defining the requirement for ordering of subsets confuses students or, conversely, brings premature joy even when the word “order” appears in the text. For example, the teacher takes a box containing fifteen cards with letters. He takes four cards out of the box and places them in a row in alphabetical order. Does this plot require ordering of the selected subsets? Usually, the answers include a joyful “Yes!” It is written that there is alphabetical order in selectable fours. This is where the following formulation comes in handy: question about orderliness. Among the selected fours there will be no sets of identical letters, but arranged in a different order. This means that the subsets will not differ from each other in order element records in them. There will be sets so many But how many would there be if they were not laid out in a row, but placed in bags, inside of which there would be no order between the elements. Such a quantitative understanding of the question of the ordering of elements in combinations is very important for combinatorics.

When mastering the ability to determine the orderliness of the combinations being made, it is effective to organize a discussion of the following question: “Will there be more ordered or unordered subsets if you choose pairs from the students sitting in class?” First of all, there are always wrong answers. Only the understanding that for every unordered pair there will be two ordered pairs, differing from each other only in the order in which the surnames are written, leads to the optimistic belief: “There are more ordered ones.”

Example 5.7

Out of ten students, three must be selected to work in admissions committee with applicants. How many combinations must be considered to make a complete search of options?

Solution

Stage 1. Brief verbal processing: for example, “choose three students out of ten students.”

Stage 2. Complete recording of the condition in the language of mathematical symbols.

To implement this stage of work on a combinatorial problem, you need knowledge of the symbolism of combinatorics and the ability to determine the presence of such a property of sets as their ordering. Therefore, the following preparation is proposed for symbolic text processing in order to solve combinatorial problems.

Given: n =...; T =...;

order: yes/no.

For example 5.8, this blank will be filled in as follows:

Given: n = 10; T = 3;

order: no.

Based on this workpiece and table. 5.2, the selection of the mathematical model necessary to solve the problem is easy.

Since in given condition the number of elements in the set and subset are not equal (/? F t), then the answers to two questions in the table are “no - no.” In the corresponding row of the table there is a formula for counting the number of combinations of n elements by T. Thus, the solution to the problem as a whole will look like this:

“Choose three students out of ten students.”

Given: p - 10; T = 3;

order: no.

Answer: 120 combinations must be considered to make a complete selection of options.

For more advanced users, table. 5.2 can be expanded by adding another parameter - reusing elements in a subset (Table 5.3).

Table 53

Selecting formulas to calculate all possible combinations

Combinations		Subsets may differ but in order elements?	Is it possible to reuse elements in subsets?
Rearrangements				R p = p
Placements				a;:,=
Combinations				w (p-t)t!
Placements with repetitions				A"= and""
Combinations with repetitions				W_(//2-1-/7-1)! " ~t!-(l- 1)!
Permutations with repetitions			k Jreps 1st element, k 2 repetitions 2nd element, k n repeats /7th element.	Pn(k t,&2,= n V- k 2 ! *„!

The principle of choosing a mathematical model according to table. 5.3 is similar to that shown in example 5.7. Some difficulties may arise with specifying the formula for calculating the number of permutations with repetitions. Therefore, let's consider more example its use.

Example 5.8

Children love to play games with words, in particular, forming words from the letters of a hidden word. The winner is the one who completes more words with the most letters. For simplicity, let’s assume that the word “loon” is a guess. In order not to miss out on profitable long options, let’s calculate how many six-letter combinations of the letters of the word “loon” can, in principle, be made.

Solution

Stage 1: “Choose six letters from six letters.”

Given: n = 6; T = 6;

order: yes;

repeat: yes, to a = 3, k g = 2, k? = 1

Since the answer to three questions in the table is “yes,” we choose a mathematical model using counting the number of permutations with repetitions. Element “a” is repeated three times in the original set, which means that it will be reused three times in six-element combinations. Similarly, the “p” element has a repeat count of two. Next is the simplest part. Since mathematical model selected, all that remains is to correctly substitute the values ​​of the unknowns into the formula and perform the necessary calculations:

Answer: 60.

The form of the formula for calculating the number of permutations with repetitions is easy to justify. If all six letters were different, then the number of permutations would be 6!. But if, for example, three identical letters can appear in subsets, then it does not matter which of these identical letters is in which place allocated for these letters. And this means that the number of permutations with repetitions will be less than the number of non-repeated permutations by as many times as the number of permutations of identical elements that can be made, i.e. in /^-factorial times. Therefore, in the formula for the number of permutations with repetitions, a denominator appeared, in contrast to the formula for non-repeated permutations.

Basic rules of combinatorics.

Combinatorics is a branch of mathematics that studies ways of arranging objects in accordance with special rules and methods of counting the number of all possible ways. Multiplication rule. If some choice A can be made in m ways, and for each of them some other choice B can be made in n ways, then the choice of A and B (in that order) can be made in m × n ways. Example 1. There are 6 roads leading up the mountain. In how many ways can you go up a mountain and down a mountain if the ascent and descent must be on different roads? Solution. The road to the mountain can be chosen in 6 ways, since the ascent and descent must be on different roads, then you can choose the road for descent in 5 ways. Then, according to the multiplication rule, the number of ways to choose a road for ascent and descent is 6×5=30. Addition rule. If a certain choice A can be made in m ways, and a choice B can be made in n ways, then the choice of A or B can be made in m+n ways. Example 2. The box contains 6 red pencils, 5 blue pencils and 3 simple pencils. In how many ways can you choose a colored pencil? Solution. A colored pencil is either red or blue, therefore, according to the rule of addition, the number of ways to choose a colored pencil is 6+5=11. Comment. These rules can be generalized to a larger number of elections. Question. How many basic rules of combinatorics are there?

Rearrangements.

Definition 1. A set is called ordered if each element of this set is assigned a certain natural number from 1 to n, where n is the number of elements of this set, and different numbers are assigned to different elements.

Ordered sets are considered distinct if they differ either in their elements or in their order. Definition 2. Various ordered sets composed of elements of a given set, differing only in the order of the elements, are called its permutations. Example 3. Consider the set M=(a,b,c). This is a set of three elements. Let's make up its various permutations: (a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b, a). We got 6 permutations. P n - the number of all permutations of a set of n elements.

P n =n! (1), where

n!=1·2·3·...·n (read "n factorial"). Comment. 0!=1; (n+1)!=n!·(n+1) . Example 4. How many six-digit numbers, multiples of five, can be made from the digits 0,1,2,3,4,5, provided that there are no identical digits in the number? Solution. Numbers that are multiples of five (divisible by five) end in either 0 or 5. If the last digit of the number is 0, then the remaining digits can be placed in any order, we get permutations of five elements, their P 5 =5!=120. If there is a 5 at the end, then the rest can be arranged P 5 = 120 ways, but among them those that start with 0 are not suitable, since these will not be six-digit numbers. and five-digit numbers, given numbers P 4 =4!=24. Then the required numbers will be 120+120-24=216.

Question. How many permutations of six elements are there?

Your Answer : 720

Permutations with repetitions.

If you take the numbers 1, 2, 3, 4, then you can make 24 permutations from them. But if you take four digits 1, 1, 2, 2, then you can only get the following different permutations: (1,1,2,2),(1,2,1,2),(1,2,2,1) ,((2,2,1,1),(2,1,2,1),(2,1,1,2), that is, six permutations, there are 4 times fewer of them than permutations of four different numbers, since permutations in which identical numbers are swapped are not new permutations, there are 2!·2!=4. Let us consider the problem in general form: let there be a set of elements in which elements occur once, elements occur once,... , elements occur once, and .

Definition 3.Permutations with repetitions- These are permutations of the elements of a given set in which the elements are repeated. - the number of all permutations with repetitions. The number of permutations that do not change a given permutation with repetitions is equal to , and numbers can be rearranged in ways, so we get the following formula for calculating the number of permutations with repetitions:

Example 4. In how many ways can 8 students be accommodated in three rooms: single, triple and quadruple? Solution. Various ways of settling students into rooms are permutations with repetitions, since inside, for example, a triple room, selected students can occupy sleeping places in different ways, but these options will not be new permutations, so we get: That is, a total of 280 ways of settling students. Question. Calculate

Combinations.

Let some set contain n elements.

Definition 4. Any m-element subset of an n-element set is called a combination of n elements by m. - the number of all combinations.

(3)

Example 5. For the competition, out of 30 athletes, three people must be selected. In how many ways can this be done? Solution. A team of 3 athletes is a subset of three elements, that is, a combination of 30 by 3, so the number of ways to select such teams is calculated by formula (3): .

Properties of combinations.

1. 2. . From these properties it follows that , then , next , , and so on. You can arrange these numbers in table form:

.....................................................

.......................

This triangle-shaped table is called Pascal's triangle.

Definition 5. The expression a+b is called a binomial.

Formula (4) is called Newton's binomial formula, and the coefficients are called binomial coefficients. From this formula follows the following property of the number of combinations

Question. .

Combinations with repetitions

Let there be a set containing n types of elements, so if you take some subset of this set, then it can contain identical elements. Definition 6. A combination with repetitions is an m-element subset of a set containing n types of elements in which the elements are repeated. - the number of all combinations with repetitions from n to m. The composition of an m-element subset has the form , where . Replacing each of the numbers with the corresponding number of ones and separating the ones with zeros, we get a set consisting of m ones and n-1 zeros. Each composition corresponds to only one entry of zeros and ones, and each entry specifies only one composition, therefore, the number of different compositions is equal to the number of permutations with repetitions of n-1 zeros and m ones. We get a formula for calculating all combinations with repetitions.

(5)

Example 6. The pastry shop sells four types of cakes: Napoleons, eclairs, shortbread and sponge cakes. In how many ways can you buy 7 cakes? Solution. Any purchase is a subset, which may contain the same elements, so it is a combination with repetitions. The number of all possible purchases is found using formula (5): . Question. In formula (5) m can be greater than n.

Placements

Definition 7. An ordered m-element subset of an n-element set is called an arrangement. - the number of all placements of n elements by m. The number of all arrangements from n to m is greater than the number of all combinations from n to m, since from each subset of m elements you can get m using permutations! ordered subsets, we obtain a formula for the number of placements

(6)

Example 7. There are 25 people in the group. You need to choose the active members of the group: the headman, the deputy headman and the trade union organizer. In how many ways can this be done? Solution. The asset of the group is an ordered subset of three elements, since it is necessary to select not only three people, but also distribute positions between them, which means the asset of the group is the placement, the number of all placements is calculated using the formula (6): . Question. How many times is the number of combinations of 20 by 4 less than the number of placements of 20 by 4?

Placements with repetitions

Let a set of n elements be given, in which there are identical elements, then its subsets can also contain identical elements. Definition 8. Ordered m-element subsets of an n-element set in which elements can be repeated are called repeat arrangements. - the number of all placements from n to m. In a subset of m elements, the first element can be selected in n ways (that is, any element of the set), since elements can be repeated, the second element can also be selected in n ways, similarly, the remaining elements of the subset can be selected in n ways, if you use the multiplication rule, we get the formula to calculate the number of placements with repetitions:

Example 8. 5 people entered the elevator of a ten-story building. Each of them can exit on any floor, starting from the second. In how many ways can they do this? Solution. Since each person can exit on any floor, starting from the second, there are 9 floors for exit. It is necessary to select floors for each person to exit: for the first person, you can choose any of the nine floors, similarly for the remaining passengers, then according to the formula (7 ): ways. Question. Calculate.