Combination

From Wikipedia for FEVERv2
Jump to navigation Jump to search

This article is about the mathematics of selecting part of a collection. Combination_sentence_0

For other uses, see Combination (disambiguation). Combination_sentence_1

"COMBIN" and "nCr" redirect here. Combination_sentence_2

For other uses, see Combin (disambiguation) and NCR (disambiguation). Combination_sentence_3

In mathematics, a combination is a selection of items from a collection, such that the order of selection does not matter (unlike permutations). Combination_sentence_4

For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. Combination_sentence_5

More formally, a k-combination of a set S is a subset of k distinct elements of S. If the set has n elements, the number of k-combinations is equal to the binomial coefficient Combination_sentence_6

Combinations refer to the combination of n things taken k at a time without repetition. Combination_sentence_7

To refer to combinations in which repetition is allowed, the terms k-selection, k-multiset, or k-combination with repetition are often used. Combination_sentence_8

If, in the above example, it were possible to 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. Combination_sentence_9

Although the set of three fruits was small enough to write a complete list of combinations, this becomes impractical as the size of the set increases. Combination_sentence_10

For example, a poker hand can be described as a 5-combination (k = 5) of cards from a 52 card deck (n = 52). Combination_sentence_11

The 5 cards of the hand are all distinct, and the order of cards in the hand does not matter. Combination_sentence_12

There are 2,598,960 such combinations, and the chance of drawing any one hand at random is 1 / 2,598,960. Combination_sentence_13

Number of k-combinations Combination_section_0

Main article: Binomial coefficient Combination_sentence_14

from which it is clear that Combination_sentence_15

and further, Combination_sentence_16

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

it has 2 distinct terms corresponding to all the subsets of S, each subset giving the product of the corresponding variables Xs. Combination_sentence_18

Now setting all of the Xs equal to the unlabeled variable X, so that the product becomes (1 + X), the term for each k-combination from S becomes X, so that the coefficient of that power in the result equals the number of such k-combinations. Combination_sentence_19

Binomial coefficients can be computed explicitly in various ways. Combination_sentence_20

To get all of them for the expansions up to (1 + X), one can use (in addition to the basic cases already given) the recursion relation Combination_sentence_21

for 0 < k < n, which follows from (1 + X) = (1 + X)(1 + X); this leads to the construction of Pascal's triangle. Combination_sentence_22

For determining an individual binomial coefficient, it is more practical to use the formula Combination_sentence_23

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. Combination_sentence_24

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

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. Combination_sentence_26

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

where n! Combination_sentence_28

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

The last formula can be understood directly, by considering the n! Combination_sentence_30

permutations of all the elements of S. Each such permutation gives a k-combination by selecting its first k elements. Combination_sentence_31

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. Combination_sentence_32

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

Example of counting combinations Combination_section_1

As a specific example, one can compute the number of five-card hands possible from a standard fifty-two card deck as: Combination_sentence_34

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: Combination_sentence_35

Another alternative computation, equivalent to the first, is based on writing Combination_sentence_36

which gives Combination_sentence_37

When evaluated in the following order, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, this can be computed using only integer arithmetic. Combination_sentence_38

The reason is that when each division occurs, the intermediate result that is produced is itself a binomial coefficient, so no remainders ever occur. Combination_sentence_39

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

Enumerating k-combinations Combination_section_2

There are many ways to enumerate k combinations. Combination_sentence_41

One way is to visit all the binary numbers less than 2. Combination_sentence_42

Choose those numbers having k nonzero bits, although this is very inefficient even for small n (e.g. n = 20 would require visiting about one million numbers while the maximum number of allowed k combinations is about 186 thousand for k = 10). Combination_sentence_43

The positions of these 1 bits in such a number is a specific k-combination of the set { 1, …, n }. Combination_sentence_44

Another simple, faster way is to 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 to the next allowed k-combination by incrementing the last index number if it is lower than n-1 (zero-based) or n (one-based) or the last index number x that is less than the index number following it minus one if such an index exists and resetting the index numbers after x to {x+1, x+2, …}. Combination_sentence_45

Number of combinations with repetition Combination_section_3

See also: Multiset coefficient Combination_sentence_46

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

a notation that is analogous to the binomial coefficient which counts k-subsets. Combination_sentence_48

This expression, n multichoose k, can also be given in terms of binomial coefficients: Combination_sentence_49

This relationship can be easily proved using a representation known as stars and bars. Combination_sentence_50

This identity follows from interchanging the stars and bars in the above representation. Combination_sentence_51

Example of counting multisubsets Combination_section_4

For example, if you have four types of donuts (n = 4) on a menu to choose from and you want three donuts (k = 3), the number of ways to choose the donuts with repetition can be calculated as Combination_sentence_52

Number of k-combinations for all k Combination_section_5

See also: Binomial coefficient § Sum of coefficients row Combination_sentence_53

Given 3 cards numbered 1 to 3, there are 8 distinct combinations (subsets), including the empty set: Combination_sentence_54

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

Combination_description_list_0

  • Combination_item_0_0
    • 0 – 000Combination_item_0_1
    • 1 – 001Combination_item_0_2
    • 2 – 010Combination_item_0_3
    • 3 – 011Combination_item_0_4
    • 4 – 100Combination_item_0_5
    • 5 – 101Combination_item_0_6
    • 6 – 110Combination_item_0_7
    • 7 – 111Combination_item_0_8

Probability: sampling a random combination Combination_section_6

See also Combination_section_7

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Combination.