cp's OEIS Frontend

This involution effects the following transformation on the binary trees (labels A,B,C,D refer to arbitrary subtrees located on those nodes and () stands for a terminal node.)

.....C...D.........A...D

......\./...........\./

...B...X2........C...Y2......B..().......A..()

....\./...........\./.........\./.........\./

.A...X1....-->.B...Y1......A...X1..-->.B...Y1

..\./...........\./.........\./.........\./

...X0............Y0..........X0..........Y0

Note that automorphism *A072796 = SPINE(*A129605). See the definition given in A122203.

This involution effects the following transformation on the binary trees (labels A,B,C,D refer to arbitrary subtrees located on those nodes and () stands for a terminal node.)

.....C...D.........B...D

......\./...........\./

...B...X2........A...Y2......B..().......A..()

....\./...........\./.........\./.........\./

.A...X1....-->.C...Y1......A...X1..-->.B...Y1

..\./...........\./.........\./.........\./

...X0............Y0..........X0..........Y0

Note that automorphism *A072796 = ENIPS(*A129606). See the definition given in A122204.

Automorphism *A074679 = ENIPS(*A129609). See the definition given in A122204.

Automorphism *A074680 = SPINE(*A129610). See the definition given in A122203.

The comments at A123694 concerning counts of fixed points apply also here.

If a(n) is nonzero, then the n-th non-recursive Catalan Automorphism in A089840 does not have orbits (cycles) larger than that and the corresponding LCM-sequence will set to a constant sequence a(n),a(n),a(n),a(n),... E.g. A089840[4] = A089851 is obtained by rotating three subtrees cyclically and its LCM-sequence begins as 1,1,1,3,3,3,3,3,3,3,3,... (a(4)=3). Similarly, A089840[15] = A089859, whose LCM-sequence begins as 1,1,2,4,4,4,4,4,4,4,4,.... (a(15)=4). In contrast, the Max. cycle and LCM-sequence (A089410) of A089840[12] (= A074679) exhibits genuine growth, thus a(12)=0.

Each row is a permutation of nonnegative integers induced by a Catalan bijection (constructed as explained below) acting on the parenthesizations/plane binary trees as encoded and ordered by A014486/A063171.

The construction process is akin to the constructive mapping of primitive recursive functions to N: we have two basic primitives, A069770 (row 0) and A072796 (row 1), of which the former swaps the left and the right subtree of a binary tree and the latter exchanges the positions of the two leftmost subtrees of plane general trees, unless the tree's degree is less than 2, in which case it just fixes it. From then on, the even rows are constructed recursively from any other Catalan bijection in this table, using one of the five allowed recursion types:

0 - Apply the given Catalan bijection and then recurse down to both subtrees of the new binary tree obtained. (last decimal digit of row number = 2)

1 - First recurse down to both subtrees of the old binary tree and only after that apply the given Catalan bijection. (last digit = 4)

2 - Apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree obtained. (last digit = 6)

3 - First recurse down to the right subtree of old binary tree and only after that apply the given Catalan bijection. (last digit = 8)

4 - First recurse down to the left subtree of old binary tree, after that apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree. (last digit = 0)

The odd rows > 2 are compositions of the rows 0, 1, 2, 4, 6, 8, ... (i.e. either one of the primitives A069770 or A072796, or one of the recursive compositions) at the left hand side and any Catalan bijection from the same array at the right hand side. See the scheme-functions index-for-recursive-sgtb and index-for-composed-sgtb how to compute the positions of the recursive and ordinary compositions in this table.

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.

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.......A...B

....\./.........\./

.A...x....-->....x...C.................A..().........()..A..

..\./.............\./...................\./....-->....\./...

...x...............x.....................x.............x....

(a . (b . c)) -> ((a . b) . c) ____ (a . ()) --> (() . a)

That is, we rotate the binary tree left, in case it is possible and otherwise (if the right hand side of a tree is a terminal node) swap the left and right subtree (so that the terminal node ends to the left hand side), i.e., apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.

This is the first multiclause nonrecursive automorphism in table A089840 and the first one whose order is not finite, i.e., the maximum size of cycles in this permutation is not bounded (see A089842). The cycle counts in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+1), which is otherwise the same sequence as for Catalan automorphisms *A057161/*A057162, but shifted once right. For an explanation, please see the notes in OEIS Wiki.