login
Signature-permutation of A057164-conjugate of the inverse of Elizalde's and Deutsch's 2003 bijection for Dyck paths.
5

%I #8 Dec 14 2023 14:24:30

%S 0,1,3,2,8,4,7,6,5,22,11,17,16,12,21,9,20,19,10,18,14,13,15,64,33,48,

%T 47,34,58,23,57,56,24,49,37,35,38,63,30,45,44,31,62,28,61,60,29,46,42,

%U 32,43,59,25,54,53,26,50,39,36,40,55,51,27,52,41,196,102,145,144,103

%N Signature-permutation of A057164-conjugate of the inverse of Elizalde's and Deutsch's 2003 bijection for Dyck paths.

%C Used to construct the inverse for A127291.

%D Emeric Deutsch and Sergi Elizalde, A simple and unusual bijection for Dyck paths and its consequences, Annals of Combinatorics, 7 (2003), no. 3, 281-297.

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

%o (MIT/GNU Scheme)

%o (define (A127300 n) (A080300 (transpos-list->A014486 (A127300-aux1 (A014486 n)))))

%o (define (transpos-list->A014486 tplist) (fold-left (lambda (s p) (+ s (expt 2 (max (car p) (cdr p))))) 0 tplist))

%o (define (a127300-aux1 n) (if (zero? n) (list) (let loop ((n n) (tplist1 (list)) (tplist2 (list)) (i 0) (j (A000523 n)) (b 1)) (cond ((zero? n) (append tplist1 tplist2)) ((even? n) (loop (/ n 2) tplist2 (cons (cons '() i) tplist1) j (+ i b) (- b))) ((assq '() tplist1) => (lambda (p) (set-car! p i) (loop (/ (- n 1) 2) tplist2 tplist1 j (+ i b) (- b)))) ((rassq '() tplist2) => (lambda (p) (set-car! p i) (loop (/ (- n 1) 2) tplist2 tplist1 j (+ i b) (- b)))) (else (error "n not in A014486!")))))) ;; Returns a list of non-crossing transpositions.

%o (define (rassq key al) (let loop ((al al) (last-found #f)) (cond ((null? al) last-found) ((eq? (caar al) key) (loop (cdr al) (car al))) (else (loop (cdr al) last-found))))) ;; (rassq key al) is essentially the same as: (assq key (reverse al))

%Y Inverse: A127299. a(n) = A057164(A127292(A057164(n))) = A127290(A057164(n)). Cf. A014486.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jan 16 2007