Combinatorics - basic concepts and formulas with examples. Combinatorics

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 orderly, otherwise - disordered.

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.Because the 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: adding two adjacent numbers, we get the number below 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 from 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 of 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

Let us consider the problem of counting the number of samples from a given set in general form. Let there be some set N, consisting of n elements. Any subset consisting of m elements can be considered without taking into account their order, or taking it into account, i.e. when changing the order, move to another m– sampling.

Let us formulate the following definitions:

Placements without repetition

Placement without repetition ofn elements bym Ncontainingmvarious elements.

From the definition it follows that the two arrangements differ from each other, both in their elements and in their order, even if the elements are the same.

Theorem 3. The number of placements without repetition is equal to the product m factors, the largest of which is the number n . Write down:

Permutations without repetition

Permutations fromn elements are called different orderings of the setN.

From this definition it follows that the two permutations differ only in the order of the elements and they can be considered as a special case of placements.

Theorem 4. The number of different permutations without repetition is calculated by the formula

Combinations without repetitions

A combination without repetition ofn elements bym any unordered subset of a set is calledNcontainingm various elements.

From the definition it follows that the two combinations differ only in elements; the order is not important.

Theorem 5. The number of combinations without repetitions is calculated using one of the following formulas:

Example 1. There are 5 chairs in the room. In how many ways can you place them on them?

a) 7 people; b) 5 people; c) 3 people?

Solution: a) First of all, you need to select 5 people out of 7 to sit on chairs. It can be done
way. With each choice of a specific five, you can produce
rearrangements. According to the multiplication theorem, the required number of landing methods is equal.

Comment: The problem can be solved using only the product theorem, reasoning as follows: for seating on the 1st chair there are 7 options, on the 2nd chair there are 6 options, on the 3rd -5, on the 4th -4 and on 5- th -3. Then the number of ways to seat 7 people on 5 chairs is . The solutions by both methods are consistent, since

b) The solution is obvious -

V) - number of elections of occupied chairs.

- the number of seats for three people on three selected chairs.

The total number of elections is .

It's not hard to check the formulas
;

;

The number of all subsets of a set consisting of n elements.

Repeat placements

By placing with repetition fromn elements bym every ordered subset of a set is calledN, consisting ofm elements so that any element can be included in this subset from 1 tomtimes, or be absent from it altogether.

The number of placements with repetition is denoted by and calculated using the formula, which is a consequence of the multiplication theorem:

Example 2. Let N = (a, b, c) be a set of three letters. Let us call any set of letters included in this set a word. Let's find the number of words of length 2 that can be made from these letters:
.

Comment: Obviously, placements with repetition can also be considered when
.

Example 3. You need to use the letters (a, b) to create all possible words of length 3. In how many ways can this be done?

Answer:

Combinatorics is a branch of mathematics. The basic concepts and formulas of combinatorics as a science are applied in all spheres of life.

It is not surprising that it is included in the 11th grade program, as well as in the entrance examinations in many universities in the Russian Federation. Its foundations lie in the applied arts of many spheres of human activity.

Its history goes back more than 6 centuries. The first combinatorial problems appeared in the works of philosophers and mathematicians of the Middle Ages.

Representatives of that scientific world tried to find methods for solving such problems, their basic rules and concepts, and establish unique formulas and equations for those who had not yet encountered them. Such information in our time is called information “for dummies.”

Let's try to understand the aspects of this field of science: what are the elements, properties, rules, methods and its main application in our lives? Of course, it is impossible to cover the entire area in one article. Therefore, all the most basic things will be presented below.

What is combinatorics in mathematics

The essence of this term is given by books of past years: this branch of mathematics dealing with operations on many elements.

On the Internet there are textbooks on computer science and mathematics for children and schoolchildren, collections of materials and problems for beginners, where “entertaining” combinatorics is explained in an accessible way. We need to firmly figure out how to solve such problems.

In elementary grades, problems on this topic are solved in additional clubs, and in schools with in-depth study of mathematics - in main lessons. In addition, combinatorics problems are included in olympiads at all levels.

Basic Concepts

There are several of them:

