Possible combinations. Combinations

Consider the problem of counting the number of samples from a given set in general terms. Let there be some set N, consisting of n elements. Any subset of m elements can be considered without taking into account their order, and with it, i.e. when changing the order, go to another m- sampling.

We formulate the following definitions:

Placements without repetition

By placing without repeating outn elements bym Ncontainingmvarious elements.

It follows from the definition that two arrangements differ from each other, both in 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.

It follows from this definition that two permutations differ only in the order of the elements and can be considered as a special case of arrangements.

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

Combinations without repetition

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

It follows from the definition that 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

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

Decision: a) First of all, you need to choose 5 people out of 7 to sit on the chairs. It can be done
way. With each choice of a particular five, one can produce
permutations in places. According to the multiplication theorem, the desired number of landing methods is equal.

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

b) The solution is obvious -

in) - the number of choices of occupied chairs.

- the number of placements of three people on three selected chairs.

The total number of choices is .

It's not hard to check the formulas
;

;

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

Placements with repetition

Placement with repetition fromn elements bym is any ordered subset of a setN, consisting ofm elements so that any element can be included in this subset from 1 tomtimes, or not at all.

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

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

Comment: Obviously, arrangements with repetition can also be considered for
.

Example 3. It is required from the letters (a, b) to compose all possible words of length 3. In how many ways can this be done?

Answer:

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 make it possible to calculate the fundamentally possible number of different scenarios for the development of events.

Basic combinatorics formula

Let there be k groups of elements, and the i-th group consists of n i elements. Let's choose 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, the first group consisting of n 1 elements, and the second - of n 2 elements. How many different pairs of elements can be made from these two groups so that the pair contains one element from each group? Suppose 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 are 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, there will be n 1 *n 2 possible options.

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?
Decision: n 1 \u003d 6 (since you can take any digit from 1, 2, 3, 4, 5, 6 as the first digit), n 2 \u003d 7 (since you can take any digit from 0 as the second digit , 1, 2, 3, 4, 5, 6), n 3 \u003d 4 (since you can take any digit from 0, 2, 4, 6 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 choice is made from the same group, and the element returns to the group after the choice. Then the number of all ways of choosing is equal to n k . This way of choosing in combinatorics is called return samples.

Example 3 How many four-digit numbers can be made from the numbers 1, 5, 6, 7, 8?
Decision. There are five possibilities for each digit of a four-digit number, so N=5*5*5*5=5 4 =625.

Consider a set consisting of n elements. This set in combinatorics is called general population.

Number of placements from n elements by m

Definition 1. Accommodation from n elements by m in combinatorics is called any ordered set from m various elements selected from the general population in n elements.

Example 4 Different arrangements of three elements (1, 2, 3) two by two will be sets (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2 ). Placements can 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?
Decision: because there are five odd digits, namely 1, 3, 5, 7, 9, then this problem is reduced to choosing and placing two of the five different digits in two different positions, i.e. the given numbers will be:

Definition 2. Combination from n elements by m in combinatorics is called any unordered set from m various elements selected from the general 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 by m

The number of combinations is denoted by C n m and is calculated by the formula:

Example 7 In how many ways can the reader choose two books out of six available?

Decision: The number of ways is equal to the number of combinations of six books by two, i.e. equals:

Permutations of n elements

Definition 3. Permutation from n elements is 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 a row on a shelf?

Decision: 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 principle of counting and the formulas themselves are different. Looking closely at the definitions, you can see that the result depends on several factors at the same time.

Firstly, from how many elements we can combine their sets (how large is the general population of elements).

Secondly, the result depends on what size sets of elements we need.

Finally, it is important to know whether the order of the elements in the set is significant for us. Let us explain the last factor with the following example.

Example 9 There are 20 people at the parent meeting. How many different options for the composition of the parent committee are there if it should include 5 people?
Decision: In this example, we are not interested in the order of the names on the committee list. If, as a result, the same people appear in its composition, then in terms of meaning for us this is the same option. Therefore, we can use the formula to calculate the number combinations out of 20 elements, 5.

Things will be different if each member of the committee is initially responsible for a certain area of work. Then, with the same payroll of the committee, 5 are possible inside it! options permutations that matter. The number of different (both in terms of composition and area of responsibility) options is determined in this case by the number placements out of 20 elements, 5.

Tasks for self-test
1. How many three-digit even numbers can be made from the numbers 0, 1, 2, 3, 4, 5, 6 if the numbers can be repeated?

2. How many five-digit numbers are there that read the same way 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 make a schedule for one day?

4. In how many ways can 4 delegates be chosen for the conference if there are 20 people in the group?

5. In how many ways can eight different letters be put into eight different envelopes if only one letter is placed in each envelope?

6. From three mathematicians and ten economists it is necessary to make a commission consisting of two mathematicians and six economists. In how many ways can this be done?

It should be noted that combinatorics is an independent section of higher mathematics (and not a part of terver) and weighty textbooks have been written in this discipline, the content of which, at times, is no easier than abstract algebra. However, a small share of theoretical knowledge will be enough for us, and in this article I will try to analyze the basics of the topic with typical combinatorial problems in an accessible form. 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, a soldering iron and a marsh frog. It is fundamentally important that these objects are enumerable - there are three of them. (discreteness) and it is essential that none of them are alike.

With a lot sorted out, now about the 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

Do not be afraid of obscure terms, especially since some of them are really not very successful. Let's start with the tail of the title - what does " without repetition"? 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, something tastier is better =) Imagine that an apple, a pear and a banana materialized on the table in front of you (if there are any, the situation can be simulated in real). 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.

Well, it was not difficult to list all possible cases here, but what if there are more objects? Already with four different fruits, the number of combinations will increase significantly!

Please open reference material (Manual is easy to print) and in paragraph number 2, find the formula for the number of permutations.

No torment - 3 objects can be rearranged in 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 they worked up an appetite in the previous paragraph - in order to eat! =)

a) One fruit can be chosen, obviously, in three ways - take either an apple, or a pear, or a banana. The formal count is based on 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) We list all possible combinations of two fruits:

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

The number of combinations is easy to check using the same formula:

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

c) And finally, three fruits can be chosen in a unique way:

By the way, the formula for the number of combinations also makes sense 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 “at least one” condition implies that we are satisfied with 1 fruit (any) or any 2 fruits or all 3 fruits:
ways you can choose at least one fruit.

Readers who have carefully studied the introductory lesson on probability theory already figured something out. But about the meaning of the plus sign later.

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

Question three: In how many ways can one fruit be distributed to Dasha and Natasha?

In order to distribute two fruits, you must first select them. According to paragraph "be" of the previous question, this can be done in ways, I will rewrite them again:

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 every 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?

Ways you can choose 1 young man;
ways you can choose 1 girl.

So one young man and one girl can be chosen: ways.

When 1 object is selected from each set, then the following principle of counting combinations is valid: “ everyone 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 - also any of the thirteen, and other young people have a similar choice. Total: possible pairs.

It should be noted that in this example, the "history" of pair formation does not matter; however, if initiative is taken into account, then 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 two young men be chosen and two girls to participate in a KVN skit?

Union And hints unambiguously that the combinations must be multiplied:

Possible groups of artists.

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

The multiplication rule applies to more multipliers:

Task 8

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

Decision: for clarity, we denote this number with three asterisks: ***

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

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

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

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

At the same time, the work is deciphered as follows: “9 ways you can choose a number in hundreds place and 10 ways to select a number in tens place and 2 ways in unit digit»

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

Answer: 180

And now…

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

And now the problem for an independent solution ... now I’ll come up with something more interesting, ... let it be about the same Russian version of blackjack:

Task 9

How many winning combinations of 2 cards are there in a "point" game?

For those who don't know: wins combination 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)

Short solution and answer at the end of the lesson.

