Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Combination

From Wikipedia, the free encyclopedia
(Redirected fromCombinations)
This article is about the mathematics of selecting part of a collection. For other uses, seeCombination (disambiguation).
"COMBIN" redirects here. For other uses, seeCombin (disambiguation).
Selection of items from a set

Inmathematics, acombination is a selection of items from aset that has distinct members, such that the order of selection does not matter (unlikepermutations). 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. More formally, ak-combination of a setS is a subset ofk distinct elements ofS. So, two combinations are identicalif and only if each combination has the same members. (The arrangement of the members in each set does not matter.) If the set hasn elements, the number ofk-combinations, denoted byC(n,k){\displaystyle C(n,k)} orCkn{\displaystyle C_{k}^{n}}, is equal to thebinomial coefficient

(nk)=n(n−1)⋯(n−k+1)k(k−1)⋯1,{\displaystyle {\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},}

which can be written usingfactorials asn!k!(n−k)!{\displaystyle \textstyle {\frac {n!}{k!(n-k)!}}} wheneverk≤n{\displaystyle k\leq n}, and which is zero whenk>n{\displaystyle k>n}. This formula can be derived from the fact that eachk-combination of a setS ofn members hask!{\displaystyle k!} permutations soPkn=Ckn×k!{\displaystyle P_{k}^{n}=C_{k}^{n}\times k!} orCkn=Pkn/k!{\displaystyle C_{k}^{n}=P_{k}^{n}/k!}.[1] The set of allk-combinations of a setS is often denoted by(Sk){\displaystyle \textstyle {\binom {S}{k}}}.

A combination is a selection ofn things takenk at a timewithout repetition. To refer to combinations in which repetition is allowed, the termsk-combination with repetition,k-multiset,[2] ork-selection,[3] are often used.[4] 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.

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. For example, apoker hand can be described as a 5-combination (k = 5) of cards from a 52 card 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 ofk-combinations

[edit]
Main article:Binomial coefficient
"COMBIN" redirects here. For other uses, seeCombin (disambiguation).
3-element subsets of a 5-element set

The number ofk-combinations from a given setS ofn elements is often denoted in elementary combinatorics texts byC(n,k){\displaystyle C(n,k)}, or by a variation such asCkn{\displaystyle C_{k}^{n}},nCk{\displaystyle {}_{n}C_{k}},nCk{\displaystyle {}^{n}C_{k}},Cn,k{\displaystyle C_{n,k}} or evenCnk{\displaystyle C_{n}^{k}}[5] (the last form is standard in French, Romanian, Russian, and Chinese texts).[6][7] The same number however occurs in many other mathematical contexts, where it is denoted by(nk){\displaystyle {\tbinom {n}{k}}} (often read as "n choosek"); notably it occurs as a coefficient in thebinomial formula, hence its name binomial coefficient. One can define(nk){\displaystyle {\tbinom {n}{k}}} for all natural numbersk at once by the relation

(1+X)n=∑k≥0(nk)Xk,{\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}

from which it is clear that

(n0)=(nn)=1,{\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}

and further

(nk)=0{\displaystyle {\binom {n}{k}}=0}

fork>n{\displaystyle k>n}.

To see that these coefficients countk-combinations fromS, one can first consider a collection ofn distinct variablesXs labeled by the elementss ofS, and expand theproduct over all elements of S:

∏s∈S(1+Xs);{\displaystyle \prod _{s\in S}(1+X_{s});}

it has 2n distinct terms corresponding to all the subsets ofS, each subset giving the product of the corresponding variablesXs. Now setting all of theXs equal to the unlabeled variableX, so that the product becomes(1 +X)n, the term for eachk-combination fromS becomesXk, so that the coefficient of that power in the result equals the number of suchk-combinations.

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

(nk)=(n−1k−1)+(n−1k),{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}

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

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

(nk)=n(n−1)(n−2)⋯(n−k+1)k!.{\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.}

Thenumerator gives the number ofk-permutations ofn, i.e., of sequences ofk distinct elements ofS, while thedenominator gives the number of suchk-permutations that give the samek-combination when the order is ignored.

Whenk exceedsn/2, the above formula contains factors common to the numerator and the denominator, and canceling them out gives the relation

(nk)=(nn−k),{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},}

for 0 ≤k ≤n. This expresses a symmetry that is evident from the binomial formula, and can also be understood in terms ofk-combinations by taking thecomplement 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 to remember:

