Combinations

A combination is a subset of k elements selected from a set of n elements. $$ \begin{pmatrix} n \\ k \end{pmatrix} $$

When a combination contains k elements, it is called a combination of class k.

Because a combination is defined as a set, the order of the elements has no effect.

There are two types of combinations: simple combinations and combinations with repetition.

Simple combinations (without repetition)
Combinations with Replacement
Properties of Combinations
Binomial Coefficients

Simple combinations (without repetition)

The simple combinations of $ n $ distinct elements taken $ k $ at a time are the $ k $-element subsets that can be formed from the $ n $ elements, with no repetition and no regard for order. Their total number is $$ C_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} = \frac{D_{n,k}}{P_k} $$ where $ k $ is a positive integer such that $ 0 < k < n $.

In other words, a simple combination includes no repeated elements. Each element can appear only once within the subset.

From a set of $ n $ elements, we can form exactly $ C_{n,k} $ simple combinations of class $ k $.

This count is the familiar binomial coefficient.

$$ C_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} = \frac{D_{n,k}}{P_k} = \frac{n \cdot (n-1) \cdot ... \cdot (n-k+1)}{k!} $$

To compute the binomial coefficient, we divide the number of simple arrangements $ D_{n,k} $ by the number of permutations of the $ k $ elements involved, namely $ P(k)=k! $.

This process removes all ordered arrangements that contain the same elements in different orders, leaving only the distinct $ k $-element subsets.

Note. The binomial coefficient is often expressed using the classic factorial identity known as the three factorial rule: $$ C_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{k!(n-k)!} $$ This follows from the compact expression for simple arrangements, $ D_{n,k} = \frac{n!}{(n-k)!} $. Substituting this into the general formula for simple combinations gives: $$ C_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} = \frac{D(n,k)}{P_k} = \frac{ \frac{n!}{(n-k)!} }{k!} = \frac{n!}{k!(n-k)!}. $$

An example

Consider the set consisting of the first three letters of the alphabet:

$$ I = \{ A,B,C \} $$

We want to list all simple combinations of class 2, that is all 2-element subsets of this set.

$$ n=3 \\ k=2 $$

We begin by computing the number of such subsets:

$$ C_{3,2} = \binom{3}{2} = \frac{D_{3,2}}{P_2} $$

The simple arrangements are $ D_{3,2} = 3 \cdot 2 = 6 $, and the permutations of two elements are $ P_2 = 2! = 2 $.

$$ C_{3,2} = \binom{3}{2} = \frac{6}{2} = 3 $$

So there are exactly three 2-element subsets:

(A,B)
(A,C)
(B,C)

Each subset contains two distinct elements, and their order is irrelevant.

For this reason, (A,B) and (B,A) represent the same combination.

Note. Using the alternative factorial formula with $ n=3 $ and $ k=2 $ leads to the same value: $$ C_{3,2} = \frac{ \frac{n!}{(n-k)!} }{k!} = \frac{3!}{2!(3-2)!} = \frac{6}{2} = 3 $$ as expected.

Example 2

Now take a set of $ n = 5 $ elements, the first five letters of the alphabet:

$$ I = \{ A,B,C,D,E \} $$

We want to find all simple combinations of class $ k = 3 $, meaning all 3-element subsets of this set.

Compute the corresponding binomial coefficient:

$$ C_{5,3} = \binom{5}{3} = \frac{D_{5,3}}{P_3} $$

The simple arrangements are $ D_{5,3} = 5 \cdot 4 \cdot 3 = 60 $, and the permutations of three elements are $ P_3 = 3 \cdot 2 \cdot 1 = 6 $.

$$ C_{5,3} = \binom{5}{3} = \frac{60}{6} = 10 $$

Therefore, there are 10 simple combinations of three elements. They are:

(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)

These are all the 3-element subsets drawn from the original set of five elements.

Each subset contains distinct elements, and the order of selection does not matter.

Combinations with Replacement

Combinations with replacement of $ n $ distinct elements, taken in groups of size $ k $, include every selection of $ k $ elements from a set of $ n $ items where order is irrelevant and elements may appear multiple times. The total number of such combinations is given by $$ C'_{n,k} = \begin{pmatrix} n+k-1 \\ k \end{pmatrix} = \frac{(n+k-1)!}{k!(n-1)!} $$ The parameter $ k $ may be any non negative integer, that is $ k \ge 0 $.

Unlike combinations without replacement, we do not require $ k \le n $ here, because elements may be used repeatedly within the same group.

The quantity C' coincides with the binomial coefficient $ C(n+k-1, k) $.

An example

Consider the set of three letters

$$ I = \{ A,B,C \} $$

We want to find all combinations of size 2 with replacement

$$ n=3 \\ k=2 $$

In other words, we are forming every possible pair of letters.

A letter may appear twice in the same pair.

$$ C'_{3,2} = \frac{(n+k-1)!}{k!(n-1)!} = \frac{(3+2-1)!}{2!(3-1)!} = \frac{4!}{2!2!} = \frac{24}{4} = 6 $$

There are six distinct combinations.

(A,A)
(A,B)
(A,C)
(B,B)
(B,C)
(C,C)

Each group contains two elements taken from {A, B, C}. Order does not matter, and repetition is allowed. For instance, (A,A) consists of the same letter chosen twice.

Example 2

We again use the same set of three letters.

$$ I = \{ A,B,C \} $$

This time we want to determine the combinations of size 4 with replacement

$$ n=3 \\ k=4 $$

In other words, we are forming all possible four letter groups from these three elements, allowing repetitions.

$$ C'_{3,4} = \frac{(n+k-1)!}{k!(n-1)!} = \frac{(3+4-1)!}{4!(3-1)!} = \frac{6!}{4!2!} $$

$$ C'_{3,4} = \frac{6 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(4 \cdot 3 \cdot 2 \cdot 1) \cdot (2 \cdot 1)} = \frac{720}{48} = 15 $$

There are fifteen distinct combinations.

(A,A,A,A)
(A,A,A,B)
(A,A,A,C)
(A,A,B,B)
(A,A,B,C)
(A,A,C,C)
(A,B,B,B)
(A,B,B,C)
(A,B,C,C)
(A,C,C,C)
(B,B,B,B)
(B,B,B,C)
(B,B,C,C)
(B,C,C,C)
(C,C,C,C)

Each group contains four elements selected from {A, B, C}, with order ignored and replacement permitted. For example, in (A,A,A,B), the letter A appears three times.

What is the difference between combinations with replacement and arrangements with replacement? In arrangements with replacement, order matters, which means sequences such as (A, B, A) and (A, A, B) are treated as different outcomes. In combinations with replacement, order does not matter, so any groups that differ only by permutation represent the same combination. Thus (A, B, A) and (A, A, B) correspond to the same combination.

Properties of Combinations

Several key properties of combinations are worth remembering.

Empty choice
There is exactly one way to choose zero elements from a set of $ n $ objects, namely selecting nothing. $$ \begin{pmatrix} n \\ 0 \end{pmatrix} = 1 $$
Single choice
Choosing exactly one element from $ n $ possibilities yields $ n $ distinct choices. $$ \begin{pmatrix} n \\ 1 \end{pmatrix} = n $$
Complete choice
There is only one way to choose all $ n $ elements, that is selecting the entire set. $$ \begin{pmatrix} n \\ n \end{pmatrix} = 1 $$
Pascal's Identity
The number of ways to choose $ k $ elements from $ n+1 $ objects can be found by summing the choices that exclude the last object $ \binom{n}{k} $ and those that include it $ \binom{n}{k-1} $. These two sets are disjoint and together account for all possibilities, so their sum gives $ \binom{n+1}{k} $. $$ \begin{pmatrix} n+1 \\ k \end{pmatrix} = \begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k-1 \end{pmatrix} $$
Example. Apply Pascal's identity to the case $ n=5 $ and $ k=2 $ $$ \begin{pmatrix} 5+1 \\ 2 \end{pmatrix} = \begin{pmatrix} 5 \\ 2 \end{pmatrix} + \begin{pmatrix} 5 \\ 1 \end{pmatrix} $$ Substituting and calculating gives $$ \begin{pmatrix} 6 \\ 2 \end{pmatrix} = 10 + 5 = 15 $$
Complementary classes
Choosing $ k $ elements from $ n $ is equivalent to choosing which $ n-k $ elements to leave out, and the corresponding binomial coefficients are equal. $$ C_{n,k} = C_{n,n-k} = \binom{n}{k} = \binom{n}{n-k} $$ This symmetry is extremely useful, especially when $ k \gt \frac{n}{2} $, since it often simplifies the computation.

