Combinations

Consider two problems. In a class of 30 students, in how many ways can a class president and a vice president be chosen? In how many ways can two students on duty be selected from the same class?

The answer to the first problem is known: it is the number of 2-element ordered subsets of a 30-element set, i.e., $A_{30}^2$ . To solve the second problem, we need to find the number of 2-element subsets (not ordered subsets) of a 30-element set. Each such subset is called a combination of 30 elements taken 2 at a time.

Definition

📐Definition — Combination

Any $k$ -element subset of a given $n$ -element set is called a combination of $n$ elements taken $k$ at a time.

The number of all possible combinations of $n$ elements taken $k$ at a time is denoted by $C_n^k$ , using the first letter of the French word combinaison.

Formula

Consider an $n$ -element set. The number of its $k$ -element subsets is $C_n^k$ . From each such subset, $k!$ ordered $k$ -element subsets can be formed. Therefore, $A_n^k = C_n^k \cdot P_k$ , which gives:

C_n^k = \frac{A_n^k}{P_k}.

⚡Theorem — Formula for the Number of Combinations

For any natural numbers $n$ and $k$ such that $k \leqslant n$ :

C_n^k = \binom{n}{k} = \frac{n!}{(n-k)!\, k!}

This formula remains valid for $k = 0$ and $n = 0$ :

C_n^0 = \frac{n!}{n! \cdot 0!} = 1, \qquad C_0^0 = \frac{0!}{0! \cdot 0!} = 1.

Properties of Combinations

⚡Theorem — Symmetry Property

C_n^k = C_n^{n-k}

By choosing a $k$ -element subset $A$ from an $n$ -element set $M$ , we simultaneously define the complementary $(n-k)$ -element subset $M \setminus A$ . Therefore, the number of ways to choose a $k$ -element subset equals the number of ways to choose an $(n-k)$ -element subset.

✎Example 1 — Sum of All Combinations

Statement. Prove that $C_n^0 + C_n^1 + C_n^2 + \ldots + C_n^n = 2^n$ .

Solution. The left side of this equality is the total number of subsets of an $n$ -element set. As shown earlier, this number equals $2^n$ .

Pascal’s Identity

⚡Theorem — Pascal's Identity

C_{n+1}^k = C_n^{k-1} + C_n^k

Proof. Consider an $(n+1)$ -element set. Fix a particular element $a$ in it. All $k$ -element subsets can be divided into two types: those containing element $a$ and those not containing it.

Subsets of the first type are formed by choosing $k - 1$ elements from the remaining $n$ elements (since element $a$ is already included). The number of such subsets is $C_n^{k-1}$ .

Subsets of the second type are formed by choosing $k$ elements from $n$ elements (excluding $a$ ). Their number is $C_n^k$ .

Therefore, $C_{n+1}^k = C_n^{k-1} + C_n^k$ .

This identity can also be proved using a geometric interpretation with shortest paths on a grid, where vertical and horizontal segments correspond to choosing $k$ vertical segments from $m + k$ total segments.

✏Exercise — Combination Problems

A class has 29 students. In how many ways can a team of 5 be formed for a math olympiad?
Ten points are marked on a plane such that no three are collinear. How many triangles can be formed with vertices at these points?
A chess club has 5 girls and 12 boys. In how many ways can a team of 2 girls and 5 boys be formed for a competition?