Calculator of possible combinations. Combinations without repetition: Combinatorics in MS EXCEL

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 get a completely laconic formula: A = n! / (n - m)!

Combination

We 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 every possible way. 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.

It should be noted that combinatorics is an independent branch of higher mathematics (and not part of terver) and weighty textbooks have been written on this discipline, the content of which, at times, is no easier than abstract algebra. However, a small portion of theoretical knowledge will be enough for us, and in this article I will try to analyze in an accessible form the basics of the topic with typical combinatorial problems. And many of you will help me ;-)

What are we going to do? In a narrow sense, combinatorics is the calculation of various combinations that can be made from a certain set discrete objects. Objects are understood as any isolated objects or living beings - people, animals, mushrooms, plants, insects, etc. At the same time, combinatorics does not care at all that the set consists of a plate of semolina porridge, a soldering iron and a swamp frog. It is fundamentally important that these objects can be enumerated - there are three of them (discreteness) and the important thing is that none of them are identical.

We've dealt with a lot, now about combinations. The most common types of combinations are permutations of objects, their selection from a set (combination) and distribution (placement). Let's see how this happens right now:

Permutations, combinations and placements without repetition

Don't be afraid of obscure terms, especially since some of them are really not very good. Let's start with the tail of the title - what does “ no repetitions"? This means that in this section we will consider sets that consist of various objects. For example, ... no, I won’t offer porridge with a soldering iron and a frog, it’s better to have something tastier =) Imagine that an apple, a pear and a banana have materialized on the table in front of you (if you have them, the situation can be simulated in reality). We lay out the fruits from left to right in the following order:

apple / pear / banana

Question one: In how many ways can they be rearranged?

One combination has already been written above and there are no problems with the rest:

apple / banana / pear
pear / apple / banana
pear / banana / apple
banana / apple / pear
banana / pear / apple

Total: 6 combinations or 6 permutations.

Okay, it wasn’t difficult to list all the possible cases, but what if there are more objects? With just four different fruits, the number of combinations will increase significantly!

Please open the reference material (it’s convenient to print the manual) and in point No. 2, find the formula for the number of permutations.

No hassle - 3 objects can be rearranged in different ways.

Question two: In how many ways can you choose a) one fruit, b) two fruits, c) three fruits, d) at least one fruit?

Why choose? So we worked up an appetite in the previous point - in order to eat! =)

a) One fruit can be chosen, obviously, in three ways - take either an apple, a pear, or a banana. The formal calculation is carried out according to formula for the number of combinations:

The entry in this case should be understood as follows: “in how many ways can you choose 1 fruit out of three?”

b) Let us list all possible combinations of two fruits:

apple and pear;
apple and banana;
pear and banana.

The number of combinations can be easily checked using the same formula:

The entry is understood in a similar way: “in how many ways can you choose 2 fruits out of three?”

c) And finally, there is only one way to choose three fruits:

By the way, the formula for the number of combinations remains meaningful for an empty sample:
In this way, you can choose not a single fruit - in fact, take nothing and that’s it.

d) In how many ways can you take at least one fruit? The condition “at least one” implies that we are satisfied with 1 fruit (any) or any 2 fruits or all 3 fruits:
using these methods you can choose at least one fruit.

Readers who have carefully studied the introductory lesson on probability theory, we’ve already guessed something. But more about the meaning of the plus sign later.

To answer the next question I need two volunteers... ...Well, since no one wants to, then I’ll call you to the board =)

Question three: In how many ways can you distribute one fruit each to Dasha and Natasha?

In order to distribute two fruits, you first need to select them. According to paragraph “be” of the previous question, this can be done in ways, I’ll rewrite them:

apple and pear;
apple and banana;
pear and banana.

But now there will be twice as many combinations. Consider, for example, the first pair of fruits:
You can treat Dasha with an apple, and Natasha with a pear;
or vice versa - Dasha will get the pear, and Natasha will get the apple.

And such a permutation is possible for each pair of fruits.

Consider the same student group that went to the dance. In how many ways can a boy and a girl be paired?

In ways you can select 1 young man;
ways you can choose 1 girl.

Thus, one young man And You can choose one girl: ways.

When 1 object is selected from each set, the following principle for counting combinations is valid: “ every an object from one set can form a pair with every object of another set."

That is, Oleg can invite any of the 13 girls to dance, Evgeny can also invite any of the thirteen, and the rest of the young people have a similar choice. Total: possible pairs.

It should be noted that in this example, the “history” of the formation of the pair does not matter; however, if we take into account the initiative, the number of combinations must be doubled, since each of the 13 girls can also invite any boy to dance. It all depends on the conditions of a particular task!

A similar principle is valid for more complex combinations, for example: in how many ways can you choose two young men? And two girls to participate in a KVN skit?

Union AND clearly hints that the combinations need to be multiplied:

Possible groups of artists.

In other words, each a pair of boys (45 unique pairs) can perform with any a pair of girls (78 unique pairs). And if we consider the distribution of roles between the participants, there will be even more combinations. ...I really want to, but I’ll still refrain from continuing so as not to instill in you an aversion to student life =).

The rule for multiplying combinations also applies to a larger number of multipliers:

Problem 8

How many three-digit numbers are there that are divisible by 5?

Solution: for clarity, let’s denote this number with three asterisks: ***

IN hundreds place You can write any of the numbers (1, 2, 3, 4, 5, 6, 7, 8 or 9). Zero is not suitable, since in this case the number ceases to be three-digit.

But in tens place(“in the middle”) you can choose any of 10 digits: .

According to the condition, the number must be divisible by 5. A number is divisible by 5 if it ends in 5 or 0. Thus, we are satisfied with 2 digits in the least significant digit.

In total, there is: three-digit numbers that are divisible by 5.

In this case, the work is deciphered as follows: “9 ways you can choose a number in hundreds place And 10 ways to choose a number in tens place And 2 ways in units digit»

Or even simpler: “ each from 9 digits to hundreds place combines with each of 10 digits tens place and with each from two digits to units digit».

Answer: 180

And now…

Yes, I almost forgot about the promised commentary on problem No. 5, in which Bor, Dima and Volodya can be dealt one card each in different ways. Multiplication here has the same meaning: ways to remove 3 cards from the deck AND in each sample rearrange them in ways.

And now a problem to solve on your own... now I’ll come up with something more interesting... let it be about the same Russian version of blackjack:

Problem 9

How many winning combinations of 2 cards are there when playing "point"?

For those who don’t know: the winning combination is 10 + ACE (11 points) = 21 points and, let’s consider the winning combination of two aces.

(the order of the cards in any pair does not matter)

A short solution and answer at the end of the lesson.

By the way, do not consider the example primitive. Blackjack is almost the only game for which there is a mathematically based algorithm that allows you to beat the casino. Those interested can easily find a wealth of information about optimal strategy and tactics. True, such masters quite quickly end up on the black list of all establishments =)

It's time to consolidate the material covered with a couple of solid tasks:

Problem 10

