# Combination

## What is a Combination ?

A combination of p elements from n is an unordered selection of p elements from n elements.

Examples:

- {2,3,1 is a combination of three elements out of {1,2,3,4} but {2,1,3} represents the same combination because the order does not matter.

- {c, a} is a combination of two elements from {a, b, c}. Similarly, {a, c} represents the same combination.

## Combination calculation formula

Given a set of n different objects then, the number of combinations of p objects from n is equal to,

`([n], [p]) = frac {n!}{p! * (n-p)!}`

Example: E is a set of three elements 1, 2, 3.
The number of combinations of two elements from E is equal to 3! / (2! . (3-2)!) = 3.
These combinations are :

1, 2,

1, 3,

2, 3

## How to identify a combination ?

There are 2 criteria in recognizing a combination :

- Order does not matters

- Only a subset of the whole set is concerned

Example: How many possible draws are there in a 5/49 lottery ?

We need to calculate a combination because the draw order is not important and only a subset of numbers is concerned (5 of 49).

The number of possible draws is 49! / (5! (49-5)!) = 1 906 884.

## Comparison of enumeration methods

Method | Elements concerned | Order matters ? | Formula |
---|---|---|---|

Permutation | All elements (n) | Yes | `n!` |

Arrangement | Subset of p elements among n | Yes | `frac {n!}{(n-p)!}` |

Combination | Subset of p elements among n | No | `frac {n!}{p!* (n-p)!}` |

## See also

Permutation

Arrangement

Binomial coefficient