A125981 Signature-permutation of Deutsch's 2000 bijection on ordered trees.

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).

Links

Antti Karttunen, Table of n, a(n) for n = 0..2055

Emeric Deutsch, A bijection on ordered trees and its consequences, J. Comb. Theory, A, 90, 210-215, 2000.

Index entries for signature-permutations of Catalan automorphisms

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

Adjacent sequences: A125978 A125979 A125980 * A125982 A125983 A125984

Keyword

nonn

Author

Antti Karttunen, Jan 02 2007

Status

approved