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