Combination

From Wikipedia, the free encyclopedia

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

<math> C_k^n = {n \choose k} = \frac{n!}{k!(n-k)!}.</math>

As an example, the number of five-card hands possible from a standard fifty-two card deck is:

<math> {52 \choose 5} = \frac{n!}{k!(n-k)!} = \frac{52!}{5!(52-5)!} = 2598960.</math>

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 <math>n!</math> if the value of n is very large, a more efficient algorithm is

<math> {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)) }.</math>

Example:

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

[edit] See also

• Combinadic
• Combinatorics
• Multiset
• Permutation
  • List of permutation topics
• Probability

[edit] 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 solutionscs:Kombinace

de:Kombinatorik#Kombination ohne Zur.C3.BCcklegen fr:Combinaison (mathématiques) ko:조합 id:Kombinasi it:Combinazione lv:Kombinācija hu:Kombináció nl:Combinatie (wiskunde) ja:組合せ (数学) pl:Kombinacja bez powtórzeń pt:Combinação sem repetição ru:Сочетание sq:Kombinacioni sr:Комбинација fi:Kombinaatio sv:Kombination (matematik) ta:சேர்வு (கணிதம்) th:การจัดหมู่ zh:組合