Counting — A visit to Combinatorics
As we briefly discussed on the previous story being able to count the sample points of a sample space (or an event) is very important when we try to solve a probability problem. So I decided to moved some chapters back in my book in chapter about Counting.
Counting techiques are explored by the field of mathematics called Combinatorics and multiplication principle is part of Combinatorics fundamentals.
The multiplication principle
- How many triplets can be formed out of four different nucleotides?
- In how many different ways can I align four flowers pots on my window table?
- How many phone numbers (of 10 digits) can exist?
- How many combinations of high quality and low quality products can be spot in a series of 20 quality controls?
All the above questions can be summarized in this general sentence:
- How many different k-element groups can be formed out using v different elements (1≤k≤ν)?
How many: We care about the number of different combinations that can be created (not which exactly are these combinations)
k-element groups: We deal with ordered group of elements of k length. That means that the position of each element in the group matters. We refer to each element by saying the 1st element (α1), the 2nd element (α2), …, the kth element (ακ).
ν different elements: we pick an element out of a set of v elements to fill in each position in the k-element group.
We can use the multiplication principal to answer each counting problem that can formatted and summarized to much the type of the question above.
The multiplication principal:
If we have v1 different choices for the element a1 and for each of v1 choices we have v2 different choices for the element a2, …., and for each of v1, v2, …., v(k-1) choices we have vk choices for the element ak, then for the combination of the elements a1, a2, …., ak in this particular order we have v1*v2*…*vk total choices.
In other words we split the counting process in steps. Each step is performed after other and we are able to know the number of choices in one step when we know the results in all the previous steps.
Examples
-How many triplets can be formed out of four different nucleotides?
a1 a2 a3 is the 3-element ordered group that represents our triplet. {A,T,C,U} is our fill-in set.
In the a1 position we can place any of the four nucleotides. In the a2 position we can also place any of the four nucleotides. In the a3 position we can also place any of the four nucleotides. So, for each position there are 4 choices.
Following the multiplication principle, 4*4*4 = 4³ different triplets can be formed of 4 different nucleotides.
-How many phone numbers (of 10 digits) can exist?
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 is the 10-element ordered group that represents our phone number. {0,1,2,3,4,5,6,7,8,9} is the fill-in set.
Case 1:
There are no restrictions on which number should be placed on each position. So we have 10 different choices for each element a1, a2, …, a10.
Following the multiplication principle, 10¹⁰ different phone numbers (of 10 digits) can exist.
Case 2:
Let’s say that there is the restriction of the first three digits of the phone number to be 5.
Then the elements a1, a2 and a3 have just 1 choice, while the elements a4, a5, …, a10 still have 10 choices each.
In this case, following the multiplication principle there are 10⁷different phone numbers.
Case 3:
Let’s make it a bit more difficult and say that there is the restriction of the last digit of our phone number to be even number and all the digits to be different.
In this case we should recall the approach of counting in steps and choose carefully which our first step will be.
As we see in the picture, in order to solve this counting problem, we have to set the last digit as the first step of our counting procedure. For digit10 we spot 4 different choices, as many as the even numbers between 0 and 9 {2,4,6,8}.
Remember that each digit of our phone number must be different. So after a digit is chosen for digit10, there are 9 digits available for digit1 (step a2).
The decrease of number of choices by one (1) continues until step a10. On step a3, after a digit for digit1 is chosen, there 8 digits available for digit2. On step a4, after a digit digit2 is chosen, there are 7 choices available for digit3. And so on.
So, following the multiplication principe the number of different phone numbers (using 10 digits and accoriding to the given restrictions) is 9*8*7*6*5*4*3*2*1*4 = 1,451,420.
About my learning journey
My goal is to learn a bit of Statistics everyday for the next 21 days. I am going to study the basics to solidify my knowledge on Statistics and build a strong background for more advanced Data Science concepts.
This challenge is part of a bigger one, the #66daysofdata challenge! To learn more about the #66daysofdata challenge click here and here.
Resource
Introduction in Probability and Statistics, George Papadopoulos, Gutenberg (in greek)
Thank you!
