Front-loaded Boxes

To destroy the symmetry of the problem, label the balls 1, 2, 3, 4, 5, 6, 7 and assert that if a ball comes earlier in the list, it will not come in a higher box. e.g. if 4 is in box 3, 5 will not be in box 2.

Under these circumstances, we note that ball i must be in a box with number at most i, and then once this is forced the arrangement will work.

Let n(A,B) be the number of ways of doing it with A balls and B boxes, so we meed to work out n(7,6).

Now, suppose that A < B. Then n(A,B) = n(A,B-1), since no balls could have gone in the last box anyway.

Otherwise, suppose A $\geq$ B. Then n(A,B) = n(A-1,B) + n(A,B-1), since the first term corresponds to putting the first A-1 balls into the boxes and then the last ball into the rightmost box (which can be done as A is small enough), and the second term corresponds to ways of doing it such that the rightmost box is empty.

Hence, n(7,7) = n(6,7) + n(7,6) = n(6,6) + n(7,6), so n(7,6) = n(7,7) - n(6,6).

Finally, we will show that n(i,i) is equal to the i'th term in the Catalan sequence , and since we know the formula for the Catalan numbers that will give us the answer of 297:

The Catalan numbers correspond to the number of parenthetical expressions with n open and n close brackets, such that there are always at least as many open brackets as close brackets. Thus the bijection between n(i,i) and the i'th Catalan number will be to take the expression, and for each open bracket, put a ball in the box corresponding to one more than the number of close brackets so far. For example, if i = 5, the expression (()(()())) will have balls in boxes 1,1,2,2,3.

Let $f(n,k)$ be a function returning the number of different placements of $n$ balls into $k$ boxes ( $1,2,...k$ ) with the requirement above.

If $n < k$ , the value of $f(n,k)$ will be zero ( $0$ ) since it is impossible to get at least $k$ balls in $k$ boxes.

To get the value of $f(n,k)$ in general :

If we put $i$ balls in $k^{th}$ box, hence the other balls are put amongst boxes $1,2,...k-1$ and it must be in a valid condition. Therefore, the number of different placements when we put $i$ balls in $k^{th}$ box is $f(n-i,k-1)$ .

Because we can put between $0$ to $n$ balls in $k^{th}$ box, hence $f(n,k) = \displaystyle \sum_{i=0}^n f(n-i,k-1)$ .

The exception is when $k = 1$ that we have to put all of the balls in the $1^{st}$ box, so $f(n,1) = 1$ .

It is faster and easier to find the value of $f(n,k)$ when we make it on table :

Table of f(n,k)

Remember that $f(n,k) = 0$ when $n < k$ .

The answer is $f(7,6) = 297$ .

Let $b_k$ be the number of balls in box $k$ and let $r_k = b_1+\cdots+b_k - k$ , or in other words, the extra number of balls in boxes $1, 2, \cdots n$ above the minimum needed. So $0\leq r_k \leq 7-k$ , since we can have at most $7$ balls and at least the number of balls required to satisfy the problem. Finally, let $f_b(r)$ be the number of ways to fill $b$ boxes so that $r_b = r$ . We'll find a recurrence relation to find $f_6(1)$ , the number of ways to fill $6$ boxes with $1$ ball left over (total of $7$ balls).

Suppose that we filled $k$ boxes with $r_k$ remaining. In the next box $(k+1)$ , we can place $0$ balls up to the number of balls that make the total $7$ balls, as long as the problem's conditions are satisfied (e.g. we can't place 0 balls in the next box if $r_k = 0$ ). In other words, from $k$ boxes with $r_k$ remaining, we can have any $r_{k+1}$ between $r_k-1\leq r_{k+1} \leq 7 - (k+1)$ as long as $r_{k+1} \geq 0$ . Rearranging the left side of the inequality, we see that with $k$ boxes filled, we can fill $k+1$ boxes with extra $r_{k+1}$ if and only if $0\leq r_k \leq r_{k+1} + 1$ .

The number of ways to fill $(k+1)$ boxes with $r_{k+1}$ remaining, $f_{k+1}(r_{k+1})$ , is the sum of the number of ways to fill $k$ boxes so that by adding some number of balls to the next box, we can achieve $(k+1)$ boxes with $r_{k+1}$ remaining. We can only do so if $0\leq r_k \leq r_{k+1} + 1$ , so $f_{k+1}(r_{k+1})$ is the sum of number of ways to fill $k$ boxes such that $0\leq r_k \leq r_{k+1} + 1$ . We have

$f_{k+1}(r_{k+1}) = f_k(0)+f_k(1)+\cdots + f_k(r_{k+1}+1)$ or if $r_{k+1}\geq 1$ , $f_{k+1}(r_{k+1}) = f_{k+1}(r_{k+1}-1)+ f_k(r_{k+1}+1)$

Now, $f_1(k) = 1$ for all $0\leq r_k \leq 6$ , since there's only 1 way to place identical balls in one box. With this information and our recurrence relation, we record $f_6(1)$ with this table . (the first column is filled with 1 and each entry $n$ in a column after is the sum of the entry below $n$ and the entry above the cell to the left of $n$ , or else if $n$ is in the bottom row, the sum of the entry to the left of $n$ and the entry above the one to the left of $n$ )

We obtain our answer of $\boxed{297}$ .

Let $f(x,y) = n$ denote $n$ ways (satisfying the question's conditions) to place $y$ balls in boxes $1$ to $x$ . $f(1,y) = 1$ for all $y>0$ , and $f(x,y) = 0$ if $x > y$ . To calculate $f(x,y)$ , we note that this can be formed from cases in $f(x-1,y-k)$ (where $0 \leq k \leq y-1$ ), by adding $k$ balls to the box $x$ . Thus, $f(x,y) = \sum_{i=1}^y f(x-1,i) = f(x-1,y) + f(x,y-1)$ for $x>1$ . We can then construct $f(6,7) = 297$ .

We can reformulate this problem as arranging 7 balls and 5 dividers, such that up to any point, the number of balls is more than the number of dividers. We can think of these as steps in the Cartesian plane, beginning at $(0,0)$ and taking a $(1,1)$ step for a ball and a $(1,-1)$ step for a divider. This will give us a path from $(0,0)$ to $(12,2).$ Any path that crosses below the $x$ -axis will not be a valid path. We can count the number of valid paths by considering a reflection. For any path that crosses below the $x$ -axis, when it first has $y$ -coordinate $-1,$ we can flip the rest of the path along the line $y = -1,$ yielding a path from $(0,0)$ to $(12,-4).$ We can see that any invalid path will give a unique path of this type, and any path of this type comes from a unique invalid path, so there are the same number of both. Thus, the number of valid paths (and the number of ways we can arrange the balls) is $\binom{12}{5} - \binom{12}{4} = 792 - 495 = 297.$