login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A215406 A ranking algorithm for the lexicographic ordering of the Catalan families. 4
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, 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, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,11

COMMENTS

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."

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

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

A. Karttunen, Catalan's Triangle and ranking of Mountain Ranges

D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, Generation, Enumeration and Search, CRC Press, 1998.

F. Ruskey, Algorithmic Solution of Two Combinatorial Problems, Thesis, Department of Applied Physics and Information Science, University of Victoria, 1978.

MAPLE

A215406 := proc(n) local m, a, y, t, x, u, v;

m := iquo(A070939(n), 2);

a := A030101(n);

y := 0; t := 1;

for x from 0 to 2*m-2 do

    if irem(a, 2) = 1 then y := y + 1

    else u := 2*m - x;

         v := m-1 - iquo(x+y, 2);

         t := t + A037012(u, v);

         y := y - 1 fi;

    a := iquo(a, 2) od;

A014137(m) - t end:

seq(A215406(i), i=0..199); # Peter Luschny, Aug 10 2012

MATHEMATICA

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 *)

PROG

(Sage)

def A215406(n) : # CatalanRankGlobal(n)

    m = A070939(n)//2

    a = A030101(n)

    y = 0; t = 1

    for x in (1..2*m-1) :

        u = 2*m - x; v = m - (x+y+1)/2

        mn = binomial(u, v) - binomial(u, v-1)

        t += mn*(1 - a%2)

        y -= (-1)^a

        a = a//2

    return A014137(m) - t

CROSSREFS

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.

Sequence in context: A301805 A260236 A122462 * A231717 A253315 A210480

Adjacent sequences:  A215403 A215404 A215405 * A215407 A215408 A215409

KEYWORD

nonn,look

AUTHOR

Peter Luschny, Aug 09 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 22:34 EST 2019. Contains 329323 sequences. (Running on oeis4.)