# Thread: partition of an integer

1. ## partition of an integer

Suppose $\displaystyle d,n \in N$ with $\displaystyle n \leq d$. Then find the number of ways in which $\displaystyle d=r_1+ \cdots + r_k$ with $\displaystyle r_1,...,r_k \in N \cup \{0\}$ and $\displaystyle r_i \leq n$ for all $\displaystyle i=1,\ldots ,k$

2. ## Rougher problem than it looks...

You do realize that the partition function P(n), the number of ways a natural number n can be partitioned as the sum of smaller numbers, is given by Hardy and Ramanujan's complicated formula:

$\displaystyle P(n)=\frac1{\pi\sqrt2}\sum_{k=0}^\infty A_k(n)\sqrt{k}\frac d{dn}\left[\frac{\sinh\left(\frac\pi{k}\sqrt{\frac23(n-\frac1{24})}\right)}{\sqrt{n-\frac1{24}}}\right]$

where $\displaystyle A_k(n)=\sum_{h=1}^k\delta_{gcd(h,k),1}exp\left[\pi i\sum_{j=1}^{k-1}\frac{j}k\left(\frac{hj}{k}-\lfloor\frac{hj}{k}\rfloor-\frac12\right)-\frac{2\pi i h n}{k}\right]$

Are you attempting to place an upper limit on the highest addend $\displaystyle r_i$ in effort to simplify this formula? Or do you seek an algorithmic solution?

3. ## problem with additional constraints

In P(d) there is no restriction on the number of $\displaystyle r_i's$.
But in my question each partition of $\displaystyle d$ must have exactly $\displaystyle n$ values (including repetitions) and all those partitioned values ($\displaystyle r_i's$) must be $\displaystyle \leq n$.

Is there any formula for such a case ?

4. Originally Posted by thippli In P(d) there is no restriction on the number of $\displaystyle r_i's$.
But in my question each partition of $\displaystyle d$ must have exactly $\displaystyle n$ values (including repetitions) and all those partitioned values ($\displaystyle r_i's$) must be $\displaystyle \leq n$.

Is there any formula for such a case ?
I've derived a formula (unless I've made an embarrassing mistake) ... but it is not nice ( beware, for it may cause irreversible damage in you )
Spoiler:

$\displaystyle \sum\limits_{1 \leqslant k \leqslant d} {\sum\limits_{j \geqslant 0} {\binom{k}{j}\left( { - 1} \right)^j \binom{k+d-j\cdot {(n+1)}-1}{k-1}} }$

Sketch of the Proof:
Spoiler:

Our solution is the coefficient of $\displaystyle x^d$ in the following polynomial: $\displaystyle \sum\limits_{1 \leqslant k \leqslant d} {\left( {1 + x + ... + x^n } \right)^k } = \sum\limits_{1 \leqslant k \leqslant d} {\left( {\tfrac{{1 - x^{n + 1} }} {{1 - x}}} \right)^k } = \sum\limits_{1 \leqslant k \leqslant d} {\left( {\tfrac{1} {{1 - x}}} \right)^k \left( {1 - x^{n + 1} } \right)^k }$
Now write both, $\displaystyle {\left( {\tfrac{1} {{1 - x}}} \right)^k }$ and $\displaystyle {\left( {1 - x^{n + 1} } \right)^k }$ as power series and multiply them and pick the coefficient of $\displaystyle x^d$. Then sum over $\displaystyle k$

integer, partition 