A075166 Natural numbers mapped to Dyck path encodings of the rooted plane trees obtained by recursing on the exponents of the prime factorization of n.

0, 10, 1010, 1100, 101010, 101100, 10101010, 110100, 110010, 10101100, 1010101010, 10110100, 101010101010, 1010101100, 10110010, 111000, 10101010101010, 11001100, 1010101010101010, 1010110100, 1010110010

Offset

1,2

Comments

Note that we recurse on the exponent + 1 for all other primes except the largest one in the factorization. Thus for 6 = 3^1 * 2^1 we construct a tree by joining trees 1 and 2 with a new root node, for 7 = 7^1 * 5^0 * 3^0 * 2^0 we join four 1-trees (single leaves) with a new root node, for 8 = 2^3 we add a single edge below tree 3 and for 9 = 3^2 * 2^0 we join trees 2 and 1, to get the mirror image of tree 6. Compare to Matula/Goebel numbering of (unoriented) rooted trees as explained in A061773.

Links

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

A. Karttunen, Alternative Catalan Orderings (with the complete Scheme source)

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

Formula

a(n) = A007088(A075165(n)) = A106456(A106442(n)). - Antti Karttunen, May 09 2005

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

Prog

(Scheme functions showing the essential idea. For the complete source, follow the "Alternative Catalan Orderings" link:)
(define (A075166 n) (A007088 (parenthesization->binexp (primefactorization->parenthesization n))))
(define (primefactorization->parenthesization n) (map primefactorization->parenthesization (explist->Nvector! (primefactorization->explist n))))
Function primefactorization->explist maps 1 to (), 2 to (1), 3 to (1 0), 4 to (2), 12 to (1 2), etc.
(define (explist->Nvector! el) (cond ((pair? el) (let loop ((el (cdr el))) (cond ((pair? el) (set-car! el (1+ (car el))) (loop (cdr el))))))) el)

Crossrefs

Permutation of A063171. Same sequence shown in decimal: A075165. The digital length of each term / 2 (the number of o-nodes in the corresponding trees) is given by A075167. Cf. A075171, A007088.

Sequence in context: A276758 A066489 A063171 * A071671 A075171 A106456

Adjacent sequences: A075163 A075164 A075165 * A075167 A075168 A075169

Keyword

nonn,nice,base

Author

Antti Karttunen, Sep 13 2002

Status

approved