PA-4 / Lesson 2

For easier and less intimidating viewing, better use a bigger display. Unless you're watching a video or recalling something

ClassworkProblem SetExtra

02. Combinatorics

2.1 Intro & Comments

The problems from the previous lesson primarily focused on counting, revolving mostly around "counting combinatorics". While we did introduce a few new terms, such as "probability model", these weren't new tools for solving problems or groundbreaking theorems. They were simply additions to our mathematical vocabulary. This is an important point, as well as a helpful way of looking at things here. I.e even though "Probability Theory" is ultra-applicable for solving many real-world problems, on a foundational level, the so-called "Discrete Probability Theory" (i.e not picking a point on an interval, or in a square) is just combinatorics: you count things, find the ratio of a particular type of combinations among the whole set of combinations and so on...

We are yet to put our new vocabulary in some use, in particular see how come probability theory is so applicable in real-life. We will get there, don't worry. But today we will stress the point above, in particular we will see yet again that even though the word "random" (or its synonyms) is used quite a lot in probability theory, there is no "randomness" involved in the maths behind it! It is all deterministic from the maths point of view.

This lesson will be mostly about problem-solving, and here a few comments before we move on to doing them:

  • We expect that you have already worked enough with the so-called product rule and the factorials (in particular its meaning in combinatorics);
  • Moreover, we assume that you have worked enough with $\binom{n}{k}$ (read as "$n$ choose $k$") things;
  • For the problems below (and many non-trivial combinatorial problems actually), it is totally okay to leave a closed formula in the answer, e.g smth like $1-\frac{\binom{10}{5} \cdot 5^5}{6^{10}}$. I.e no need to get the final approximate answer or the final fraction! In fact, it is often better if you do not simplify it further, because then it is easier to see the logic behind your answer;
  • Just in case, the $\mathbb{P}(A)$ is the notation for "probability of an event A". This is merely a notation.

2.2 Standard Exercises

Exercise 1.

An 8-digits number is picked at random. What is the chance that this number has at least one digit 4 in its decimal representation?

Explanation and comments

click on blur to reveal

The main idea of this exercise is to realise that the answer is $1 - \mathbb{P}$(no fours in decimal representation). Before we get to the answer though, let's clarify the Probability Model:  

  • Our model's simple events will be all of the 8-digits numbers, there are $9 \cdot 10^7$ of them;
  • We will choose our model to be uniform (it is in particular motivated by the problem statement), so each of the simple events gets probability $\frac{1}{9 \cdot 10^7}$ assigned;

See, it does not take long to clarify this important bit :) Anyway, note that there are $8 \cdot 9^7$ eight-digits numbers which don't have digit 4 in their decimal representation. From here, it is easy to derive that the answer is
\[ 1 - \mathbb{P}(\text{no fours in decimal representation}) = 1 - \frac{8 \cdot 9^7}{9 \cdot 10^7} \]

Exercise 2.

A fair die is rolled 60 times. What is the probability that you will see 1 precisely 10 times?

Explanation and comments

click on blur to reveal

First of all, let's clearly define our probability model:

  • Our simple events will be all possible combinations of 60 die-rolls, and there are $6^{60}$ of them;
  • We will choose our model to be uniform (it is in particular motivated by the problem statement), so each of the simple events gets probability $\frac{1}{6^{60}}$ assigned to it;

Now, all we need to calculate is the number of combinations in which there are precisely $10$ ones. This is not difficult if you are on good terms with standard counting combinatorics (which is a prerequisite for this lesson): there are $\binom{60}{10} \cdot 5^{50}$ such combinations. Therefore the final answer is \[ \frac{\binom{60}{10} \cdot 5^{50}}{6^{60}} \]

Exercise 3.

The letters of the word BEAR are mixed and then laid out in a random order. What is the probability that the same word is laid out? What if the word is BEER? What if its ABRACADABRA?
For this question especially: please specify your probability model clearly!

Explanation and comments

click on blur to reveal

Interestingly,  there are two ways to construct a reasonable uniform probability model for this question. They are similar and both will lead to the same answers, but they are not exactly the same! In particular, one could argue that one is not as "reasonable" as the other ones. Here they are:

  • Assume that each letter is written on its own card. Then, even if some letters are the same, there are still $n!$ permutations of the cards. Thus, we can reasonably consider a uniform probability model with $n!$ simple events, where $n$ is the number of letters in the word;
  • Alternatively, we could say that the simple events are the set of possible words we can get (i.e not think of any cards or anything). For example, in case of the word DAD we only have 3 simple events, and not 6 (as we would in the model above);

