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 often 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. In combinatorics, they study questions about how many combinations of a certain type can be made from given objects (elements). The birth of combinatorics as a branch is associated with the works of B. Pascal and P. Fermat on the theory of gambling. A great contribution to the development of combinatorial methods was made by G.V. Leibniz, J. Bernoulli and L. Euler. The French philosopher, writer, mathematician and physicist Blaise Pascal (1623–1662) showed his outstanding mathematical abilities early on. Pascal's range of mathematical interests was very diverse. Pascal proved one thing Gottfried Wilhelm Leibniz (1646–1716) was a German philosopher, mathematician, physicist and inventor, lawyer, historian, and linguist. In mathematics, along with I. Newton, he developed differential and integral calculus. He made important contributions to combinatorics. His name, in particular, is associated with number-theoretic problems. Gottfried Wilhelm Leibniz had little impressive appearance and therefore gave the impression of a rather plain-looking person. One day in Paris, he went into a bookstore in the hope of purchasing a book by a philosopher he knew. When a visitor asked about this book, the bookseller, having examined him from head to toe, mockingly said: “Why do you need it? Are you really capable of reading such books?” Before the scientist had time to answer, the author of the book himself entered the shop with the words: “Greetings and respect to the Great Leibniz!” The seller could not understand that this was really the famous Leibniz, whose books were in great demand among scientists. In the future, the following will play an important role Lemma. Let in a set of elements, and in a set - elements. Then the number of all distinct pairs where will be equal to . Proof. Indeed, with one element from a set we can make such different pairs, and in total in a set of elements. Placements, permutations, combinations Let us have a set of three elements. In what ways can we select two of these elements? . Definition. Arrangements of a set of different elements by elements are combinations that are made up of given elements by > elements and differ either in the elements themselves or in the order of the elements. The number of all arrangements of a set of elements by elements is denoted by (from the initial letter of the French word “arrangement”, which means arrangement), where and . Theorem. The number of placements of a set of elements by elements is equal to Proof. Let's say we have elements. Let be possible placements. We will build these placements sequentially. First, let's define the first placement element. From a given set of elements it can be selected in various ways. After selecting the first element, there are still ways to select the second element, etc. Since each such choice gives a new placement, all these choices can be freely combined with each other. Therefore we have: Example. In how many ways can a flag be composed of three horizontal stripes of different colors if there is material in five colors? Solution. The required number of three-band flags: Definition. Permutation of a set of elements is the arrangement of elements in a certain order. Thus, all different permutations of a set of three elements are The number of all permutations of elements is indicated (from the initial letter of the French word “permutation”, which means “permutation”, “movement”). Therefore, the number of all different permutations is calculated by the formula Example. In how many ways can the rooks be placed on the chessboard so that they do not attack each other? Solution. The required number of rooks A-priory! Definition. Combinations of different elements by elements are combinations that are made up of given elements by elements and differ in at least one element (in other words, -element subsets of a given set of elements). As you can see, in combinations, unlike placements, the order of elements is not taken into account. The number of all combinations of elements, elements in each, is indicated (from the initial letter of the French word “combinasion”, which means “combination”). Numbers All combinations from a set of two are . Properties of numbers (\sf C)_n^k Indeed, each -element subset of a given -element set corresponds to one and only one -element subset of the same set. Indeed, we can select subsets of elements in the following way: fix one element; the number of -element subsets containing this element is equal to ; the number of -element subsets not containing this element is equal to . Pascal's triangle In this triangle, the extreme numbers in each row are equal to 1, and each non-extreme number is equal to the sum of the two numbers above it from the previous row. Thus, this triangle allows you to calculate numbers. Theorem. Proof. Let's consider a set of elements and solve the following problem in two ways: how many sequences can be made from the elements of a given 1 way. We select the first member of the sequence, then the second, third, etc. member Method 2. Let's first select elements from a given set, and then arrange them in some order Multiply the numerator and denominator of this fraction by: Example. In how many ways can you choose 5 numbers out of 36 in the game “Sportloto”? Required number of ways Tasks. 1.
Car license plates consist of 3 letters of the Russian alphabet (33 letters) and 4 numbers. How many different license plate numbers are there? Partitions are considered different if they differ either in numbers or in the order of their terms. How many different partitions of a number into terms are there? 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. Efron In this article we will talk about a special branch of mathematics called combinatorics. Formulas, rules, examples of problem solving - you can find all this here by reading the article to the very end. So what is this section? Combinatorics deals with the issue of counting any objects. But in this case, the objects are not plums, pears or apples, but something else. Combinatorics helps us find the probability of an event. For example, when playing cards - what is the probability that the opponent has a trump card? Or this example: what is the probability that you will get a white one from a bag of twenty marbles? It is for this kind of problem that we need to know at least the basics of this branch of mathematics. Considering the issue of basic concepts and formulas of combinatorics, we cannot help but pay attention to combinatorial configurations. They are used not only to formulate, but also to solve various examples. Examples of such models are: We will talk about the first three in more detail later, but we will pay attention to composition and partitioning in this section. When they talk about the composition of a certain number (for example, a), they mean representing the number a as an ordered sum of certain positive numbers. And a partition is an unordered sum. Before we move directly to the formulas of combinatorics and consideration of problems, it is worth paying attention to the fact that combinatorics, like other branches of mathematics, has its own subsections. These include: In the first case, we are talking about calculative combinatorics; the problems consider enumeration or counting of different configurations that are formed by elements of sets. As a rule, some restrictions are imposed on these sets (distinctiveness, indistinguishability, possibility of repetition, and so on). And the number of these configurations is calculated using the rules of addition or multiplication, which we will talk about a little later. Structural combinatorics includes the theories of graphs and matroids. An example of an extremal combinatorics problem is what is the largest dimension of a graph that satisfies the following properties... In the fourth paragraph, we mentioned Ramsey theory, which studies the presence of regular structures in random configurations. Probabilistic combinatorics is able to answer the question - what is the probability that a given set has a certain property. As you might guess, topological combinatorics applies methods in topology. And finally, the seventh point - infinitary combinatorics studies the application of combinatorics methods to infinite sets. Among the combinatorics formulas you can find quite simple ones, with which we have been familiar for quite a long time. An example is the sum rule. Suppose that we are given two actions (C and E), if they are mutually exclusive, action C can be performed in several ways (for example, a), and action E can be performed in b-ways, then any of them (C or E) can be performed in a + b ways . In theory, this is quite difficult to understand; we will try to convey the whole point using a simple example. Let's take the average number of students in one class - let's say it's twenty-five. Among them are fifteen girls and ten boys. One person on duty is assigned to each class every day. How many ways are there to appoint a class monitor today? The solution to the problem is quite simple; we will resort to the addition rule. The text of the problem does not say that only boys or only girls can be on duty. Therefore, it could be any of the fifteen girls or any of the ten boys. Applying the sum rule, we get a fairly simple example that a primary school student can easily handle: 15 + 10. After counting, we get the answer: twenty-five. That is, there are only twenty-five ways to assign a class on duty for today. The basic formulas of combinatorics also include the multiplication rule. Let's start with the theory. Let's say we need to perform several actions (a): the first action is performed in 1 ways, the second - in 2 ways, the third - in 3 ways, and so on until the last a-action, performed in 3 ways. Then all these actions (of which we have a total) can be performed in N ways. How to calculate unknown N? The formula will help us with this: N = c1 * c2 * c3 *…* ca. Again, nothing is clear in theory, so let’s move on to consider a simple example of applying the multiplication rule. Let's take the same class of twenty-five people, in which there are fifteen girls and ten boys. Only this time we need to choose two people on duty. They can be just boys or girls, or a boy and a girl. Let's move on to the elementary solution of the problem. We choose the first person on duty, as we decided in the last paragraph, we get twenty-five possible options. The second person on duty can be any of the remaining people. We had twenty-five students, we chose one, which means the second person on duty could be any of the remaining twenty-four people. Finally, we apply the multiplication rule and find that two officers on duty can be elected in six hundred ways. We obtained this number by multiplying twenty-five and twenty-four. Now we will look at another combinatorics formula. In this section of the article we will talk about permutations. We propose to immediately consider the problem using an example. Let's take billiard balls, we have nth number of them. We need to count how many options there are to arrange them in a row, that is, to create an ordered set. Let's start, if we don't have balls, then we also have zero options for placement. And if we have one ball, then the arrangement is also the same (mathematically this can be written as follows: P1 = 1). The two balls can be placed in two different ways: 1,2 and 2,1. Therefore, P2 = 2. Three balls can be arranged in six ways (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. What if there are not three such balls, but ten or fifteen? It would take a very long time to list all the possible options, then combinatorics comes to our aid. The permutation formula will help us find the answer to the question that interests us. Pn = n *P (n-1). If we try to simplify the formula, we get: Pn = n* (n - 1) *…* 2 * 1. And this is the product of the first natural numbers. This number is called factorial, and is denoted as n! Let's consider the problem. Every morning the counselor lines up his squad (twenty people). There are three best friends in the squad - Kostya, Sasha and Lesha. What is the probability that they will stand next to each other? To find the answer to the question, you need to divide the probability of a “good” outcome by the total number of outcomes. The total number of permutations is 20! = 2.5 quintillion. How to count the number of “good” outcomes? Let's assume that Kostya, Sasha and Lesha are one superman. Then we have only eighteen subjects. The number of permutations in this case is 18 = 6.5 quadrillion. With all this, Kostya, Sasha and Lesha can arbitrarily move among themselves in their indivisible three, and that’s 3 more! = 6 options. This means that we have 18 “good” arrangements in total! * 3! All we have to do is find the desired probability: (18! * 3!) / 20! Which equals approximately 0.016. If converted into percentages, it turns out to be only 1.6%. Now we will look at another very important and necessary combinatorics formula. Placement is our next issue, which we invite you to consider in this section of the article. We are going for complications. Suppose we want to consider possible permutations, not from the entire set (n), but from a smaller one (m). That is, we are considering permutations of n items by m. The basic formulas of combinatorics should not only be memorized, but understood. Even though they become more complicated, since we have not one parameter, but two. Suppose that m = 1, then A = 1, m = 2, then A = n * (n - 1). If we further simplify the formula and switch to notation using factorials, we get a completely laconic formula: A = n! / (n - m)! We reviewed almost all the basic combinatorics formulas with examples. Now let's move on to the final stage of considering the basic combinatorics course - getting to know combinations. Now we will choose m items from the n we have, and we will choose everything in every possible way. How then is this different from placement? We will not take into account the order. This unordered set will be the combination. Let us immediately introduce the notation: C. We take the placement of m balls out of n. We stop paying attention to order and end up with repeating combinations. To get the number of combinations we need to divide the number of placements by m! (m factorial). That is, C = A / m! Thus, there are only a few ways to select from n balls, which is approximately equal to the number of ways to select almost all of them. There is a logical expression for this: choosing a little is the same as throwing out almost everything. It is also important to mention at this point that the maximum number of combinations can be achieved when trying to select half of the items. We examined in detail the basic formulas of combinatorics: placement, permutation and combination. Now our task is to facilitate the selection of the necessary formula for solving a combinatorics problem. You can use the following fairly simple scheme: We looked at elements of combinatorics, formulas and some other issues. Now let's move on to consider the real problem. Imagine that you have a kiwi, an orange and a banana in front of you. Question one: in how many ways can they be rearranged? To do this, we will use the permutation formula: P = 3! = 6 ways. Question two: in how many ways can you choose one fruit? This is obvious, we have only three options - choose kiwi, orange or banana, but let's apply the combination formula: C = 3! / (2! * 1!) = 3. Question three: in how many ways can you choose two fruits? What options do we even have? Kiwi and orange; kiwi and banana; orange and banana. That is, there are three options, but this is easy to check using the combination formula: C = 3! / (1! * 2!) = 3 Question four: in how many ways can you choose three fruits? As you can see, there is only one way to choose three fruits: take kiwi, orange and banana. C = 3! / (0! * 3!) = 1. Question five: in how many ways can you choose at least one fruit? This condition means that we can take one, two or all three fruits. Therefore, we add C1 + C2 + C3 = 3 + 3 + 1 = 7. That is, we have seven ways to take at least one fruit from the table. Let's count in MS EXCEL the number of combinations of n elements by k. Using formulas, we will display on the sheet all the variants of combinations (English translation of the term: Combinations without repetition). Combinations of n different elements of k elements are combinations that differ in at least one element. For example, below are ALL 3-element combinations taken from a set consisting of 5 elements (1; 2; 3; 4; 5): (1; 2; 3); (1; 2; 4); (1; 2; 5); (1; 3; 4); (1; 3; 5); (1; 4; 5); (2; 3; 4); (2; 3; 5); (2; 4; 5); (3; 4; 5) Note: This is an article about counting the number of combinations using MS EXCEL. We recommend reading the theoretical foundations in a specialized textbook. Learning combinations from this article is a bad idea. In the example file, formulas are created to display all Combinations for given n and k. By specifying the number of elements of the set (n) and the number of elements that we select from it (k), using formulas we can display all Combinations. A car transporter can transport 4 cars. It is necessary to transport 7 different cars (LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo, Lada Largus). In how many different ways can the first car transporter be filled? The specific place of the car in the car transporter is not important. We need to determine the number Combinations 7 cars on 4 places of a car transporter. Those. n=7, and k=4. It turns out that there are 35 such options =NUMCOMB(7,4).
from the basic theorems of projective geometry (Pascal’s theorem), designed a summing machine (Pascal’s adding machine), gave a method for calculating binomial coefficients (Pascal’s triangle), was the first to accurately define and apply the method of mathematical induction for proof, made a significant step in the development of infinitesimal analysis, played an important role role in the emergence of probability theory. In hydrostatics, Pascal established its fundamental law (Pascal's law). Pascal's “Letters to a Provincial” was a masterpiece of French classical prose.
sets in each of which no element appears twice?
2.
There are 88 keys on the piano. In how many ways can you produce 6 sounds in succession?
3.
How many six-digit numbers are there that are divisible by 5?
4.
In how many ways can 7 different coins be placed in three pockets?
5.
How many five-digit numbers can you make that have the digit 5 at least once in their decimal notation?
6.
In how many ways can 20 people be seated at a round table, considering the ways to be the same, if they can be obtained one from the other by moving in a circle?
7.
How many five-digit numbers are there that are divisible by 5 and do not contain identical digits?
8.
On checkered paper with a cell side of 1 cm, a circle of radius 100 cm is drawn that does not pass through the tops of the cells and does not touch the sides of the cells. How many cells can this circle intersect?
9.
In how many ways can numbers be arranged in a row so that the numbers are adjacent and in ascending order?
10.
How many five-digit numbers can be made from digits if each digit can only be used once?
11.
From the word ROT, by rearranging the letters, you can get the following words: TOP, ORT, OTR, TRO, RTO. They are called anagrams. How many anagrams can you make from the word LOGARITHM?
12.
Let's call splitting natural number, its representation as a sum of natural numbers. Here, for example, are all the partitions of a number:
13.
How many three-digit numbers are there with non-increasing digit order?
14.
How many four-digit numbers are there with non-increasing digit order?
15.
In how many ways can 17 people be seated in a row so that they end up side by side?
16.
girls and boys are seated randomly in a row of seats. In how many ways can they be seated so that no two girls sit next to each other?
17.
girls and boys are seated randomly in a row of seats. In how many ways can they be seated so that all the girls sit next to each other?Explicit formulas
Links
See what “Number of combinations” is in other dictionaries:
Books
Combinatorial configurations
Sections
Addition rule
Multiplication rule
Rearrangement
Accommodation
Combination
How to choose a formula to solve a problem?
Example
Difference between Combinations and Placements
Displaying all combinations of Combinations
Task