A057123 -id:A057123 - cp's OEIS frontend

A123501 Signature permutation of a Catalan automorphism: apply *A123497 at the root, then recurse into the left subtree of the right hand side subtree of a binary tree.

0, 1, 2, 3, 4, 6, 7, 5, 8, 9, 10, 14, 16, 19, 17, 18, 12, 11, 13, 20, 15, 21, 22, 23, 24, 25, 26, 27, 37, 38, 42, 44, 47, 51, 53, 56, 60, 45, 46, 48, 49, 50, 31, 34, 30, 28, 29, 35, 33, 32, 36, 54, 55, 40, 39, 41, 57, 43, 58, 59, 61, 52, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

Index entries for signature-permutations of Catalan automorphisms

Inverse: A123502. A057501(n) = A083927(a(A057123(n))) = A083927(A085159(A057123(n))).

A130919 Signature permutation of a Catalan automorphism: DEEPEN-transform of automorphism *A057511.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 11, 14, 16, 19, 10, 15, 12, 17, 18, 13, 20, 21, 22, 23, 25, 28, 30, 33, 37, 39, 42, 44, 47, 51, 53, 56, 60, 24, 29, 38, 43, 52, 26, 40, 31, 45, 54, 32, 46, 49, 50, 27, 41, 34, 48, 55, 35, 57, 58, 62, 36, 61, 59, 63, 64, 65, 67, 70, 72, 75, 79, 81

Offset: 0

Antti Karttunen, Jun 11 2007

nonn

*A130919 = DEEPEN(*A057511) = NEPEED(*A057511) = DEEPEN(DEEPEN(*A057509)) = NEPEED(NEPEED(*A057509)). See A122283, A122284 for the definitions of DEEPEN and NEPEED transforms.

Inverse: A130920. A122351(n) = A083927(A130919(A057123(n))). The number of cycles and the number of fixed points in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A130967 and A130968. Maximum cycle sizes seems to be given by A000793 (shifted once right).

A130920 Signature permutation of a Catalan automorphism: DEEPEN-transform of automorphism *A057512.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 14, 10, 16, 19, 11, 15, 12, 17, 18, 13, 20, 21, 22, 23, 37, 24, 42, 51, 25, 38, 26, 44, 47, 27, 53, 56, 60, 28, 39, 29, 43, 52, 30, 40, 31, 45, 48, 32, 54, 49, 50, 33, 41, 34, 46, 55, 35, 57, 58, 62, 36, 61, 59, 63, 64, 65, 107, 66, 121, 149, 67

Offset: 0

Antti Karttunen, Jun 11 2007

nonn

*A130920 = DEEPEN(*A057512) = NEPEED(*A057512) = DEEPEN(DEEPEN(*A057510)) = NEPEED(NEPEED(*A057510)). See A122283, A122284 for the definitions of DEEPEN and NEPEED transforms.

Inverse: A130919. A122351(n) = A083927(A130920(A057123(n))).

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

