Combination

For other uses, see Combination (disambiguation).

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.

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"):

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

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

A combination is a special case of a partition of a set; specifically, a partition into two sets of size k and n − k.

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.

See also

• Factorial
• Combinadic (how to enumerate combinations and generate i:th combination in a reasonably way)
• Combinatorics
• Multiset
• Permutation
  • List of permutation topics
• Probability

Combination listing from a group. a SIMPLE one pass algorithm Theory ( origin not known ) The nCr elements of the group are represented by the n bit binary numbers that have r positive bits.

eg if we are selecting  4 from  7    ABCDEFG
   71  1000111  indexes  A  EFG
   29  0011101  indexes   CDE G

To generate these index numbers get a number to binary function and add a counter of the number of 1 's.

assuming n is the number in the group r is the number to be picked Generic type program outline for x = 0 to 2^n-1 if x mod 2 =1 then count=count+1 , inString =binstring +"1" else binstring=binstring +"0" if count > r then exit next x if count = r then 'this binstring is one if the indices index to the combinations from any LIST.'

External links

• Article on 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