cp's OEIS Frontend

A215406 A ranking algorithm for the lexicographic ordering of the Catalan families.

%I A215406 #31 Feb 01 2017 12:31:06
%S A215406 0,0,1,1,1,1,1,1,1,1,2,2,3,3,3,3,1,1,1,1,2,2,2,2,3,3,3,3,3,3,3,3,2,2,
%T A215406 2,2,2,2,3,3,3,3,4,4,5,5,5,5,5,5,6,6,7,7,7,7,8,8,8,8,8,8,8,8,2,2,2,2,
%U A215406 2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4
%N A215406 A ranking algorithm for the lexicographic ordering of the Catalan families.
%C A215406 See Antti Karttunen's code in A057117. Karttunen writes: "Maple procedure CatalanRank is adapted from the algorithm 3.23 of the CAGES (Kreher and Stinson) book."
%C A215406 For all n>0, a(A014486(n)) = n = A080300(A014486(n)). The sequence A080300 differs from this one in that it gives 0 for those n which are not found in A014486. - _Antti Karttunen_, Aug 10 2012
%H A215406 G. C. Greubel, <a href="/A215406/b215406.txt">Table of n, a(n) for n = 0..1000</a>
%H A215406 A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/tab9766.htm">Catalan's Triangle and ranking of Mountain Ranges</a>
%H A215406 D. L. Kreher and D. R. Stinson, <a href="http://www.math.mtu.edu/~kreher/cages.html">Combinatorial Algorithms, Generation, Enumeration and Search</a>, CRC Press, 1998.
%H A215406 F. Ruskey, <a href="http://www.cs.uvic.ca/~ruskey/Publications/Thesis/Thesis.html">Algorithmic Solution of Two Combinatorial Problems</a>, Thesis, Department of Applied Physics and Information Science, University of Victoria, 1978.
%p A215406 A215406 := proc(n) local m,a,y,t,x,u,v;
%p A215406 m := iquo(A070939(n), 2);
%p A215406 a := A030101(n);
%p A215406 y := 0; t := 1;
%p A215406 for x from 0 to 2*m-2 do
%p A215406     if irem(a, 2) = 1 then y := y + 1
%p A215406     else u := 2*m - x;
%p A215406          v := m-1 - iquo(x+y,2);
%p A215406          t := t + A037012(u,v);
%p A215406          y := y - 1 fi;
%p A215406     a := iquo(a, 2) od;
%p A215406 A014137(m) - t end:
%p A215406 seq(A215406(i),i=0..199); # _Peter Luschny_, Aug 10 2012
%t A215406 A215406[n_] := Module[{m, d, a, y, t, x, u, v}, m = Quotient[Length[d = IntegerDigits[n, 2]], 2]; a = FromDigits[Reverse[d], 2]; y = 0; t = 1; For[x = 0, x <= 2*m - 2, x++, If[Mod[a, 2] == 1, y++, u = 2*m - x; v = m - Quotient[x + y, 2] - 1; t = t - Binomial[u - 1, v - 1] + Binomial[u - 1, v]; y--]; a = Quotient[a, 2]]; (1 - I*Sqrt[3])/2 - 4^(m + 1)*Gamma[m + 3/2]*Hypergeometric2F1[1, m + 3/2, m + 3, 4]/(Sqrt[Pi]*Gamma[m + 3]) - t]; Table[A215406[n] // Simplify, {n, 0, 86}] (* _Jean-François Alcover_, Jul 25 2013, translated and adapted from Peter Luschny's Maple program *)
%o A215406 (Sage)
%o A215406 def A215406(n) : # CatalanRankGlobal(n)
%o A215406     m = A070939(n)//2
%o A215406     a = A030101(n)
%o A215406     y = 0; t = 1
%o A215406     for x in (1..2*m-1) :
%o A215406         u = 2*m - x; v = m - (x+y+1)/2
%o A215406         mn = binomial(u, v) - binomial(u, v-1)
%o A215406         t += mn*(1 - a%2)
%o A215406         y -= (-1)^a
%o A215406         a = a//2
%o A215406     return A014137(m) - t
%Y A215406 Cf. A213704, A057117, A057164, A057505, A057506, A057501, A057502, A057511, A057512, A057123, A057117, A057509, A057510, A057161, A057162, A072766, A071654, A071652, A075161, A061856, A072635, A072788, A057518, A075168, A080119, A057120, A072773.
%K A215406 nonn,look
%O A215406 0,11
%A A215406 _Peter Luschny_, Aug 09 2012