(nk)=n!k!(n−k)!,{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}

wheren! denotes thefactorial ofn. 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.

The last formula can be understood directly, by considering then! permutations of all the elements ofS. Each such permutation gives ak-combination by selecting its firstk elements. There are many duplicate selections: any combined permutation of the firstk 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:

(nk)={(nk−1)n−k+1kif k>0(n−1k)nn−kif k<n(n−1k−1)nkif n,k>0.{\displaystyle {\binom {n}{k}}={\begin{cases}\displaystyle {\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\\displaystyle {\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\\displaystyle {\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}.}

Together with the basic cases(n0)=1=(nn){\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}, these allow successive computation of respectively all numbers of combinations from the same set (a row in Pascal's triangle), ofk-combinations of sets of growing sizes, and of combinations with a complement of fixed sizen −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 card deck as:[8]

(525)=52×51×50×49×485×4×3×2×1=311,875,200120=2,598,960.{\displaystyle {\binom {52}{5}}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}

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:(525)=52!5!47!=52×51×50×49×48×47!5×4×3×2×1×47!=52×51×50×49×485×4×3×2=(26×2)×(17×3)×(10×5)×49×(12×4)5×4×3×2=26×17×10×49×12=2,598,960.{\displaystyle {\begin{alignedat}{2}{\binom {52}{5}}&={\frac {52!}{5!47!}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3}})\times (10\times {\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}}

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

(nk)=(n−0)1×(n−1)2×(n−2)3×⋯×(n−(k−1))k,{\displaystyle {\binom {n}{k}}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}},}

which gives

(525)=521×512×503×494×485=2,598,960.{\displaystyle {\binom {52}{5}}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{,}598{,}960.}

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, so no remainders ever occur.

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

(525)=n!k!(n−k)!=52!5!(52−5)!=52!5!47!=80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000120×258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000=2,598,960.{\displaystyle {\begin{aligned}{\binom {52}{5}}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\[6pt]&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}}

Enumeratingk-combinations

[edit]

One canenumerate allk-combinations of a given setS ofn elements in some fixed order, which establishes abijection from an interval of(nk){\displaystyle {\tbinom {n}{k}}} integers with the set of thosek-combinations. AssumingS is itself ordered, for instanceS = { 1, 2, ...,n }, there are two natural possibilities for ordering itsk-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 toS will not change the initial part of the enumeration, but just add the newk-combinations of the larger set after the previous ones. Repeating this process, the enumeration can be extended indefinitely withk-combinations of ever larger sets. If moreover the intervals of the integers are taken to start at 0, then thek-combination at a given placei in the enumeration can be computed easily fromi, and the bijection so obtained is known as thecombinatorial number system. It is also known as "rank"/"ranking" and "unranking" in computational mathematics.[9][10]

There are many ways to enumeratek combinations. One way is to trackk index numbers of the elements selected, starting with {0 ..k−1} (zero-based) or {1 ..k} (one-based) as the first allowedk-combination. Then, repeatedly move to the next allowedk-combination by incrementing the smallest index number for which this would not create two equal index numbers, at the same time resetting all smaller index numbers to their initial values.

Number of combinations with repetition

[edit]
See also:Multiset coefficient

Ak-combination with repetitions, ork-multicombination, ormultisubset of sizek from a setS of sizen is given by a set ofk not necessarily distinct elements ofS, 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 ofk elements from a set ofn elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. {2,1,2} = {1,2,2}). Associate an index to each element ofS and think of the elements ofS astypes of objects, then we can letxi{\displaystyle x_{i}} denote the number of elements of typei in a multisubset. The number of multisubsets of sizek is then the number of nonnegative integer (so allowing zero) solutions of theDiophantine equation:[11]

x1+x2+…+xn=k.{\displaystyle x_{1}+x_{2}+\ldots +x_{n}=k.}

IfS hasn elements, the number of suchk-multisubsets is denoted by

((nk)),{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right),}

a notation that is analogous to thebinomial coefficient which countsk-subsets. This expression,n multichoosek,[12] can also be given in terms of binomial coefficients:

((nk))=(n+k−1k).{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.}

This relationship can be easily proved using a representation known asstars and bars.[13]

Proof

A solution of the above Diophantine equation can be represented byx1{\displaystyle x_{1}}stars, a separator (abar), thenx2{\displaystyle x_{2}} more stars, another separator, and so on. The total number of stars in this representation isk and the number of bars isn - 1 (since a separation into n parts needs n-1 separators). Thus, a string ofk +n - 1 (orn +k - 1) symbols (stars and bars) corresponds to a solution if there arek stars in the string. Any solution can be represented by choosingk out ofk +n − 1 positions to place stars and filling the remaining positions with bars. For example, the solutionx1=3,x2=2,x3=0,x4=5{\displaystyle x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5} of the equationx1+x2+x3+x4=10{\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10} (n = 4 andk = 10) can be represented by[14]

★★★|★★||★★★★★.{\displaystyle \bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .}

The number of such strings is the number of ways to place 10 stars in 13 positions,(1310)=(133)=286,{\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,} which is the number of 10-multisubsets of a set with 4 elements.

Bijection between 3-subsets of a 7-set (left) and 3-multisets with elements from a 5-set (right).
This illustrates that(73)=((53)){\textstyle {\binom {7}{3}}=\left(\!\!{\binom {5}{3}}\!\!\right)}.

As with binomial coefficients, there are several relationships between these multichoose expressions. For example, forn≥1,k≥0{\displaystyle n\geq 1,k\geq 0},

((nk))=((k+1n−1)).{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).}This identity follows from interchanging the stars and bars in the above representation.[15]

