Elements of combinatorics. Basic rules and formulas of combinatorics

Rumor has it that a key prerequisite for creating elements of combinatorics and probability theory has become the addiction of people to lotteries, dice, cards and other gambling. Excitement was of great importance in antiquity. Some have won fortunes, lands, wives. Others lost everything they had, right up to the last shirt. Indeed, the influence of risk games or random games has taken place. However, there were more thorough reasons, including the rapid development of science: conducting experiments, the need to predict the course of a series of experiments and evaluate the error of the results. All this and much more led to the appearance of elements of combinatorics and probability theory.

Bernoulli's theorem

It is believed that combinatorics appeared in the XVII century thanks to the work of scientists such as Cardano, Pascal, Galileo, Fermat, Leibniz, Bernoulli. It was they who introduced the use of specific terms for this science and proved a number of fundamental laws and the first formulas for combinatorics. For example, Bernoulli’s theorem, which states that consideration should be given only to those experiments and experiments with randomness that are independent of each other and can be repeated as many times as necessary under the same conditions. It is generally accepted that this theorem determined the further development of combinatorics and probability theory as a science.

Frequency stability

Before we move on to studying the elements of combinatorics, we give a clear example that leads to certain thoughts - tossing bones. Consider one bone for simplicity. This is a hex cube, each side of which is numbered. If we conduct a series of experiments from n throws and put that ₁ is the number of drops of the face with number 1, ₂ with number 2, etc., it turns out that with an increase in the number of throws n, the frequency ₁ / n, ₂ / n, ..., ₆ / n, which at the beginning of the experiment seem random, acquire quite definite values. And for a well-balanced dice, the frequency of loss of each face will be equal with great accuracy.

Another example is the coin experiment. Thus, the scientist Pearson, having spent 24,000 coin flips, came to the conclusion that the frequency of the loss of one of the sides of the coin approaches 0.5, the more accurately, the more throws are made. Thus, he got a probability of 0.5005 for the emblem to fall out. This principle of frequency stability is also one of the foundations of the theory.

Historical note

Probability theory and combinatorics were most actively developed in the 20th century. And a huge contribution to this matter was made by Russian and Soviet mathematicians. Among them, for example, Kolmogorov, Chebyshev, Lyapunov, Markov. They significantly expanded the field of applicability, investigated and described the law of large numbers, the central limit theorem, and the axiomatics of probability theory. All this has become the basis for a whole science. Today it is difficult to overestimate the importance of elements of combinatorics and probability theory in physics, chemistry, biology, and many other fields, especially in their practical field.

Examples of combinatorics problems

Combinatorics is an estimate of the number of possible combinations made up of any set of elements, subject to certain conditions. For this, formulas were derived in combinatorics that make it possible to conveniently and quickly solve the required problem. But before showing these formulas, we will consider examples of questions that led to their appearance.

Problem 1. 16 teams take part in the playoffs of the World Cup stage. How many ways will they be able to distribute among themselves places? For example:

• (3, 1, 2, 4..16) - in the first place the team is at number 3, in the second - at number 1, etc.
• (16, 1, 2, 3, 4..15) - in the first place the team at number 16, ...
• (1..7, 9, 8, 10..16) - in the first places teams 1, 2, 3, ...

These are all examples of options. The obvious solution to this problem is to write out all possible combinations. However, it will take a lot of time, because their number will be the same as there are ways to rearrange 16 digits in places. Elements of combinatorics, examples like this, are solved in two ways.

Task 2. Among these 16 teams, only three can get a prize. How many medalists will be determined? In this case, the task differs from the previous one in that it does not matter at all what the standings look like and the order of the finalists. Indeed, among all the teams it is important to find only three who will win prizes among themselves. That is, sets can look like {3, 2, 1}, {5, 12, 7}, {8, 1, 2}, etc.

Task 3. And what if we raise the question a little differently: how many options are there for distributing medals to 16 teams participating in the playoffs? The difference with the second task may not be entirely obvious. However, now we have to choose not only three teams that will compete for prizes, but to determine which one will take which place. In other words, if for the second task, for example, the sets (5, 12, 1) and (1, 12, 5) were equivalent, now the order of the teams has weight. Indeed, in the first case, the team will receive gold at number 5, and in the second - at number 1.

Below we will consider which of the sections of combinatorics each of the problems relates to and in detail we will describe how to solve them. In the meantime, you can try to reflect on the questions posed by yourself.

Combinations or combinations without regard to order

A combination of all n-pieces of elements sets of k-pieces of elements, where k can take values ​​from 1 to n, is any combination of k elements selected from n pieces of elements. In this case, two sets will be considered different if one of them contains an element from n but is not included in the second. In other words, they differ only in composition. In elements of combinatorics, combinations are an introductory basis.

The number of combinations of n through k is denoted by C _n ^k , from the English word Combination. The statements C _n ¹ = n and C _n ⁿ = 1 are quite obvious. That is, there are options to choose from n elements one total of n pieces (as many as the elements themselves) and, accordingly, you can compose a set of n elements in the amount of n pieces only one.

So, for example, consider a set of three elements {e, 2, a}. For him, C ₃ ¹ = 3: {a}, {2}, {e}; C ₃ ² = 3: {e, 2}, {2, a}, {a, e}; and finally, C ₃ ³ = 1: {e, 2, a}. Recall that in this case, the order of the elements in the sets does not matter.

And what will happen if we try to figure out what is C _n ⁰ ?

Placements or combination in order

In combinatorics, placement is easy enough to understand. These are the same combinations, only now not only the composition, but also the order in each combination is taken into account. So, placing from n pieces of elements combinations (sets) of k pieces, where k can take values ​​from 1 to n, is called any combination consisting of k-pieces of elements from n arranged in a certain order. In other words, the two placement combinations are different in three cases:

