mixedmath

I was playing with a variant of my Containers of Water question where we were instead interested in solid weights on a scale. It occurred to me that, as is often the case, I should consider easier problems first and see what comes of them. Ultimately, this led me down a path towards the idea of a 'perfect partition' and a few papers published in the late 1800s by MacMahon. Here's how that went:

Consider the vastly easier problem: you have n stones (each of some integer weight) on a balancing scale (a classic balance, so that one kilogram on each side will cause the scale to be 'balanced'). How many different integer weights can you correctly measure with these n stones? Alternately, for each n, what stones maximize the number of weights one can properly measure (for this post, we want to measure the weights $ (1,...,n)$ for some $ n$).

Say for example that you have 2 stones, a 1-stone and a 3-stone (to take from my containers of water notation - this means one weighs 1 kg and the other weighs 3 kg). Then it is possible to measure out 1, 2, 3, and 4 kg on the scale. To measure 1 kg, simply measure against the 1-stone. To measure 2 kg, measure the 1-stone against the 3-stone (i.e. place the 1-stone on one side and the 3-stone on the other, so that 2 kg will balance the scale). 3 and 4 follow.

In one direction, it is very easy to construct maximal sets of stones. Let us distinguish the two sides of the balance so that there is a Load side (where we put weights to weigh against) and a Measure side. In our previous example, we might have (3 in Load ; 1 in Measure) and we can properly measure 2 kg. So we also expect the Load-weight to be greater than the Measure-weight, so that we can actually measure a positive weight (no negative weights here). So if there is exactly 1 stone, we require it to be a 1-stone. Now say we add an n-stone from some n>1: we can get up to 4 different possible measurements. We can see this as follows:

(Load; Measure) (1; 0) , (1, n; 0) , (n; 1) , (n; 0)

In fact, this can be generalized to a recurrence relation. Suppose we have a set S of weights whose total weight is W and which can measure N different measurements. Then by adding a new weight w > W, we can get at most 3N + 1 different measurements.

(Load; Measure)
(S; 0) This has N different measurements corresponding to the assumption
(S, w; 0) This also has N different measurements, except w more than above
(w; S) This also has N different measurements, except w less than the first
(w; 0) This measures only the weight w.

It also turns out that this bound is attainable. Simply start with 1 and add 3, then $ 2*(3+1) + 1 = 9$, and so on. You always add twice the previous total weight plus 1. And it is quickly apparent that this is maximal as there is no overlap. It is cool, though, that this means that with weights of size 1, 3, 9, 27, and 81, one can measure every weight up to 121 kg. And it's unique!

But there is a more interesting question here, closely related to the uniqueness of the measurements up to 121 done with the weights 1, 3, 9, 27, and 81 (or, for a better parallel, the weights 1, 1, 3, 3, 9, 9, 27, 27, 81, and 81 for the weight 242 - actually a perfect partition). And this is the true topic of the day: perfect partitions.

An English mathematician by the name of Percy Alexander MacMahon came up with the idea of a perfect partition in his first paper: Certain Special Partitions of Numbers, published in 1886 in the Quarterly Journal of Mathematics, pg. 367-373. A perfect partition of a number n is a partition whose elements uniquely generate any number in (1, ..., n). For example, (12) is a perfect partition of 3, and (122) is a perfect partition of 5. MacMahon also established quick ways of determining the number of perfect partitions for a number. Unfortunately, as neither the Quarterly Journal of Mathematics nor the collected works of MacMahon (available from MIT Press) were at hand, I found the proofs behind these results to be elusive. Fortunately, Goulden and Jackson's book Combinatorial Enumeration has a key hint in their problem 2.5.12. I present a set of proofs for these very interesting results.

Proof

So consider a number of the form $ p^{\alpha} - 1$, where p is a prime. Note that every number has the trivial perfect partition of units, i.e. any number n has as a perfect partition $ (1 ... 1)$ with n 1's. Note also the relation: $$ \dfrac{1 - x^{p^{\alpha}}}{1-x} = 1 + x + x^2 + x^3 + ... + x^{ {p^\alpha} -1}$$

This relation corresponds to the perfect partition (1 ... 1) with n 1's. But there's more - consider the special case where $ \alpha = 3$. $$ \dfrac{1 - x^{p^3}}{1-x} = \dfrac{1 - x^{p^3}}{1-x^{p^2}} * \dfrac{1-x^{p^2}}{1-x} = 1 + x + x^2 + x^3 + ... + x^{ {p^3} -1}$$ or $$ (1 + x^{p^2} + x^{2(p^2)} + ... + x^{p^3 - p^2})*(1 + x + x^{2} + ... + x^{p^2 - 1})$$ $$ = 1 + x + x^2 + x^3 + ... + x^{ {p^3} -1}. $$

In considering the multiplications of the product, we see that each of the exponents $ 0, 1, 2, ..., p^3 -1$ is the product of a unique set of factors from each term. This is to say that the possible exponents form a perfect partition. So, in this example, from the $ \dfrac{1 - x^{p^3}}{1-x^{p^2}}$ term we take the partition element $ p^2$. How many do we have? We have as many as are possible from the product, which is to say up to p - 1 of them. From the $ \dfrac{1-x^{p^2}}{1-x}$ term, we take the partition element 1 (just as from the trivial example). How many? From the product, we determine there are $ p^2 -1$ of them. So this shows that $ ((p^2)^{p-1} {1}^{p^2 -1})$ is a perfect partition of $ p^3 -1$, where $ 1^{p^2 - 1}$ denotes that there are $ p^2 - 1$ 1's included in the partition (do a quick check - it's perfect, and they add up to $ p^3 -1$.

In fact, each of the factorizations of $ \dfrac{1 - x^{p^3}}{1-x}$ yields a different perfect partition. Here, I show the correspondence. $$ \dfrac{1 - x^{p^3}}{1-x^{p^2}} * \dfrac{1 - x^{p^2}}{1-x^p} * \dfrac{1 - x^{p}}{1-x} \Longleftrightarrow ( (p^2)^{p-1}p^{p-1}1^{p-1})$$ $$ \dfrac{1 - x^{p^3}}{1-x^{p^2}}* \dfrac{1 - x^{p^2}}{1-x} \Longleftrightarrow ((p^2)^{p-1}1^{p^2 -1})$$ $$ \dfrac{1 - x^{p^3}}{1-x^{p}}* \dfrac{1 - x^{p}}{1-x} \Longleftrightarrow (p^{p^2-1}1^{p-1})$$ $$ \dfrac{1 - x^{p^3}}{1-x} \Longleftrightarrow (1^{p^3-1})$$

That strikes me as being pretty cool already, but we aren't done. In each factor, let's note the difference between the difference of the exponent of p on the numerator and denominator. For example, we see $$ \dfrac{1 - x^{p^3}}{1-x^{p^2}} * \dfrac{1 - x^{p^2}}{1-x^p} * \dfrac{1 - x^{p}}{1-x} \mapsto [111]$$ $$ \dfrac{1 - x^{p^3}}{1-x^{p^2}}* \dfrac{1 - x^{p^2}}{1-x} \mapsto [12]$$ and so on. It is quickly apparent that every different factoring yields a different composition of the number 3, and therefore corresponds to a different perfect partition of $ p^3-1$. Of course, this quickly generalizes, so that when we have $ p^{\alpha}-1$, and we write $$ \dfrac{1 - x^{p^{\alpha}}}{1-x^{\beta}} * \dfrac{1 - x^{\beta}}{1-x^{\gamma}} * \dfrac{1 - x^{\gamma}}{1-x}$$ where $ \gamma | \beta, \beta | \alpha$ (and extended for as many factors as necessary in the logical manner).

And this corresponds to a perfect partition and the composition of $ \alpha : [(\alpha - \beta)(\beta - \gamma)(\gamma)]$ (again, extended for as many factors as necessary. Further, it is quickly apparent that each composition $ [\xi _1 \xi _2 ... \xi _k ] $ can be written as $ [ (\alpha - (\alpha - \xi _1))(\alpha - \xi _1 - (\alpha - \xi _1 - \xi _2 )) ...$ {continued on next line}

$ ... (\alpha - ... - \xi _{k-1} - (\alpha - ... - \xi_{k-1} - \xi _k ))]$

which corresponds to the factoring:

$$ \dfrac{1 - x^{p^\alpha}}{1-x^{\alpha - \xi _1}} * \dfrac{1 - x^{p^{\alpha - \xi _1} } }{1-x^{p^{\alpha - \xi _1 - \xi_2} } } $$ $$ *(...) * $$ $$ \dfrac{1 - x^{p^{\alpha - \xi _1 - ... - \xi_k}}}{1-x}$$

Thus there is a bijection between the factorings of $ \dfrac{1 - x^{p^{\alpha}}}{1-x}$ and the perfect partitions of $ p^\alpha -1$, and another with the compositions of the number $ \alpha $. Thus we have proven that the number of perfect partitions of the number $ p^\alpha -1 $ is the same as the number of compositions of the number $ \alpha $. And we are done with this claim!

Leave a comment

Comment via email