Author 
Topic: Partitions (Read 1356 times) 

Pietro K.C.
Full Member
Gender:
Posts: 213


Partitions
« on: Sep 14^{th}, 2002, 8:13pm » 
Quote Modify

Given a natural number n, a partition P of n is a nondecreasing sequence (a_{1}, ... , a_{k}) 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 7^{th}, 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 5^{th}, 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 5^{th}, 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 nonobvious 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 7^{th}, 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 nonincreasing 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 onetoone, 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 8^{th}, 2002, 4:22am » 
Quote Modify

on Oct 7^{th}, 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 8^{th}, 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 8^{th}, 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 8^{th}, 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 onetoone 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 9^{th}, 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 9^{th}, 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: A_{n} = sum of A(P) (over all unique partitions P of n) B_{n} = sum of B(P) (over all unique partitions P of n) Q_{n} = 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 willynillyyou 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 n1? 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 stairsteps 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) sum_{n} (B(P) + 1) = sum_{n+1} (B(P)) B_{n} + Q_{n} = B_{n+1} But this is exactly what I wanted to prove! (see my last post) We know that: A_{n} + Q_{n} = A_{n+1} And it is easy to see that: A_{1} = B_{1} If we assume the inductive hypothesis, then the answer falls right out: A_{n} = B_{n} A_{n} + Q_{n} = B_{n} + Q_{n} A_{n+1} = B_{n+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 9^{th}, 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 n1, 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 n1; because exactly Q(ni) members of S have i 1's or more  they are of the form (1, ... , 1, P(ni)), where P(ni) is any partition of ni. 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(ni) partitions; because, if a_{1} + ... + i + ... + a_{k} = n, then a_{1} + ... + a_{k} = ni, and viceversa. 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 n1, and we have sum A(P) = sum B(P). Quod erat demonstrandum.

« Last Edit: Oct 9^{th}, 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)



