Combinatorics - 3

Combinatorics - 3

PREVIOUS

Kabani was making progress with her counting of how many possibilities are there in anything she did. Sometimes she found it easy like switching a light on or off, sometimes it became tougher like the possible lengths of a line she could draw with a 15cm scale. Her parents couldn't help her either on this. Her unsolved problem list was ever-increasing now. It was a big motivation to explore further...

Kabani observed that while calculating the number of possibilities sometimes she was adding and sometimes she was multiplying and she never did them together. Now this was strange! She wasn't told where to do what, then how did she know - when and what to do. Look at the following problems -

There are 5 apples and 3 oranges, the number of ways you can select an apple or an orange is ______.

There are 5 apples and 3 oranges, the number of ways you can select an apple and an orange is ______.

The two questions varied in just one word and that makes all the difference. When Kabani was given the choice to select an apple or an orange, she was selecting one object out of the 8 objects as there was no emphasis on what she should be selecting. So the number of ways she could have done that was 8. However, when she was told she had to select both an apple and an orange, the situation is very different. She can select any one of the 5 apples, so the selection is possible in 5 ways. Once she has selected the apple, she can select an orange in 3 ways. After every choice of an apple there are 3 further choices. So in all she can make a selection in 3 + 3 + 3 + 3 + 3 (=15) ways, i.e., 3*5 or 5*3 ways. (Do you remember the law which says 3*5 = 5*3?). What Kabani thought was multiplication was just repeated addition! But why repeated addition?

The reason lies in the fact that, in the first case Kabani was doing only one work but in the later she had two tasks. She could do the first in a few different ways and then later do the second in few more ways, thereby resulting in a huge number of ways she can complete both the tasks together.

Mathematicians call the first case as the law of sums and the second as the law of products. The names hardly matter... may be they should better be called as the law of addition and the law of repeated addition. It is for you to decide, what you would like to call them. How about Alpha Rule and Beta Rule? You are now one step ahead in your understanding of combinatorics, that is what matters. 

Until next time -

A "sign" is being assigned to every person in a village. Each "sign" consists of a geometrical figure (triangle, square, rectangle or circle), an alphabet and a single-digit number. How many unique signs can be made?

NEXT (coming up)

Combinatorics - 2

PREVIOUS

Permutations with Repetitions - In the world around us

As Kabani tried to read more about permutations with repetitions, she comes across several examples: Secret locks, Morse code, Genetic code etc.

One of them was that of secret locks (also called combination locks). These locks open up only when a specific combination of numbers or alphabets is dialed.* One example of such a combination lock is the ATM card pin number. Each pin number has 4 digits and each digit's place can be filled with any of the ten numbers (0, 1, 2... 9). Using the method we have seen earlier, the total number of calculations is found to be 10⁴ = 10000. Which means that of these 10000 combinations, 9999 will be failures. (ATM cards usually stop working after typing the wrong pin number thrice, so even if someone gets your card there is very little chance that they can get the right number in three attempts. 9999 is too big you see!)

Morse Code
The Morse code is used in telegraph communications. In this code, the alphabets, numbers and punctuation marks are represented by dots and dashes. Some characters are represented by just a single sign (by a single sign we mean one (.) or (-)), like E (.), T (-); whereas others use five signs, like zero, 0 (- - - - -), 1 (. - - - -) etc. But why the number 5? The answer lies in the number of permutations with repetitions possible. Here, we can fill each place with either dot (.) or dash (-), i.e. 2 options. Suppose we are using only one sign, it is possible to have 2¹ (= 2) distinct arrangements and hence we can transmit only 2 letters (E and T). Using two signs, we can transmit 2² (= 4) letters, using three signs we can transmit 2³ (= 8) letters and using four signs we can transmit 2⁴ (= 16) letters. Thus the total number of letters we can transmit using up to four signs is 2 + 4 + 8 + 16 = 30 which will not be sufficient for transmitting all the alphabets, numbers and punctuation marks. Using five signs, we can additionally transmit 2⁵ (= 32) letters and so in total we will now have 62 options which is quite sufficient. The Morse code described here makes no difference between alphabets written in the upper case and lower case. If we were to incorporate that, how many signs would we need?

Similar to the Morse code is the Wig Wag code (also called as flag semaphore). This is a visual signaling system for conveying information over long distances by using flags (especially in navy). Each letter is represented by two flags in a specific arrangement.

Genetic code
Breaking the genetic code has been one of the most remarkable achievements of the twentieth century. Scientists now know how genetic information is passed on from one generation to the other. The genetic information is stored in giant molecules of deoxyribonucleic acid (DNA). Each molecule of DNA is an arrangement of the four nucleotides (adenine, thymine, guanine and cytosine). Molecules of DNA differ in the arrangement of these nucleotides and they determine the order in which the proteins are built from the 20 amino acids. Each amino acid is in the form of a code made up of three nucleotides.  Why codes of only 3 nucleotides? The answer is similar to the one in Morse code. Using combinations of just one or two nucleotides would not result in sufficient number of combinations for the 20 amino acids and the START / STOP functions. Hence, codes of three nucleotides would be required. It is interesting to see how nature takes advantage of so much redundant information – the number of combinations is 64 while the number of amino acids is only one third! (Do find out more about how nature uses the excess of combinations in regulating the protein expression and fighting mutations).

A single chromosome contains millions of nucleotides. The number of distinct chromosomes possible is 4^N , where N is the number of nucleotides in the chromosome. The number is just too big to write it down here, however only a very small fraction of these have been sufficient to ensure the diversity of all life on this planet. Why only a few? These are questions yet to be answered.

*Do you remember the CRYPTEX in Dan Brown's book "The Da Vinci Code"? The CRYPTEX is a word coined by Brown for a vault which carries secret messages. The dials on the top of the vault have to be arranged as per the secret code to open the CRYPTEX. Secret messages are written on a papyrus scroll and kept inside the vault. If someone forces open the CRYPTEX, the vial (inside the vault) carrying vinegar will break and the vinegar will dissolve the message on the papyrus scroll; the message will be lost forever. So to access the secret message, we need to have access to the secret code.

NEXT

Combinatorics - 1

PREVIOUS

1 - Lucky or Unlucky?

The summer vacation had been a boring time for Kabani. She was not allowed to go out and play in the sun, she was in her room all day painting. Even painting was getting a bit boring now... Few of her mother's friends came home, they had been talking long.

Kabani overheard one of her aunts saying "1 is so unlucky for me!". She wondered how it really mattered. Kabani started counting how many other digits were there - 0, 2, 3, 4, 5, 6, 7, 8 and 9 - i.e., nine of them! Then she started counting the number of two-digit numbers which didn't have 1 - 00, 02, 03, 04... - she finally had written down all of them. There were 81 one of them. The most interesting observation she made was that each digit could be followed by any of the nine digits, which meant she could have 9*9 (=81) possible two-digit numbers without 1.

Taking the calculation forward, she predicted that there will 9*9*9 = 729 three-digit numbers without 1 and there would be 9*9*9*9 = 6,561 of those four-digit numbers! Kabani wondered how these numbers would change if her aunt felt that both 1 and 2 were unlucky. The answers were simple, there would be 8 one-digit numbers, 8*8 = 64 two-digit numbers, 8*8*8 = 512 three-digit numbers and 8*8*8*8 = 4,096 four-digit numbers which don't contain 1 or 2!

Permutations with Repetitions
The above problem falls into the following class of problems. There are n different objects. We have to select objects from the above n to fill r vacancies in a straight line. When each of the r vacancies has been filled, we call it an arrangement (also called as r-arrangements). Each r-arrangement can contain more than one object of the same type (this is referred to as repetition) and two r-arrangements would be considered distinct if they vary at least at one of the r positions. The task is to find the total number of such distinct arrangements. These arrangements are called r-permutations of n distinct objects with repetitions. For filling the first vacancy we have n options, for filling the second vacancy we have n options, for the third it is n options and so on. So for filling each of the r vacancies we will have n options and hence the total number of ways we can make the arrangement is n^r . It would also be equal to the number of distinct r-arrangement possible.

In the earlier problem, we had to find the number of possible two-digit numbers from 9 distinct digits. The answer would be 9² ! All the calculations of Kabani can now be done easily without wasting much time and energy. Permutations with repetitions have many valuable applications in the world around us, we will explore a few of them in the next article.

NEXT

Combinatorics - 0

The story behind a dice game

Every day we come across passwords. Passwords for computers, passwords for ATMs (commonly referred to as pin number), number locks, and so on. All of these are combinations; some are combinations of alphabets while others are combinations of numbers and still others use symbols; in some cases the passwords are case-sensitive, sometimes they are not.

Among other examples of combinations we can think of – how your teachers come up with the time table, how a metallurgist tries different combinations of elements to come with up an alloy of desired properties, how a linguist examines the meanings of combinations of letters in an unknown language and so on. All of these visibly 'different' applications come under one roof called combinatorics. Combinatorics (or combinatorial mathematics) is a field of mathematics that deals with problems of how many different combinations can be built out of a specific number of objects.

This field has its origin in the gambling games that played a large part in the European high societies in the 16th century. Whole fortunes were won or lost in a game of cards or dice; something very similar to how the Pandavas lost all their fortunes in a game of dice in the Mahabharatha! In how many ways can a certain sum in throws of two or three dice be scored (haven't you played Ludo?), in how many ways is it possible to get two kings in a card game and other similar problems in a game of chance gave the initial push to develop combinatorial mathematics and the theory of probability.

Italian mathematician Tartaglia was among the first to list the various combinations that can be achieved in a game of dice. His list showed the number of ways 'x' dice can fall. However he failed to take into account the fact that the same sum can be achieved in different ways. For example, if we are using 2 dice and we want a sum of 7, the various combinations are (1,6), (2,5) and (3,4).

In the 17th century, Chevalier de Mere, an ardent gambler, had sort the help of his friend Pascal to determine the division of the stakes of an interrupted game of chance. This marked the first theoretical investigation into the problems of combinatorics. Fermat, a contemporary French mathematician, was also working on the same problem. Their work was followed by valuable contributions from Bernoulli, Leibnitz and Euler.

Combinatorics is extensively used in the field of statistics, cryptography, discrete mathematics, linear programming, group theory, non-associative algebra... the list is unending. Most of the names given above might sound new and not of your understandability. However, it is interesting to realise that the mathematics involved in all of them is the same as in a game of dice. Through a series of articles we will travel with Kabani (a student like you) through the field of combinatorics. We will learn to solve problems from the simplest to the toughest, and enjoy the beauty of mathematics. The only thing that you need to know is how to play a game of dice!

Food for thought -

Simplest Question – In a class, every student is to be given a 2-digit roll number. What is the maximum number of students that can be given the roll number?

Toughest Question – There is a queue of x + y persons at a ticket counter of a cinema theatre. x have Rs20 note and y have Rs10 note. Each ticket costs Rs10 and the cashier has no change to start with. In how many ways can the people line up so that the line keeps moving and no one has to wait for change?

Reference – “Combinatorial Mathematics for Recreation” by N. Vilenkin. Translated from the Russian by George Yankovsky

NEXT