

A057503


Signaturepermutation 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


REFERENCES

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


LINKS

Antti Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Cprogram which computes this sequence.
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 5354.
Index entries for signaturepermutations of Catalan automorphisms


FORMULA

a(0) = 0, and for n>=1, a(n) = A085201(A072771(n), A057548(a(A072772(n)))). [This formula reflects the Sexpression implementation given first in the Program section: A085201 is a 2ary 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. 5354 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 Sexpressions, i.e. liststructures):
(Constructive implementation): (define (*A057503 a) (cond ((null? a) a) (else (append (car a) (list (*A057503 (cdr a)))))))
(Another implementation): (define (*A057503 s) (foldright (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 IntSeqlibrary):
(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(n1)..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


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



