which is an analytic version of the fact that every integer is uniquely a sum of distinct powers of 2. What I

*didn't*realize at the time, but learned from George Andrews article Euler's "De Partitio Numerorum", in the current issue (Vol. 44, No. 4) of the

*Bulletin of the American Mathematical Society*, is that this is due to Euler. This is hardly surprising, though, as Euler was as far as I know the first person to apply generating functions to partitions. (The result was known before that; it's the generating-function statement that's due to Euler.)

But here's one I didn't know:

This is an analytic version of the fact that every integer is uniquely a sum of distinct powers of 3 and their negatives, and is Theorem 4 of the Andrews paper. For example, 1 = 1, 2 = 3-1, 3 = 3, 4 = 3+1, 5 = 9-3+1, 6 = 9-3, 7 = 9-3+1, and so on.

To see this fact combinatorially, note that we can make 3

^{k}sums out of the numbers 3

^{0}, 3

^{1}, ..., 3

^{k-1}; for each of these we include the number, its negative, or neither. If we can show that these are the distinct integers from -l to l, where l = (3

^{k}-1)/2, then that's enough. (For example, when k = 2, we have l = 4, and the nine possible sums of 1, 3, and their negatives are

-3-1, -3, -3+1, -1, 0, 1, 3-1, 3, 3+1

where "0" denotes the empty sum. These are just the integers from -4 to 4.)

But this can be shown by induction on k. Clearly it's true for k = 0. Then, for the induction, consider the 3

^{k}sums of the powers of three up to 3

^{k-1}and their negatives; by the inductive hypothesis these are just the integers in the interval . Now consider the 3

^{k+1}sums of the powers of three up to 3

^{k}and their negatives. There are 3

^{k}of these which are just the ones which don't include 3

^{k}. Those that include +3

^{k}add up to , and those which include -3

^{k}add up to . These three intervals put together are , as desired. (For example, when k=2, these three intervals are [-4, 4], [5, 13], and [-13, -5], which together make up [-13, 13].) By induction, we can make each integer in uniquely as a sum of distinct powers of 3 which are less than 3

^{k}and their negatives, which is essentially the desired result.

The last section of the article talks about partitions with some negative parts, or "signed partitions". For example, 9+8-6-5 is a signed partition of 6. These are a bit more awkward to work with in terms of generating functions -- the generating function above about the powers of 3 doesn't converge, ever! So it's basically a curiosity, but one can actually prove things about these signed partitions using generating functions; see the article for examples.

## No comments:

Post a Comment