Let $a_n$ be the number of ways of placing $n$ indistinguishable objects into $n$ distinguishable boxes called $B_1$, $B_2$, ..., $B_n$, such that the following hold:
- There is at most $1$ object in $B_1$;
- There are at most $2$ objects in $B_1$ and $B_2$ together;
- There are at most $3$ objects in $B_1$, $B_2$, $B_3$ together;
- etc.
Find $a_n$ and then find $a_8$.
At first I thought this problem was a recurrence relation problem however I was having a lot of difficulty coming up with one. However, when I calculated the first 4 $a_n$ I noticed that the pattern follows the Catalan numbers. Now the issue I am having is that I don't understand how this connects to Catalan numbers. My understanding of Catalan numbers is that they come from the number of "right-up" paths from the bottom left corner to the top right corner of an $n\times n$ grid such that the path never crosses the diagonal. I believe I somehow have to find a 1-1 correspondence between the 2 but I am having trouble seeing one. I appreciate any help.
Given such a placement of the objects into boxes, write down a sequence $(s_1, s_2, \dots, s_n)$, where $s_i$ is the number of objects in $B_1,B_2, \dots, B_i$ combined (i.e. $s_i$ is the total number of objects in the first $i$ boxes). Some things to notice:
Create a "right-up" path from the sequence of $s_i$'s as follows. Start the path by going RIGHT (all Catalan paths must always start going RIGHT because they cannot go above the line $y=x$). Then for each $1 \leq i \leq n-1$, draw the path so that the horizontal step from $x=i$ to $x=i+1$ is at a height of $y=s_i$.
In other words, if there are $k$ objects in the first $i$ boxes, then your "right-up" path will have a horizontal step from $(i,k)$ to $(i+1,k)$. The fact that $s_i \leq i$ means the path will never go above the diagonal line $y=x$.