approximation for star and bars method with bounded upper limit

Question

As we see in the answers of this linked question which is counting the solutions $(a_1,a_2,\ldots,a_n)$ with integer $0\leq a_i\leq r_i$ for $i \in \{1,2,\ldots,n\}$ such that

$$a_1+a_2+a_3+\ldots+a_n=N$$

Mike Earnest answered like this:

$$ W = \sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{N+n-1-\sum_{i\in S}(r_i+1)}{n-1} $$

But this is a little hard to calculate. Is there any approximation that be close to the answers of this statement?

Edit: Let me clear my question with some example. I test the result for $a_1+a_2+a_3=N$ such that

$$ 0 \leq a_1 \leq 1\text{,} \qquad 0 \leq a_2 \leq 3 \text{,} \qquad 0 \leq a_3 \leq 5$$

for $ 0\leq N \leq9$. This is how the result look like in system of coordinates with $N$ for $x$-axis and $W$ for $y$-axis

As we see by increasing $N$, $W$ begins from $1$ and hits a maximum value and then decreases to $1$ again.

But in unbounded case, it rises:

The reason that there is no maximum value for $0\leq N$ is that by increasing $N$ the bounds for $a_i$, which is $0 \leq a_i \leq N$, increase too, but in other case we have a fixed bound.

In this example by trial and error I found this polynomial approximation

$$ W = -\frac{2}{5}\left( N-\frac{9}{2}\right)^2 + 8 $$

It makes me wonder if can we find a polynomial approximation for $W(N,n,r_i)$ in any bounded case?

Answer 1

I know how to handle the situation where all of the upper limits are equal to each other. Let us say the common upper limit for the variables is $r$.

Imagine you choose $n$ integers randomly between $0$ and $r$ inclusive, independently of each other. Let $S$ be the sum of the chosen integers. Then $S$ is a random integer between $0$ and $nr$. This is useful because $P(S=N)$ is related to the number of solutions of $x_1+\dots+x_n=N$, via $$ \text{number of solutions} = (r+1)^n\cdot P(S = N) $$ The reason is because the probability space has $(r+1)^n$ equally likely outcomes; there are $n$ variables, each of which can take on $r+1$ values. The rule for the probability of an event in a uniform discrete set is $\text{probability}=(\text{# favorable outcomes})/(\text{# total outcomes})$.

To approximate $P(S=N)$, we use the the central limit theorem. Since $S$ is a sum of i.i.d. random variables, as long as $n$ is large enough, $S$ will be approximately equal in distribution to a normal random variable with the same mean and variance as $S$. Since $\mathsf E[S]=nr/2$ and $\mathsf{Var}[S]=n\cdot \frac{(r+1)^2-1}{12}$, we conclude that $$ P(S=N)\approx \frac1{\sqrt{2\pi \sigma^2}}e^{-(x-\mu)^2/(2\sigma^2)}, $$ where $\mu=nr/2$ and $\sigma^2=n\cdot \frac{(r+1)^2-1}{12}$. Combining the last two displayed lines gives the desired approximation. This is not a polynomial approximation like you requested, but you can turn it into a polynomial approximation by truncating the MacLaurin series for $e^t$. That is, you replace $e^t$ with $\sum_{k=0}^K \frac{t^k}{k!}$ for some natural number $K$, where $t=-(x-\mu)^2/(2\sigma^2)$.

You can attempt to do a similar thing in the case where the upper limits are unequal. The result would be $$ \text{number of solutions} = P(S=N)\cdot \prod_{i=1}^n (r_i+1),\\ P(S=N)\stackrel?\approx \frac1{\sqrt{2\pi \sigma^2}}e^{-(x-\mu)^2/(2\sigma^2)},\quad\text{where}\\ \mu=\frac12\sum_{i=1}^n r_i,\qquad \sigma^2=\sum_{i=1}^n\frac{(r_i+1)^2-1}{12} $$ This approximation is not always good, and it is exceedingly bad if the upper limits are widely and non-uniformly spread out. It does work well when the upper limits are approximately equal to each other, and it seems to work well if the upper limits are evenly spread out, like if $(r_1,r_2,\dots,r_7)=(1,3,5,7,9,11,13)$.