A125986 - OEIS

%I #8 Mar 22 2016 04:55:26

%S 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,

%T 52,51,62,54,55,41,39,53,40,38,37,63,57,58,46,44,59,49,50,36,33,47,34,

%U 29,28,56,45,48,35,31,43,32,27,25,42,30,26,24,23,196,191,192,178,177

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

%H A. Karttunen, <a href="/A125986/b125986.txt">Table of n, a(n) for n = 0..2055</a>

%H J. Vaillé, <a href="http://dx.doi.org/10.1006/eujc.1996.0089">Une Bijection Explicative de Plusieurs Propriétés Remarquables des Ponts</a>, European J. Combin. 18 (1997), no. 1, 117-124.

%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>

%o (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))))

%o (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)))))))

%o (define (binlist->n binlist) (let loop ((s 0) (bl binlist)) (if (null? bl) s (loop (+ s s (car bl)) (cdr bl)))))

%o (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))))))

%o (define (>> n i) (if (zero? i) n (>> (floor->exact (/ n 2)) (- i 1))))

%o (define (<< n i) (if (<= i 0) (>> n (- i)) (<< (+ n n) (- i 1))))

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

%K nonn

%O 0,3

%A _Antti Karttunen_, Jan 02 2007