Possible combinations. Elements of combinatorics
A combination is an unordered selection of elements of a finite set with a fixed number and without repetitions of elements. Different combinations must differ in at least one element, and the order of the elements does not matter. For example, from the set of all vowels of Latin letters (AEIOU), you can make 10 different combinations of 3 letters, forming the following unordered triplets:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
It is interesting to note that from the same five letters you can also get 10 different combinations if you combine them 2 letters at a time, making the following unordered pairs:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
However, if you combine the same vowel Latin letters by 4, you will only get the following 5 different combinations:
AEIO, AEIU, AIOU, EIOU, AEOU.
In general, to denote the number of combinations of n different elements of m elements, the following functional, index or vector (Appel) symbolism is used:
Regardless of the form of notation, the number of combinations of n elements by m elements can be determined using the following multiplicative and factorial formulas:
It is easy to check that the result of calculations using these formulas coincides with the results of the example discussed above with combinations of vowels in Latin letters. In particular, with n=5 and m=3, calculations using these formulas will give the following result:
In the general case, formulas for the number of combinations have a combinatorial meaning and are valid for any integer values of n and m, such that n > m > 0. If m > n and m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
In addition, it is useful to remember the following limiting numbers of combinations, which can be easily checked by direct substitution into the multiplicative and factorial formulas:
It should also be noted that the multiplicative formula remains valid even when n is a real number, as long as m is still an integer value. However, then the result of the calculation using it, while maintaining formal validity, loses its combinatorial meaning.
IDENTITIES OF COMBINATIONS
The practical use of multiplicative and factorial formulas to determine the number of combinations for arbitrary values of n and m turns out to be of little productivity due to the exponential growth of the factorial products of their numerator and denominator. Even for relatively small values of n and m, these products often exceed the capabilities of representing integers in modern computing and software systems. Moreover, their values turn out to be significantly greater than the resulting value of the number of combinations, which can be relatively small. For example, the number of combinations of n=10 by m=8 elements is only 45. However, to find this value using the factorial formula, you must first calculate much larger values of 10! in the numerator and 8! in the denominator:
To eliminate time-consuming operations for processing large quantities, to determine the number of combinations, you can use various recurrence relations, which directly follow from the multiplicative and factorial formulas. In particular, the following recurrence relation follows from the multiplicative formula, which allows us to take the ratio of its indices beyond the sign of the number of combinations:
Finally, keeping the subscript constant provides the following recurrence relation, which is easily obtained from the factorial formula for the number of combinations:
After elementary transformations, the three resulting recurrence relations can be represented in the following forms:
If we now add the left and right sides of the first 2 formulas and reduce the result by n, we get an important recurrence relation, which is called the identity of adding combination numbers:
The addition identity provides a basic recurrence rule for efficiently determining the number of combinations for large values of n and m, since it allows the multiplication operations in factorial products to be replaced by the simpler addition operations, and for smaller numbers of combinations. In particular, using the addition identity, it is now easy to determine the number of combinations of n=10 by m=8 elements, which was discussed above, by performing the following sequence of recurrent transformations:
In addition, several useful relations for calculating finite sums can be derived from the addition identity, in particular, the formula for summation by subscript, which has the following form:
This relation is obtained if in the addition identity we expand the recurrence along the term with the largest superscript while its subscript is greater than 0. The following numerical example illustrates this process of recurrent transformations:
The subscript summation formula is often used to calculate the sum of powers of natural numbers. In particular, assuming m=1, using this formula it is easy to find the sum of the first n numbers of the natural series:
Another useful version of the summation formula can be obtained by expanding the recurrence of the addition identity along the term with the smallest superscript. The following numerical example illustrates this version of recurrent transformations:
In the general case, as a result of such transformations, the sum of the numbers of combinations is obtained, both indices of which differ by one from the neighboring terms, and the difference in the indices remains constant (in the example considered, it is also equal to one). Thus, we obtain the following summation formula for both indices of combination numbers:
In addition to the recurrence relations and summation formulas discussed above, many other useful identities for combination numbers have been obtained in combinatorial analysis. The most important among them is symmetry identity, which looks like this:
The validity of the symmetry identity can be verified in the following example by comparing the numbers of combinations of 5 elements by 2 and by (5 2) = 3:
The symmetry identity has an obvious combinatorial meaning, since, by determining the number of options for selecting m elements from n elements, it simultaneously establishes the number of combinations from the remaining (nm) unselected elements. The indicated symmetry is immediately obtained by replacing m by (nm) in the factorial formula for the number of combinations:
Numbers and combination identities are widely used in various areas of modern computational mathematics. However, their most popular applications are related to Newton's binomial and Pascal's triangle.
BINOMIAL THEOREM
To perform various mathematical transformations and calculations, it is important to be able to represent any natural power of an algebraic binomial (binomial) in the form of a polynomial. For small powers, the desired polynomial can be easily obtained by directly multiplying binomials. In particular, the following formulas for the square and cube of the sum of two terms are well known from the course of elementary mathematics:
In the general case, for an arbitrary degree n of a binomial, the required representation in the form of a polynomial is provided by Newton’s binomial theorem, which declares the following equality to be true:
This equality is usually called Newton's binomial. The polynomial on its right side is formed by the sum of the products of n terms X and Y of the binomial on the left side, and the coefficients in front of them are called binomial and are equal to the number of combinations with indices, which are obtained from their powers. Given the particular popularity of Newton's binomial formula in combinatorial analysis, the terms binomial coefficient and number of combinations are generally considered synonymous.
Obviously, the squared and cubed sum formulas are special cases of the binomial theorem for n=2 and n=3, respectively. To handle higher degrees (n>3), Newton's binomial formula should be used. Its application for a fourth degree binomial (n=4) is demonstrated by the following example:
It should be noted that the binomial formula was known even before Newton to medieval mathematicians of the Arab East and Western Europe. Therefore, its generally accepted name is not historically fair. Newton's merit is that he generalized this formula to the case of an arbitrary real exponent r, which can take any positive or negative rational and irrational values. In the general case, such a Newton binomial formula has an infinite sum on the right side and is usually written as follows:
For example, with a positive fractional value of the exponent r=1/2, taking into account the values of the binomial coefficients, the following expansion is obtained:
In the general case, Newton's binomial formula for any exponent is a special version of Maclaurin's formula, which gives the expansion of an arbitrary function into a power series. Newton showed that for |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . If we now set Z=X/Y and multiply the left and right sides by Yn, we get a version of the Newton binomial formula discussed above.
Despite its universality, the binomial theorem retains its combinatorial meaning only for non-negative integer powers of the binomial. In this case, it can be used to prove several useful identities for binomial coefficients. In particular, formulas for summing the numbers of combinations by subscript and by both indices were discussed above. The missing superscript summation identity can be easily obtained from Newton’s binomial formula by putting X = Y = 1 or Z = 1 in it:
Another useful identity establishes the equality of the sums of binomial coefficients with even and odd numbers. It is immediately obtained from Newton's binomial formula if X = 1 and Y = 1 or Z = 1:
Finally, from both considered identities we obtain the identity of the sum of binomial coefficients with only even or only odd numbers:
Based on the considered identities and the recurrent rule of removing indices from under the sign of the number of combinations, a number of interesting relationships can be obtained. For example, if in the superscript summation formula we replace n everywhere with (n1) and remove the indices in each term, we get the following relation:
Using a similar technique in the formula for the sum of binomial coefficients with even and odd numbers, it is possible to prove the validity of, for example, the following relation:
Another useful identity allows you to easily calculate the sum of the products of symmetrically located binomial coefficients of two binomials of arbitrary degrees n and k using the following Cauchy formula:
The validity of this formula follows from the necessary equality of coefficients for any degree m of the variable Z on the left and right sides of the following identical relation:
In the special case when n=k=m, taking into account the symmetry identity, a more popular formula for the sum of squares of binomial coefficients is obtained:
Many other useful identities for binomial coefficients can be found in the extensive literature on combinatorial analysis. However, their most famous practical application is related to Pascal's triangle.
PASCAL'S TRIANGLE
Pascal's arithmetic triangle forms an infinite numerical table made up of binomial coefficients. Its lines are ordered by powers of binomials from top to bottom. In each line, the binomial coefficients are arranged in ascending order of the superscripts of the corresponding combination numbers from left to right. Pascal's triangle is usually written either in isosceles or rectangular form.
More visual and common is the isosceles format, where the binomial coefficients, staggered, form an infinite isosceles triangle. Its initial fragment for binomials up to the 4th degree (n=4) has the following form:
In general, Pascal's isosceles triangle provides a convenient geometric rule for determining binomial coefficients, which is based on the identities of addition and the symmetry of number combinations. In particular, according to the addition identity, any binomial coefficient is the sum of the two coefficients of the previous row closest to it. According to the symmetry identity, Pascal's isosceles triangle is symmetrical with respect to its bisector. Thus, each of its lines is a numerical palindrome of binomial coefficients. The indicated algebraic and geometric features make it possible to easily expand Pascal's isosceles triangle and consistently find the values of binomial coefficients of arbitrary powers.
However, to study various properties of Pascal's triangle, it is more convenient to use the formally more strict rectangular format. In this format, it is specified by a lower triangular matrix of binomial coefficients, where they form an infinite right triangle. The initial fragment of Pascal's right triangle for binomials up to the 9th degree (n=9) has the following form:
Geometrically, such a rectangular table is obtained by horizontally deforming Pascal's isosceles triangle. As a result, the number series parallel to the lateral sides of Pascal’s isosceles triangle turn into verticals and diagonals of Pascal’s right triangle, and the horizontal lines of both triangles coincide. At the same time, the rules of addition and symmetry of binomial coefficients remain valid, although Pascal's right triangle loses the visual symmetry characteristic of its isosceles counterpart. To compensate for this, it becomes more convenient to formally analyze the various numerical properties of the binomial coefficients for the horizontals, verticals, and diagonals of Pascal's right triangle.
Starting the analysis of the horizontals of Pascal's right triangle, it is easy to notice that the sum of the elements of any row with number n is equal to 2n in accordance with the formula for summing binomials by superscript. It follows from this that the sum of the elements above any of the horizontal lines with number n is equal to (2 n 1). This result becomes quite obvious if the value of the sum of the elements of each horizontal is written in the binary number system. For example, for n=4 this addition can be written as follows:
Here are a couple more interesting properties of horizontals that are also related to powers of two. It turns out that if the horizontal number is a power of two (n=2 k), then all its internal elements (except for the outer ones) are even numbers. On the contrary, all numbers of a horizontal line will be odd if its number is one less than a power of two (n=2 k 1). The validity of these properties can be verified by checking the parity of the internal binomial coefficients, for example, in the horizontals n=4 and n=3 or n=8 and n=7.
Let now the row number of Pascal's right triangle be a prime number p. Then all its internal binomial coefficients are divisible by p. This property is easy to check for small values of prime contour numbers. For example, all the internal binomial coefficients of the fifth horizontal (5, 10 and 5) are obviously divisible by 5. To prove this result for any prime horizontal number p, you need to write the multiplicative formula for its binomial coefficients as follows:
Since p is a prime number and, therefore, is not divisible by m!, the product of the remaining factors of the numerator of this formula must be divisible by m! to guarantee an integer value of the binomial coefficient. It follows that the ratio in square brackets is a natural number N and the desired result becomes obvious:
Using this result, we can establish that the numbers of all horizontal lines of Pascal's triangle, the internal elements of which are divisible by a given prime number p, are powers of p, that is, they have the form n=p k. In particular, if p=3, then the prime number p divides not only all internal elements of row 3, as established above, but, for example, the 9th horizontal (9, 36, 84 and 126). On the other hand, in Pascal's triangle it is impossible to find a horizontal line whose internal elements are all divisible by a composite number. Otherwise, the number of such a horizontal line must simultaneously be a power of prime divisors of the composite number by which all its internal elements are divided, but this is impossible for obvious reasons.
The considered considerations allow us to formulate the following general criterion for the divisibility of the horizontal elements of Pascal's triangle. The greatest common divisor (GCD) of all internal elements of any horizontal line of Pascal's triangle with number n is equal to the prime number p if n=pk or 1 in all other cases:
GCD(Cmn) = ( ) for any 0< m < n .
In conclusion of the analysis of horizontals, it is worth considering one more interesting property that the series of binomial coefficients that form them have. If the binomial coefficients of any horizontal line with number n are multiplied by successive powers of the number 10, and then all these products are added, the result is 11 n. The formal justification for this result is the substitution of the values X=10 and Y=1 (or Z=1) into the Newton binomial formula. The following numerical example illustrates the fulfillment of this property for n=5:
The analysis of the properties of the verticals of Pascal's right triangle can begin with the study of the individual characteristics of their constituent elements. Formally, each vertical m is formed by the following infinite sequence of binomial coefficients with a constant superscript (m) and an increment of the subscript:
Obviously, when m=0 a sequence of ones is obtained, and when m=1 a series of natural numbers is formed. When m=2 the vertical is made up of triangular numbers. Each triangular number can be depicted on a plane in the form of an equilateral triangle, which is filled with arbitrary objects (nuclei) arranged in a checkerboard pattern. In this case, the value of each triangular number T k determines the number of representing kernels, and the index shows how many rows of kernels are needed to represent it. For example, 4 initial triangular numbers represent the following configurations of the corresponding number of nuclear "@" symbols:
It should be noted that in a similar way one can introduce into consideration square numbers S k , which are obtained by squaring natural numbers and, in general, polygonal figured numbers formed by regularly filling regular polygons. In particular, the 4 initial square numbers can be represented as follows:
Returning to the analysis of the verticals of Pascal's triangle, we can note that the next vertical at m=3 is filled with tetrahedral (pyramidal) numbers. Each such number P k specifies the number of cores that can be arranged in the shape of a tetrahedron, and the index determines how many horizontal triangular layers of rows of cores are required to depict it in three-dimensional space. In this case, all horizontal layers must be represented as successive triangular numbers. The elements of the following verticals of Pascal's triangle for m>3 form series of hypertetraedal numbers, which do not have a visual geometric interpretation on the plane or in three-dimensional space, but formally correspond to multidimensional analogues of triangular and tetrahedal numbers.
Although the vertical number series of Pascal's triangle have the considered individual shaped features, for them it is possible to calculate the partial sums of the values of the initial elements in the same way, using the formula for summing the numbers of combinations by subscript. In Pascal's triangle, this formula has the following geometric interpretation. The sum of the values of the n upper binomial coefficients of any vertical is equal to the value of the element of the next vertical, which is located one line below. This result is also consistent with the geometric structure of triangular, tetrahedral and hypertetrahedal numbers, since the representation of each such number consists of core layers that represent lower order numbers. In particular, the nth triangular number T n can be obtained by summing all the natural numbers representing its linear layers:
Similarly, it is not difficult to find the tetrahedral number Pn by calculating the following sum of the first n triangular numbers that make up its horizontal core layers:
In addition to the horizontals and verticals in Pascal’s right triangle, one can trace diagonal rows of elements, the study of the properties of which is also of some interest. In this case, a distinction is usually made between descending and ascending diagonals. The downward diagonals are parallel to the hypotenuse of Pascal's right triangle. They are formed by series of binomial coefficients with an increment of both indices. Due to the identity of symmetry, the descending diagonals coincide in the values of their elements with the corresponding vertical rows of Pascal’s triangle and therefore repeat all their properties discussed above. The indicated correspondence can be traced by the coincidence of the values of the elements of the descending diagonal and the vertical with any number n, if vertical zeros are not taken into account:
Ascending diagonals form number series geometrically perpendicular to the hypotenuse of Pascal's right triangle. They are filled with binomial coefficients with a decrement of the lower and increment of the superscript. In particular, the 7 upper ascending diagonals form the following numerical sequence without taking into account the trailing zeros:
In general, the ascending diagonal number n contains the following binomial coefficients, the sum of the indices of each of which is equal to (n1):
By virtue of the addition identity for combination numbers, each diagonal element is equal to the sum of two elements corresponding in indices from the two previous ascending diagonals. This allows each subsequent ascending diagonal to be constructed by pairwise summation of adjacent horizontal elements from the two previous diagonals, infinitely expanding Pascal's triangle along the diagonal. The following fragment of Pascal's triangle illustrates the construction of an ascending diagonal number 8 along diagonals numbered 6 and 7:
With this method of construction, the sum of the elements of any ascending diagonal, starting from the 3rd, will be equal to the sum of the elements of the two previous ascending diagonals, and the first 2 diagonals consist of only one element, the value of which is 1. The results of the corresponding calculations form the following numerical series, according to which you can check the validity of the considered property of the ascending diagonals of Pascal’s right triangle:
Analyzing these numbers, you can see that according to a similar law, the well-known sequence of Fibonacci numbers is formed, where each next number is equal to the sum of the two previous ones, and the first two numbers are equal to 1:
Thus, we can draw the following important conclusion: the diagonal sums of the elements of Pascal’s triangle constitute the Fibonacci sequence. This property allows us to establish another interesting feature of Pascal's triangle. Expanding the Fibonacci formula recursively, it is easy to prove that the sum of the first n Fibonacci numbers is equal to (F n+2 1).
Therefore, the sum of the binomial coefficients that fill the upper n diagonals is also equal to (F n+2 1). It follows that the sum of the first n diagonals of Pascal’s triangle is 1 less than the sum of the binomial coefficients that stand on its diagonal with number (n+2).
In conclusion, it should be noted that the considered properties of the horizontals, verticals and diagonals of Pascal's triangle do not exhaust the huge variety of possibilities that connect together various mathematical aspects that at first glance have nothing in common. Such unusual properties allow us to consider Pascal’s triangle one of the most perfect numerical systems, all of whose capabilities cannot be listed and are difficult to overestimate.
The algorithm for calculating the number of combinations using Pascal's triangle is presented below:
Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Next For i = 2 To n For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next SochTT = TT (n, k) End Function
If you need to calculate the number of combinations many times, then it may be more convenient to construct Pascal's triangle once, and then receive data from the array.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j As Integer ReDim Preserve TT (end, end) For i = start To end TT (0, i) = 1 TT (i, i) = 1 Next If end< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
First you need to call the CreateTT procedure. You can then obtain the number of combinations using the SochTT function. When you no longer need the triangle, call the TerminateTT procedure. In the above code, when calling the SochTT function, if the triangle has not yet been completed to the required level, then it is completed using the BuildTT procedure. The function then gets the desired element of the TT array and returns it.
Dim X () As Integer Dim Counter () As Integer Dim K As Integer Dim N As Integer Public Sub Soch() Dim i As Integer N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Then ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 For j = 1 To N If X1(j)<>0 Then n1 = n1 + 1 If n1 = Counter(i) Then Out(i) = X1(j) X1(j) = 0 Exit For End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Next txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
LISTING COMBINATIONS OF NATURAL NUMBERS
To solve many practical problems, it is necessary to list all combinations of fixed cardinality that can be obtained from the elements of a given finite set, and not just determine their number. Taking into account the always existing possibility of integer numbering of the elements of any finite set, in most cases it is permissible to limit ourselves to the use of algorithms for enumerating combinations of natural numbers. The most natural and simple of them is the algorithm for listing combinations of natural numbers in lexigraphic order.
To formally describe this algorithm, it is convenient to assume that the main set, all combinations of m elements of which must be listed, form consecutive natural numbers from 1 to n. Then any combination of m As a result of ordering, the value in each position of such a vector of combinations naturally turns out to be limited in value from above and below as follows: The lexigraphic algorithm sequentially generates such combination vectors, starting with the lexigraphically smallest vector, where all positions contain the following minimum possible values of elements equal to their indices: Each successive combination vector is formed from the current one after scanning its elements from left to right in order to find the rightmost element that has not yet reached its limit value: The value of such an element should be increased by 1. Each element to the right of it should be assigned the smallest possible value, which is 1 greater than its neighbor to the left. After these changes, the next vector of combinations will have the following elemental composition: Thus, the next combination vector will be lexigraphically larger than the previous one, since the values of their initial (j1) elements are equal in value, and the value of the element at position j is 1 greater than that of the previous one. The specified relation of increasing lexigraphic order is guaranteed to be satisfied at all iterations of the algorithm. The result is an increasing lexigraphic sequence, which is completed by the lexigraphically largest combination vector, where the elements in all positions have the following maximum values: The considered lexigraphic algorithm is illustrated by the following example, where it is necessary to list in increasing lexigraphic order all 15 combinations of n=6 first natural numbers by m=4 numbers, that is, all possible 4-element subsets of the main generating set (1, 2, 3, 4 , 5, 6) from 6 elements. The calculation results are presented in the following table: In this example, the largest permissible values of numbers in the positions of the combination vectors are, respectively, 3, 4, 5 and 6. For ease of interpretation of the results, in each combination vector, the rightmost element, which has not yet reached its maximum value, is underlined. Numerical indices of combination vectors determine their numbers in lexigraphic order. In the general case, the lexigraphic number N of any combination of n elements by m can be calculated using the following formula, where, for cosmetic reasons, Appel symbolism is used to denote the numbers of combinations: In particular, the following calculations using this formula for the combination number (1, 3, 4, 6) of n=6 elements of m=4 in lexigraphic order will give the result N=8, which corresponds to the example discussed above: In the general case, using the identity for the sum of the numbers of combinations for both indices, it is possible to show that the number of the lexigraphically smallest combination (1, ... i, ... m) when calculated using this formula will always be equal to 1: It is also obvious that the number of the lexigraphically largest combination (m, … nm+i, … n) when calculated using this formula will be equal to the number of combinations of n elements by m: The formula for calculating lexigraphic combination numbers can be used to solve the inverse problem, where you need to determine the combination vector by its number in lexigraphic order. To solve such an inverse problem, it must be written in the form of an equation, where all the unknown values of the elements of the vector of the desired combination (C 1, ... C i, ... C m) are concentrated in the numbers of combinations of its right side, and the known difference L of the number of combinations is written on the left side of n elements each m and the number of the required combination N: The solution to this equation is provided by the following “greedy” algorithm, during the iterations of which the values of the elements of the vector of the desired combination are sequentially selected. At the initial iteration, the minimum possible (within its limitations) value of C 1 is selected, at which the first term on the right side will have a maximum value not exceeding L: Now the left side of L should be reduced by the first number of combinations on the right side with the selected value of C 1, and similarly determine the value of C 2 at the second iteration: Similarly, all subsequent iterations should be performed to select the values of all other elements C i of the desired combination, up to the last element C m: For obvious reasons, the value of the last element C m can be determined based on the equality of its number of combinations to the residual value of the left side of L: It should be noted that the value of the last element of the combination C m can be found even more simply, without enumerating its possible values: The implementation of iterations of the considered algorithm is illustrated by the following example, where it is necessary to determine combinations with the number N=8 in lexigraphic order, if n=6 and m=4: The algorithmic ability to determine a combination by a given number in lexigraphic order can be used in various directions. In particular, when listing combinations in lexigraphic order, it is necessary to ensure a return to any combination that was obtained earlier, it is enough to know only its number. In addition, it becomes possible to generate combinations in any order, which is regulated by an arbitrarily given sequence of their lexigraphic numbers. Now we present an algorithm for generating combinations in lexicographic order: 2 for i:= 1 to k do A[i] := i; 5 begin write(A, …, A[k]); 6 if A[k] = n then p:= p 1 else p:= k; 8 for i:= k downto p do A[i] := A[p] + i p + 1 COMBINATIONS WITH REPEATING ELEMENTS Unlike a classical combination, where all elements are different, a combination with repetitions forms an unordered selection of elements of a finite set, where any element can appear indefinitely frequently and is not necessarily present in a single copy. In this case, the number of repetitions of elements is usually limited only by the length of the combination, and combinations that differ in at least one element are considered different. For example, by choosing 4 optionally different numbers from the set 1, 2 and 3, you can create the following 15 combinations with repetitions: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
In general, combinations with repetitions can be formed by selecting n elements of arbitrary types. However, they can always be associated with consecutive natural numbers from 1 to n. Then any combination of m optionally different numbers in this range can be written in vector form, arranging them in non-decreasing order from left to right: Naturally, with this form of notation, any neighboring elements can be equal due to the possibility of unlimited repetitions. However, each combination vector with repetitions of n elements by m can be associated with a combination vector of (n+m−1) elements by m, which is constructed as follows: It is clear that for any values of the elements of the vector f, the elements of the vector C are guaranteed to be different and strictly ordered in increasing order of their values from the range from 1 to (n+m1): The presence of a one-to-one correspondence between the elements of the combination vectors f and C allows us to propose the following simple method for systematically listing combinations with repetitions of n elements by m. It is only necessary to list, for example, in lexigraphic order, all C combinations of (n+m1) elements of m, sequentially transforming the elements of each of them into the corresponding elements of combinations with repetitions f using the following formula: As a result, a sequence of vectors of combinations with repetitions of elements is formed, which are arranged in the order generated by listing the corresponding combinations without repetitions of elements. In particular, in order to obtain the above sequence of combinations of 3 digits 1, 2 and 3 with repetitions of 4 digits, it is necessary to list in lexigraphic order all combinations without repetitions of 6 digits 1,2,3,4, 5 and 6 are 4 digits each, converting them as indicated. The following example shows such a conversion of the combination (1,3,4,6) with the lexicographic number 8: The considered one-to-one correspondence between combinations with and without repetitions of elements means that their sets are equally powerful. Therefore, in the general case, the number of combinations with repetitions of n elements by m is equal to the number of combinations without repetitions of (n+m1) elements by m. Using the same symbolism to denote the numbers of combinations with repetitions f and without repetitions C, this equality can be written as follows: It is easy to check that for the example considered above, where n=3 and m=4, the number of repetition combinations will be equal to 15, which coincides with the result of their direct listing: It should be noted that, unlike the classical version, the values of the combination parameters with repetitions n and m are not directly related to each other, therefore f(n,m)>0 for any combination of their positive values. The corresponding boundary conditions are determined from the equality between the values of (n+m1) and (n1) or (n+m1) and m: It should also be quite obvious that if m is equal to 1, then no repetitions of elements are possible and, therefore, for any positive value of n>0 the following equality will be true: In addition, for numbers of combinations with repetitions for any positive values of n and m, the following recurrence relation is valid, which is similar to the addition identity for numbers of combinations without repetitions of elements: Actually, it turns into the indicated addition identity upon formal substitution of the corresponding numbers of combinations without repetitions into its left and right sides: The considered recurrence relation can be used to effectively determine the numbers of combinations with repetitions, when it is important to eliminate the labor-intensive operations of calculating factorial products and replace them with simpler addition operations. In this case, to calculate the value of f(n,m), you only need to apply this recurrence relation until you obtain the sum of terms of the form f(1,m) and f(i,1), where i takes values in the range from n to 1. By definition of the quantity such terms are equal to 1 and i, respectively. The following example illustrates the use of this transformation technique for the case of n=3 and m=4: LISTING BINARY COMBINATIONS When implementing combinations in hardware or programming in assembly language, it is important to be able to process combination records in binary format. In this case, any combination of n elements of m should be specified in the form of an n-bit binary number (B n,...B j,...B 1), where m unit digits indicate the elements of the combination, and the remaining (nm) digits have zero values. Obviously, with this form of notation, different combinations must differ in the arrangement of the 1's digits, and there are only C(n,m) ways to arrange m ones or (nm) zeros in an n-bit binary set. For example, the following table lists all 6 such binary combinations, which provide 4-bit binary numbers for all combinations of 4 elements of an arbitrary set (E 1 , E 2 , E 3 , E 4 ) by 2: In the general case, the task of enumerating such binary combinations comes down to a systematic search of all n-bit binary sets with different arrangements of m one and (nm) zero bits. In the simplest form, such search is implemented by various methods of transposing adjacent bits with a shift (transpositive-shift algorithms). These are iterative algorithms, and their names reflect the nature of the operations performed at each step. Iterative procedures of transpositive-shift algorithms form sequences of binary combinations that begin with a binary set, where all ones are concentrated in the low-order digits (on the right), and end when all the 1’s are in the high-order digits (on the left): While matching in initial and final combinations, these sequences differ in the order in which intermediate binary sets are listed. However, in all cases, each subsequent binary combination is formed from the previous one as a result of performing the corresponding transposition and shift operations. At the same time, various transpositive-shift algorithms differ in the way they select a pair of bits for transposition and a group of bits for shifting. This specificity is discussed below for transposition algorithms with left and right shift. In the transposition algorithm with a left shift, at each step the next binary combination is obtained from the current one by replacing the leftmost pair of digits 01 with 10 (transposition) and shifting the group of leading unit digits, if any, close to the pair 10 obtained after the transposition (shift). If in this case there are no units in the leading digits in the current binary combination, then the shift is not performed, even when the leading unit is obtained after transposition at this step. The shift is also not performed when there are no zeros in the most significant bits before the pair 10 obtained after the transposition. The considered actions are illustrated by the following example of performing two successive iterations of this algorithm, where at one iteration (15) only transposition (T") is performed, and at the other iteration (16) the transposition is supplemented by a shift (T"+S"): In the right-shift transposition algorithm, conceptually similar steps are performed at each step. Only transposition ensures that the rightmost bits of 01 are replaced by 10 (instead of the leftmost ones), and then all the ones to the right of it are shifted to the least significant bits. As before, the shift is performed only if there are units that can be shifted to the right. The considered actions are illustrated by the following example of performing two successive iterations of this algorithm, where at one iteration (3) only transposition (T") is performed, and at the other iteration (4) the transposition is supplemented by a shift (T"+S"): It should be noted that the iterations of both algorithms can be written in additive form if binary combinations are interpreted as integers in the base 2 number system. In particular, for the transposition algorithm with a right shift, each next binary combination (B" n ,…B" j , …B" 1), can always be obtained from the current combination (B n,…B j,…B 1) by performing the operations of adding integers using the following additive formula: In this additive formula, the exponents of powers of twos f and t denote, respectively, the number of low-order zero digits of the current binary combination and the number of ones in a row to the left of them. For example, for the 4th binary combination (001110) of n=6 digits f =1 and t =3. Therefore, calculating the next binary combination using the additive formula at iteration 5 will give the following result, equivalent to performing the transposition and shift operations: For a comparative analysis of the considered transposition algorithms with left and right shifts, it is advisable to compare the sequences of binary combinations that they generate in their iterations. The following table shows two such sequences of binary combinations of 4 elements of 2, which are obtained by the left (TSL) and right (TSR) shift algorithms, respectively: Comparing these 2 sequences, you can see that they are reverse mirror. This means that any two binary combinations that are located in them at the same distance from the mutually opposite ends of their sequences are a mirror image of each other, that is, they coincide when the indexing of the bits in any of them is reversed. For example, the second binary pattern from the beginning of the TSL sequence (0101) is a mirror image of the binary pattern (1010) that is second from the end of the TSR sequence. In general, any binary combination with number i of one sequence is a mirror image of a binary combination with number (ni+1) of another sequence. This relationship between these sequences is a consequence of the symmetrical nature of the transposition and shift operations in the two considered algorithms for enumerating binary combinations. It should be noted that the binary format can also be used to record combinations with repetitions of elements. To do this, it is necessary to establish a one-to-one correspondence between combinations with repetitions and binary combinations, which are constructed as follows. Let there be an arbitrary combination with repetitions, which is obtained by choosing m optionally different elements from the n elements of the generating set. To establish the desired match, you must first add all the elements of the forming set (cat) to the combination, and then sort the resulting concatenation (sort) so that all identical elements are side by side. The result is a sequence of (n+m) elements, where there are n groups of identical elements. There will be a total of (n+m1) gaps between elements, among which there will be (n1) gaps between groups of identical elements and m gaps between elements within groups. For clarity, you can place the symbols “|” in the indicated spaces. and correspondingly. If we now match 1 to the spaces between groups (|) and 0 to all other spaces (), we get a binary combination. It is formed by a binary set of (n+m1) bits, where (n1) are ones and m zero bits, the location of which uniquely corresponds to the original combination with repetitions of elements n through m. The considered transformation technique is illustrated by the following example of constructing a binary combination (1001101) using a combination with repetitions (BBD), the elements of which are selected from the generating set of the first five Latin letters: In general, the number of such binary sets determines the number of ways to arrange (n1) ones (or m zeros) in (n+m1) binary digits. This value is obviously equal to the number of combinations from (n+m1) by (n1) or by m, that is, C(n+m1,n1) or C(n+m1,m), which is equal to the number of combinations with repetitions f( n,m) of n elements, m each. Thus, having a one-to-one correspondence between combinations with repetitions and binary combinations, it is legitimate to reduce the enumeration of combinations with repetitions to enumeration of binary combinations, for example, using transposition algorithms with left or right shift. After this, you only need to restore the required combinations with repetitions using the resulting binary combinations. This can always be done by using the following recovery technique. Let the main set, from the elements of which combinations with repetitions of m not necessarily different elements be formed, be ordered in an arbitrary way so that each of its elements has a certain serial number from 1 to n. Let us also implement the enumeration of binary combinations of (n+m1) binary digits, where (n1) ones and m zero digits. Each resulting binary combination can be supplemented on the left with a fictitious unit digit, and all unit digits can be numbered from left to right with integers from 1 to n. Then the number of zeros in a row after each i-th unit of the binary combination will be equal to the number of instances of the i-th element of the main set in the corresponding combination with repetitions. The considered technique is illustrated by the following example, where, using a binary combination (1001101), a combination with repetitions of BBD is restored, the elements of which are selected from the generating set of the first five Latin letters, written in alphabetical order, and the overline indicates elements that are absent in this combination: By performing similar actions in the conditions of this example, you can list all 35 binary combinations that form 7-bit binary sets, where there are 4 ones and 3 zeros, and restore the corresponding combinations with repetitions of 5 elements of 3. Winter was approaching, and Khoma and Suslik decided to stock up on peas. All day they ran to the barn and carried several pods: Khoma, four, and Suslik, two. By evening, they counted all the pods that they had harvested and wondered how to divide these peas now. Khoma argued that if he dragged twice as much at a time as Suslik, then he should get twice as many peas. Suslik reasonably objected to this that, firstly, Khoma’s speed is noticeably lower than Suslik’s, and, secondly, who knows, maybe Khoma only ran away once or twice, and the rest of the time he was idle... Help your friends understand this difficult situation at least a little. Determine all possible options for how many pods Suslik brought and how many Khoma. In the first line there is a natural even number M – the number of stolen pods, 2 ≤ M ≤ 1000. All possible combinations of the quantities of pods brought by Suslik and Khoma, one combination per line. Each combination represents two non-negative integers separated by a space: the first number is the number of pods brought by Suslik, the second – brought by Khoma. Sort the combinations in descending order of the first number. #include using namespace std ; int main()( int a, b = 0; cin >> a ; while (a >= 0 ) ( cout<<
a
<<
" "
<<
b
<<
"\n"
;
a -= 4 ; b += 4 ; return 0 ; Let a be the number of pods brought by Homa and b be the number of pods brought by Suslik. Since, according to the conditions of the problem, Khoma carried only four pods, we will consider a = a-4 and b = b + 4 in order to thus enumerate all possible combinations of the numbers of pods brought by Suslik and Khoma. Let's also use a loop while, which will repeat the action described above until a \geq 0. In the answer we print all possible combinations of the numbers of pods brought by friends, one per line, ordered in descending order of the first number. Example // Combinations of 3 out of 52 for (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Here we will look at a more complex problem, the solution of which I have not found in RuNet (however, I will give one link, but that formula is clearly incorrect) - based on the combination itself (in this case, a set of three numbers) find its index. Let us assume, for definiteness, after ordering i1 = 3, i2 = 7, i3 = 12. A typical generation algorithm is that we generate combinations of 2 out of 52, and for each such combination in a nested loop we generate combinations of 3 out of 50, and check that the indices (i3, i4, i5) in the nested combination do not coincide with the indices (i1, i2) in external combination: C++ code // EXTERNAL COMBINATION for (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
C++ code if (i3 >= i1) --i3; if (i3 >= i2) --i2; // similar for i4, i5 Example code for split index by 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Index of the combination of 2 out of 52, multiplied by C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // “Re-index” the internal group so that the numbering is 0...49 if (i3 >= i1) --i3; if (i3 >= i2) --i3; if (i4 >= i1) --i4; if (i4 >= i2) --i4; if (i5 >= i1) --i5; if (i5 >= i2) --i5; // Now add the index of the combination by 3 // 0: // SUM for n = 0 by i3-1 COMBINATIONS (2, 49-n) // = SUM for m = 50-i3 by 49 (m * (m-1) / 2) offset += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // SUM for n = i3+1 to i4-1 COMBINATIONS (1, 49-n) offset += (((48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SUM for n = i4+1 to i5-1 (1) offset += (i5 - i4 - 1); return offset ; ) In general, I would divide combinatorial algorithms into the following classes: Number of combinations Combination from n By k called a set k elements selected from data n elements. Sets that differ only in the order of the elements (but not in composition) are considered identical; this is why combinations differ from placements. Number of combinations of n By k
equal to the binomial coefficient For a fixed value n generating function of numbers of combinations with repetitions from n By k is: The two-dimensional generating function of numbers of combinations with repetitions is: Wikimedia Foundation. 2010. 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 the external conditions during photography (usually the brightness of the subject and the photosensitivity of the photographic material used). Any value of E. h. can be selected several times. combinations aperture number... ... Big Encyclopedic Polytechnic Dictionary A form of number that distinguishes two objects both in relation to a single object and in relation to many objects. This form does not exist in modern Russian, but remnants of its influence remain. 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 method of construction... ... 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 identical, these combinations ... ... Wikipedia Engaged in the study of events the occurrence of which is not known with certainty. It allows us to judge the reasonableness of expecting the occurrence of some events compared to others, although assigning numerical values to the probabilities of events is often unnecessary... ... Collier's Encyclopedia 1) the same as mathematical combinatorial analysis. 2) A section of 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 sharply diverges from generally accepted, established opinion, a denial of what seems “unconditionally correct”; in a narrower sense, two opposing statements, for... ... Philosophical Encyclopedia - (or the principle of inclusions and exclusions) a combinatorial formula that allows you to determine the cardinality of the union of a finite number of finite sets, which in the general case can intersect with each other ... Wikipedia A mathematical theory concerned with determining the number of different ways of distributing given objects in a known order; is especially important in the theory of equations and probability theory. The simplest tasks of this kind are... ... Encyclopedic Dictionary F.A. Brockhaus and I.A. EfronInput data
Output
Tests
Input data
Output
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
Program code
The solution of the problem
Combination index
Each combination, permutation, arrangement and other combinatorial objects can be associated with an index - this is the number in which it appears when iterating through this algorithm.
There is an option to search “head-on”. We turn on the combination counter, take the algorithm above and try everything until we reach the desired option. This option has a very high time complexity, so we will discard this option.
Let's assume that the input contains numbers i1, i2, i3. First of all, we need to arrange them in ascending order (note that the generation algorithm itself, given above, always produces them in ordered form, although the very concept of “combination” implies an arbitrary order).
This means we “went through” all combinations where i1 was equal to 0, 1 and 2.
For i1 = 0, we have gone through C(2, 51) combinations, since the indices i1, i2 go through all combinations of 2 of the 51 numbers.
For i1 = 1 we went through C(2, 50) combinations.
For i1 = 2 we went through C(2, 49) combinations.
In total, we went through SUM (from n = 0 to n = i1-1) C(2, 51-n).
For i1 = 3, let’s consider those combinations that we went through while running through index i2 (and for us it starts with i2 = i1+1 = 4).
When i2 = 4, C(1, 47) combinations passed, when i2 = 5, C(1, 46) combinations passed, when i2 = 6, C(1, 45) combinations passed.
By complete analogy, for i2 = 7 we consider the combinations that the index i3 ran through.
We get the general formula:
The required combination index = SUM (from n = 0 to i1-1) C(2, 51-n) + SUM (from n = i1+1 to i2-1) C(1, 51-n) + SUM (from n = i2+1 to i3-1) C (0, 51-n).Subset index
In combinatorics there is a more complex object - partitioning into subsets. For example, splitting a 52-element set into three subsets of, say, 2, 3, and 47 elements, respectively, where the order of the elements within each subset is unimportant. (By the way, a combination of 2 out of 52 is simply a special case of splitting into two subsets of 2 and 50 elements, respectively).
Again, each such partition has its own index.
It turns out that our algorithm for finding the combination index can be modified to find the partition index.
It should be noted that we need to arrange the indices in the “external combination” i1, i2 among themselves, and the indices i3, i4, i5 among themselves, but independently of the first two.
It should also be taken into account that in a “nested combination” we are essentially working with a 50-element set, but the indices i3, i4, i5 need to be “shifted” in a certain way so that they change not from 0 to 51, but from 0 to 49:
(so to speak, we cut out indices i1, i2 from our 52-element set and then shift the remaining set to close the holes, while indices i3-i5 are shifted).
It should be taken into account that inside each “external” combination we have exactly C(3, 50) “nested” combinations.
Then the algorithm will be reduced to the following:
COMBINATION_INDEX (i1, i2 of 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 of 50 after index shift). Bringing algorithms to constant complexity
I should immediately note that an “error” occurs in the formula if, for example, i1 = 0 (we count the sum for n = from 0 to -1) or i2 = 1 (we count the sum from 1 to 0). In fact, in such cases the corresponding sum should be taken equal to zero, and the result will be correct.
I should also pay attention to the time complexity of our algorithms: they have linear complexity, provided that you consider C to be constant time. This is already much better than brute force.
But actually (in our case 52) nothing prevents us from reducing the algorithm to constant complexity. To do this, we will apply knowledge of mathematics and analytically calculate all the amounts.
For example, the number of combinations C(2, K), if you “expand” it in the form of a formula K! / ((K-2)! * 2!), reduces to a polynomial of the 2nd degree. And since we have it under the sum sign, we can apply the formulas for the sum of Nth powers of numbers in the natural series (see Wikipedia) and get a single polynomial of the 3rd degree. Which obviously has constant time complexity. (Moreover, the “error” that I cited at the beginning of the subtitle does not manifest itself in any way; the formula remains correct).
I repeat, this for a fixed dimension of the base set. However, I am sure that with the help of metaprogramming you can “teach” the compiler so that it does this work for you. Afterword
In my poker simulator (Texas Hold'em), I wanted to calculate and store the winning probabilities in advance for all possible combinations of my hand cards (2 pieces) and all flop cards (3 cards on the table). This corresponds to dividing the 52-set by 2, 3, 47 subsets.
Calculated and saved.
But when it came time to read data from a file for a specific combination, I really didn’t want to calculate something for a long time or search in a gigabyte file. Now I just determine the offset in the file and read directly what I need.
It would be interesting to have a reference book on combinatorial algorithms for all combinatorial objects, including permutations, combinations, placements, subsets, combinations with repetitions, placements with repetitions. Explicit formulas
Links
See what “Number of combinations” is in other dictionaries:
Books