|
%I #14 Mar 28 2014 23:38:10
%S 0,10,1010,1100,101010,101100,10101010,110100,110010,10101100,
%T 1010101010,10110100,101010101010,1010101100,10110010,111000,
%U 10101010101010,11001100,1010101010101010,1010110100,1010110010
%N Natural numbers mapped to Dyck path encodings of the rooted plane trees obtained by recursing on the exponents of the prime factorization of n.
%C 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.
%H A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/Nekomorphisms/ACO1.htm">Alternative Catalan Orderings</a> (with the complete Scheme source)
%H A. Karttunen, <a href="/A091247/a091247.scm.txt">Complete Scheme-program for computing this sequence.</a>
%F a(n) = A007088(A075165(n)) = A106456(A106442(n)). - _Antti Karttunen_, May 09 2005
%e The rooted plane trees encoded here are:
%e .....................o...............o.........o...o..o.......
%e .....................|...............|..........\./...|.......
%e .......o....o...o....o....o.o.o..o...o.o.o.o.o...o....o...o...
%e .......|.....\./.....|.....\|/....\./...\|.|/....|.....\./....
%e *......*......*......*......*......*......*......*......*.....
%e 1......2......3......4......5......6......7......8......9.....
%o (Scheme functions showing the essential idea. For the complete source, follow the "Alternative Catalan Orderings" link:)
%o (define (A075166 n) (A007088 (parenthesization->binexp (primefactorization->parenthesization n))))
%o (define (primefactorization->parenthesization n) (map primefactorization->parenthesization (explist->Nvector! (primefactorization->explist n))))
%o Function primefactorization->explist maps 1 to (), 2 to (1), 3 to (1 0), 4 to (2), 12 to (1 2), etc.
%o (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)
%Y 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.
%K nonn,nice,base
%O 1,2
%A _Antti Karttunen_, Sep 13 2002
| 