A085161 Involution of natural numbers induced by Catalan Automorphism *A085161 acting on symbolless S-expressions encoded by A014486/A063171.

0, 1, 2, 3, 4, 7, 6, 5, 8, 9, 17, 14, 12, 21, 11, 20, 16, 10, 18, 19, 15, 13, 22, 23, 45, 37, 31, 58, 28, 54, 42, 26, 49, 51, 40, 35, 63, 25, 48, 39, 34, 62, 30, 57, 44, 24, 46, 56, 38, 32, 59, 33, 61, 53, 29, 55, 47, 43, 27, 50, 60, 52, 41, 36, 64, 65, 129, 107, 87, 170

Offset

0,3

Comments

This automorphism reflects the interpretations (pp)-(rr) of Stanley, obtained from the Dyck paths with the "rising slope mapping" illustrated on the example lines.

Links

Table of n, a(n) for n=0..69.

A. Karttunen, Catalan Automorphisms

R. P. Stanley, Exercises on Catalan and Related Numbers (including 66 combinatorial interpretations)

Index entries for signature-permutations induced by Catalan automorphisms

Example

Map the Dyck paths (Stanley's interpretation (i)) to noncrossing Murasaki-diagrams (Stanley's interpretation (rr)) by drawing a vertical line above each rising slope / and connect those vertical lines that originate from the same height without any lower valleys between, as in illustration below:
..................................................
...._____..___....................................
...|.|...||...|...................................
...|.||..|||..|...................._.___...___....
...|.||..|||..|...................|.|...|.|...|...
...|.||..||/\.|....i.e..equal.to..|.|.|.|.|.|.|...
...|.|/\.|/..\/\..................|.|.|.|.|.|.|...
.../\/..\/......\.................|.|.|.|.|.|.|...
...10110011100100=11492=A014486(250)..............
...()(())((())()).................................
Now this automorphism gives the parenthesization such that the corresponding Murasaki-diagram is a reflection of the original one:
....___.._____....................................
...|...||...|.|...................................
...||..|||..|.|....................___..._____....
...||..|||..|.|...................|...|.|...|.|...
...||..||/\.|.|....i.e..equal.to..|.|.|.|.|.|.|...
...|/\.|/..\/\/\..................|.|.|.|.|.|.|...
.../..\/........\.................|.|.|.|.|.|.|...
...11001110010100=13204=A014486(360)..............
...(())((())()()).................................
So we have A085161(250)=360 and A085161(360)=250.

Prog

(Scheme function implementing this automorphism on list-structures:)
(define (*A085161 s) (cond ((null? s) s) (else (let ((u (reverse s))) (app-to-xrt (*A085161 (car u)) (append (map *A085161 (cdr u)) (list (list))))))))
(define (app-to-xrt a b) (cond ((null? a) b) ((pair? (cdr a)) (cons (car a) (app-to-xrt (cdr a) b))) (else (cons (app-to-xrt (car a) b) (cdr a)))))

Crossrefs

a(n) = A085163(A057508(n)) = A074684(A057164(A074683(n))). Occurs in A073200. Cf. also A085159, A085160, A085162, A085175. Alternative mappings illustrated in A086431 & A085169.

Number of cycles: A007123. Number of fixed points: A001405 (in each range limited by A014137 and A014138).

Sequence in context: A270426 A270425 A332212 * A085162 A182178 A326316

Adjacent sequences: A085158 A085159 A085160 * A085162 A085163 A085164

Keyword

nonn

Author

Antti Karttunen, Jun 23 2003

Status

approved