Distributing balls into distinct boxes

Question

So basically my question is this:

I have $30$ non distinct balls that I want to put inside $4$ distinct boxes. For every $1\le i\le 4$, the $"i"$ indexed box must at least have $i$ balls and at max $10i$ balls.

Answer 1

You want:

$$[x^{30}]: (x+\dots+x^{10})(x^2+\dots+x^{20})(x^3+\dots+x^{30})(x^4+\dots+x^{40})$$

where $[x^{30}]:$ is the coefficient of $x^{30}$, and each term represents the ways to put balls into the $i^{th}$ box.

Answer 2

Let us consider brackets corresponding to each box. $$(x^1+x^2+\dots+x^{10})\;\dots\text{(for $1$)}\\ (x^2+x^3+\dots+x^{20}) \;\dots\text{(for $2$)}\\ (x^3+x^4+\dots+x^{30})\;\dots\text{(for $3$)} \\ (x^4+x^5+\dots+x^{40})\;\dots\text{(for $4$)} $$

Here, the powers of $x$ represents the no. of balls the box can receive. There is no significance of $x$ but we are interested in powers of $x$. Now, the total no. of distributions is coefficient of $x^{30}$ in $(x^1+x^2+\dots+x^{10})(x^2+x^3+\dots+x^{20})(x^3+x^4+\dots+x^{30})(x^4+x^5+\dots+x^{40}) $

Answer 3

You’ll need to read up on stars and bars to understand this answer.

The lower bounds are straightforward to deal with: Put $i$ balls in box $i$ and then distribute the remaining $30-\sum_{i=1}^4i=20$ balls over the $4$ boxes, with box $i$ receiving at most $9i$ more balls.

As @lulu remarked, only the first two upper bounds are actually constraints. There are $\binom{20+4-1}{4-1}=\binom{23}3$ ways to distribute the $20$ balls over $4$ boxes without constraints, $\binom{20-10+4-1}{4-1}=\binom{13}3$ ways to first put $10$ more balls into box $1$ to violate the first constraint and then distribute the remaining $20-10$ balls over $4$ boxes, and $\binom{20-19+4-1}{4-1}=\binom43$ ways to first put $19$ more balls into box $2$ to violate the second constraint and then distribute the remaining $20-19$ balls over $4$ boxes. Usually we would now have to deal with the cases where both constraints are violated using inclusion–exclusion, but here it’s impossible to violate both constraints. So we’re done, and the total is

$$ \binom{23}3-\binom{13}3-\binom43=1481\;. $$