These two models are different, they have different number of simple events in some cases! Which one would you call "more reasonable"? I would argue, that the first one is, since it feels more natural to consider permutations of letters as a permutation of cards where all of the outcomes are equally likely. As for the second model: why would you say that all of the possible words you can get are "equally likely" (i.e symmetric)? Is it really that trivial and intuitive? So let us stick to the first model and le'ts solve the problem then:

  • BEAR and BEER: In case of the word BEAR, there are $4!=24$ simple events, and only one of them is favourable. Thus the answer is $\frac{1}{4!} = \frac{1}{24}$ in this case. In case of the word BEER we still have $4!=24$ simple events, but this time $2$ of them are favourable (since we can obtain the word BEER in two ways). Thus the answer is $\frac{2}{4!} = \frac{2}{24} = \frac{1}{12}$.
  • ABRACADABRA: In this word there are 5 letters A, 2 letters B, 2 letters R, 1 letter C and 1 letter D, 11 letters all together. Each of the cards with the same letter can be permuted without changing the word. Therefore we can obtain the word ABRACADABRA in $5! \cdot 2! \cdot 2! \cdot 1! \cdot 1!$ ways, and thus the answer is \[ \frac{5! \cdot 2! \cdot 2!}{11!} \]

2.2 Further Exercises

Exercise 4.

Ellina has twelve blocks, two each of red (R), blue (B), yellow (Y), green (G), orange (O), and purple (P). Call an arrangement of blocks even if there is an even number of blocks between each pair of blocks of the same color, for example, the arrangement
{R B B Y G G Y R O P P O} is even. Ellina arranges her blocks in a row in random order. Find the probability that her arrangement is even.

Explanation and comments

click on blur to reveal

Unlike the problems from before, this one requires an insight. Consider labeling the positions where blocks can be placed as 1 through 12. To satisfy the requirement that there must be an even number of spaces between each pair of spots of the same color, the odd-numbered positions (1, 3, 5, 7, 9, 11) must contain a permutation of all six colored blocks. Similarly, the even-numbered positions (2, 4, 6, 8, 10, 12) must contain another set of six blocks of different colors.
On the other hand, by placing six differently colored blocks in the odd-numbered positions and another six in the even-numbered positions, we achieve an even configuration. Thus, the number of even configurations is $6! \cdot 6!$. The total number of possible arrangements of blocks is $\frac{12!}{(2!)^6}$, therefore the probability of achieving an even arrangement under the uniform probability model is: \[ \frac{6!\cdot6!}{12! / (2!)^6} \]

Exercise 5.

There are 35 children are in a class. Show that the probability two of them having a birthday the same day is greater than $\frac{1}{2}$.
You can assume that there are 365 possible birthdays and each day is equally likely to be someone’s birthday. But just so you know – this assumption is not true in reality... If you struggle to prove it, feel free to look up "Stirling's Approximation".

Explanation and comments

click on blur to reveal

First of all, without going through details like probability model and simple events, the answer is this: $1-\frac{365 \cdot 364 \cdot ... \cdot 331}{365^{35}}$.

Now, how do we show that $\frac{365 \cdot 364 \cdot ... \cdot 331}{365^{35}}$ is larger than a half (from where the conclusion will follow)? Both the denominator and the numerator are huge numbers, so what do we do? One of the ways, is to use a so-called Stirling's Approximation. In its simple form, it says that \[ n! \approx \sqrt{2\pi n} \cdot (n/e)^n .\] Yeap, the famous constants $\pi$ and $e$ both play a role here! But you do not really have to know much about them, maybe only the approximate value of $\pi$ (the $e$-s will cancel out in this problem). Surprisingly, this approximation is good even for small $n$, it is always a slight underestimate: \begin{array}{c|c|c|c} & n! & \text{Approximation} & \text{Ratio} \\\hline1 & 1 & 0.922 & 1.084 \\2 & 2 & 1.919 & 1.042 \\3 & 6 & 5.836 & 1.028 \\4 & 24 & 23.506 & 1.021 \\5 & 120 & 118.019 & 1.016 \\6 & 720 & 710.078 & 1.013 \\7 & 5040 & 4980.396 & 1.011 \\8 & 40320 & 39902.395 & 1.010 \\9 & 362880 & 359536.873 & 1.009 \\10 & 3628800 & 3598696.619 & 1.008 \\ \end{array}
It is totally fine if you do not know how to formalise the "approximately equal" (which involves talking about the limits of things). We do not expect you to at this stage. It is okay if you simply think about this result as "an approximately equal" without knowing how to formalise it or how to bound the ratio of $n!$ and the formula.

By the way, here are two interesting remarks on the exercise itself: 
1) Even if there are just 23 students in a classroom, it is already true that the probability of two of them sharing a birthday is larger than 0.5. In fact: \begin{array}{c|c|c|c|c|c|c|c|c|c} n = 1 & n = 5 & n = 10 & n = 20 & n = 23 & n = 30 & n = 40 & n = 50 & n = 60 & n = 70 \\\hline 0.0\% & 2.7\% & 11.7\% & 41.1\% & 50.7\% & 70.6\% & 89.1\% & 97.0\% & 99.4\% & 99.9\% \\ \end{array}
2) Also, the probability of finding a triple with the same birthday exceeds 0.5 for $n \geq 88$.

Conclusions, and next steps

We've practiced solving combinatorial problems that look like probability problems. The next step is to solve a bit more of these in the Problem Set and, if you get to it, Extra.