# Catalan numbers - number of ways to stack coins

How many ways are there to stack coins on top of the other (2D stack) without any coin falling down ?

Here's an example for $$n=3$$:

Now this is most likely just like the monotonic path of Catalan number with up and down instead of up and right but I just don't get why is that ? Well, any advice would be appreciated.

## 2 Answers

A picture is worth a thousand words, they say:

• This is basically what I drew only with circles but I still don't get it... It's like you're trying to get from one side to other, not find all the ways to stack the coins. – GinKin Dec 1 '13 at 12:38
• @GinKin We need a bijection between Dyck paths and stacks of coins. Such bijection is given by the picture: any stack of coins gives a path (draw the contour of the stack), any path gives a stack of coins (fill the space below the path), and these are two inverse maps. – Grigory M Dec 1 '13 at 12:52
• @GrigoryM How would we show that this bijection is indeed well defined? – user46372819 Dec 2 '15 at 19:34

Take any Dyck path of length $$2n$$ and observe the points bounded by it above the diagonal. This is precisely a coin stack of base $$n$$ since every layer has one less place to put coins than the layer below, and the different "peaks" of the Dyck path result from how many coins you've stacked in each layer.

Inversely, you can start with a coin stack, add a bottom layer of $$n+1$$ coins to it and draw its boundary. This will be a Dyck path as it can never go below the base (ie the diagonal) and it requires exactly $$n$$ moves of "going up" and $$n$$ moves of "going right". The last claim is pretty obvious if you imagine the path is from $$(0,0)$$ to $$(n,n)$$.

Here is how the bijection looks like for $$n=4$$. (added as a link as my reputation is insufficient to post images). the points on the path are colored blue, the points on the diagonal are crossed out, and the points inside the stack are colored black.