Combination

From GM-RKB
(Redirected from k-combination)
Jump to navigation Jump to search

A Combination a set that is the result of drawing a subset from some other set.



References

2018

  • (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 5P2, 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 nPk.

      [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 nCk, 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).

2015

  • (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/combination Retrieved:2015-2-9.
    • In mathematics, a combination is a way of selecting members from a grouping, such that (unlike permutations) the order of selection does not matter. In smaller cases it is possible to count the number of combinations. 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)\ldots(n-k+1)}{k(k-1)\dots1}, }[/math]

      which can be written using factorials as [math]\displaystyle{ \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 sometimes denoted by [math]\displaystyle{ \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, [1] k-multiset, or k-combination with repetition are often used. [2] If, in the above example, it was 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.

  1. also referred to as an unordered selection.
  2. When the term combination is used to refer to either situation (as in ) care must be taken to clarify whether sets or multisets are being discussed.