1
$\begingroup$

I am attempting to determine the generating function for the number of partitions of n into k-distinct parts all having a largest part y. My attempt is below. It appears to work for all cases I am interested in but then I tried a very simple case involving a reasonably large expansion (using mathematica) and odd things (pun intended) occurred. I’m assuming I’m wrong. A pointer would be helpful.

let $n={{y}_{1}}+{{y}_{2}}+...+{{y}_{k}}$ such that all the y’s are distinct and ${{y}_{1}}>{{y}_{2}}>...>{{y}_{k}}$. This implies ${{y}_{k}}\ge 1,{{y}_{k-1}}\ge 2,...,{{y}_{2}}\ge k-1,{{y}_{1}}\ge k$. Now we assume ${{y}_{1}}$is known. We have then $n-{{y}_{1}}={{y}_{2}}+...+{{y}_{k}}$. Write this as,

$n-{{y}_{1}}=\left( {{z}_{2}}+k-1 \right)+...+\left( {{z}_{k}}+1 \right)={{z}_{2}}+{{z}_{3}}+..+{{z}_{k}}+\frac{1}{2}k\left( k-1 \right)$

Or

$n-{{y}_{1}}-\frac{1}{2}k\left( k-1 \right)={{z}_{2}}+...+{{z}_{k}}$

this is a partition of a number into at most k-1 terms. Hence

$\sum\limits_{n=0}^{\infty }{Q\left( n,k,y \right){{x}^{n}}}=\frac{{{x}^{\frac{1}{2}k\left( k-1 \right)+y}}}{\left( 1-x \right)\left( 1-{{x}^{2}} \right)...\left( 1-{{x}^{k-1}} \right)}$

Where Q here represents the number of ways of partitioning n into k distinct parts all with largest part y. For example consider partitioning n=16 into k=3 distinct parts, all of which contain y=10 as the largest part. There are three partitions of 16 into three parts with 10 being the largest part, namely (10,5,1),(10,4,2),(10,3,3). Hence there are two partitions that are distinct. And from the above (mathematica)…

$\frac{{{x}^{13}}}{\left( 1-x \right)\left( 1-{{x}^{2}} \right)}={{x}^{13}}+{{x}^{14}}+2{{x}^{15}}+2{{x}^{16}}+3{{x}^{17}}+O{{[x]}^{18}}$

Hence Q(16,3,10)=2 (yay!). Lots of other very specific cases work as well. However consider the very simple counting exercise of n=125,k=3,y=50, of which there are 12 distinct partitions. Mathematica, however, yeilds

$\frac{{{x}^{53}}}{\left( 1-x \right)\left( 1-{{x}^{2}} \right)}=...37{{x}^{125}}+O{{[x]}^{126}}$

Wtf?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.