By the way, it is not necessary to consider an example primitive. Blackjack is almost the only game for which there is a mathematically justified algorithm that allows you to beat the casino. Those who wish can easily find a lot of information about the optimal strategy and tactics. True, such masters quickly fall into the black list of all establishments =)

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

Task 10

Vasya has 4 cats at home.

a) In how many ways can the cats be seated in the corners of the room?
b) In how many ways can cats be allowed to roam?
c) in how many ways can Vasya pick up two cats (one on the left, the other on the right)?

We decide: first, it should again be noted that the problem is about different objects (even if the cats are identical twins). This is a very important condition!

a) Silence of cats. This execution is subject to all cats at once
+ their location is important, so there are permutations here:
ways you can seat cats in the corners of the room.

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

b) In how many ways can cats be allowed to roam?

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

We consider all possible combinations:

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

You probably guessed that the obtained values should be summed up:
ways to let cats go for a walk.

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 of the 10th floor. There will be more combinations!

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

The situation involves not only the choice of 2 animals, but also their placement on the hands:
ways you can pick up 2 cats.

The second solution: in ways you can choose two cats and ways to plant every a couple in hand:

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

Well, to clear my conscience, something more specific on the multiplication of combinations .... Let Vasya have 5 extra cats =) 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 an independent solution:

Task 11

3 passengers got into the elevator of a 12-storey building. Everyone, independently of the others, can exit on any (starting from the 2nd) floor with the same probability. In how many ways:

1) Passengers can get off at the same floor (exit order doesn't matter);
2) two people can get off on one floor and a third on another;
3) people can get off at different floors;
4) Can passengers exit the elevator?

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

Complete solution with detailed comments at the end of the tutorial.

The final paragraph is devoted to combinations that also occur quite often - according to my subjective assessment, in about 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 on 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, the whole set of objects at once, but there is one thing: in this set, one or more elements (objects) are repeated. Meet the next standard:

Task 12

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

Decision: in the event that all letters were different, then a trivial formula should be applied, however, it is quite clear that for the proposed set of cards, some manipulations will work "idle", so, for example, if you swap any two cards with the letters "K in any word, it will be the same word. Moreover, physically the cards can be very different: one can be round with a printed letter “K”, the other is square with a drawn letter “K”. But according to the meaning of the problem, even such cards considered the same, since the condition asks about letter combinations.

Everything is extremely simple - in total: 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 - repeats 1 time.

Check: 3 + 3 + 2 + 1 + 1 + 1 = 11, which is what we wanted to check.

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

For a quick calculation of a large factorial value, it is convenient to use the standard Excel function: we score in any cell =FACT(11) and click Enter.

In practice, it is quite acceptable not to write down 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 repetitions is found in the problem of arranging chess pieces, 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 template task:

Task 13

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

The formula doesn't work here because it takes into account overlapping permutations (for example, when strength exercises on Wednesday are swapped with strength exercises on Thursday). And again - in fact, the same 2 strength training sessions can be very different from each other, but in the context of the task (in terms 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 the same objects.

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

Task 14

The student cafeteria sells sausages in dough, cheesecakes and donuts. In how many ways can five cakes be purchased?

Decision: immediately pay attention to the typical criterion for combinations with repetitions - according to the condition, not a set of objects as such, 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, of course, are different - because absolutely identical donuts can only be simulated on a computer =) However, the physical characteristics of the pies are not essential in the sense of the problem, and hot dogs / cheesecakes / donuts in their groups are considered the same.

What can be in the sample? First of all, it should be noted that there will definitely be identical pies in the sample (because we choose 5 pieces, and 3 types are offered to choose from). 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 sample does not matter - they just chose 5 pieces and that's it.

We use the formula number of combinations with repetitions:
way you can buy 5 pies.

Bon appetit!

Answer: 21

What conclusion can be drawn from many combinatorial problems?

Sometimes, the most difficult thing is to understand the condition.

A similar example for a do-it-yourself solution:

Task 15

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

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

1) Can all coins in the sample be different?
2) Name the "cheapest" and the 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 sample is important. And everything would be fine, but a rather unexpected joke is that we can choose any object of the original set as many times as we like. Figuratively speaking, from "the multitude will not decrease."

