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,3

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

Prog

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

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.

Sequence in context: A122357 A122298 A122337 * A073282 A089859 A130958

Adjacent sequences: A125982 A125983 A125984 * A125986 A125987 A125988

Keyword

nonn

Author

Antti Karttunen, Jan 02 2007

Status

approved