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.5The number of ordered subsets of a given size

Now, we move to the world of Formula 1. During Formula 1 racing some cars obtain points (usually the cars finishing the race first), and these points are accumulated during the whole season. This is how the order in the Driver's Championship is based on.

Between 1960 and 2002 only the first six cars (out of 22) finishing the race obtained points. The scoring system had changed a lot during these years, but we concentrate on the fact that some of the drivers obtain points. Moreover, depending on their place they obtain different points. That is, the order of the first six cars matter, but the order of all the other cars do not matter (for the Driver's Championship).

We are interested in how many possible outcomes exist for the Driver's Championship. That is, how many ways can we choose the first 6 cars out of 22 if their order counts? We can try to count the number of possibilities similarly as in Section 2.3, when we counted the number of permutations of some elements. For the first place 22 cars can arrive. No matter which car finishes the race first, there will be 21 possible cars to finish the race second. Then, there will be 20 possible cars to finish the race as the third. Then, there are 19 possibilities for the fourth place, 18 possibilities for the fifth place, and finally, there will remain 17 cars who can finish the race as sixth. Since the order of all the remaining cars does not matter (for the Driver's Championship), the number of possibilities for the first six cars is

\begin{equation*} 22\cdot 21 \cdot 20 \cdot 19 \cdot 18 \cdot 17 = 53~721~360\text{.} \end{equation*}

Which number is bigger?

\begin{align*} \amp 22\cdot 21 \cdot 20 \cdot 19 \cdot 18 \cdot 17 \amp \text{ or } \amp \amp \frac{22!}{16!} \end{align*}

Exercise 2.5.1 can help us to obtain the answer for our question in a different way. Altogether there are \(22!\) possible orders for the 22 cars (this is the number of permutations of 22 cars). But not all of these are considered to be different for the Driver's Championship. In fact, those cases will be considered the same where the first six are the same (and in the same order). Just as we did in Section 2.4 for counting the anagrams, we can group together those permutations of the 22 cars, which are the same for the Driver's Championship, that is, where the order of the first six cars is the same. We can name every group with the order of the first six cars. Thus, we are interested in the number of groups we have. In one group there are those permutations, where the order of the first six cars is the same, thus they only differ in the last \(22-6 = 16\) cars. There are \(16!\) possible permutations of the last 16 cars, therefore every group contains \(16!\) orderings of the 22 cars. Hence, the number of possibilities (for the Driver's Championship) is

\begin{equation*} \frac{22!}{(22-6)!} = \frac{22!}{16!} = 22 \cdot 21 \cdot 20 \cdot 19 \cdot 18 \cdot 17 = 53~721~360\text{.} \end{equation*}

Let us try to generalize the result. We considered a set of 22 cars (the racing cars). We were interested in the first six arriving. That is, we were interested in the number of 6-element sets, but the order of those 6 elements counted, as well. Thus, we may generalize our results in the following way.

For the first element we have \(n\) possibilities to choose from. No matter which element we chose first, there will be \((n-1)\) possibilities to choose a second element. Then, there will be \((n-2)\) possibilities to choose a third element, etc. Finally, there will remain \((n-k+1)\) possibilities to choose the \(k\)th element, as we have already chosen \((k-1)\) elements. Thus the number of the ordered \(k\)-element subsets is

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

  1. Between 2003 and 2009, the first eight cars finishing the race counts for the Driver's Championship. How many possibilities are there for the first eight cars (out of 22)?

  2. Nowadays, the first ten cars finishing the race counts for the Driver's Championship. How many possibilities are there for the first ten cars (out of 22)?

There are \(n\) people at a running competition. In the end, only the first \(k\) arrivals are recorded into a final list. How many possible lists exist if

  1. \(n = 10\) and \(k=3\text{,}\)

  2. \(n = 12\) and \(k=3\text{,}\)

  3. \(n = 10\) and \(k=4\text{,}\)

  4. \(n = 12\) and \(k=4\text{,}\)

  5. \(n = 8\) and \(k=5\text{,}\)

  6. \(n = 10\) and \(k=5\text{?}\)