1
$\begingroup$

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"

$\endgroup$
3
  • $\begingroup$ As the link you give shows, even the $\le M$ restriction alone gives a mess. Adding the other conditions makes it worse. $\endgroup$
    – vadim123
    Commented Jun 2, 2014 at 20:32
  • $\begingroup$ I don't doubt its a mess, I'd still like a solution though. For implementing this (in Matlab say) I could then use logs to convert the multiplications into additions, and exponentiate to calculate an approximate solution. $\endgroup$
    – user152112
    Commented Jun 2, 2014 at 20:36
  • $\begingroup$ Also maybe don't google "bounded combinatorics" (don't google "bounded mathematics") - maybe google "bounded combinations"/"restricted compositions"/"restricted integer compositions"/"bounded compositions" or something similar :) $\endgroup$
    – mathse
    Commented Jun 2, 2014 at 21:28

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .