HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
s). 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, a ''k''-combination of a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
''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 set does not matter.) If the set has ''n'' elements, the number of ''k''-combinations, denoted as C^n_k, is equal to the
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
\binom nk = \frac, which can be written using
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
s as \textstyle\frac whenever k\leq n, and which is zero when k>n. This formula can be derived from the fact that each ''k''-combination of a set ''S'' of ''n'' members has k!
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
s so P^n_k = C^n_k \times k! or C^n_k = P^n_k / k!. The set of all ''k''-combinations of a set ''S'' is often denoted by \textstyle\binom Sk. A combination is a combination of ''n'' things taken ''k'' at a time ''without repetition''. To refer to combinations in which repetition is allowed, the terms ''k''-selection, ''k''-
multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
, or ''k''-combination with repetition are often used. 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, a
poker hand In poker, players form sets of five playing cards, called ''hands'', according to the rules of the game. Each hand has a rank, which is compared against the ranks of other hands participating in the showdown to decide who wins the pot. In high ...
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 of ''k''-combinations

The number of ''k''-combinations from a given set ''S'' of ''n'' elements is often denoted in elementary combinatorics texts by C(n,k), or by a variation such as C^n_k, _nC_k, ^nC_k, C_ or even C_n^k (the last form is standard in French, Romanian, Russian, Chinese and Polish texts). The same number however occurs in many other mathematical contexts, where it is denoted by \tbinom nk (often read as "''n'' choose ''k''"); notably it occurs as a coefficient in the
binomial formula In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial into a sum involving terms of the form , where the ...
, hence its name binomial coefficient. One can define \tbinom nk for all natural numbers ''k'' at once by the relation (1 + X)^n = \sum_\binom X^k, from which it is clear that \binom = \binom = 1, and further, \binom = 0 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 Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Produ ...
over all elements of ''S'': \prod_(1+X_s); it has 2''n'' distinct terms corresponding to all the subsets of ''S'', each subset giving the product of the corresponding variables ''X''''s''. Now setting all of the ''X''''s'' equal to the unlabeled variable ''X'', so that the product becomes , the term for each ''k''-combination from ''S'' becomes ''X''''k'', so 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 to , one can use (in addition to the basic cases already given) the recursion relation \binom = \binom + \binom, for 0 < ''k'' < ''n'', which follows from =; this leads to the construction of
Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ot ...
. For determining an individual binomial coefficient, it is more practical to use the formula \binom nk = \frac. The
numerator A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
gives the number of ''k''-permutations of ''n'', i.e., of sequences of ''k'' distinct elements of ''S'', while the
denominator A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
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 to the numerator and the denominator, and canceling them out gives the relation \binom nk = \binom n, 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 A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...
of such a combination, which is an -combination. Finally there is a formula which exhibits this symmetry directly, and has the merit of being easy to remember: \binom nk = \frac, where ''n''! denotes the
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
of ''n''. It is obtained from the previous formula by multiplying denominator and numerator by !, so it is certainly computationally less efficient than 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: \binom nk = \begin \binom n \frac k &\quad \text k > 0 \\ \binom k \frac n &\quad \text k < n \\ \binom \frac nk &\quad \text n, k > 0 \end. Together with the basic cases \tbinom n0=1=\tbinom nn, these allow successive computation of respectively all numbers of combinations from the same set (a row in Pascal's triangle), of ''k''-combinations of sets of growing sizes, and of combinations with a complement of fixed size .


Example of counting combinations

As a specific example, one can compute the number of five-card hands possible from a standard fifty-two card deck as: = \frac = \frac = 2598960. 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: \begin &= \frac \\ pt &= \frac \\ pt &= \frac \\ pt &= \frac \\ pt &= \\ pt &= 2598960. \end Another alternative computation, equivalent to the first, is based on writing = \frac 1 \times \frac 2 \times \frac 3 \times \cdots \times \frac k, which gives = \frac1 \times \frac2 \times \frac3 \times \frac4 \times \frac5 = 2598960. When evaluated in the following order, , 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: \begin &= \frac = \frac = \frac \\ pt&= \tfrac \\ pt&= 2598960. \end


Enumerating ''k''-combinations

One can enumerate all ''k''-combinations of a given set ''S'' of ''n'' elements in some fixed order, which establishes a
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
from an interval of \tbinom nk integers with the set of those ''k''-combinations. Assuming ''S'' is itself ordered, for instance ''S'' = , 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 to ''S'' will not change the initial part of the enumeration, but just add the new ''k''-combinations of the larger set 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 to start at 0, then the ''k''-combination at a given place ''i'' in the enumeration can be computed easily from ''i'', and the bijection so obtained is known as the
combinatorial number system In mathematics, and in particular in combinatorics, the combinatorial number system of degree ''k'' (for some positive integer ''k''), also referred to as combinadics, or the Macaulay representation of an integer, is a correspondence between natural ...
. It is also known as "rank"/"ranking" and "unranking" in computational mathematics. There are many ways to enumerate ''k'' combinations. One way is to visit all the binary numbers less than 2''n''. 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). The positions of these 1 bits in such a number is a specific ''k''-combination of the set . Another simple, faster way is to track ''k'' index numbers of the elements selected, starting with (zero-based) or (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 .


Number of combinations with repetition

A ''k''-combination with repetitions, or ''k''-multicombination, or multisubset of size ''k'' from a set ''S'' of size ''n'' is given by a set 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 set of ''n'' elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. = ). Associate an index to each element of ''S'' and think of the elements of ''S'' as ''types'' of objects, then we can let x_i 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 In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
: x_1 + x_2 + \ldots + x_n = k. If ''S'' has ''n'' elements, the number of such ''k''-multisubsets is denoted by \left(\!\!\binom\!\!\right), a notation that is analogous to the
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
which counts ''k''-subsets. This expression, ''n'' multichoose ''k'', can also be given in terms of binomial coefficients: \left(\!\!\binom\!\!\right)=\binom. This relationship can be easily proved using a representation known as stars and bars. A solution of the above Diophantine equation can be represented by x_1 ''stars'', a separator (a ''bar''), then x_2 more stars, another separator, and so on. The total number of stars in this representation is ''k'' and the number of bars is ''n'' - 1 (since a separation into n parts needs n-1 separators). Thus, a string of ''k'' + ''n'' - 1 (or ''n'' + ''k'' - 1) symbols (stars and bars) corresponds to a solution if there are ''k'' stars in the string. Any solution can be represented by choosing ''k'' out of positions to place stars and filling the remaining positions with bars. For example, the solution x_1 = 3, x_2 = 2, x_3 = 0, x_4 = 5 of the equation x_1 + x_2 + x_3 + x_4 = 10 (''n'' = 4 and ''k'' = 10) can be represented by \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, \binom = \binom = 286, which is the number of 10-multisubsets of a set with 4 elements. As with binomial coefficients, there are several relationships between these multichoose expressions. For example, for n \ge 1, k \ge 0, \left(\!\!\binom\!\!\right)=\left(\!\!\binom\!\!\right). This identity follows from interchanging the stars and bars in the above representation.


Example of counting multisubsets

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 \left(\!\!\binom\!\!\right) = \binom3 = \binom = \frac = 20. This result can be verified by listing all the 3-multisubsets of the set ''S'' = . This is displayed in the following table. The second column lists the donuts you actually chose, the third column shows the nonnegative integer solutions _1,x_2,x_3,x_4/math> of the equation x_1 + x_2 + x_3 + x_4 = 3 and the last column gives the stars and bars representation of the solutions. where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.


Number of ''k''-combinations for all ''k''

The number of ''k''-combinations for all ''k'' is the number of subsets of a set of ''n'' elements. There are several ways to see that this number is 2''n''. In terms of combinations, \sum_\binom n k = 2^n, which is the sum of the ''n''th row (counting from 0) of the
binomial coefficients In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
in
Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ot ...
. These combinations (subsets) are enumerated by the 1 digits of the set of base 2 numbers counting from 0 to 2''n'' − 1, where each digit position is an item from the set of ''n''. Given 3 cards numbered 1 to 3, there are 8 distinct combinations ( subsets), including the
empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
: , \, = 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

There are various
algorithms In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...
to pick out a random combination from a given set or list.
Rejection sampling In numerical analysis and computational statistics, rejection sampling is a basic technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or "accept-reject algorithm" and is a type of ...
is extremely slow for large sample sizes. One way to select a ''k''-combination efficiently from a population of size ''n'' is to iterate across each element of the population, and at each step pick that element with a dynamically changing probability of \frac (see
Reservoir sampling Reservoir sampling is a family of randomized algorithms for choosing a simple random sample, without replacement, of items from a population of unknown size in a single pass over the items. The size of the population is not known to the algorit ...
). Another is to pick a random non-negative integer less than \textstyle\binom nk and convert it into a combination using the
combinatorial number system In mathematics, and in particular in combinatorics, the combinatorial number system of degree ''k'' (for some positive integer ''k''), also referred to as combinadics, or the Macaulay representation of an integer, is a correspondence between natural ...
.


Number of ways to put objects into bins

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 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 the
multinomial coefficient In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials. Theorem For any positive integer an ...
= \frac, where ''n'' is the number of items, ''m'' is the number of bins, and k_i is the number of items that go into bin ''i''. One way to see why this equation holds is to first number the objects arbitrarily from ''1'' to ''n'' and put the objects with numbers 1, 2, \ldots, k_1 into the first bin in order, the objects with numbers k_1+1, k_1+2, \ldots, k_2 into the second bin in order, and so on. There are 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 of k_1!\, k_2! \cdots k_m! distinct numberings, and the number of equivalence classes is \textstyle\frac. The binomial coefficient is the special case where ''k'' items go into the chosen bin and the remaining n-k items go into the unchosen bin: \binom nk = = \frac.


See also

*
Binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
*
Combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
*
Block design In combinatorial mathematics, a block design is an incidence structure consisting of a set together with a family of subsets known as ''blocks'', chosen such that frequency of the elements satisfies certain conditions making the collection of bl ...
*
Kneser graph In graph theory, the Kneser graph (alternatively ) is the graph whose vertices correspond to the -element subsets of a set of elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs a ...
*
List of permutation topics This is a list of topics on mathematical permutations. Particular kinds of permutations *Alternating permutation *Circular shift *Cyclic permutation *Derangement *Even and odd permutations—see Parity of a permutation *Josephus permutation ...
*
Multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
*
Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ot ...
*
Permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
*
Probability Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
*
Subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...


Notes


References

* * *
Erwin Kreyszig Erwin Otto Kreyszig (January 6, 1922 in Pirna, Germany – December 12, 2008) was a German Canadian applied mathematician and the Professor of Mathematics at Carleton University in Ottawa, Ontario, Canada. He was a pioneer in the field of applied ...
, ''Advanced Engineering Mathematics'', John Wiley & Sons, INC, 1999. * *


External links


Topcoder tutorial on combinatorics

C code to generate all combinations of n elements chosen as k


* ttp://www.murderousmaths.co.uk/books/unknownform.htm The Unknown FormulaFor combinations when choices can be repeated and order does ''not'' matter
Combinations with repetitions (by: Akshatha AG and Smitha B)
{Dead link, date=November 2019 , bot=InternetArchiveBot , fix-attempted=yes
The dice roll with a given sum problem
An application of the combinations with repetition to rolling multiple dice Combinatorics