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.8Balls from urns

In this Section we apply our knowledge on counting to solve the problem of pulling balls out of a urn. In the usual Hungarian lottery, 5 numbers are chosen randomly from 90. That is, there are 90 balls numbered from 1 to 90, and 5 balls are chosen such that none of them will be put back after pulling them out, and in the end the order they have been chosen is not interesting, only what the five numbers are. This problem can have four different versions, depending on whether or not the order of the chosen balls counts, and whether or not we put back a ball into the urn after pulling it out.

Let us see the four different cases. If the order counts and we allow repetition, then the answer is clearly \(90^5\text{:}\) for each of the five choices we have 90 balls to choose from. (This is the same problem as with the sequences in Section 2.1.) If we do not allow repetition (but the order counts), then this is the same problem as with the Formula 1 competition (Section 2.5): for first choice we have 90 balls to choose from, for second choice we have 89 balls to choose from (because we cannot choose what we chose first), for third choice we have 88 balls to choose from (because we cannot choose what we chose first or second), for fourth choice we have 87 balls to choose from (because we cannot choose what we chose first, second or third), finally, for fifth choice we have 86 balls to choose from (because we cannot choose what we chose before). That is, the number of choices we have is

\begin{equation*} 90 \cdot 89 \cdot 88 \cdot 87 \cdot 86 = \frac{90!}{85!} = \frac{90!}{(90-5)!}\text{.} \end{equation*}

Now, consider the case where the order does not count and we do not allow repetition. Then, each of those cases are considered to be the same, where we chose exactly the same 5 balls, only in different orders. Five balls have \(5!\)-many orders, thus the number of choices for choosing 5 balls out of 90 without any repetition such that the order does not count is

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

This is the same problem we discussed in Section 2.6. Finally, consider the last case: choose 5 balls out of 90 such that repetition is allowed, and the order does not count. We claim that this is the same problem as 90 pirates distributing 5 gold pieces among themselves (Section 2.7). Indeed, for every gold distribution we can consider to choose those balls which have the same number as the pirates who received gold pieces, exactly as many times as the number of gold pieces they received. For example, if the first pirate received 3 gold pieces and the tenth pirate received two, this corresponds to choosing the numbers \(1, 1, 1, 10, 10\text{.}\) Similarly, for every choice of numbers we have a distribution: a pirate gets as many gold pieces as the number of times its corresponding ball has been chosen. Thus, by Theorem 2.7.10 the number of possibilities to choose 5 numbers out of 90 if repetition is allowed and the order does not count is

\begin{equation*} \binom{90+5-1}{90-1} = \binom{90+5-1}{5}\text{.} \end{equation*}

Table 2.8.1 collects these results.

order counts order does not count
no repetition \(90 \cdot 89 \cdot 88 \cdot 87 \cdot 86\) \(\binom{90}{5}\)
with repetition \(90^5\) \(\binom{90+5-1}{90-1} = \binom{90+5-1}{5}\)
Table2.8.1Choosing 5 balls out of 90

These ideas can of course be generalized. Say, we have \(n\) numbered balls in a urn, and we want to choose \(k\) out of them, and we are interested in the number of possible ways to do this. There are four different problems according to whether or not the order of the chosen balls counts, and whether or not we put back a ball into the urn after pulling it out. Let us consider the four problems one by one.

If the order counts and we allow repetition, then the answer is clearly \(n^k\text{:}\) for each of the \(k\) choices we have \(n\) balls to choose from, as in Section 2.1. If we do not allow repetition (but the order counts), then this is the same problem as with the Formula 1 competition (Section 2.5): for first choice we have \(n\) balls to choose from, for second choice we have \((n-1)\) balls to choose from (because we cannot choose what we chose first), etc. For the final (e.g. \(k\)th) choice we have \((n-k+1)\) balls to choose from (because we cannot choose those \((k-1)\) balls what we chose before). That is, the number of choices we have is

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

Note, here that the first formula gives a correct answer if \(k>n\text{,}\) that is, when there is no way we can choose \(k\) balls out of \(n\text{.}\) Now, consider the case where the order does not count and we do not allow repetition. Then, each of those cases are considered to be the same, where we chose exactly the same \(k\) balls, only in different orders. So \(k\) balls have \(k!\)-many orders, thus the number of choices for choosing \(k\) balls out of \(n\) without any repetition such that the order does not count is

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

Again, this answer is correct if \(k\leq n\text{,}\) otherwise the answer is 0. This is the same problem we discussed in Section 2.6. Finally, consider the last case: choose \(k\) balls out of \(n\) such that repetition is allowed, and the order does not count. This is the same problem as \(n\) pirates distributing \(k\) gold pieces among themselves (Section 2.7). Indeed, for every gold distribution we can consider to choose those balls which have the same number as the pirates who received gold pieces, and exactly as many times as the number of gold pieces they received. Similarly, for every choice of balls we have a distribution: a pirate gets as many gold pieces as the number of times its corresponding ball has been chosen. Thus, by Theorem 2.7.10 the number of possibilities to choose \(k\) numbers out of \(n\) if repetition is allowed and the order does not count is

\begin{equation*} \binom{n+k-1}{n-1} = \binom{n+k-1}{k}\text{.} \end{equation*}

Table 2.8.2 collects these results in a condensed form.

order counts order does not count
no repetition (\(n\lt k\)) \(0\) \(0\)
no repetition (\(n\geq k\)) \(\frac{n!}{(n-k)!}\) \(\binom{n}{k}\)
with repetition \(n^k\) \(\binom{n+k-1}{k}\)
Table2.8.2Choosing \(k\) balls out of \(n\)

An urn contains \(n\) numbered balls. How many ways can we choose \(k\) balls out of the urn if

  1. \(n = 9\text{,}\) \(k=3\text{,}\) with repetition, the order does not count;

  2. \(n = 3\text{,}\) \(k=9\text{,}\) with repetition, the order does not count;

  3. \(n = 10\text{,}\) \(k=5\text{,}\) without repetition, the order counts;

  4. \(n = 5\text{,}\) \(k=10\text{,}\) without repetition, the order counts;

  5. \(n = 45\text{,}\) \(k=6\text{,}\) without repetition, the order does not count;

  6. \(n = 6\text{,}\) \(k=45\text{,}\) without repetition, the order does not count;

  7. \(n = 100\text{,}\) \(k=10\text{,}\) with repetition, the order counts;

  8. \(n = 10\text{,}\) \(k=100\text{,}\) with repetition, the order counts.