# Consider the problem of stacking coins in the plane. Prove that the number of coin configurations satisfies the Catalan recurrence [duplicate]

Consider the problem of stacking coins in the plane such that the bottom row consists of $n$ consecutive coins.

Prove that the number of coin configurations satisfies the Catalan recurrence.

I understand I need some sort of bijection to Dyck paths, possibly with {$(1,1),(1.-1)$} steps in the plane, and then the length of the path would be the number of such configurations for every $n$. However thats not really a proof..

• Could you please give a more detailed description of the problem "stacking coins"? Oct 8 '15 at 2:26
• Does this help? math.stackexchange.com/questions/587958/… Oct 8 '15 at 2:37
• @SteveKass Yes already looked at it. The diagram is pretty much what I had in mind but I didnt quite understand the part where "you're trying to get from one side to other". With n = 3 in the example, the path length is 6 isnt it? so the number of configurations is 6, shouldnt it be 5? Oct 8 '15 at 3:29
• Ignoring the black squares for a moment, find out how many different blue paths can you take in that picture that get from the point $(0,0)$ to the point $(6,0)$ moving by diagonals, such that the path never dips below the $x$-axis? (You should be able to draw them all.) For each such path, draw the corresponding black squares. Oct 8 '15 at 14:04
• Also look at the blue and tan picture here: en.wikipedia.org/wiki/…, but consider just the blue squares that are on or below the diagonal of each figure. Oct 8 '15 at 14:07