A071652 -id:A071652 - cp's OEIS frontend

A071651 Permutation of natural numbers induced by reranking plane binary trees given in the standard lexicographic order (A014486) with an "arithmetic global ranking algorithm", using the bivariate form of A061579 as the packing bijection N x N -> N.

0, 1, 2, 3, 4, 7, 5, 6, 10, 11, 29, 16, 22, 56, 8, 12, 9, 15, 36, 14, 21, 28, 66, 67, 436, 137, 254, 1597, 37, 79, 46, 121, 667, 106, 232, 407, 2212, 17, 38, 23, 30, 68, 13, 18, 20, 78, 465, 44, 153, 276, 1653, 19, 25, 27, 45, 91, 35, 55, 136, 703, 77, 120, 253, 435, 2278

Offset: 0

Antti Karttunen, May 30 2002

It seems that a(A014137(n)) = a(A014137(n)-1)+1 = A006894(n+1) for all n. - Antti Karttunen, Jul 30 2012

Antti Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Alternative Catalan Orderings
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A071652. Cf. also A014486, A061579, A071653, A071654.

A071654 Inverse permutation to A071653.

Original entry on oeis.org

0, 1, 3, 2, 8, 6, 5, 7, 19, 15, 4, 22, 16, 52, 14, 13, 20, 60, 43, 51, 41, 11, 18, 53, 178, 42, 153, 39, 10, 21, 47, 155, 177, 125, 151, 38, 12, 61, 56, 136, 154, 555, 123, 150, 40, 33, 55, 179, 164, 135, 479, 553, 122, 152, 117, 29, 17, 159, 557, 163, 417, 477, 552, 124

Offset: 0

Antti Karttunen, May 30 2002

A014137(n-1) = A071654(A072638(n)) for n>0 - Antti Karttunen, Jul 30 2012, based on Paul D. Hanna's similar observation in A071653.

Antti Karttunen, Rows n=0..66 of triangle, flattened
A. Karttunen, Alternative Catalan Orderings
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A071653. A071672 gives the corresponding parenthesizations (from the term 1 onward) encoded as binary numbers, i.e. A071672(n) = A063171(A071654(n)) for n >= 1.

a(n) = A057163(A071652(n)). Cf. also A014486, A002262, A025581, A071651, A071652.

A072635 Inverse permutation to A072634.

Original entry on oeis.org

0, 1, 3, 2, 6, 8, 7, 19, 16, 5, 15, 4, 14, 52, 43, 51, 42, 20, 22, 53, 60, 21, 61, 56, 179, 155, 178, 154, 177, 164, 557, 163, 556, 11, 39, 13, 41, 151, 123, 153, 125, 12, 40, 33, 117, 152, 124, 471, 381, 477, 553, 479, 555, 505, 1797, 507, 1799, 478, 554, 1536

Offset: 0

Antti Karttunen, Jun 02 2002

nonn

A. Karttunen, Gatomorphisms
Index entries for sequences that are permutations of the natural numbers

A072644 gives the size of the corresponding parenthesizations, i.e. A072644(n) = A029837(A014486(A072635(n))+1)/2 [A029837(n+1) gives the binary width of n].

A072635(n) = A057163(A072637(n)). Cf. also A014486, A059905, A059906, A071652, A072647, A072637.

A071653 Permutation of natural numbers induced by reranking plane binary trees given in the standard lexicographic order (A014486) with an "arithmetic global ranking algorithm", using the bivariate form of A001477 as the packing bijection N x N -> N.

Original entry on oeis.org

0, 1, 3, 2, 10, 6, 5, 7, 4, 66, 28, 21, 36, 15, 14, 9, 12, 56, 22, 8, 16, 29, 11, 2278, 435, 253, 703, 136, 120, 55, 91, 1653, 276, 45, 153, 465, 78, 77, 35, 27, 44, 20, 25, 18, 68, 2212, 407, 30, 232, 667, 121, 19, 13, 23, 106, 46, 38, 79, 1597, 254, 17, 37, 137, 436

Offset: 0

Antti Karttunen, May 30 2002

nonn

A071653(A014137(n-1)) = A072638(n) for all n > 0. - Paul D. Hanna, Jan 04 2007

Also seems that A071653(A014137(n)-1) = A006894(n) for all n > 0. - Antti Karttunen, Jul 30 2012

Antti Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Alternative Catalan Orderings
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A071654. Cf. also A014486, A001477, A071651, A071652.

A071671 The binary encoding of parenthesizations given in a "global arithmetic order", using A061579 as the packing bijection N X N -> N.

Original entry on oeis.org

10, 1010, 1100, 101010, 110010, 110100, 101100, 11001010, 11010010, 111000, 10101010, 11001100, 1101001010, 11100010, 11010100, 10110010, 1100101010, 1101001100, 1110001010, 1101010010, 11100100, 10110100, 1100110010

Offset: 1

Antti Karttunen, May 30 2002

A. Karttunen, Gatomorphisms (Includes the complete Scheme source for computing this sequence)

a(n) = A063171(A071652(n)). Permutation of A063171 and A071672. In particular, applying the automorphism ReflectBinTree (A057163) to A071671(n) yields A071672(n). The length of each term / 2 gives A071673.

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

Original entry on oeis.org

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

Offset: 0

Peter Luschny, Aug 09 2012

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

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.

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.

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

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

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

cp's OEIS Frontend

A071651 Permutation of natural numbers induced by reranking plane binary trees given in the standard lexicographic order (A014486) with an "arithmetic global ranking algorithm", using the bivariate form of A061579 as the packing bijection N x N -> N.

Views

Author

Keywords

Comments

Links

Crossrefs

A071654 Inverse permutation to A071653.

Views

Author

Keywords

Comments

Links

Crossrefs

A072635 Inverse permutation to A072634.

Views

Author

Keywords

Links

Crossrefs

A071653 Permutation of natural numbers induced by reranking plane binary trees given in the standard lexicographic order (A014486) with an "arithmetic global ranking algorithm", using the bivariate form of A001477 as the packing bijection N x N -> N.

Views

Author

Keywords

Comments

Links

Crossrefs

A071671 The binary encoding of parenthesizations given in a "global arithmetic order", using A061579 as the packing bijection N X N -> N.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Sage