toán tổ hợp

This article is about the mathematics of selecting part of a collection. For other uses, see Combination (disambiguation).

Bạn đang xem: toán tổ hợp

In mathematics, a combination is a selection of items from a mix that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an hãng apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an hãng apple and a pear; an hãng apple and an orange; or a pear and an orange. More formally, a k-combination of a mix S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members. (The arrangement of the members in each mix does not matter.) If the mix has n elements, the number of k-combinations, denoted by or , is equal lớn the binomial coefficient

which can be written using factorials as whenever , and which is zero when . This formula can be derived from the fact that each k-combination of a mix S of n members has permutations ví or .^[1] The mix of all k-combinations of a mix S is often denoted by .

A combination is a combination of n things taken k at a time without repetition. To refer lớn combinations in which repetition is allowed, the terms k-combination with repetition, k-multiset,^[2] or k-selection,^[3] are often used.^[4] If, in the above example, it were possible lớn have two of any one kind of fruit there would be 3 more 2-selections: one with two apples, one with two oranges, and one with two pears.

Although the mix of three fruits was small enough lớn write a complete list of combinations, this becomes impractical as the size of the mix increases. For example, a poker hand can be described as a 5-combination (k = 5) of cards from a 52 thẻ deck (n = 52). The 5 cards of the hand are all distinct, and the order of cards in the hand does not matter. There are 2,598,960 such combinations, and the chance of drawing any one hand at random is 1 / 2,598,960.

Number of k-combinations[edit]

The number of k-combinations from a given mix S of n elements is often denoted in elementary combinatorics texts by , or by a variation such as , , , or even ^[5] (the last size is standard in French, Romanian, Russian, Chinese^[6][7] and Polish texts^{[citation needed]}). The same number however occurs in many other mathematical contexts, where it is denoted by (often read as "n choose k"); notably it occurs as a coefficient in the binomial formula, hence its name binomial coefficient. One can define for all natural numbers k at once by the relation

from which it is clear that

and further,

for k > n.

To see that these coefficients count k-combinations from S, one can first consider a collection of n distinct variables X_s labeled by the elements s of S, and expand the product over all elements of S:

it has 2ⁿ distinct terms corresponding lớn all the subsets of S, each subset giving the product of the corresponding variables X_s. Now setting all of the X_s equal lớn the unlabeled variable X, ví that the product becomes (1 + X)ⁿ, the term for each k-combination from S becomes X^k, ví that the coefficient of that power in the result equals the number of such k-combinations.

Binomial coefficients can be computed explicitly in various ways. To get all of them for the expansions up lớn (1 + X)ⁿ, one can use (in addition lớn the basic cases already given) the recursion relation

for 0 < k < n, which follows from (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X); this leads lớn the construction of Pascal's triangle.

For determining an individual binomial coefficient, it is more practical lớn use the formula

The numerator gives the number of k-permutations of n, i.e., of sequences of k distinct elements of S, while the denominator gives the number of such k-permutations that give the same k-combination when the order is ignored.

When k exceeds n/2, the above formula contains factors common lớn the numerator and the denominator, and canceling them out gives the relation

for 0 ≤ k ≤ n. This expresses a symmetry that is evident from the binomial formula, and can also be understood in terms of k-combinations by taking the complement of such a combination, which is an (n − k)-combination.

Finally there is a formula which exhibits this symmetry directly, and has the merit of being easy lớn remember:

where n! denotes the factorial of n. It is obtained from the previous formula by multiplying denominator and numerator by (n − k)!, ví it is certainly computationally less efficient than thở that formula.

The last formula can be understood directly, by considering the n! permutations of all the elements of S. Each such permutation gives a k-combination by selecting its first k elements. There are many duplicate selections: any combined permutation of the first k elements among each other, and of the final (n − k) elements among each other produces the same combination; this explains the division in the formula.

From the above formulas follow relations between adjacent numbers in Pascal's triangle in all three directions:

