A073191 -id:A073191 - cp's OEIS frontend

A072796 Self-inverse permutation of natural numbers induced by the Catalan bijection swapping the two leftmost subtrees in the general tree context of the parenthesizations encoded by A014486. See illustrations in the comments.

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

Offset: 0

Antti Karttunen, Jun 12 2002

nonn

This bijection effects the following transformation on the unlabeled rooted plane general trees (letters A, B, C, etc. refer to arbitrary subtrees located on those vertices):
    A        A      A     B       B     A       A  B  C       B  A  C
    |  -->   |       \   /   -->   \   /         \ | /   -->   \ | /
    |        |        \./           \./           \|/           \|/     etc.
I.e., it keeps "planted" (root degree = 1) trees intact, and swaps the two leftmost toplevel subtrees of the general trees that have a root degree > 1.
On the level of underlying binary trees that general trees map to (see, e.g., 1967 paper by N. G. De Bruijn and B. J. M. Morselt, or consider lists vs. dotted pairs in Lisp programming language), this bijection 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           A   C
     \ /             \ /
  A   x    -->    B   x                 A   ()        A   ()
   \ /             \ /                   \ /    -->    \ /
    x               x                     x             x
(a . (b . c)) -> (b . (a . c))         (a . ()) ---> (a . ())
Note that the first clause corresponds to what is called "generator pi_0" in Thompson's group V. (See also A074679, A089851 and A154121 for other related generators.)
Look at the example section to see how this will produce the given sequence of integers.
Applying this permutation recursively down the right hand side branch of the binary trees (or equivalently, along the topmost level of the general trees) produces permutations A057509 and A057510 (that occur at the same index 2 in tables A122203 and A122204) that effect "shallow rotation" on general trees and parenthesizations. Applying it recursively down the both branches of binary trees (as in pre- or postorder traversal) produces A057511 and A057512 (that occur at the same index 2 in tables A122201 and A122201) that effect "deep rotation" on general trees and parenthesizations.
For this permutation, A127301(a(n)) = A127301(n) for all n, which in turn implies A129593(a(n)) = A129593(n) for all n, likewise for all such recursively generated bijections as A057509 - A057512. Compare also to A072797.

			To obtain the signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486 and for each n, a(n) will be the position of the tree to which the n-th tree is transformed to, as follows:
.
                   one tree of one internal
  empty tree         (non-leaf) node
      x                      \/
n=    0                      1
a(n)= 0                      1               (both are always fixed)
.
the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are:
.
                          \/     \/                 \/     \/
       \/     \/         \/       \/     \/ \/     \/       \/
      \/       \/       \/       \/       \_/       \/       \/
n=     2        3        4        5        6        7        8
.
and the new shapes after swapping the two subtrees in positions marked "A" and "B" in the diagram given in the comments are:
.
                          \/               \/       \/     \/
       \/     \/         \/     \/ \/       \/     \/       \/
      \/       \/       \/       \_/       \/       \/       \/
a(n)=  2        3        4        6        5        7        5
thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 6, 5, 7, 8.

Antti Karttunen, Table of n, a(n) for n = 0..196
J. W. Cannon, W. J. Floyd, and W. R. Parry, Notes on Richard Thompson's Groups F and T
J. W. Cannon, W. J. Floyd, and W. R. Parry, Introductory notes on Richard Thompson's groups, L'Enseignement Mathématique, Vol. 42 (1996), pp. 215-256.
N. G. De Bruijn and B. J. M. Morselt, A note on plane trees, J. Combinatorial Theory 2 (1967), 27-34.
Antti Karttunen, Catalan Automorphisms

Row 2 of A089840. Row 3613 of A122203 and row 3617 of A122204.
Fixed point counts and cycle counts are given in A073190 and A073191.
Cf. A014486, A072797, A057509, A057510, A057511, A057512, A127301, A129593, A129608.

Comment section edited and Examples added by Antti Karttunen, Jan 26 2024

A072797 Self-inverse permutation of natural numbers induced by a Catalan bijection acting on binary trees as encoded by A014486. See comments and examples for details.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 12 2002

nonn

This bijection 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           A   C
    \ /             \ /
     x   C    -->    x   B               ()  A        ()   A
      \ /             \ /                 \ /    -->    \ /
       x               x                   x             x
  ((a . b) . c) --> ((a . c) . b)      (() . a) ---> (() . a)
See the example for an explanation of how to obtain a given integer sequence from this definition.
Notably for this permutation, A127301(a(n)) = A127301(n) does not always hold, even though for all n, A129593(a(n)) = A129593(n). - Antti Karttunen, Jan 14 2024

			To obtain the signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486 and for each n, a(n) will be the position of the tree to which the n-th tree is transformed to, as follows:
.
                   one tree of one internal
  empty tree         (non-leaf) node
      x                      \/
n=    0                      1
a(n)= 0                      1               (both are always fixed)
.
the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are:
.
                          \/     \/                 \/     \/
       \/     \/         \/       \/     \/ \/     \/       \/
      \/       \/       \/       \/       \_/       \/       \/
n=     2        3        4        5        6        7        8
.
and the new shapes after swapping the two subtrees in positions marked "B" and "C" in the diagram given in the comments are:
.
                          \/     \/       \/               \/
       \/     \/         \/       \/     \/       \/ \/     \/
      \/       \/       \/       \/       \/       \_/       \/
