cp's OEIS Frontend

A127291 Signature-permutation of Elizalde's and Deutsch's 2003 bijection for Dyck paths.

%I A127291 #22 Dec 14 2023 14:24:20
%S A127291 0,1,3,2,6,7,8,5,4,15,18,14,16,17,20,22,19,11,12,21,13,10,9,39,47,40,
%T A127291 48,50,41,49,38,43,46,37,42,44,45,53,60,54,61,63,55,62,52,29,32,51,28,
%U A127291 30,31,59,64,57,34,36,56,33,25,26,58,35,27,24,23,113,136,116,139,146
%N A127291 Signature-permutation of Elizalde's and Deutsch's 2003 bijection for Dyck paths.
%C A127291 Deutsch and Elizalde show in their paper that this automorphism converts certain properties concerning "tunnels" of Dyck path to another set of properties concerning the number of hills, even and odd rises, as well as the number of returns (A057515), thus proving the equidistribution of the said parameters.
%C A127291 This automorphism is implemented with function "tau" (Scheme code given below) that takes as its arguments an S-expression and a Catalan automorphism that permutes only the top level of the list (i.e., the top-level branches of a general tree, or the whole arches of a Dyck path) and thus when the permuting automorphism is applied to a list (parenthesization) of length 2n it induces some permutation of [1..2n].
%C A127291 This automorphism is induced in that manner by the automorphism *A127287 and likewise, *A127289 is induced by *A127285, *A057164 by *A057508, *A057501 by *A057509 and *A057502 by *A057510.
%C A127291 Note that so far these examples seem to satisfy the homomorphism condition, e.g., as *A127287 = *A127285 o *A057508 so is *A127291 = *A127289 o *A057164. and likewise, as *A057510 = *A057508 o *A057509 o *A057508, so is *A057502 = *A057164 o *A057501 o *A057164.
%C A127291 However, it remains open what are the exact criteria of the "picking automorphism" and the corresponding permutation that this method would induce a bijection. For example, if we give *A127288 (the inverse of *A127287) to function "tau" it will not induce *A127292 and actually not a bijection at all.
%C A127291 Instead, we have to compute the inverse of this automorphism with another, more specific algorithm that implements Deutsch's and Elizalde's description and is given in A127300.
%H A127291 A. Karttunen, <a href="/A127291/b127291.txt">Table of n, a(n) for n = 0..2055</a>
%H A127291 Emeric Deutsch and Sergi Elizalde, <a href="http://www.msri.org/people/members/elizalde/papers/Eliz-p.pdf">A simple and unusual bijection for Dyck paths and its consequences</a>, Annals of Combinatorics, 7 (2003), no. 3, 281-297.
%H A127291 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>
%o A127291 (MIT/GNU Scheme)
%o A127291 (define (A127291 n) (tau (A014486->parenthesization (A014486 n)) *A127287!)) ;; A014486->parenthesization is given in A014486.
%o A127291 (define (tau s permuter) (let* ((sper (transpos-list->permvec (sexp->kk s))) (visivec (make-vector (vector-length sper) ()))) (let loop ((tper (if (null? s) s (permuter (iota0 (-1+ (vector-length sper)))))) (s 0)) (cond ((null? tper) (A080300 s)) (else (let ((x (vector-ref sper (car tper)))) (cond ((not (vector-ref visivec x)) (vector-set! visivec (car tper) #t) (loop (cdr tper) (+ s s 1))) (else (loop (cdr tper) (+ s s))))))))))
%o A127291 (define (transpos-list->permvec tplist) (let ((permvec (make-initialized-vector (* 2 (length tplist)) (lambda (i) i)))) (let loop ((tplist tplist)) (cond ((null? tplist) permvec) (else (let* ((tp (car tplist)) (x (car tp)) (y (cdr tp)) (temp (vector-ref permvec x))) (vector-set! permvec x (vector-ref permvec y)) (vector-set! permvec y temp) (loop (cdr tplist)))))))) ;; Converts a list of transpositions to a permutation vector [0..(n-1)]
%o A127291 (define (iota0 upto_n) (let loop ((n upto_n) (result (list))) (cond ((zero? n) (cons 0 result)) (else (loop (- n 1) (cons n result)))))) ;; (iota0 5) gives (0 1 2 3 4 5)
%o A127291 (define (sexp->kk p) (let ((c (list (list))) (maxnode (list -1))) (let recurse ((p p)) (cond ((pair? p) (let ((this-trans (cons (1+ (car maxnode)) 0))) (set-car! maxnode (1+ (car maxnode))) (attach! this-trans c) (recurse (car p)) (set-car! maxnode (1+ (car maxnode))) (set-cdr! this-trans (car maxnode)) (recurse (cdr p)))))) (cdr (reverse! c)))) ;; Converts a symbolless S-expression to a list of noncrossing transpositions in a standard way.
%o A127291 (define (attach! elem lista) (set-cdr! lista (cons (car lista) (cdr lista))) (set-car! lista elem) lista) ;; Attaches an element physically to the front of nonempty list.
%Y A127291 Inverse: A127292. a(n) = A127289(A057164(n)) = A057164(A127299(A057164(n))). A127291(A057548(n)) = A072795(A127291(n)), A127291(A072795(n)) = A127307(A127291(A057502(n))) for all n >= 1. 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 A127293, A127294 and A127295. Number of fixed points begins as 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, ...
%K A127291 nonn,look
%O A127291 0,3
%A A127291 _Antti Karttunen_, Jan 16 2007