Vasya has 4 cats at home.

a) in how many ways can cats be seated in the corners of the room?
b) in how many ways can you let cats go for a walk?
c) in how many ways can Vasya pick up two cats (one on his left, the other on his right)?

Let's decide: firstly, you should again pay attention to the fact that the problem deals with different objects (even if the cats are identical twins). This is a very important condition!

a) Silence of cats. Subject to this execution all the cats at once
+ their location is important, so there are permutations here:
using these methods you can place cats in the corners of the room.

I repeat that when permuting, only the number of different objects and their relative positions matter. Depending on Vasya’s mood, she can seat the animals in a semicircle on the sofa, in a row on the windowsill, etc. – in all cases there will be 24 permutations. For convenience, those interested can imagine that cats are multi-colored (for example, white, black, red and tabby) and list all possible combinations.

b) In how many ways can you let cats go for a walk?

It is assumed that cats go for walks only through the door, and the question implies indifference regarding the number of animals - 1, 2, 3 or all 4 cats can go for a walk.

We count all possible combinations:

In ways you can let one cat (any of the four) go for a walk;
ways you can let two cats go for a walk (list the options yourself);
in ways you can let three cats go for a walk (one of the four sits at home);
This way you can release all the cats.

You probably guessed that the resulting values ​​should be summed up:
ways you can let cats go for walks.

For enthusiasts, I offer a complicated version of the problem - when any cat in any sample can randomly go outside, both through the door and through the window on the 10th floor. There will be a noticeable increase in combinations!

c) In how many ways can Vasya pick up two cats?

The situation involves not only choosing 2 animals, but also placing them in each hand:
In these ways you can pick up 2 cats.

Second solution: you can choose two cats using methods And ways to plant every a couple on hand:

Answer: a) 24, b) 15, c) 12

Well, to clear your conscience, something more specific about multiplying combinations... Let Vasya have 5 additional cats =) In how many ways can you let 2 cats go for a walk? And 1 cat?

That is, with each a couple of cats can be released every cat.

Another button accordion for independent solution:

Problem 11

Three passengers boarded the elevator of a 12-story building. Everyone, regardless of the others, can exit on any (starting from the 2nd) floor with equal probability. In how many ways:

1) passengers can get off on the same floor (exit order does not matter);
2) two people can get off on one floor, and a third on the other;
3) people can exit on different floors;
4) can passengers exit the elevator?

And here they often ask again, I clarify: if 2 or 3 people exit on the same floor, then the order of exit does not matter. THINK, use formulas and rules for adding/multiplying combinations. In case of difficulties, it is useful for passengers to give names and speculate in what combinations they can exit the elevator. There is no need to be upset if something doesn’t work out, for example, point No. 2 is quite insidious.

Full solution with detailed comments at the end of the lesson.

The final paragraph is devoted to combinations that also occur quite often - according to my subjective assessment, in approximately 20-30% of combinatorial problems:

Permutations, combinations and placements with repetitions

The listed types of combinations are outlined in paragraph No. 5 of the reference material Basic formulas of combinatorics, however, some of them may not be very clear upon first reading. In this case, it is advisable to first familiarize yourself with practical examples, and only then comprehend the general formulation. Go:

Permutations with repetitions

In permutations with repetitions, as in “ordinary” permutations, all the many objects at once, but there is one thing: in this set one or more elements (objects) are repeated. Meet the next standard:

Problem 12

How many different letter combinations can be obtained by rearranging cards with the following letters: K, O, L, O, K, O, L, b, Ch, I, K?

Solution: in the event that all the letters were different, then a trivial formula would have to be applied, but it is completely clear that for the proposed set of cards some manipulations will work “idlely”, for example, if you swap any two cards with the letters “K” " in any word, you get the same word. Moreover, physically the cards can be very different: one can be round with the letter “K” printed on it, the other can be square with the letter “K” drawn on it. But according to the meaning of the task, even such cards are considered the same, since the condition asks about letter combinations.

Everything is extremely simple - only 11 cards, including the letter:

K – repeated 3 times;
O – repeated 3 times;
L – repeated 2 times;
b – repeated 1 time;
H – repeated 1 time;
And - repeated 1 time.

Check: 3 + 3 + 2 + 1 + 1 + 1 = 11, which is what needed to be checked.

According to the formula number of permutations with repetitions:
different letter combinations can be obtained. More than half a million!

To quickly calculate a large factorial value, it is convenient to use the standard Excel function: enter into any cell =FACT(11) and press Enter.

In practice, it is quite acceptable not to write the general formula and, in addition, to omit the unit factorials:

But preliminary comments about repeated letters are required!

Answer: 554400

Another typical example of permutations with repetition occurs in the chess piece placement problem, which can be found in the warehouse ready-made solutions in the corresponding pdf. And for an independent solution, I came up with a less formulaic task:

Problem 13

Alexey goes in for sports, and 4 days a week - athletics, 2 days - strength exercises and 1 day resting. In how many ways can he create a weekly schedule for himself?

The formula doesn't work here because it takes into account coincidental swaps (for example, swapping Wednesday's strength exercises with Thursday's strength exercises). And again - in fact, the same 2 strength training sessions can be very different from each other, but in the context of the task (from the point of view of the schedule) they are considered the same elements.

Two line solution and answer at the end of the lesson.

Combinations with repetitions

A characteristic feature of this type of combination is that the sample is drawn from several groups, each of which consists of identical objects.

Everyone has worked hard today, so it's time to refresh yourself:

Problem 14

The student canteen sells sausages in dough, cheesecakes and donuts. In how many ways can you buy five pies?

Solution: immediately pay attention to the typical criterion for combinations with repetitions - according to the condition, it is not a set of objects as such that is offered for choice, but different kinds objects; it is assumed that there are at least five hot dogs, 5 cheesecakes and 5 donuts on sale. The pies in each group are, of course, different - because absolutely identical donuts can only be simulated on a computer =) However, the physical characteristics of the pies are not significant for the purpose of the problem, and the hot dogs / cheesecakes / donuts in their groups are considered the same.

What might be in the sample? First of all, it should be noted that there will definitely be identical pies in the sample (since we are choosing 5 pieces, and there are 3 types to choose from). There are options here for every taste: 5 hot dogs, 5 cheesecakes, 5 donuts, 3 hot dogs + 2 cheesecakes, 1 hot dog + 2 cheesecakes + 2 donuts, etc.

As with “regular” combinations, the order of selection and placement of pies in the selection does not matter - you just chose 5 pieces and that’s it.

We use the formula number of combinations with repetitions:
You can purchase 5 pies using this method.

Bon appetit!

Answer: 21

What conclusion can be drawn from many combinatorial problems?

Sometimes the hardest thing is to understand the condition.

A similar example for an independent solution:

Problem 15

The wallet contains a fairly large number of 1-, 2-, 5- and 10-ruble coins. In how many ways can three coins be removed from a wallet?

For self-control purposes, answer a couple of simple questions:

1) Can all the coins in the sample be different?
2) Name the “cheapest” and most “expensive” combination of coins.

Solution and answers at the end of the lesson.

From my personal experience, I can say that combinations with repetitions are the rarest guest in practice, which cannot be said about the following type of combinations:

Placements with repetitions

From a set consisting of elements, elements are selected, and the order of the elements in each selection is important. And everything would be fine, but a rather unexpected joke is that we can select any object of the original set as many times as we like. Figuratively speaking, “the multitude will not decrease.”

When does this happen? A typical example is a combination lock with several disks, but due to technological developments, it is more relevant to consider its digital descendant:

Problem 16

How many four-digit PIN codes are there?

Solution: in fact, to resolve the problem, knowledge of the rules of combinatorics is enough: in ways you can select the first digit of the PIN code And ways - the second digit of the PIN code And in as many ways - third And the same number - the fourth. Thus, according to the rule of multiplying combinations, a four-digit pin code can be composed in: ways.

And now using the formula. According to the condition, we are offered a set of numbers, from which the numbers are selected and arranged in a certain order, while the numbers in the sample may be repeated (i.e. any digit of the original set can be used an arbitrary number of times). According to the formula for the number of placements with repetitions:

Answer: 10000

What comes to mind here... ...if the ATM “eats” the card after the third unsuccessful attempt to enter the PIN code, then the chances of picking it up at random are very slim.

And who said that combinatorics has no practical meaning? A cognitive task for all readers of the site:

Problem 17

According to the state standard, a car license plate consists of 3 numbers and 3 letters. In this case, a number with three zeros is unacceptable, and letters are selected from the set A, B, E, K, M, N, O, P, S, T, U, X (only those Cyrillic letters are used whose spelling coincides with Latin letters).

How many different license plates can be created for a region?

Not that many of them, by the way. In large regions there is not enough such quantity, and therefore for them there are several codes for the inscription RUS.

The solution and answer are at the end of the lesson. Don’t forget to use the rules of combinatorics ;-) ...I wanted to show off what was exclusive, but it turned out not to be exclusive =) I looked at Wikipedia - there are calculations there, although without comments. Although for educational purposes, probably, few people solved it.

Our exciting lesson has come to an end, and finally I want to say that you have not wasted your time - for the reason that combinatorics formulas find another vital practical application: they are found in various problems in probability theory,
and in problems involving the classical determination of probability– especially often =)

Thank you all for your active participation and see you soon!

Solutions and Answers:

Task 2: Solution: find the number of all possible permutations of 4 cards:

When a card with a zero is placed in the 1st place, the number becomes three-digit, so these combinations should be excluded. Let zero be in the 1st place, then the remaining 3 digits in the lower digits can be rearranged in different ways.

Note : because Since there are only a few cards, it’s easy to list all the options here:
0579
0597
0759
0795
0957
0975

Thus, from the proposed set we can make:
24 – 6 = 18 four-digit numbers
Answer : 18

Task 4: Solution: in ways you can choose 3 cards out of 36.
Answer : 7140

Task 6: Solution: ways.
Another solution : ways you can select two people from the group and and
2) The “cheapest” set contains 3 ruble coins, and the most “expensive” – 3 ten-ruble coins.

Problem 17: Solution: using these methods, you can create a digital combination of a car number, while one of them (000) should be excluded: .
using these methods you can create a letter combination of a license plate number.
According to the rule of multiplying combinations, the total can be made:
license plates
(each digital combination is combined with each letter combination).
Answer : 1726272

A combination is an unordered selection of elements of a finite set with a fixed number and without repetitions of elements. Different combinations must differ in at least one element, and the order of the elements does not matter. For example, from the set of all vowels of Latin letters (AEIOU), you can make 10 different combinations of 3 letters, forming the following unordered triplets:

AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.

It is interesting to note that from the same five letters you can also get 10 different combinations if you combine them 2 letters at a time, making the following unordered pairs:

AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.

However, if you combine the same vowel Latin letters by 4, you will only get the following 5 different combinations:

AEIO, AEIU, AIOU, EIOU, AEOU.

In general, to denote the number of combinations of n different elements of m elements, the following functional, index or vector (Appel) symbolism is used:

Regardless of the form of notation, the number of combinations of n elements by m elements can be determined using the following multiplicative and factorial formulas:

It is easy to check that the result of calculations using these formulas coincides with the results of the example discussed above with combinations of vowels in Latin letters. In particular, with n=5 and m=3, calculations using these formulas will give the following result:

In the general case, formulas for the number of combinations have a combinatorial meaning and are valid for any integer values ​​of n and m, such that n > m > 0. If m > n and m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:

In addition, it is useful to remember the following limiting numbers of combinations, which can be easily checked by direct substitution into the multiplicative and factorial formulas:

It should also be noted that the multiplicative formula remains valid even when n is a real number, as long as m is still an integer value. However, then the result of the calculation using it, while maintaining formal validity, loses its combinatorial meaning.

IDENTITIES OF COMBINATIONS

The practical use of multiplicative and factorial formulas to determine the number of combinations for arbitrary values ​​of n and m turns out to be of little productivity due to the exponential growth of the factorial products of their numerator and denominator. Even for relatively small values ​​of n and m, these products often exceed the capabilities of representing integers in modern computing and software systems. Moreover, their values ​​turn out to be significantly greater than the resulting value of the number of combinations, which can be relatively small. For example, the number of combinations of n=10 by m=8 elements is only 45. However, to find this value using the factorial formula, you must first calculate much larger values ​​of 10! in the numerator and 8! in the denominator:

To eliminate time-consuming operations for processing large quantities, to determine the number of combinations, you can use various recurrence relations, which directly follow from the multiplicative and factorial formulas. In particular, the following recurrence relation follows from the multiplicative formula, which allows us to take the ratio of its indices beyond the sign of the number of combinations:

Finally, keeping the subscript constant provides the following recurrence relation, which is easily obtained from the factorial formula for the number of combinations:

After elementary transformations, the three resulting recurrence relations can be represented in the following forms:

If we now add the left and right sides of the first 2 formulas and reduce the result by n, we get an important recurrence relation, which is called the identity of adding combination numbers:

The addition identity provides a basic recurrence rule for efficiently determining the number of combinations for large values ​​of n and m, since it allows the multiplication operations in factorial products to be replaced by the simpler addition operations, and for smaller numbers of combinations. In particular, using the addition identity, it is now easy to determine the number of combinations of n=10 by m=8 elements, which was discussed above, by performing the following sequence of recurrent transformations:

In addition, several useful relations for calculating finite sums can be derived from the addition identity, in particular, the formula for summation by subscript, which has the following form:

This relation is obtained if in the addition identity we expand the recurrence along the term with the largest superscript while its subscript is greater than 0. The following numerical example illustrates this process of recurrent transformations:

The subscript summation formula is often used to calculate the sum of powers of natural numbers. In particular, assuming m=1, using this formula it is easy to find the sum of the first n numbers of the natural series:

