2

I am reading about catalan numbers and they are considered to represent the number of valid pair of parentesis, mountains etc.
Although the number checks out correct when comparing against specific cases e.g. $n = 2$ or $n = 3$ for pairs of parenthesis, it is not clear to me how it is correct.
I am reading an example in a book using mountains i.e. strokes up and down e.g.

       /\/\
/\/\  /
    \/

and mentions that if we add an extra up stroke we have $\frac{7!}{4!3!} = 35$ sequences of $4$ upstrokes and $3$ downstrokes which I think means that if we have in total $7$ symbols and we choose $3$ or $4$ pairs (${7 \choose 3} = {7 \choose 4}$) we have $35$ combinations valid and invalid in total e.g. for the example of parenthesis something like $)()($ or $)((($is invalid.
Then the text claims that if we continue these patterns periodically we get only $5$ infinite sequences i.e. only $5$ different mountains with $3$ upstrokes and $3$ downstrokes.
I don't really understand this point.

  1. How is it that we are guaranteed that we get only the number of valid configurations?
  2. Trying to reproduce the process with a small number e.g. $4 \choose 2$ which gives $6$ possible configurations, and started appending and repeating them I couldn't come with just $2$ unique patterns repeating so I must be doing something wrong

Can someone help understand this?

Update:
For example I was trying to follow the process with a small number i.e. $4 \choose 2$ which gives $6$ which are (map opening bracket to upstroke and closing to downstroke):

()() or /\/\  (1)

     /\



(()) or /  \  (2)


      /\  (3)



)(() or /


())( or /\    (4)
          /


)()( or  //  (5)


))(( or \  /   (6)
         /

According to the text if I append them there should be only $2$ infinite patterns but I don't understand how to reproduce the process.

E.g I can start appending $1,3,3,4,5,2,3,1,3,3...$ to form one sequence but I am not sure what criteria I can use to figure out if I am doing this right

 1    3   3   4  5   2    3

                 /\



//\  /\  //\      /  \  /

    /  /    ///    /
Jim
  • 1,589

1 Answers1

1

We already have an idea of the nice relationship between expressions of well-formed parentheses and mountains. Let's revisit the relevant text part in The Book of Numbers by J.H. Conway and R.K. Guy.

  • [Conway, Guy]: To see that they are the Catalan Numbers, it's perhaps easiest to count the mountains. ... If we add in an extra upstroke, there are $7!/4!3!=35$ sequences of $4$ upstrokes and $3$ downstrokes, but if we continue these patterns periodically ... we get only $5$ different infinite sequences, which break naturally at the dashed edges to reveal the $5$ different mountains with $3$ upstrokes and $3$ downstrokes.

I think the interesting part, which might help to clarify the situation are the words: ... which break naturally at the dashed edges ....

enter image description here

The graphic shows the case $n=2$ with $C_n=2$. The upper two mountain chains are periodic copies of well formed mountains corresponding to the well-formed parentheses. A well-formed mountain

  • starts with an upstroke,

  • has as many upstrokes as downstrokes and

  • each left part of a mountain contains at least as many upstrokes as downstrokes.

This way up- or downstrokes of a mountain are never below its baseline, the segment joining leftmost and rightmost endpoint.

We observe the two valid mountain chains have the nice property, that each mountain is connected with an upstroke and we can draw a dotted line going through the left point of dashed edges. Invalid mountain chains do not have this property as seen in the third part of the graphic.

Markus Scheuer
  • 108,315
  • What is the meaning of the "we get only $5$ different infinite sequences"? $5$ is the number of well-formed cases but how do we get them from that sentence?
  • What is the meaning of that baseline? The third cases with is the bad one, does not go bellow the baseline either
    • – Jim Apr 25 '22 at 20:55
  • @Jim: Ad 1.) I think you sketch all possible sequences and check them for being valid. In the same way as you did it for the $6$ sequences with $n=2$ which show two valid sequences. 2.) With baseline of a mountain I mean the line seqment joining the leftmost and the rightmost node of a mountain, A well-formed mountain does not go below this kind of baseline. This property assures that we can draw a line going through the left point of dashed lines. This is not the case in the third example. – Markus Scheuer Apr 25 '22 at 21:28
  • If I pick from my post the case (3) which is bad form, and I start appending $3$ one after the other I would create a mountain repeated without needing a dashed edge. If I do the same with $4$ the mountain will be exactly the same (again no dashed edges required). If I keep repeating $5$ I'll get the same mountain as $1$ (no dashed edge). If I keep repeating $6$ I'll get the same mountain pattern as if I repeated $2$. So I am not sure exactly what's going on and how the dashed edges make a difference in these cases – Jim Apr 25 '22 at 21:55
  • Also when you say "the line seqment joining the leftmost and the rightmost node of a mountain" I am not sure which do you mean. Originally my question was about the dashed line acting as a horizon that none of the patterns go bellow and if you were talking about that, only the rightmost edge of the good cases touch it. If you were referring to the dashed edges then I don't see a difference with the last case – Jim Apr 25 '22 at 21:57
  • Also I think that in the book the very first example in the list of $6$ that it shows presents a dot instead of a dash. I think the case showing is $()())($ and then it adds an upstroke every other mountain in that line. I don't understand what it tries to demonstrate – Jim Apr 25 '22 at 22:13
  • 1
    @Jim: As I wrote in my answer, the key point is the dotted line goes through the left point of dashed edges. This is only possible for valid sequences. – Markus Scheuer Apr 25 '22 at 22:31
  • If we have for $n = 3$ the bad case $())(()$ if we draw the corresponding mountain the dashed line will cross the dashed edge through its right point so I think I see what you mean. But how does this observation help us in determining the actual number of good cases? What is the core idea that makes this observation appear in the mountains? – Jim Apr 25 '22 at 23:05
  • 1
    @Jim: I've reformulated the criteria which make a sequence of up- and downstrokes a valid mountain. This is the core idea and it turns out, that when we add an additional upstroke it has the nice property that dotted lines go through the left endpoint of dashed edges. – Markus Scheuer Apr 26 '22 at 16:59
  • Thank you very much for the update. I do understand what the text means now! The only part that I am not sure is how would find there are only $5$ such infinite sequences that match the criteria without knowing the Catalan number beforehand? Would it be by drawing them all? – Jim Apr 26 '22 at 19:06
  • @Jim: In fact it can be done nicely by a direct counting argument. We count all paths with $n$ upstrokes and $n$ downstrokes and subtract all invalid paths. See for instance this answer. – Markus Scheuer Apr 26 '22 at 19:46