A057505 - OEIS

%I #41 Jan 11 2024 09:03:47

%S 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 62,58,50,49,55,61,57,46,48,54,45,36,35,32,34,31,41,40,52,60,56,43,47,

%U 53,44,27,26,29,33,30,38,39,51,42,24,25,28,37,23,196,195,190,194,189

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

%C 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 This can be also considered as a "more recursive" variant of A057501 or A057503 or A057161.

%D 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 Antti Karttunen, <a href="/A057505/b057505.txt">Table of n, a(n) for n = 0..2055</a>

%H 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 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 Indranil Ghosh, <a href="/A057505/a057505_1.txt">Python program for computing this sequence</a> (after the functions mentioned in the OEIS wiki).

%H 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 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 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 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>

%F 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 As a composition of related permutations:

%F a(n) = A057164(A057163(n)).

%F a(n) = A057163(A057506(A057163(n))).

%p map(CatalanRankGlobal,map(DonagheysM, A014486)); or map(CatalanRankGlobal,map(DeepRotateTriangularization, A014486));

%p DonagheysM := n -> pars2binexp(DonagheysMP(binexp2pars(n)));

%p DonagheysMP := h -> `if`((0 = nops(h)),h,[op(DonagheysMP(car(h))),DonagheysMP(cdr(h))]);

%p 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 (Scheme functions implementing this automorphism on S-expressions, three different variants):

%o (define (*A057505 a) (cond ((null? a) a) (else (append (*A057505 (car a)) (list (*A057505 (cdr a)))))))

%o (define (*A057505 bt) (let loop ((lt bt) (nt (list))) (cond ((not (pair? lt)) nt) (else (loop (car lt) (cons (*A057505 (cdr lt)) nt))))))

%o (define (*A057505! s) (cond ((pair? s) (*A057505! (car s)) (*A057505! (cdr s)) (*A057501! s))) s)

%o ;; A version working directly on nonnegative integers (definec is a memoization macro from _Antti Karttunen_'s IntSeq-library):

%o (definec (A057505 n) (if (zero? n) n (A085201bi (A057505 (A072771 n)) (A057548 (A057505 (A072772 n)))))) ;; A085201bi, see: A085201.

%Y Inverse: A057506.

%Y The 2nd, 3rd, 4th, 5th and 6th "power": A071661, A071663, A071665, A071667, A071669.

%Y Other related permutations: A057501, A057503, A057161.

%Y Cycle counts: A057507. Maximum cycle lengths: A057545. LCM's of all cycles: A060114. See A057501 for other Maple procedures.

%Y Row 17 of table A122288.

%Y Cf. A080981 (the "primitive elements" of this automorphism), A079438, A079440, A079442, A079444, A080967, A080968, A080972, A080272, A080292, A083929, A080973, A081164, A123050, A125977, A126312.

%K nonn

%O 0,3

%A _Antti Karttunen_, Sep 03 2000