• they differ in composition;
• they differ in the order of the elements in the sets;
• they differ in composition and order.

The number of placement of n by k is denoted by A _n ^k , from the word Arrangements. Consider all placement options for the three-element set {x, e, z}:

• A ₃ ¹ = 3: (x), (e), (z);
• A ₃ ² = 6: (x, e), (e, x), (x, z), (z, x), (e, z), (z, e);
• A ₃ ³ = 6: (x, e, z), (e, x, z), (z, x, e), (x, z, e), (e, z, x), (z, e , x).

The last line of A ₃ ³ deserves special attention. This is nothing but a permutation.

Permutations

As already mentioned above, permutations are quite simple in meaning. This is just a placement of n elements of n pieces. That is, we are interested in all combinations that differ in the sequence of elements, and only them. Or, which is the same, A _n ⁿ . The number of permutations is indicated by the letter P, from the word Permutation. In combinatorics, permutations are provided with only one index. So, for example, P ₃ = 6, as we found in the previous chapter.

Combinations through set theory

As you know, in mathematics it is difficult to communicate with uncertain entities: a set, a combination, etc. It would be nice to mathematically determine exactly what we are dealing with. And here the language of set theory fits perfectly. We define what constitute elements of combinatorics in the language of set theory.

Let some n-set A = {a ₁ , a ₂ , ..., a _n } be given, it contains n pieces of elements. It is easy to determine from an n-set its k-subset, where k is less than or equal to n. Then combinations of n over k will mean all subsets k of the set n. Thanks to this definition, one can easily answer the question of what the record C _n ^{0 will be} . Since in set theory an empty set is contained in any subset, then C _n ⁰ = 1. In other words, it will be a combination that contains one element - an empty set.

Thus, studying the set of three elements {c, b, a}, we get that C _n ⁰ = 1: {}; C ₃ ¹ = 3: {a}, {b}, {c}; C ₃ ² = 3: {a, b}, {b, c}, {c, a}; and finally C ₃ ³ = 1: {a, b, c}.

Accordingly, they will be similarly determined in the combinatorics of placement. The only difference being that one needs to distinguish ordered k-subsets from an n-set. And all subsets will also contain an empty set. It is conditionally considered an ordered combination of n elements of 0 pieces, i.e. A _n ⁰ = 1.

Thanks to the transition from obscure constructions to clearly defined objects in set theory, it turned out to be a rather trivial answer to one of the questions that arose. This is all the math.

Addition principle

This is one of the two basic rules of combinatorics. Suppose that in Moscow from point A to point B you can get 5 buses, 3 trams and 1 metro train. It will turn out, all the ways to get to the right place 5 + 3 + 1 = 9. This is the combinatorial principle of addition.

If, when considering a problem, it can be solved in n ways, while the first of these methods can be applied m ₁ time, the second - m ₂ times, etc., then this problem will be solved m ₁ + m ₂ + ... + m _n ways.

Multiplication principle

Now imagine that you need to get from Moscow to Kazan through Nizhny Novgorod. At the same time, Moscow and Nizhny Novgorod are connected by 2 trains, 3 flights and 10 cars, and Nizhny Novgorod and Kazan - by 1 train, 1 flight and 2 buses. By the principle of addition, we come to the fact that from Moscow to Nizhny Novgorod can be reached in 13 ways, and from there to Kazan - 4. The total number of routes that connects Moscow and Kazan will be: 13 * 4 = 52.

Thus, the combinatorial principle of multiplication reads as follows. If the problem is solved in n pieces of consecutive stages, with m ₁ methods at the first stage, m ₂ at the second stage, etc., while these consecutive stages are independent, that is, the number of methods does not change depending on how the solution in the previous steps, then the problem is solved m ₁ * m ₂ * ... * m _{n in} ways. Two solutions are considered different if there is at least one difference at the stages.

Basic formulas

We show the formulas immediately, then briefly describe where they come from, and solve the examples described earlier using these combinatorics elements.

• Placements. We start with this formula because others are derived from it.

• Permutations.

• Combinations.

The proof of these formulas is based on the principles of combinatorics - the rules of addition and multiplication. Consider the first formula for finding the number of placements. At the first stage, we take one of the n-pieces of elements and for this we have n ways. At the second stage, we have n-1 elements and, accordingly, n-1 methods of choice. In the third - n-3 ways. We continue to do this until there are k pieces of elements in our set. By the rule of multiplication, we will come to the conclusion that in all ways we can choose k elements with n (n-1) (n-2) (n-3) (n-4) (n-5) ... (n-k + 1). The second formula for finding permutations is a simple consequence of the first due to the substitution m = k. The last formula, which gives the number of combinations, is obtained from the considerations that when we search for combinations of n elements of k pieces, each time we come to view k! placements from n to k (they are obtained as permutations of k elements). Therefore, we have A _n ^k = C _n ^k * k !.

Now we can return to the tasks that were announced earlier, and estimate the number of options. For the first task we need to use the permutation formula, i.e., P ₁₆ = 16! = 20 922 789 888 000 ≈ 21 * 10 ¹² possible options for how 16 teams can be placed in the standings. The second problem concerns combinations, which means that C ₁₆ ³ = 16! / [3! (16-3)!] = 560 prize winners. Finally, the last problem concerns placements, that is, A ₁₆ ³ = 16! / (16-3)! = 3360 options, as 3 teams out of 16 can split the prizes.

Given the above, it is unnecessary to talk about how large numbers combinatorics works.