Marbles and boxes I came up with a seeminlgy simple problem: Suppose we have $N$ boxes (labeled) and $N$ marbles (unlabeled), in how many ways can we put the marbles in the boxes such that for every $i$ such that $1\leq i \leq N$ there are at most $i$ marbles is the first $i$ boxes? 
I calculated the first few answers from $N=0$ to $N=8$ and got $1,1,2,5,14,41,158,415$. 
(Eric pointed out that this is wrong, the last correct number is $14$)
Is there a formula or generating function for this sequence?
 A: These are the Catalan Numbers. To show this, I will show that you are actually counting something more well-known, namely the number of monotonic paths on the integer grid from $(0,0)$ to $(n,n)$ that do not pass above the diagonal.
We have $n$ boxes $B_1,\ldots,B_n$, and $n$ indistinguishable balls to place among them such that for all $k$, the total of the balls in $B_1,\ldots,B_k$ is at most $k$.
Now consider the $n \times n$ grid, and begin at $(0,0)$. For each of $n$ steps, first move 1 unit in the positive $x$ direction. Now move $k$ units in the positive $z$ direction, where $k$ is the number of balls in $B_k$. Clearly, since we have taken $n$ total steps in the positive $x$ direction and similarly for $z$, this process stops at $(n,n)$.
The condition on the number of balls in the first $k$ boxes is equivalent to never going above the diagonal, so every valid position of the balls gives a valid path. For the same reason, every valid monotonic path gives a valid positioning of the balls.
Therefore, these two interpretations count the same thing, and we know already that the number of ways to form a monotonic path on the grid from $(0,0)$ to $(n,n)$ without going above the diagonal is
$$C_n = \frac{1}{n+1}\binom{2n}{n}.$$
A: 
Every configuration will give you a path from $(0,0)$ to $(n,n)$ as in the picture that doesn't cross the main diagonal, hence Catalan.In the picture the number of blocks under the column is the number of marbles in total stored in the boxes up to that number.
