A086431 Involution of natural numbers induced by the Catalan bijection gma086431 acting on symbolless S-expressions encoded by A014486/A063171.

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

Offset

0,3

Comments

This Catalan bijection reflects the interpretations (pp)-(rr) of Stanley, obtained with the "descending slope mapping" from the Dyck paths encoded by A014486.

Links

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

A. Karttunen, Noncrossing Murasaki diagrams obtained via descending slope mapping illustrated up to seven sticks

A. Karttunen, Gatomorphisms (With the complete Scheme source)

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 descending 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 the Catalan bijection gma086431 gives the parenthesization such that the corresponding Murasaki-diagram is a reflection of the original one:
.....___________..................................
....|...._..|...|.................................
....|...|.|||..||..................___________....
....|...|.|||..||.................|.._....|...|...
....|../\/\||..||..i.e..equal.to..|.|.|.|.|.|.|...
....|./....\|./\|.................|.|.|.|.|.|.|...
.../\/......\/..\.................|.|.|.|.|.|.|...
...10111010001100=11916=A014486(296)
So we have A086431(250)=296 and A086431(296)=250.

Crossrefs

a(n) = A057164(A085161(A057164(n))) = A086425(A057164(A086426(n))). Occurs in A073200. Cf. also A086427, A086430.

Number of cycles: A007123. Number of fixed points: A001405. (In range [A014137(n-1)..A014138(n-1)] of this permutation.).

Sequence in context: A342383 A371593 A358733 * A143579 A100806 A102451

Adjacent sequences: A086428 A086429 A086430 * A086432 A086433 A086434

Keyword

nonn

Author

Antti Karttunen, Jun 23 2003

Status

approved