A057506 -id:A057506 - cp's OEIS frontend

A122287 Signature permutations of FORK-transformations of Catalan automorphisms in table A122204.

0, 1, 0, 2, 1, 0, 3, 3, 1, 0, 4, 2, 2, 1, 0, 5, 7, 3, 2, 1, 0, 6, 8, 4, 3, 2, 1, 0, 7, 6, 6, 5, 3, 2, 1, 0, 8, 5, 5, 4, 5, 3, 2, 1, 0, 9, 4, 7, 6, 6, 6, 3, 2, 1, 0, 10, 17, 8, 7, 4, 5, 6, 3, 2, 1, 0, 11, 18, 9, 8, 7, 4, 4, 4, 3, 2, 1, 0, 12, 20, 14, 13, 8, 7, 5, 5, 4, 3, 2, 1, 0, 13, 21, 11, 12, 13

Offset: 0

Antti Karttunen, Sep 01 2006, Jun 20 2007

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122204 with the recursion scheme "FORK", or equivalently row n is obtained as FORK(ENIPS(n-th row of A089840)). See A122201 and A122204 for the description of FORK and ENIPS. Moreover, each row of A122287 can be obtained as the "DEEPEN" transform of the corresponding row in A122286. (See A122283 for the description of DEEPEN). Each row occurs only once in this table. Inverses of these permutations can be found in table A122288. This table contains also all the rows of A122201 and A089840.

A. Karttunen, paper in preparation, draft available by e-mail.

Index entries for signature-permutations of Catalan automorphisms

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A069767, 2: A057164, 3: A130981, 4: A130983, 5: A130982, 6: A130984, 7: A130986, 8: A130988, 9: A130994, 10: A130992, 11: A130990, 12: A057506, 13: A131004, 14: A131006, 15: A057163, 16: A131008, 17: A131010, 18: A130996, 19: A130998, 20: A131002, 21: A131000. Other rows: 169: A122353, 3617: A057511, 65167: A074681.

A080069 a(n) = A014486(A080068(n)).

Original entry on oeis.org

0, 2, 10, 44, 178, 740, 2868, 11852, 47522, 190104, 735842, 3090116, 11777124, 48557252, 194656036, 778669672, 3117617996, 12677727330, 49850271300, 192901051976, 795560529352, 3243898094388, 12977884832332, 51055591319170

Offset: 0

Antti Karttunen, Jan 27 2003

Note that A080068 can be also obtained as iteration of A072795 o A057506.

Antti Karttunen, Table of n, a(n) for n = 0..512
Antti Karttunen, Python program for computing this sequence and the associated image. (this replaces the old a080069.py.txt)
Antti Karttunen, Terms a(1)-a(512) drawn as binary strings.
Antti Karttunen, Terms a(1)-a(2048) drawn as binary strings.

Same sequence in binary: A080070. Compare with similar Wolframesque plots given in A122229, A122232, A122235, A122239, A122242, A122245, A328111.

Cf. A179758.

Python
```
# See attached program
```

Python program and Wolfram-like plot added by Antti Karttunen, Sep 14 2006

A080967 Orbit size of each tree encoded by A014486(n) under Donaghey's "Map M" Catalan automorphism.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 3, 3, 2, 2, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 6, 6, 6, 3, 6, 3, 2, 6, 3, 6, 5, 6, 6, 6, 6, 3, 5, 6, 6, 5, 6, 6, 6, 5, 5, 3, 6, 3, 6, 3, 6, 2, 6, 3, 3, 6, 6, 6, 6, 6, 2, 2, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 20, 6, 6, 6, 6, 6, 24, 6, 6, 24, 6, 6, 6, 24, 24, 6, 6, 6, 6, 24, 20, 24, 2, 24, 6

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

This is the size of the cycle containing n in the permutations A057505/A057506.

Cf. A080311, A080968, A080969, A080972.

A080292 Orbit size of each tree A080293(n) under Donaghey's "Map M" Catalan automorphism.

Original entry on oeis.org

1, 3, 9, 9, 81, 81, 81, 27, 1701, 1701, 1701, 1701, 2673, 2673, 891, 891

Offset: 0

Antti Karttunen, Mar 02 2003

This is the size of the cycle containing A080295(n) in the permutations A057505/A057506.

A080977(n) = A080272(2*n)/a(n). A080302(n) = a(n)/3 for n>0. Cf. A080973/A080975.

a(n) = A080967(A080295(n))

A080972 a(n) = A080969(n)/A080967(A080979(A080970(n))).

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 2, 1, 4, 1, 2, 1, 2, 2, 3, 3, 1, 2, 2, 1, 2, 4, 1, 1, 2, 1, 4, 4, 1, 2, 2, 1, 2, 4, 1, 2, 4, 2, 4, 1, 1, 4, 4, 1, 4, 1, 2, 1, 4, 4, 2, 1, 4, 4, 2, 4, 4, 2, 1

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