Example of counting multisubsets

[edit]

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

((43))=(4+3−13)=(63)=6×5×43×2×1=20.{\displaystyle \left(\!\!{\binom {4}{3}}\!\!\right)={\binom {4+3-1}{3}}={\binom {6}{3}}={\frac {6\times 5\times 4}{3\times 2\times 1}}=20.}

This result can be verified by listing all the 3-multisubsets of the setS = {1,2,3,4}. This is displayed in the following table.[16] The second column lists the donuts you actually chose, the third column shows the nonnegative integer solutions[x1,x2,x3,x4]{\displaystyle [x_{1},x_{2},x_{3},x_{4}]} of the equationx1+x2+x3+x4=3{\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3} and the last column gives the stars and bars representation of the solutions.[17]

No.3-multisetEq. solutionStars and bars
1{1,1,1}[3,0,0,0]★★★|||{\displaystyle \bigstar \bigstar \bigstar |||}
2{1,1,2}[2,1,0,0]★★|★||{\displaystyle \bigstar \bigstar |\bigstar ||}
3{1,1,3}[2,0,1,0]★★||★|{\displaystyle \bigstar \bigstar ||\bigstar |}
4{1,1,4}[2,0,0,1]★★|||★{\displaystyle \bigstar \bigstar |||\bigstar }
5{1,2,2}[1,2,0,0]★|★★||{\displaystyle \bigstar |\bigstar \bigstar ||}
6{1,2,3}[1,1,1,0]★|★|★|{\displaystyle \bigstar |\bigstar |\bigstar |}
7{1,2,4}[1,1,0,1]★|★||★{\displaystyle \bigstar |\bigstar ||\bigstar }
8{1,3,3}[1,0,2,0]★||★★|{\displaystyle \bigstar ||\bigstar \bigstar |}
9{1,3,4}[1,0,1,1]★||★|★{\displaystyle \bigstar ||\bigstar |\bigstar }
10{1,4,4}[1,0,0,2]★|||★★{\displaystyle \bigstar |||\bigstar \bigstar }
11{2,2,2}[0,3,0,0]|★★★||{\displaystyle |\bigstar \bigstar \bigstar ||}
12{2,2,3}[0,2,1,0]|★★|★|{\displaystyle |\bigstar \bigstar |\bigstar |}
13{2,2,4}[0,2,0,1]|★★||★{\displaystyle |\bigstar \bigstar ||\bigstar }
14{2,3,3}[0,1,2,0]|★|★★|{\displaystyle |\bigstar |\bigstar \bigstar |}
15{2,3,4}[0,1,1,1]|★|★|★{\displaystyle |\bigstar |\bigstar |\bigstar }
16{2,4,4}[0,1,0,2]|★||★★{\displaystyle |\bigstar ||\bigstar \bigstar }
17{3,3,3}[0,0,3,0]||★★★|{\displaystyle ||\bigstar \bigstar \bigstar |}
18{3,3,4}[0,0,2,1]||★★|★{\displaystyle ||\bigstar \bigstar |\bigstar }
19{3,4,4}[0,0,1,2]||★|★★{\displaystyle ||\bigstar |\bigstar \bigstar }
20{4,4,4}[0,0,0,3]|||★★★{\displaystyle |||\bigstar \bigstar \bigstar }

