cp's OEIS Frontend

See comments at A153246. Essentially, A123493 does not extend uniquely to an automorphism of infinite binary tree, because its behavior is dependent on whether certain vertices of a finite binary tree are leaves (terminal nodes) or not. Similarly for bijections like A127387 and A127379.

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 automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C and D refer to arbitrary subtrees located on those nodes.)

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

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

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

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

.....A...x...-->...x...A...........x...D...-->...D...x...

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

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

This is the signature-permutation of Catalan automorphism which is derived from the automorphism *A123492 with the recursion schema KROF (defined in A122202). Like automorphisms *A057163 and *A069767/*A069768 these automorphisms are closed with respect to the subset of "zigzagging" binary trees (i.e., those binary trees where there are no nodes with two nonempty branches, or equivalently, those ones for which Stanley's interpretation (c) forms a non-branching line) and thus induce a permutation of binary strings. That is, starting from the root of such a binary tree, the turns taken by nonempty branches are interpreted as binary digits 0 or 1, depending on whether the tree grows to the left or right. In this manner, the Catalan automorphisms *A123494 and *A123493 induce the Binary Reflected Gray Code (see A003188 and A006068).

A "fleeing tree" sequence computed for Catalan bijection CatBij gives for each binary tree A014486(n) the number of cases where, when a new V-node (a bud) is inserted into one of the A072643(n)+1 possible leaves of that tree, it follows that (CatBij tree) is not a subtree of (CatBij tree-with-bud-inserted). I.e., for each tree A014486(n), we compute Sum_{i=0}^A072643(n) (1 if catbij(n) is a subtree of catbij(A153250bi(n,i)), 0 otherwise). Here A153250 gives the bud-inserting operation. Note that for any Catalan Bijection, which is an image of "psi" isomorphism (see A153141) from the Automorphism Group of infinite binary trees, the result will be A000004, the zero-sequence. To satisfy that condition, CatBij should at least satisfy A127302(CatBij(n)) = A127302(n) for all n (clearly A057164 does not satisfy that, so we got nonzero terms here). However, that is just a necessary but not a sufficient condition. For example, A123493 & A123494 satisfy it, but they still produce nonzero sequences: A153247, A153248.