A106456 Natural numbers mapped to Dyck path encodings of the rooted plane trees obtained by recursing on the exponents of the GF(2)[X] factorization of n.

0, 10, 1010, 1100, 110010, 101100, 101010, 110100, 10110010, 11001100, 10101010, 10110100, 1010101010, 10101100, 11010010, 111000, 11100010, 1011001100, 101010101010, 1100110100, 11001010, 1010101100, 101010110010

Offset

1,2

Comments

Note that we recurse on the exponent + 1 for all other irreducible polynomials except the largest one in the GF(2)[X] factorization. Thus for 6 = A048723(3,1) X A048723(2,1) we construct a tree by joining trees 1 and 2 with a new root node, for 7 = A048723(7,1) X A048723(3,0) X A048723(2,0) we join three 1-trees (single leaves) with a new root node, for 8 = A048273(2,3) we add a single edge below tree 3 and for 9 = A048723(7,1) X A048723(3,1) X A048273(2,0) we connect the trees 1 and 2 and 1 with a new root node.

Links

Table of n, a(n) for n=1..23.

A. Karttunen, Scheme-program for computing this sequence.

Example

The rooted plane trees encoded here are:
.....................o....o..........o.........o...o....o.....
.....................|....|..........|..........\./.....|.....
.......o....o...o....o....o...o..o...o..o.o.o....o....o.o.o...
.......|.....\./.....|.....\./....\./....\|/.....|.....\|/....
*......*......*......*......*......*......*......*......*.....
1......2......3......4......5......6......7......8......9.....

Crossrefs

a(n) = A007088(A106455(n)) = A075166(A106443(n)). GF(2)[X]-analog of A075166. Permutation of A063171. Same sequence shown in decimal: A106455. The digital length of each term / 2 (the number of o-nodes in the corresponding trees) is given by A106457. Cf. A106451-A106454.

Sequence in context: A075166 A071671 A075171 * A079214 A377192 A163662

Adjacent sequences: A106453 A106454 A106455 * A106457 A106458 A106459

Keyword

nonn,base

Author

Antti Karttunen, May 09 2005

Status

approved