This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(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)



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


E. Deutsch, A bijection on Dyck paths and its consequences, Discrete Math., 179 (1998), 253-256.


Antti Karttunen, Table of n, a(n) for n = 0..2055

A. Karttunen, C-program which computes this sequence.

A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 53-54.

Index entries for signature-permutations of Catalan automorphisms


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]


(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.


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: A122361 A131162 A131172 * A074684 A131003 A082358

Adjacent sequences:  A057500 A057501 A057502 * A057504 A057505 A057506




Antti Karttunen, Sep 03 2000


Equivalence with Emeric Deutsch's 1998 bijection realized Dec 15 2006 and entry edited accordingly by Antti Karttunen, Jan 16 2007



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 16:49 EST 2019. Contains 319235 sequences. (Running on oeis4.)