A125985 Signature-permutation of Vaillé's 1997 bijection on 'bridges' (Dyck paths).

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

Offset: 0

Author

Antti Karttunen, Jan 02 2007

Keywords

• nonn

Comments

Vaillé shows in 1997 paper that this automorphism transforms a 'derivation' of a Dyck path to its 'compression', i.e., in OEIS terms, A125985(A126310(n)) = A126309(A125985(n)) holds for all n. He also proves that A057515(A125985(n)) = A126307(n) and A057514(A125985(n)) = A072643(n) - A057514(n) + 1 (the latter identity for all n >= 1).

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

Crossrefs

Inverse: A125986. The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A126291, A126292 and A126293. The fixed points are given by A126300/A126301.

Programs

Scheme

(define (A125985 n) (A080300 (rising-list->binexp (A125985-aux2 (A014486 n)))))
(define (A125985-aux2 n) (let loop ((lists (A125985-aux1 n)) (z (list)) (m 1)) (if (null? lists) z (loop (cdr lists) (m-join z (car lists) m) (+ m 1)))))
(define (A125985-aux1 n) (if (zero? n) (list) (let ((begin_from (<< 1 (- (- (A000523 n) (A090996 n)) 1)))) (let loop ((s (A090996 n)) (t 0) (nth_list 1) (p begin_from) (b (if (= 0 (A004198bi n begin_from)) 0 1)) (lists (list (list)))) (cond ((< s 1) (cond ((< p 1) (reverse! lists)) (else (loop (- t (- 1 b)) b (+ 1 nth_list) (>> p 1) (if (= 0 (A004198bi n (>> p 1))) 0 1) (cons (list (+ b 1 nth_list)) lists))))) (else (loop (- s (- 1 b)) (+ t b) nth_list (>> p 1) (if (= 0 (A004198bi n (>> p 1))) 0 1) (cons (cons (+ b nth_list) (car lists)) (cdr lists)))))))))
(define (A125985-aux2 n) (let loop ((lists (A125985-aux1 n)) (z (list)) (m 1)) (if (null? lists) z (loop (cdr lists) (m-join z (car lists) m) (+ m 1)))))
(define (m-join a b m) (let loop ((a a) (b b) (c (list))) (cond ((and (not (pair? a)) (not (pair? b))) (reverse! c)) ((not (pair? a)) (loop a (cdr b) (cons (car b) c))) ((not (pair? b)) (loop (cdr a) b (cons (car a) c))) ((equal? (car a) (car b)) (loop (cdr a) (cdr b) (cons (car a) c))) ((> (car b) m) (loop a (cdr b) (cons (car b) c))) (else (loop (cdr a) b (cons (car a) c))))))
(define (rising-list->binexp rising-list) (let loop ((s 0) (i 0) (h 0) (fs rising-list)) (cond ((null? fs) (+ s (<< (- (<< 1 h) 1) i))) ((> (car fs) h) (loop s (+ i 1) (car fs) (cdr fs))) (else (loop (+ s (<< (- (<< 1 (+ 1 (- h (car fs)))) 1) i)) (+ i 2 (- h (car fs))) (car fs) (cdr fs))))))
(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))))