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

Viruses, Viruses and Viruses!

“Mannu don’t play in the rain, you will catch cold” calls out Mannu’s mother as he gets drenched in rain. During the rainy season a number of children get diagnosed of ‘Common cold’. Similarly, there is an increase in the number of ‘Chicken pox’ cases during the summer season. The recent outbreak of Swine flu caused havoc throughout the world. All these are human diseases caused by viruses: common cold is caused by Rhinovirus or Coronavirus, chicken pox by Varicella-Zoster virus and swine flu by H1N1 virus. It is known that viruses are unable to grow and reproduce outside a host i.e. they are non living outside the body of a living organism, then how can they spread and survive in the atmosphere? Scientists, till date, debate whether viruses are living or non living. Such a simple question could not be answered yet, as it raises a fundamental question - what defines life?

So before we get on with finding out the answer to that simple question, let us see what these viruses are made of. ‘Virus’ is Latin word for ‘Poison’. They are well established as parasites of living beings. They are much smaller than even bacteria and their size ranges from 20nm to 300nm (1nm = 10-9m; cannot be seen using a microscope!). A virus simply consists of a core of nucleic acid (DNA or RNA) enclosed within a protein coat called Capsid. Some viruses have an extra covering made of lipid membrane called Envelope (e.g. HIV- which causes AIDS), but they do not have any machinery for carrying out metabolic activities. Even the simplest and most primitive unicellular organism, the Blue Green algae (also known as Cyanobacteria, 2.8 billion years old fossil samples have been found!), contain protoplasm with membrane bound organelles participating in energy consuming processes. Viruses replicate themselves by utilizing the host cell machinery in a sequence of stages (consisting of adsorption, penetration, uncoating, nucleic acid replication, maturation and release). During Adsorption , the whole virus lands and fixes itself on to the surface of the host cell. This is followed by Penetration in which the Nucleic acid of virus alone enters in to the host cell leaving the protein coat behind. Once inside the cell, the viral genome (nucleic acid) integrates itself with the host cell genome and as the host carries out its normal round of replication, unaware of the presence of viral genome, replicates the viral genes too. These viral genes which code for viral proteins get expressed and result in the formation of many new virus particles. The viruses taken together have genes to counter attack every known form of immune response against them by the host. This is how a virus propagates itself. While outside a host cell it remains dormant waiting to come in to contact with living cell. Air borne viruses like the cold virus remain alive only up to 3 hours outside human body, after which they cannot replicate themselves even when in contact with host.

A virus seems to be on the verge of life, similar to a seed i.e. it looks dead but possesses a certain potential for life. Viruses also have been known to constantly evolve themselves as seen by emergence of new viruses like Swine flu etc. The Eighth report of the International Committee on Taxonomy of Viruses (Taxonomy is the science of classification) reports existence of more than 5450 viruses belonging to more than 2000 species. These viruses infect all type of cells, ranging from bacteria (they are called Bacteriophages) to blue green algae (Cyanophages) and also human beings. A recent report shows that marine viruses help in increasing efficiency of photosynthesis in blue green algae, contributing up to 5% of total world’s oxygen. Apart from this various other genes of viral origin are identified in human beings too, indicating that viruses play a major role in evolution of life on earth. Thus in a way they control life on earth by determining the survival of their hosts. These so called non living beings are closely intertwined in the web of life making them immensely powerful.

Coursing through the Cell

Peeking into a cell using an electron microscope you can see many compartments which are called organelles. Each of these organelles is a mini factory producing goods required for the happy functioning of the cell. Each one of them manufactures unique products (proteins, RNAs, sugars etc) that are distributed to others either to be utilized or to be processed further. To ensure safe and timely transport of these precious consumables, the cell uses a very intricate rail system consisting of five specially designed protein molecules, two of which, called actin filament and microtubule, act as the railroads, and the rest three as the goods carriers.

Like the local trains connecting places across the city, all the regions in the cell are interconnected by actin filaments which are randomly distributed throughout the cell. The cargo in this network is transported by the motor protein called myosin (one of the goods carriers) to their respective destinations. This line connects even places where the second type of rail road, the microtubules, is unable to access. Microtubules are like the interstate expresses connecting only selected places and unlike actin, microtubules are more neatly organized. Kinesins and dyneins use this route for delivering the cargo. Kinesin mediated transport generally is used to bring cargo to cell’s periphery and dyneins ,towards the cell’s interior. All of these motors are powered by ATP (adenosine triphosphate, an energy rich molecule produced by the cells).

Each of these motors, although different in structural and functional details, share some common features. They all have heads and a tail connected by a central region called stalk. They carry their goods by their tails and hold on to the rail (actin filament or microtubules as the case may be) using their heads. On their heads is also the region where ATP can bind and gets hydrolyzed to give the energy for moving the motor.



Myosin keeps a 10nm step for every single ATP used (nearly 3.048 x 10-9 times your step size), Kinesin and dynein have a 8nm step size.(remember the late Michael Jackson doing his famous moon walk , nearly that’s how the motors look when they move along the rail). Check out these videos to watch myosin and kinesin on the move:

http://www.youtube.com/watch?v=686qX5yzksU
http://www.youtube.com/watch?v=vJ9ffKeUCvE&NR=1

Among the three goods carriers, myosin and kinesin give better performance than dynein . The amount of ATP in the cell affects the working efficiency of dynein, whereas kinesin and myosin are independent of this factor. Moreover dynein’s step size also varies with the load its carrying and availability of ATP. Dynein also tends to take backsteps even in the absence of a load. But it overcomes these drawbacks and comes in par with myosin and kinesin by making use of additional proteins such as dynactin which are like the additional engines that provide the extra force and support to a goods carrier travelling in hilly regions.

It has been observed that all of these carriers work together and sometimes also help each other carry the heavy load, especially dyneins almost always teams up and work together. Given that both the railroads are such a busy network, how is the traffic on the lines regulated? It may not be such a great trouble on actin filament line as it’s only the myosin using the route and also these lines are more numerous. But when it comes to microtubule, two different goods carrier (kinesin and dynein) use the same line! To add to the problem these two carriers move in different directions. Although not much is known as to how traffic jams on a single line are avoided, it is clear that dyneins can avoid traffic by changing tracks.If a kinesin and a dynein happen to take the same line, kinesin being a lean and mean machine forces dynein to change its track.

All this said about the cell’s railway system, three important questions remain unanswered as yet; how does the goods carrier know its destination? And how are head on collisions prevented (Accidents don’t occur in healthy cells)? While functioning together how do they co-ordinate with each other (ensuring that the cargo doesn’t get lost and that ATP doesn’t get wasted)? With the amount of active research going on in this field we can hope to have the complete understanding of the cell’s railway system soon.

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