Combination

This MedLibrary.org supplementary page on Combination is provided directly from the open source Wikipedia as a service to our readers. Please see the note below on authorship of this content, as well as the Wikipedia usage guidelines. To search for other content from our encyclopedia supplement, please use the form below:

Related Sponsors

BM Pharmacy Generic pharmaceuticals at unbeatable prices. Insomnia, men's health, hair health, pain control. bmpharmacy.com
Online Pharmacy Carisoprodol, tadalafil, sildenafil, vardenafil and more... xlpharmacy.com
MedBasket.com Discreet. Inexpensive. Fast shipping. Great selection. What more can we say? medbasket.com
Frugalmed 2000 reasons to shop with us first. frugalmed.com
Ads by Tiva

For other uses, see Combination (disambiguation).

In combinatorial mathematics, a combination is an un-ordered collection of distinct elements, usually of a prescribed size and taken from a given set. (An ordered collection of distinct elements would sometimes be called a permutation, but that term is ambiguous.) Given such a set S, a combination of elements of S is just a subset of S, where as always for (sub)sets the order of the elements is not taken into account (two lists with the same elements in different orders are considered to be the same combination). Also, as always for (sub)sets, no elements can be repeated more than once in a combination; this is often referred to as a "collection without repetition". For instance, {1,1,2} is not a combination of three digits; as a set this is the same as {1,2,1} or as {2,1,1}. On the contrary, a poker hand can be described as a combination of 5 cards from a 52-card deck: the order of the cards doesn't matter, and there can be no identical cards among the 5.

A k-combination (or k-subset) is a subset with k elements.

Contents

Number of k-combinations from a set

The number of k-combinations (each of size k) from a set S with n elements (size n) is the binomial coefficient (also known as the "choose function"):

C^n_k = {n \choose k} = \frac{n!}{k!(n-k)!}.

where n is the number of objects from which you can choose and k is the number to be chosen, and n! denotes the factorial.

The definition can be understood by considering a list of n elements; the list can be ordered n! ways, and for each possible ordering can be partitioned into the first k elements followed by the remaining n − k elements. The first partition is then a selection of k elements from the original list and all those partitions from every ordering cover all such selections. The complete permutation of the original list produces duplicate selections, however; some permutations result in a permuted but identical set for the first partition, and so we divide by k! to remove these, and other permutations result in permuted second partitions, and so we divide by (n − k)! to remove these.

The use of the definition in calculation is not always straightforward. For example, the number of five-card hands possible from a standard fifty-two card deck is:

{52 \choose 5} = \frac{n!}{k!(n-k)!} = \frac{52!}{5!(52-5)!} = \frac{52!}{5!47!} = 2598960.

Since it is impractical to calculate n! if the value of n is very large, a more efficient algorithm is

{n \choose k} = \frac { ( n - 0 ) }{ (k - 0) } \times \frac { ( n - 1 ) }{ (k - 1) } \times \frac { ( n - 2 ) }{ (k - 2) } \times \frac { ( n - 3 ) }{ (k - 3) } \times \cdots \times \frac { ( n - (k - 1) ) }{ (k - (k - 1)) }.

which gives

{52 \choose 5} = \frac { 52 }{ 5 } \times \frac { 51 }{ 4 } \times \frac { 50 }{ 3 } \times \frac { 49 }{ 2 } \times \frac { 48 }{ 1 } = 2598960.

This method of calculation can be seen immediately from the recursive definition of the choose function:

{n \choose k+1} = {n \choose k}\frac{n-k}{k+1}

with a base case of {n\choose 0}=1. It can be argued that {n\choose 1}=n is a more natural base case but the former follows easily from the latter anyway.

This second definition can be understood as stating that when adding an element to the selection, there are n − k elements to choose from, and so this increases the number of possible selections by that much, but doing this to all selections produces duplicates (e.g. \{a,b\}\cup\{c\}=\{a,c\}\cup\{b\}) and so we divide by the size of the selection since that is the number of possibilities for the last element added.

Since as explained above a combination is a special case of a partition of a set; specifically, a partition into two sets of size k and n − k, you get the same number of combinations if you substitute k with n − k. Therefore, when k is more than half of n, it may be easier to compute the binomial coefficient using n − k in place of k.

Number of combinations with repetition

The number of combinations with repetition can be calculated as:

{{(n + k - 1)!} \over {k!(n - 1)!}} = {{n + k - 1} \choose {k}} = {{n + k - 1} \choose {n - 1}}

For example, if you have ten types of donuts (n) on a menu to choose from and you want three donuts (k) there are (10 + 3 − 1)! / 3!(10 − 1)! = 220 ways to choose (see also multiset).

See also

External links

Wikipedia content modification information:

  • This page was last modified on 2 September 2008, at 23:05.

Wikipedia Authorship and Review

Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.

Wikipedia Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Combination".

The URL for this specific entry is:

All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.