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$
  • $\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 Jun 2 '14 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 Jun 2 '14 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 Jun 2 '14 at 21:28
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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