integer partition problem

A triangle with integer sides and perimeter n is in one to one correspondence with the solutions of the equation

x+y+z = n

with x,y,z being positive integers, x=<y=<z, x+y>z.

Replacing x by x-1, y by y-1, z by z-1, this is the same as the solutions of

x+y+z = n-3

with x,y,z =>0, x=<y=<z, x+y= >z.

We construct a bijection of these set of solutions to partitions of n-3 into 2,3,4 by a Ferrer graph as follows:

given a solution x,y,z as above, draw a Ferrer graph with the first row having z dots, the second row having y dots, and the third row having x dots.

cut the tail of the first row so that the first two rows have the same lenght. Place the tail part on the fourth row.

Flip this graph, we get a partition of n-3 into 2,3,4.

Conversely, starting with a partition of n-3 into 2,3,4, we can reverse the above process (ie, flip the graph and attach the fourth row to the end of the first row) and get a solution of x+y+z=n-3.

It is obvious that x,y,z => 0, and x=<y=<z. Also, before combining the 1st and the 4th row, the first two row are the same and the 4th row is shorter than or equal to the 3rd row. Therefore, we see that x+y => z. Hence this solution satisfies the required conditions.

These two process are inverse of each other. Hence, the process is indeed a bijection.

Therefore the two numbers in the question are equal.

2009-03-05 18:09:45 補充：

用算式表達，partition of n-3 into parts of 2,3,4 is a nonnegative soluiton of

4a+3b+2c=n-3.

Then we can construct the bijection between {(x,y,z)} and {(a,b,c)} as

x=b+c, y=a+b+c, z=2a+b+c.

It is easy to check that it is a well defined bijection

腸胃健康

我做文職, 133磅, 用咗簡單經濟既方法!減左22磅,改善頭痛,胃痛,暈車浪, 靜脈曲脹

我個女14歲由小到大肥胖, 三個月減20磅.改善鼻敏感, 流鼻血, 讀書仲好咗, 仲拿第一添.

營養蛋白素

一杯營養代餐相當於33種蔬菜, 6種水果,內含200多種營養素,

蛋白素相等於5錢燕窩、2份蔬菜、1份水果、1塊牛扒同半杯鮮奶！

濃縮蘆薈汁

功能 :

促進體內的自我潔淨功能，令消化系統更健康

紓緩消化系統壓力

維護消化系統功能正常運作，確保腸胃的潔淨

清除體內毒素。

增強免疫功能。

對抗炎症，消炎止痛。

促進傷口愈合。

健康新文化www.HealthComeTrue.com/life