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

Author

Antti Karttunen, Jun 23 2003

Keywords

• nonn

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.

Examples

			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.
		

Links

• 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

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