|
Search: id:A075166
|
|
|
| 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
12
|
|
| 0, 10, 1010, 1100, 101010, 101100, 10101010, 110100, 110010, 10101100, 1010101010, 10110100, 101010101010, 1010101100, 10110010, 111000, 10101010101010, 11001100, 1010101010101010, 1010110100, 1010110010
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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
|
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 (Antti.Karttunen(AT)iki.fi), 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.....
|
|
PROGRAM
|
(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: A098753 A066489 A063171 this_sequence A071671 A075171 A106456
Adjacent sequences: A075163 A075164 A075165 this_sequence A075167 A075168 A075169
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
Antti Karttunen Sep 13 2002
|
|
|
Search completed in 0.002 seconds
|
