# 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).

If the order does matter such as in a digital lock (pin) or the arrival order of a race, the term used is permutation

## Example

• 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.

## Formula

### Without repetition

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 $\displaystyle n\choose k$ ways to choose k elements from a set of n elements.
• or Binomial coefficient 1) 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: $$\binom nk = (n \text{ choose } k) = \frac{n(n-1)\dotsb(n-k+1)}{k(k-1)\dotsb1} = \frac{n!}{k!(n-k)!}$$

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

n! is factorial n

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

### With repetition

Combination where repetition is allowed is also known as:

• k-selection,
• k-combination with repetition

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

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

$$\binom {n+k-1}k = ({n+k-1} \text{ choose } k) = \frac{(k+n-1)!}{k!(n-1)!}$$