k-Combination

A k-Combination is a subset of k distinct elements of a given set.

• Context:
  • It can be defined as [math]\displaystyle{ \binom nk = \frac{n!}{k!(n-k)!} }[/math] where n is the set's number of elements.
• Example(s):
  • k-Combinations With Replacement Function,
  • k-Combinations Without Replacement.
  • …
• Counter-Example(s):
  • Random Combination,
  • Permutation.
• See: Combination, Mathematics, Permutation, Set, Binomial Coefficient, Factorial.

---

---

References

2018a

• (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Combination Retrieved:2018-8-3.
  • In mathematics, a combination is a selection of items from a collection, such that (unlike permutations) the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange.

    More formally, a k-combination of a set S is a subset of k distinct elements of S. If the set has n elements, the number of k-combinations is equal to the binomial coefficient : [math]\displaystyle{ \binom nk = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1}, }[/math] which can be written using factorials as [math]\displaystyle{ \textstyle\frac{n!}{k!(n-k)!} }[/math] whenever [math]\displaystyle{ k\leq n }[/math] , and which is zero when [math]\displaystyle{ k \gt n }[/math] . The set of all k-combinations of a set S is often denoted by [math]\displaystyle{ \textstyle\binom Sk }[/math] .

    Combinations refer to the combination of n things taken k at a time without repetition. To refer to combinations in which repetition is allowed, the terms k-selection, k-multiset, or k-combination with repetition are often used. If, in the above example, it were possible to have two of any one kind of fruit there would be 3 more 2-selections: one with two apples, one with two oranges, and one with two pears.

    Although the set of three fruits was small enough to write a complete list of combinations, with large sets this becomes impractical. For example, a poker hand can be described as a 5-combination (k = 5) of cards from a 52 card deck (n = 52). The 5 cards of the hand are all distinct, and the order of cards in the hand does not matter. There are 2,598,960 such combinations, and the chance of drawing any one hand at random is 1 / 2,598,960.

2018b

• (Encyclopaedia Britannica Inc., 2018) ⇒ The Editors of Encyclopaedia Britannica (2018). “Permutations and combinations": https://www.britannica.com/science/permutation. Date Published: July 03, 2018. Retrieved: 08-03-018.
  • QUOTE: The concepts of and differences between permutations and combinations can be illustrated by examination of all the different ways in which a pair of objects can be selected from five distinguishable objects — such as the letters A, B, C, D, and E. If both the letters selected and the order of selection are considered, then the following 20 outcomes are possible:
    [math]\displaystyle{ \begin{matrix} AC & BA & AC & CA & AD\\ DA & AE & EA & BC & CB \\ BD & DB & BE & EB & CD \\ DC & CE & BC & DE & ED \end{matrix} }[/math]

    Each of these 20 different possible selections is called a permutation. In particular, they are called the permutations of five objects taken two at a time, and the number of such permutations possible is denoted by the symbol ₅P₂, read “5 permute 2.” In general, if there are n objects available from which to select, and permutations (P) are to be formed using k of the objects at a time, the number of different permutations possible is denoted by the symbol _nP_k.

    [math]\displaystyle{ _nP_k=\frac{n!}{(n-k)!} }[/math]

    The expression n!—read “n factorial” — indicates that all the consecutive positive integers from 1 up to and including n are to be multiplied together, and 0! is defined to equal 1.(...)

    For combinations, k objects are selected from a set of n objects to produce subsets without ordering. Contrasting the previous permutation example with the corresponding combination, the AB and BA subsets are no longer distinct selections; by eliminating such cases there remain only 10 different possible subsets — AB, AC, AD, AE, BC, BD, BE, CD, CE, and DE.

    The number of such subsets is denoted by _nC_k, read “n choose k.” For combinations, since k objects have k! arrangements, there are k! indistinguishable permutations for each choice of k objects; hence dividing the permutation formula by k! yields the following combination formula:

    [math]\displaystyle{ _nC_k=\frac{n!}{k!(n-k)!} }[/math]

    This is the same as the (n, k) binomial coefficient (see binomial theorem).

---