Any of the N elements can take the first place in the row, therefore, N options are obtained. In second place - any, except for the one that has already been used for first place. Therefore, for each of the N options already found, there are (N - 1) second place options, and the total number of combinations becomes N*(N - 1).
The same can be repeated for the remaining elements of the series. For the very last place, there is only one option left - the last remaining element. For the penultimate - two options, and so on.
Therefore, for a series of N non-repeating elements, the possible permutations are equal to the product of all integers from 1 to N. This product is called N and N! (read "en factorial").
In the previous case, the number possible elements and the number of places in the series coincided, and their number was equal to N. But a situation is possible when there are fewer places in the series than there are possible elements. In other words, the number of elements in the sample is equal to some number M, and M< N. В этом случае задача определения возможных комбинаций может иметь два различных варианта.
First, it may be necessary to count the total possible ways, with which you can line up M elements from N. Such methods are placements.
Secondly, the researcher may be interested in the number of ways in which M elements can be chosen from N. In this case, the order of the elements is no longer important, but any two options must differ from each other by at least one element. Such methods are called combinations.
To find the number of placements by M elements out of N, one can resort to the same way of reasoning as in the case of permutations. In the first place, there can still be N elements, in the second (N - 1), and so on. But for the last place, the number of possible options is not one, but (N - M + 1), because when the placement is completed, there will still be (N - M) unused elements.
Thus, the number of placements over M elements from N is equal to the product of all integers from (N - M + 1) to N, or, equivalently, the quotient N!/(N - M)!.
Obviously, the number of combinations of M elements from N will be less than the number of placements. For every possible combination, there is an M! possible placements depending on the order of the elements of this combination. Therefore, to find this number, you need to divide the number of placements over M elements from N by N!. In other words, the number of combinations of M elements from N is N!/(M!*(N - M)!).
Sources:
- number of combinations
Factorial natural number is the product of all previous natural numbers, including the number itself. Factorial zero is equal to one. It seems that calculating the factorial of a number is very simple - it is enough to multiply all natural numbers that do not exceed the given one. However, the value of the factorial increases so rapidly that some calculators cannot cope with this task.
You will need
- calculator, computer
Instruction
To calculate the factorial of a natural number, multiply all that do not exceed the given number. Each number is counted only once. In the form of a formula, this can be written as follows: n! = 1*2*3*4*5*…*(n-2)*(n-1)*n, where n is a natural number whose factorial is to be calculated.
0! is taken equal to one (0!=1). As the argument increases, the value of the factorial increases very quickly, so the usual (accounting) factorial of 15 instead of the result may give an error.
To calculate the factorial of a large natural number, take an engineering calculator. That is, such a calculator on the keyboard of which there are symbols of mathematical functions (cos, sin, √). Enter the original number on the calculator, and then click the factorial button. Usually a button like "n!" or similar (instead of "n" it can be "N" or "x", but the exclamation mark "!" in the notation of the factorial must be present in any case).
At large values argument, the results of calculations begin to be displayed in an "exponential" (exponential) form. So, for example, the factorial of 50 would be in the form: 3.0414093201713378043612608166065e+64 (or similar). To get the result of calculations in the usual form, add as many zeros to the number shown before the symbol "e" as indicated after "e +" (if, of course, there is enough space).
We sometimes choose from many regardless of order. Such a 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).
Decision These combinations are:
(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 the objects is not considered. Then,
(A, C, B) is called the same set as (A, B, C).
Subset
The set A is a subset of B, and means that A is a subset and/or the same as B if every element of A is an element of B.
The elements of a 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 a formula to calculate the number of combinations of n objects if k objects are taken at the same time.
Combination notation
The number of combinations of n objects, if taken at the same time, is denoted by n C k .
We call n C k number of combinations . We want to write 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, 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 consider other combinations, let's go back to Example 1 and compare the number of combinations with the number of permutations.
Note that each combination of 3 elements has 6, or 3!, permutations.
3! . 5 C 3 \u003d 60 \u003d 5 P 3 \u003d 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 over k elements:
k!. n C k = n P k
n C k = n P k /k!
n C k = (1/k!). nP k
n Ck = 
Combinations of k objects out of 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 become clear below.
Binomial coefficient
Example 2 Calculate using formulas (1) and (2).
Decision
a) According to (1), 
.
b) According to (2), 
Keep in mind that does not mean n/k.
Example 3 Calculate and .
Decision 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
.
This implies 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 gives alternative way combination calculations.
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. Held in Michigan twice a week, WINFALL has a jackpot of at least $2 million. For one dollar, the player can cross out any 6 numbers from 1 to 49. If these numbers match those that fall during the lottery, the player wins. (
Number of combinations
combination from n on k called a set k elements selected from the data n elements. Sets that differ only in the order of the elements (but not in composition) are considered the same; this is how combinations differ from placements.
Explicit formulas
Number of combinations from n on k is equal to the binomial coefficient
For a fixed value n generating function of the numbers of combinations with repetitions from n on k is an:
The two-dimensional generating function of the numbers of combinations with repetitions is:
Links
- R. Stanley Enumerative combinatorics. - M.: Mir, 1990.
- Calculating the number of combinations online
Wikimedia Foundation. 2010 .
See what the "Number of combinations" is in other dictionaries:
70 seventy 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Factorization: 2×5×7 Roman notation: LXX Binary: 100 0110 ... Wikipedia
Light number, a conditional number that uniquely expresses external. conditions during photography (usually the brightness of the subject and the sensitivity of the photographic material used). Any value of E. h. can be selected several. f-number combinations ... ... Big encyclopedic polytechnic dictionary
A form of number that distinguishes two objects both in relation to a single object and in relation to a multitude of objects. This form does not exist in modern Russian, but remnants of its influence have been preserved. So, combinations of two tables (cf. plural ... ... Dictionary of linguistic terms
Combinatorial mathematics, combinatorics, a branch of mathematics devoted to solving problems of choosing and arranging elements of a certain, usually finite, set in accordance with given rules. Each such rule determines the way of constructing ... ... Mathematical Encyclopedia
In combinatorics, a combination of by is a set of elements selected from a given set containing different elements. Sets that differ only in the order of the elements (but not in composition) are considered the same, these combinations ... ... Wikipedia
Engaged in the study of events, the occurrence of which is not known for certain. It allows you to judge the reasonableness of expecting the occurrence of some events compared to others, although attributing numerical values to the probabilities of events is often redundant ... ... Collier Encyclopedia
1) the same as mathematical combinatorial analysis. 2) Section elementary mathematics, associated with the study of the number of combinations subject to certain conditions that can be composed from a given finite set of objects ... ... Great Soviet Encyclopedia
- (Greek paradoxos unexpected, strange) in a broad sense: a statement that is sharply at odds with the generally accepted, established opinion, the denial of what seems to be “undoubtedly correct”; in a narrower sense, two opposite statements, for ... ... Philosophical Encyclopedia
- (or the principle of inclusions of exclusions) a combinatorial formula that allows you to determine the power of the union of a finite number of finite sets, which in the general case can intersect with each other ... Wikipedia
Mathematical theory dealing with the definition of a number various ways distribution of these items in a known order; is of particular importance in the theory of equations and in the theory of probability. The simplest tasks of this kind are ... ... encyclopedic Dictionary F. Brockhaus and I.A. Efron
Books
- Destiny number. Horoscope of compatibility. Desires. Passion. Fantasies (number of volumes: 3), Maier Maxim. Destiny number. How to make an individual numerological forecast. Numerology is one of the most ancient esoteric systems. It is impossible to accurately determine the time of its occurrence. However, in…
A combination is an unordered selection of elements of a finite set with a fixed number and without repetition of elements. Different combinations must differ by 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), 10 different combinations of 3 letters can be formed, 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 each, making the following unordered pairs:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
However, if you combine the same Latin vowels by 4, then you get only the following 5 different combinations:
AEIO, AEIU, AIOU, EIOU, AEOU.
In the general case, to denote the number of combinations of n different elements by m elements, the following functional, index or vector (Appel) symbolism is used:
Regardless of the form of designation, the number of combinations of n elements by m elements can be determined by 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 above example with combinations of Latin vowels. In particular, for 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 limit numbers of combinations, which are easy to check 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. However, then the result of the calculation on it, while maintaining formal validity, loses its combinatorial meaning.
COMBINATION IDENTITIES
The practical use of multiplicative and factorial formulas for determining the number of combinations for arbitrary values of n and m is not very productive 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 possibilities of representing integers in modern computing and software systems. At the same time, their values turn out to be much larger 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 the much larger values of 10! in the numerator and 8! in the denominator:
To exclude time-consuming operations of processing large values, to determine the number of combinations, you can use various recurrence relations that 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 lower index unchanged 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 parts of the first 2 formulas and reduce the result by n, then we get an important recurrence relation, which is called the identity of adding the numbers of combinations:
The addition identity provides a basic recursive rule for effective definition the number of combinations for large values of n and m, since it allows us to replace the multiplication operations in factorial products with 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 considered above, by performing the following sequence of recurrent transformations:
In addition, several useful relations can be derived from the addition identity for calculating finite sums, in particular, the subscript summation formula, which has the following form:
Such a relationship is obtained by expanding the recurrence in the addition identity over the term with the largest superscript, as long as its subscript is greater than 0. The following numerical example illustrates the indicated process of recursive 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 option summation formulas can be obtained by expanding the recurrence of the addition identity over the term with the smallest superscript. The following numerical example illustrates this variant 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 neighboring terms, and the difference of the indices remains constant (in the considered example, it is also equal to one). Thus, the following summation formula over both indices of combination numbers is obtained:
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 has the following form:
The validity of the symmetry identity can be seen 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, while determining the number of options for choosing 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 mutually replacing m with (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 application is associated with 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 degrees, the desired polynomial can be easily obtained by directly multiplying the 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 the binomial, the desired representation in the form of a polynomial is provided by Newton's binomial theorem, which declares that the following equality holds:
This equality is usually called Newton's binomial. The polynomial on its right side is the sum of the products of the 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 that are obtained from their powers. Given the particular popularity of Newton's binomial formula in combinatorial analysis, the terms binomial coefficient and the number of combinations are usually considered synonymous.
Obviously, the sum square and cube formulas are special cases of the binomial theorem for n=2 and n=3, respectively. To handle higher powers (n>3), Newton's binomial formula should be used. Its application for the 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 common 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 it is customary to write it 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, the Newton binomial formula for any exponent is a particular version of the Maclaurin formula, which gives the expansion of an arbitrary function in a power series. Newton showed that for |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . If we now put Z=X/Y and multiply the left and right sides by Yn, then we get a variant of Newton's binomial formula discussed above.
Despite its universality, the binomial theorem retains its combinatorial meaning only for integer nonnegative powers of the binomial. In this case, it can be used to prove several useful identities for binomial coefficients. In particular, the summation formulas for the numbers of combinations by the lower index and by both indices were considered above. The missing superscript summation identity can be easily obtained from Newton's binomial formula by setting 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, one obtains the identity of the sum of binomial coefficients with only even or only odd numbers:
On the basis of the considered identities and the recurrent rule for removing indices from under the sign of the number of combinations, a number of interesting relations can be obtained. For example, if in the summation formula for the superscript, we replace n with (n1) everywhere and take out the indices in each term, then we get the following relation:
Using a similar technique in the formula for the sum of binomial coefficients with even and odd numbers, one can prove the validity of, for example, the following relationship:
Another useful identity makes it easy to calculate the sum of 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 the coefficients for any degree m of the variable Z in the left and right parts of the following identity relation:
In the particular 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 composed of binomial coefficients. Its rows are ordered by binomial powers from top to bottom. In each row, the binomial coefficients are arranged in ascending order of the upper indices of the corresponding numbers of combinations 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, arranged in a checkerboard pattern, form an infinite isosceles triangle. Its initial fragment for binomials up to the 4th degree (n=4) is as follows:
In general, Pascal's isosceles triangle provides a convenient geometric rule for determining binomial coefficients, which is based on addition identities and symmetry of combination numbers. In particular, in accordance with 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 rows is a numerical palindrome of binomial coefficients. These algebraic and geometric features make it easy to expand Pascal's isosceles triangle and consistently find the values of binomial coefficients of arbitrary degrees.
However, to study the various properties of Pascal's triangle, it is more convenient to use the formally more strict rectangular format. In this format, it is given by a lower-triangular matrix of binomial coefficients, where they form an infinite right triangle. Starting Fragment right triangle Pascal for binomials up to the 9th degree (n=9) has the following form:
Geometrically, such a rectangular table is obtained by horizontal deformation isosceles triangle Pascal. As a result, the number series parallel to the sides of Pascal's isosceles triangle turn into verticals and diagonals of Pascal's right triangle, and the horizontals of both triangles coincide. At the same time, the rules of addition and symmetry of binomial coefficients remain valid, although Pascal's right-angled triangle loses the visual symmetry inherent in its isosceles counterpart. As compensation 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 contours of Pascal's right-angled triangle, it is easy to see that the sum of the elements of any row with number n is equal to 2 n in accordance with the summation formula for binomial by superscript. It follows from this that the sum of elements over any of the horizontals 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, such an addition can be written as follows:
Here's a couple more interesting properties contour lines, which are also associated with a power 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 extreme units) are even numbers. Conversely, all the numbers of a horizontal line will be odd if its number per unit less degree deuces (n=2k1). 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 simple numbers of horizontals. For example, all internal binomial coefficients of the fifth horizontal (5, 10 and 5) are obviously divisible by 5. To prove the validity of this result for any prime number of the horizontal p, we need to write the multiplicative formula of its binomial coefficients as follows:
Since p is a prime number and therefore not divisible by m!, the product of the other factors of the numerator of this formula must be divisible by m! to guarantee an integer value of the binomial coefficient. It follows from this that the relation square brackets is a natural number N and the desired result becomes obvious:
Using this result, it can be established that the numbers of all contours of Pascal's triangle, whose internal elements are divisible by a given prime number p, are the power 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 the internal elements of row 3, as was 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, all the internal elements of which are divisible by a composite number. Otherwise, the number of such a horizontal must be at the same time the degree of prime divisors composite number, into which all its internal elements are divided, but this is impossible for obvious reasons.
The considered considerations allow us to formulate the following common feature divisibility of the horizontal elements of Pascal's triangle. largest common divisor(GCD) all internal elements any horizontal of Pascal's triangle with number n is equal to a prime number p if n=pk or 1 otherwise:
GCD(Cmn) = ( ) for any 0< m < n .
In conclusion of the analysis of horizontals, it is worth considering one more curious property that the series of binomial coefficients that form them have. If the binomial coefficients of any horizontal with number n are multiplied by successive powers of the number 10, and then all these products are added, then 11 n will be obtained. The formal substantiation of this result is the substitution of the values X=10 and Y=1 (or Z=1) into Newton's binomial formula. The following numerical example illustrates the implementation of this property for n=5:
An analysis of the properties of the verticals of Pascal's right triangle can be started by studying individual characteristics their constituent elements. Formally, each vertical m is formed by the following infinite sequence of binomial coefficients with constant superscript (m) and increment of subscript:
Obviously, when m=0, a sequence of ones is obtained, and when m=1, a series of natural numbers is formed. For m=2, the vertical is made up of triangular numbers. Each triangular number can be depicted on a plane as an equilateral triangle, which is filled with arbitrary objects (kernels) arranged in a checkerboard pattern. In this case, the value of each triangular number T k determines the number of representing nuclei, and the index shows how many rows of nuclei are needed to represent it. For example, the 4 initial triangular numbers represent the following configurations from the corresponding number of kernel characters "@":
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 figurative numbers formed by regular filling regular polygons. In particular, 4 initial square numbers can be depicted as follows:
Returning to the analysis of the verticals of Pascal's triangle, it can be noted that the next vertical at m=3 is filled with tetrahedral (pyramidal) numbers. Each such number P k specifies the number of nuclei that can be arranged in the form of a tetrahedron, and the index determines how many horizontal triangular layers from the rows of nuclei are required to image it in three-dimensional space. In this case, all horizontal layers should be represented as consecutive triangular numbers. The elements of the next verticals of Pascal's triangle for m>3 form rows of hypertetrahedal numbers that do not have a clear geometric interpretation on the plane or in three-dimensional space, but formally correspond to multidimensional analogues of triangular and tetrahedal numbers.
Although the vertical numerical series of Pascal's triangle have the considered individual curly features, but 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 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 kernel layers that represent numbers of a lower order. In particular, nth triangular the number T n can be obtained by summing all natural numbers representing its linear layers:
Similarly, it is easy to find the tetrahedral number P n by calculating the following sum of the first n triangular numbers that make up its horizontal nuclear layers:
In addition to the horizontals and verticals in Pascal's right triangle, one can trace the diagonal rows of elements, the study of the properties of which is also of particular interest. In this case, descending and ascending diagonals are usually distinguished. The descending 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 considered above. The specified 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 rows geometrically perpendicular to the hypotenuse of Pascal's right triangle. They are filled with binomial coefficients with subscript increment and superscript increment. In particular, the 7 upper ascending diagonals form the following numerical sequence, excluding trailing zeros:
In the general case, the following binomial coefficients are on the ascending diagonal with number n, 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 makes it possible to build each subsequent ascending diagonal 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 with number 8 along diagonals with numbers 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 it is possible to verify the validity of the considered property of the ascending diagonals of Pascal's right-angled triangle:
Analyzing these numbers, you can see that, according to a similar law, the well-known sequence of Fibonacci numbers is formed, where each successive number is equal to the sum of the previous two, and the first two numbers are equal to 1:
Thus, the following important conclusion can be drawn: the diagonal sums of the elements of Pascal's triangle constitute the Fibonacci sequence. This property allows you to set another interesting feature 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 top 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 the number (n + 2).
In conclusion, it should be noted that the considered properties of the horizontals, verticals and diagonals of Pascal's triangle are far from exhausting the huge variety of possibilities that link together various mathematical aspects that at first glance have nothing in common. Such unusual properties make it possible to consider Pascal's triangle as one of the most advanced numerical systems, all the possibilities of which cannot be listed and it is 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 build Pascal's triangle once, and then get the 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 get the number of combinations using the SochTT function. When you no longer need the triangle, call TerminateTT. In the above code, when calling the SochTT function, if the triangle has not yet been completed to required level, then it is completed using the BuildTT procedure. The function then gets the required 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
Enumeration of combinations of natural numbers
To solve many practical problems, it is necessary to enumerate all combinations of fixed cardinality that can be obtained from elements of a given finite set, and not just determine their number. Given the always existing possibility of integer numbering of elements of any finite set, in most cases it is permissible to restrict ourselves to using algorithms for enumerating combinations of natural numbers. The most natural and simplest of them is the algorithm for listing combinations of natural numbers in lexigraphic order.
For a formal description of 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 vectors of combinations, starting from the lexigraphically smallest vector, where all positions contain the following minimum possible values of elements equal to their indices: Each next combination vector is formed from the current one after viewing 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 more than the 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 in 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. As a result, an increasing lexigraphic sequence is formed, which is completed by the lexigraphically largest combination vector, where the elements in all positions have the following maximum values: The considered lexigraphic algorithm illustrates the following example, where it is necessary to list in ascending lexigraphic order all 15 combinations of n=6 first natural numbers with m=4 numbers, that is, all possible 4-element subsets of the main generating set (1, 2, 3, 4 , 5, 6) of 6 elements. The calculation results are presented in the following table: In this example, the largest allowable values of numbers in the positions of the combination vectors are 3, 4, 5, and 6, respectively. For the convenience of interpreting the results in each combination vector, the rightmost element, which has not yet reached its maximum value, is underlined. Numerical indexes 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's symbolism is used to indicate the number of combinations: In particular, the following calculations using this formula for the combination number (1, 3, 4, 6) of n=6 elements by 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 can be shown that the number of the lexigraphically smallest combination (1, ... i, ... m) when calculating it 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 calculating it according to this formula will be equal to the number of combinations of n elements by m: The formula for calculating lexigraphic numbers of combinations can be used to solve an inverse problem where it is required to determine the combination vector by its number in lexigraphic order. To solve such an inverse problem, it must be written as an equation, where all 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 by m and the number of the desired combination N: The solution of this equation provides the following "greedy" algorithm, on 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 C 1 is selected, in 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 chosen value of C 1 , and the value of C 2 should be determined in the same way 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 enumeration of 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 a lexigraphic order can be used in various directions. In particular, when listing combinations in lexigraphic order, it is required to provide 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 that regulates an arbitrarily given sequence of their lexigraphic numbers. Now we present the 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 REPETITIONS OF ELEMENTS In contrast to the 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 often and not necessarily be present in a single copy. At the same time, the number of repetitions of elements is usually limited only by the length of the combination, and combinations that differ by at least one element are considered different. For example, by choosing 4 optionally different numbers from the set 1, 2 and 3, you can make the following 15 combinations with repetitions: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
In the general case, combinations with repetitions can be formed by a selection of 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 writing, 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 ascending 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 systematic enumeration of combinations with repetitions of n elements over m. It is only necessary to list, for example, in lexigraphic order all C combinations of (n + m1) elements by m, sequentially converting the elements of each of them into the corresponding elements of combinations with repetitions f according to the following formula: As a result, a sequence of combination vectors with repetitions of elements is formed, which are arranged in the order generated by the enumeration of 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 required to list in lexigraphic order all combinations without repetitions of 6 digits 1,2,3,4, 5 and 6 by 4 digits, converting them in the specified way. The following example shows such a transformation of the combination (1,3,4,6) with lexigraphic number 8: The considered one-to-one correspondence between combinations with repetitions and without repetitions of elements means that their sets are equivalent. Therefore, in the general case, the number of combinations with repetitions of n elements over m is equal to the number of combinations without repetitions from (n + m1) elements over m. Using the same symbolism to denote the number of combinations with repetitions of f and without repetitions of C, this equality can be written as follows: It is easy to check that for the example above, where n=3 and m=4, the number of combinations with repetition will be 15, which coincides with the result of their direct enumeration: 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 (n+m1) and (n1) or (n+m1) and m: It should also be quite obvious that if m is equal to 1, then no repetition of elements is possible and, therefore, for any positive value of n>0, the following equality will hold: In addition, for the numbers of combinations with repetitions for any positive values n and m, the following recurrence holds, which is similar to the addition identity for combination numbers without repetition of elements: Actually, it turns into the specified addition identity with the formal substitution of the corresponding numbers of combinations without repetitions in its left and right parts: The considered recurrence relation can be used to effectively determine the number of combinations with repetitions, when it is important to eliminate the laborious operations of calculating factorial products and replace them with simpler addition operations. In this case, to calculate the value of f(n,m), it is only necessary to apply this recurrence relation until the sum of terms of the form f(1,m) and f(i,1) is obtained, where i takes values in the range from n to 1. By definition of the value such terms are equal to 1 and i, respectively. The following example illustrates the use of this transformation technique for the case n=3 and m=4: Enumeration of binary combinations When implementing combinations in hardware or when 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 by m should be specified in the form of an n-bit binary number (B n ,…B j ,…B 1), where m single digits denote the elements of the combination, and the remaining (nm) digits have zero values. Obviously, with this form of writing, different combinations must differ in the arrangement of units 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 that provide 4-digit 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 is reduced to a systematic enumeration of all n-bit binary sets with different arrangements of m single and (nm) zero bits. In the simplest form, such an enumeration is implemented various methods transpositions of adjacent digits 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 transpositive-shift algorithms form sequences of binary combinations that begin with a binary set, where all ones are concentrated in the lower digits (on the right), and end when all the ones are in the higher digits (on the left): Coinciding in initial and final combinations, these sequences differ in the order of enumeration of intermediate binary sets. However, in all cases, each next binary combination is formed according to 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 of choosing a pair of digits for transposition and a group of digits for shift. This specificity is considered below for transposition algorithms with left and right shifts. 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 bits 01 with 10 (transposition) and shifting the group of leading unit bits, if any, close to the pair 10 obtained after the transposition (shift). If at the same time in the current binary combination there are no ones in the highest digits, then the shift is not performed, even when the leading unit is obtained after transposition by this step. The shift is also not performed when there are no zeros in the high-order bits before the pair of 10s obtained after the transposition. The considered actions are illustrated by the following example of performing two successive iterations this algorithm, where at one iteration (15) only the 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 actions are performed at each step. Only the transposition ensures that the right-most digits 01 are replaced by 10 (instead of the left-most ones), and then all units to the right of it are shifted to the lower digits. 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 the execution of two successive iterations of this algorithm, where at one iteration (3) only the 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 an 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 integer addition operations using the following additive formula: In this additive formula, the exponents of twos f and t denote, respectively, the number of zeros 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 bits, f =1 and t =3. Therefore, the calculation of the next binary combination by the additive formula at iteration 5 will give the following result, which is equivalent to performing the transposition and shift operations: For 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 at their iterations. The following table shows two such sequences of binary combinations of 4 elements by 2, which are obtained by 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 changing to the reverse indexing of bits in any of them. 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 the general case, any binary combination with number i of one sequence is a mirror image of a binary combination with number (ni + 1) of another sequence. Such a ratio of these sequences is a consequence of the symmetrical nature of the operations of transposition and shift in the two considered algorithms for enumerating binary combinations. It should be noted that the binary format can also be used to write combinations with repetitions of elements. To do this, you need 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 n elements of the generating set. To establish the desired correspondence, you must first attach to the combination all the elements of the generating set (cat), and then sort the resulting concatenation (sort) so that all identical elements are nearby. The result is a sequence of (n+m) elements, where n groups of identical elements. There will be only (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, in the specified intervals, you can place the characters "|" and correspondingly. If we now map 1 to the gaps between groups (|) and 0 to all other gaps (), then we get a binary combination. It is formed by a binary set of (n+m1) digits, where (n1) are ones and m zero digits, the location of which uniquely corresponds to the original combination with repetitions from elements n to m. The considered transformation technique is illustrated by the following example of constructing a binary combination (1001101) by 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) over (n1) or over 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 by m. 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 an enumeration of binary combinations, for example, using transposition algorithms with left or right shift. After that, you only need to restore the desired combinations with repetitions from the obtained binary combinations. This can always be done by applying the following restorative technique. Let the main set, from the elements of which combinations are formed with repetitions of m optionally different elements, be ordered arbitrarily so that each of its elements has a certain serial number from 1 to n. Let the enumeration of binary combinations of (n+m1) binary digits be also implemented, where (n1) are single 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 standing 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 the binary combination (1001101) restores the combination with BBD repetitions, the elements of which are selected from the generating set of the first five Latin letters written in alphabetical order, and overlining denotes elements that are missing in this combination: Performing similar actions in the conditions this example, you can list all 35 binary combinations that form 7-digit binary sets, where 4 ones and 3 zeros, and restore the corresponding combinations with repetitions of 5 elements by 3. To make it easier to navigate the material, I will add the content of this topic: 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" . Highly short story about sets: 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. 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. 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 - 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. A permutation without repetitions of $n$ elements is an ordered $(n,n)$-selection without repetitions. In fact, a permutation without repetitions is special case placement without repetitions, 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 There are five servings of ice cream in the freezer from various firms. 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. 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 elements"d". 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. 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. 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.Introduction. Sets and selections.
Allocations without repetitions of $n$ elements by $k$
Allocations with repetitions of $n$ elements by $k$
Permutations without repetitions of $n$ elements
Permutations with repetitions
Combinations without repetitions of $n$ elements by $k$
Combinations with repetitions of $n$ elements by $k$
