|
%I #23 Mar 30 2024 17:21:39
%S 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,
%T 49,50,54,55,57,58,59,61,62,63,64,44,47,53,56,60,42,51,37,23,24,38,25,
%U 26,27,43,52,39,28,29,40,30,31,32,41,33,34,35,36,129,130,132,133,134
%N 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.
%C 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):
%C A B B A
%C \ / --> \ /
%C x x
%C (a . b) -----> (b . a)
%C 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.
%C 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.
%H A. Karttunen, <a href="/A069770/b069770.txt">Table of n, a(n) for n = 0..2055</a>
%H A. Karttunen, <a href="/A089840/a089840p.txt">Prolog-program which illustrates the construction of this and similar nonrecursive Catalan automorphisms.</a>
%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>
%F a(n) = A154125(A154126(n)) = A154126(A154125(n)).
%F a(n) = A083927(A072796(A057123(n))) = A083927(A057508(A057123(n))) = A083927(A057509(A057123(n))).
%e 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:
%e .
%e one tree of one internal
%e empty tree (non-leaf) node
%e x \/
%e n= 0 1
%e a(n)= 0 1 (both are always fixed)
%e .
%e the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are:
%e .
%e \/ \/ \/ \/
%e \/ \/ \/ \/ \/ \/ \/ \/
%e \/ \/ \/ \/ \_/ \/ \/
%e n= 2 3 4 5 6 7 8
%e .
%e and the new shapes after swapping their left and right hand subtrees are:
%e .
%e \/ \/ \/ \/
%e \/ \/ \/ \/ \/ \/ \/ \/
%e \/ \/ \/ \/ \_/ \/ \/
%e a(n)= 3 2 7 8 6 4 5
%e thus we obtain the first nine terms of this sequence: 0, 1, 3, 2, 7, 8, 6, 4, 5.
%o (Scheme implementations of this automorphism. These act on S-expressions, i.e. list-structures:)
%o (CONSTRUCTIVE VERSION:) (define (*A069770 s) (if (pair? s) (cons (cdr s) (car s)) s))
%o (DESTRUCTIVE VERSION:) (define (*A069770! s) (if (pair? s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car))) s)
%Y Row 1 of A089840.
%Y The number of cycles and the number of fixed points in each subrange limited by terms of A014137 are given by A007595 and A097331.
%Y Other related sequences: A014486, A057163, A069767, A069768, A089864, A123492, A154125, A154126.
%Y Cf. also A127302, A153835.
%K nonn
%O 0,3
%A _Antti Karttunen_, Apr 16 2002.
%E Entry revised by _Antti Karttunen_, Oct 11 2006 and Mar 30 2024
|
