A126310 -id:A126310 - cp's OEIS frontend

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

Antti Karttunen, Jan 02 2007

nonn

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

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

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.

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

A126309 A014486-index for the Dyck path "compressed" from the n-th Dyck path encoded by A014486(n).

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 1, 1, 3, 0, 1, 1, 1, 3, 1, 2, 1, 1, 3, 3, 3, 3, 8, 0, 1, 1, 1, 3, 1, 2, 1, 1, 3, 3, 3, 3, 8, 1, 2, 2, 2, 5, 1, 2, 1, 1, 3, 3, 3, 3, 8, 3, 6, 3, 3, 7, 3, 3, 3, 8, 8, 8, 8, 8, 22, 0, 1, 1, 1, 3, 1, 2, 1, 1, 3, 3, 3, 3, 8, 1, 2, 2, 2, 5, 1, 2, 1, 1, 3, 3, 3, 3, 8, 3, 6, 3, 3, 7, 3, 3, 3, 8

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

According to Vaillé, the concept of "compression d'un pont" was introduced by Poupard, in "Sur les quasi-ponts" paper. In effect, the operation removes all the peaks /\ from the Dyck path.

			A014486(4) encodes the Dyck path /\/\/\, of which, when all the peaks are removed, nothing remains, thus a(4)=0. A014486(18) encodes the Dyck path:
....../\
.../\/..\
../......\,
which, after the peaks are removed, results
.../\,
../..\ encoded by A014486(3), thus a(18)=3.

Y. Poupard, Sur les quasi-ponts, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 32, Paris, 1979, pp. 3-20.
J. Vaillé, Une Bijection Explicative de Plusieurs Propriétés Remarquables des Ponts, European J. Combin. 18 (1997), no. 1, 117-124.

Cf. A014486, A080300, A125985, A125986, A126308, A126310.

a(n) = A080300(A126308(A014486(n))).

a(n) = A125985(A126310(A125986(n))).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme