There are $n$ boxes which is numbere from $1$ to $n$. The box with number $1$ is open, and the others are closed. There are $m$ identical balls ($m\geq n$). One of the balls is put into the open box, then we open the box with number $2$. Now, we put another ball to one of two open boxes, then we open the box with number $3$. Go on until the last box will be open. After that the remaining balls will be randomly put into the boxes. In how many ways this arrangement can be done?
Problem
Source:
Tags: induction, inequalities, combinatorics proposed, combinatorics
14.03.2011 02:00
Let the answer to the problem be $s_{n,m}$. Suppose the number of balls in box $i$ is $a_i$. So we have $a_1 + a_2 + \cdots + a_n = m$. Furthermore, the box opening conditions are equivalent to $a_1 + a_2 + \cdots + a_k \geq k$ for all $k \leq m$. Note that the truncated sequence $a_1, a_2, \ldots a_{n-1}$ will still satisfy the partial sum conditions and has sum $m-a_n$. Hence if we fix $a_n$, the number of ways to distribute the remaining $m - a_n$ balls in the other $n-1$ boxes is $s_{n-1,m-a_n}$ if $m-a_n \geq n-1$ and 0 otherwise. We then get the recurrence $s_{n,m} = \sum_{k=n-1}^{m} s_{n-1,k}$. Now we prove $s_{n,m} = {m+n-2 \choose n-1} - {m+n-2 \choose n-3}$ by induction on $n$. It is clear that $s_{1,m} = 1$ for all $m$, and this satisfies the formula. Suppose that the formula holds for some fixed $n$ and all $m$. We have \[s_{n+1,m} = \sum_{k=n}^{m} s_{n,k} = \sum_{k=n}^{m} {k+n-2 \choose n-1} - \sum_{k=n}^{m} {k+n-2 \choose n-3}.\] Note that $\sum_{k=n}^{m} {k+n-2 \choose n-1} = {m+n-1 \choose n} - {2n-2 \choose n}$ by the Hockeystick identity applied twice. Likewise $\sum_{k=n}^{m} {k+n-2 \choose n-3} = {m+n-1 \choose n-2} - {2n-2 \choose n-2}$. We have ${2n-2 \choose n} = {2n-2 \choose n-2}$, so by subtracting these two, we get $s_{n+1,m} = {m+n-1 \choose n} - {m+n-1 \choose n-2}$, as desired. Note when $m = n$ we get the Catalan numbers. I'm guessing this particular counting scheme is well known?
30.08.2011 00:46
First say that $a_1,a_2...;a_n$ are the boxes than we $a_i\le{m-i}$(because $a_1$ must have at least one ball) then using principle of inclusion and distribution formula: Suppose that for $k$ number of $i$ satiesfied this inequality $a_i>{m-i}$ then say this $a_i$'s $a_{x_1},a_{x_2},....a_{x_k},$ we have this formula for permutations : \[\dbinom{n+m-1-(m-x_1)-(m-x_2).....-(m-x_k)-+1}{n-1}\] \[\forall x_1,x_2,....x_k\in[1,n]\] now using principle of inclusion we have the solution. The solution is: \[\sum_{k=0}^{n}(-1)^k({\sum_{x_1,x_2....x_k\in[1,k]}\dbinom{n+m-1-(m-x_1)-(m-x_2).....-(m-x_k)-1}{n-1}})\] \[\forall x_1,x_2,....x_k\in[1,n]\] \[x_1,x_2,....x_k\in\mathbb{Z^{+}}\] And a remark if $a<0$ say that $\dbinom{a}{b}=0$ Sorry for my bad english