The Lumber Room

"Consign them to dust and damp by way of preserving them"

A theorem by Euler on partitions

with 2 comments

There are so many beautiful facts in mathematics that are not as well known as they deserve to be. [Just today I couldn’t find an online reference for the Robinson-Schensted(-Knuth) correspondence.] Some efforts in the direction of communicating these to an online audience have been collected in the Carnival of Mathematics (41 so far) posts on various blogs. Another good idea I recently found is Theorem of the Day. [EtA: Found at Theorem of the Day: RSK correspondence.]

Anyway… today I attended a lecture on Euler by William Dunham (great talk!) where after a brief biography of Euler and a tour through some of his results, he showed Euler’s proof of a particular theorem about partitions. It will be familiar to anyone who has read about integer partitions, but it deserves to be familiar to everyone! So here is a sketch of the proof, for your reading pleasure. [It doesn’t do justice to present only a “sketch”, but I have assignments due tomorrowtoday… feel free to take it and turn it into some form worthy of the content. :-)]

Now when I say “a theorem by Euler”, it is very ambiguous which one I mean, and even with the “on partitions” restriction, there are several. So let me state it:

The number of partitions of a number into odd parts is the same as the number of partitions of the number into distinct parts.

[If I remember correctly what was narrated in the talk, one of the Bernoullis wrote to Euler asking him a question about partitions, and within a few days (think of the postal system then) Euler replied with a proof of the theorem, along with a apology for the delay caused by the poor eyesight he had recently been suffering from. This is an outline of his proof, ask me about the details.]

Let D(n) denote the number of partitions into distinct parts, and O(n) denote the number of partitions into odd parts. Then we have:
\displaystyle \sum_{n\ge0}D(n)x^n
\displaystyle = (1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)\dots
\displaystyle = \frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^6}{1-x^3}\frac{1-x^8}{1-x^4}\frac{1-x^{10}}{1-x^5}\dots
\displaystyle = \frac{1}{(1-x)(1-x^3)(1-x^5)\dots}
\displaystyle = (1+x+x^{1+1}+\dots)(1+x^3+x^{3+3}+\dots)(1+x^5+x^{5+5}+\dots)
\displaystyle = \sum_{n\ge0}O(n)x^n
which proves the theorem.
The first equality, which gives the generating function for the D(n)s, can be seen as follows: when you “expand” and write out (1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)\dots, you get 1 + x + x^2 + (x^3+xx^2) + (x^4+xx^3) + (x^5+xx^4+x^2x^3) + \dots, where the coefficient of any term x^n is exactly the number of ways of writing x^n as a product of distinct factors of the form x^k, which is D(n). Similarly, the last equality, about the generating function for the O(n)s, is because the coefficient of any term x^n in (1+x+x^{1+1}+\dots)(1+x^3+x^{3+3}+\dots)(1+x^5+x^{5+5}+\dots) is exactly the number of ways of writing n as a product of (not necessarily distinct) x^k for odd k.

The result might not be terribly important, but this idea was the starting point for proving several observations about partitions, and the method has led to the discovery of several facts and is more widely applicable than you think!

If you want a combinatorial proof by bijection (“For Entertainment Only”) here is an outline of one:
Given a partition of n into odd parts, say
n = a_11 + a_33 + a_55 + \dots,
write each a_i “in binary”, by which I mean as a sum of distinct powers of two. So you have
n =  (2^{b_{11}}+2^{b_{12}}+...)1 + (2^{b_{31}}+2^{b_{32}}+...)3 + \dots.
Now just get rid of the brackets, and note that all terms are distinct.
E.g. for 19 = 5+3+3+3+1+1+1+1+1,
i.e. 19 = (1)5 + (2+1)3 + (4+1)1, you get the partition
19 = 5 + 6 + 3 + 4 + 1.
[Exercise: Why are all parts distinct?]

Conversely, given a partition into distinct parts, we can separate the “even part” from the “odd part” in each term, so for example with 19 = 5+6+3+4+1, we write
19 = 5 + (2)3 + 3 + (4)1 + 1, and collect the coefficients of each odd number, so 19= 5 + (2+1)3 + (4+1)1, which was our original odd partition.
[Exercise: Why can’t we do the same thing starting with any partition?]

[Question: Is the bijective proof related to the algebraic one?]

About these ads

Written by S

Wed, 2008-10-15 at 06:26:39 +05:30

Posted in public

Tagged with , ,

2 Responses

Subscribe to comments with RSS.

  1. Hi–

    Even, i loved this. I downloaded the Video given by Prof. Dunham from the Clay Mathematical Institute Website.

    Chandrasekhar

    Tue, 2010-08-03 at 09:20:50 +05:30

    • Glad to hear! I hadn’t noticed the video of the talk (or maybe it wasn’t there the last time I looked), so thanks for mentioning it too. :-)

      S

      Tue, 2010-08-03 at 10:50:26 +05:30


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 75 other followers