Raising the bar

Chapter 4. Probability

Unit 4.6. Combinatorics

Factorial. For a natural number $latex n$ denote $latex n! = n \cdot (n - 1)...2 \cdot 1$. This number is called $latex n$ factorial.

What do you think grows faster (as $latex n$ increases): $latex {e^n}$, $latex n!$ or $latex n^n$?

Combinatorics is a wide area with a lot of tricky facts but we need only two results, one about orderings and the other about combinations. In order not to confuse them, remember just two motivating examples.

Example 4.1. There are three contestants in a competition, denoted $latex {A_1},\,{A_2},\,{A_3}$, and three prizes of different values (the possibility of ties is excluded). How many prize distributions are possible?

Solution. Let $latex >$ stand for "better". The ordering $latex {A_1} > {A_2} > {A_3}$ is not the same as, say, $latex {A_2} > {A_1} > {A_3}$ because the prizes are different. The number of prize distributions equals the number of orderings and can be found as follows. Any of the three contestants can get the first prize, which gives us 3 possibilities. After the first prize is awarded, any of the remaining two contestants can get the second prize, which gives us 2 possibilities. After the second prize is awarded, there is only one possibility for the third prize. Any of these possibilities (3, 2 and 1) can be combined with any other, so the total number of possibilities is $latex 3 \times 2 \times 1 = 3!$

Example 4.2. To internalize the above argument, consider the case of $latex n$ contestants and $latex n$ prizes.

Orderings. The number of orderings is the number of ways $latex n$ elements can be ordered and it equals $latex n!$.

Example 4.3. There are three new professors on campus and the IT department has 5 new identical computers, 3 of which will be distributed among the new professors. In how many different ways this is possible to do?

Solution. Denote $latex {A_1},\,{A_2},\,{A_3}$ the professors and $latex {C_1},\,{C_2},\,...,\,{C_5}$ the computers. Since the computers are identical, the computer assignment

$latex {C_1} \to {A_1},\,\,{C_2} \to {A_2},\,\,{C_3} \to {A_3}$

is as good as, say,

$latex {C_1} \to {A_1},\,\,{C_3} \to {A_2},\,\,{C_5} \to {A_3}.$

Here is the way to think about this. Each computer is provided with a label $latex {C_i}$. After distributing computers we can remove the labels. Then the above distributions become the same: $latex C \to {A_1},\,\,C \to {A_2},\,\,C \to {A_3}$ which means that professors receive computers with identical characteristics.

To make use of Example 4.2 let us introduce two fictitious persons $latex {F_1},\,{F_2}$. As we know, $latex {A_1},\,{A_2},\,{A_3},\,{F_1},\,{F_2}$ can be assigned computers in $latex 5!$ different ways, if order matters. However, many of these ways are indistinguishable from one another because order does not matter. All distributions indistinguishable from one another fall in one class, and the set of all ordered distributions is a union of classes of indistinguishable distributions. If we find the number of elements $latex N$ in one class, then the answer will be $latex 5!/N$ (division by $latex N$ is similar to removing labels).

After removing labels we still have dependence on persons, therefore the number $latex N$ is equal to the number of orderings of $latex {A_1},\,{A_2},\,{A_3},\,{F_1},\,{F_2}$. To find it, we take into account that real persons can be ordered in $latex 3!$ ways. Fictitious persons can be ordered in $latex 2!$ ways. Five people can be ordered in $latex N = 3!\,2!$ ways. Thus, the number of computer assignments to real persons when the order doesn't matter is $latex \frac{{5!}}{{3!\,2!}}$.

Combinations. The number of different choices of $latex x$ objects out of $latex n$ identical objects is called the number of combinations of $latex x$ elements out of $latex n$ and denoted $latex C_x^n$ (here $latex 0 \le x \le n$).

Example 4.4. Generalize the above argument to show that $latex C_x^n = \frac{{n!}}{{x!(n - x)!}}$.

Comments.

1. When order matters, use orderings and when it does not, apply combinations.
2. I recommend reading $latex C_x^n$ as the "number of Choices" of $latex x$ out of $latex n$.
3. For the choices formula to work in the extreme cases $latex x = 0,\,x = n$ we put formally $latex 0! = 1$.

Exercise 4.5. Write out sequences $latex {C_0^1,C_1^1},\ {C_0^2,C_1^2,C_2^2},\ {C_0^3,C_1^3,C_2^3,C_3^3}$. They first grow and then decline, the first and last elements being 1.

Previous: Ways to find probabilities | Next: All about joint events

Want the whole book (all 14 chapters, exercises, and the index) as a single PDF? Available on Lulu for $1.99.