When does it happen? A typical example is a combination lock with several disks, but due to the development of technology, it is more relevant to consider its digital descendant:

Task 16

How many 4-digit pin codes are there?

Decision: in fact, to solve the problem, it is enough to know the rules of combinatorics: you can choose the first digit of the pin code in ways and ways - the second digit of the pin code and in as many ways - a third and as many - the fourth. Thus, according to the rule of multiplication of combinations, a four-digit pin code can be composed: in ways.

And now with the formula. By condition, we are offered a set of numbers, from which numbers are selected and placed in a certain order, while the numbers in the sample can 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 illusory.

And who said that there is no practical sense in combinatorics? 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 not allowed, and the letters are selected from the set A, B, E, K, M, H, O, R, C, T, U, X (only those Cyrillic letters are used, the spelling of which matches the Latin letters).

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

Not so, by the way, and a lot. In large regions, this number is not enough, and therefore for them there are several codes for the inscription RUS.

Solution and answer at the end of the lesson. Don't forget to use the rules of combinatorics ;-) …I wanted to brag about being exclusive, but it turned out to be not exclusive =) I looked at Wikipedia - there are calculations there, however, without comments. Although for educational purposes, probably, few people solved it.

Our fascinating lesson has come to an end, and in the end I want to say that you did not waste your time - for the reason that combinatorics formulas find another vital practical application: they are found in various tasks on probability theory,
and in tasks on the classical definition of probability- especially often

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

Solutions and answers:

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

When a card with a zero is in 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 least significant digits can be rearranged in ways.

Note : because there are few cards, it is easy to list all such options here:
0579
0597
0759
0795
0957
0975

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

Task 4: Decision: 3 cards can be selected from 36 ways.
Answer : 7140

Task 6: Decision: 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” set contains 3 ten-ruble coins.

Task 17: Decision: ways you can make a digital combination of a license plate, while one of them (000) should be excluded:.
ways you can make a letter combination of a car number.
According to the rule of multiplication of combinations, everything can be composed:
car numbers
(each digital combination combined with each letter combination).
Answer : 1726272

To make it easier to navigate the material, I will add the content of this topic:

Introduction. Sets and selections.

In this topic, we will consider the basic concepts of combinatorics: permutations, combinations and placements. Let's find out their essence and formulas by which you can find their number.

To get started, we need some background information. Let's start with such a fundamental mathematical concept as a set. The concept of a set was described in detail in the topic "The concept of a set. Methods for specifying sets" .

A very short story about the multitude: show/hide

In short, a set is a collection of objects. Sets are written in curly brackets. The order in which the elements are written does not matter; repetition of elements is not allowed. For example, the set of digits of the number 11115555999 will be: $$1,5,9 $$. The set of consonant letters in the word "tiger cub" is as follows: $$t, r, r, n, k$$. The notation $5\in A$ means that element 5 belongs to the set $A=$1,5,9 $$. The number of elements in a finite set is called power of this set and are denoted by $|A|$. For example, for a set $A=$1,5,9 $$ containing 3 elements, we have: $|A|=3$.

Let us consider some non-empty finite set $U$, the cardinality of which is equal to $n$, $|U|=n$ (that is, the set $U$ has $n$ elements). Let us introduce such a concept as sample(some authors call it a tuple). By a sample of size $k$ of $n$ elements (abbreviated as $(n,k)$-selection) we mean a set of elements $(a_1, a_2,\ldots, a_k)$, where $a_i\in U$. A selection is said to be ordered if the order of the elements is specified in it. Two ordered samples that differ only in the order of the elements are distinct. If the order of the elements of the sample is not significant, then the sample is called unordered.

Notice that the selection definition doesn't say anything about item repetitions. Unlike set elements, selection elements can be repeated.

For example, consider the set $U=$a,b,c,d,e$$. The set $U$ contains 5 elements, i.e. $|U|=5$. A sample without repetitions could be: $(a,b,c)$. This sample contains 3 elements, i.e. the size of this sample is 3. In other words, this is a $(5,3)$-sample.

A sample with repetitions could be: $(a,a,a,a,a,c,c,d)$. It contains 8 elements, i.e. its volume is 8. In other words, this is a $(5,8)$-sample.

Consider two more $(5,3)$-samples: $(a,b,b)$ and $(b,a,b)$. If we assume that our samples are unordered, then the sample $(a,b,b)$ is equal to the sample $(b,a,b)$, i.e. $(a,b,b)=(b,a,b)$. If we assume our samples are ordered, then $(a,b,b)\neq(b,a,b)$.

Let's look at another example, a little less abstract :) Suppose there are six candies in a basket, and all of them are different. If the first candy is assigned the number 1, the second candy is the number 2, and so on, then the following set can be associated with the candies in the basket: $U=$1,2,3,4,5,6$$. Imagine that we randomly put our hand into the basket in order to pull out three sweets. The pulled out sweets - this is the sample. Since we are pulling out 3 candies from 6, we get a (6,3)-sample. The order in which the candies are placed in the palm is completely irrelevant, so this sample is unordered. Well, and since all candies are different, the sample is without repetition. So, in this situation we are talking about an unordered (6,3)-selection without repetitions.

Now let's go from the other side. Let's imagine that we are in a candy factory, and this factory produces four types of candy. The set $U$ in this situation is as follows: $U=$1,2,3,4 $$ (each digit is responsible for its own kind of candy). Now imagine that all the sweets are poured into a single chute, near which we are standing. And, substituting the palms, we select 20 sweets from this stream. Candy in a handful - this is the sample. Does the order of the candies in the handful play a role? Naturally, no, so the sample is unordered. There are only 4 varieties of sweets, and we select twenty pieces from the general flow - repetitions of varieties are inevitable. At the same time, the samples can be very different: we may even have all the candies of the same variety. Consequently, in this situation we are dealing with an unordered (4.20)-selection with repetitions.

Let's look at a couple more examples. Let different 7 letters be written on the cubes: k, o, n, f, e, t, a. These letters form the set $U=$k,o,n,f,e,t,a$$. Suppose we want to make "words" of 5 letters from these cubes. The letters of these words (for example, "confé", "tenko" and so on) form (7,5)-selections: $(k,o,n,f,e)$, $(t,e,n,k ,o)$ etc. Obviously, the order of the letters in such a sample is important. For example, the words "nokft" and "kfton" are different (although they consist of the same letters), because they do not have the same order of letters. There are no repetitions of letters in such “words”, because there are only seven cubes. So, the set of letters of each word is an ordered (7,5)-sample without repetitions.

Another example: we make all kinds of eight-digit numbers from four digits 1, 5, 7, 8. For example, 11111111, 15518877, 88881111 and so on. The set $U$ is as follows: $U=$1,5,7,8$$. The digits of each compiled number form a (4,8)-sample. The order of the digits in a number is important, i.e. the sample is ordered. Repetitions are allowed, so here we are dealing with an ordered (4,8)-selection with repetitions.

Allocations without repetitions of $n$ elements by $k$

Allocation without repetitions of $n$ elements by $k$ - ordered $(n,k)$-selection without repetitions.

Since the elements in the sample under consideration cannot be repeated, we cannot select more elements in the sample than there are in the original set. Therefore, for such samples, the following inequality is true: $n≥ k$. The number of placements without repetitions of $n$ elements by $k$ is determined by the following formula:

\begin(equation)A_(n)^(k)=\frac(n{(n-k)!} \end{equation} !}

What does the sign "!" mean?: show/hide

Recording "n!" (read "en factorial") denotes the product of all numbers from 1 to n, i.e.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

By definition, it is assumed that $0!=1!=1$. For example, let's find 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Example #1

The alphabet consists of a set of characters $E=$+,*,0,1,f$$. Let's determine the number of such three-character words in this alphabet that do not contain repeated letters.

