cp's OEIS Frontend

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

%I A125985 #13 Jul 07 2025 16:14:19
%S A125985 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,
%T A125985 62,58,50,49,61,55,57,46,48,54,45,36,35,32,34,31,60,56,41,52,40,47,53,
%U A125985 43,44,27,26,33,29,30,51,38,39,42,24,25,28,37,23,196,195,190,194,189
%N A125985 Signature-permutation of Vaillé's 1997 bijection on 'bridges' (Dyck paths).
%C A125985 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).
%H A125985 A. Karttunen, <a href="/A125985/b125985.txt">Table of n, a(n) for n = 0..2055</a>
%H A125985 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 A125985 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>
%o A125985 (Scheme) (define (A125985 n) (A080300 (rising-list->binexp (A125985-aux2 (A014486 n)))))
%o A125985 (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)))))
%o A125985 (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)))))))))
%o A125985 (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)))))
%o A125985 (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))))))
%o A125985 (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))))))
%o A125985 (define (>> n i) (if (zero? i) n (>> (floor->exact (/ n 2)) (- i 1))))
%o A125985 (define (<< n i) (if (<= i 0) (>> n (- i)) (<< (+ n n) (- i 1))))
%Y A125985 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.
%K A125985 nonn
%O A125985 0,3
%A A125985 _Antti Karttunen_, Jan 02 2007