0,3

A. Karttunen, Gatomorphisms

Index entries for sequences that are permutations of the natural numbers

(Scheme functions below show the essential idea. For a complete source, follow the "Gatomorphisms" link.)

(define arithrankA061579->lexrank (arithrank->lexrank-bijection A002262 A025581))

(define (arithrank->lexrank-bijection pr1 pr2) (lambda (n) (CatalanRankGlobal (parenthesization->binexp (unrank-bintree n pr1 pr2)))))

(define (unrank-bintree rank pr1 pr2) (cond ((zero? rank) (list)) (else (cons (unrank-bintree (pr1 (-1+ rank)) pr1 pr2) (unrank-bintree (pr2 (-1+ rank)) pr1 pr2)))))

(define (A002262 n) (- n (binomial_n_2 (floor->exact (+ (/ 1 2) (sqrt (* 2 (1+ n))))))))

(define (A025581 n) (- (binomial_n_2 (1+ (floor->exact (+ (/ 1 2) (sqrt (* 2 (1+ n))))))) (1+ n)))

Inverse permutation: A071651. A071671 gives the corresponding parenthesizations (from the term 1 onward) encoded as binary numbers, i.e. A071671(n) = A063171(A071652(n)) for n >= 1.

A071652(n) = A057163(A071654(n)). Cf. also A014486, A002262, A025581, A071653, A071654.

Sequence in context: A130264 A072659 A072766 this_sequence A089884 A086163 A071789

Adjacent sequences: A071649 A071650 A071651 this_sequence A071653 A071654 A071655

nonn,tabl

Antti Karttunen May 30 2002