%I #5 May 01 2014 02:47:43
%S 0,1,3,2,6,5,13,8,4,14,10,36,20,9,25,19,24,11,12,18,38,16,7,44,27,209,
%T 77,21,105,66,104,28,35,65,230,54,15,34,33,75,43,26,85,50,40,37,22,31,
%U 191,67,23,51,41,69,107,68,49,92,30,29,32,56,211,46,17,299,120,5671
%N Permutation of natural numbers induced by reranking plane binary trees given in the standard lexicographic order (A014486) with an "arithmetic global ranking algorithm", using A072734 as the packing bijection N X N -> N.
%C This ranking scheme condenses the structures of the same size (cf. A072789) somewhat better than scheme presented in A072656 (which uses the N X N -> N bijection A072793). Compare the sequences A072790 and A072640 giving the max positions where the last structure with size n will occur in these orderings and the respective binary widths A072791 & A072642. However, by using the second or third power of the bijection A072734 one gets even better results in a certain range.
%H A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/Nekomorphisms/gatomorf.htm">Gatomorphisms</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%o (Scheme functions below show the essential idea. For a complete source, follow the "Gatomorphisms" link.)
%o (define A072787 (lexrank->arithrank-bijection packA072734))
%o (define (lexrank->arithrank-bijection packfun) (lambda (n) (rank-bintree (binexp->parenthesization (A014486 n)) packfun)))
%o (define (rank-bintree bt packfun) (cond ((not (pair? bt)) 0) (else (1+ (packfun (rank-bintree (car bt) packfun) (rank-bintree (cdr bt) packfun))))))
%Y Inverse permutation: A072788. Cf. also A014486, A072734, A072789.
%K nonn
%O 0,3
%A _Antti Karttunen_, Jun 12 2002
|