1.2.2 Combinations

Consider the selection of $k$ objects from a set of $n$ objects where order does not matter and repetition is not allowed.
Any such selection is called a $k$ -combination. The total number of $k$ -combinations of a set of $n$ (distinct) objects is denoted by $C (n, k)$ or $(_{k}^{n})$ “ $n$ choose $k$ ”

For integers $k$ and $n$ such that $0 \leq k \leq n$ , the total number of $k$ -combinations of a set of $n$ objects is $C (n, k) = \frac{n!}{k! (n - k)!}$

Proof

Since a set of $k$ elements ( $k$ -permutations) can be arranged into exactly $k!$ sequences,
$P (n, k) = C (n, k) k!$
i.e.
In the $k$ -combinations of $n$ , order doesn’t matter
$∴$ To ‘make order matter’ you can use the Multiplication Principle to order the set of $k$ -combinations into the set of $k$ -permutations

Example

How many subsets of three integers can be chosen from the set ${1, 2, \dots, 10}$ ?

Subsets of 3 integers, $∴ k = 3$
From the set ${1, 2, \dots, 10}$ , $∴ n = 10$
$n - k = 7$
$(\binom{10}{3}) = \frac{10!}{3! (10 - 3)!} = \frac{10!}{3! 7!}$
How many of these subsets contain 3?
Find sets that don’t contain 3
Remove 3 from the set $n$ , $n = 9$
$k = 3$
$n - k = 6$
$(\binom{9}{3}) = \frac{9!}{3! 6!}$
Sets that do contain 3 = All sets - sets that don’t
$: = \frac{10!}{3! 7!} - \frac{9!}{3! 6!}$
…
or just do $(\binom{10}{2})$ lol