A080981 -id:A080981 - cp's OEIS frontend

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

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

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

A005554 Sums of successive Motzkin numbers.

Original entry on oeis.org

1, 2, 3, 6, 13, 30, 72, 178, 450, 1158, 3023, 7986, 21309, 57346, 155469, 424206, 1164039, 3210246, 8893161, 24735666, 69051303, 193399578, 543310782, 1530523638, 4322488212, 12236130298, 34713220977, 98677591278

Offset: 1

N. J. A. Sloane

nonn

The Donaghey reference shows that a(n) is the number of n-vertex binary trees such that for each non-root vertex that is incident to exactly two edges, these two edges have opposite slope. It also notes that these trees correspond to Dyck n-paths (A000108) containing no DUDUs and no subpaths of the form UUPDD with P a nonempty Dyck path. For example, a(3)=3 counts UUDUDD, UDUUDD, UUDDUD. - David Callan, Sep 25 2006

Hankel transform of the sequence starting with 2 appears to be 3, 4, 5, 6, 7, ... Gary W. Adamson, May 27 2011

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
Rosa Orellana, Nancy Wallace, and Mike Zabrocki, Quasipartition and planar quasipartition algebras, Sém. Lotharingien Comb., Proc. 36th Conf. Formal Power Series Alg. Comb. (2024) Vol. 91B, Art. No. 50. See p. 11.
Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 99.

Enumerates the branch-reduced trees encoded by A080981. Cf. A001006.
First differences are in A102071.
Cf. A014138.
A diagonal of A059346.

Rest[CoefficientList[Series[(x+x^2)*(1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2), {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 21 2014 *)

a(n):=(2*sum(binomial(n,j)*binomial(n-j+1,n-2*j+2),j,0,(n+2)/2))/n; /* Vladimir Kruchinin, Oct 04 2015 */

a(n) = sum(k=0, (n+2)/2, 2*(binomial(n,k)*binomial(n-k+1,n-2*k+2)/n));
vector(40, n, if(n==1, 1, a(n-1))) \\ Altug Alkan, Oct 04 2015

Inverse binomial transform of A014138: (1, 3, 8, 22, 64, 196, ...). - Gary W. Adamson, Nov 23 2007
D-finite with recurrence (n + 1)*a(n) = 2*n*a(n - 1) + (3*n - 9)*a(n - 2).
G.f.: (x+x^2)*M(x) where M(x)=(1 - x - (1 - 2*x - 3*x^2)^(1/2))/(2*x^2) is the g.f. for the Motzkin numbers A001006. - David Callan, Sep 25 2006
a(n) = (-1)^n*2*hypergeometric([2-n,5/2],[4],4), for n>1. - Peter Luschny, Aug 15 2012
a(n) ~ 2*3^(n-1/2)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 21 2014
a(n) = (2*Sum_{j=0..(n+2)/2} (binomial(n,j)*binomial(n-j+1,n-2*j+2)))/n. - Vladimir Kruchinin, Oct 04 2015

More terms from James Sellers, Jul 10 2000

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

Original entry on oeis.org

42, 56, 170, 172, 184, 202, 212, 226, 232, 240, 682, 684, 690, 692, 696, 714, 724, 738, 744, 752, 810, 812, 824, 842, 850, 852, 856, 880, 906, 908, 916, 930, 936, 944, 962, 964, 968, 976, 992, 2730, 2732, 2738, 2740, 2744, 2762, 2764, 2770, 2772, 2776, 2786

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
Antti Karttunen, Initial terms illustrated in positions 4, 8, 9, 10, 13, 14, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28, 31, ...

Cf. A014486, A080970, A080981.

a(n) = A014486(A080970(n)).

A080980 A014486-indices 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, 1, 2, 3, 5, 6, 7, 11, 12, 15, 16, 18, 20, 29, 30, 32, 34, 39, 40, 43, 47, 48, 49, 53, 55, 57, 81, 82, 85, 89, 90, 91, 95, 97, 99, 113, 114, 116, 118, 123, 124, 136, 137, 139, 140, 141, 143, 146, 155, 159, 160, 161, 165, 167, 173, 183, 245, 246, 248, 250, 255, 256, 268

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
R. P. Stanley, Exercises on Catalan and Related Numbers

Cf. A080979. a(n) = A080300(A080981(n)). See comment at A080981. Complement of A080970.

cp's OEIS Frontend

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

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

A005554 Sums of successive Motzkin numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs