Combinations

Suppose that there are $14$ students in a class. $3$ people are to be selected to form a leadership team. How many different $3$-person teams can be formed?

The above question is an example of a general type of problem where the goal is to count the total number of $k$-element subsets of an $n$-element set. To solve such problems, we need to be introduced to the concept of combinations.

Combinations

A combination is a specific subset of a set. The order of selection of the elements does not matter for a combination. For example, combinations $\text{\{1, 2, 3, 4}\}$ and $\text{\{2, 1, 4, 3}\}$ are considered the same.

Let's revisit the problem from the introduction. How many different $3$-person teams can be formed from a class of $14$ students? In other words, we need to find the number of $3$-element subsets of a $14$-element set.
$${14 \choose 3} = {14! \over 3! (14-3)!} = 364$$

Therefore, there are $364$ possible ways to select a team with $3$ members from a class of $14$ students.

Relation between combinations and arrangements without repetition

The formula for $n \choose k$ can be derived using permutations.

Making an ordered selection of size $k$ from a set of $n$ distinct elements can be thought of as selecting the first element, then the second, then the third, and so on until element $k$. The number of ordered selections of $k$ elements from a set of $n$ elements is denoted $P_{n}^k$ and is equal to:$$P_{n}^k = {n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1)} = {n! \over {(n-k)!}}$$For example, suppose we want to choose a President, Vice President, and Secretary from a class of $14$ students. In this case, order matters — we cannot simply choose an arbitrary team of three students. We can select a President first, then Vice President, and finally a Secretary. The number of possible ways to select such a team is:

$$14 \cdot 13 \cdot 12 = {14! \over {(14-3)!}} = 2184$$In the case that order does not matter, we must take into account the $k!$ orderings of the chosen elements. We can calculate the number of unordered selections using the Division rule. This gives the formula for $n \choose k$.

$${n \choose k} = {P_{n}^k \over k!} = {n! \over k! (n-k)!}$$

Properties of combinations

In this section, we'll look at some properties of combinations.

One property is:

$${n \choose n} = {n \choose 0} = 1$$This can be proven using the formula:

$${n \choose n} = {n! \over n! (n-n)!} = {1! \over 1! \cdot 0!} = 1$$$${n \choose 0} = {n! \over 0! (n-0)!} = {n! \over 0! \cdot n!} = 1$$To understand the intuition behind this property, consider the case of choosing a team from $14$ students. If we want to choose a team with $0$ students, there is only one way to do this. If we want to choose a team with all $14$ students, there is also only one way to do this.

Another property is:

$${n \choose n-1} = {n \choose 1} = n$$Again, we can prove this using the formula.

$${n \choose n-1} = {n! \over (n-1)! (n-(n-1))!} = {n! \over (n-1)! \cdot 1!} = n$$$${n \choose 1} = {n! \over 1! (n-1)!} = n$$Let's consider once more the example of forming teams from $14$ students. There are $14$ ways to choose a team with only one person. Likewise, there are $14$ ways to choose a team with $13$ people; in other words, there are $14$ ways where one person is not chosen to be part of the team.

A further property is:

$${n \choose k} = {n \choose n-k}$$This is proven as follows.

$$LHS: {n \choose k} = {n! \over k! (n-k)!}$$$$RHS: {n \choose n-k} = {n! \over (n-k)! (n-(n-k))!} = {n! \over (n-k)!k!}$$LHS equals RHS, so the property is true.

Intuitively, when counting the number of possible $k$-member teams from a set of $n$ people, we can either count the number of ways to form a team of $k$ students or we can count the number of ways $n-k$ students will be left out. These will both result in the same number.

Conclusion

A combination is a selection of elements from a set disregarding the order of the selection. The total number of $k$-element subsets from a set with $n$ elements is calculated as:

$$C_{n}^k = {n \choose k} = {n! \over k! (n-k)!} = {P_{n}^k \over k!}$$Some properties of combinations are the following

$$C_{n}^n = C_{n}^0 = 1$$$$C_{n}^1 = C_{n}^{n-1} = n$$$$C_{n}^k = C_{n}^{n-k}$$