NationMaster - Encyclopedia: Combination

In combinatorial mathematics, a combination is an un-ordered collection of unique sizes. (An ordered collection is called a permutation.) Given S, the set of all possible unique elements, a combination is a subset of the elements of S. The order of the elements in a combination is not important (two lists with the same elements in different orders are considered to be the same combination). Also, the elements cannot be repeated in a combination (every element appears uniquely once); this is often referred to as "without replacement/repetition". This is because combinations are defined by the elements contained in them, thus the set {1,1,2} is the same as {2,1,1}. For example, from a 52-card deck any 5 cards can form a valid combination (a hand). The order of the cards doesn't matter and there can be no repetition of cards. Combination may mean: in mathematics, a combination of members of a set is a subset. ... Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... Permutation is the rearrangement of objects or symbols into distinguishable sequences. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... Superset redirects here. ... A hand in poker can mean any of the following: A unit of play consisting of a deal, one or more rounds of betting, and possibly a showdown. ...

A k-combination (or k-subset) is a subset with k elements. 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"): In mathematics, the concept of hypergraph generalizes the notion of a graph. ... In mathematics, particularly in combinatorics, a binomial coefficient is a coefficient of any of the terms in the expansion of the binomial (x+1)n. ...

$C^k_n = {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. For factorial rings in mathematics, see unique factorisation domain. ...

As an 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.$

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). In mathematics, a multiset (or bag) is a generalization of a set. ...

A combination is a special case of a partition of a set; specifically, a partition into two sets of size k and n − k. A partition of U into 6 blocks: an Euler diagram representation. ...

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)) }.$

Example:

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

You get the same result for $n - k$ as for k. Therefore, when k is more than half of n, it may be easier to compute using $n - k$ in place of k.

External links

Excellent Review of Combinations-PlainMath.Net Example and how to solve a combination
Many Common types of permutation and combination math problems, with detailed solutions
The Unknown Formula For combinations when choices can be repeated and order does NOT matter
Web-based calculator of permutations and combinations

Categories: Combinatorics

Results from FactBites:

Combination lock - Wikipedia, the free encyclopedia (618 words)
	A combination lock is a type of lock in which a sequence of numbers or symbols is used to open the lock.
	The notches on the disc correspond to the numerals in the correct combination.
	For example, early combination padlocks made by Master lock could be cracked by pulling on the shackle of the lock and turning the dial until it stopped; each numeral in the combination could be revealed in this manner.

Combination - Wikipedia, the free encyclopedia (163 words)
	It has been suggested that Permutations and combinations be merged into this article or section.
	Given S, the set of all possible unique elements, a combination is a subset of the elements of S.
	The order of the elements in a combination is not important (two lists with the same elements in different orders are considered to be the same combination).

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

See also GA_googleFillSlot("encyclopedia_square");

External links

See also