cp's OEIS Frontend

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

%I A057505 #41 Jan 11 2024 09:03:47
%S A057505 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,
%T A057505 62,58,50,49,55,61,57,46,48,54,45,36,35,32,34,31,41,40,52,60,56,43,47,
%U A057505 53,44,27,26,29,33,30,38,39,51,42,24,25,28,37,23,196,195,190,194,189
%N A057505 Signature-permutation of a Catalan Automorphism: Donaghey's map M acting on the parenthesizations encoded by A014486.
%C A057505 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.
%C A057505 This can be also considered as a "more recursive" variant of A057501 or A057503 or A057161.
%D A057505 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).
%H A057505 Antti Karttunen, <a href="/A057505/b057505.txt">Table of n, a(n) for n = 0..2055</a>
%H A057505 Robert Donaghey, <a href="https://doi.org/10.1016/0095-8956(80)90045-3">Automorphisms on Catalan trees and bracketing</a>, J. Combin. Theory, Series B, 29 (1980), 75-90.
%H A057505 Robert Donaghey and Louis W. Shapiro, <a href="https://doi.org/10.1016/0097-3165(77)90020-6">Motzkin numbers</a>, J. Combin. Theory, Series A, Vol. 23, No. 3 (1977), pp. 291-301.
%H A057505 Indranil Ghosh, <a href="/A057505/a057505_1.txt">Python program for computing this sequence</a> (after the functions mentioned in the OEIS wiki).
%H A057505 Antti Karttunen, <a href="https://oeis.org/A079438/a079438.pdf">Illustration of symmetric general trees whose A057163-reflection is also symmetric (ones that occur in 2-cycles of A057505/A057506)</a>
%H A057505 Antti Karttunen, <a href="https://oeis.org/wiki/User:Antti_Karttunen/Speculations/On_the_fixed_points_of_A071661">On the fixed points of A071661</a> (Notes in OEIS Wiki regarding the 2-cycles of this automorphism)
%H A057505 D. E. Knuth, <a href="http://www-cs-staff.Stanford.EDU/~knuth/fasc4a.ps.gz">Pre-Fascicle 4a: Generating All Trees</a>, Exercise 17, 7.2.1.6.
%H A057505 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>
%F A057505 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'].
%F A057505 As a composition of related permutations:
%F A057505 a(n) = A057164(A057163(n)).
%F A057505 a(n) = A057163(A057506(A057163(n))).
%p A057505 map(CatalanRankGlobal,map(DonagheysM, A014486)); or map(CatalanRankGlobal,map(DeepRotateTriangularization, A014486));
%p A057505 DonagheysM := n -> pars2binexp(DonagheysMP(binexp2pars(n)));
%p A057505 DonagheysMP := h -> `if`((0 = nops(h)),h,[op(DonagheysMP(car(h))),DonagheysMP(cdr(h))]);
%p A057505 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;
%o A057505 (Scheme functions implementing this automorphism on S-expressions, three different variants):
%o A057505 (define (*A057505 a) (cond ((null? a) a) (else (append (*A057505 (car a)) (list (*A057505 (cdr a)))))))
%o A057505 (define (*A057505 bt) (let loop ((lt bt) (nt (list))) (cond ((not (pair? lt)) nt) (else (loop (car lt) (cons (*A057505 (cdr lt)) nt))))))
%o A057505 (define (*A057505! s) (cond ((pair? s) (*A057505! (car s)) (*A057505! (cdr s)) (*A057501! s))) s)
%o A057505 ;; A version working directly on nonnegative integers (definec is a memoization macro from _Antti Karttunen_'s IntSeq-library):
%o A057505 (definec (A057505 n) (if (zero? n) n (A085201bi (A057505 (A072771 n)) (A057548 (A057505 (A072772 n)))))) ;; A085201bi, see: A085201.
%Y A057505 Inverse: A057506.
%Y A057505 The 2nd, 3rd, 4th, 5th and 6th "power": A071661, A071663, A071665, A071667, A071669.
%Y A057505 Other related permutations: A057501, A057503, A057161.
%Y A057505 Cycle counts: A057507. Maximum cycle lengths: A057545. LCM's of all cycles: A060114. See A057501 for other Maple procedures.
%Y A057505 Row 17 of table A122288.
%Y A057505 Cf. A080981 (the "primitive elements" of this automorphism), A079438, A079440, A079442, A079444, A080967, A080968, A080972, A080272, A080292, A083929, A080973, A081164, A123050, A125977, A126312.
%K A057505 nonn
%O A057505 0,3
%A A057505 _Antti Karttunen_, Sep 03 2000