login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A057503 Signature-permutation of a Catalan Automorphism: Deutsch's 1998 bijection on Dyck paths. 11
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, 58, 62, 50, 49, 46, 45, 48, 55, 54, 57, 61, 36, 35, 32, 31, 34, 27, 26, 24, 23, 25, 29, 28, 30, 33, 41, 40, 38, 37, 39, 43, 42, 44, 47, 52, 51, 53, 56, 60, 196, 195, 190, 189, 194 (list; graph; refs; listen; history; text; internal format)
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
Emeric Deutsch, A bijection on Dyck paths and its consequences, Discrete Math., 179 (1998), 253-256.
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:
A057515(n) = A080237(a(n)) holds for all n. [See the Comments section.]
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):
(definec (A057503 n) (if (zero? n) n (A085201bi (A072771 n) (A057548 (A057503 (A072772 n)))))) ;; A085201bi, see: A085201.
CROSSREFS
Inverse: A057504. Row 17 of A122285. Cf. A057501, A057161, A057505.
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).
Sequence in context: A131162 A364390 A131172 * A074684 A131003 A082358
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:22 EDT 2024. Contains 370951 sequences. (Running on oeis4.)