Author |
Topic: Partitions (Read 1377 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
Given a natural number n, a partition P of n is a nondecreasing sequence (a1, ... , ak) of strictly positive integers such that the sum of its terms is n. For instance, the partitions of 4 are:
(1,1,1,1), (1,1,2), (1,3), (2,2), (4). (Hope I didn't forget any  )
Given a particular partition P of n, let A(P) be the number of 1's to appear in P, and let B(P) be the number of distinct elements of P. So A(1,1,1,1) = 4 and B(1,1,1,1) = 1. Prove that, for all n,
sum A(P) = sum B(P)
where the sum extends over all partitions of n. (For n = 4, both sums are equal to 7, for example)
|
| « Last Edit: Nov 7th, 2002, 8:48am by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
 |
Re: NEW PUZZLE: PARTITIONS
« Reply #1 on: Oct 5th, 2002, 1:28pm » |
 Quote  Modify
|
This is a GREAT puzzle!
I'm attacking it using Ferrers diagrams? Could this be a fruitful approach?
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE: PARTITIONS
« Reply #2 on: Oct 5th, 2002, 3:34pm » |
Quote Modify
|
Well, finally someone shows some interest!!! I was beginning to think this problem was too boring for you guys.
I'm not too sure how to solve it with Ferrers diagrams; my approach was different. Would you care to detail your method? And are there any non-obvious results about partitions that Ferrers diagrams give easy proofs to? I'm really not that familiar with them.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: PARTITIONS
« Reply #3 on: Oct 7th, 2002, 11:47am » |
Quote Modify
|
Here's a weird sort of proof. Image each partition as a series of stacks of square blocks. Here's a couple examples (using round blocks, which ironically don't stack in real life), for n = 13:
00
00
00
000
0000
5521 = "X"
0
00
00000
00000
43222 = "Y"
You can see that each series of stacks has a non-increasing property (each stack is at least as big as the next stack). You can also see that you can "rotate" each partition, to make a complementary partition. We'll say that complementary partition of X is X'.
Notice that Y=X' in the above diagrams.
Now notice that A(X) = B(X').
This inversion process is one-to-one, and the result can be the same as the initial partition only if A(X) = B(X).
Furthermore, if a partition X is included for a number n, then so is X'.
To sum up:
1) Take all the partitions P of n, and calculate sum A(P).
2) Now complement them all. You know that sum B(P') = sum A(P)
3) But the set P' is the same as the set P, so sum B(P) = sum A(P)
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: NEW PUZZLE: PARTITIONS
« Reply #4 on: Oct 8th, 2002, 4:22am » |
Quote Modify
|
on Oct 7th, 2002, 11:47am, James Fingas wrote:You can also see that you can "rotate" each partition, to make a complementary partition. We'll say that complementary partition of X is X'.
Notice that Y=X' in the above diagrams.
Now notice that A(X) = B(X').
|
|
Maybe I misunderstand you or the definition of A or B, but isn't A(X) = 1, B(X') = B(Y) = 3 ?
I think that A(X) is the difference between the largest and the second largest element in X'. Haven't had time yet to consider what B(X) maps to when you rotate X though.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: PARTITIONS
« Reply #5 on: Oct 8th, 2002, 11:34am » |
Quote Modify
|
You're right. I posted that on too little sleep. If you consider C(P) = the largest element in the partition, and D(P) = the number of elements in the partition, then my proof is okay, but it doesn't have much to do with this question.
After thinking about the problem harder, I don't think there can be any proof as simple as this for A(P) and B(P).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE: PARTITIONS
« Reply #6 on: Oct 8th, 2002, 11:50am » |
Quote Modify
|
The rotating idea is really good, even though it does not help much in this case. I'm sure it could help give a simple proof of a variety of results.
I'm trying REALLY hard not to give hints on this one - I know just how hard it is not to read them.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: PARTITIONS
« Reply #7 on: Oct 8th, 2002, 12:52pm » |
Quote Modify
|
I have been examining the problem, and I have come to the conclusion that your solution is by induction on n. However, I don't yet know what the solution is.
The reason I say this is that the number of unique partitions as a function of n is: 1,2,3,5,7,11, ..., and the number of 1s as a function of n is: 1,2,4,7,12,19,30, .... You can see that the increase in the number of 1s is equal to the number of partitions.
This makes intuitive sense: when you increase n by one, you add 1s in only one way: by tacking a 1 on the end of every partition. Tacking a 1 on the end is a one-to-one modification. Now all I have to show is that the number of unique elements in the partitions grows in the same way.
|
| « Last Edit: Oct 9th, 2002, 10:35am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: PARTITIONS
« Reply #8 on: Oct 9th, 2002, 6:28am » |
Quote Modify
|
I have finally solved the problem! It was pretty tough, so good work, Pietro!
I'm going to introduce some new notation:
An = sum of A(P) (over all unique partitions P of n)
Bn = sum of B(P) (over all unique partitions P of n)
Qn = the number of unique partitions of n (think 'quantity') (I could have picked N for this, but I decided not to)
The start of my solution came by examining how you actually take the inductive step from n to n+1.
My first realization was that the partitions of n+1 aren't really very unique. In fact, all of these partitions share a lot in common with the partitions of n. Looking at this partition of 3,
0
00
21
It is similar to both of the partitions of 2:
0
0
2
00
11
All you do is add a single block (I'm still using those darned round blocks) to the partitions of 2, and you get a partition of 3. However, you can't add the block just willy-nilly--you must follow certain rules. Consider the following partition, P:
0
00
00
00000
00000
00000000
65333111
It consists of a series of "stair steps". You are only allowed to add new blocks on the inside corners of the stairsteps (I'll mark these locations with X)
X
0X
00
00X
00000
00000X
00000000X
65333111
If you add a block in any other place, you don't get a valid partition with n+1 blocks. Now I realized the following: the number of stairsteps in a partition P is equal to B(P). The number of blocks you can add is equal to B(P) + 1.
Now I looked at the problem in reverse. How do you go from n to n-1? You just take away blocks! You have to take them away from the outside corners of the stairsteps. I will now mark the blocks that you can take away with 'o'.
o
0o
00
0000o
00000
0000000o
You'll notice that you can take away exactly B(P) blocks.
Next, I tried to consider how many stair-steps you end up with, depending on which block you add or take away, but this problem is very complicated. Sometimes, adding a block adds a stairstep, but sometimes it doesn't, and sometimes it removes a stairstep. Looking at P above, you can see all these possibilities. Consideration of the partitions one at a time is very difficult.
However, you will notice that every block that you can add will become the outside corner of a stairstep. Therefore, for every possible transition from a partition of n to a partition of n+1, there is exactly one corresponding transition from a partition of n+1 back to the partition of n. When you sum up these possible transitions, you get:
sum (possibilities going forward from n) = sum (possibilities going backwards from n+1)
sumn (B(P) + 1) = sumn+1 (B(P))
Bn + Qn = Bn+1
But this is exactly what I wanted to prove! (see my last post) We know that:
An + Qn = An+1
And it is easy to see that:
A1 = B1
If we assume the inductive hypothesis, then the answer falls right out:
An = Bn
An + Qn = Bn + Qn
An+1 = Bn+1
QED
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE: PARTITIONS
« Reply #9 on: Oct 9th, 2002, 11:13am » |
Quote Modify
|
Well, good job! Such smart people on this forum!
My proof was direct, with just some overtones of induction; the proof for n involves mention of n-1, but no induction hypothesis. It's good to see a different proof, especially one so ingenious! Mine is as follows.
To keep things short, let S be the set of all partitions of n, and let Q(n) be as James's (i.e. Q(n) is the cardinality of S). Defining Q(0) = 1, the sum of A(P) over S is clearly equal to the sum of Q from 0 to n-1; because exactly Q(n-i) members of S have i 1's or more - they are of the form
(1, ... , 1, P(n-i)), where P(n-i) is any partition of n-i.
So, when you sum the Q's, you count those P's in S with i 1's exactly i times, giving the previously stated result. This is the result that got me started, and, I thought, the easier to come up with first.
Now, another way to look at the sum of B(P) over S is the following: count the number of partitions in which a number i appears, and sum those results over i. With that in mind, it is easily seen that i appears in Q(n-i) partitions; because, if
a1 + ... + i + ... + ak = n,
then
a1 + ... + ak = n-i,
and vice-versa.
The degenerate case i = n is taken care of by our previous definition of Q(0). Hence, the sum of B(P) over S is also equal to the sum of Q from 0 to n-1, and we have
sum A(P) = sum B(P).
Quod erat demonstrandum.
|
| « Last Edit: Oct 9th, 2002, 11:20am by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print