OFFSET
0,3
COMMENTS
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.
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
LINKS
Antti Karttunen, Table of n, a(n) for n = 0..2055
Emeric Deutsch, A bijection on Dyck paths and its consequences, Discrete Math., 179 (1998), 253-256.
Antti Karttunen, C program which computes this sequence..
Antti Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 53-54.
FORMULA
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'].
a(n) = A057164(A057162(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 144.]
Other identities:
PROG
(Scheme implementations of this automorphism that acts on S-expressions, i.e., list-structures):
(Constructive implementation): (define (*A057503 a) (cond ((null? a) a) (else (append (car a) (list (*A057503 (cdr a)))))))
(Another implementation): (define (*A057503 s) (fold-right (lambda (x y) (append x (list y))) '() s))
(Destructive implementation): (define (*A057503! s) (cond ((pair? s) (*A057503! (cdr s)) (*A057501! s))) s)
;; A version working directly on nonnegative integers (definec is a memoization macro from Antti Karttunen's IntSeq-library):
CROSSREFS
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).
KEYWORD
nonn
AUTHOR
Antti Karttunen, Sep 03 2000
EXTENSIONS
Equivalence with Emeric Deutsch's 1998 bijection realized Dec 15 2006 and entry edited accordingly by Antti Karttunen, Jan 16 2007
STATUS
approved