A126305 -id:A126305 - cp's OEIS frontend

A126303 a(n) = number of nodes with odd distance to the root in the n-th plane general tree encoded by A014486(n). Both internal and terminal nodes (leaves) are counted.

0, 1, 2, 1, 3, 2, 2, 1, 2, 4, 3, 3, 2, 3, 3, 2, 2, 1, 2, 3, 2, 3, 2, 5, 4, 4, 3, 4, 4, 3, 3, 2, 3, 4, 3, 4, 3, 4, 3, 3, 2, 3, 3, 2, 2, 1, 2, 3, 2, 3, 2, 4, 3, 3, 2, 3, 4, 3, 4, 3, 3, 2, 3, 2, 3, 6, 5, 5, 4, 5, 5, 4, 4, 3, 4, 5, 4, 5, 4, 5, 4, 4, 3, 4, 4, 3, 3, 2, 3, 4, 3, 4, 3, 5, 4, 4, 3, 4, 5, 4, 5, 4

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

			A014486(27) = 696 (1010111000 in binary), encodes the following general plane tree, where the root is marked with * and nodes with even or odd distance to root with 'e's and 'o's, respectively.
.......o
.......|
.......e
.......|
...o.o.o
....\|/.
.....*..
there are four nodes marked with 'o', thus a(27)=4.

a(n) = A072643(n)-A126305(n). Cf. A126304. Scheme-function A014486->parenthesization given in A014486.

A126304 a(n) = number of nodes with nonzero even distance to the root in the n-th plane general tree encoded by A014486(n).

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 1, 1, 2, 2, 3, 2, 1, 2, 1, 2, 0, 1, 1, 2, 1, 1, 2, 2, 3, 2, 1, 2, 1, 2, 1, 2, 2, 3, 2, 2, 3, 3, 4, 3, 2, 3, 2, 3, 1, 2, 2, 3, 2, 1, 2, 1, 2, 2, 3, 2, 3, 2, 0, 1, 1, 2, 1, 1, 2, 2, 3, 2, 1, 2, 1, 2, 1, 2, 2, 3, 2, 2, 3, 3, 4, 3, 2, 3, 2, 3, 1, 2, 2, 3, 2, 1, 2, 1, 2

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

			A014486(27) = 696 (1010111000 in binary), encodes the following general plane tree, where the root is marked with * and nodes with even or odd distance to root with 'e's and 'o's, respectively.
.......o
.......|
.......e
.......|
...o.o.o
....\|/.
.....*..
there is one node marked with 'e', thus a(27)=1.

a(n) = A126305(n)-1. Cf. A126303. Scheme-function A014486->parenthesization given in A014486.

(define (A126304 n) (*A126304 (A014486->parenthesization (A014486 n))))
(define (*A126304 s) (cond ((null? s) 0) (else (apply + (map *A126303 s)))))

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

Original entry on oeis.org

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

Antti Karttunen, Jan 02 2007

nonn

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

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

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.

cp's OEIS Frontend

A126303 a(n) = number of nodes with odd distance to the root in the n-th plane general tree encoded by A014486(n). Both internal and terminal nodes (leaves) are counted.

Views

Author

Keywords

Examples

Crossrefs

A126304 a(n) = number of nodes with nonzero even distance to the root in the n-th plane general tree encoded by A014486(n).

Views

Author

Keywords

Examples

Crossrefs

Programs

Scheme

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

Views

Author

Keywords

Comments

Links

Crossrefs