Another useful version of the summation formula can be obtained by expanding the recurrence of the addition identity along the term with the smallest superscript. The following numerical example illustrates this version of recurrent transformations:

In the general case, as a result of such transformations, the sum of the numbers of combinations is obtained, both indices of which differ by one from the neighboring terms, and the difference in the indices remains constant (in the example considered, it is also equal to one). Thus, we obtain the following summation formula for both indices of combination numbers:

In addition to the recurrence relations and summation formulas discussed above, many other useful identities for combination numbers have been obtained in combinatorial analysis. The most important among them is symmetry identity, which looks like this:

The validity of the symmetry identity can be verified in the following example by comparing the numbers of combinations of 5 elements by 2 and by (5 2) = 3:

The symmetry identity has an obvious combinatorial meaning, since, by determining the number of options for selecting m elements from n elements, it simultaneously establishes the number of combinations from the remaining (nm) unselected elements. The indicated symmetry is immediately obtained by replacing m by (nm) in the factorial formula for the number of combinations:

Numbers and combination identities are widely used in various areas of modern computational mathematics. However, their most popular applications are related to Newton's binomial and Pascal's triangle.

BINOMIAL THEOREM

To perform various mathematical transformations and calculations, it is important to be able to represent any natural power of an algebraic binomial (binomial) in the form of a polynomial. For small powers, the desired polynomial can be easily obtained by directly multiplying binomials. In particular, the following formulas for the square and cube of the sum of two terms are well known from the course of elementary mathematics:

In the general case, for an arbitrary degree n of a binomial, the required representation in the form of a polynomial is provided by Newton’s binomial theorem, which declares the following equality to be true:

This equality is usually called Newton's binomial. The polynomial on its right side is formed by the sum of the products of n terms X and Y of the binomial on the left side, and the coefficients in front of them are called binomial and are equal to the number of combinations with indices, which are obtained from their powers. Given the particular popularity of Newton's binomial formula in combinatorial analysis, the terms binomial coefficient and number of combinations are generally considered synonymous.

Obviously, the squared and cubed sum formulas are special cases of the binomial theorem for n=2 and n=3, respectively. To handle higher degrees (n>3), Newton's binomial formula should be used. Its application for a fourth degree binomial (n=4) is demonstrated by the following example:

It should be noted that the binomial formula was known even before Newton to medieval mathematicians of the Arab East and Western Europe. Therefore, its generally accepted name is not historically correct. Newton's merit is that he generalized this formula to the case of an arbitrary real exponent r, which can take any positive or negative rational and irrational values. In the general case, such a Newton binomial formula has an infinite sum on the right side and is usually written as follows:

For example, with a positive fractional value of the exponent r=1/2, taking into account the values ​​of the binomial coefficients, the following expansion is obtained:

In the general case, Newton's binomial formula for any exponent is a special version of Maclaurin's formula, which gives the expansion of an arbitrary function into a power series. Newton showed that for |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . If we now set Z=X/Y and multiply the left and right sides by Yn, we get a version of the Newton binomial formula discussed above.

Despite its universality, the binomial theorem retains its combinatorial meaning only for non-negative integer powers of the binomial. In this case, it can be used to prove several useful identities for binomial coefficients. In particular, formulas for summing the numbers of combinations by subscript and by both indices were discussed above. The missing superscript summation identity can be easily obtained from Newton’s binomial formula by putting X = Y = 1 or Z = 1 in it:

Another useful identity establishes the equality of the sums of binomial coefficients with even and odd numbers. It is immediately obtained from Newton's binomial formula if X = 1 and Y = 1 or Z = 1:

Finally, from both considered identities we obtain the identity of the sum of binomial coefficients with only even or only odd numbers:

Based on the considered identities and the recurrent rule of removing indices from under the sign of the number of combinations, a number of interesting relationships can be obtained. For example, if in the superscript summation formula we replace n everywhere with (n1) and remove the indices in each term, we get the following relation:

Using a similar technique in the formula for the sum of binomial coefficients with even and odd numbers, it is possible to prove the validity of, for example, the following relation:

Another useful identity allows you to easily calculate the sum of the products of symmetrically located binomial coefficients of two binomials of arbitrary degrees n and k using the following Cauchy formula:

The validity of this formula follows from the necessary equality of coefficients for any degree m of the variable Z on the left and right sides of the following identical relation:

In the special case when n=k=m, taking into account the symmetry identity, a more popular formula for the sum of squares of binomial coefficients is obtained:

Many other useful identities for binomial coefficients can be found in the extensive literature on combinatorial analysis. However, their most famous practical application is related to Pascal's triangle.

PASCAL'S TRIANGLE

Pascal's arithmetic triangle forms an infinite numerical table made up of binomial coefficients. Its lines are ordered by powers of binomials from top to bottom. In each line, the binomial coefficients are arranged in ascending order of the superscripts of the corresponding combination numbers from left to right. Pascal's triangle is usually written either in isosceles or rectangular form.

More visual and common is the isosceles format, where the binomial coefficients, staggered, form an infinite isosceles triangle. Its initial fragment for binomials up to the 4th degree (n=4) has the following form:

In general, Pascal's isosceles triangle provides a convenient geometric rule for determining binomial coefficients, which is based on the identities of addition and the symmetry of number combinations. In particular, according to the addition identity, any binomial coefficient is the sum of the two coefficients of the previous row closest to it. According to the symmetry identity, Pascal's isosceles triangle is symmetrical with respect to its bisector. Thus, each of its lines is a numerical palindrome of binomial coefficients. The indicated algebraic and geometric features make it possible to easily expand Pascal's isosceles triangle and consistently find the values ​​of binomial coefficients of arbitrary powers.

However, to study various properties of Pascal's triangle, it is more convenient to use the formally more strict rectangular format. In this format, it is specified by a lower triangular matrix of binomial coefficients, where they form an infinite right triangle. The initial fragment of Pascal's right triangle for binomials up to the 9th degree (n=9) has the following form:

Geometrically, such a rectangular table is obtained by horizontally deforming Pascal's isosceles triangle. As a result, the number series parallel to the lateral sides of Pascal’s isosceles triangle turn into verticals and diagonals of Pascal’s right triangle, and the horizontal lines of both triangles coincide. At the same time, the rules of addition and symmetry of binomial coefficients remain valid, although Pascal's right triangle loses the visual symmetry characteristic of its isosceles counterpart. To compensate for this, it becomes more convenient to formally analyze the various numerical properties of the binomial coefficients for the horizontals, verticals, and diagonals of Pascal's right triangle.

Starting the analysis of the horizontals of Pascal's right triangle, it is easy to notice that the sum of the elements of any row with number n is equal to 2n in accordance with the formula for summing binomials by superscript. It follows from this that the sum of the elements above any of the horizontal lines with number n is equal to (2 n 1). This result becomes quite obvious if the value of the sum of the elements of each horizontal is written in the binary number system. For example, for n=4 this addition can be written as follows:

Here are a couple more interesting properties of horizontals that are also related to powers of two. It turns out that if the horizontal number is a power of two (n=2 k), then all its internal elements (except for the outer ones) are even numbers. On the contrary, all numbers of a horizontal line will be odd if its number is one less than a power of two (n=2 k 1). The validity of these properties can be verified by checking the parity of the internal binomial coefficients, for example, in the horizontals n=4 and n=3 or n=8 and n=7.

Let now the row number of Pascal's right triangle be a prime number p. Then all its internal binomial coefficients are divisible by p. This property is easy to check for small values ​​of prime contour numbers. For example, all the internal binomial coefficients of the fifth horizontal (5, 10 and 5) are obviously divisible by 5. To prove this result for any prime horizontal number p, you need to write the multiplicative formula for its binomial coefficients as follows:

Since p is a prime number and, therefore, is not divisible by m!, the product of the remaining factors of the numerator of this formula must be divisible by m! to guarantee an integer value of the binomial coefficient. It follows that the ratio in square brackets is a natural number N and the desired result becomes obvious:

Using this result, we can establish that the numbers of all horizontal lines of Pascal's triangle, the internal elements of which are divisible by a given prime number p, are powers of p, that is, they have the form n=p k. In particular, if p=3, then the prime number p divides not only all internal elements of row 3, as established above, but, for example, the 9th horizontal (9, 36, 84 and 126). On the other hand, in Pascal's triangle it is impossible to find a horizontal line whose internal elements are all divisible by a composite number. Otherwise, the number of such a horizontal line must simultaneously be a power of prime divisors of the composite number by which all its internal elements are divided, but this is impossible for obvious reasons.

The considered considerations allow us to formulate the following general criterion for the divisibility of the horizontal elements of Pascal's triangle. The greatest common divisor (GCD) of all internal elements of any horizontal line of Pascal's triangle with number n is equal to the prime number p if n=pk or 1 in all other cases:

GCD(Cmn) = ( ) for any 0< m < n .

In conclusion of the analysis of horizontals, it is worth considering one more interesting property that the series of binomial coefficients that form them have. If the binomial coefficients of any horizontal line with number n are multiplied by successive powers of the number 10, and then all these products are added, the result is 11 n. The formal justification for this result is the substitution of the values ​​X=10 and Y=1 (or Z=1) into the Newton binomial formula. The following numerical example illustrates the fulfillment of this property for n=5:

The analysis of the properties of the verticals of Pascal's right triangle can begin with the study of the individual characteristics of their constituent elements. Formally, each vertical m is formed by the following infinite sequence of binomial coefficients with a constant superscript (m) and an increment of the subscript:

Obviously, when m=0 a sequence of ones is obtained, and when m=1 a series of natural numbers is formed. When m=2 the vertical is made up of triangular numbers. Each triangular number can be depicted on a plane in the form of an equilateral triangle, which is filled with arbitrary objects (nuclei) arranged in a checkerboard pattern. In this case, the value of each triangular number T k determines the number of representing kernels, and the index shows how many rows of kernels are needed to represent it. For example, 4 initial triangular numbers represent the following configurations of the corresponding number of nuclear "@" symbols:

It should be noted that in a similar way one can introduce into consideration square numbers S k , which are obtained by squaring natural numbers and, in general, polygonal figured numbers formed by regularly filling regular polygons. In particular, the 4 initial square numbers can be represented as follows:

Returning to the analysis of the verticals of Pascal's triangle, we can note that the next vertical at m=3 is filled with tetrahedral (pyramidal) numbers. Each such number P k specifies the number of cores that can be arranged in the shape of a tetrahedron, and the index determines how many horizontal triangular layers of rows of cores are required to depict it in three-dimensional space. In this case, all horizontal layers must be represented as successive triangular numbers. The elements of the following verticals of Pascal's triangle for m>3 form series of hypertetraedal numbers, which do not have a visual geometric interpretation on the plane or in three-dimensional space, but formally correspond to multidimensional analogues of triangular and tetrahedal numbers.

Although the vertical number series of Pascal's triangle have the considered individual shaped features, for them it is possible to calculate the partial sums of the values ​​of the initial elements in the same way, using the formula for summing the numbers of combinations by subscript. In Pascal's triangle, this formula has the following geometric interpretation. The sum of the values ​​of the n upper binomial coefficients of any vertical is equal to the value of the element of the next vertical, which is located one line below. This result is also consistent with the geometric structure of triangular, tetrahedral and hypertetrahedal numbers, since the representation of each such number consists of core layers that represent lower order numbers. In particular, the nth triangular number Tn can be obtained by summing all the natural numbers representing its linear layers:

Similarly, it is not difficult to find the tetrahedral number Pn by calculating the following sum of the first n triangular numbers that make up its horizontal core layers:

In addition to the horizontals and verticals in Pascal’s right triangle, one can trace diagonal rows of elements, the study of the properties of which is also of some interest. In this case, a distinction is usually made between descending and ascending diagonals. The downward diagonals are parallel to the hypotenuse of Pascal's right triangle. They are formed by series of binomial coefficients with an increment of both indices. Due to the identity of symmetry, the descending diagonals coincide in the values ​​of their elements with the corresponding vertical rows of Pascal’s triangle and therefore repeat all their properties discussed above. The indicated correspondence can be traced by the coincidence of the values ​​of the elements of the descending diagonal and the vertical with any number n, if vertical zeros are not taken into account:

Ascending diagonals form number series geometrically perpendicular to the hypotenuse of Pascal's right triangle. They are filled with binomial coefficients with a decrement of the lower and increment of the superscript. In particular, the 7 upper ascending diagonals form the following numerical sequence without taking into account the trailing zeros:

In general, the ascending diagonal number n contains the following binomial coefficients, the sum of the indices of each of which is equal to (n1):

By virtue of the addition identity for combination numbers, each diagonal element is equal to the sum of two elements corresponding in indices from the two previous ascending diagonals. This allows each subsequent ascending diagonal to be constructed by pairwise summation of adjacent horizontal elements from the two previous diagonals, infinitely expanding Pascal's triangle along the diagonal. The following fragment of Pascal's triangle illustrates the construction of an ascending diagonal number 8 along diagonals numbered 6 and 7:

With this method of construction, the sum of the elements of any ascending diagonal, starting from the 3rd, will be equal to the sum of the elements of the two previous ascending diagonals, and the first 2 diagonals consist of only one element, the value of which is 1. The results of the corresponding calculations form the following numerical series, according to which you can check the validity of the considered property of the ascending diagonals of Pascal’s right triangle:

Analyzing these numbers, you can see that according to a similar law, the well-known sequence of Fibonacci numbers is formed, where each next number is equal to the sum of the two previous ones, and the first two numbers are equal to 1:

Thus, we can draw the following important conclusion: the diagonal sums of the elements of Pascal’s triangle constitute the Fibonacci sequence. This property allows us to establish another interesting feature of Pascal's triangle. Expanding the Fibonacci formula recursively, it is easy to prove that the sum of the first n Fibonacci numbers is equal to (F n+2 1).

Therefore, the sum of the binomial coefficients that fill the upper n diagonals is also equal to (F n+2 1). It follows that the sum of the first n diagonals of Pascal’s triangle is 1 less than the sum of the binomial coefficients that stand on its diagonal with number (n+2).

In conclusion, it should be noted that the considered properties of the horizontals, verticals and diagonals of Pascal's triangle do not exhaust the huge variety of possibilities that connect together various mathematical aspects that at first glance have nothing in common. Such unusual properties allow us to consider Pascal’s triangle one of the most perfect numerical systems, all of whose capabilities cannot be listed and are difficult to overestimate.

The algorithm for calculating the number of combinations using Pascal's triangle is presented below:

Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Next For i = 2 To n For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next SochTT = TT (n, k) End Function

If you need to calculate the number of combinations many times, then it may be more convenient to construct Pascal's triangle once, and then receive data from the array.

Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j As Integer ReDim Preserve TT (end, end) For i = start To end TT (0, i) = 1 TT (i, i) = 1 Next If end< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub

First you need to call the CreateTT procedure. You can then obtain the number of combinations using the SochTT function. When you no longer need the triangle, call the TerminateTT procedure. In the above code, when calling the SochTT function, if the triangle has not yet been completed to the required level, then it is completed using the BuildTT procedure. The function then gets the desired element of the TT array and returns it.

Dim X () As Integer Dim Counter () As Integer Dim K As Integer Dim N As Integer Public Sub Soch() Dim i As Integer N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Then ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 For j = 1 To N If X1(j)<>0 Then n1 = n1 + 1 If n1 = Counter(i) Then Out(i) = X1(j) X1(j) = 0 Exit For End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Next txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub

LISTING COMBINATIONS OF NATURAL NUMBERS

To solve many practical problems, it is necessary to list all combinations of fixed cardinality that can be obtained from the elements of a given finite set, and not just determine their number. Taking into account the always existing possibility of integer numbering of the elements of any finite set, in most cases it is permissible to limit ourselves to the use of algorithms for enumerating combinations of natural numbers. The most natural and simple of them is the algorithm for listing combinations of natural numbers in lexigraphic order.

To formally describe this algorithm, it is convenient to assume that the main set, all combinations of m elements of which must be listed, form consecutive natural numbers from 1 to n. Then any combination of m

As a result of ordering, the value in each position of such a vector of combinations naturally turns out to be limited in value from above and below as follows:

The lexigraphic algorithm sequentially generates such combination vectors, starting with the lexigraphically smallest vector, where all positions contain the following minimum possible values ​​of elements equal to their indices:

Each successive combination vector is formed from the current one after scanning its elements from left to right in order to find the rightmost element that has not yet reached its limit value:

The value of such an element should be increased by 1. Each element to the right of it should be assigned the smallest possible value, which is 1 greater than its neighbor to the left. After these changes, the next vector of combinations will have the following elemental composition:

Thus, the next combination vector will be lexigraphically larger than the previous one, since the values ​​of their initial (j1) elements are equal in value, and the value of the element at position j is 1 greater than that of the previous one. The specified relation of increasing lexigraphic order is guaranteed to be satisfied at all iterations of the algorithm. The result is an increasing lexigraphic sequence, which is completed by the lexigraphically largest combination vector, where the elements in all positions have the following maximum values:

The considered lexigraphic algorithm is illustrated by the following example, where it is necessary to list in increasing lexigraphic order all 15 combinations of n=6 first natural numbers by m=4 numbers, that is, all possible 4-element subsets of the main generating set (1, 2, 3, 4 , 5, 6) from 6 elements. The calculation results are presented in the following table:

In this example, the largest permissible values ​​of numbers in the positions of the combination vectors are, respectively, 3, 4, 5 and 6. For ease of interpretation of the results, in each combination vector, the rightmost element, which has not yet reached its maximum value, is underlined. Numerical indices of combination vectors determine their numbers in lexigraphic order. In the general case, the lexigraphic number N of any combination of n elements by m can be calculated using the following formula, where, for cosmetic reasons, Appel symbolism is used to denote the numbers of combinations:

In particular, the following calculations using this formula for the combination number (1, 3, 4, 6) of n=6 elements of m=4 in lexigraphic order will give the result N=8, which corresponds to the example discussed above:

In the general case, using the identity for the sum of the numbers of combinations for both indices, it is possible to show that the number of the lexigraphically smallest combination (1, ... i, ... m) when calculated using this formula will always be equal to 1:

It is also obvious that the number of the lexigraphically largest combination (m, … nm+i, … n) when calculated using this formula will be equal to the number of combinations of n elements by m:

The formula for calculating lexigraphic combination numbers can be used to solve the inverse problem, where you need to determine the combination vector by its number in lexigraphic order. To solve such an inverse problem, it must be written in the form of an equation, where all the unknown values ​​of the elements of the vector of the desired combination (C 1, ... C i, ... C m) are concentrated in the numbers of combinations of its right side, and the known difference L of the number of combinations is written on the left side of n elements each m and the number of the required combination N:

The solution to this equation is provided by the following “greedy” algorithm, during the iterations of which the values ​​of the elements of the vector of the desired combination are sequentially selected. At the initial iteration, the minimum possible (within its limitations) value of C 1 is selected, at which the first term on the right side will have a maximum value not exceeding L:

Now the left side of L should be reduced by the first number of combinations on the right side with the selected value of C 1, and similarly determine the value of C 2 at the second iteration:

Similarly, all subsequent iterations should be performed to select the values ​​of all other elements C i of the desired combination, up to the last element C m:

For obvious reasons, the value of the last element C m can be determined based on the equality of its number of combinations to the residual value of the left side of L:

It should be noted that the value of the last element of the combination C m can be found even more simply, without enumerating its possible values:

The implementation of iterations of the considered algorithm is illustrated by the following example, where it is necessary to determine combinations with the number N=8 in lexigraphic order, if n=6 and m=4:

The algorithmic ability to determine a combination by a given number in lexigraphic order can be used in various directions. In particular, when listing combinations in lexigraphic order, it is necessary to ensure a return to any combination that was obtained earlier, it is enough to know only its number. In addition, it becomes possible to generate combinations in any order, which is regulated by an arbitrarily given sequence of their lexigraphic numbers.

Now we present an algorithm for generating combinations in lexicographic order:

2 for i:= 1 to k do A[i] := i;

5 begin write(A, …, A[k]);

6 if A[k] = n then p:= p 1 else p:= k;

8 for i:= k downto p do A[i] := A[p] + i p + 1

COMBINATIONS WITH REPEATING ELEMENTS

Unlike a classical combination, where all elements are different, a combination with repetitions forms an unordered selection of elements of a finite set, where any element can appear indefinitely frequently and is not necessarily present in a single copy. In this case, the number of repetitions of elements is usually limited only by the length of the combination, and combinations that differ in at least one element are considered different. For example, by choosing 4 optionally different numbers from the set 1, 2 and 3, you can create the following 15 combinations with repetitions:

