A125986 Signature-permutation of the inverse of Vaillé's 1997 bijection on Dyck paths.

0, 1, 3, 2, 8, 6, 7, 5, 4, 22, 19, 20, 15, 14, 21, 17, 18, 13, 11, 16, 12, 10, 9, 64, 60, 61, 52, 51, 62, 54, 55, 41, 39, 53, 40, 38, 37, 63, 57, 58, 46, 44, 59, 49, 50, 36, 33, 47, 34, 29, 28, 56, 45, 48, 35, 31, 43, 32, 27, 25, 42, 30, 26, 24, 23, 196, 191, 192, 178, 177

Offset

0,3

Links

A. Karttunen, Table of n, a(n) for n = 0..2055

J. Vaillé, Une Bijection Explicative de Plusieurs Propriétés Remarquables des Ponts, European J. Combin. 18 (1997), no. 1, 117-124.

Index entries for signature-permutations of Catalan automorphisms

Prog

(MIT Scheme:) (define (A125986 n) (let ((z (reduce append! '() (reverse! (descending-list->bin-lists (binexp->A071158-list (A014486 n)))))) (tl (A057515 n))) (A080300 (/ (+ (<< (- (<< 1 tl) 1) (+ (length z) 1)) (binlist->n z)) 2))))
(define (descending-list->bin-lists rl) (let loop ((z (list)) (m 1)) (let ((sl (map (lambda (n) (- n m)) (keep-matching-items rl (lambda (n) (or (= n m) (= n (+ 1 m)))))))) (cond ((null? sl) z) (else (loop (cons sl z) (+ m 1)))))))
(define (binlist->n binlist) (let loop ((s 0) (bl binlist)) (if (null? bl) s (loop (+ s s (car bl)) (cdr bl)))))
(define (binexp->A071158-list n) (let loop ((n n) (lista (list)) (h 1)) (cond ((zero? n) lista) ((odd? n) (loop (/ (- n 1) 2) lista (- h 1))) (else (loop (/ n 2) (cons h lista) (1+ h))))))
(define (>> n i) (if (zero? i) n (>> (floor->exact (/ n 2)) (- i 1))))
(define (<< n i) (if (<= i 0) (>> n (- i)) (<< (+ n n) (- i 1))))

Crossrefs

Inverse: A125985. Cf. A057515, A071158. Algorithm is partially described in A126301.

Sequence in context: A071667 A057506 A086427 * A131155 A085174 A131164

Adjacent sequences: A125983 A125984 A125985 * A125987 A125988 A125989

Keyword

nonn

Author

Antti Karttunen, Jan 02 2007

Status

approved