New URL: http://www.iki.fi/~kartturi/matikka/tab9766.htm


Catalan's Triangle and ranking of Mountain Ranges

I explain here Catalan Mountain Range ranking & unranking algorithms which are variants of ones given in [2].

Let's rank the totally balanced binary string 11011001110000, in decimal 13936. First we draw a corresponding mountain range, moving from the left (the most significant end) to the right (the least significant end) in binary string, letting 1 stand for the upward slope /, and 0 stand for the downward slope \. 


11011001110000

         /\
    /\  /  \
 /\/  \/    \
/            \
Then we draw the mountain range over the triangle obtained from the EIS-sequence A009766, formatted as a triangular array, with one additional diagonal of zeroes appended at its left side. We start from the right-hand end of the range, setting the last downward slope to stretch from the first zero at the top to the next zero below it.


    0   1
    0   1   1
    0   1   2   2
    0   1   3   5   5
    0-------1-------4-------9  14  14
    0   1   5  14  28  42  42
    0   1   620------48------90 132 132
    0   1   7  27  75 165-----297-----429 429
    0   1   8  35110 275 572100114301430
    0   1   9  44 154 42910012002343248624862


Them all the terms which are on positions where the slope is falling downward (when viewing the original drawing from left to right) are summed up, i.e. here the terms marked with blue colour, 0+0+0+0+0+14+20+165 = 199, which is the rank, See Kreher's and Stinson's book for the rationale behind the algorithm.


Above algorithm implemented with Maple procedures: 

CatTriangleDirect := (r,m) -> `if`((m < 0),0,((r-m+1)*(r+m)!)/(r! * m! * (r+1)));

CatTriangle := proc(r,m) option remember;
  if(m < 0) then RETURN(0); fi;
  if(r < 0) then RETURN(0); fi;
  if(m > r) then RETURN(0); fi;
  if(0 = m) then RETURN(1); fi;
  RETURN(CatTriangle(r,m-1) + CatTriangle(r-1,m));
end;

CatalanRank2 := proc(n,aa) local y,r,lo,a;
 a := aa;
 r := 0;
 y := -1;
 lo := 0;
 while (a > 0)
  do
      if(0 = (a mod 2))
        then
          r := r+1;
          lo := lo + CatTriangle(r,y);
        else
          y := y+1;
      fi;
      a := floor(a/2);
  od;
 RETURN((binomial(2*n,n)/(n+1))-(lo+1));
end;

CatalanUnrank2 := proc(n,rr) local t,y,lo,r,a,m;
 r  := (binomial(2*n,n)/(n+1))-(rr+1);
 a := 0;
 lo := 0;
 t := n;
 y := n-1;
 while(t > 0)
  do
     m := CatTriangle(t,y);
     if(r < (lo+m))
        then
          y := y-1;
          a := 2*a + 1;
        else
          lo := lo+m;
          t := t-1;
          a := 2*a;
     fi;
  od;
 RETURN(a);
end;


Another example: 


convert(2762, binary);

101011001010



     /\
/\/\/  \/\/\
   0   1
*
   0--------1   1
*
   0   1-------2   2
*
   0   1   3   5   5
*
   0   1   4-------9------14  14
*
   0   1   5  14  28------42  42
*
   0   1   620  48  90-----132 132
 
   0   1   7  27  75 165 297 429 429
 
   0   1   8  35110 275 572100114301430
 
   0   1   9  44 154 42910012002343248624862


Summing up the blue terms, we get 0+0+1+3+4+28+90 = 126, and subtracting this from the 6th Catalan number, 132, and decreasing by one, we get 132-126-1 = 5 as its rank among the sequences/mountain ranges of the same length, or alternatively, subtracting 126 from the 6th term of A014137 and decreasing by one, we get 197-126-1 = 70, meaning that it would occur as the 70th term in the sequence A014486.


Let's draw the above range another time on top of the triangle, this time starting from the top 1, at (0,0). Note, that because each term in the triangle is obtained by summing its two neighbours, one at its left side, and one at its NE-corner (everything outside the triangle is zeroes), the each term gives precisely the number of different paths that start from the top (0,0)-cell, stay inside the triangle, and end to that node, using only those two steps, NE->SW and W->E.

Furthermore, this one is a palindromic mountain range. Any palindromic range of length 12, consists of a sequence of 6 steps, that end somewhere on the shallow diagonal marked here with bold numbers, 1, 5, 9, 5, and which steps are then reflected as a mirror-image, on the other side of that "axis". Because we know that terms on such shallow diagonals sum to the central binomial coefficients C(n,[n/2]) (see [1]), i.e. the EIS-sequence A001405, we see that they enumerate the number of such palindromic mountain ranges, A061855, and the corresponding "half-paths", A061854. It's now also easy to see why the squares of the terms on shallow diagonals sum to Catalan numbers themselves A000108.
(But can you see why the row sums of the triangle, like 1+3+5+5 = 14, 1+4+9+14+14 = 42, etc. also sum to Catalan numbers?)

       1
*
           1-------1
*
       1       2-------2
*
       1   3   5   5
*
       1   4       9------14------14
*
       1   5  14  28      42------42
*
       1   620  48  90     132-----132
 
       1   7  27  75 165 297 429 429
 
       1   8  35110 275 572100114301430
 
       1   9  44 154 42910012002343248624862


Addendum October 20 2004: On October 03 2003, I received an e-mail from Frank Ruskey, informing me that his 1978 Thesis [3] was concerned with similar ranking & unranking algorithms of Catalan families as the ones presented here. (I promptly promised to update this page with that new information, and here is the result, 383 days later.) In any case, his system is in a certain way a mirror image of the system presented above, which is just a boon, because it orders the Catalan paths directly in my local rank ordering, without any subtraction steps in the beginning or the end of the said functions. I have used this new algorithm for example in the following "exploratory programs for gatomorphology" [5]: gatomorf.c, gatonore.c and gatorank.scm. Search for the functions CatalanRank and CatalanUnrank. In the Scheme source file, the functions named CatalanRank and CatalanUnrankOld are implemented in the "Kreher-Stinson way", and the functions named CatalanRankSexpAux, CatalanUnrank and CatalanUnrankSexpAux are implemented in the "Ruskey way". (Slightly confusing, yes...)

Note that on the page 24 of the Frank's thesis, the while loop condition of the unranking algorithm is erroneously given as m > 0, while it should be m >= 0, i.e. we stop only when m goes negative.

Frank also mentioned in his mail that

These ranking and unranking schemes seem to get periodically re-discovered. It's quite possible that I'm not the originator either. Certainly Knott, Trojanowski, Rotem, Zaks and others were also ranking and generating various Catalan sequences in the late 70's.


References:


Back to Antti Karttunen's main page.