cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-9 of 9 results.

A074683 Permutation of natural numbers induced by the Catalan Automorphism *A074683 acting on parenthesizations as encoded and ordered by A014486/A063171.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Sep 11 2002

Keywords

Comments

This bijection maps between the "standard" ordering of binary trees as encoded by A014486 and "variant A quaternary encoding" as explained in the sequence A085184.
This is a rare example of Catalan Automorphism (with simple definition) where the cycle count sequence (A089411) is not monotone. (See A127296 for more complex example.)

Links

Crossrefs

Row 12 of A122202. Inverse of A074684. a(n) = A057163(A074682(A057163(n))).
The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in subpermutations limited by A014137 and A014138 are given by A089411, A086586 and A089412.

A074684 Permutation of natural numbers induced by Catalan Automorphism *A074684 acting on the parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Sep 11 2002

Keywords

Comments

This bijection maps between the "standard" ordering of binary trees as encoded by A014486 and "variant A quaternary encoding" as explained in the sequence A085184.
This is a rare example of a simply defined Catalan Automorphism where the cycle count sequence (A089411) is not monotone. (See A127296 for a much more complex example.)

Links

Crossrefs

Row 17 of A122201. Inverse of A074683. a(n) = A057163(A074681(A057163(n))).
The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in subpermutations limited by A014137 and A014138 are given by A089411, A086586 and A089412.

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

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jun 23 2003

Keywords

Comments

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.

Examples

			.........................
..._____....________.....
..|.....|..|.....|..|....
..|..|..|..|..|..|..|....
..|..|..|..|..|..|..|....
..|..|..|..|..|..|..|....
..|..|..|..|..|..|..|....
..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.

Links

Crossrefs

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

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

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jun 23 2003

Keywords

Links

Crossrefs

Inverse: A085169 (see comments there). a(n) = A086434(A082853(n))+A082852(n). Cf. also A074683, 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).

A089867 Permutation of natural numbers induced by the Catalan bijection gma089867 acting on the parenthesizations/binary trees encoded by A014486/A063171.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Dec 20 2003

Keywords

Comments

This Catalan bijection arises when we apply the Catalan bijection A085169 to the left subtree and keep the right subtree intact.

Links

Crossrefs

Inverse of A089868.
Number of cycles: A089846. Number of fixed-points: A090826. Max. cycle size: A086586. LCM of cycle sizes: A086587. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A089868 Permutation of natural numbers induced by the Catalan bijection gma089868 acting on the parenthesizations/binary trees encoded by A014486/A063171.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Dec 20 2003

Keywords

Comments

This Catalan bijection arises when we apply the Catalan bijection A085170 to the left subtree and keep the right subtree intact.

Links

Crossrefs

Inverse of A089867.
Number of cycles: A089846. Number of fixed-points: A090826. Max. cycle size: A086586. LCM of cycle sizes: A086587. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A089869 Permutation of natural numbers induced by the Catalan bijection gma089869 acting on the parenthesizations/binary trees encoded by A014486/A063171.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Dec 20 2003

Keywords

Comments

This Catalan bijection arises when we apply the Catalan bijection A085169 to each top-level subtree (sub-parenthesization).

Links

Crossrefs

Inverse of A089870.
Number of cycles: A090827. Number of fixed-points: A000129. Max. cycle size: A086586. LCM of cycle sizes: A086587. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A089870 Permutation of natural numbers induced by the Catalan bijection gma089870 acting on the parenthesizations/binary trees encoded by A014486/A063171.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Dec 20 2003

Keywords

Comments

This Catalan bijection arises when we apply the Catalan bijection A085170 to each top-level subtree (sub-parenthesization).

Links

Crossrefs

Inverse of A089869.
Number of cycles: A090827. Number of fixed-points: A000129. Max. cycle size: A086586. LCM of cycle sizes: A086587. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A125981 Signature-permutation of Deutsch's 2000 bijection on ordered trees.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jan 02 2007

Keywords

Comments

Deutsch shows in his 2000 paper that this automorphism converts any ordered tree with the number of nodes having degree q to a tree with an equal number of odd-level nodes having degree q-1, from which it follows that, for each positive integer q, the parameters "number of nodes of degree q" and "number of odd-level nodes of degree q-1" are equidistributed. He also shows that this automorphism converts any tree with k leaves to a tree with k even-level nodes, i.e., in OEIS terms, A057514(n) = A126305(A125981(n)).
To obtain the signature permutation, we apply the given Scheme-function *A125981 to the parenthesizations as encoded and ordered by A014486/A063171 (and surrounded by extra pair of parentheses to make a valid Scheme-list) and for each n, we record the position of the resulting parenthesization (after discarding the outermost parentheses from the Scheme-list) in A014486/A063171 and this value will be a(n).

Links

Crossrefs

Inverse: A125982. The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of this permutation seem to be given by A089411, A086586 and A089412, thus this is probably a conjugate of A074683/A074684. A125983 gives the A057163-conjugate.
Showing 1-9 of 9 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.