cp's OEIS Frontend

Each row is a permutation of natural numbers and occurs only once. The table is closed with regards to the composition of its rows (see A089839) and it contains the inverse of each (their positions are shown in A089843). The permutations in table form an enumerable subgroup of the group of all size-preserving "Catalan bijections" (bijections among finite unlabeled rooted plane binary trees). The order of each element is shown at A089842.

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

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

.A...x....-->....B...x.................A..().........A...()..

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

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

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

In terms of S-expressions, this rotates car, cadr and cddr of an S-exp

if its length > 1, otherwise keeps it intact.

Note that the first clause corresponds to generator C of Thompson's groups T and V.

(Cf. also A072796, A074679 and A154121 for other related generators).

See "Catalan Automorphisms" OEIS-Wiki page for a detailed explanation how to obtain a given integer sequence from this definition.

This bijection of binary trees is obtained when we apply bijection *A074679 to the left subtree and keep the right subtree intact.

....B...C.......A...B

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

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

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

....x...D...........x...D.................x...C.........x...C..

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

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

...............................................................

Compare to A154121.

See "Catalan Automorphisms" OEIS-Wiki page for a detailed explanation how to obtain a given integer sequence from this definition.

This bijection of binary trees can be obtained by applying bijection *A074680 to the right hand side subtree and leaving the left hand side subtree intact. See also comments at A154121.

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

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

...x...D....-->....B...x.................()..C ........C...()

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

.A...x...........A...x.................A...x.........A...x....

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

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

..............................................................

That is, (a . ((b . c) . d)) -> (a . (b . (c . d)))

or (a . (() . c)) -> (a . (c . ())) if the former is not possible.

This bijection of binary trees is obtained in the following way. See also comments at A154122.

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

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

..B...x....-->....x...D.................B..().........()..A..

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

A...x...........A...x.................A...x.........B...x....

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

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

.............................................................

That is, we do (a . (b . (c . d))) -> (a . ((b . c) . d))

or (a . (b . ())) --> (b . (() . a)) if the former is not possible.

Note that the first clause corresponds to generator B of Thompson's groups F, T and V. See further comments at A154121.

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