%I #14 May 19 2024 08:07:00
%S 0,1,3,2,7,8,5,6,4,17,18,20,22,21,12,13,15,16,19,10,11,14,9,45,46,48,
%T 50,49,54,55,61,63,64,57,59,62,58,31,32,34,36,35,40,41,43,44,47,52,53,
%U 60,56,26,27,29,30,33,38,39,42,51,24,25,28,37,23,129,130,132,134,133
%N Signature-permutation of Deutsch's 2000 bijection on ordered trees.
%C Deutsch shows in his 2000 paper that this automorphism converts any ordered tree with the number of nodes having degree q to a tree with an equal number of odd-level nodes having degree q-1, from which it follows that, for each positive integer q, the parameters "number of nodes of degree q" and "number of odd-level nodes of degree q-1" are equidistributed. He also shows that this automorphism converts any tree with k leaves to a tree with k even-level nodes, i.e., in OEIS terms, A057514(n) = A126305(A125981(n)).
%C To obtain the signature permutation, we apply the given Scheme-function *A125981 to the parenthesizations as encoded and ordered by A014486/A063171 (and surrounded by extra pair of parentheses to make a valid Scheme-list) and for each n, we record the position of the resulting parenthesization (after discarding the outermost parentheses from the Scheme-list) in A014486/A063171 and this value will be a(n).
%H Antti Karttunen, <a href="/A125981/b125981.txt">Table of n, a(n) for n = 0..2055</a>
%H Emeric Deutsch, <a href="https://doi.org/10.1006/jcta.1999.3027">A bijection on ordered trees and its consequences</a>, J. Comb. Theory, A, 90, 210-215, 2000.
%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>
%o (Scheme implementation of this automorphism that acts on S-expressions, i.e. list-structures:) (define (*A125981 s) (cond ((null? s) s) (else (append (*A125981 (car s)) (list (map *A125981 (cdr s)))))))
%Y Inverse: A125982. The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of this permutation seem to be given by A089411, A086586 and A089412, thus this is probably a conjugate of A074683/A074684. A125983 gives the A057163-conjugate.
%K nonn
%O 0,3
%A _Antti Karttunen_, Jan 02 2007