Calculating cardinality

Our life is full of unpredictability. Whether you are thinking about sports competitions, tomorrow's unstable train schedule, or next week's weather forecast, you often do not know exactly how it is going to end. Everything you can do is to guess and sometimes hope it ends the way you need.

Probability provides precise mathematical rules for understanding and analyzing problems. It does not tell you the winner of competitions, does not ask the train station worker about transport routes, and does not make the sky clear. Instead, it gives you an understanding and a couple of skills to make decisions based on what you should and should not do in different situations. If there is a 95% chance that the train will not come, you can plan your route from home to the office differently.

This topic is going to talk about outcomes of different but simple and clear examples. It will help you to understand the main concept of probability theory and introduce commonly used concepts from combinatorics.

Flipping coin

Imagine you are flipping a fair two-sided coin. Which side will it land on? Well, there are only two options: heads or tails. The number of all options you can get is the number of outcomes, and one flip gives us two different outcomes. As you can see, it is a 50/50 chance of getting heads or tails.

Let's say you flip a coin twice in a row. If the first flip results in heads, there are still only $2$ options for the second flip: heads or tails. If the first flip lands on tails, again, there are only $2$ options for the second flip: heads or tails. In each of the $2$ possible outcomes from the first flip, there are $2$ possible outcomes for the second flip. Therefore, you have a total of $2 \cdot 2=4$ possible outcomes. Check out the table below for a visual representation:

It also can be illustrated by a binary tree:

Okay, what if you flip the coin $3$ times? A binary tree describes the situation clearer:

The last row is all possible outcomes, and if you count them, you can see that the total is $8$. Although it may not always be possible in a probabilistic problem to calculate all outcomes, there is no reason to not do that when you can.

How could you get this number without a picture? Let's break it down. For each possible outcome of the first coin flip, there are a certain number of possible outcomes for the second flip, and then for the third flip.Thus, coin flipped $3$ times gives $2 \cdot 2 \cdot 2=8$ possible outcomes.

Ready to count all outcomes of flipping a coin $4$ times? It is like you have already flipped it $3$ times (getting $8$ possible outcomes) and now want to flip one more time (as you already know, it is going to be heads or tails). So there are $8 \cdot 2=16$ possible outcomes — and you do not need to make a binary tree to confirm it!

Now you are ready to formulate the first conclusion.

For example, a coin flipped $5$ times gives $2^5=2 \cdot 2 \cdot 2 \cdot 2 \cdot 2=32$ possible outcomes, and there are $65536=2^{16}$ outcomes if you flip the coin $16$ times. Imagine drawing such a binary tree! It would take a lot of space and would be tedious to do by hand. Thankfully the formula helps us to avoid manual calculations.

When considering the flips and number of total outcomes, you don't care about the particular order. But what if you need to be more specific and want to investigate particular combinations? In this case, you have to work with permutations.

Permutations

Suppose you bought $3$ named concert tickets for yourself and two friends. Before the staff checks everyone's ticket, you randomly give one ticket to one friend. Is there any chance that all of you are holding your own named ticket now? And how lucky are you if it is?

Let's name all persons as $A,\ B,\ C$ and give them tickets $1,\ 2,\ 3$ (first ticket belongs to $A$, second one is to $B$ and third one is to $C$). Now describe all possible outcomes and check your luckiness:

$A-1,\ B-2,\ C-3\\ A-1,\ B-3,\ C-2\\ A-2,\ B-1,\ C-3\\ A-2,\ B-3,\ C-1\\ A-3,\ B-1,\ C-2\\ A-3,\ B-2,\ C-1$

There are no other ways to rearrange $3$ tickets, so if everyone got their own ticket, there is only $1$ chance of $6$ possible outcomes.

In other words, we have just described and calculated all possible permutations of $3$ items.

Order is very important when it comes to permutations. How to calculate it without naming all outcomes? First, you have three choices for the first ticket for person $A$ (let it be ticket number $2$ for example). Then you have two available options for $B$ (as number $2$ is unavailable now, there are tickets number $1$ or $3$, let it be $1$). And finally, there is only one ticket left for $C$ — ticket number $3$. Thus, three tickets can be permutated $3 \cdot 2 \cdot 1=6$ different ways: for each of $3$ possible outcomes to give the first ticket, there are $2$ possible outcomes to give the second one and only $1$ possible outcome to give the third one.

What about $4$ tickets for $4$ persons? It is better to draw a tree when every branch from the top to the bottom is an outcome. For example, the colored path indicates the order $3241$. Take a look:

Having all possible branches in the tree, you are able to count all outcomes now: to get all paths from the top to the bottom is the same as counting the number of terminal points of the tree! A set of terminal points gives you $24$ possible ways to permutate $4$ items, and it is equal to $4!=4 \cdot 3 \cdot 2 \cdot 1$.

Now you are ready to define the permutation's formula.

The sign"$!$" after the number $n$ is called factorial of number $n$. Factorial of zero is equal to $1$: there is only one way to permutate a set with no elements.

Five books on a bookshelf can be permutated in $5!=5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=120$ ways, and there are $720=6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=6!$ ways to define the queue of $6$ people at the cash desk.

A permutation of $n$ items is also called a permutation of length $n$. Since writing out exclamation marks or direct explicit multiplication takes too much space (and sometimes you need the context that it is indeed permutations and not just a factorial), the common notation for the number of permutations is denoted as $P_n$.

Combinations of a match-making

Let's say we want to know some possibilities but we don't care about the order inside the subset. For this let's turn to throwing dice. Suppose we roll two six-sided dices. There are $6$ possible outcomes for each dice: $1,\ 2,\ 3,\ 4,\ 5,\ 6$. Let's calculate all possible outcomes filling the following table:

Since each dice has $6$ possible outcomes, this is referred to the multiplicational principle again: for each of the $6$ possible outcomes first dice gave there are $6$ possible outcomes second dice gave. Therefore, six-sided dice rolled twice outcomes $6 \cdot 6=36$ different ways. It also can be illustrated by a tree:

Now what if you roll one six-sided dice and another one with only odd numbers going twice on its sides? How to count all the different pairs? First, let's make a table the way you did before, but this time the green dice would only have values of 1, 3, and 5 (it still has six sides, though):

You got $6 \cdot 6=36$ pairs again since you throw two six-sided dice. The key point is that every second column of the table is a copy of the previous one. Half of all cells are not unique because only $3$ of second dice's sides are different. Thus, there are only $6 \cdot 3=18$ different pairs.

Dice's research leads to the multiplication formula of making a pair.

All elements of both sets are different, and all pairs are different as well: you can make $4 \cdot 3=12$ two-words phrases "adjective+noun" using sets "red, green, blue, yellow" and "cup, hat, pillow", all words and pairs are unique and different.

Picking marbles

The cases above used all the items you are working with. If you permutate tickets, you choose the owner for each of them. If you make pairs, you match every first possible item with the second possible one. Now you are going to look at selection — a situation when you pick only a few items, not all of them.

Imagine there is an urn with $5$ marbles: red, green, blue, yellow, and violet. You pick two marbles at random. Order does not matter: pairs "red+green" and "green+red" are equivalent. Given this, how many outcomes will you get?

Let's make a table. You will use the first letter to mark colors: pair "red+green" will be described as "RG". Since there are only $5$ marbles, a combination "RR" or any other "same-color-twice" pair does not exist: picking red marble as the first one, there is no option to pick it twice.

Now look at all combinations we get:

Counting all color pairs for this, you get $20$ possible outcomes. Since order does not matter and you are looking for unique sets, half of the cells are unnecessary: pairs GR and RG mean the same. Therefore, there are only $10$ ways to pick $2$ marbles out of $5$, not $20$. To be more formal, you count all combinations of size $2$ that can you can form from $5$ items.

The order of selection is not important. All that matters is which $2$ marbles you pick.

Making combinations of $3$ marbles from a set of $20$ marbles is a bit complicated. Fortunately, there is a way to calculate all of them. And you are just only one step away from it!

You can pick the first marble in $20$ ways: all marbles are available now. There are $19$ marbles available after the first pick, therefore now you can pick the second one in $19$ different ways. Next only $18$ marbles left, so you can pick the third marble in $18$ ways. For each of the $20$ possible outcomes of the first pick, there are $19$ possible outcomes of the second one and $18$ possible outcomes of the third one. The multiplicational principle gives you $20 \cdot 19 \cdot 18=6840$ possible ways to make a marble trio. However, outcomes "red+green+blue" and "red+blue+green" are not different: order does not matter. So to get the final answer, you need to exclude all undifferent outcomes — to count permutations of $3$ marbles. Three marbles give $3!=3 \cdot 2 \cdot 1=6$ permutations. This means that getting $6840$ as an answer is $6$ times greater than it is actually needed. Therefore, the number of all different combinations of $3$ marbles from a set of $20$ marbles is $\dfrac{6840}6=1140$.

This was tedious, but there is good news: a number of combinations has its special formula that allows you to calculate them for any number of outcomes!

The number of all combinations is denoted as $C_n^k$ or a binomial coefficient $\binom{n}{k}$, that depends on the traditions of the particular field. Usually, in probability, we use $C_n^k$ notation, the lower number is always greater than the upper one, so it may help you to not get confused. Take into account that subscript and superscript in $\binom{n}{k}$ changed places for $n$ and $k$, in this case, the upper number is greater than the lower one.

Let's use the formula to $3$ out of $20$ marble's case and check the answer:

$C_{20}^3=\binom{20}3=\dfrac{20!}{3! \cdot (20-3)!}=\dfrac{20!}{3! \cdot 17!}=\dfrac{20 \cdot 19 \cdot 18 \cdot 17!}{3 \cdot 2 \cdot 1 \cdot 17!}=\dfrac{20 \cdot 19 \cdot 18}{6}=1140$

Surprisingly picking up $17$ marbles out of $20$ leads to the same result — and it is totally logical since if you pick $3$ marbles, there would be $17$ marbles staying in the bag. The formula proves it mathematically:

$C_{20}^{17}=\dfrac{20!}{17! \cdot (20-17)!}=\dfrac{20!}{17! \cdot 3!}=\dfrac{20!}{3! \cdot 17!}=C_{20}^3$

Let's mark it as a symmetrical conclusion.

There are other combinatorial formulas for other cases, but we covered the most commonly used ones, and now you are ready to continue applying them to study probability.

Conclusion

The main concept of probability theory is based on counting outcomes — all desired and possible ones. To calculate it wisely, here are some conclusions:

• A two-sided coin flipped $2,\ 3,\ ...,\ N$ times gives $2^2,\ 2^3,\ ...,\ 2^N$ possible outcomes
• The number of permutation of $n$ items is equal to $n!=n \cdot (n-1) \cdot ... \cdot 3 \cdot 2 \cdot 1$
• There are $6 \cdot 6=36$ possible outcomes for six-sided dice rolled twice

• The number of ways to make a pair is $n \cdot k$ for two sets of $n$ and $k$ different elements

• The number of all combinations of size $k$ that can be formed from $n$ items is $\dfrac{n!}{k! \cdot (n-k)!}$. Item's order (in subset of size $k$) is not taken into account in this formula

• The number of all combinations $C_n^k$ is symmetrical: $C_n^k=C_n^{n-k}$