3
$\begingroup$

we know that the number of integer solutions for the following equation with integers $m, r$:

$\begin{equation} z_1 + \cdots + z_m = 2m, \quad 1 \leq z_i \leq r \end{equation}$

is $N = \binom{2m-1}{m-1} - \binom{m}{1} \binom{2m-r-1}{m-1} + \binom{m}{2} \binom{2m-2r-1}{m-1} - \binom{m}{3} \binom{2m-3r-1}{m-1}+ \binom{m}{4} \binom{2m-4r-1}{m-1}- \cdots$

I am interesting in the asymptotic behavior of $N$ when $m$ goes to infinity. My first try is to derive a upper bound for $N$, but I do not know how to do that. Can anyone give me some hints?

$\endgroup$
3
  • 2
    $\begingroup$ To get bounds and asymptotics on the sequence $N(m)$ it is much easier to work with its generating function. Check e.g. Richard Stanley's Enumerative Combinatorics $\endgroup$ Commented May 13, 2021 at 5:14
  • $\begingroup$ Thanks, I tried this method, it remains to bound the coefficient of $x^m$ on $\left(1+x+\cdots+x^{r-1}\right)^m$ $\endgroup$
    – fs l
    Commented May 13, 2021 at 5:56
  • $\begingroup$ @fsI if $r$ is fixed, the asymptotics is obtained by the saddle point method $\endgroup$ Commented May 13, 2021 at 17:53

1 Answer 1

4
$\begingroup$

Hint: it's always worth checking the Online Encyclopedia of Integer Sequences.

For $r=3$ the values of $N$ are the sequence A002426. There's a wealth of literature references, a number of comments which you could try generalising, and the asymptotic $N \sim \sqrt{\frac{3}{8\pi}} 3^m m^{-1/2}$.

For $r=4$ the sequence is A005725. There's a recurrence for the g.f., and the asymptotic $N \sim k \alpha^m m^{-1/2}$ where $k = \sqrt{\frac{39 (117+2\sqrt{78})^{1/3} +7\times 39^{2/3}+39^{1/3}(117+2\sqrt{78})^{2/3}}{156\pi(117+2\sqrt{78})^{1/3}}}$, $\alpha = \frac{(6371+624\sqrt{78})^{2/3}+11(6371+624\sqrt{78})^{1/3}+217}{12(6371+624\sqrt{78})^{1/3}}$.

For $r=5$ the sequence is A187925. There's a statement that the g.f. is $1 + x\frac{A'(x)}{A(x)}$ where $A(x) = \frac{1 - x^5 A(x)^5}{1 - xA(x)}$ which looks like a very interesting avenue of investigation, and the asymptotic $N \sim k \alpha^m m^{-1/2}$ where $\alpha = 3.834437249\ldots$ is a root of the equation $27\alpha^4 - 94\alpha^3 - 15\alpha^2 - 50\alpha - 125= 0$, $k = 0.340444098\ldots$

Some higher values of $r$ are also present, but their entries are rather spartan.

$\endgroup$
3
  • $\begingroup$ Thanks for sharing the idea, this is very helpful! $\endgroup$
    – fs l
    Commented May 13, 2021 at 12:46
  • $\begingroup$ @fsl, talking of literature references, A005725 points to an exercise in Comtet's Advanced Combinatorics which gives an integral expression for the coefficient of $x^k$ in $(1 + x + \cdots + x^{r-1})^m$. $\endgroup$ Commented May 13, 2021 at 19:46
  • $\begingroup$ Thanks! I will have a look $\endgroup$
    – fs l
    Commented May 14, 2021 at 1:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.