a(n)=  2        3        4        5        7        6        8
thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 5, 7, 6, 8.

Row 8 of A089840.
Cf. A014486, A057163, A072796, A127301, A129593.
Counts for the fixed points and for the number of distinct cycles (in each subrange limited by A014137) are given by A073190 and A073191.

a(n) = A057163(A072796(A057163(n))).

Further comments added by Antti Karttunen, Jun 04 2011 and Mar 30 2024

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

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 11, 12, 13, 14, 15, 19, 21, 22, 16, 20, 17, 18, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 51, 52, 56, 58, 59, 60, 62, 63, 64, 42, 43, 53, 57, 61, 44, 54, 45, 46, 47, 55, 48, 49, 50, 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...A
..\./.............\./
...x...C....-->....x...C...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((b . a) . c) ___ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism swaps caar and cdar of an S-exp if its first element 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

a(n) = A089859(A069770(n)) = A069770(A089863(n)) = A057163(A089850(A057163(n))). Row 7 of A089840. Cf. A122282.

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 (*A089854) 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

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

A073201 Array of cycle count sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 7, 4, 1, 1, 1, 22, 11, 3, 1, 1, 1, 66, 31, 7, 2, 1, 1, 1, 217, 96, 22, 4, 3, 1, 1, 1, 715, 305, 66, 11, 7, 2, 1, 1, 1, 2438, 1007, 217, 30, 22, 4, 2, 2, 1, 1, 8398, 3389, 715, 93, 66, 11, 3, 5, 1, 1, 1, 29414, 11636, 2438, 292, 217, 30, 6, 14, 2, 2, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the counts of separate orbits/cycles to which the Catalan bijection given in the corresponding row of A073200 partitions each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

Note that for involutions (self-inverse Catalan bijections) this is always (A000108(n)+Affffff(n))/2, where Affffff is the corresponding "fix-count sequence" from the table A073202.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Only the first known occurrence(s) given (marked with ? if not yet proved/unclear): rows 0, 2, 4, etc.: A007595, Row 1: A073191, Rows 6 (& 8): A073431, Row 7: A000108, Rows 12, 14, 20, ...: A057513, Rows 16, 18, ...: A003239, Row 57, ..., 164: A007123, Row 168: A073193, Row 261: A002995, Row 2614: A057507, Row 2618 (?), row 17517: A001683.

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

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 8, 7, 6, 9, 10, 11, 12, 13, 21, 22, 20, 17, 18, 19, 16, 14, 15, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 58, 59, 62, 63, 64, 57, 61, 54, 45, 46, 55, 48, 49, 50, 56, 60, 53, 44, 47, 51, 42, 37, 38, 52, 43, 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...........C...B
..\./.............\./
...x...C....-->....x...A...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((c . b) . a) ___ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism swaps caar 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

Row 10 of A089840. a(n) = A073269(A069770(n)) = A069770(A073270(n)) = A057163(A089852(A057163(n))).

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 (*A089856) added by Antti Karttunen, Jun 04 2011

A073190 Number of general plane trees which are either empty (the case a(0)), or whose root degree is either 1 (i.e., the planted trees) or the two leftmost subtrees (of the root node) are identical.

Original entry on oeis.org

1, 1, 2, 3, 8, 20, 60, 181, 584, 1916, 6476, 22210, 77416, 272840, 971640, 3488925, 12621168, 45946156, 168206604, 618853270, 2286974856, 8485246456, 31596023208, 118037654258, 442287721872, 1661790513944, 6259494791096

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

The Catalan bijection A072796 fixes only these kinds of trees, so this occurs in the table A073202 as row 1.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Occurs for first time in A073202 as row 1. A073191(n) = (A000108(n)+A073190(n))/2. Cf. also A073192.

A073190 := proc(n) local d; Cat(n-1)+ add( (`mod`((n-d+1),2))*Cat((n-d-2)/2)*Cat(d), d=0..n-2); end;
Cat := n -> binomial(2*n,n)/(n+1);

a[n_] := CatalanNumber[n - 1] + Sum[Mod[n - d + 1, 2]*CatalanNumber[(n - d - 2)/2]*CatalanNumber[d], {d, 0, n - 2}]; a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 06 2016 *)

Cat(n) = binomial(2*n,n)/(n+1);
a(n) = if (n==0, 1, Cat(n-1) + sum(i=0, n-2, if (!((n-i)%2), Cat((n-i-2)/2)*Cat(i)))); \\ Michel Marcus, May 30 2018

a(0)=1, a(n) = Cat(n-1) + Sum_{i=0..n-2, (n-i) is even} Cat((n-i-2)/2)*Cat(i), where Cat(n) is A000108(n).

cp's OEIS Frontend

A072796 Self-inverse permutation of natural numbers induced by the Catalan bijection swapping the two leftmost subtrees in the general tree context of the parenthesizations encoded by A014486. See illustrations in the comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A072797 Self-inverse permutation of natural numbers induced by a Catalan bijection acting on binary trees as encoded by A014486. See comments and examples for details.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A089854 Involution of natural numbers induced by Catalan automorphism *A089854 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

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

A073201 Array of cycle count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A073190 Number of general plane trees which are either empty (the case a(0)), or whose root degree is either 1 (i.e., the planted trees) or the two leftmost subtrees (of the root node) are identical.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula