This article will focus on a special section of mathematics called combinatorics. Formulas, rules, examples of solving problems - 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 likelihood of an event. For example, when playing cards - what is the likelihood that the opponent has a trump card? Or such an example - what is the likelihood that you will get exactly white from a bag with twenty balls? It is for such problems that we need to know at least the basics of this section of mathematics.
Combinatorial configurations
Considering the question of 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:
- accommodation;
- rearrangement;
- combination;
- number composition;
- splitting a number.
We will talk about the first three in more detail below, but we will pay attention to composition and splitting in this section. When one speaks about the composition of a certain number (say, a), they mean representing the number a in the form of an ordered sum of certain positive numbers. A partition 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 branches of mathematics, has its own subsections. These include:
- enumerative;
- structural;
- extreme;
- Ramsey theory;
- probabilistic;
- topological;
- infinite.
In the first case, it is a calculating combinatorics, tasks consider the enumeration or calculation of different configurations, which are formed by elements of sets. As a rule, any restrictions are imposed on these sets (distinguishability, 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 theories of graphs and matroids. An example of an extreme combinatorics problem is what is the largest dimension of a graph that satisfies the following properties ... In the fourth paragraph, we mentioned Ramsey's theory, which studies the presence of regular structures in random configurations. Probabilistic combinatorics are 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 - infinite combinatorics studies the application of combinatorics methods to infinite sets.
Addition rule
Among the formulas of combinatorics can be found quite simple, with which we have long been familiar. An example is the sum rule. Suppose we are given two actions (C and E), if they are mutually exclusive, action C is feasible in several ways (for example a), and action E is feasible in b-ways, then any of them (C or E) can be performed in a + b ways .
In theory, this is 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 — for example, twenty-five. Among them are fifteen girls and ten boys. Every day, one attendant is assigned in the classroom. How many ways are there to appoint a class duty officer today? The solution to the problem is quite simple, we will resort to the addition rule. The task text does not say that only boys or only girls can be on duty. Therefore, it may be any of the fifteen girls or any of ten boys. Applying the rule of sum, we get a fairly simple example, which a primary school student can easily cope with: 15 + 10. Counting, we get the answer: twenty-five. That is, there are only twenty-five ways to appoint a duty class for today.
Multiplication rule
The basic formula for combinatorics is the rule of multiplication. Let's start with the theory. Suppose we need to perform several actions (a): the first action is performed with 1 methods, the second with 2 methods, the third with 3 methods and so on until the last a-action performed by these methods. Then all these actions (of which we have a total) can be performed in N ways. How to calculate unknown N? The formula will help us with this: N = c1 * c2 * c3 * ... * sa.
Again, in theory, nothing is clear, we proceed to consider a simple example on the application of the multiplication rule. Let us take the same class of twenty-five in which fifteen girls and ten boys study. Only this time we need to choose two attendants. They can be as soon as boys or girls, and a boy with a girl. We pass to the elementary solution of the problem. We select 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, one of whom we chose, so the second person on duty could be any of the remaining twenty-four people. Finally, we apply the multiplication rule and we find that two attendants can be chosen in six hundred ways. We got this number by multiplying twenty-five and twenty-four.
Rearrangement
Now we will consider another formula for combinatorics. In this section of the article we will talk about permutations. We offer to consider the problem immediately with an example. Take billiard balls, we have their nth number. We need to calculate: how many options are there to put them in a row, that is, to make an ordered set.
Let's start, if we do not have balls, then we also have zero placement options. And if we have one ball, then the arrangement is also one (mathematically this can be written as follows: P1 = 1). Two balls can be arranged in two different ways: 1.2 and 2.1. Therefore, P2 = 2. Three balls can already be arranged in six ways (P3 = 6): 1,2,3; 1,3,2; 2.1.3; 2,3,1; 3.2.1; 3,1,2. And if such balls are not three, but ten or fifteen? Enumerate all the possible options for a very long time, then combinatorics come to our aid. The permutation formula will help us find the answer to our question. Pn = n * P (n-1). If we try to simplify the formula, we get: Pn = n * (n - 1) * ... * 2 * 1. And this is the product of the first natural numbers. Such a number is called a factorial, and is denoted by n!
Consider the problem. The counselor every morning builds his squad in a line (twenty people). There are three best friends in the squad - Kostya, Sasha and Lesha. What is the likelihood that they will stand nearby? 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 calculate the number of “good” outcomes? Suppose that Kostya, Sasha and Lesha are one superman. Then we have a total of 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 three, and this is 3 more! = 6 options. So we have 18 “good” constellations! * 3! We can only find the desired probability: (18! * 3!) / 20! Which equals approximately 0.016. If translated into percentages, then it turns out only 1.6%.
Accommodation
Now we will consider another very important and necessary formula for combinatorics. Accommodation is our next question, which we suggest you consider in this section of the article. We are going to complicate. Suppose we want to consider possible permutations, not only from the whole set (n), but from the smaller (m). That is, we consider permutations of n objects in m.
The basic formulas of combinatorics should not just be memorized, but understand them. Even despite the fact that they are becoming more complicated, since we have not one parameter, but two. Suppose that m = 1, then A = 1, m = 2, then A = n * (n - 1). If we further simplify the formula and go to the record using factorials, we get a completely concise formula: A = n! / (n - m)!
Combination
We examined almost all the basic combinatorics formulas with examples. Now let's move on to the final stage of considering the basic course of combinatorics - familiarity with the combination. Now we will choose m items from n that we have, while we will choose all in all possible ways. How then is this different from accommodation? We will not take into account the order. This unordered set will be a combination.
Immediately introduce the notation: C. Take the placement of m balls from n. We stop paying attention to order and get repeated combinations. To get the number of combinations we need to divide the number of placements by m! (m factorial). That is, C = A / m! Thus, the ways to choose a little from n balls are approximately as many as to choose almost everything. There is a logical expression for this: choosing a little bit is the same as throwing out almost everything. Even in this paragraph, it is important to mention that the maximum number of combinations can be achieved when trying to choose half of the items.
How to choose a formula to solve the problem?
We examined in detail the basic formulas of combinatorics: placement, rearrangement, and combination. Now our task is to facilitate the selection of the necessary formula for solving the combinatorics problem. You can use the following fairly simple scheme:
- Ask yourself a question: is the arrangement of elements taken into account in the text of the task?
- If the answer is no, then use the combination formula (C = n! / (M! * (N - m)!)).
- If the answer is no, then one more question must be answered: 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 examined the elements of combinatorics, formulas and some other questions. Now we turn to the consideration of the real problem. Imagine kiwi, orange and 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: how many ways can I choose one fruit? This is obvious, we have only three options - choose a kiwi, orange or banana, but apply the combination formula: C = 3! / (2! * 1!) = 3.
Question three: how many ways can I choose two fruits? What options do we have in general? Kiwi and orange; kiwi and banana; orange and banana. That is, there are three options, but it is easy to verify using the combination formula: C = 3! / (1! * 2!) = 3
Question four: how many ways can I choose three fruits? As you can see, you can choose three fruits in one single way: take kiwi, orange and banana. C = 3! / (0! * 3!) = 1.
Question five: in 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 fruit from the table.