4
$\begingroup$

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$:

enter image description here

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.

$\endgroup$
4
$\begingroup$

A picture is worth a thousand words, they say:

square coins

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – GinKin
    Dec 1 '13 at 12:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – Grigory M
    Dec 1 '13 at 12:52
  • $\begingroup$ @GrigoryM How would we show that this bijection is indeed well defined? $\endgroup$ Dec 2 '15 at 19:34
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.