cp's OEIS Frontend

This is the simplest possible Catalan automorphism after the identity bijection (A001477). It effects the following transformation on the unlabeled rooted plane binary trees (letters A and B refer to arbitrary subtrees located on those vectices):

A B B A

\ / --> \ /

x x

(a . b) -----> (b . a)

Applying this permutation recursively to the right hand side branch of the binary trees produces permutations A069767 and A069768 (that occur at the same index 1 in tables A122203 and A122204), and applying this recursively to the both branches of binary trees (as in pre- or postorder traversal) produces A057163 (which occurs at the same index 1 in tables A122201 and A122202) that reflects the whole binary tree.

For this permutation, A127302(a(n)) = A127302(n) for all n, [or equally, A153835(a(n)) = A153835(n)], and likewise for all such recursive derivations as mentioned above.

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.

CatalanRankGlobal given in A057117 and the other Maple procedures in A056539.

Composition with A057163 gives Donaghey's Map M (A057505/A057506).

This is equivalent to map M given by Donaghey on page 81 of his paper "Automorphisms on ..." and also equivalent to the transformation procedure depicted in the picture (23) of Donaghey-Shapiro paper.

This can be also considered as a "more recursive" variant of A057501 or A057503 or A057161.

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th nonrecursive automorphism in the table A089840 with the recursion scheme "FORK". In this recursion scheme the given automorphism is first applied at the root of binary tree, before the algorithm recurses down to the both branches (new ones, possibly changed by the given automorphism). I.e. this corresponds to the pre-order (prefix) traversal of a Catalan structure, when it is interpreted as a binary tree. The associated Scheme-procedures FORK and !FORK can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism. Each row occurs only once in this table. Inverses of these permutations can be found in table A122202.

This is inverse of A057505, which is a signature permutation of Catalan automorphism (bijection) known as "Donaghey's map M". See A057505 for more comments, links and references.

This is a permutation of natural numbers induced when "noncrossing handshakes", i.e., Stanley's interpretation (n), "n nonintersecting chords joining 2n points on the circumference of a circle", are rotated.

The same permutation is induced when the root position of plane trees (Stanley's interpretation (e)) is successively changed around the vertices.

For a good illustration how the rotation of the root vertex works, please see the Figure 6, "Rotation of an ordered rooted tree" in Torsten Mütze's paper (on page 24 in 20 May 2014 revision).

For yet another application of this permutation, please see the attached notes for A085197.

By "recursivizing" either the left or right hand side argument of A085201 in the formula, one ends either with A057161 or A057503. By "recursivizing" the both sides, one ends with A057505. - Antti Karttunen, Jun 06 2014

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th nonrecursive automorphism in the table A089840 with the recursion scheme "KROF". In this recursion scheme the algorithm first recurses down to the both branches, before the given automorphism is applied at the root of binary tree. I.e., this corresponds to the post-order (postfix) traversal of a Catalan structure, when it is interpreted as a binary tree. The associated Scheme-procedures KROF and !KROF can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism. Each row occurs only once in this table. Inverses of these permutations can be found in table A122201.

The recursion scheme KROF is equivalent to a composition of recursion schemes ENIPS (described in A122204) and NEPEED (described in A122284), i.e., KROF(f) = NEPEED(ENIPS(f)) holds for all Catalan automorphisms f. Because of the "universal property of folds", these recursion schemes have well-defined inverses, that is, they are bijective mappings on the set of all Catalan automorphisms. Specifically, if g = KROF(f), then (f s) = (g (cons (g^{-1} (car s)) (g^{-1} (cdr s)))), that is, to obtain an automorphism f which gives g when subjected to recursion scheme KROF, we compose g with its own inverse applied to the car- and cdr-branches of a S-expression (i.e., the left and right subtrees in the context of binary trees). This implies that for any nonrecursive automorphism f of the table A089840, KROF^{-1}(f) is also in A089840, which in turn implies that all rows of table A089840 can be found also in table A122202 (e.g., row 1 of A089840 (A069770) occurs here as row 1654720) and furthermore, the table A122290 contains the rows of both tables, A122202 and A089840 as its subsets. Similar notes apply to recursion scheme FORK described in A122201. - Antti Karttunen, May 25 2007