Combinations without repetition. Permutations, placements and combinations. Formulas Placement without repetition formula
UNORDERED ORDERED PARTITIONS WITH FIXED PARTS
Target: To study in practice the methodology for calculating the number of permutations without repetitions and with repetitions
Task 4 () .
Task 5 ( number of permutations with repetitions).
Task 6 ( number of unordered partitions with fixed sizes of parts ) .
Task 7 () .
Task 4 ( number of permutations without repetitions ) .
How many different n n pieces of digits: 1,3,5,7,9?
NUMBER OF PERMUTATIONS WITHOUT REPETITIONS . BRIEF THEORY
Permutations without repetition or just permutations of elements P different types are called their sequences that differ from each other only in order elements included in them. (Here and below, under the sequence of P elements is understood as their linearly ordered set, similar to P books lined up on a shelf.
Example. Permutations of 3 different elements a, b and with: abs, bca, sab, cba, bas, acb.
The number of all permutations from P various elements (denoted R p) There is P n = 1 2 3 ... n = P!(P! read "en-factorial").
The table below shows the numerical values of the factorials of the first natural numbers and zero.
Table. Values of factorials of the first natural numbers and zero.
n= | |||||||||||
n!= |
END OF THEORY.
Solution.
IN task 4n= 5, because they are rearranged in all sorts of ways n\u003d 5 pieces of different numbers: 1,3,5,7,9. In this case, each new permutation of digits corresponds to a new telephone number (a natural number). Therefore, the desired number of different telephone numbers is equal to the number of different permutations without repetitions from n=5 pieces of different items.
According to the theory, the desired number is equal to P 5 = 5!= 120 different 5-digit phone numbers.
Answer: 120 different 5-digit phone numbers.
Task 5 (on number of permutations with repetitions.)
How many different n– significant telephone numbers (natural numbers) can be written by rearranging the following set n pieces of numbers: 1,1,1,3,3,5?
NUMBER OF PERMUTATIONS WITH REPETITIONS . BRIEF THEORY
Permutations with repetitions
permutations with repetitions from T elements n various types, including k 1 identical elements of the 1st type, k 2 identical elements of the 2nd type, ... , k n identical elements P th type (k 1 + k 2 + ... + k p= m) , their sequences are called, differing only in the order of their elements.
Example. Permutations of 3 elements, among which 2 identical elements of the type A and 1 element of type b: aab, aba, baa.
Number of permutations from T elements, among which k 1 - identical elements of the 1st type, k2 identical elements of the 2nd type,..., k p - identical elements n-th type [denoted R(m; k1,k2,..., k p)] equals :
R(m; k1,k2,..., k p)= m!/(k 1!k2!... k p!).
For an example of permutations with repetitions of 3 elements, among which 2 are of the same type A and 1 element of type b, we have R(m=3; k1=2,k2=1)= 3!/ (2 !1!).
END OF THEORY.
Solution.
IN task 5m=6, because they are rearranged in all sorts of ways m\u003d 6 pieces of different numbers: 1,1,1,3,3,5, among which there are repeating (identical) ones. In this case, each new permutation of digits corresponds to a new telephone number (a natural number). Therefore, the desired number of different telephone numbers is equal to the number of different permutations with repetitions from m=6 pieces of elements, among which k 1 = 3 identical elements of the 1st type (number 1), k2=2 identical elements of the 2nd type (number 3), k 3=1 identical elements 3 -th type (number 5), equal to R(m; k1,k2,..., k p)= m!/(k 1!k2!... k p!), R(6; 3, 2, 1) = 6!/(3! 2! 1!)= =60.
Answer: R(6; 3, 2, 1) = 60, i.e. 60 different variants of 6-digit telephone numbers (6-digit numbers) containing the number 1 three times, 3 twice and 5 once.
Task 6 ( by the number of unordered partitions with fixed sizes of parts ) .
How many variants can be obtained by dividing a group of five people (of five soldiers) into three subgroups - two subgroups of two people (two submachine gunners each) and one subgroup of one person (one machine gunner)?
UNORDERED PARTITIONS. BRIEF THEORY
Unordered partitionn-element set X is any family X 1 , X 2 ,…, X k ), where 1≤ k≤p; X 1 , X 2 ,…, X k - non-empty pairwise disjoint subsets of the set X , whose union is x.
We call such a partition disordered, So How family- it's unordered totality.
Example. For a set (a, b, c) an unordered partition is, for example, ((a),(b,c)). And ((a),(b,c))=((b,c),(a)).
For a set with P elements will be denoted by D(n; k 1 , k 2 ,…, k n) the number of all such unordered partitions, in which there is k 1 subsets with one element, k 2 subsets with two elements, etc., where k 1 ≥0, k 2 ≥0,…, k n ≥0; k 1 +2 k 2 +…+nk n= n.
END OF THEORY.
Solution.
Each variant is an unordered partition (Ivanov, Petrov, Sidorov, Andreev, Borisov). A set of 5 elements One of the partitioning options ((Ivanov, Petrov), (Sidorov, Andreev), (Borisov))
We have n = 5, k 1 =1, k 2 =2,k 3 =0, k 4 =0, k 5 = 0 (since by condition there are no subgroups of three, four, five people).
Answer: 15 options.
Task 7 ( number of ordered partitions with fixed sizes of parts ) .
In how many ways can three machine gunners, three grenade launchers and four submachine gunners be chosen from ten soldiers (3 machine gunners 3 grenade launchers 4 submachine gunners, 10 soldiers in total)?
ORDERED PARTITIONS . BRIEF THEORY
Ordered partition finite set X With n elements is any tuple kind<X 1 , X 2 ,…, X k >, where 1 ≤ k≤n; X 1 , X 2 ,…, X k- non-empty, pairwise disjoint, subsets of the set x, whose union is x.
We call such a partition orderly, since the elements of the tuple are ordered.
Example. For a set (a, b, c)ordered partition this is for example a tuple<((a),(b,c))>. And<((a),(b,c))>¹<((b,c),(a))>.
For a set with P elements will be denoted by E(n; m 1 , m 2 ,…, m k ,) the number of all such ordered partitions into subsets X 1 , X 2 ,…, X k containing m 1 , m 2 ,…, m k , where m 1 ≥0, m 2 ≥0,…, m k ≥0; m 1 +m 2 +…+ m k = n.
Number all ordered partitions<X 1 , X 2 ,…, X k > sets with P elements into subsets X 1 , X 2 ,…, X k containing m 1 , m 2 ,…, m k , elements, respectively. determined by polynomial formula
Where m 1 ≥1, m 2 ≥1,…, m n ≥1; m 1 + m 2 +…+m k = n.
END OF THEORY.
Solution.
In the task we have ordered partition< X 1 , X 2 , X 3 > sets with ten elements where X 1 - subset machine gunners,X 2- subset grenade launchers,X 3- subset submachine gunners;
That's why n = 10, m 1 = 3, T 2 , = 3, T 3 = 4.
Then everything is
Answer: 4200 options
Let's look at some general terms first.
- Let some collection contain n elements, from which k elements are chosen. Each such set will be called sample size k of n elements.
- We will distinguish samples with and without return. Let there be a set of n numbered elements:
- if the selected element after the selection is not returned to the original population and cannot be repeated in this sample more than once, then such sampling is called sampling without replacement or without repetition;
- if the selected element, after fixing the number, returns to the original population again and, thus, may again be in this sample, then one speaks of sampling with return or repetition.
- A selection is said to be ordered if the order of the elements in it is given. If two ordered samples differ only in the order of the elements, then they are considered different (for example: 12 and 21).
- A selection is called unordered if the order of the elements in it does not matter.(i.e. 12 and 21 are indistinguishable).
Placements without repetition.
Non-repeating allocations are ordered selections containing k distinct elements from given n elements.
Let's pay attention to the following important points:
- The order of the elements in the selection is important.
Formula for determining the number of placements without repetitions:
Task. Given a sequence of characters A, B, C. How many variants of a code consisting of two different characters can be made from a given sequence?
Solution. By condition, the code consists of “two different symbols”, while the codes AB and BA are not the same, therefore, the samples are placements without repetitions.
The sample is made from 3 elements by 2. Hence, n = 3, k = 2 .
Indeed, there are only six combinations that satisfy the condition: (AB, AS, BA, BS, SA, SB)
Permutations without repetition.
It is easy to see that arrangements that include all n different elements of a given set (i.e. k = n ) will differ only in the order of the incoming elements. Such arrangements are called permutations.
Permutations without repetitions are called all sorts of ordered samples made up of all given n elements.
Formula for determining the number of permutations without repetition
P n = n! = n * (n − 1) * (n − 2) *...* 2 * 1
Task. How many variants of a code of length 3 characters can be made from three letters A, B, C, if each letter is included in the sequence no more than once?
Solution. Since “each letter is included in the sequence no more than once”, then the selections are permutations without repetitions.
P n = 3! = 3 * 2 * 1 = 6 (ABS, ASB, BAS, BSA, SAB, SBA)
Combinations without repetition.
Combinations without repetitions are called unordered samples containing k different elements from given n elements.
Note that
- ... "samples are unordered", i.e. samples AB and BA are the same combination.
- Any element can appear in any of k places, but it can be used only once in the selection.
Formula for determining the number of combinations without repetitions:
Task. Of the 4 candidates, the conference participants are elected. How many delegation options are there?
Solution. Obviously, the same candidate in a given sample can be elected only once. At the same time, the set A, B and B, A are the same participants. Therefore, samples are combinations without repetitions.
Let's use the formula to calculate the number of different combinations without repetitions:
In this section, three types of connections without repetitions will be considered: placements, permutations and combinations. For the sake of brevity, we will omit the addition “without repetitions”.
1. Accommodations.Placements of n elements by are ordered sets of pairwise distinct elements of the -set . Thus, two arrangements of elements differ either in the order or in the composition of their constituent elements. For example, placements from a 3-set of 2 are exhausted by the following ordered pairs:
, , , , , .
We will be interested the problem of finding the number of all placements from elements by. As the first element, you can choose any of the elements of the set . After the first element is chosen, the second element can be chosen only in ways (you can take any element, excluding the selected one). After selecting the first two elements, there are only options to select the third element, and so on. The last -th element can be chosen in ways - after all, the element has already been selected before it, and therefore only elements remain. By the product rule, we get that the number of all possible ordered sets is equal to the product of numbers , , , …, , i.e. the following
THEOREM 1.The number of placements from elements by is found by the formula
Recall that the product of the first n natural numbers, i.e. , called n-factorial and denote . The product can be written as a fraction = and therefore formula (1) can be rewritten as follows
In particular, for from formula (2) we obtain
This means that there is only one ordered set of length 0, an empty tuple with no components.
Example 1 Find the number of five-digit numbers in the decimal number system, in the record of which the digits do not repeat.
□ Arguing by analogy with how it was done when considering example 1 (2nd method) from § 2, we conclude that the required number is .
2. Permutations. Let us now consider various linear orderings of the given -set . The resulting ordered sets differ from each other only in the order of their constituent elements. They are called permutations(no repeats) of n elements, and their number is denoted by . For example, if , then = 6, since six permutations can be made from three elements:
, , , , , .
The general formula for is obtained from formula (1), since a permutation of elements is the same as a placement without repetitions of elements by . Assuming in (1) we get = = = = . So fair
THEOREM 2.The number of permutations of the elements is equal to -factorial, i.e.
Assuming in formula (2) , we obtain
Comparing (3) and (4), we conclude that 0! = 1. At first glance, this equality seems paradoxical. But for all the equality = is true. If we require that this equality also be valid for , then we obtain . From this it follows again that naturally put 0! = 1.
Example 2 In how many ways can 7 different textbooks be arranged on a shelf so that "Algebra" and "Geometry" do not stand side by side?
□ Let's agree to denote these textbooks for brevity by the letters A and D, respectively. The number of possible ways of arranging textbooks is equal to the number of permutations of seven elements, i.e. . But at the same time, those in which textbooks A and D are found side by side are also counted, and in two positions: AG and GA. Considering AG and GA as one book, for each such arrangement we get arrangements in which textbooks A and D are found side by side. The desired number of arrangements of textbooks is equal to .
3. Combinations. One of the most important tasks of combinatorics is to count the number k-subsets of the given n-sets . Such unordered subsets are called combinations of elements, and their number is denoted by (from the French word combinaison - combination). For example, from the elements of the 4-set it is possible to compose the following 2-sets: , , , , , . The number of these subsets is 6. Therefore, = 6. Note that = 1, since each set has only one 0-set, namely, the empty set . Further, it is clear that = , since the -set contains singleton subsets. It is also clear that .
We derive a formula expressing through and . To do this, we specify a method for obtaining all placements from elements by . Let's choose any k-subset of the given n-sets . This can be done in ways. Each such k- subset is ordered in all possible ways. There are as many such different orderings as there are permutations of elements, i.e. = . It is clear that in this way all placements from elements by . Hence, the equality = takes place. This implies the validity of the following assertion.
THEOREM 3.The number of combinations of n elements by k is calculated by the formula:
= = = . (5)
Example 3 Find the number of all diagonals of a correct n-gon.
□ Any two vertices n-gons uniquely determine the segment connecting these vertices. Therefore, the number of possible segments connecting the vertices n-gon is equal to the number of combinations of 2 each, i.e. . But among them are the sides n-gons that are not diagonals,
So the desired number is
.
For example, when we get that a regular 10-gon has = 35 diagonals.
combination properties.
□ Indeed, due to formula (5) we have
= = = .
□ Indeed,
= = = . =
Directly properties - combinations follow the following
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?
Solution: 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 -
V) - 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:
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 the element $a_1$ is repeated $k_1$ times, $a_2$ is repeated $k_2$ times, and so on, until 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.