1. Element– any object or phenomenon included in the desired set.
2. Combination– subsets located in an arbitrary order in the original set.
3. Rearrangement– elements in a set are in a strictly defined order.
4. Accommodation– ordered subsets in the original set.

Product rule

It is one of the basic rules when solving such problems and sounds like this:

When selecting element A fromnmethods and selection of element B frommIn some ways it is true that it is possible to choose a pair A and B at the same timen* mways.

Let's look at specific examples.

Task No. 1.

The box contains 2 balls and 6 jump ropes. How many ways are there to get 1 ball and 1 jump rope?

The answer is simple: 2 * 6 = 12.

Task No. 2.

There are 1 cube, 2 balls, 3 flowers and 4 candies. In how many ways can you draw a cube, a ball, a flower and a candy?

The solution is similar: 1 * 2 * 3 * 4 = 24.

Moreover, the left side can be written much simpler: 4!

! in this case it is not a punctuation mark, but a factorial. Using it, you can calculate more complex options and solve difficult problems (there are different formulas, but more on that later).

Task No. 3.

How many two-digit numbers can be made from 2 digits?

Answer: 2! = 2.

Task No. 4.

How many ten-digit numbers can be made from 10 digits?

Sum Rule

This is also a basic rule of combinatorics.

If A can be chosenntimes, and B -mtimes, then A or B can be chosen (n+ m) once.

Task No. 5.

The box contains 5 red, 3 yellow, 7 green, 9 black pencils. How many ways are there to pull out any 1 pencil?

Answer: 5 + 3 + 7 + 9 = 24.

Combinations with and without repetitions

This term refers to combinations in any order from a set of n by m elements.

The number of combinations is equal to the number of such combinations.

Task No. 6.

The box contains 4 different fruits. In how many ways can you get 2 different fruits at the same time?

The solution is simple:

Where is 4! – a combination of 4 elements.

With repetitions a little more complicated, combinations are calculated using the following formula:

Task No. 7.

Let's take the same case, but on the condition that one fruit is returned to the box.

In this case:

Placements with and without repetitions

This definition means a set of m elements from a set of n elements.

Task No. 8.

From 3 digits, you need to choose 2 to get different two-digit numbers. How many options?

The answer is simple:

But what about with repetitions? Here, each element can be placed several times! In this case, the general formula will look like this:

Task No. 9.

From 12 letters of the Latin alphabet and 10 digits of the natural series, you need to find all the options for composing the automobile region code.

Permutations with and without repetitions

This term refers to all possible combinations of an n element set.

Task No. 10.

How many possible 5-digit numbers can be made from 5 digits? What about six digits from 6 digits? Seven digits out of 7 digits?

The solutions, according to the above formula, are as follows:

But what about with repetitions? If in such a set there are elements of equal importance, then there will be fewer permutations!

Task No. 11.

The box contains 3 identical pencils and one pen. How many permutations can you make?

The answer is simple: 4! / (3! * 1!) = 4.

Combinatorial problems with solutions

Examples of all possible types of problems with solutions were given above. Here we will try to deal with more complex cases encountered in our lives.

Types of tasks	What you need to find	Solution methods
Magic square	A figure in which the sum of the numbers in the rows and columns must be the same (its variety is the Latin square).	Recurrence relations. A similar problem is solved, but with a much smaller set of elements according to known rules and formulas.
Placement problem	A standard production task (for example, in patchwork technology) is to find possible ways to decompose quantities of products into cells in a certain order.	Inclusions and exclusions. As a rule, it is used when proving various expressions.
Problems about traders	The point is to find all possible ways for people to get from point A to point B.	Trajectories. This type of problem is characterized by a geometric construction of possible solutions.

Conclusion

It is worth studying this science, since in the age of rapid modernization of technology, specialists will be required who can provide various solutions to certain practical problems.

Abstract on the topic:

Completed by 10th grade student “B”

secondary school No. 53

Glukhov Mikhail Alexandrovich

Naberezhnye Chelny

2002
Content

From the history of combinatorics_______________________________________________	3
Sum rule_________________________________________________________	4
	-
