The Two Rules of Combinatorics
Let’s start with the good news: in combinatorics, there are only two rules that you need to know. If you master these, then you will understand the whole of combinatorics, which will greatly simplify your life. How exactly? We will demonstrate this later on. The bad news is that understanding these rules is not that easy.</p>
<h3>Combinatorics | THE RULE OF SUM</h3>
<p>The number of possible ways to select 1 object from 2 sets is equal to the total number of objects in these sets.</p>
<img width="800" height="675" src="https://oyla.us/wp-content/uploads/2021/02/Scheme01-1-e1690172999900.png" alt="Example of the rule of sum" />
<p>Consider an example. If there are <b>6</b> girls and <b>4</b> boys in a class, then there are <b>6 + 4 = 10</b> ways to choose 1 student. What if we were talking about tables or chairs instead of boys and girls? It’s simple enough — the same operations would apply. But it is necessary to select a pair of objects, instead of just a single object: an object from each set (in this case, there are 2). In that case, the following rule can be applied.</p>
<h3>THE RULE OF PRODUCT</h3>
<img width="435" height="1024" src="https://oyla.us/wp-content/uploads/2021/02/Scheme02.jpg" alt="Example of the rule of product" />
<p>The number of ways to choose a pair of objects from 2 sets (the first object from the first set, the second object from the second) is equal to the product of the number of objects in these sets.
Again, let’s look at an example. Say you have 4 pens and 5 pencils. How many different pairs from these sets can you assemble? For the first pen there are 5 possibilities, for the second — also 5, for the third and the fourth — 5 again. In total, there are 4 × 5 = 20 possibilities.
This rule can work not only for 2 sets. If you also have 3 felt-tip pens, you can assemble the kit of felt-tip pens, pens and pencils in 3 × 4 × 5 = 60 ways. This can be proven in the same way: for each of the 20 ways of choosing a pen-pencil pair, there are 3 ways of choosing a felt-tip pen. And you already know how to proceed from there.
How do we go about distinguishing these rules from each other? Let’s say that, 2 teams of 5 people played in a Dota 2 tournament final, and you need to select a Most Valuable Player among the finalists. How many ways are there of doing this? The correct answer is 10. The sum rule can be used here since we select 1 element from 2 sets. What if we need to select 1 player from each team and reward them as the best in their respective teams, how many ways are there of choosing this pair? The answer is 25. Here, we applied the product rule — after all, you need to choose not just 1 element, but a pair! Figured it out? Then we can move on to examples from real life.
The Magic of Zeros and Ones
Information in a computer is stored in binary code, written in zeros and ones. A single memory cell, also a bit, contains either a 0 or 1. The question is: how many bits would we need to encode, for example, the 26-letter Latin alphabet? It is assumed that each letter is encoded with the same number of bits, and this number must be minimal so that the letters take up less memory space.
Don’t be alarmed if you don’t see a solution right away. In such cases, take the problem step by step by sorting out the simplest answers. What if there’s only one bit? It can be written as either 0 or 1. That is, there are only 2 ways or rather just 2 letters — not enough.
Suppose there are 2 bits or 2 cells. How many different 2-digit numbers can be made up of zeros and ones? Each cell can be represented as a set in which there is either 0 or 1. Then, our task is to select 2 elements from 2 sets. This is the product rule. We end up with 4 ways — again, too few.
In a similar way, taking 3 bits, we have 3 cells to fill. According to the same rule of product, we will have 2 x 2 x 2 = 8 different ways to produce a combination of zeros and ones.
Accordingly, 4 bits will give 2 x 2 x 2 x 2 = 16 ways, and 5 bits — 32 ways. This works for us since 32 is greater than 26. Therefore, at least 5 bits are required to encode the Latin alphabet. And we have arrived at the answer with the rule of product.
Unique Numbers for All
On August 14, 1893, France became the first country in the world to introduce a registration plate for vehicles. Later, almost all countries would follow their example. A registration number is a unique combination of letters and numbers; it is needed to uniquely identify the owner and their vehicle. Over nearly one and a half centuries, the number of cars in the world has come to exceed 1 billion units, and each one requires its own unique number. How has this problem been addressed?
Consider a plate number of 3 numbers and 3 letters — this format is used in countries such as Canada, Botswana, Sweden, Kazakhstan, and Russia. Here, we are not taking into account the regional code, which will be discussed separately.
Combinatorics | Cracking the Code
First of all, we can only use Latin characters for the letters. Accordingly, there are 10 possibilities for each digit and 26 possibilities for each letter. How many unique numbers can we come up with? We must select 1 combination of 3 sets of 10 digits and 3 sets of 26 letters. That is, we must apply the product rule:
10 × 10 × 10 × 26 × 26 × 26 = 17 576 000
Is that a lot or too little? For example, 35 million people live in Canada, or an average of about 2.7 million people in 13 provinces. Even if every resident, including children, has a car, everyone will be able to get a unique number.
In fact, 38% of the population, or more than 13 million people, live in Ontario. As you can see, this number of unique numbers would be sufficient for this province. But in 1997, the province decided to switch to a 4-letter and 3-digit format, thereby expanding the range of possible registration numbers. The population is similarly distributed in Russia — Moscow and Moscow Oblast are the most densely populated. As we said earlier, a regional code is assigned to a 3-digit number, and there may be several such codes for densely populated regions.
<img width="800" height="324" src="https://oyla.us/wp-content/uploads/2021/02/Scheme05.png" alt="Combinatorics | Russian registration number" />
<p>You can even calculate how many digits there should be in a telephone number in your city so that there are enough numbers for everyone! The product rule can be used in this case.</p>
<h2>Combinatorics | Password Strength
Every modern mobile phone has password protection, the simplest form of which is the 4-digit pin code. Knowing the product rule, you can calculate how many different possibilities a hacker would need to sort through to figure out a password:
10 × 10 × 10 × 10 = 10 000
Would you consider this an impressive amount? Today, many phones have built-in protection against hacking — after several unsuccessful attempts to enter a password, your device will be blocked.
But if you think that a 4-digit pin is adequate, we have bad news for you. The British information security company MDSec released a device that can figure out any 4-digit password in a maximum of 111 hours. The trick is that the device enters a password and then waits for 40 seconds — this way, it bypasses the protection system. As a result, it can crack the device in 4.6 days of continuous operation.
How would this situation differ if letters were used in a password? First, apply the sum rule to determine how many ways there are of choosing 1 element from 2 sets:
10 numbers + 26 letters = 36 ways
Now, apply the product rule to determine the number of ways of choosing a password from 4 sets of 36 elements:
36 × 36 × 36 × 36 = 1 679 616 ways
It will take:
40 × 1 679 616 = 67 184 640 seconds, or 777 days
As an independent task, try to count the number of passwords that meet modern security standards:
At least 8 characters in password length
One uppercase letter (A–Z)
At least one lowercase letter (a–z)
One number (0–9)
At least one special character
(~`!@#$%^&*()+=_-{}[]|:;”’?/<>,.)
And most importantly: in boosting your password protection, don’t forget the password itself!
WHAT DO THE COLORS ON A FLAG MEAN?
Determination and victory over enemies.
The color of bloodshed in the struggle for independence, as well as courage and determination.
Freedom, perseverance, justice, prosperity, and peace.
The color of the earth, hope and, in a religious context, Islam.
Purity of thought and innocence.
Prosperity, justice, or wealth.
Fun with Flags
About 30 % of all existing national flags are similar — 3 stripes of 2 or 3 colors. Typically, these colors symbolize the country’s values or history. For example, the colors of the national flag of Germany are black, red, and gold.
In almost all countries, colors on flags represent similar concepts. The most common colors are black, red, blue, green, white, and yellow.
Let’s imagine how many tricolor flags can result from a combination of 6 colors. Would there be enough combinations for 252 countries?
Combinatorics | Flag Design Choices
Let’s consider: for the first flag color, we can use any of the 6 colors. As for the second flag color, it is logical to assume that it should be different than the first, so there are 5 color options instead. For the third flag color — there are 4 options if we do not want the colors to repeat. Still, you may opt for 6 options for the third flag color — if you don’t mind that the first and third flag colors will be the same (like the flags of Austria and Argentina).
Overall:
6 × 5 × 4 = 120 ways
Recall that we applied the product rule here since we select 3 elements, not just 1, from 3 sets. Fortunately for vexillologists studying flags, heraldic flags, banners, and pennants, standardizing all flags is not possible. And we’ve given a rigorous mathematical proof of that.
We’ve given examples of the use of two simple but important rules that underlie combinatorics, which deal with the calculation of the number of possibilities and combinations. In turn, these possibilities and combinations are the basis for calculating, for example, the probability of events — from gains in games to crises in the economy. Seems like combinatorics isn’t useless after all!
Post on topic: Everyday Combinatorics.
Did you like the post? We invite you to read our other topics in Education category.
Follow us on Instagram.
<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" id="Layer_1" x="0px" y="0px" viewBox="0 0 597.03 475.39" style="enable-background:new 0 0 597.03 475.39;" xml:space="preserve"><style type="text/css"> .st0{clip-path:url(#SVGID_00000021828697454809692600000004318893268413411000_);fill:#54A7B7;}</style><g> <defs> <rect id="SVGID_1_" x="63.22" y="2.39" width="470.59" height="470.65"></rect> </defs> <clipPath id="SVGID_00000125586198135712050590000014503595150480814249_"> <use xlink:href="#SVGID_1_" style="overflow:visible;"></use> </clipPath> <path style="clip-path:url(#SVGID_00000125586198135712050590000014503595150480814249_);fill:#54A7B7;" d="M352.92,237.74 c0-30.06-24.38-54.38-54.38-54.38c-30.06,0-54.38,24.32-54.38,54.38c0,30.01,24.32,54.38,54.38,54.38 C328.54,292.12,352.92,267.74,352.92,237.74 M440.15,237.74c0,78.06-63.55,141.62-141.62,141.62 c-78.12,0-141.62-63.55-141.62-141.62c0-78.12,63.5-141.62,141.62-141.62C376.6,96.12,440.15,159.61,440.15,237.74 M533.83,237.74 c0-129.78-105.58-235.3-235.3-235.3c-129.78,0-235.3,105.52-235.3,235.3s105.52,235.3,235.3,235.3 C428.26,473.03,533.83,367.51,533.83,237.74"></path></g></svg>
