• 0

Partition Identity

Question

Posted (edited) · Report post

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).

post-53485-0-68580100-1361808500_thumb.p

Edited by BMAD
0

Share this post


Link to post
Share on other sites

5 answers to this question

  • 0

Posted · Report post

Let p(n) be the number of partitions of n. So, for example, p(5) = 7. Establish the following two results, for 1 le.gif i le.gif 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).
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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 by witzar
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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)
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.