Mathematics - Combination (Binomial coefficient|n choose k)

A combination is a selection of elements from a set where the order of selection does not matter.

Order doesn't matter means that the selections AB and BA are considered a single combination (a single selection).

• with the set {1,2,3}
• with a selection without repetition (where the elements are deleted from the set when selected)
• the possible selections are:
  • 1 2 3
  • 1 3 2
  • 2 1 3
  • 2 3 1
  • 3 1 2
  • 3 2 1
• and are all equivalent to the single combination 1 2 3 (because the order in the selections does not matter)

The most known example is a lottery - if the number are selected in the bad order, you still win.

When repeat is not valid (ie AA is not a valid pair)

We say that:

• the elements selected are removed from the set.
• no duplicate element can not be found in a selection.

The best known example of a combination without repetition is lottery numbers (2,14,15,27,30,33)

Combination calculation without repetition is also known as:

• n choose k, because there are <math>\displaystyle n\choose k</math> ways to choose k elements from a set of n elements.
• or Binomial coefficient ¹⁾ because it's a coefficient in the binomial theorem

Without repetition, the number of combination possible of length k in a set of possible value of length n is: <MATH> \binom nk = (n \text{ choose } k) = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1} = \frac{n!}{k!(n-k)!} </MATH>

Note:

• k is also known as:
  • the trial number, k = 0, 1, …, n
  • the number of elements in each combination
• n is also known as:
  • the number total of trial
  • the number of element in the whole set

Therefore, when the length of the set is equal to the length of the combinations, the number of combinations is 1.

Combination where repetition is allowed is also known as:

• k-selection,
• k-multiset,
• k-combination with repetition

Example: coins in your pocket (5,5,5,10,10)

There are <math>\tbinom {n+k-1}k</math> ways to choose k elements from a set of n elements if repetitions are allowed.

<MATH> \binom {n+k-1}k = ({n+k-1} \text{ choose } k) = \frac{(k+n-1)!}{k!(n-1)!} </MATH>

• combinations, permutation calculator