By three-character words we mean expressions like "+*0" or "0f1". The set $E$ has five elements, so the letters of the three-character words form (5,3)-selections. The first question is: are these samples ordered or not? Words that differ only in the order of the letters are assumed to be different, so the order of the elements in the sample is important. So the sample is ordered. Second question: are repetitions allowed or not? The answer to this question is given by the condition: words should not contain repeated letters. Summing up: the letters of each word that satisfies the condition of the problem form an ordered (5,3)-sample without repetitions. In other words, the letters of each word form an arrangement without repetitions of 5 elements of 3. Here are examples of such arrangements:

$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$

We are also interested in the total number of these placements. According to formula (1), the number of placements without repetitions of 5 elements by 3 will be as follows:

$$ A_(5)^(3)=\frac(5{(5-3)!}=\frac{5!}{2!}=60. $$ !}

Those. you can make 60 three-character words, the letters of which will not be repeated.

Answer: 60.

Allocations with repetitions of $n$ elements by $k$

Placement with repetitions of $n$ elements over $k$ is an ordered $(n,k)$-selection with repetitions.

The number of placements with repetitions of $n$ elements by $k$ is determined by the following formula:

\begin(equation)\bar(A)_(n)^(k)=n^k \end(equation)

Example #2

How many five-digit numbers can be formed from the set of digits $$5,7,2$$?

From this set of numbers, you can make five-digit numbers 55555, 75222 and so on. The digits of each such number form a (3,5)-sample: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Let us ask ourselves: what are these samples? First, digits in numbers can be repeated, so we are dealing with samples with repetitions. Secondly, the order of the numbers in the number is important. For example, 27755 and 77255 are different numbers. Therefore, we are dealing with ordered (3,5)-selections with repetitions. The total number of such samples (i.e. the total number of required five-digit numbers) can be found using formula (2):

$$ \bar(A)_(3)^(5)=3^5=243. $$

Therefore, from the given digits, 243 five-digit numbers can be made.

Answer: 243.

Permutations without repetitions of $n$ elements

A permutation without repetitions of $n$ elements is an ordered $(n,n)$-selection without repetitions.

In fact, permutation without repetition is a special case of placement without repetition, when the sample size is equal to the power of the original set. The number of permutations without repetitions of $n$ elements is determined by the following formula:

\begin(equation)P_(n)=n! \end(equation)

By the way, this formula is easy to obtain if we take into account that $P_n=A_(n)^(n)$. Then we get:

$$ P_n=A_(n)^(n)=\frac(n{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$ !}

Example #3

The freezer contains five servings of ice cream from various companies. In how many ways can you choose the order in which they are eaten?

Let the number 1 correspond to the first ice cream, the number 2 to the second, and so on. We will get a set $U=$1,2,3,4,5$$ which will represent the contents of the freezer. The eating order can be $(2,1,3,5,4)$ or $(5,4,3,1,2)$. Each such collection is a (5,5)-sample. It will be orderly and without repetition. In other words, each such sample is a permutation of 5 elements of the original set. According to formula (3), the total number of these permutations is:

$$ P_5=5!=120. $$

Therefore, there are 120 orders of eating order.

Answer: 120.

Permutations with repetitions

A permutation with repetitions is an ordered $(n,k)$-selection with repetitions in which element $a_1$ is repeated $k_1$ times, $a_2$ is repeated $k_2$ times, and so on, up to the last element $a_r$, which is repeated $ k_r$ times. Moreover, $k_1+k_2+\ldots+k_r=k$.

The total number of permutations with repetitions is given by:

\begin(equation)P_(k)(k_1,k_2,\ldots,k_r)=\frac(k{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation} !}

Example #4

Words are formed on the basis of the alphabet $U=$a,b,d$$. How many different words of seven characters can be composed if the letter "a" must be repeated 2 times in these words; the letter "b" - 1 time, and the letter "d" - 4 times?

Here are examples of search words: "aabdddd", "daddabd" and so on. The letters of each word form a (3,7)-sample with repetitions: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ and etc. Each such selection consists of two "a" elements, one "b" element, and four "d" elements. In other words, $k_1=2$, $k_2=1$, $k_3=4$. The total number of repetitions of all characters, of course, is equal to the sample size, i.e. $k=k_1+k_2+k_3=7$. Substituting these data into formula (4), we will have:

$$ P_7(2,1,4)=\frac(7{2!\cdot 1!\cdot 4!}=105. $$ !}

Therefore, the total number of searched words is 105.

Answer: 105.

Combinations without repetitions of $n$ elements by $k$

A combination without repetitions of $n$ elements by $k$ is an unordered $(n,k)$-selection without repetitions.

The total number of combinations without repetitions of $n$ elements by $k$ is determined by the formula:

\begin(equation)C_(n)^(k)=\frac(n{(n-k)!\cdot k!} \end{equation} !}

Example #5

The basket contains cards on which integers from 1 to 10 are written. 4 cards are taken out of the basket and the numbers written on them are summed up. How many different sets of cards can be drawn from the basket?

So, in this problem, the initial set is as follows: $U=$1,2,3,4,5,6,7,8,9,10$$. From this set, we select four elements (i.e., four cards from the basket). The numbers of the pulled out elements form a (10,4)-sample. Repetitions in this sample are not allowed, since the numbers of all cards are different. The question is: does the order in which cards are chosen matter or not? That is, for example, are the samples $(1,2,7,10)$ and $(10,2,1,7)$ equal or not equal? Here you need to turn to the condition of the problem. Cards are taken out in order to then find the sum of the elements. And this means that the order of the cards is not important, since the amount will not change from changing the places of the terms. For example, the sample $(1,2,7,10)$ and the sample $(10,2,1,7)$ will match the same number $1+2+7+10=10+2+1+7= 20$. Conclusion: it follows from the condition of the problem that we are dealing with unordered samples. Those. we need to find the total number of unordered (10,4)-samples without repetitions. In other words, we need to find the number of combinations of 10 elements by 4. We use formula (5) for this:

$$ C_(10)^(4)=\frac(10{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$ !}

Therefore, the total number of required sets is 210.

Answer: 210.

Combinations with repetitions of $n$ elements by $k$

A combination with repetitions of $n$ elements over $k$ is an unordered $(n,k)$-selection with repetitions.

The total number of combinations with repetitions of $n$ elements over $k$ is determined by the formula:

\begin(equation)\bar(C)_(n)^(k)=\frac((n+k-1){(n-1)!\cdot k!} \end{equation} !}

Example #6

Imagine that we are in a candy factory - right next to the conveyor along which four types of candies move. We put our hands in this stream and pull out twenty of them. How many different "candy combinations" can there be in a handful?

If we assume that the number 1 corresponds to the first sort, the number 2 corresponds to the second sort, and so on, then the initial set in our problem is as follows: $U=$1,2,3,4$$. From this set, we select 20 elements (i.e., those same 20 candies from the conveyor). A handful of sweets forms a (4,20)-sample. Naturally, there will be repetitions of varieties. The question is, does the order of the elements in the selection play a role or not? It follows from the conditions of the problem that the order of the elements does not matter. It makes no difference to us whether the handful contains 15 lollipops first, and then 4 chocolates, or first 4 chocolates, and only then 15 lollipops. So, we are dealing with an unordered (4.20) sample with repetitions. To find the total number of these samples, we use formula (6):

$$ \bar(C)_(4)^(20)=\frac((4+20-1){(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$ !}

Therefore, the total number of desired combinations is 1771.

COMBINATORICS

Combinatorics is a branch of mathematics that studies the problems of choosing and arranging elements from some basic set in accordance with given rules. Formulas and principles of combinatorics are used in probability theory to calculate the probability of random events and, accordingly, to obtain the laws of distribution of random variables. This, in turn, makes it possible to study the laws of mass random phenomena, which is very important for a correct understanding of the statistical laws that manifest themselves in nature and technology.

Rules for addition and multiplication in combinatorics

Sum rule. If two actions A and B are mutually exclusive, and action A can be performed in m ways, and B in n ways, then any one of these actions (either A or B) can be performed in n + m ways.

Example 1

There are 16 boys and 10 girls in the class. In how many ways can one attendant be appointed?

Decision

You can appoint either a boy or a girl on duty, i.e. any of the 16 boys or any of the 10 girls can be on duty.

According to the sum rule, we get that one duty officer can be assigned 16+10=26 ways.

Product rule. Let it be required to perform sequentially k actions. If the first action can be performed in n 1 ways, the second action in n 2 ways, the third in n 3 ways, and so on up to the kth action that can be performed in n k ways, then all k actions together can be performed:

ways.

Example 2

There are 16 boys and 10 girls in the class. In how many ways can two attendants be appointed?

Decision

The first person on duty can be either a boy or a girl. Because there are 16 boys and 10 girls in the class, then you can appoint the first duty officer in 16 + 10 = 26 ways.

After we have chosen the first duty officer, we can choose the second one from the remaining 25 people, i.e. 25 ways.

By the multiplication theorem, two attendants can be chosen in 26*25=650 ways.

Combinations without repetition. Combinations with repetitions

The classical problem of combinatorics is the problem of the number of combinations without repetitions, the content of which can be expressed by the question: how many ways can choose m from n different items?

Example 3

You must choose 4 of the 10 different books available as a gift. In how many ways can this be done?

Decision

We need to choose 4 out of 10 books, and the order of choice does not matter. Thus, you need to find the number of combinations of 10 elements by 4:

Consider the problem of the number of combinations with repetitions: there are r identical objects of each of n different types; how many ways can choose m() of these (n*r) items?

Example 4

The pastry shop sold 4 types of cakes: napoleons, eclairs, shortbread and puff. In how many ways can 7 cakes be bought?

Decision

Because among 7 cakes there can be cakes of the same variety, then the number of ways in which 7 cakes can be bought is determined by the number of combinations with repetitions from 7 to 4.

Placements without repetition. Placements with repetitions

The classical problem of combinatorics is the problem of the number of placements without repetitions, the content of which can be expressed by the question: how many ways can choose and place on m different places m from n different items?

Example 5

Some newspaper has 12 pages. It is necessary to place four photographs on the pages of this newspaper. In how many ways can this be done if no page of the newspaper should contain more than one photograph?

Decision.

In this problem, we do not just select photos, but place them on certain pages of the newspaper, and each page of the newspaper should contain no more than one photo. Thus, the problem is reduced to the classical problem of determining the number of placements without repetitions from 12 elements by 4 elements:

Thus, 4 photos on 12 pages can be arranged in 11880 ways.

Also, the classical task of combinatorics is the problem of the number of placements with repetitions, the content of which can be expressed by the question: how many ways can youbarmy and place on m different places m from n itemswithredi which there is the same?

Example 6

The boy had stamps with the numbers 1, 3 and 7 from the set for the board game. He decided to use these stamps to put five-digit numbers on all the books - to compile a catalog. How many different five-digit numbers can the boy make?

Permutations without repetition. Permutations with repetitions

The classical problem of combinatorics is the problem of the number of permutations without repetition, the content of which can be expressed by the question: how many ways can place n various items on the n different places?

Example 7

How many four-letter "words" can be made from the letters of the word "marriage"?

Decision

The general set is 4 letters of the word "marriage" (b, p, a, k). The number of "words" is determined by the permutations of these 4 letters, i.e.

For the case when among the selected n elements there are the same (selection with return), the problem of the number of permutations with repetitions can be expressed by the question: In how many ways can n objects be rearranged in n different places if among n objects there are k different types (k< n), т. е. есть одинаковые предметы.

Example 8

How many different letter combinations can be made from the letters of the word "Mississippi"?

Decision

There is 1 letter "m", 4 letters "i", 3 letters "c" and 1 letter "p", 9 letters in total. Therefore, the number of permutations with repetitions is

BACKGROUND SUMMARY ON THE SECTION "COMBINATORICS"