Number ofk-combinations for allk

[edit]
See also:Binomial coefficient § Sum of coefficients row

The number ofk-combinations for allk is the number of subsets of a set ofn elements. There are several ways to see that this number is 2n. In terms of combinations,∑0≤k≤n(nk)=2n{\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}, which is the sum of thenth row (counting from 0) of thebinomial coefficients inPascal's triangle. These combinations (subsets) are enumerated by the 1 digits of the set ofbase 2 numbers counting from 0 to 2n − 1, where each digit position is an item from the set ofn.

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

|{{};{1};{2};{1,2};{3};{1,3};{2,3};{1,2,3}}|=23=8{\displaystyle |\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8}

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 variousalgorithms to pick out a random combination from a given set or list.Rejection sampling is extremely slow for large sample sizes. One way to select ak-combination efficiently from a population of sizen is to iterate across each element of the population, and at each step pick that element with a dynamically changing probability ofk−#samples chosenn−#samples visited{\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}} (seeReservoir sampling). Another is to pick a random non-negative integer less than(nk){\displaystyle \textstyle {\binom {n}{k}}} and convert it into a combination using thecombinatorial number system.

Number of ways to put objects into bins

[edit]

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

(nk1,k2,…,km)=n!k1!k2!⋯km!,{\displaystyle {\binom {n}{k_{1},k_{2},\ldots ,k_{m}}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},}

wheren is the number of items,m is the number of bins, andki{\displaystyle k_{i}} is the number of items that go into bini.

One way to see why this equation holds is to first number the objects arbitrarily from1 ton and put the objects with numbers1,2,…,k1{\displaystyle 1,2,\ldots ,k_{1}} into the first bin in order, the objects with numbersk1+1,k1+2,…,k2{\displaystyle k_{1}+1,k_{1}+2,\ldots ,k_{2}} into the second bin in order, and so on. There aren!{\displaystyle n!} distinct numberings, but many of them are equivalent, because only the set 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 ofk1!k2!⋯km!{\displaystyle k_{1}!\,k_{2}!\cdots k_{m}!} distinct numberings, and the number of equivalence classes isn!k1!k2!⋯km!{\displaystyle \textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}.

The binomial coefficient is the special case wherek items go into the chosen bin and the remainingn−k{\displaystyle n-k} items go into the unchosen bin:

(nk)=(nk,n−k)=n!k!(n−k)!.{\displaystyle {\binom {n}{k}}={\binom {n}{k,n-k}}={\frac {n!}{k!(n-k)!}}.}

See also

[edit]

Notes

[edit]
  1. ^Reichl, Linda E. (2016). "2.2. Counting Microscopic States".A Modern Course in Statistical Physics. WILEY-VCH. p. 30.ISBN 978-3-527-69048-0.
  2. ^Mazur 2010, p. 10
  3. ^Ryser 1963, p. 7 also referred to as anunordered selection.
  4. ^When the termcombination is used to refer to either situation (as in (Brualdi 2010)) care must be taken to clarify whether sets or multisets are being discussed.
  5. ^Uspensky 1937, p. 18
  6. ^High School Textbook for full-time student (Required) Mathematics Book II B (in Chinese) (2nd ed.). China: People's Education Press. June 2006. pp. 107–116.ISBN 978-7-107-19616-4.
  7. ^人教版高中数学选修2-3 [Mathematics textbook, volume 2-3, for senior high school, People's Education Press]. People's Education Press. p. 21.Archived from the original on 7 April 2023.
  8. ^Mazur 2010, p. 21
  9. ^Lucia Moura."Generating Elementary Combinatorial Objects"(PDF).Site.uottawa.ca.Archived(PDF) from the original on 9 October 2022. Retrieved10 April 2017.
  10. ^"SAGE : Subsets"(PDF).Sagemath.org. Retrieved10 April 2017.
  11. ^Brualdi 2010, p. 52
  12. ^Benjamin & Quinn 2003, p. 70
  13. ^In the articleStars and bars (combinatorics) the roles ofn andk are reversed.
  14. ^Benjamin & Quinn 2003, pp. 71 –72
  15. ^Benjamin & Quinn 2003, p. 72 (identity 145)
  16. ^Benjamin & Quinn 2003, p. 71
  17. ^Mazur 2010, p. 10 where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.

References

[edit]

External links

[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Combination&oldid=1280683775"
Category:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp