Counting Techniques and Probabilities

Combination, Variation, and Permutation are the most used counting techniques in the study of probabilities due to the facilities they introduce in the study of experiments with equiprobable outcomes. One of the most iconic examples of these experiments comes from gambling. These are generally non-deterministic processes over a sample space \Omega = \{\omega_1, \omega_2, \cdots, \omega_N\}. These experiments have the common feature that all events of the form \{\omega_i\}\in\mathcal{A}_\Omega, with i\in\{1,2,\cdots, n\}, have the same probability of occurring.

From the measure of probability as a limit of relative frequencies, we can establish the probability of an event as a quotient of cardinalities. As we have seen, this is done through the relationship:

P(E) = \displaystyle \lim_{N\to\infty}g_N(E) = \lim_{N\to\infty}\frac{f_N(E)}{N}= \frac{\# E}{\# \Omega}

Here the symbol “#” refers to the cardinality of the set. This is known as the formula of favorable cases over possible cases.

In these situations, the calculation of probabilities is reduced to calculating the cardinality of the sample space and the event to be measured. That is why it will be very useful to first review some counting techniques.

Derivation of Counting Techniques

To introduce combinations, variations, and permutations, we will design some experiments with equiprobable outcomes and, from them, make inferences that lead to these counting techniques.

Suppose we have a “perfect random machine”, consisting of a black box, a memory, an action button, and a reset button. The machine has the following properties:

1. The machine only has one customizable setting: the cardinality of its sample space \Omega_N = \{\omega_1,\cdots,\omega_N\}
2. Upon pressing the action button, it will display one of the elements of \Omega_N
3. Once a result is displayed, it is stored in the memory, and as long as it is there, it will not be shown again when the action button is pressed.
4. If the machine has shown all possible results, it will freeze and show nothing.
5. The reset button clears the memory and what is displayed on the screen.

With this machine, we will design some experiments and analyze their sample spaces.

Experiment 1 (AORm): Activate – Record in Order – Reset, repeat m times

The machine is configured with \#\Omega = N and the following series of steps are repeated m\leq N times:

1. Press the action button
2. Record the result in an ordered list
3. Reset

When we finish, we will obtain an ordered list with m elements of \Omega_N = \{\omega_1,\cdots,\omega_N\}. This list can be interpreted as an m-tuple of \Omega_N. In other words, the sample space of this experiment \Omega_{AORm} will be in the form

\Omega_{AORm}=\Omega_N \times \cdots \times \Omega_N = \Omega_N^m

Therefore, we will have \#\Omega_{AORm}=\#\Omega_N^m = N^m.

Experiment 2 (AOk): Activate – Record in Order, repeat k times

The machine is set up again with \#\Omega = N and the following series of steps are repeated k times (k\leq N):

1. Press the action button.
2. Record the result in an ordered list.

When we finish, we will have obtained an ordered list of k elements of \Omega_N = \{\omega_1,\cdots,\omega_N\}, but where no element repeats any of the preceding ones.

As the machine, in principle, does not favor any possible result over another (because it is perfectly random), it can be assumed without loss of generality that the first time the action was performed the event \{\omega_1\} occurred, so the sample space of the next action should be \Omega_N\setminus\{\omega_1\}. Similarly, it can be assumed without loss of generality that the second time the action was performed the event \{\omega_2\} occurred; therefore, the sample space of the next action will be of the form (\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}. If we continue in this way, when we reach the k-th action, its sample space will be of the form

(\cdots(\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}\cdots)\setminus\{\omega_{k-1}\}

So, the sample space of possible results of this experiment will be of the form

\Omega_{AOk}= \Omega \times (\Omega_N\setminus\{\omega_1\}) \times ((\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}) \times \cdots \times ((\cdots(\Omega_N\setminus\{\omega_1\})\setminus\{\omega_2\}\cdots)\setminus\{\omega_{k-1}\})

So if we calculate the cardinality of this set we will get

\#\Omega_{AOk}= N \cdot (N-1) \cdot (N-2) \cdots [N-(k-1)]=\displaystyle \frac{N!}{(N-k)!}

Based on this result the following definition is created:

Experiment 3 (ADk): Activate – Record in Disorder, repeat k times

This experiment is exactly the same as the previous one, only now the order in which the elements of \Omega_N appear is not recorded. In other words, what would be two k-tuples with the same elements, but in different orders, are now considered the same. Thus, taking advantage of the fact that each k-tuple obtained from the experiment AOk can be written in (k)_k=k! different ways, it will be that the cardinality of the sample space of this experiment will be of the form

\#\Omega_{ADk} = \displaystyle \frac{\#\Omega_{AOk}}{(k)_k} = \frac{(N)_k}{k!} = \frac{N!}{k!(N-k)!}

From this we can establish the following definition:

With the counting techniques of permutation, variation, and combination, we can now measure the size of a wide variety of sets.