1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.

In general, combinations with repetitions can be formed by selecting n elements of arbitrary types. However, they can always be associated with consecutive natural numbers from 1 to n. Then any combination of m optionally different numbers in this range can be written in vector form, arranging them in non-decreasing order from left to right:

Naturally, with this form of notation, any neighboring elements can be equal due to the possibility of unlimited repetitions. However, each combination vector with repetitions of n elements by m can be associated with a combination vector of (n+m−1) elements by m, which is constructed as follows:

It is clear that for any values ​​of the elements of the vector f, the elements of the vector C are guaranteed to be different and strictly ordered in increasing order of their values ​​from the range from 1 to (n+m1):

The presence of a one-to-one correspondence between the elements of the combination vectors f and C allows us to propose the following simple method for systematically listing combinations with repetitions of n elements by m. It is only necessary to list, for example, in lexigraphic order, all C combinations of (n+m1) elements of m, sequentially transforming the elements of each of them into the corresponding elements of combinations with repetitions f using the following formula:

As a result, a sequence of vectors of combinations with repetitions of elements is formed, which are arranged in the order generated by listing the corresponding combinations without repetitions of elements. In particular, in order to obtain the above sequence of combinations of 3 digits 1, 2 and 3 with repetitions of 4 digits, it is necessary to list in lexigraphic order all combinations without repetitions of 6 digits 1,2,3,4, 5 and 6 are 4 digits each, converting them as indicated. The following example shows such a conversion of the combination (1,3,4,6) with the lexicographic number 8:

The considered one-to-one correspondence between combinations with and without repetitions of elements means that their sets are equally powerful. Therefore, in the general case, the number of combinations with repetitions of n elements by m is equal to the number of combinations without repetitions of (n+m1) elements by m. Using the same symbolism to denote the numbers of combinations with repetitions f and without repetitions C, this equality can be written as follows:

It is easy to check that for the example considered above, where n=3 and m=4, the number of repetition combinations will be equal to 15, which coincides with the result of their direct listing:

It should be noted that, unlike the classical version, the values ​​of the combination parameters with repetitions n and m are not directly related to each other, therefore f(n,m)>0 for any combination of their positive values. The corresponding boundary conditions are determined from the equality between the values ​​of (n+m1) and (n1) or (n+m1) and m:

It should also be quite obvious that if m is equal to 1, then no repetitions of elements are possible and, therefore, for any positive value of n>0 the following equality will be true:

In addition, for numbers of combinations with repetitions for any positive values ​​of n and m, the following recurrence relation is valid, which is similar to the addition identity for numbers of combinations without repetitions of elements:

Actually, it turns into the indicated addition identity upon formal substitution of the corresponding numbers of combinations without repetitions into its left and right sides:

The considered recurrence relation can be used to effectively determine the numbers of combinations with repetitions, when it is important to eliminate the labor-intensive operations of calculating factorial products and replace them with simpler addition operations. In this case, to calculate the value of f(n,m), you only need to apply this recurrence relation until you obtain the sum of terms of the form f(1,m) and f(i,1), where i takes values ​​​​in the range from n to 1. By definition of the quantity such terms are equal to 1 and i, respectively. The following example illustrates the use of this transformation technique for the case of n=3 and m=4:

LISTING BINARY COMBINATIONS

When implementing combinations in hardware or programming in assembly language, it is important to be able to process combination records in binary format. In this case, any combination of n elements of m should be specified in the form of an n-bit binary number (B n,...B j,...B 1), where m unit digits indicate the elements of the combination, and the remaining (nm) digits have zero values. Obviously, with this form of notation, different combinations must differ in the arrangement of the 1's digits, and there are only C(n,m) ways to arrange m ones or (nm) zeros in an n-bit binary set. For example, the following table lists all 6 such binary combinations, which provide 4-bit binary numbers for all combinations of 4 elements of an arbitrary set (E 1 , E 2 , E 3 , E 4 ) by 2:

In the general case, the task of enumerating such binary combinations comes down to a systematic search of all n-bit binary sets with different arrangements of m one and (nm) zero bits. In the simplest form, such search is implemented by various methods of transposing adjacent bits with a shift (transpositive-shift algorithms). These are iterative algorithms, and their names reflect the nature of the operations performed at each step. Iterative procedures of transpositive-shift algorithms form sequences of binary combinations that begin with a binary set, where all ones are concentrated in the low-order digits (on the right), and end when all the 1’s are in the high-order digits (on the left):

While matching in initial and final combinations, these sequences differ in the order in which intermediate binary sets are listed. However, in all cases, each subsequent binary combination is formed from the previous one as a result of performing the corresponding transposition and shift operations. At the same time, various transpositive-shift algorithms differ in the way they select a pair of bits for transposition and a group of bits for shifting. This specificity is discussed below for transposition algorithms with left and right shift.

