Ways of Distributing $n$ balls among $k$ boxes, each box containing $L \leq x_i \leq M$ or $0$ Balls

Question

I need to calculate the number of ways of distributing $n$ balls among $k$ boxes, each box may contain no ball, but if it contains any, then it must contain $\geq L$ & $\leq M$ balls.

This effectively solves:

$x_1+x_2+x_3+\dotsb+x_k = n; \quad x_i\in [0,L,L+1,L+2,\dotsc,M-1,M]$.

Is there a known solution to this? Googling "bounded combinatorics" and similar doesn't reveal anything, except for the post below which is a solution for an upper-bound.

Number of ways to distribute indistinguishable balls into distinguishable boxes of given size

It feels like there should be a solution to the $L \leq x_i \leq M$ case, and then the $0$-possible case can then (hopefully) be added to this as a solution to "ways to distribute $n$ balls among $k$ boxes such that at least one box contains no balls"

Answer 1

Use generating functions to see if something turns up.

Each variable gets represented by: $$ 1 + z^L + z^{L + 1} + \ldots + z^M = 1 + z^L \frac{1 - z^{M - L + 1}}{1 - z} $$ The full problem is then to get the coefficient of $z^n$: $$ [z^n] \left(1 + z^L \frac{1 - z^{M - L + 1}}{1 - z} \right)^k = [z^n] \left(\frac{1 - z + z^L - z^{M + 1}}{1 - z} \right)^k $$ Doable by expanding the numerator using the multinomial theorem, and using that with the extended binomial theorem: $$ (1 + u)^{-m} = \sum_{r \ge 0} \binom{-m}{r} u^r = \sum_{r \ge 0} (-1)^r \binom{r + m - 1}{m - 1} u^r $$ where $m \in \mathbb{N}$, but the coefficients won't turn out nice.

Answer 2

Here's an alternative solution. First, let's get rid of your zero. Note that exactly $i$ boxes can be empty, where $0\le i\le k$. If $i$ boxes are empty, the remaining $k-i$ boxes have between $L$ and $M$ balls. So, denoting by $c(n,k,0,L,M)$ the number of solutions of your problem, you find

$$c(n,k,0,L,M)=\sum_{i=0}^k \binom{k}{i}c(n,k-i,L,M),$$

where $c(n,k,L,M)$ denotes the number of solutions of the problem where each box contains between $L$ and $M$ balls. Note that the number $c(n,k,L,M)$ denotes the number of restricted integer compositions and there is some literature on this problem. (You may also note that $c(n,k,L,M)=c(n-kL,k,0,M-L)$, which kind of simplifies the problem).

Answer 3

We can obtain a closed form using inclusion-exclusion principle. Depending on your purpose, you might choose between this approach or the generating function approach as suggested by vonbrand.

Let $l$ and $l'$ be the minimum and maximum number of boxes that can be empty. Suppose $l\le e\le l'$ boxes be empty. We can choose $e$ boxes in $\binom{k}{e}$ ways. We need to find the number of solutions to $$x_1+x_2+\dots +x_{k-e}=m$$ such that $L\le x_i\le M$ for all $1\le i \le k-e$. Distribute to $L$ to each $x_i$. This leaves us with $$y_1+y_2+\dots +y_{k-e}=m-L(k-e)$$ such that $0\le y_i\le M-L$.

By inclusion-exclusion principle, the number of solutions of the above equation such that at least one entry exceeds $M-L$ is, $$E(m,k,e,L,M):=\sum_{x=1}^{\lfloor \frac{m-L(k-e)}{M-L+1}\rfloor }(-1)^{x+1}\binom{k-e}{x}\binom{m-L(k-e)-(M-L+1)x+k-e-1}{k-e-1}$$

The number of solutions we seek is, $$\sum_{e=l}^{l'}\left( \binom{m-L(k-e)+k-e-1}{k-e-1}-E(m,k,e,L,M)\right)$$