Product rule_____________________________________________	4
Examples of tasks__________________________________________________________	-
Intersecting sets_______________________________________________	5
Examples of tasks__________________________________________________________	-
Euler circles______________________________________________________________	-
Placements without repetition_____________________________________________	6
Examples of tasks__________________________________________________________	-
Permutations without repetitions________________________________________________	7
Examples of tasks__________________________________________________________	-
Combinations without repetitions_______________________________________________	8
Examples of tasks__________________________________________________________	-
Placements and combinations without repetition______________________________	9
Examples of tasks__________________________________________________________	-
Permutations with repetitions________________________________________________	9
Examples of tasks__________________________________________________________	-
Problems for independent solution________________________________	10
Bibliography___________________________________	11

From the history of combinatorics

Combinatorics deals with various types of connections that can be formed from elements of a finite set. Some elements of combinatorics were known in India as early as the 2nd century. BC e. The Nydians knew how to calculate numbers, which are now called “combinations”. In the 12th century. Bhaskara calculated some types of combinations and permutations. It is believed that Indian scientists studied the compounds in connection with their use in poetics, the study of the structure of verse and poetic works. For example, in connection with the calculation of possible combinations of stressed (long) and unstressed (short) syllables of a foot of n syllables. As a scientific discipline, combinatorics was formed in the 17th century. In the book “The Theory and Practice of Arithmetic” (1656), the French author A. also devotes an entire chapter to combinations and permutations.
B. Pascal in his “Treatise on the Arithmetic Triangle” and in his “Treatise on Numerical Orders” (1665) outlined the doctrine of binomial coefficients. P. Fermat knew about the connections between mathematical squares and figured numbers with the theory of compounds. The term “combinatorics” began to be used after Leibniz published his work “Discourse on the Art of Combination” in 1665, which for the first time provided a scientific basis for the theory of combinations and permutations. J. Bernoulli first studied placements in the second part of his book “Ars conjectandi” (the art of prediction) in 1713. Modern symbolism of combinations was proposed by various authors of educational manuals only in the 19th century.

The whole variety of combinatorial formulas can be derived from two basic statements concerning finite sets - the sum rule and the product rule.

Sum Rule

If finite sets do not intersect, then the number of elements of X U Y (or) is equal to the sum of the number of elements of set X and the number of elements of set Y.

That is, if there are X books on the first shelf, and Y books on the second, then you can select a book from the first or second shelf in X+Y ways.

Sample problems

The student must complete practical work in mathematics. He was offered a choice of 17 topics in algebra and 13 topics in geometry. In how many ways can he choose one topic for practical work?

Solution: X=17, Y=13

According to the sum rule X U Y=17+13=30 topics.

There are 5 tickets for the cash lottery, 6 tickets for the sports lottery and 10 tickets for the car lottery. In how many ways can you choose one ticket from a sports lotto or auto lottery?

Solution: Since the cash and clothing lottery is not involved in the choice, there are only 6 + 10 = 16 options.

Product rule

If element X can be chosen in k ways, and element Y in m ways, then the pair (X,Y) can be chosen in k*m ways.

That is, if there are 5 books on the first shelf and 10 on the second, then you can choose one book from the first shelf and one from the second in 5 * 10 = 50 ways.

Sample problems

A bookbinder must bind 12 different books in red, green and brown bindings. In how many ways can he do this?

Solution: There are 12 books and 3 colors, which means that according to the product rule, 12 * 3 = 36 binding options are possible.

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

Solution: In such numbers, the last digit will be the same as the first, and the penultimate digit will be the same as the second. The third digit will be anything. This can be represented in the form XYZYX, where Y and Z are any numbers, and X is not zero. This means that according to the product rule, the number of digits that can be read equally both from left to right and from right to left is 9*10*10=900 options.

Intersecting sets

But it happens that the sets X and Y intersect, then they use the formula

, where X and Y are sets, and is the area of ​​intersection. Sample problems

20 people know English and 10 know German, of which 5 know both English and German. How many people are there in total?

Answer: 10+20-5=25 people.

Euler circles are also often used to visually solve the problem. For example:

Out of 100 tourists going on a trip abroad, 30 people speak German, 28 - English, 42 - French. 8 people speak English and German at the same time, 10 - English and French, 5 - German and French, 3 - all three languages. tourists don’t speak any language?

