A simple problem that led us to Ramanujan’s work on Integer Partitioning

September 12th, 2010 admin Posted in Family, Tidbits, Tutorials | 2 Comments »

Raghu, my cousin, sent me an email with the following problem a few months ago.

Question

Manish was on his way to an interview. On the way, he encountered his long lost cousin, Vijay, whom he hadn’t met in more than a decade. They started catching up on lost time. Manish learned that Vijay had 3 sons. When he asked about their ages, Vijay replied, “You’re going for an interview, right? Consider this a trial question. Figure out their ages from this: The product of the ages of my three sons is 36.” To this, Manish grumbled that he needed more information. Vijay, then, pointed to a sign board across the street that displayed the address of the area and said that the sum of the ages of his three children was equal to the last two digits of the pin code (zip code) of that area. Manish demanded still more information. Finally, Vijay said, “My eldest son wore a black shirt today. This is all I can tell you.”

What were the ages of the three children?

Solution

Say the ages are a, b and c. We know from clue 1 that a.b.c = 36, where “.” represents multiplication. First step in identifying such factors is to factorize 36 into its smallest factors – 1.2.2.3.3. The next step is to figure out how to group these 5 numbers into 3 groups. Note that we can have more 1s in the factorization. For example, what if 2 kids are 1 year old and 1 “kid” is 36 years old? So, to allow that to happen, we need another 1 in the factors. So the factors are 1.1.2.2.3.3. By trial and error, we recognize that the way to make 3 groups from 6 objects is by making groups of:

1 + 1 + 4 (call it Grouping Style 1, or GS1)

1 + 2 + 3 (call it Grouping Style 2, or GS2)

and 2 + 2 + 2 (call it Grouping Style 3, or GS3)

GS1 requires selecting 1 out of 6 for the first component, 1 out of remaining 5 for the second component and the remaining 4 automatically go into the third component. There are 6 ways to choose the first component, 5 ways to choose the second component and 1 way to chose the third component. This gives us a total of 6.5=30 combinations for GS1. Many of these will turn out to be identical. After some work, we can whittle down the GS1 groupings to the following:

1,1,36

1,2,18

1,3,12

2,2,9

2,3,6

3,3,4

GS2 requires selecting 1 out of 6 for the first component, 2 out of 5 for the second component and the remaining 3 automatically go into the third component. There are 6 ways to choose the first component, 5C2 = 10 ways to choose the second component, and 1 way to choose the third component. This gives us a total of 6.10=60 combinations for GS2. In reality it is easier to work it out by trial and error. After some work, and after recognizing and ignoring the combinations that we have already seen under GS1, we can whittle down the GS2 groupings to the following:

1,4,9

1,6,6

Similar analysis for GS3 gives us no new combinations.

Before we can use clue 2, we need to add up the ages in these combinations. Doing so, we get the following:

1+1+36=38

1+2+18=21

1+3+12=16

2+2+9=13

2+3+6=11

3+3+4=10

1+4+9=14

1+6+6=13

Notice that all the combinations give us unique totals, except for two combinations which both give us 13. The fact that the second clue did not suffice to answer the question indicates that the total of the ages must have been 13. The children could be aged (2,2 and 9) or (1,6 and 6). Any other value for the total age and the answer would have been clear after clue 2.

Clue 3 tells us of the existence of an eldest child. The color of the shirt is immaterial. In the (1,6 and 6) combination, there is no eldest child. There are 2 elder children, who are twins. In the (2,2 and 9) combination, there is an eldest child. Hence, that is the answer. The children are aged 2 years, 2 years and 9 years.

Intersecting Ramanujan’s trail

With the specific problem out of the way, let us think about a generalization to the problem. India’s best known mathematician, Srinivasa Ramanujan, hiked (given his genius, he probably breezed) along a mathematical thought process, probably in 1913, leading to his work on Integer Partitions. In attempting to solve this problem, I seem to have unknowingly stepped onto this trail briefly. Let me explain. Remember that we had to figure out how many ways could 6 objects be grouped into 3 groups. I listed these out as groupings with (1,1,4), (1,2,3) and (2,2,2) objects. There are 3 grouping styles possible, no more, no less. But as the number of total objects grows larger, or the number of groups to create changes, the number of such grouping styles are harder to figure out. At least they seem to follow no simple pattern. For example, to group 6 objects into 2 groups, there are also 3 ways – {5,1}, {4,2} and {3,3}. To group 7 objects into 2 groups, there are only 3 groupings – {6,1} and {5,2} and {4,3}. To group 7 objects into 3 groups, however, there are 4 groupings – {1,1,5}, {1,2,4}, {1,3,3}, and {2,2,3}.

The question is, is there a more general formula to figure this (the number of distinct ways to group N objects into G groups) out? And another question is – what is Integer Partitioning and how is that related to this problem?

So before going into the theory, let us try to do look at this problem from different angles, and we may see an opening to solving it. Let us use the following example – find the number of ways of grouping 7 objects into 2 groups. We discovered (through some mental enumerations, I admit) that there are three grouping styles – {6,1}, {5,2}, {4,3} – possible here. But now, let me draw your attention to a simple fact – notice that the sum of the numbers each of the groupings is equal to 7. Hardly a surprise, you say. There were 7 objects to begin with. And regardless of how we group them, the total object count is 7. Big deal! But it is often rewarding to look at problems from a different perspective. We now know that “grouping 7 objects into 2 groups” is essentially the same as “finding 2 positive integers that add up to 7″. How many ways are there to add up 2 positive integers to get a total of 7? 6+1=7 and 5+2=7 and 4+3=7. No more ways to do it. So, the number of ways to group N things into G groups is equal to the number of ways to add G positive integers to make N. Allow me create a short hand notation to identify this count. I will use P(N,G). P for partition, but really you can use any symbol. I think it only makes sense when N>=G. Otherwise P(N,G)=0.

P(N,G) = number of ways to add G positive integers to make N = numbers of ways to divide N objects into G groups

There are a couple of simple properties of P(N,G) which are easy to observe. There is only 1 way to divide N objects into N groups, and that is to assign 1 object per group. Similarly there is 1 way to divide N objects into 1 group, and that is to place all objects into 1 group. Symbolically,

P(N,N) = 1

P(N, 1) = 1

OK, I think we have beaten that one into submission (if not to death).

Note that we have only defined it. We we after a general formula for P(N,G). And we do not have that yet.

Now, let us visualize this slightly differently, meditate upon it a bit, and see if we can uncover some other properties about P(N,G). The following figure shows the objects, and groupings, visually. This style of representation, called, Ferrers Diagrams, uses one dot for one object. And it arranges the dots in each group along a column. There are 3 groupings shown – these are our friends {6,1}, {5,2} and {4, 3}. If we stare at this for some time we realize that the reason there are 2 columns is because we wanted 2 groups. This means there is at least 1 row, the first row, which has 2 dots in each of the groupings. Now, imagine that we remove those two dots from each of the groupings. What are we left with?

The figure below shows the case where the 2 dots in the first row are removed. We are left with 5 dots. But more importantly notice the groupings that are left. {5}, {4,1} and {3,2}. These are some of the ways you can group 5 objects. This time, we do not necessarily group 5 objects into 2 groups – since we have a grouping, {5}, with only 1 group. It may be interesting to see how many ways there are in all to group 5 objects – not necessarily into 1 or 2 groups, but rather into any number of groups.

The following figure shows all the ways to group 5 objects.

1 group – {5}

2 groups – {4,1}, {3,2}

3 groups – {3,1,1}, {2,2,1}

4 groups – {2,1,1,1}

5 groups – {1,1,1,1,1}

Note that the number of ways to group 5 into 1 and 2 groups in this figure exactly matches the 3 groups in the previous figure. That is P(7,2) = P(5,1)+P(5,2)! That is a breakthrough. So maybe there is a way to break down any P(N,G) into smaller and smaller pieces and add up the totals of the smaller pieces. For example, P(N,G) = P(N-G,1)+P(N-G,2)+ … + P(N-G,G). Let’s try this for P(7,2).

P(7,2) = P(5,1) + P(5,2) = 1 + P(3,1) + P(3,2) = 1 + 1 + P(1,1) = 1 + 1 + 1 = 3

Not quite a closed form, but an recursive solution.

Integer Partitioning and a Generating Function for it

By the way, this is a good place to (finally) get into Integer Partitioning. In the figure above we listed out all the ways to group 5 objects. That is the Integer Partitioning of 5. I use P(5) to represent it.

P(5) = P(5,1) + P(5,2) + P(5,3) + P(5,4) + P(5,5)

Though it is possible to use the recursive technique I described above to solve for P(5) term by term, there is a very interesting alternative way to figure it out. It is based on a near mind-bending technique, based on Generating Functions. It is powerful technique, used in many different places. I have not yet been able to pin down if the abstraction involved in using Generating Functions is pure genius or if it simply falls out of the mechanics of mathematics if only you start from the correct perspective. Let me attempt to convey how Generating Functions work in this specific situation.

We want to find out all the possible ways to group N objects. But instead of starting with this specific problem we turn the problem on its head and solve a much more general problem. Let us use a bunch of 1s, a bunch of 2s, a bunch of 3s etc. and see what we can add them up to. We do this exhaustively. That is, we we do not let any combination fall through the cracks. Then, we can count up all the different ways a bunch of addends give us the total N. For example, if N is 5, and we do this exhaustive (but structured) adding of all integers (repetitions allowed) and see how many combinations add to 5. We can be sure that none of the addends will be 6 or greater. Similarly, the number of addends will also be no greater than 5, because each addend is at least 1, and with 5 1s we already are at 5. So, the number of combinations we need to look at only needs to cover the addends 1 through 5, and no more than 5 of those addends.

This exhaustive search seems hard to do. But generating functions provide a structured method to approach this. Let us do it one step at a time. We will look at the potential contributions to the total, of each candidate addend one at a time.  Let us look at the addend 1. What totals can 1 contribute to? 1s can add up to 1 in 1 way, {1}. 1s can add up to 2 in 1 way, {1,1}. 1s can add up to 3 in 1 way {1,1,1} and so on. That is, 1 alone can add up to any N, AND, in only 1 way for each given N. In fact if there is no 1 in the addends, then 1 can contribute 0 to the total. In generating function terms this would be represented as follows:

What? Where did that come from? That is typically, always the reaction in my own mind when I see that. Essentially, the order of , which is k, indicates the total that the addends (remember we are only talking about the addends being 1) add up to. The coefficient of , which is 1, indicates the number of ways the addends can be added up to get to k. There is only 1 way to do this using only 1s. And there may be no 1s in the addends, and that is the term .

But what if 2s are allowed? There can be 1 two, or 2 twos, or 3 twos, etc. Thus the generating function based on contributions only from twos is as follows:

This basically means twos can add up to 0 or 2 or 4 or 6 or 8 etc.

Now, we know that we can have both 1s and 2s in the set of addends. In fact, we can have 1s, and 2s, and 3s, and 4s etc. Let us restrict the addends to 1s and 2s for the time being. There can be 1 one and 1 two, or 1 one and 2 twos or 2 ones and 1 two etc. How do we mathematically express these combinations? This is where the true import of the elegance of generating functions becomes clear. By allowing the contributions of the addends to be in the power of x position, products of and correctly give us the sum in the power’s position, .  Further, if there are multiple ways to add up to a given addend, they show up in the coefficient position. That is, as an example, say we want to figure out the Integer Partitions of any number N, using only the addends 1 and 2, we can multiply the individual addends’ generating polynomials.

This product of infinite polynomials will give us every possible way to add up 1s and 2s to get us to a specific total N. Say N=5, then we know we need not worry about and above in either polynomial.

And after some math, we end up with the necessary coefficient for , and that is the number of ways to get to 5 using only 1s and 2s.

Now, just extending this to allow contributions from the addends 3, 4, 5 etc., we get the full generating function for Integer Partitioning.

P(N) = coefficient of in

Whew! So we have that out of the way. What amazes me no end is how generating functions are able to hijack this polynomial product form to solve (or, more accurately, bring structure to) seemingly impossible scenarios that need counting. Notice that we still do not have a closed form for the Partition of Integers, P(N). Computers can be employed for the multiplication of terms and accumulation of coefficients.

A Closed Form Approximation

In 1918, Srinivasa Ramanujan and his advisor, G. Hardy, came up with a closed form , albeit a closed form for an approximation to P(N). With the current understanding of Integer Partitioning, this seems like an amazing accomplishment. This closed form was:

This produces pretty good approximations. For example, P(100) = 190,569,292, and this closed form approximates it to around 199 million.

References

1. Joseph Laurendi, Partitions of Integers, 2005, http://www.artofproblemsolving.com/Resources/Papers/LaurendiPartitions.pdf

2. Wikipedia, http://en.wikipedia.org/wiki/Partition_%28number_theory%29