A071152 Łukasiewicz words for the rooted plane binary trees (interpretation d in Stanley's exercise 19) with the last leaf implicit, i.e., these words are given without the last trailing zero, except for the null tree which is encoded as 0.

Original entry on oeis.org

0, 20, 2020, 2200, 202020, 202200, 220020, 220200, 222000, 20202020, 20202200, 20220020, 20220200, 20222000, 22002020, 22002200, 22020020, 22020200, 22022000, 22200020, 22200200, 22202000, 22220000, 2020202020, 2020202200

Offset: 0

Antti Karttunen, May 14 2002

nonn

Paolo Xausa, Table of n, a(n) for n = 0..23713
Indranil Ghosh, Python program for computing this sequence
Antti Karttunen, Collection of source-code for this and similar sequences in Internet Archive (Look especially in the first three modules, gatomain.scm, gatorank.scm and gatoaltr.scm. To be replaced later with a stand-alone code.)
R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
R. P. Stanley, Exercises on Catalan and Related Numbers
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz

a(n) = 2*A063171(n) = A071153(A057123(n)).

Cf. A014486, A059984, A059985, A071153, A071154, A079436.

balancedQ[0] = True; balancedQ[n_] := (s = 0; Do[s += If[b == 1, 1, -1]; If[s < 0, Return[False]], {b, IntegerDigits[n, 2]}]; Return[s == 0]); 2*FromDigits /@ IntegerDigits[ Select[Range[0, 684], balancedQ], 2] (* Jean-François Alcover, Jul 24 2013 *)
Array[Map[FromDigits[# /. -1->0]*20 &, Select[Permutations[Join[Table[-1, #-1], Table[1,#]]], Min[Accumulate[#]] >=0 &]]&, 6, 0] (* Paolo Xausa, Mar 12 2024 *)

from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A071152_gen(): # generator of terms
    yield 0
    for l in count(1):
        for s in multiset_permutations('0'*l+'1'*(l-1)):
            c, m = 0, (l<<1)-1
            for i in range(m):
                if s[i] == '1':
                    c += 2
                if cA071152_list = list(islice(A071152_gen(),30)) # Chai Wah Wu, Nov 28 2023

a(n) = 2*A063171(n).

A122300 Row 2 of A122283 and A122284. An involution of nonnegative integers.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 14, 16, 19, 11, 15, 12, 17, 20, 13, 18, 21, 22, 23, 24, 25, 26, 27, 37, 38, 42, 44, 53, 51, 47, 56, 60, 28, 29, 39, 43, 52, 30, 40, 31, 45, 46, 34, 54, 57, 61, 33, 41, 32, 48, 55, 35, 49, 58, 62, 36, 50, 59, 63, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Sep 01 2006

nonn

The signature-permutation of the automorphism which is derived from the second non-recursive automorphism *A072796 either with recursion schema DEEPEN or NEPEED. (see A122283, A122284 for their definitions).

Index entries for signature-permutations of Catalan automorphisms

A057163(n) = A083927(A122300(A057123(n))).

A122313 Row 8 of A122283.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 6, 8, 9, 10, 11, 12, 13, 17, 18, 16, 14, 15, 21, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 34, 36, 45, 46, 48, 49, 50, 44, 47, 42, 37, 38, 43, 39, 40, 41, 58, 59, 56, 51, 52, 57, 53, 54, 55, 63, 60, 61, 62, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Sep 01 2006

nonn

The signature-permutation of the automorphism which is derived from the eighth non-recursive automorphism *A072797 with recursion schema DEEPEN (see A122283 for the definition).

Index entries for signature-permutations of Catalan automorphisms

Inverse: A122314. A082325(n) = A083927(A122313(A057123(n))). Differs from A069775 for the first time at n=34, where a(n)=35, while A069775(n)=34.

A122314 Row 8 of A122284.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 6, 8, 9, 10, 11, 12, 13, 17, 18, 16, 14, 15, 20, 21, 19, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 34, 36, 45, 46, 48, 49, 50, 44, 47, 42, 37, 38, 43, 39, 40, 41, 54, 55, 57, 58, 59, 53, 56, 51, 52, 61, 62, 63, 60, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Sep 01 2006

nonn

The signature-permutation of the automorphism which is derived from the eighth non-recursive automorphism *A072797 with recursion schema NEPEED (see A122284 for the definition).

Index entries for signature-permutations of Catalan automorphisms

Inverse: A122313. A082326(n) = A083927(A122314(A057123(n))). Differs from A069776 for the first time at n=34, where a(n)=35, while A069776(n)=34.

A123502 Signature permutation of a Catalan automorphism: first recurse into the left subtree of the right hand side subtree of a binary tree and after that apply *A123498 at the root.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 5, 6, 8, 9, 10, 17, 16, 18, 11, 20, 12, 14, 15, 13, 19, 21, 22, 23, 24, 25, 26, 27, 45, 46, 44, 42, 49, 48, 43, 47, 50, 28, 29, 54, 53, 55, 30, 57, 31, 37, 38, 32, 39, 40, 41, 33, 61, 34, 51, 52, 35, 56, 58, 59, 36, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

Index entries for signature-permutations of Catalan automorphisms

Inverse: A123501. A057502(n) = A083927(a(A057123(n))) = A083927(A085160(A057123(n))).

A083930 Map from binary trees of size n to the set of corresponding trivalent plane trees (tpt) represented as size 2n+1 general trees.

Original entry on oeis.org

0, 7, 49, 57, 439, 452, 515, 541, 585, 4612, 4631, 4757, 4795, 4865, 5455, 5468, 5744, 5795, 5865, 6268, 6294, 6433, 6688, 53200, 53226, 53448, 53500, 53604, 54935, 54954, 55430, 55501, 55605, 56356, 56394, 56601, 57003, 63294, 63313, 63439

Offset: 0

Antti Karttunen, May 13 2003

nonn

Inverse function: A083929. Positions of A083936 in A014486.

a(n) = A057548(A057123(n)).

cp's OEIS Frontend

A123501 Signature permutation of a Catalan automorphism: apply *A123497 at the root, then recurse into the left subtree of the right hand side subtree of a binary tree.

Views

Author

Keywords

Links

Crossrefs

A130919 Signature permutation of a Catalan automorphism: DEEPEN-transform of automorphism *A057511.

Views

Author

Keywords

Comments

Links

Crossrefs

A130920 Signature permutation of a Catalan automorphism: DEEPEN-transform of automorphism *A057512.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Sage

A071152 Łukasiewicz words for the rooted plane binary trees (interpretation d in Stanley's exercise 19) with the last leaf implicit, i.e., these words are given without the last trailing zero, except for the null tree which is encoded as 0.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

A122300 Row 2 of A122283 and A122284. An involution of nonnegative integers.

Views

Author

Keywords

Comments

Links

Crossrefs

A122313 Row 8 of A122283.

Views

Author

Keywords

Comments

Links

Crossrefs

A122314 Row 8 of A122284.

Views

Author

Keywords

Comments

Links

Crossrefs

A123502 Signature permutation of a Catalan automorphism: first recurse into the left subtree of the right hand side subtree of a binary tree and after that apply *A123498 at the root.

Views

Author

Keywords

Links

Crossrefs

A083930 Map from binary trees of size n to the set of corresponding trivalent plane trees (tpt) represented as size 2n+1 general trees.

Views

Author

Keywords

Crossrefs

Formula