Together with the basic cases , these allow successive computation of respectively all numbers of combinations from the same mix (a row in Pascal's triangle), of k-combinations of sets of growing sizes, and of combinations with a complement of fixed size n − k.

Example of counting combinations[edit]

As a specific example, one can compute the number of five-card hands possible from a standard fifty-two thẻ deck as:^[8]

Alternatively one may use the formula in terms of factorials and cancel the factors in the numerator against parts of the factors in the denominator, after which only multiplication of the remaining factors is required:

Xem thêm: sự tạo thành nước tiểu gồm những quá trình nào chúng diễn ra ở đâu

Another alternative computation, equivalent lớn the first, is based on writing

which gives

When evaluated in the following order, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, this can be computed using only integer arithmetic. The reason is that when each division occurs, the intermediate result that is produced is itself a binomial coefficient, ví no remainders ever occur.

Using the symmetric formula in terms of factorials without performing simplifications gives a rather extensive calculation:

Enumerating k-combinations[edit]

One can enumerate all k-combinations of a given mix S of n elements in some fixed order, which establishes a bijection from an interval of integers with the mix of those k-combinations. Assuming S is itself ordered, for instance S = { 1, 2, ..., n }, there are two natural possibilities for ordering its k-combinations: by comparing their smallest elements first (as in the illustrations above) or by comparing their largest elements first. The latter option has the advantage that adding a new largest element lớn S will not change the initial part of the enumeration, but just add the new k-combinations of the larger mix after the previous ones. Repeating this process, the enumeration can be extended indefinitely with k-combinations of ever larger sets. If moreover the intervals of the integers are taken lớn start at 0, then the k-combination at a given place i in the enumeration can be computed easily from i, and the bijection ví obtained is known as the combinatorial number system. It is also known as "rank"/"ranking" and "unranking" in computational mathematics.^[9][10]

There are many ways lớn enumerate k combinations. One way is lớn visit all the binary numbers less than thở 2ⁿ. Choose those numbers having k nonzero bits, although this is very inefficient even for small n (e.g. n = đôi mươi would require visiting about one million numbers while the maximum number of allowed k combinations is about 186 thousand for k = 10). The positions of these 1 bits in such a number is a specific k-combination of the mix { 1, ..., n }.^[11] Another simple, faster way is lớn track k index numbers of the elements selected, starting with {0 .. k−1} (zero-based) or {1 .. k} (one-based) as the first allowed k-combination and then repeatedly moving lớn the next allowed k-combination by incrementing the last index number if it is lower than thở n-1 (zero-based) or n (one-based) or the last index number x that is less than thở the index number following it minus one if such an index exists and resetting the index numbers after x lớn {x+1, x+2, ...}.

Number of combinations with repetition[edit]

A k-combination with repetitions, or k-multicombination, or multisubset of size k from a mix S of size n is given by a mix of k not necessarily distinct elements of S, where order is not taken into account: two sequences define the same multiset if one can be obtained from the other by permuting the terms. In other words, it is a sample of k elements from a mix of n elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. {2,1,2} = {1,2,2}). Associate an index lớn each element of S and think of the elements of S as types of objects, then we can let denote the number of elements of type i in a multisubset. The number of multisubsets of size k is then the number of nonnegative integer (so allowing zero) solutions of the Diophantine equation:^[12]

If S has n elements, the number of such k-multisubsets is denoted by

a notation that is analogous lớn the binomial coefficient which counts k-subsets. This expression, n multichoose k,^[13] can also be given in terms of binomial coefficients:

This relationship can be easily proved using a representation known as stars and bars.^[14]

As with binomial coefficients, there are several relationships between these multichoose expressions. For example, for ,

This identity follows from interchanging the stars and bars in the above representation.^[16]

Example of counting multisubsets[edit]

For example, if you have four types of donuts (n = 4) on a thực đơn lớn choose from and you want three donuts (k = 3), the number of ways lớn choose the donuts with repetition can be calculated as

This result can be verified by listing all the 3-multisubsets of the mix S = {1,2,3,4}. This is displayed in the following table.^[17] The second column lists the donuts you actually chose, the third column shows the nonnegative integer solutions of the equation and the last column gives the stars and bars representation of the solutions.^[18]

