A057503 - OEIS

%I #25 Jan 14 2024 04:37:20

%S 0,1,3,2,8,7,5,4,6,22,21,18,17,20,13,12,10,9,11,15,14,16,19,64,63,59,

%T 58,62,50,49,46,45,48,55,54,57,61,36,35,32,31,34,27,26,24,23,25,29,28,

%U 30,33,41,40,38,37,39,43,42,44,47,52,51,53,56,60,196,195,190,189,194

%N Signature-permutation of a Catalan Automorphism: Deutsch's 1998 bijection on Dyck paths.

%C Deutsch shows in his 1998 paper that this automorphism maps the number of returns of Dyck path to the height of the last peak, i.e., that A057515(n) = A080237(A057503(n)) holds for all n, thus the two parameters have the same distribution.

%C From the recursive forms of A057161 and A057503 it is seen that both can be viewed as a convergent limits of a process where either the left or right side argument of A085201 in formula for A057501 is "iteratively recursivized", and on the other hand, both of these can then in turn be made to converge towards A057505, when the other side of the formula is also "recursivized" in the same way. - _Antti Karttunen_, Jun 06 2014

%H Antti Karttunen, <a href="/A057503/b057503.txt">Table of n, a(n) for n = 0..2055</a>

%H Emeric Deutsch, <a href="https://doi.org/10.1016/S0012-365X(97)00097-6">A bijection on Dyck paths and its consequences</a>, Discrete Math., 179 (1998), 253-256.

%H Antti Karttunen, <a href="/A089408/a089408.c.txt">C program which computes this sequence.</a>.

%H Antti Karttunen, <a href="http://web.archive.org/web/20121004142217/http://ndirty.cute.fi/~karttu/matikka/Nekomorphisms/CatBijections.pdf">Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft)</a>, pp. 53-54.

%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(A072771(n), A057548(a(A072772(n)))). [This formula 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 the unary form of function 'list'].

%F a(n) = A057164(A057162(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 144.]

%F Other identities:

%F A057515(n) = A080237(a(n)) holds for all n. [See the Comments section.]

%o (Scheme implementations of this automorphism that acts on S-expressions, i.e., list-structures):

%o (Constructive implementation): (define (*A057503 a) (cond ((null? a) a) (else (append (car a) (list (*A057503 (cdr a)))))))

%o (Another implementation): (define (*A057503 s) (fold-right (lambda (x y) (append x (list y))) '() s))

%o (Destructive implementation): (define (*A057503! s) (cond ((pair? s) (*A057503! (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 (A057503 n) (if (zero? n) n (A085201bi (A072771 n) (A057548 (A057503 (A072772 n)))))) ;; A085201bi, see: A085201.

%Y Inverse: A057504. Row 17 of A122285. Cf. A057501, A057161, A057505.

%Y The number of cycles, count of the fixed points, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n)] of this permutation are given by LEFT(LEFT(A001683)), LEFT(A019590), A057544 and A057544, the same sequences as for A057162 because this is a conjugate of it (cf. the Formula section).

%K nonn

%O 0,3

%A _Antti Karttunen_, Sep 03 2000

%E Equivalence with _Emeric Deutsch_'s 1998 bijection realized Dec 15 2006 and entry edited accordingly by _Antti Karttunen_, Jan 16 2007