0
$\begingroup$

I guess that the following was solved sometime in the 18th century, but could not find a reference to it. I am interested in approximations to the following integer partition problem:

Denote $R(N,L)$ as the number of ways to write an integer L as a sum (might be empty) of distinct positive integers in the range [1..N] (where order is unimportant). Formally

$R(N,L) = \sum_{ \{\sigma_n\}_{n=1}^{N} } I\left( \sum_{n=1}^N \sigma_n n = L \right) $

I know that $R(N,L)$ satisfies

$R(N,L) = R(N-1,L) + R(N-1,L-N)$,

and $R(N,0)=1$ for all $N$.

In addition, I know that it has several entries in Sloane's OEIS, for instance A053632 (https://oeis.org/A053632), as the coefficients of the product $\prod_{n=1}^N (1+x^n)$.

What I am looking for is some simple expression which approximates it for large enough $N$ (but finite!). From playing with it in Matlab I found that

$R(N,L) \approx A\times 2^{\sqrt{\sin \left( \frac{2\pi L}{N(N+1)} \right)} }$

But I am not sure what $A$ is, whether this is really the asymptotic for large $N$, and what is the finite $N$ corrections.

If anyway has a clue, I will be grateful.

Many thanks,

Amir Bar

$\endgroup$
2
  • 1
    $\begingroup$ How are large $N$ and $L$ related? $\endgroup$ Jun 22, 2015 at 15:13
  • 1
    $\begingroup$ $R(n,n)$ is the number of partitions of $n$ into distinct parts. This is tabulated at oeis.org/A000009 where there are many references and also asymptotics. $\endgroup$ Jun 23, 2015 at 0:11

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.