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..

  • 1
    $\begingroup$ Could you please give a more detailed description of the problem "stacking coins"? $\endgroup$
    – PSPACEhard
    Oct 8 '15 at 2:26
  • 6
    $\begingroup$ Does this help? math.stackexchange.com/questions/587958/… $\endgroup$
    – Steve Kass
    Oct 8 '15 at 2:37
  • $\begingroup$ @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? $\endgroup$
    – Mark S
    Oct 8 '15 at 3:29
  • $\begingroup$ 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. $\endgroup$
    – Steve Kass
    Oct 8 '15 at 14:04
  • $\begingroup$ 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. $\endgroup$
    – Steve Kass
    Oct 8 '15 at 14:07