Solution: Let us express the condition of this problem graphically. Let us denote by a circle those who know English, another circle by those who know French, and a third circle by those who know German.

Three tourists speak all three languages, which means that in the general part of the circles we enter the number 3. 10 people speak English and French, and 3 of them also speak German. Consequently, 10-3=7 people speak only English and French.

Similarly, we find that 8-3 = 5 people speak only English and German, and 5-3 = 2 tourists speak German and French. We enter this data in the appropriate parts.

Let us now determine how many people speak only one of the listed languages. 30 people know German, but 5+3+2=10 of them speak other languages, therefore, only 20 people know German. Similarly, we find that 13 people speak English alone, and 30 people speak French alone.

According to the problem, there are only 100 tourists. 20+13+30+5+7+2+3=80 tourists know at least one language, therefore, 20 people do not speak any of these languages.

Placements without repetition.

How many phone numbers can be made from 6 digits each, so that all the digits are different?

This is an example of a placement problem without repetition. There are 10 numbers of 6 placed here. And options in which the same numbers are in different orders are considered different.

If an X-set consisting of n elements, m≤n, then the arrangement without repetition of n elements of the set X into m is called an ordered set X containing m elements. An ordered set X containing m elements is called.

The number of all arrangements of n elements by m is denoted by

n! - n-factorial (factorial factor) is the product of numbers in the natural series from 1 to any number n Task

In how many ways can 4 boys ask four out of six girls to dance?

Solution: two boys cannot invite the same girl at the same time. And the options in which the same girls dance with different boys are considered different, therefore:

360 options possible.

Permutations without repetition

In the case of n=m (see placements without repetition) of n elements of m is called a permutation of the set x.

The number of all permutations of n elements is denoted by P n.

Valid for n=m:

Sample problems

How many different six-digit numbers can be made from the digits 0, 1, 2, 3, 4.5 if the digits are not repeated in the number?

1) Find the number of all permutations from these numbers: P 6 =6!=720

2) 0 cannot be in front of a number, so the number of permutations in which 0 is in front must be subtracted from this number. And this is P 5 =5!=120.

P 6 -P 5 =720-120=600

Naughty Monkey

Yes, clubfooted Mishka

We started playing a quartet

Stop, brothers, stop! –

Monkey shouts, - wait!

How should the music go?

After all, you’re not sitting like that...

And this way and that they changed seats - again the music doesn’t go well.

In this article we will talk about a special branch of mathematics called combinatorics. Formulas, rules, examples of problem solving - you can find all this 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 this example: what is the probability that you will get a white one from a bag of twenty marbles? It is for this kind of problem that we need to know at least the basics of this branch of mathematics.

Combinatorial configurations

Considering the issue of basic concepts and formulas of combinatorics, we cannot help but pay attention to combinatorial configurations. They are used not only to formulate, but also to solve various examples. Examples of such models are:

• accommodation;
• rearrangement;
• combination;
• number composition;
• splitting a number.

We will talk about the first three in more detail later, but we will pay attention to composition and partitioning in this section. When they talk about the composition of a certain number (for example, a), they mean representing the number a as an ordered sum of certain positive numbers. And a partition is an unordered sum.

Sections

Before we move directly to the formulas of combinatorics and 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;
• infinitary.

In the first case, we are talking about calculative 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 (distinctiveness, indistinguishability, possibility of repetition, and so on). And the number of these configurations is calculated using the rules of addition or multiplication, which we will talk about a little later. Structural combinatorics includes 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 Ramsey theory, which studies the presence of regular structures in random configurations. Probabilistic combinatorics 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 combinatorics formulas you can find quite simple ones, with which we have been familiar for quite a long time. An example is the sum rule. Suppose that we are given two actions (C and E), if they are mutually exclusive, action C can be performed in several ways (for example, a), and action E can be performed in b-ways, then any of them (C or E) can be performed in a + b ways .

In theory, this is quite difficult to understand; we will try to convey the whole point using 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 person on duty is assigned to each class every day. How many ways are there to appoint a class monitor today? The solution to the problem is quite simple; we will resort to the addition rule. The text of the problem 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 handle: 15 + 10. After counting, we get the answer: twenty-five. That is, there are only twenty-five ways to assign a class on duty for today.

