# Thread: partition of an integer

1. ## partition of an integer

Suppose $d,n \in N$ with $n \leq d$. Then find the number of ways in which $d=r_1+ \cdots + r_k$ with $r_1,...,r_k \in N \cup \{0\}$ and $r_i \leq n$ for all $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:

$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 $

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 $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 $r_i's$.
But in my question each partition of $d$ must have exactly $n$ values (including repetitions) and all those partitioned values ( $r_i's$) must be $\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 $r_i's$.
But in my question each partition of $d$ must have exactly $n$ values (including repetitions) and all those partitioned values ( $r_i's$) must be $\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:

$
\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 $x^d$ in the following polynomial: $
\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, $
{\left( {\tfrac{1}
{{1 - x}}} \right)^k }
$
and $
{\left( {1 - x^{n + 1} } \right)^k }
$
as power series and multiply them and pick the coefficient of $x^d$. Then sum over $k$