A086431 -id:A086431 - cp's OEIS frontend

A085169 Permutation of natural numbers induced by the Catalan bijection gma085169 acting on symbolless S-expressions encoded by A014486/A063171.

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

A parenthesization is fixed by the Catalan bijections A085169/A085170 if and only if no other elements than () and (()) occur at its top-level: (); ()(),(()); ()()(),()(()),(())(); ()()()(),()()(()),()(())(),(())()(),(())(()); ... There is a simple bijection between these and Zeckendorf-expansions, explaining why Fibonacci numbers gives the number of fixed points of this permutation.

In addition to "rising slope" and "descending slope" mappings from Dyck paths to noncrossing Murasaki-diagrams as illustrated in A085161 and A086431 there is also a mapping where we insert a vertical stick after every second parenthesis and connect those that are on the same level without any intermediate points below. This Catalan bijection converts between these two mappings. See the illustration at example lines.

			.........................
..._____....________.....
..|.....|..|.....|..|....
..|..|..|..|..|..|..|....
..|..|..|..|..|..|..|....
..|..|..|..|..|..|..|....
..|..|..|..|..|..|..|....
..1((2))3((4((5))6()7))..
...(())(((())()))........
...11001111001000=13256=A014486(368)
To obtain the same Murasaki diagram using the "rising slope mapping" illustrated in A085161, we should use the following Dyck path, encoded by 360th binary string in A014486/A063171:
....___.._____...........
...|...||...|.|..........
...||..|||..|.|..........
...||..|||..|.|..........
...||..||/\.|.|..........
...|/\.|/..\/\/\.........
.../..\/........\........
...11001110010100=13204=A014486(360)
So we have A085169(368)=360 and A085170(360)=368.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A085170. a(n) = A086433(A082853(n))+A082852(n). A074684 = A083925(A085169(A057548(n))). Cf. also A085159, A085160, A085175.

Number of cycles: A086585. Number of fixed points: A000045. Max. cycle size: A086586. LCM of cycle sizes: A086587. (In range [A014137(n-1)..A014138(n-1)] of this permutation).

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

Original entry on oeis.org

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

Antti Karttunen, Jun 23 2003

nonn

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

			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.

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

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

A086430 Permutation of natural numbers induced by the Catalan bijection gma086430 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates the interpretations (pp)-(rr) of Stanley, using the "descending slope" mapping illustrated in A086431.

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

Inverse: A086429. a(n) = A086428(A086428(n)) = A086431(A086429(A086431(n))) = A057164(A085160(A057164(n))) = A086425(A082316(A086426(n))). Occurs in A073200.

Number of cycles: A054357. Number of fixed points: A046698. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A086425 Permutation of natural numbers induced by the Catalan bijection gma086425 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A086426. a(n) = A057164(A074684(n)). Occurs in A073200. Cf. also A086427, A086428, A086429, A086430, A086431.

A086426 Permutation of natural numbers induced by the Catalan bijection gma086426 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A086425. a(n) = A074683(A057164(n)). Occurs in A073200. Cf. also A086427, A086428, A086429, A086430, A086431.

A086427 Permutation of natural numbers induced by the Catalan bijection gma086427 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates by "half step" the interpretations (pp)-(rr) of Stanley, using the "descending slope" mapping illustrated in A086431.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A086428. a(n) = A086431(A086428(A086431(n))) = A057164(A085173(A057164(n))) = A086425(A057501(A086426(n))). Occurs in A073200. Cf. also A086429 (whole step rotate).

Number of cycles: A002995. Number of fixed points: A019590. Max. cycle size: A057543. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A086429 Permutation of natural numbers induced by the Catalan bijection gma086429 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates the interpretations (pp)-(rr) of Stanley, using the "descending slope" mapping illustrated in A086431.

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

Inverse: A086430. a(n) = A086427(A086427(n)) = A086431(A086430(A086431(n))) = A057164(A085159(A057164(n))) = A086425(A082315(A086426(n))). Occurs in A073200.

Number of cycles: A054357. Number of fixed points: A046698. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A086428 Permutation of natural numbers induced by the Catalan bijection gma086428 acting on symbolless S-expressions encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

This Catalan bijection rotates by "half step" the interpretations (pp)-(rr) of Stanley, using the "descending slope" mapping illustrated in A086431.

A. Karttunen, Gatomorphisms (With the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Inverse: A086427. a(n) = A086431(A086427(A086431(n))) = A057164(A085174(A057164(n))) = A086425(A057502(A086426(n))). Occurs in A073200. Cf. also A086430 (whole step rotate).

Number of cycles: A002995. Number of fixed points: A019590. Max. cycle size: A057543. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A085162 Permutation of natural numbers induced by Catalan Automorphism *A085162.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 23 2003

nonn

a(n) = A057163(A085161(A057163(n))). Cf. also A085165, A085166, A086431. Occurs in A073200.

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

cp's OEIS Frontend

A085169 Permutation of natural numbers induced by the Catalan bijection gma085169 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A086430 Permutation of natural numbers induced by the Catalan bijection gma086430 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

A086425 Permutation of natural numbers induced by the Catalan bijection gma086425 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Links

Crossrefs

A086426 Permutation of natural numbers induced by the Catalan bijection gma086426 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Links

Crossrefs

A086427 Permutation of natural numbers induced by the Catalan bijection gma086427 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

A086429 Permutation of natural numbers induced by the Catalan bijection gma086429 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

A086428 Permutation of natural numbers induced by the Catalan bijection gma086428 acting on symbolless S-expressions encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

A085162 Permutation of natural numbers induced by Catalan Automorphism *A085162.

Views

Author

Keywords

Links

Crossrefs