This article will focus on a special section of mathematics called combinatorics. Formulas, rules, examples of problem solving - all this you can find here by reading the article to the very end.
So, what is this section? Combinatorics deals with the issue of counting any objects. But in this case, the objects are not plums, pears or apples, but something else. Combinatorics helps us find the probability of an event. For example, when playing cards, what is the probability that the opponent has a trump card? Or such an example - what is the probability that you will get exactly white from a bag of twenty balls? It is for this kind of tasks that we need to know at least the basics of this section of mathematics.
Combinatorial configurations
Considering the question of the basic concepts and formulas of combinatorics, we cannot but pay attention to combinatorial configurations. They are used not only for formulation, but also for solving various combinatorial problems. Examples of such models are:
- placement;
- permutation;
- combination;
- number composition;
- split number.
We will talk about the first three in more detail later, but we will pay attention to composition and splitting in this section. When they talk about the composition of a certain number (say, a), they mean the representation of the number a as an ordered sum of some positive numbers. And a split is an unordered sum.
Sections
Before we go directly to the formulas of combinatorics and the consideration of problems, it is worth paying attention to the fact that combinatorics, like other sections of mathematics, has its own subsections. These include:
- enumerative;
- structural;
- extreme;
- Ramsey theory;
- probabilistic;
- topological;
- infinite.
In the first case, we are talking about computational combinatorics, the problems consider enumeration or counting of different configurations that are formed by elements of sets. As a rule, some restrictions are imposed on these sets (distinctness, indistinguishability, the possibility of repetition, and so on). And the number of these configurations is calculated using the rule of addition or multiplication, which we will talk about a little later. Structural combinatorics include the theories of graphs and matroids. An example of an extremal combinatorics problem is what is the largest dimension of a graph that satisfies the following properties… In the fourth paragraph, we mentioned the Ramsey theory, which studies the presence of regular structures in random configurations. Probabilisticcombinatorics is able to answer the question - what is the probability that a given set has a certain property. As you might guess, topological combinatorics applies methods in topology. And finally, the seventh point - infinitary combinatorics studies the application of combinatorics methods to infinite sets.
Addition rule
Among the formulas of combinatorics, one can find quite simple ones, with which we have been familiar for a long time. An example is the sum rule. Suppose we are given two actions (C and E), if they are mutually exclusive, action C can be done in several ways (for example, a), and action E can be done in b-ways, then any of them (C or E) can be done in a + b ways.
In theory, this is quite difficult to understand, we will try to convey the whole point with a simple example. Let's take the average number of students in one class - let's say it's twenty-five. Among them are fifteen girls and ten boys. One attendant is assigned to the class daily. How many ways are there to assign a class attendant today? The solution to the problem is quite simple, we will resort to the addition rule. The text of the task does not say that only boys or only girls can be on duty. Therefore, it could be any of the fifteen girls or any of the ten boys. Applying the sum rule, we get a fairly simple example that a primary school student can easily cope with: 15 + 10. Having calculated, we get the answer: twenty-five. That is, there are only twenty-five waysassign a duty class for today.
Multiplication rule
The rule of multiplication also belongs to the basic formulas of combinatorics. Let's start with theory. Suppose we need to perform several actions (a): the first action is performed in 1 ways, the second - in 2 ways, the third - in 3 ways, and so on until the last a-action is performed in sa ways. Then all these actions (of which we have a total) can be performed in N ways. How to calculate the unknown N? The formula will help us with this: N \u003d c1c2c3…ca.
Again, nothing is clear in theory, let's move on to a simple example of applying the multiplication rule. Let's take the same class of twenty-five people, in which fifteen girls and ten boys study. Only this time we need to choose two attendants. They can be either only boys or girls, or a boy with a girl. We turn to the elementary solution of the problem. We choose the first attendant, as we decided in the last paragraph, we get twenty-five possible options. The second person on duty can be any of the remaining people. We had twenty-five students, we chose one, which means that any of the remaining twenty-four people can be the second on duty. Finally, we apply the multiplication rule and find that the two attendants can be chosen in six hundred ways. We got this number by multiplying twenty-five and twenty-four.
Swap
Now we will consider one more combinatorics formula. In this section of the article, weLet's talk about permutations. Consider the problem immediately with an example. Let's take billiard balls, we have n-th number of them. We need to calculate: how many options there are to arrange them in a row, that is, to make an ordered set.
Let's start, if we don't have balls, then we also have zero placement options. And if we have one ball, then the arrangement is also the same (mathematically, this can be written as follows: Р1=1). Two balls can be arranged in two different ways: 1, 2 and 2, 1. Therefore, Р2=2. Three balls can be arranged in six ways (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. And if there are not three such balls, but ten or fifteen? To list all the possible options is very long, then combinatorics comes to our aid. The permutation formula will help us find the answer to our question. Pn=nP(n-1). If we try to simplify the formula, we get: Pn=n (n - 1) … 21. And this is the product of the first natural numbers. Such a number is called a factorial, and is denoted as n!
Let's consider the problem. The leader every morning builds his detachment in a line (twenty people). There are three best friends in the detachment - Kostya, Sasha and Lesha. What is the probability that they will be next to each other? To find the answer to the question, you need to divide the probability of a “good” outcome by the total number of outcomes. The total number of permutations is 20!=2.5 quintillion. How to count the number of "good" outcomes? Suppose that Kostya, Sasha and Lesha are one superman. Then weWe have only eighteen subjects. The number of permutations in this case is 18=6.5 quadrillion. With all this, Kostya, Sasha and Lesha can arbitrarily move among themselves in their indivisible triple, and this is 3 more!=6 options. So we have 18 “good” constellations in total!3! We just have to find the desired probability: (18!3!) / 20! Which is approximately 0.016. If converted to a percentage, it turns out to be only 1.6%.
Accommodation
Now we will consider another very important and necessary combinatorics formula. Accommodation is our next issue, which we suggest you consider in this section of the article. We're going to get more complicated. Let's assume that we want to consider possible permutations, only not from the whole set (n), but from a smaller one (m). That is, we consider permutations of n items by m.
The basic formulas of combinatorics should not just be memorized, but understood. Even despite the fact that they become more complicated, since we have not one parameter, but two. Suppose that m \u003d 1, then A \u003d 1, m \u003d 2, then A \u003d n(n - 1). If we further simplify the formula and switch to notation using factorials, we get a quite concise formula: A \u003d n! / (n - m)!
Combination
We have considered almost all the basic formulas of combinatorics with examples. Now let's move on to the final stage of considering the basic course of combinatorics - getting to know the combination. Now we will choose m items from the n we have, while we will choose all of them in all possible ways. How then is this different from accommodation? We will notconsider order. This unordered set will be a combination.
Immediately introduce the notation: C. We take placements of m balls out of n. We stop paying attention to order and get repeating combinations. To get the number of combinations, we need to divide the number of placements by m! (m factorial). That is, C \u003d A / m! Thus, there are a few ways to choose from n balls, approximately equal to how many to choose almost everything. There is a logical expression for this: choosing a little is the same as throwing away almost everything. It is also important to mention at this point that the maximum number of combinations can be achieved when trying to select half of the items.
How to choose a formula to solve a problem?
We have examined in detail the basic formulas of combinatorics: placement, permutation and combination. Now our task is to facilitate the choice of the necessary formula for solving the problem in combinatorics. You can use the following rather simple scheme:
- Ask yourself: is the order of the elements taken into account in the text of the problem?
- If the answer is no, then use the combination formula (C=n! / (m!(n - m)!)).
- If the answer is no, then you need to answer one more question: are all the elements included in the combination?
- If the answer is yes, then use the permutation formula (P=n!).
- If the answer is no, then use the placement formula (A=n! / (n - m)!).
Example
We have considered the elements of combinatorics, formulas and some other issues. Now let's move on toconsidering a real problem. Imagine that you have a kiwi, an orange and a banana in front of you.
Question one: in how many ways can they be rearranged? To do this, we use the permutation formula: P=3!=6 ways.
Question two: in how many ways can one fruit be chosen? This is obvious, we have only three options - choose kiwi, orange or banana, but we apply the combination formula: C \u003d 3! / (2!1!)=3.
Question three: in how many ways can two fruits be chosen? What options do we have? Kiwi and orange; kiwi and banana; orange and banana. That is, three options, but this is easy to check using the combination formula: C \u003d 3! / (1!2!)=3
Question four: in how many ways can three fruits be chosen? As you can see, there is only one way to choose three fruits: take a kiwi, an orange and a banana. C=3! / (0!3!)=1.
Question five: how many ways can you choose at least one fruit? This condition implies that we can take one, two or all three fruits. Therefore, we add C1 + C2 + C3=3 + 3 + 1=7. That is, we have seven ways to take at least one piece of fruit from the table.