In the transposition algorithm with a left shift, at each step, the next binary combination is obtained from the current one by replacing the leftmost pair of digits 01 with 10 (transposition) and shifting the group of leading unit digits, if any, close to the pair 10 obtained after the transposition (shift). If in this case there are no units in the leading digits in the current binary combination, then the shift is not performed, even when the leading unit is obtained after transposition at this step. The shift is also not performed when there are no zeros in the most significant bits before the pair 10 obtained after the transposition. The considered actions are illustrated by the following example of performing two successive iterations of this algorithm, where at one iteration (15) only transposition (T") is performed, and at the other iteration (16) the transposition is supplemented by a shift (T"+S"):

In the right-shift transposition algorithm, conceptually similar steps are performed at each step. Only transposition ensures that the rightmost bits of 01 are replaced by 10 (instead of the leftmost ones), and then all the ones to the right of it are shifted to the least significant bits. As before, the shift is performed only if there are units that can be shifted to the right. The considered actions are illustrated by the following example of performing two successive iterations of this algorithm, where at one iteration (3) only transposition (T") is performed, and at the other iteration (4) the transposition is supplemented by a shift (T"+S"):

It should be noted that the iterations of both algorithms can be written in additive form if binary combinations are interpreted as integers in the base 2 number system. In particular, for the transposition algorithm with a right shift, each next binary combination (B" n ,…B" j , …B" 1), can always be obtained from the current combination (B n,…B j,…B 1) by performing the operations of adding integers using the following additive formula:

In this additive formula, the exponents of powers of twos f and t denote, respectively, the number of low-order zero digits of the current binary combination and the number of ones in a row to the left of them. For example, for the 4th binary combination (001110) of n=6 digits f =1 and t =3. Therefore, calculating the next binary combination using the additive formula at iteration 5 will give the following result, equivalent to performing the transposition and shift operations:

For a comparative analysis of the considered transposition algorithms with left and right shifts, it is advisable to compare the sequences of binary combinations that they generate in their iterations. The following table shows two such sequences of binary combinations of 4 elements of 2, which are obtained by the left (TSL) and right (TSR) shift algorithms, respectively:

Comparing these 2 sequences, you can see that they are reverse mirror. This means that any two binary combinations that are located in them at the same distance from the mutually opposite ends of their sequences are a mirror image of each other, that is, they coincide when the indexing of the bits in any of them is reversed. For example, the second binary pattern from the beginning of the TSL sequence (0101) is a mirror image of the binary pattern (1010) that is second from the end of the TSR sequence. In general, any binary combination with number i of one sequence is a mirror image of a binary combination with number (ni+1) of another sequence. This relationship between these sequences is a consequence of the symmetrical nature of the transposition and shift operations in the two considered algorithms for enumerating binary combinations.

It should be noted that the binary format can also be used to record combinations with repetitions of elements. To do this, it is necessary to establish a one-to-one correspondence between combinations with repetitions and binary combinations, which are constructed as follows. Let there be an arbitrary combination with repetitions, which is obtained by choosing m optionally different elements from the n elements of the generating set. To establish the desired match, you must first add all the elements of the forming set (cat) to the combination, and then sort the resulting concatenation (sort) so that all identical elements are side by side. The result is a sequence of (n+m) elements, where there are n groups of identical elements. There will be a total of (n+m1) gaps between elements, among which there will be (n1) gaps between groups of identical elements and m gaps between elements within groups. For clarity, you can place the symbols “|” in the indicated spaces. and correspondingly. If we now match 1 to the spaces between groups (|) and 0 to all other spaces (), we get a binary combination. It is formed by a binary set of (n+m1) bits, where (n1) are ones and m zero bits, the location of which uniquely corresponds to the original combination with repetitions of elements n through m. The considered transformation technique is illustrated by the following example of constructing a binary combination (1001101) using a combination with repetitions (BBD), the elements of which are selected from the generating set of the first five Latin letters:

In general, the number of such binary sets determines the number of ways to arrange (n1) ones (or m zeros) in (n+m1) binary digits. This value is obviously equal to the number of combinations from (n+m1) by (n1) or by m, that is, C(n+m1,n1) or C(n+m1,m), which is equal to the number of combinations with repetitions f( n,m) of n elements, m each. Thus, having a one-to-one correspondence between combinations with repetitions and binary combinations, it is legitimate to reduce the enumeration of combinations with repetitions to enumeration of binary combinations, for example, using transposition algorithms with left or right shift. After this, you only need to restore the required combinations with repetitions using the resulting binary combinations. This can always be done by using the following recovery technique.

Let the main set, from the elements of which combinations with repetitions of m not necessarily different elements be formed, be ordered in an arbitrary way so that each of its elements has a certain serial number from 1 to n. Let us also implement the enumeration of binary combinations of (n+m1) binary digits, where (n1) ones and m zero digits. Each resulting binary combination can be supplemented on the left with a fictitious unit digit, and all unit digits can be numbered from left to right with integers from 1 to n. Then the number of zeros in a row after each i-th unit of the binary combination will be equal to the number of instances of the i-th element of the main set in the corresponding combination with repetitions. The considered technique is illustrated by the following example, where, using a binary combination (1001101), a combination with repetitions of BBD is restored, the elements of which are selected from the generating set of the first five Latin letters, written in alphabetical order, and the overline indicates elements that are absent in this combination:

By performing similar actions in the conditions of this example, you can list all 35 binary combinations that form 7-bit binary sets, where there are 4 ones and 3 zeros, and restore the corresponding combinations with repetitions of 5 elements of 3.

We sometimes make a choice from many without regard to order. This choice is called combination . If you play cards, for example, you know that in most situations the order in which you hold the cards doesn't matter.

Example 1 Find all combinations of 3 letters taken from a set of 5 letters (A, B, C, D, E).

Solution These combinations are as follows:
(A, B, C), (A, B, D),
(A, B, E), (A, C, D),
(A, C, E), (A, D, E),
(B, C, D), (B, C, E),
(B, D, E), (C, D, E).
There are 10 combinations of three letters chosen from five letters.

When we find all combinations from a set with 5 objects, if we take 3 objects at a time, we find all 3-element subsets. In this case, the order of objects is not considered. Then,
(A, C, B) is called the same set as (A, B, C).

Subset
A set A is a subset of B, which means that A is a subset of and/or the same as B if every element of A is an element of B.

The elements of the subset are not ordered. When combinations are considered, order is not considered!

Combination
Combination, containing k objects is a subset consisting of k objects.

We want to write down a formula for calculating the number of combinations of n objects if k objects are taken at the same time.

Combination designations
The number of combinations of n objects, if k objects are taken simultaneously, is denoted n C k .

We call n C k number of combinations . We want to write down a general formula for n C k for any k ≤ n. First, it is true that n C n = 1, because a set with n elements has only one subset with n elements, which is the set itself. Second, n C 1 = n because a set with n elements has only n subsets with 1 element each. Finally, n C 0 = 1 because a set with n elements has only one subset with 0 elements, that is, the empty set ∅. To look at other combinations, let's go back to Example 1 and compare the number of combinations with the number of permutations.

Please note that each combination of 3 elements has 6, or 3!, permutations.
3! . 5 C 3 = 60 = 5 P 3 = 5. 4 . 3,
so
.
In general, the number of combinations of k elements selected from n objects, n C k times permutations of these elements k!, must be equal to the number of permutations of n elements by k elements:
k!. n C k = n P k
n C k = n P k /k!
n C k = (1/k!). n P k
n C k =

Combinations of k objects from n objects
The total number of combinations of k elements from n objects is denoted by n C k , determined by
(1) n C k = ,
or
(2) n C k =

Another type of notation for n C k is binomial coefficient . The reason for this terminology will be clear below.

Binominal coefficient

Example 2 Calculate using formulas (1) and (2).

Solution
a) According to (1),
.
b) According to (2),

Keep in mind that n/k does not mean.

Example 3 Calculate and .

Solution We use formula (1) for the first expression and formula (2) for the second. Then
,
using (1), and
,
using formula (2).

note that
,
and using the result of example 2 gives us
.
It follows that the number of a 5-element subset of a set of 7 elements is the same as the number of a 2-element subset of a set of 7 elements. When 5 elements are selected from a set, they do not include 2 elements. To see this, consider the set (A, B, C, D, E, F, G):


In general, we have the following. This result provides an alternative way to calculate the combination.

Subsets of size k and size
and n C k = n C n-k
The number of subsets of size k of a set with n objects is the same as the number of subsets of size n - k. The number of combinations of k objects from a set of n objects is the same as the number of combinations of n objects taken at the same time.

Now we will solve problems with combinations.

Example 4 Michigan Lottery. Michigan's twice-weekly WINFALL lottery has a jackpot that... at least, equal to 2 million US dollars. For one dollar, a player can cross out any 6 numbers from 1 to 49. If these numbers match those drawn in the lottery, the player wins. (

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 scenarios for the development of events.

Basic formula of combinatorics

Let there be k groups of elements, and the i-th group consists of n i elements. Let's select one element from each group. Then the total number N of 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. There are 20 people present at the parent meeting. 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?