Skip to main content
\(\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{ #1}}{\thechapter~ #1}} \renewcommand{\sectionmark}[1]{} \newcommand{\abs}[1]{\left|#1\right|} \renewcommand{\theenumi}{5.\arabic{enumi}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\norma}[1]{\left\|#1\right\|} \newcommand{\BM}[1]{\text{\boldmath$#1$}} \newcommand{\halmaz}[1]{\left\{\,#1\,\right\}} \newcommand{\halmazvonal}[2]{\left\{\,#1\mid #2\,\right\}} \newcommand{\halmazpont}[2]{\left\{\,#1:#2\,\right\}} \newcommand{\N}{\mathbb{N}} \newcommand{\len}{\norm} \newcommand{\var}[2][]{v_{#1}\left(#2\right)} \newcommand{\vari}[2]{v_{#1}\left(#2\right)} \newcommand{\size}[2][]{s_{#1}\left(#2\right)} \newcommand{\dep}[2][]{d_{#1}\left(#2\right)} \newcommand{\sizestar}[2][]{s_{#1}^*\left(#2\right)} \newcommand{\depstar}[2][]{d_{#1}^*\left(#2\right)} \renewcommand{\headrulewidth}{0pt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section2.6The number of subsets of a given size

In the Hungarian lottery there are 90 balls in a urn (numbered from 1 to 90). Five numbers of them are chosen in an arbitrary way (usually a celebrity blindly pulls out five balls without putting them back). The order in which the numbers are chosen does not matter, only the chosen numbers themselves (in fact, at the end of the show, the numbers are repeated in their increasing order). People can guess in advance what the five chosen numbers will be, and they can win money depending on how many numbers they managed to guess correctly. The jackpot goes to those, who manage to guess all five numbers properly.

Let us imagine the situation that we want to win the jackpot. How many lottery tickets should we buy for that? Or, in other words, how many ways can the celebrity choose five numbers out of 90? Let us consider first the case, if the order of the five chosen numbers mattered. We have already solved this problem in Theorem 2.5.2 of Section 2.5. There are 90 possibilities to choose the first number, then there are 89 possibilities to choose the second number, 88 possibilities to choose the third number, 87 possibilities to choose the fourth number, and finally, there are 86 possibilities to choose the fifth number. Thus the number of possibilities to choose five numbers such that their order counts is

\begin{equation*} 90 \cdot 89 \cdot 88 \cdot 87 \cdot 86 = 5~273~912~160\text{.} \end{equation*}

Now, to count the number of unordered possibilities we can try the same trick we successfully implemented in Section 2.4 and Section 2.5. That is, let us group together those chosen five numbers, where the five numbers are the same, they only differ in the order they were chosen. Let us name these groups with the chosen five numbers. For example, there will be a group called ‘1, 2, 3, 4, 5’, which contains all possible choosing of 1, 2, 3, 4, 5, in any order. Similarly, there will be a group called ‘13, 42, 51, 66, 90’ containing all possible choosing of these five numbers. For example, if the numbers chosen were (in order) ‘42, 13, 90, 66, 51’, then they are put into the group ‘13, 42, 51, 66, 90’. Similarly, the numbers ‘51, 66, 90, 13, 42’ are put into the group ‘13, 42, 51, 66, 90’, as well. We are interested in the number of groups. To count the number of groups, we first count the number of ordered five numbers in one group. How many elements does the group ‘13, 42, 51, 66, 90’ have? This group contains all possible orders in which one can choose these five numbers. This is the number of permutations of these five numbers. That is, there are \(5! = 120\)-many orders in the group ‘13, 42, 51, 66, 90’. Similarly, there are \(5! = 120\)-many orders in every other group. Therefore the number of groups (and the number of possible ways to choose five numbers out of 90) is

\begin{equation*} \frac{90 \cdot 89 \cdot 88 \cdot 87 \cdot 86}{5!} = \frac{5~273~912~160}{120} = 43~949~268\text{.} \end{equation*}

Which number is bigger?

\begin{align*} \amp \frac{90 \cdot 89 \cdot 88 \cdot 87 \cdot 86}{5!} \amp \text{ or } \amp \amp \frac{90!}{5! \cdot 85!} \end{align*}

The number occurring in Exercise 2.6.1 is so important, that it has its own name. We denote it by \(\binom{90}{5}\) (read as ‘90 choose 5’), and it equals

\begin{equation*} \binom{90}{5} = \frac{90!}{5! \cdot 85!}\text{.} \end{equation*}

In general, we can define \(\binom{n}{k}\) similarly.

Definition2.6.2

Let \(\binom{n}{k}\) (read ‘\(n\) choose \(k\)’) be

\begin{equation*} \binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}\text{.} \end{equation*}

These numbers are called binomial coefficients.

Calculate the numbers \(\binom{n}{k}\) for \(n = 0, 1, 2, 3, 4, 5, 6\) and \(k = 0, 1, \dots, n\text{.}\)

Usually, it is easier to calculate \(\binom{n}{k}\) as in the left hand side of Exercise 2.6.1.

The following calculation shows that the two sides are equal:

\begin{align*} \binom{n}{k} \amp = \frac{n!}{k! \cdot (n-k)!} = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+1) \cdot (n-k)!}{k! \cdot (n-k)!}\\ \amp = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+1)}{k!}\text{.} \end{align*}

Now, we are ready to generalize our results on the lottery. With that argument we proved that the number of possibilities to choose 5 numbers out of 90 is \(\binom{90}{5}\text{.}\) This is the same as to say that the number of 5-element subsets of a 90-element set is \(\binom{90}{5}\text{.}\)

The number of \(k\)-element ordered subsets is \(\frac{n!}{(n-k)!}\) by Theorem 2.5.2. To count the number of unordered \(k\)-element subsets we group together those \(k\)-element subsets, which differ only in their order. That is, every group contains different orderings of the same \(k\) elements. Every group contains \(k!\)-many orderings, since \(k!\) is the number of possible permutations of those \(k\) elements. Therefore the number of groups (and the number of \(k\)-element subsets) is

\begin{equation*} \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{k! \cdot (n-k)!} = \binom{n}{k}\text{.} \end{equation*}

By Proposition 2.6.4 this is the same number as

\begin{equation*} \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+1)}{k!}\text{.} \end{equation*}

In light of Theorem 2.6.5, the binomial coefficients are important numbers. Therefore, we spend some time to know them a little bit better. It is easy to calculate (and remember) some particular binomial coefficients.

What is \(\binom{n}{0}\text{,}\) \(\binom{n}{1}\text{,}\) \(\binom{n}{2}\text{,}\) \(\binom{n}{n-2}\text{,}\) \(\binom{n}{n-1}\) and \(\binom{n}{n}\) in general?

Moreover, it is pretty straightforward from formula (2.6.1) that

Rather than simply substituting into (2.6.1), we give a combinatorial argument. That is, we give a combinatorial meaning to both sides of the equation, that is, they both will count the same thing. Naturally, if they count the same thing, they must be equal.

The left hand side counts the number of \(k\)-element subsets of an \(n\)-element set. The right hand side counts the number of \((n-k)\)-element subsets of an \(n\)-element set. We prove that there are the same number of \(k\)-element subsets as \((n-k)\)-element subsets. Let \(S\) be an \(n\)-element set, and let us map every \(k\)-element subset into its complementer. This way, we map every \(k\)-element subset to an \((n-k)\)-element subset. Moreover, different \(k\)-element subsets are mapped to different \((n-k)\)-element subsets. Finally, every \((n-k)\)-element subsets is mapped from a \(k\)-element subset (in fact, it is mapped from its complementer). Therefore this map is a one-to-one correspondence between the \(k\)-element subsets and the \((n-k)\)-element subsets.

We can think about this proof in the following way. Choosing \(k\) elements out of \(n\) elements is the same as not choosing \((n-k)\)-elements. That is, deciding which \((n-k)\) elements will not be chosen is the same as deciding which \(k\) elements will be chosen. We can ‘not choose’ \((n-k)\) elements in \(\binom{n}{n-k}\)-many ways, which therefore must be the same as the number of choices to choose \(k\) elements, which is \(\binom{n}{k}\text{.}\)

Finally, let us conclude this Section by calculating the sum of the binomial coefficients.

Calculate the sum

\begin{equation*} \sum_{k=0}^n \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n-1} + \binom{n}{n} \end{equation*}

for \(n=0, 1, 2, 3, 4, 5, 6\text{.}\)

After solving Exercise 2.6.8, one can conjecture on the general case:

Again, we give a combinatorial argument. The right hand side counts the number of subsets of an \(n\)-element set. We prove that the left hand side counts the same, only in a different manner. It counts the number of subsets in a way that first we choose how many elements the subset will have, and then we count the number of subsets with that many elements.

That is, a subset of an \(n\)-element set can have \(0\text{,}\) \(1\text{,}\) \(2\text{,}\) \(\dots\text{,}\) \((n-1)\) or \(n\) elements. An \(n\)-element set has \(\binom{n}{0}\)-many \(0\)-element subsets, \(\binom{n}{1}\)-many \(1\)-element subsets, \(\binom{n}{2}\)-many \(2\)-element subsets, etc., \(\binom{n}{n-1}\)-many \((n-1)\)-element subsets, and \(\binom{n}{n}\)-many \(n\)-element subsets. That is, the number of subsets the \(n\)-element set has is

\begin{equation*} \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n-1} + \binom{n}{n}\text{.} \end{equation*}

Alternatively, we can say that an \(n\)-element set can have \(k\)-element subsets for \(0 \leq k\leq n\text{.}\) An \(n\)-element set has exactly \(\binom{n}{k}\)-many \(k\)-element subsets, hence it has \(\sum_{k=0}^n \binom{n}{k}\)-many subsets altogether.

As the left hand side and the right hand side count the same thing (the number of subsets of an \(n\)-element set), they must be equal.

For what \(n\) does \(n\) divide \(\binom{n}{2}\text{?}\)

Prove that \(n^2 = \binom{n+1}{2} + \binom{n}{2}\) for \(n\geq 2\text{.}\)