A057163 -id:A057163 - cp's OEIS frontend

A071655 Permutation of natural numbers induced by the automorphism robr_car_cdr! acting on the parenthesizations encoded by A014486.

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

Offset: 0

Antti Karttunen, May 30 2002

nonn

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

Inverse permutation: A071656. The car/cdr-flipped conjugate of A071660, i.e. A071655(n) = A057163(A071660(A057163(n))). Cf. also A071657, A071658.

A218787 a(n) = A014486-index for the n-th tendril of infinite beanstalk (A213730(n)), with the "lesser numbers to the left side" construction.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 2, 0, 8, 0, 0, 1, 0, 0, 1, 2, 0, 8, 0, 0, 1, 8, 0, 0, 3, 0, 2, 1, 0, 0, 0, 1, 2, 0, 8, 0, 0, 1, 8, 0, 0, 3, 0, 2, 1, 0, 8, 0, 0, 3, 0, 60, 0, 0, 172, 0, 2, 0, 1, 0, 0, 1, 2, 0, 8, 0, 0, 1, 8, 0, 0, 3, 0, 2, 1, 0, 8, 0, 0

Offset: 1

Antti Karttunen, Nov 11 2012

nonn

"Tendrils" of the beanstalk are the finite side-trees sprouting from its infinite trunk (see A179016) at the numbers given by A213730.

			A213730(9)=22, and from that branches 24 and 25 (as both A011371(24)=A011371(25)=22) and while 24 is a leaf (in A055938) the other branch 25 further branches to two leaves (as both A011371(28)=A011371(29)=25).
When we construct a binary tree from this in such a fashion that the lesser numbers go to the left, we obtain:
...........
...28...29.
.....\./...
..24..25...
...\ /.....
....22.....
...........
and the binary tree
........
...\./..
....*...
.\./....
..*.....
........
is located as A014486(2) in the normal encoding order of binary trees, thus a(9)=2.

A. Karttunen, Table of n, a(n) for n = 1..8727
A. Karttunen, Illustration of how binary trees (the second rightmost column) are encoded by A014486

These are the mirror-images of binary trees given in A218788, i.e. a(n) = A057163(A218788(n)). A218786 gives the sizes of these trees. Cf. A072764, A218609, A218611.

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

A125976 Signature-permutation of Kreweras' 1970 involution on Dyck paths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

Lalanne shows in the 1992 paper that this automorphism preserves the sum of peak heights, i.e., that A126302(a(n)) = A126302(n) for all n. Furthermore, he also shows that A126306(a(n)) = A057514(n)-1 and likewise, that A057514(a(n)) = A126306(n)+1, for all n >= 1.
Like A069772, this involution keeps symmetric Dyck paths symmetric, but not necessarily same.
The number of cycles and fixed points in range [A014137(n-1)..A014138(n-1)] of this involution seem to be given by A007595 and the "aerated" Catalan numbers [1, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, ...], thus this is probably a conjugate of A069770 (as well as of A057163).

A. Karttunen, Table of n, a(n) for n = 0..2055
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
J.-C. Lalanne, Une Involution sur les Chemins de Dyck, European J. Combin. 13 (1992), no. 6, 477-487.
Index entries for signature-permutations of Catalan automorphisms

Cf. A080300, A125974, A014486.
Cf. A057163, A069770, A007595, A014137, A014138.
Compositions and conjugations with other automorphisms: A125977-A125979, A125980, A126290.

a(n) = A080300(A125974(A014486(n))).

A057162 Signature-permutation of a Catalan Automorphism: rotate one step clockwise the triangulations of polygons encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 18 2000; entry revised Jun 06 2014

nonn

This is a permutation of natural numbers induced when Euler's triangulation of convex polygons, encoded by the sequence A014486 in a straightforward way (via binary trees, cf. the illustration of the rotation of a triangulated pentagon, given in the Links section) are rotated clockwise.

In A057161 and A057162, the cycles between A014138(n-1)-th and A014138(n)-th term partition A000108(n) objects encoded by the corresponding terms of A014486 into A001683(n+2) equivalence classes of flexagons (or unlabeled plane boron trees), thus the latter sequence can be counted with the Maple procedure A057162_CycleCounts given below. Cf. also the comments in A057161.

A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Illustration of how the five triangulations of a pentagon will rotate, and the corresponding changes it induces in the binary trees
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 51-54.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057161.
Also, an "ENIPS"-transform of A069773, and thus occurs as row 17 of A130402.
Other related permutations: A057163, A057164, A057501, A057503, A057505.
Cf. A001683 (cycle counts), A057544 (max cycle lengths).

a(n) = CatalanRankGlobal(RotateTriangularizationR(A014486[n]))
RotateTriangularizationR := n -> ReflectBinTree(RotateTriangularization(ReflectBinTree(n)));
with(group); A057162_CycleCounts := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,RotateTriangularization(CatalanUnrank(n,r)))]; od; a := [op(a),(`if`((n < 2),1,nops(convert(b,'disjcyc'))))]; od; RETURN(a); end;
# See also the code in A057161.

As a composition of related permutations:
a(n) = A069768(A057508(n)).
a(n) = A057163(A057161(A057163(n))).
a(n) = A057164(A057503(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 143.]

A071663 Permutation A057505 applied three times ("cubed").

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, May 30 2002

nonn

Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
Antti Karttunen, Gatomorphisms (Includes the complete Scheme source for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A071664 and also its car/cdr-flipped conjugate, i.e. A071663(n) = A057163(A071664(A057163(n))) = A057505(A071661(n)). Cf. also A071665, A071667, A071669.

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

cp's OEIS Frontend

A071655 Permutation of natural numbers induced by the automorphism robr_car_cdr! acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Links

Crossrefs

A218787 a(n) = A014486-index for the n-th tendril of infinite beanstalk (A213730(n)), with the "lesser numbers to the left side" construction.

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

A125976 Signature-permutation of Kreweras' 1970 involution on Dyck paths.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A057162 Signature-permutation of a Catalan Automorphism: rotate one step clockwise the triangulations of polygons encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A071663 Permutation A057505 applied three times ("cubed").

Views

Author

Keywords

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