No.	3-multiset	Eq. solution	Stars and bars
1	{1,1,1}	[3,0,0,0]
2	{1,1,2}	[2,1,0,0]
3	{1,1,3}	[2,0,1,0]
4	{1,1,4}	[2,0,0,1]
5	{1,2,2}	[1,2,0,0]
6	{1,2,3}	[1,1,1,0]
7	{1,2,4}	[1,1,0,1]
8	{1,3,3}	[1,0,2,0]
9	{1,3,4}	[1,0,1,1]
10	{1,4,4}	[1,0,0,2]
11	{2,2,2}	[0,3,0,0]
12	{2,2,3}	[0,2,1,0]
13	{2,2,4}	[0,2,0,1]
14	{2,3,3}	[0,1,2,0]
15	{2,3,4}	[0,1,1,1]
16	{2,4,4}	[0,1,0,2]
17	{3,3,3}	[0,0,3,0]
18	{3,3,4}	[0,0,2,1]
19	{3,4,4}	[0,0,1,2]
20	{4,4,4}	[0,0,0,3]

Number of k-combinations for all k[edit]

The number of k-combinations for all k is the number of subsets of a mix of n elements. There are several ways lớn see that this number is 2ⁿ. In terms of combinations, , which is the sum of the nth row (counting from 0) of the binomial coefficients in Pascal's triangle. These combinations (subsets) are enumerated by the 1 digits of the mix of base 2 numbers counting from 0 lớn 2ⁿ − 1, where each digit position is an item from the mix of n.

Given 3 cards numbered 1 lớn 3, there are 8 distinct combinations (subsets), including the empty set:

Representing these subsets (in the same order) as base 2 numerals:

• 0 – 000
• 1 – 001
• 2 – 010
• 3 – 011
• 4 – 100
• 5 – 101
• 6 – 110
• 7 – 111

Probability: sampling a random combination[edit]

There are various algorithms lớn pick out a random combination from a given mix or list. Rejection sampling is extremely slow for large sample sizes. One way lớn select a k-combination efficiently from a population of size n is lớn iterate across each element of the population, and at each step pick that element with a dynamically changing probability of (see Reservoir sampling). Another is lớn pick a random non-negative integer less than thở and convert it into a combination using the combinatorial number system.

Number of ways lớn put objects into bins[edit]

A combination can also be thought of as a selection of two sets of items: those that go into the chosen bin and those that go into the unchosen bin. This can be generalized lớn any number of bins with the constraint that every item must go lớn exactly one bin. The number of ways lớn put objects into bins is given by the multinomial coefficient

where n is the number of items, m is the number of bins, and is the number of items that go into bin i.

One way lớn see why this equation holds is lớn first number the objects arbitrarily from 1 lớn n and put the objects with numbers into the first bin in order, the objects with numbers into the second bin in order, and ví on. There are distinct numberings, but many of them are equivalent, because only the mix of items in a bin matters, not their order in it. Every combined permutation of each bins' contents produces an equivalent way of putting items into bins. As a result, every equivalence class consists of distinct numberings, and the number of equivalence classes is .

The binomial coefficient is the special case where k items go into the chosen bin and the remaining items go into the unchosen bin:

See also[edit]

Notes[edit]

References[edit]

• Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pearson Prentice Hall, ISBN 978-0-13-602040-0
• Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
• Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Association of America, ISBN 978-0-88385-762-5
• Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs 14, Mathematical Association of America
• Uspensky, James (1937), Introduction lớn Mathematical Probability, McGraw-Hill

External links[edit]

• Topcoder tutorial on combinatorics
• C code lớn generate all combinations of n elements chosen as k
• Many Common types of permutation and combination math problems, with detailed solutions
• The Unknown Formula For combinations when choices can be repeated and order does not matter
• Combinations with repetitions (by: Akshatha AG and Smitha B)^{[permanent dead link]}
• The dice roll with a given sum problem An application of the combinations with repetition lớn rolling multiple dice