login
A125981
Signature-permutation of Deutsch's 2000 bijection on ordered trees.
3
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, 50, 49, 54, 55, 61, 63, 64, 57, 59, 62, 58, 31, 32, 34, 36, 35, 40, 41, 43, 44, 47, 52, 53, 60, 56, 26, 27, 29, 30, 33, 38, 39, 42, 51, 24, 25, 28, 37, 23, 129, 130, 132, 134, 133
OFFSET
0,3
COMMENTS
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)).
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).
PROG
(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)))))))
CROSSREFS
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.
Sequence in context: A057161 A130363 A089862 * A122326 A130996 A125984
KEYWORD
nonn
AUTHOR
Antti Karttunen, Jan 02 2007
STATUS
approved