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
A. Karttunen, Catalan Automorphisms
R. P. Stanley, Exercises on Catalan and Related Numbers (including 66 combinatorial interpretations)
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)..............
...(())((())()()).................................
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
KEYWORD
nonn
AUTHOR
Antti Karttunen, Jun 23 2003
STATUS
approved