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^k\_n\; =\; \{n\; \backslash choose\; k\}\; =\; \backslash frac\{n!\}\{k!(n-k)!\}.$

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

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

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\; \backslash choose\; k\}\; =\; \backslash frac\; \{\; (\; n\; -\; 0\; )\; \}\{\; (k\; -\; 0)\; \}\; \backslash times\; \backslash frac\; \{\; (\; n\; -\; 1\; )\; \}\{\; (k\; -\; 1)\; \}\; \backslash times\; \backslash frac\; \{\; (\; n\; -\; 2\; )\; \}\{\; (k\; -\; 2)\; \}\; \backslash times\; \backslash frac\; \{\; (\; n\; -\; 3\; )\; \}\{\; (k\; -\; 3)\; \}\; \backslash times\; \backslash cdots\; \backslash times\; \backslash frac\; \{\; (\; n\; -\; (k\; -\; 1)\; )\; \}\{\; (k\; -\; (k\; -\; 1))\; \}.$

Example:

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

See also

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

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

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