A080967 -id:A080967 - cp's OEIS frontend

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

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.

A057505 Signature-permutation of a Catalan Automorphism: Donaghey's map M acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

This is equivalent to map M given by Donaghey on page 81 of his paper "Automorphisms on ..." and also equivalent to the transformation procedure depicted in the picture (23) of Donaghey-Shapiro paper.

This can be also considered as a "more recursive" variant of A057501 or A057503 or A057161.

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation, vi+120pp. ISBN 0-321-33570-8 Addison-Wesley Professional; 1ST edition (Feb 06, 2006).

Antti Karttunen, Table of n, a(n) for n = 0..2055
Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
Robert Donaghey and Louis W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, Vol. 23, No. 3 (1977), pp. 291-301.
Indranil Ghosh, Python program for computing this sequence (after the functions mentioned in the OEIS wiki).
Antti Karttunen, Illustration of symmetric general trees whose A057163-reflection is also symmetric (ones that occur in 2-cycles of A057505/A057506)
Antti Karttunen, On the fixed points of A071661 (Notes in OEIS Wiki regarding the 2-cycles of this automorphism)
D. E. Knuth, Pre-Fascicle 4a: Generating All Trees, Exercise 17, 7.2.1.6.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057506.
The 2nd, 3rd, 4th, 5th and 6th "power": A071661, A071663, A071665, A071667, A071669.
Other related permutations: A057501, A057503, A057161.
Cycle counts: A057507. Maximum cycle lengths: A057545. LCM's of all cycles: A060114. See A057501 for other Maple procedures.
Row 17 of table A122288.
Cf. A080981 (the "primitive elements" of this automorphism), A079438, A079440, A079442, A079444, A080967, A080968, A080972, A080272, A080292, A083929, A080973, A081164, A123050, A125977, A126312.

map(CatalanRankGlobal,map(DonagheysM, A014486)); or map(CatalanRankGlobal,map(DeepRotateTriangularization, A014486));
DonagheysM := n -> pars2binexp(DonagheysMP(binexp2pars(n)));
DonagheysMP := h -> `if`((0 = nops(h)),h,[op(DonagheysMP(car(h))),DonagheysMP(cdr(h))]);
DeepRotateTriangularization := proc(nn) local n,s,z,w; n := binrev(nn); z := 0; w := 0; while(1 = (n mod 2)) do s := DeepRotateTriangularization(BinTreeRightBranch(n))*2; z := z + (2^w)*s; w := w + binwidth(s); z := z + (2^w); w := w + 1; n := floor(n/2); od; RETURN(z); end;

a(0) = 0, and for n>=1, a(n) = A085201(a(A072771(n)), A057548(a(A072772(n)))). [This recurrence reflects the S-expression implementation given first in the Program section: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some languages), and A057548 corresponds to unary form of function 'list'].
As a composition of related permutations:
a(n) = A057164(A057163(n)).
a(n) = A057163(A057506(A057163(n))).

A057545 Maximum cycle size in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Original entry on oeis.org

1, 1, 2, 3, 6, 6, 24, 72, 144, 147, 588, 672, 2136, 10152, 11520, 29484, 117936, 270576, 656352, 2062368, 4040160

Offset: 0

Antti Karttunen, Sep 07 2000

For the convenience of the range notation above, we define A014137(-1) and A014138(-1) as zero.
Equal to the degree of the polynomials M_n(x) Donaghey gives on the page 81 of his paper.
Factored terms: 1, 1, 2, 3, 2*3, 2*3, 2^3 * 3, 2^3 * 3^2, 2^4 * 3^2, 3 * 7^2, 2^2 * 3 * 7^2, 2^5 * 3 * 7, 2^3 * 3 * 89, 2^3 * 3^3 * 47, 2^8 * 3^2 * 5, 2^2 * 3^4 * 7 * 13, 2^4 * 3^4 * 7 * 13, 2^4 * 3^2 * 1879, 2^5 * 3^2 * 43 * 53, 2^5 * 3^3 * 7 * 11 * 31, 2^5 * 3 * 5 * 19 * 443

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

Cf. A057507, A060114, A080967, A081165.

Occurs for first time in A073203 as row 2614.

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

A080311 Orbit size of each tree encoded by A014486(n) under Meeussen's bf<->df map on binary trees.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 4, 3, 2, 4, 3, 4, 3, 2, 4, 1, 1, 3, 3, 3, 4, 3, 2, 4, 3, 4, 3, 2, 4, 16, 16, 8, 16, 8, 2, 2, 16, 16, 16, 8, 8, 8, 16, 16, 16, 16, 8, 8, 16, 8, 2, 2, 16, 16, 16, 16, 16, 1, 1, 3, 3, 3, 4, 3, 2, 4, 3, 4, 3, 2, 4, 16, 16, 8, 16, 8, 2, 2, 16, 16, 16, 8, 8, 8, 16

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

This is the size of the cycle containing n in the permutations A057117/A057118.

Cf. A080967, A080273, A080274, A080297.

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

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

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

Views

Author

Keywords

Comments

Links

A057505 Signature-permutation of a Catalan Automorphism: Donaghey's map M acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Formula

A057545 Maximum cycle size in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Crossrefs

Formula

A080311 Orbit size of each tree encoded by A014486(n) under Meeussen's bf<->df map on binary trees.

Views

Author

Keywords

Comments

Crossrefs

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

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