Example. For $ C_{5,3} $, the rule of complementary classes tells us that choosing 3 out of 5 elements is the same as choosing the remaining 2 to omit, so $$ C_{5,3} = C_{5,2} $$ Both values equal 10. $$ C_{5,3} = \binom{5}{3} = \frac{5 \cdot 4 \cdot 3}{3!} = \frac{60}{6} = 10 $$ $$ C_{5,2} = \binom{5}{2} = \frac{5 \cdot 4}{2!} = \frac{20}{2} = 10 $$ Example 2. Consider $ C_{10,8} $. We want to select $ k=8 $ elements out of $ n=10 $. A direct computation gives $$ C_{10,8} = \binom{10}{8} = \frac{10 \cdot 9}{2 \cdot 1} = 45 $$ Since $ k \gt \frac{n}{2} $, it is easier to use the complementary class $$ C_{10,8} = C_{10,2} = \binom{10}{2} = \frac{10 \cdot 9}{2 \cdot 1} = 45 $$ The result is, of course, identical.

Binomial Coefficients

The parameters $ n $ and $ k $ in a combination are called binomial coefficients because the quantity $ C(n,k) $ appears as the coefficient of the terms in the expansion of a binomial raised to the n-th power.

$$ (a+b)^n = \sum_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} a^{\,n-k} b^{\,k} $$

Example. Consider the expansion of the binomial square $ (a+b)^2 $. Starting from the general form of the binomial expansion, $$ (a+b)^2 = \begin{pmatrix} 2 \\ 0 \end{pmatrix} a^{\,2-0} b^{\,0} + \begin{pmatrix} 2 \\ 1 \end{pmatrix} a^{\,2-1} b^{\,1} + \begin{pmatrix} 2 \\ 2 \end{pmatrix} a^{\,2-2} b^{\,2}. $$ Simplifying the exponents, $$ (a+b)^2 = \begin{pmatrix} 2 \\ 0 \end{pmatrix} a^{2} + \begin{pmatrix} 2 \\ 1 \end{pmatrix} ab + \begin{pmatrix} 2 \\ 2 \end{pmatrix} b^{2}. $$ Now evaluate the binomial coefficients using their factorial definition: $$ (a+b)^2 = \frac{2!}{0!(2-0)!}\, a^{2} + \frac{2!}{1!(2-1)!}\, ab + \frac{2!}{2!(2-2)!}\, b^{2}. $$ Substituting the factorials explicitly, $$ (a+b)^2 = \frac{2!}{0! \cdot 2!}\, a^{2} + \frac{2!}{1! \cdot 1!}\, ab + \frac{2!}{2! \cdot 0!}\, b^{2}. $$ Using the standard values $0! = 1$, $1! = 1$, and $2! = 2$, $$ (a+b)^2 = \frac{2}{1 \cdot 2}\, a^{2} + \frac{2}{1 \cdot 1}\, ab + \frac{2}{2 \cdot 1}\, b^{2}. $$ Which simplifies to $$ (a+b)^2 = 1 \cdot a^{2} + 2 \cdot ab + 1 \cdot b^{2}. $$ Therefore, the expansion is $$ (a+b)^2 = a^{2} + 2ab + b^{2}. $$ This is the familiar binomial square identity, and the same method extends directly to higher powers $ (a+b)^n $ through the binomial theorem.

And so on.