For other uses, see Combination (disambiguation).

In combinatorial mathematics, a k-combination of a finite set S is a subset of k distinct elements of S. Specifying a

subset does not arrange them in a particular order; by contrast, producing the k distinct elements in a specific order

defines a sequence without repetition, also called k-permutation (but which is not a permutation of S in the usual

sense of that term). As an example, a poker hand can be described as a 5-combination of cards from a 52-card deck:

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

The number of k-combinations of an n-element set is equal to the binomial coefficient . For this reason the set of

all k-combinations of a set X is sometimes denoted by .

Contents
[hide]

• 1 Number of k-combinations

• 2 Number of combinations with

repetition

• 3 See also

• 4 References

• 5 External links

[edit]Number of k-combinations

The number of k-combinations from a given set S of n elements of often denoted in elementary combinatorics texts

by C(n,k), or by a variation such as , nCk, nCk or even (the latter form is standard in French texts). The same

number however occurs in many other mathematical contexts, where it is denoted by ; notably it occurs as

coefficient in the binomial formula, hence its namebinomial coefficient. One can define for all natural

numbers k at once by the relation

from which it is clear that and for k > n. 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:

it has 2n distinct terms corresponding to all the subsets of S, each subset giving the product of the

corresponding variables Xs. Now setting all of the Xs equal to the unlabeled variable X, so that the product

becomes (1 + X)n, the term for each k-combination from Sbecomes Xk, so that 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 (1 + X)n, one can use (in addition to the basic cases already given) the recursion relation

which follows from (1 + X)n = (1 + X)n − 1(1 + X); the leads to the construction of Pascal's triangle.

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

In this formula the numerator gives the number of k-permutations of n, i.e., of sequences

of k distinct elements of S, while the denominatorgives 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

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 to remember:

where n! denotes the factorial of n. It is obtained from the previous formula by

multiplying denominator and numerator by (n − k)!, so it is certainly inferior as a

method of computation to 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 set (a row in Pascal's triangle),

of k-combinations of sets of growing sizes, and of

combinations with a complement of fixed sizen − k.

As a concrete example, one can compute the number of five-

card hands possible from a standard fifty-two card deck as:

An alternative, almost equivalent computation, is

which gives
Using the symmetric formula in terms of

factorials gives

which illustrates the size of such

a computation, and of the s 13,
14, 15 (preceded by
three unchosen
numbers: 3, 11, and
12) by bananas; there
are no chosen numbers
preceded by exactly 2
unchosen numbers,
and therefore no pears
in the selection. The
total number of possible
numbers involved.

[edit]Number
of
combinations with
repetition
See also: multiset coefficient

A k-combination with

repetitions, or k-

multicombination,

or multiset of size k from a

set S is given by a sequence

of k not necessarily distinct

elements of S, where order is

not taken into account: two

sequences of which one can be

obtained from the other by

permuting the terms define the

same multiset.

If S has n elements, the number

of such k-multicombinations is

also given by a binomial

coefficient, namely by

(the case where

both n and k are zero is

special; the correct value 1

(for the empty 0-

multicombination) is given

by left hand side ,

but not by the right hand

side ).

For example, if you have

ten types of donuts

(n = 10) on a menu to

choose from and you want

three donuts (k = 3), the

number of ways to choose

can be calculated as

The analogy with

the k-combination

case can be
 stressed by writing

the binomial

coefficient using

a rising factorial

power

There is an easy way to understand the above result. Label the elements of S with
numbers 0, 1, ..., n − 1, and choose a k-combination from the set of numbers { 1, 2,
..., n + k − 1 } (so that there are n − 1 unchosen numbers). Now change this k-
combination into a k-multicombination of S by replacing every (chosen) number x in
the k-combination by the element of S labeled by the number of unchosen
numbers less than x. This is always a number in the range of the labels, and it is
easy to see that every k-multicombination of S is obtained for one choice of a k-
combination.

A concrete example may be helpful. Suppose there are 4 types of fruits oranges
number(apple, orange,
pear, banana) at a grocery store, and you want to buy 12 pieces of fruit. So n = 4
and k = 12. Use label 0 for apples, 1 for oranges, 2 for pears, and 3 for bananas. A
selection of 12 fruits can be translated into a selection of 12 distinct numbers in the
range 1,...,15 by selecting as many consecutive numbers starting from 1 as there
are apples in the selection, then skip a number, continue choosing as many
consecutive numbers as there are oranges selected, again skip a number, then
again for pears, skip one again, and finally choose the remaining numbers (as many
as there are bananas selected). For instance for 2 apples, 7 oranges, 0 pears and 3
bananas, the numbers chosen will be 1, 2, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15. To recover
the fruits, the numbers 1, 2 (not preceded by any unchosen, and the numbers) are
replaced by apples, the numbers 4, 5, ..., 10 (preceded by one unchosen number: 3)
by

selection

s is