Partition Identity

[BMAD]

A partition of a positive integer n is a way if writing n as a sum of positive integers, ignoring the order of the summands. For example, a partition of 7 is 3 + 2 + 1 + 1.

The table below shows all partitions of 5. The number of 1s column shows how many times the number 1 occurs in each partition. The number of distinct parts column shows how many distinct numbers occur in each partition. The sum for each column, over all the partitions of 5, is shown at the foot of the table.

(attached)

Let a(n) be the number of 1s in all the partitions of n. Let b(n) be the sum, over all partitions of n, of the number of distinct parts. The above table demonstrates that a(5) = b(5).
Show that, for all n, a(n) = b(n).

Edited February 25, 2013 by BMAD

[BMAD]

Let p(n) be the number of partitions of n. So, for example, p(5) = 7. Establish the following two results, for 1 i n−1.

1. The number of partitions of n which have at least i 1s is p(n − i).
2. The number of partitions of n in which i appears is p(n − i).
   

[witzar]

I think I can show that

a(n) = p(0) + p(1) + ... + p(n-1)

and

b(n) = p(0) + p(1) + ... + p(n-1),

where p(n) stands for number of partitions of n (assuming p(0)=1).

I accomplish both things by using partitions of n to construct and count partitions of k<n, with two different approaches.

I will provide details in my next post.

[phil1882]

8               0 1

7 1             1 2

6 2             0 2

6 1 1           2 2

5 3             0 2

5 2 1           1 3

5 1 1 1         3 2

4 4             0 1

4 3 1           1 3

4 2 2           0 2

4 2 1 1         2 3

4 1 1 1 1       4 2

3 3 2           0 2

3 3 1 1         2 2

3 2 1 1 1       3 3

3 1 1 1 1 1     5 2

2 2 2 2         0 1

2 2 2 1 1       2 2

2 2 1 1 1 1     4 2

2 1 1 1 1 1 1   6 2

1 1 1 1 1 1 1 1 8 1

               44 42

[witzar]

8               0 1

7 1             1 2

6 2             0 2

6 1 1           2 2

5 3             0 2

5 2 1           1 3

5 1 1 1         3 2

4 4             0 1

4 3 1           1 3

4 2 2           0 2

4 2 1 1         2 3

4 1 1 1 1       4 2

3 3 2           0 2

3 3 1 1         2 2

3 2 1 1 1       3 3

3 1 1 1 1 1     5 2

2 2 2 2         0 1

2 2 2 1 1       2 2

2 2 1 1 1 1     4 2

2 1 1 1 1 1 1   6 2

1 1 1 1 1 1 1 1 8 1

               44 42

You've just missed one partition:

{3, 2, 2, 1}    1 3 

So a(8)=b(8)=45.

Edited April 3, 2013 by witzar

[witzar]

I. We can construct partition of (n-1) from partition of n by decreasing one of the parts by 1 (if decreased part equals 1 it vanishes). Let's do it for each different part of every partition of n. We will get all partitions of (n-1), but there will be repetitions. Each partition of n produces as many partitions of (n-1) as it has different parts, so we have produced b(n) partitions of (n-1). From the other hand, each partition of (n-1) was produced as many times as it has different parts plus one, therefore:

b(n) = b(n-1) + p(n-1)
This shows, that
b(n) = p(n-1) + p(n-2) + ... + p(0)

II. Let's write all partitions of n in a column. For each partition that has at least one "1" let's rewrite it skipping one "1", right next to original partition. Newly written partitions form second column. Observe, that second column contains each partition of (n-1) exactly once. We repeat the process for second column obtaining partitions of (n-2) in third column, etc.
Not counting first column we have written p(n-1) + p(n-2) + ... + p(0) partitions. From the other hand, each row not counting first partition contains as many partitions as the first partition in the row has ones, so not counting first column we have written a(n) partitions. This proves, that
a(n) = p(n-1) + p(n-2) + ... + p(0)