Jump to content
BrainDen.com - Brain Teasers
  • 0

Partition Identity


BMAD
 Share

Question

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
Link to comment
Share on other sites

5 answers to this question

Recommended Posts

  • 0

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).
Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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
Link to comment
Share on other sites

  • 0

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)
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...