Multiplication rule

The basic formulas of combinatorics also include the multiplication rule. Let's start with the theory. Let's say 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, performed in 3 ways. 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 *…* ca.

Again, nothing is clear in theory, so let’s move on to consider a simple example of applying the multiplication rule. Let's take the same class of twenty-five people, in which there are fifteen girls and ten boys. Only this time we need to choose two people on duty. They can be just boys or girls, or a boy and a girl. Let's move on to the elementary solution of the problem. We choose the first person on duty, 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 the second person on duty could be any of the remaining twenty-four people. Finally, we apply the multiplication rule and find that two officers on duty can be elected in six hundred ways. We obtained this number by multiplying twenty-five and twenty-four.

Rearrangement

Now we will look at another combinatorics formula. In this section of the article we will talk about permutations. We propose to immediately consider the problem using an example. Let's take billiard balls, we have nth number of them. We need to count how many options there are to arrange them in a row, that is, to create an ordered set.

Let's start, if we don't have balls, then we also have zero options for placement. And if we have one ball, then the arrangement is also the same (mathematically this can be written as follows: P1 = 1). The two balls can be placed in two different ways: 1,2 and 2,1. Therefore, P2 = 2. Three balls can 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. What if there are not three such balls, but ten or fifteen? It would take a very long time to list all the possible options, then combinatorics comes to our aid. The permutation formula will help us find the answer to the question that interests us. 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. This number is called factorial, and is denoted as n!

Let's consider the problem. Every morning the counselor lines up his squad (twenty people). There are three best friends in the squad - Kostya, Sasha and Lesha. What is the probability that they will stand 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? Let's assume that Kostya, Sasha and Lesha are one superman. Then we 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 three, and that’s 3 more! = 6 options. This means that we have 18 “good” arrangements in total! * 3! All we have to do is find the desired probability: (18! * 3!) / 20! Which equals approximately 0.016. If converted into percentages, it turns out to be only 1.6%.

Accommodation

Now we will look at another very important and necessary combinatorics formula. Placement is our next issue, which we invite you to consider in this section of the article. We are going for complications. Suppose we want to consider possible permutations, not from the entire set (n), but from a smaller one (m). That is, we are considering permutations of n items by m.

The basic formulas of combinatorics should not only be memorized, but understood. Even though they become 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 switch to notation using factorials, we will get a completely laconic formula: A = n! / (n - m)!

Combination

We have reviewed almost all the basic combinatorics formulas with examples. Now let's move on to the final stage of considering the basic combinatorics course - getting to know combinations. Now we will choose m items from the n we have, and we will choose everything in all possible ways. How then is this different from placement? We will not take into account the order. This unordered set will be the combination.

Let us immediately introduce the notation: C. We take the placement of m balls out of n. We stop paying attention to order and end up with repeating 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, there are only a few ways to select from n balls, which is approximately equal to the number of ways to select almost all of them. There is a logical expression for this: choosing a little is the same as throwing out 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 examined in detail the basic formulas of combinatorics: placement, permutation and combination. Now our task is to facilitate the selection of the necessary formula for solving a combinatorics problem. You can use the following fairly simple scheme:

1. Ask yourself: is the order in which the elements are placed taken into account in the text of the problem?
2. If the answer is no, then use the combination formula (C = n! / (m! * (n - m)!)).
3. If the answer is no, then another question needs to be answered: are all the elements included in the combination?
4. If the answer is yes, then use the permutation formula (P = n!).
5. If the answer is no, then use the placement formula (A = n! / (n - m)!).

Example

We looked at elements of combinatorics, formulas and some other issues. Now let's move on to consider the 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 will use the permutation formula: P = 3! = 6 ways.

Question two: in how many ways can you choose one fruit? This is obvious, we have only three options - choose kiwi, orange or banana, but let's apply the combination formula: C = 3! / (2! * 1!) = 3.

Question three: in how many ways can you choose two fruits? What options do we even have? Kiwi and orange; kiwi and banana; orange and banana. That is, there are three options, but this is easy to check using the combination formula: C = 3! / (1! * 2!) = 3

Question four: in how many ways can you choose three fruits? As you can see, there is only one way to choose three fruits: 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 means 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.