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

Nuclear Physics - 1

PREVIOUS

1. Great Discovery, Humble Beginning…

The 19th and the 20th centuries were the time for the most breath-taking discoveries and inventions of modern science. What was once considered fiction and everything that was ever dreamt of - flying machines for carrying people non-stop from continent to continent, submarines which could travel under water from Pole to Pole even under ice, rockets to carry us to the other worlds in the universe, apparatus to make it possible to converse over long distances without wires, and what not.

The development of science and technology outran the fantasies of the writers and the dreams of the scientists. One of the miracles of the era was the discovery of a mysterious chemical, a matchbox full of which could produce enough energy to propel a large ship for several years! The secret to its vast energy lies deep inside the matter that surrounds us.

At the turn of the 20th century, little was known about the structure of matter. Not all elements had been discovered, however it had been established that all matter was made of atoms. Atoms were believed to the smallest, and hence indivisible, particles of matter. J J Thomson then discovered the electron, the smallest particle of negative charge and soon Robert Millikan determined the mass of an electron to be 1836 times lighter than an atom of hydrogen, the lightest of all elements. In 1898, Thomson proposed that the indivisible atom was a uniformly distributed positively charged sphere, in which electrons were embedded. This proposal couldn't answer several of the questions raised about the plausibility of positively charged particles, stability of the atom and so on.

Becquerel's Mistake

The phenomenon of the luminescence of certain substances when exposed to sunlight is called fluorescence. The French scientist Henri Becquerel spent many years studying this phenomenon. Once he had observed a photographic film wrapped in a black paper and kept in a drawer was exposed. There was no way this could have happened because the substance (sulphate salt of potassium and uranium) he used could have fluoresced in the darkness of the drawer. When he studied more carefully the reasons for the same, he could establish that the binary salt of uranium and potassium emitted invisible rays that could expose the photographic film even in darkness. Thus, 26 February 1896, marked the discovery of a new physical phenomenon which became the starting point of the whole of new physics of the 20th century. It is interesting to note that all of the physics that followed started from this accidental observation. More to come in the articles to follow…

NEXT

Nuclear Physics: An Overview

0. Nuclear Physics – a fascinating subject

E=mc² ... In class 9, I was taught this simple equation. This is one of the most popular equations of science and it was given by none other than Albert Einstein. What does it mean? It mathematically tells us that mass (which you can see or feel) can be converted to energy (which cannot be seen or felt) and vice-versa. This was given as a part of Einstein's Special Theory of Relativity which talks about things becoming longer, clocks slowing down and many more counter-intuitive and very interesting ideas.

Everyone might have heard about the nucleus. The nucleus has protons (positively charged) and neutrons, but how are they held together? Protons should be repelled by each other, isn't it? They are held together by an enormous force called “Nuclear Force”, which is several times stronger than the Coulomb force of repulsion between the protons. Existence of such a force also implies the presence of an enormous amount of energy. Where does this energy come from? Some of the mass of the nucleus is converted to provide this energy. Nature is clever! The mass lost in the conversion is termed as mass-defect and the energy produced is called binding-energy. More the binding-energy per nucleon more stable the nucleus is (find out the most stable nucleus). It is this binding energy which is of interest for us.

Humans are trying to tap this vast energy using two types of nuclear reactions called nuclear fission and nuclear fusion. Nuclear fission reaction is used in modern day nuclear reactors and the fuel used is uranium, plutonium or thorium. The atomic bombs dropped on Hiroshima and Nagasaki was based on the same principle. Nuclear fusion reactions have so far been out of human reach. Though we have made the H-Bomb or the Super Bomb which works on this, we are unable to control it and put it to better use. The sun gains all its energy from this reaction. Scientists have been trying to replicate that reaction in a controlled manner. India is a member of the seven member group working on a project called ITER (International Thermonuclear Experiment Reactor) working on these lines. The ITER program is anticipated to last almost 30 years and cost over $13billion, which makes it one of the most expensive modern techno scientific mega projects.

There are also other areas of modern day research going on; these include particle physics, nuclear structure, hadron physics, neutrino physics, nuclear astrophysics and so on. All these began as a part of nuclear physics but today they are vast subjects. They are many research facilities working round the clock in these areas. To name a few CERN, KEK, FERMILAB, Argonne, GSI, SLAC, DESY, Brookhaven, Budker INP, JINR and CEA. Every year billions of dollars are being spent on research in these fields. Can't we put the money to better use is a question always raised. Everything we discover has its pros and cons; it is for us to make a judicious use of the available technology.

NEXT