Donaghey shows in his paper that the orbit size (under the automorphism A057505/A057506) of each non-branch-reduced tree encoded by A080971(n) is divisible by the orbit size of the corresponding branch-reduced tree. This sequence gives the corresponding ratio.

Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.

A080981 A014486-encodings of the trees whose interior zigzag-tree (Stanley's c) is branch-reduced (in the sense defined by Donaghey).

Original entry on oeis.org

0, 2, 10, 12, 44, 50, 52, 178, 180, 204, 210, 216, 228, 716, 722, 728, 740, 818, 820, 844, 866, 868, 872, 914, 920, 932, 2866, 2868, 2892, 2914, 2916, 2920, 2962, 2968, 2980, 3276, 3282, 3288, 3300, 3378, 3380, 3468, 3474, 3480, 3490, 3492, 3504, 3528, 3660

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

Donaghey defines (on page 82 of his paper) the branch-reduced zigzag-trees as those zigzag-trees which do not contain longer than one-edge branches, where a branch is a maximal connected set of edges slanted to the same direction, with no perpendicular edges emanating from its middle. These form the primitive elements of the automorphism A057505/A057506.

Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
Antti Karttunen, Initial terms illustrated in positions 0, 1, 2, 3, 5, 6, 7, 11, 12, 15, 16, 18, 20, 29, 30, 32, ...

a(n) = A014486(A080980(n)). Cf. A080968, A080971. These trees are enumerated by A005554.

a(n) = A014486(A080980(n)).

A080968 Orbit size of each branch-reduced tree encoded by A080981(n) under Donaghey's "Map M" Catalan automorphism.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 3, 6, 6, 6, 6, 6, 6, 3, 2, 3, 5, 3, 5, 5, 5, 5, 3, 3, 2, 3, 6, 24, 24, 24, 24, 6, 24, 24, 24, 6, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 6, 24, 24, 24, 24, 24, 6, 24, 24, 6, 3, 18, 9, 24, 18, 18, 9, 18, 9, 18, 18, 3, 24, 15, 15, 24, 24, 18, 15, 15, 24, 3, 24, 24, 15, 15, 24

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

This is the size of the cycle containing A080980(n) in the permutations A057505/A057506.

If the conjecture given in A080070 is true, then this sequence contains only six 2's. Questions: are there any (other) values with finite number of occurrences? Which primes will eventually appear?

Cf. A080969, A080972.

a(n) = A080967(A080980(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

A080272 Orbit size of each tree A080263(n) under Donaghey's "Map M" Catalan automorphism.

Original entry on oeis.org

1, 3, 3, 27, 54, 54, 18, 1134, 1134, 1134, 1134, 1782, 1782, 594, 594, 30618, 30618, 30618, 30618, 78246, 78246, 78246, 78246, 165726, 165726

Offset: 0

Antti Karttunen, Mar 02 2003

This is the size of the cycle containing A080265(n) in the permutations A057505/A057506.

A080977(n) = a(2*n)/A080292(n).

a(n) = A080967(A080265(n)).

A080969 Orbit size of each non-branch-reduced tree encoded by A080971(n) under Donaghey's "Map M" Catalan automorphism.

Original entry on oeis.org

2, 2, 2, 6, 6, 6, 6, 6, 6, 2, 2, 6, 6, 6, 3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 3, 6, 6, 6, 3, 6, 6, 6, 6, 6, 2, 2, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 20, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 20, 2, 6, 6, 6, 20, 20, 6, 6, 6, 6, 6, 20, 6, 6, 20, 6, 20, 6, 6, 20, 20, 6, 20, 6, 6, 6, 20, 20, 6, 6, 20, 20, 6, 20

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

This is the size of the cycle containing A080970(n) in the permutations A057505/A057506.

Cf. A080968, A080972.

a(n) = A080967(A080970(n))

cp's OEIS Frontend

A122287 Signature permutations of FORK-transformations of Catalan automorphisms in table A122204.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A080069 a(n) = A014486(A080068(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Extensions

A080967 Orbit size of each tree encoded by A014486(n) under Donaghey's "Map M" Catalan automorphism.

Views

Author

Keywords

Comments

Crossrefs

A080292 Orbit size of each tree A080293(n) under Donaghey's "Map M" Catalan automorphism.

Views

Author

Keywords

Comments

Crossrefs

Formula

A080972 a(n) = A080969(n)/A080967(A080979(A080970(n))).

Views

Author

Keywords

Comments

Links

A080981 A014486-encodings of the trees whose interior zigzag-tree (Stanley's c) is branch-reduced (in the sense defined by Donaghey).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A080968 Orbit size of each branch-reduced tree encoded by A080981(n) under Donaghey's "Map M" Catalan automorphism.

Views

Author

Keywords

Comments

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Sage

A080272 Orbit size of each tree A080263(n) under Donaghey's "Map M" Catalan automorphism.

Views

Author

Keywords

Comments

Crossrefs

Formula

A080969 Orbit size of each non-branch-reduced tree encoded by A080971(n) under Donaghey's "Map M" Catalan automorphism.

Views

Author

Keywords

Comments

Crossrefs

Formula