A123503 An involution of nonnegative integers: signature permutation of a nonrecursive Catalan automorphism, row 253 of table A089840.

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

Offset: 0

Author

Antti Karttunen, Oct 11 2006

Keywords

• nonn

Comments

This automorphism either swaps (if A057515(n) > 1) the first two toplevel elements (of a general plane tree, like *A072796 does) and otherwise (if n > 1, A057515(n)=1) swaps the sides of the left hand side subtree of the S-expression (when viewed as a binary tree, like *A089854 does). This is illustrated below, where letters A, B and C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.

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

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

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

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

...x....(A072796)....x....................x...(A089854)...x

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

This is the first multiclause automorphism in table A089840 which cannot be represented as a composition of two smaller nonrecursive automorphisms, the property which is also shared by *A123499 and *A123500.

Links

• A. Karttunen, Prolog-program which illustrates the construction of this and other similar nonrecursive Catalan automorphisms.
• Index entries for signature-permutations of Catalan automorphisms

Crossrefs

Row 253 of A089840. Used to construct A123717 and A123718.