A069770 Signature permutation of the first non-identity, nonrecursive Catalan automorphism in table A089840: swap the top branches of a binary tree. An involution of nonnegative integers.

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

Offset: 0

Author

Antti Karttunen, Apr 16 2002

Keywords

• nonn

Comments

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.

Examples

			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 their left and right hand subtrees are:
.
                        \/     \/                     \/     \/
     \/         \/     \/       \/       \/ \/       \/       \/
      \/       \/       \/       \/       \_/       \/       \/
a(n)=  3        2        7        8        6        4        5
thus we obtain the first nine terms of this sequence: 0, 1, 3, 2, 7, 8, 6, 4, 5.
		

Links

• A. Karttunen, Table of n, a(n) for n = 0..2055
• A. Karttunen, Prolog-program which illustrates the construction of this and similar nonrecursive Catalan automorphisms.
• Index entries for signature-permutations of Catalan automorphisms

Crossrefs

Row 1 of A089840.

The number of cycles and the number of fixed points in each subrange limited by terms of A014137 are given by A007595 and A097331.

Other related sequences: A014486, A057163, A069767, A069768, A089864, A123492, A154125, A154126.

Cf. also A127302, A153835.

Formula

a(n) = A154125(A154126(n)) = A154126(A154125(n)).

a(n) = A083927(A072796(A057123(n))) = A083927(A057508(A057123(n))) = A083927(A057509(A057123(n))).

Extensions

Entry revised by Antti Karttunen, Oct 11 2006 and Mar 30 2024