A080292 -id:A080292 - cp's OEIS frontend

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

1, 1, 6, 2, 14, 14, 22, 22, 18, 18, 46, 46, 62, 62, 26, 26

Offset: 0

Antti Karttunen, Mar 02 2003

This gives the orbit size (under the Catalan bijection A057505) for every other binomial-mod-2 tree A080263(2*n) divided by the orbit size of the corresponding branch-reduced tree A080293(n). See comment at A080972.

A080302 a(n) = A080292(n)/3.

Original entry on oeis.org

1, 3, 3, 27, 27, 27, 9, 567, 567, 567, 567, 891, 891, 297, 297

Offset: 1

Antti Karttunen, Mar 02 2003

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

A080293 A014486-encoding of the branch-reduced binomial-mod-2 binary trees.

Original entry on oeis.org

2, 50, 14642, 3969842, 267572689202, 69427226972978, 4581045692538239282, 301220569271221714981682, 1295918094920364850246919050705202, 332029112115571675270693117549056818

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

These are obtained from the stunted binomial-mod-2 zigzag trees (A080263) either by extending each leaf to a branch of two leaves, or by branch-reducing every other such tree.

a(n) = A014486(A080295(n)). Same sequence in binary: A080294. Breadth-first-wise encoding: A080318. "Moose-trees" obtained from these: A080973. Cf. A080292, A080297.

a(n) = A080310(A080263(n)) = A014486(A080298(A080265(n))) = A014486(A080979(A080265(2*n)))

A080973 A014486-encoding of the "Moose trees".

Original entry on oeis.org

2, 52, 14952, 4007632, 268874213792, 68836555442592, 4561331969745081152, 300550070677246403229312, 1294530259719904904564091957759232, 331402554328705507772604330809117952

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

Meeussen's observation about the orbits of a composition of two involutions F and R states that if the orbit size of the composition (acting on a particular element of the set) is odd, then it contains an element fixed by the other involution if and only if it contains also an element fixed by the other, on the (almost) opposite side of the cycle. Here those two involutions are A057163 and A057164, their composition is Donaghey's "Map M" A057505 and as the trees A080293/A080295 are symmetric as binary trees and the cycle sizes A080292 are odd, it follows that these are symmetric as general trees.

Antti Karttunen, Initial terms illustrated

Same sequence in binary: A080974. A036044(a(n)) = a(n) for all n. The number of edges (as general trees): A080978.

a(n) = A014486(A080975(n)) = A014486(A057505^((A080292(n)+1)/2) (A080293(n))) [where ^ stands for the repeated applications of permutation A057505.]

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

A080975 A014486-index of the "Moose trees".

Original entry on oeis.org

1, 7, 515, 73211, 2249220471, 431283926958, 18838905762720934, 896134321804401371660, 2333852111980919691995847581921, 537961368577436933017494169487235

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

See A080973 for illustration and comments.

A057164(a(n)) = a(n) for all n. Cf. A080976.

a(n) = A057505^((A080292(n)+1)/2) (A080293(n)) [where ^ stands for the repeated applications of permutation A057505.]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

A080302 a(n) = A080292(n)/3.

Views

Author

Keywords

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

A080293 A014486-encoding of the branch-reduced binomial-mod-2 binary trees.

Views

Author

Keywords

Comments

Crossrefs

Formula

A080973 A014486-encoding of the "Moose trees".

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Crossrefs

Formula

A080975 A014486-index of the "Moose trees".

Views

Author

Keywords

Comments

Crossrefs

Formula