Combination

We use combinations when we select a certain number of objects from a set of objects, and the order in which we select these objects does not matter. A typical problem is a Sportka - we have 49 numbers in a pool and we draw 6 of them, no matter in which order we draw them.

Deriving the formula

Consider some set M, for example M = {a, b, c, d, e}. Then the k-member combination is a subset of K ⊆ M, which contains just k elements. Of course, since K is a set, the order doesn't matter. So a three-member combination from the set M could be {a, b, d} or {b, c, d}.

The difference with variations is that for variations the order matters, so [a, b, e] and [e, b, a] are different variations, but they are the same combination because [a, b, e] and [e, b, a] contain the same elements; that they are in a different order is of no interest to us for combinations.

But we can use the variations to get a formula for the number of all the different combinations. We know that the k-element variations of the set with n elements are just

$$ V(k, n) = \frac{n!}{(n-k)!}. $$

Thus, if we counted the number of all three-membered variations from the previous set M = {a, b, c, d, e}, we would get V(3, 5) = 60 different variations. However, for each triple, we would also have all its permutations there. That is, we would have the triplet abc, but also the triplets acb, bac, bca, cab and cba. This is six different variations, but it is one combination because they all have the same elements.

So if we have a triple, how many different permutations of that triple are there? Just 3!. In other words, there are just 3! more variations of three than there are combinations of three. Instead of counting on one combination, we count on 3! more variations, with each permutation of a given triple. So if we divide the number of permutations by 3!, we get the number of combinations.

We can generalize the previous procedure and say that if we are looking for the number of all different k-ary combinations from a set of size n, then this number, denoted C(k, n), is equal,

$$ C(k, n) = \frac{V(k, n)}{k!}, $$

i.e., the number of variations divided by k!, which is the number of permutations of each k-tice. We can modify the formula by breaking down the formula for calculating the variations:

$$ C(k, n) = \frac{V(k, n)}{k!} = \frac{n!}{(n-k)!}\cdot\frac{1}{k!} = \frac{n!}{(n-k)!\cdot k!}. $$

Example: the number of binomial combinations from the set {a, b, c} is

$$ C(2, 3) = \frac{3!}{1!\cdot2!} = 3 $$

and these combinations are: {a, b}, {a, c} and {b, c}. For the three-membered combinations from the original set M = {a, b, c, d, e}, we would get the number of

$$ C(3, 5) = \frac{5!}{(5-3)!\cdot3!}=10 $$

and they are the following combinations: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

The combination number

The previous notation of the formula using C(k, n) is not used much and instead the so-called combinational number is used. The combinational number has the following form

$$ {n \choose k} $$

it is a kind of fraction without the fraction line (which you will write there anyway out of habit), but with parentheses (these are not optional, they must be there). We read the combination number as "en over ka". The value of the combination number is then the same as C(k, n).

$$ {n \choose k} = \frac{n!}{(n-k)!\cdot k!} $$

So, if we have a set of 5 elements and we select quads from it, the total number of elements will be

$$ {5 \choose 4} = \frac{5!}{1! \cdot 4!} = 5. $$

Basic relationships

For the combinational number and n ∈ ℕ, the following holds:

$$\begin{eqnarray} {n \choose 0} = {n \choose n} = {0 \choose 0} &=& 1\\ {n \choose 1} &=& n \end{eqnarray}$$

Further, for n, k ∈ ℕ₀ and k ≤ n, the following holds

$$\begin{eqnarray} {n \choose n - k} &=& {n \choose k}. \end{eqnarray}$$

And for n, k ∈ ℕ₀ and k < n, the following holds

$$\begin{eqnarray} {n \choose k} + {n \choose k+1} &=& {n+1 \choose k+1}. \end{eqnarray}$$

The computer

The following calculator will calculate the combinational number of n over k, including the procedure.

Examples solved

1. Let's start with the aforementioned Sport. In it, 6 balls are drawn from a pool containing 49 balls. How many different possibilities can we draw?

   First of all - does the order of drawing the numbers matter? It doesn't matter, we're only guessing the numbers, not their order. We'll use combinations. We have a total of 49 balls, we draw 6 balls, we get a combination number

   $$ {49 \choose 6} = \frac{49!}{(49-6)!\cdot6!}=\frac{49!}{43!\cdot6!} = 13{,}983,816 $$

   There are a total of 13,983,816 possibilities that can be drawn. Which, by the way, gives us the probability of winning on one bet 1/13 983 816, which is 0,00000715112 %.

2. Sagvan, a well-known packer of girls, is currently at a village dance where there are a total of 13 beautiful girls he would be interested in. Sagvan knows that he is able to make 4 different girls happy in an evening. How many different foursomes can Sagvan choose from?

   This is again a simple example of combinations, the order doesn't matter, Sagvan will be just as good with the first girl as with the last. So we get a set of 13 girls, from which we always choose 4 girls. This leads to a combination number

   $$ {13 \choose 4} = 715. $$

3. You have a group of 50 people - half male and half female. How many different triplets of people are there if they must not be composed of only one gender (i.e. there must not be three men or three women in a triplet).

   That's a slightly more complicated combination. If we exclude single-sex triads of people, we are left with only two ways in which a triad can be composed - two men and one woman or one man and two women, with the number of combinations of the first group (two men and one woman) being the same as the number of combinations of the second group. So we just need to calculate the number of combinations of the first group and then multiply it by two. Now it's easy again. We determine the number of combinations of different pairs of men, which is twenty-five over two, and multiply that by the number of combinations of one woman (that makes twenty-five, see the previous list of combination numbers, specifically the very first one). We just multiply this result by two and we have the final result.

   $$ 2 \cdot {25 \choose 2} \cdot {25 \choose 1} = 15000. $$

4. There are 15 products in the box, 4 of which are defective. In how many ways can 6 products be selected so,

   • so that none of them are defective? At the moment we are selecting 6 products from 15 − 4 = 11 products that are not defective. This gives us a combination number

     $$ {11 \choose 6} = 462. $$

   • so that only one product is defective? So we select a set that contains 5 functional products and 1 defective product. We have 11 functional products and 4 defective products. We use the combinatorial product rule to get the result:

     $$ {11 \choose 5} \cdot {4 \choose 1} = 1848 $$

   • so that at most one is defective? We use the previous results to solve. We know that we have a total of 462 possibilities to select just 6 functional products and we have 1848 possibilities to select 5 functional and 1 defective product. So we use the combinatorial sum rule, add these results together and have the result we want, i.e. at most one defective product (= either no defective product or just one). The result is: 462 + 1848 = 2310.

Sources and further reading

• Combinatorics at cuni.cz
• Bělohlávek, Vychodil: Discrete Mathematics [PDF]