A063171 -id:A063171 - cp's OEIS frontend

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

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
.A...B...............C...B
..\./.................\./
...x...C...-->.....A...x...............()..A.........A..()..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) --> (a . (c . b)) __ (() . a) ----> (a . ())
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

Row 19 of A089840. Inverse permutation: A073269. a(n) = A072796(A069770(n)).

A graphical description and Scheme-implementations of automorphism added by Antti Karttunen, Jun 04 2011

A089850 Involution of natural numbers induced by Catalan automorphism *A089850 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.)
...B...C...........C...B
....\./.............\./
.A...x....-->....A...x.................A..().........A...()..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> (a . (c . b)) ____ (a . ()) ---> (a . ())
In terms of S-expressions, this automorphism swaps cadr and cddr of an S-exp if its length > 1.
Look at the example in A069770 to see how this will produce the given sequence of integers.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

a(n) = A069770(A089859(n)) = A089863(A069770(n)) = A057163(A089854(A057163(n))). Row 3 of A089840. Row 3771 of A122203 and row 3677 of A122204.

Number of cycles: A073191. Number of fixed points: A073190. Max. cycle size & LCM of all cycle sizes: A046698 (in each range limited by A014137 and A014138).

The new mail-address, a graphical explanation and constructive implementation of Scheme-function (*A089850) added by Antti Karttunen, Jun 04 2011

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

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

A089852 Involution of natural numbers induced by Catalan automorphism *A089852 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
...B...C...........B...A
....\./.............\./
.A...x....-->....C...x.................A..().........A...()..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> (c . (b . a)) ____ (a . ()) ---> (a . ())
In terms of S-expressions, this automorphism swaps car and cddr of an S-exp if its length > 1, if possible, otherwise keeps it intact.
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

a(n) = A069770(A089858(n)) = A089861(A069770(n)) = A057163(A089856(A057163(n))). Row 5 of A089840.

Number of cycles: A073191. Number of fixed points: A073190. Max. cycle size & LCM of all cycle sizes: A046698 (in each range limited by A014137 and A014138).

Further comments and constructive implementation of Scheme-function (*A089852) added by Antti Karttunen, Jun 04 2011

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
.A...B...........B...C
..\./.............\./
...x...C....-->....x...A...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((b . c) . a) ___ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism rotates caar, cdar and cdr of an S-exp if possible, i.e., if car-side is not ().
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Inverse of A089857. a(n) = A089860(A069770(n)) = A069770(A074680(n)) = A057163(A089853(A057163(n))). Row 9 of A089840.

Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).

Further comments and constructive implementation of Scheme-function (*A089855) added by Antti Karttunen, Jun 04 2011

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

.A...B...........C...A
..\./.............\./
...x...C....-->....x...B...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((c . a) . b) ___ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism rotates caar, cdar and cdr of an S-exp, i.e., if car-side is not ().
See the Karttunen OEIS-Wiki link for a detailed explanation how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Row 11 of A089840. Inverse of A089855. a(n) = A074679(A069770(n)) = A069770(A089862(n)) = A057163(A089851(A057163(n))).

Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).

Further comments and constructive implementation of Scheme-function (*A089857) added by Antti Karttunen, Jun 04 2011

A071153 Łukasiewicz word for each rooted plane tree (interpretation e in Stanley's exercise 19) encoded by A014486 (or A063171), with the last leaf implicit, i.e., these words are given without the last trailing zero, except for the null tree which is encoded as 0.

Original entry on oeis.org

0, 1, 20, 11, 300, 201, 210, 120, 111, 4000, 3001, 3010, 2020, 2011, 3100, 2101, 2200, 1300, 1201, 2110, 1210, 1120, 1111, 50000, 40001, 40010, 30020, 30011, 40100, 30101, 30200, 20300, 20201, 30110, 20210, 20120, 20111, 41000, 31001, 31010

Offset: 0

Antti Karttunen, May 14 2002

Note: this finite decimal representation works only up to the 6917th term, as the 6918th such word is already (10,0,0,0,0,0,0,0,0,0). The sequence A071154 shows the initial portion of this sequence sorted.

			The 11th term of A063171 is 10110010, corresponding to parenthesization ()(())(), thus its Łukasiewicz word is 3010. The 18th term of A063171 is 11011000, corresponding to parenthesization (()(())), thus its Łukasiewicz word is 1201. I.e., in the latter example there is one list on the top-level, which in turn contains two sublists, of which the first is zero elements long and the second is a sublist containing one empty sublist (the last zero is omitted).

A. Karttunen, Gatomorphisms and other excursions amidst the plane trees and parenthesizations (Includes the complete Scheme program for computing this sequence)
R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
R. P. Stanley, Exercises on Catalan and Related Numbers
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz
Index entries for sequences related to parenthesizing

For n >= 1, the number of zeros in the term a(n) is given by A057514(n)-1.
The first digit of each term is given by A057515.
Cf. A014486, A059984, A059985, A071152, A071154.
Corresponding factorial walk encoding: A071155 (A071157, A071159).
a(n) = A079436(n)/10.

A074685 Permutation of natural numbers induced by the Catalan bijection gmA074685! acting on the parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 11 2002

nonn

A. Karttunen, Gatomorphisms (with the complete Scheme source)
Index entries for sequences that are permutations of the natural numbers

Inverse of A074686. a(n) = A057163(A074689(A057163(n))). Occurs in A073200 as row 5572436.

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.)
.....B...C.......B...A
......\./.........\./
...A...x...-->... .x...C...............A..().........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((b . a) . c) ____ (a . ()) ---> (() . a)
See the Karttunen OEIS-Wiki link for a detailed explanation how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Row 13 of A089840. Inverse of A089861. a(n) = A072797(A069770(n)) = A069770(A089852(n)) = A057163(A073270(A057163(n))).

Number of cycles: A073193. Number of fixed-points: A019590. Max. cycle size: A089422. LCM of cycle sizes: A089423 (in each range limited by A014137 and A014138).

Further comments and constructive implementation of Scheme-function (*A089858) added by Antti Karttunen, Jun 04 2011

A089860 Permutation of natural numbers induced by Catalan automorphism *A089860 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
.....B...C.......C...A
......\./.........\./
...A...x...-->... .x...B...............A..().........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
(a . (b . c)) --> ((c . a) . b) ___ (a . ()) --> (() . a)
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Row 16 of A089840. Inverse of A089862. a(n) = A089855(A069770(n)) = A069770(A089851(n)) = A069770(A074680(A069770(n))) = A057163(A089862(A057163(n))).

Number of cycles: A001683 (probably, not checked). Number of fixed points: A019590. Max. cycle size & LCM of all cycle sizes: A089410 (in each range limited by A014137 and A014138).

A graphical description and constructive version of Scheme-implementation added by Antti Karttunen, Jun 04 2011

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A089850 Involution of natural numbers induced by Catalan automorphism *A089850 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

A089852 Involution of natural numbers induced by Catalan automorphism *A089852 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A071153 Łukasiewicz word for each rooted plane tree (interpretation e in Stanley's exercise 19) encoded by A014486 (or A063171), with the last leaf implicit, i.e., these words are given without the last trailing zero, except for the null tree which is encoded as 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A074685 Permutation of natural numbers induced by the Catalan bijection gmA074685! acting on the parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A089860 Permutation of natural numbers induced by Catalan automorphism *A089860 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions