/^creative ^commor ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 16 (2019) 445-463 https://doi.org/10.26493/1855-3974.1679.ad3 (Also available at http://amc-journal.eu) Ascending runs in permutations and valued Dyck paths* Marilena Barnabei Flavio Bonetti, Niccolo Castronuovo , Matteo Silimbani Dipartimento di Matematica, Universitä di Bologna, Bologna, 40126, Italy Received 18 April 2018, accepted 2 October 2018, published online 11 February 2019 Abstract We define a bijection between permutations and valued Dyck paths, namely, Dyck paths whose odd vertices are labelled with an integer that does not exceed their height. This map allows us to characterize the set of permutations avoiding the pattern 132 as the preimage of the set of Dyck paths with minimal labeling. Moreover, exploiting this bijection we associate to the set of n-permutations a polynomial that generalizes at the same time Eulerian polynomials, Motzkin numbers, super-Catalan numbers, little Schroder numbers, and other combinatorial sequences. Lastly, we determine the Hankel transform of the sequence of such polynomials. Keywords: Permutation, Dyck path, pattern avoidance, Hankel transform. Math. Subj. Class.: 05A05, 05A15, 05A19 1 Introduction Many bijections are present in the literature between the symmetric group Sn and the set of Dyck paths of semilength n with some kind of labeling on their steps (see e.g. [3, 8, 18]). In this paper, inspired by [3], we define a bijection r between permutations and valued Dyck paths, namely, Dyck paths whose odd vertices are labelled with an integer that does not exceed their height. More precisely, we write a permutation n as the juxtaposition of ascending runs, and associate to every integer i from 1 to n a pair of consecutive steps in the path according *This work was partially supported by the University of Bologna, funds for selected research topics. t Corresponding author. E-mail addresses: marilena.barnabei@unibo.it (Marilena Barnabei), flavio.bonetti@unibo.it (Flavio Bonetti), niccolo.castronuovo2@unibo.it (Niccolo Castronuovo), matteo.silimbani4@unibo.it (Matteo Silimbani) ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 445 Ars Math. Contemp. 16 (2019) 445-463 to the fact that i is the unique element of an ascending run (a head-tail) in n or the initial (head), final (tail) or middle element (boarder) of an ascending run of length greater or equal to two. Every pair of consecutive steps is labelled with an integer that depends on the respective position of the ascending runs in n. Observe that a similar construction was described in [11] in terms of peaks, valleys, double descents and double rises of the permutation. Given a permutation n = n1n2... nn, it turns out that for i = 1, n the entry n is (i) a head if and only if it is a valley; (ii) a tail if an only if it is a peak; (iii) a head-tail if and only if it is double descent; (iv) a boarder if and only if it is a double rise. However, n1 and nn may play different roles in the two environments, and this fact leads to different results. The present construction seems to shed new light on combinatorial properties of permutations. In particular the results of Section 5 seem to be difficult to obtain with the construction in [11]. The map r allows us to characterize the set of permutations avoiding the pattern 132 (213, resp.) as the preimage of the set of Dyck paths with minimal (maximal, respectively) labeling. In these particular cases it is possible to translate the ascending runs of the permutation directly in terms of tunnels of the Dyck path. As a consequence we get a bijection between the permutations avoiding 132 and those avoiding 213 that is new, up to our knowledge. If a permutation avoids 132 its ascending runs are the blocks of a non-crossing partition. Hence our map provides also a bijection between Dyck paths and non-crossing partitions, that turns out to be the same as the bijection introduced in [24]. In Section 5 we consider monomials in the variables H, S, B associated with each permutation according to the number of heads, head-tails and boarders. In this way we construct a polynomial Fn(H,S,B) as the sum of such monomials over all the permutations of length n. These polynomials generalize at the same time Eulerian numbers, factorials and many other sequences. We exploit the results of the previous sections to deduce a recurrence relation for these polynomials and a functional equation for their generating function. We also determine the Hankel transform of the sequence (Fn)n>0, hence obtaining both new and known results about the Hankel transform of various specializations of these polynomials. Finally, we consider the sequence of polynomials Fn(H,S,B), defined as the sum of the monomials that correspond to permutations avoiding 132. These polynomials specialize in many well-known sequences related to Catalan and Motzkin numbers. 2 The bijection A Dyck path of semilength n is a lattice path contained in N x N, starting in (0,0), ending in (2n, 0), consisting of unitary north-east steps of the form (1,1) and of unitary south-east steps of the form (1, -1) and lying above the x-axis. The north-east steps are called up steps (denoted by U) and the south-east steps are called down steps (denoted by D). As usual, a Dyck path can be identified with a word w = SiS2... S2n of length 2n in the alphabet {U, D} with the constraint that the number of occurrences of the letter U is equal to the number of occurrences of the letter D and, for every i, the number of M. Barnabei at al.: Ascending runs in permutations and valued Dyck paths 447 occurrences of U in the subword S1S2... Sj is not smaller than the number of occurrences of D. The word w is called a Dyck word. In the following we will not distinguish between a Dyck path and the corresponding word. We denote by Dn the set of Dyck path of semilength n. Given a Dyck path d e Dn, decompose it into 2-step subpaths d = d1d2...dn. The subpaths dj will be called dimers and the decomposition d = d1... dn will be called the dimer decomposition of d. For every i = 1,..., n, let kj be the y-coordinate of the middle point of the dimer dj. We associate to d the n-tuple m(d) = (m1, m2,..., mn), where mj = t1. We will call the integer mj the height of the dimer dj, and the n-tuple m(d) the height list of d. Example 2.1. Consider the Dyck path d = UU|UU|DD|UD|DD in Figure 1. Then Figure 1: The Dyck path d = UU|UU|DD|UD|DD. m(d) = (0, 1,1,1, 0). Let n = n1n2... nn be a permutation in Sn written in one-line notation. An ascending run in n is a maximal increasing subsequence of n. For example, the ascending runs of 346512 are w1 = 346, w2 =5 and w3 = 12. Write n as n = w1w2 . .. wk, where the wj's are the ascending runs in n. Let hj and tj be the first and the last element of wj. Note that hj and tj can coincide. We call hj and tj the head and the tail of wj. Clearly tj > hj+1 for 1 < i < k — 1. Now we associate to every permutation of length n a Dyck path d of semilength n defined as follows. For i = 1,..., n, (i) if i is both a head and a tail, set dj = UD; (ii) if i is a head but not a tail, set dj = UU; (iii) if i is a tail but not a head, set dj = DD; (iv) if i is neither a head nor a tail, set dj = DU. Then d = d1d2 ... dn. Obviously the correspondence 7: n ^ d is far from being injective. For example, both the permutations 3124 and 1243 in S4 correspond to the Dyck path UUDUUDDD. In order to get a bijection, we associate to the permutation n a valued Dyck path, namely a pair (d, l), where d is the Dyck path defined above and l = (11,12,..., 1n) is the sequence of non-negative integers given by 1j = |{j I hj < i < tj, tj precedes i in n}|. 448 Ars Math. Contemp. 16(2019)445-463 Example 2.2. Consider the permutation n = 1254367. The ascending runs of n are wi = 125, w2 =4 and w3 = 367. The heads and the tails of n are h1 = 1, h2 = 4, h3 = 3, t1 = 5, t2 = 4, and t3 = 7. The Dyck path associated with n is d = UU|DU|UU|UD|DD|DU|DD (in Figure 2). and the list l associated with the permu- Figure 2: The Dyck path d = UU|DU|UU|UD|DD|DU|DD. tation n is (0,0,1,1,0,0,0). We denote by r(n) the valued Dyck path associated with the permutation n. The next proposition describes the connection between the list l associated with n and the height list m(d). Proposition 2.3. Let n be a permutation in Sn. Set r(n) = (d, l), with l = (11,..., 1n). Let m(d) = (m1,..., mn) be the height list of d. Then, for all 1 < i < n, k < mj. Proof. Let i be an integer such that 1 < i < n. If d = d1d2... dn is the dimer decomposition of d, the integer m; can be written as mj = |{j | dj = UU, 0 < j < i}| - |{j | dj = DD, 0 < j < i}| - e where {0 if the first step of d; is an up step; 1 if the first step of d; is a down step. We notice that, denoting by hj and tj the j-th head and tail of n, respectively, the integer |{j | dj = UU, 0 < j < i}| is the number of heads hj such that hj < i, while |{j | dj = DD, 0 < j < i}| is the number of tails tj such that tj < i. Hence m; = |{j | hj k2 > k1. A similar argument can be used for the general case. Example 2.5. Consider the path d = UU| UD | UU| DD |DU|DD | UU| DD (see Figure 4). Then, m(d) = (0,1,1,1,0,0,0,0). In order to construct A(d, (0,0,0,1,0,0,0,0)), we apply the procedure P iteratively, starting with the triple (d, (1, 2, 3,4, 5, 6, 7, 8), (0, 0,0,1,0, 0, 0,0)). We represent the triple (d, A, l) as a Dyck path with the tags written below the path, while each integer k is placed close to the respective dimer dj. A dashed line is drawn for every height m.j. The white dots represent the vertices involved in the application of P. Figure 4: The Dyck path d = UU|UD|UU|DD|DU|DD|UU|DD. At the first application of P we have i = 4, d4 = DD, j = 1, k = 0, A1 = 1 and A4 = 4. The last ascending run of the permutation n is w1 = 14 and we get the new triple (see Figure 5): (UDUUDUDDUUDD, (2, 3, 5,6,7,8), (0,0,0,0,0,0)). Figure 5: Output of the first application of P. M. Barnabei at al.: Ascending runs in permutations and valued Dyck paths 451 At the second application of P, i = 1, d1 = UD, and Ai = 2, hence the permutation n ends now by w2w1 = 214. The output is now the triple (see Figure 6): (UUDUDDUUDD, (3, 5, 6, 7,8), (0,0,0,0,0)). Figure 6: Output of the second application of P. At the third step, i = 3, d3 = DD, j = 1, k = 1, j1 = 2, A1 = 3, A2 = 5, A3 = 6, so the permutation n ends now by w3w2 w1 = 356214 and we get the new triple (see Figure 7): (UUDD, (7, 8), (0,0)). Figure 7: Output of the third application of P. At this step we have i = 2, d2 = DD, j = 1, k = 0, Ai = 7, A2 = 8. Since the application of P produces now the empty triple, the permutation A(d, l) is n = 78356214. The following result assures that the maps r and A are inverse of each other. The proof is based on an alternative description of the map r. Although this description is more complicated than the previous one, it is the most suitable for that purpose. Theorem 2.6. Let n be a permutation of length n. Then A(r(n)) = n. Moreover, let (d, l) be an element of VCn. Then r(A(d,/)) = (d,l). 452 Ars Math. Contemp. 16(2019)445-463 Proof. The map r can be described as the result of the iteration of the following procedure Q. The procedure Q takes as input a triple (d, A, l) and an increasing sequence of numbers w where, as usual, [d, A] is a tagged Dyck path of semilength r, (d, l) G DLr and the elements of w are different from the elements of A. Q produces a triple (d', A', l') with the same properties, with d' a Dyck path of greater semilength. Set A = (Ai,..., Ar), l = (li,..., lr), w = xi... xk, and let d = di... dr, be the dimer decomposition of d. Hence, Ai is the tag of dj. Then (I) The new list of tags A' is the union of A with the elements of w. (II) For i = 1,..., k define a new dimer di as follows. Then the path d' is ei1 ei2 ... eik+r, written in increasing order of the corresponding tags. Roughly speaking, the new path is obtained by interlacing the new dimers with the dimers of d, following the increasing order of the tags in A'. (III) Set m(d') = (mi, m^,..., mr+k). The sequence l' is (l',..., l'r+k), where lj = lti if i is an index corresponding to a symbol in A, and l' = mj if i is an index corresponding to a symbol in w. For every permutation n G Sn, let n = wi^ ... wk be the decomposition of n into ascending runs. The pair r(n) is obtained by applying k times the procedure Q, starting from the empty triple, and using the increasing sequence wi at the i-th application of Q, 1 < i < k. It is easily seen that the procedures P and Q are inverse of each other. □ As a consequence of the preceding theorem we have that the map r is a bijection between the set of permutations of length n and the set DLn. Hence 3 Properties of the map r Given a permutation a G Sn, one can partition the set {1, 2,..., n} into intervals Ax,..., At so that a(Aj) = Aj for every i. The restrictions of a to the intervals in the finest of these decompositions are called connected components of a. A permutation a with a single connected component is called connected. The right connected components of a = axa2... an are the connected components of the reverse R(a) = anan-1... ax UD if i = 1 = k UU if i = 1 < k DU if 1 < i < k DD if 1 < i = k. Tag the dimer di with the symbol xj. Set {ei, e2,. .., efc+r} = {di,.. ., dr} U {di,. .., dk}. | VLn | = n!. M. Barnabei at al.: Ascending runs in permutations and valued Dyck paths 453 of a. A permutation is said to be right connected if R(a) is connected. As an example, the right connected components of the permutation 45132 are 45 and 132 while the permutation 2314 is right connected. The function r maps right connected permutations to irreducible Dyck paths. We recall that a return of a Dyck path d is a down step whose ending point lies on the x-axis. An irreducible Dyck path is a Dyck path whose only return is its last step. Every Dyck path d can be uniquely written as d = pip2...pfc, where each pi is an irreducible Dyck path. Proposition 3.1. Let n be a permutation in Sn and let n = m1m2 ... uk be the decomposition of n into right connected components. Let r(n) = (d, /). Then d decomposes into irreducible components dk ... d1, where di is the path corresponding to the normalization of ui. Proof. The assertion follows immediately from the definition of the map r. □ Example 3.2. Consider the same pair (d, /) G DL8 as in Example 2.5 and the corresponding permutation n = 78356214. We have that the right-connected components of n are 78 and 356214. The Dyck path corresponding to the permutation 356214 is UUUDUUDDDUDD, the Dyck path corresponding to the normalization of 78, i.e., to the permutation 12, is UUDD, and these are precisely the irreducible components of the Dyck path d. Denote by RC(n) the reverse-complement of the permutation n, namely, if n = nin ... n„, then RC(n) = (n + 1 - n„)(n +1 - n„_i)... (n +1 - ni). The following assertion relates the images of the permutations n and RC(n) under the map r. Proposition 3.3. Let n a permutation and let r(n) = (d,/). Then r(RC(n)) = (d', /') where d' is the path obtained from d by reflecting the path d along a vertical line, and /' = m„+i_i - /„+i_i, 1 < i < n. Proof. Let w1... wk be the decomposition of n G Sn into ascending runs with wi = xi,1... xi ii. For all i, set yijj = n +1 - xijli+1_j. Then the decomposition into ascending runs of RC(n) is w ... wi with Wi = yi,1... yi,li. The assertion follows now immediately from the definition of the map r. □ Example 3.4. Consider the permutation n = 78356214 of Example 2.5. Hence RC(n) = 58734612. We have r(n) = (d, /), where d = UUUDUUDDDUDDUUDD and / = (0,0,0,1,0,0,0,0). The height list of d is m(d) = (0,1,1,1,0,0,0,0). Then r(RC(n)) = (d',/') with d' = UUDDUUDUUUDDUDDD and /' = (0,0,0,0,0,1,1,0). Now we define a map $: Sn ^ Sn. Let n G Sn and w1... wk its decomposition into ascending runs. Given two consecutive ascending runs wi and wi+1, we say that they are 454 Ars Math. Contemp. 16(2019)445-463 contigue if wi+1wi is an increasing sequence of integers or, equivalently, if the tail of wi+1 is smaller than the head of wj. Then we consider the decomposition of n = B1... Bh where the B/s are maximal sequences of contigue ascending runs. We define the image of n under the map $ as follows: $(n) = Bh ...Bi. For example, if n = 5623147, then B1 = 5623, B2 = 147 and $(n) = 1475623. Note that $ is an involution, namely, $2 is the identity over Sn. Theorem 3.5. Let n G Sn. Then r(n) = (d,/) ifandonlyif r($(n)) = (d, m(d) - /). Proof. Let r(n) = (d,/) and r($(n)) = (d',/'). Since permutation $(n) has the same heads and tails as n, d = d'. Moreover the definition of the map $ implies immediately that /' = m(d) - /. □ It follows from Proposition 3.3 and Theorem 3.5 that $ o RC = RC o$. 4 Pattern avoiding permutations Let n G Sn and t g Sm. We say that n = n1... nn contains the pattern t = t1 ... Tm if there exists an index subsequence 1 < i1 < i2 < ... < im < n such that nij < nik iff Tj < Tk for 1 < j, k < m. Otherwise, n avoids the pattern t. The set of permutations of length n that avoid the pattern t is denoted by S„(t). In this section we study the behavior of the map r when restricted to some subsets of pattern-avoiding permutations. 4.1 Permutations avoiding 132 The following proposition shows that the set Sn(132) corresponds to a particular subset of DLn. Proposition 4.1. Let n G Sn and let r(n) = (d, /). Then n G S„(132) ifandonlyif / = (0,..., 0). Proof. Set / = (/1,..., /„). We recall that /i = |{j I hj < i < tj, tj precedes i in n}|. Suppose that there exists an index i such that /i > 0. Then there are at least a head hj and a tail tj with hj < i < tj such that tj precedes i in n. As a consequence, hj tj i is an occurrence of 132 in n. This suffices to conclude the proof, since both the cardinalities of Sn(132) and Dn are given by the n-th Catalan number (see [21] and [23], respectively). □ Many bijections between 132-avoiding permutations and Dyck paths are present in the literature (see [12, Chapter 4] for an exhaustive description). The preceding proposition implies that the map r, when restricted to the set Sn(132), provides yet another one bijection between this set and Dn, whose inverse has an easy description in terms of multitunnels. M. Barnabei at al.: Ascending runs in permutations and valued Dyck paths 455 Given a Dyck path d, a multitunnel in d is a maximal horizontal segment between two lattice points of d lying always below d (see [9]). A multitunnel can consist of a single point. For our purpose we will be interested in odd multitunnels, namely, multitunnels whose points have odd y-coordinate. For example, the three odd multitunnels of the path in Figure 8 are the dashed segments (one of them reduces to a point). Figure 8: A Dyck path with three odd multitunnels (denoted with dashed segments). Proposition 4.2. Let d be a Dyck path and n be the corresponding permutation in Sn (132), namely n = A(d, (0,..., 0)). Consider the tagged Dyck path [d, (1,..., n)]. Every ascending run of n is given by the tags of the points of d lying on the same odd multitunnel. Moreover, the sequence of the heads of n is a decreasing sequence. Proof. At the first application of the procedure P the first chosen dimer is the dimer containing the first return of d, and the removed tags correspond to the dimers at height 0 in the leftmost irreducible component of d, whose middle points are precisely the points of the leftmost and lowest odd multitunnel. The same argument can be used for the following steps. □ Example 4.3. Consider the Dyck path d in Figure 9. The three multitunnels of d contain the points whose tags are {1,4, 6}, {2,3}, {5}, and the corresponding permutation in S6(132) is 523146. We recall that a descent of a permutation n is an index i, 1 < i < n - 1, such that n > ni+1. If n = wi... wk is the decomposition of n into ascending runs, a descent of n occurs at the end of each ascending run, except the last one: Hence, the descents of n are given by the positions of the first k - 1 tails. Since it is well known (see e.g. [4]) that the number of permutations in Sn(132) with h descents is the Narayana number 2 3 4 5 6 Figure 9: A Dyck path with three multitunnels. 456 Ars Math. Contemp. 16 (2019) 445-463 we get that the Dyck paths of semilength n with h odd multitunnels are counted by the Narayana number N(n, h). 4.2 Non-crossing partitions The set of 132-avoiding permutations of length n corresponds bijectively to the set of non-crossing partitions of {1, 2,..., n}. Such partitions were introduced by Kreweras in [15] and extensively studied by many authors in recent years (see [1, 17, 19, 22], to name but a few). A partition of the set {1, 2,..., n} is said to be non-crossing if, whenever four elements a,b,c,d G {1,..., n} with a < b < c < d are such that a, c are in the same block and b, d are in the same block, then the two blocks coincide. We denote by NC(n) the set of non-crossing partitions of {1,..., n}. As usual (see e.g. [19]) we represent non-crossing partitions graphically by plotting n points on the real line labelled with 1, 2,..., n and joining points corresponding to successive elements of the same block by arcs. Since we consider a non-crossing partition, the arcs of this diagram do not intersect in points different from 1,2,... ,n. For example, the non-crossing partition whose blocks are {1,5}, {2, 3}, {4}, {6,7,8} is graphically represented in Figure 10. Figure 10: The non-crossing partition with blocks {1,5}, {2, 3}, {4}, {6,7,8}. Many bijections between Sn(132) and NC(n) are available in the literature (see e.g. [19, 24]). The following proposition provides another bijection between these two sets. Proposition 4.4. The permutation n G Sn avoids 132 if and only if (a) the heads of n are in decreasing order and (b) the partition of n given by the ascending runs of n is a non-crossing partition. Proof. Proposition 4.2 implies immediately that if the permutation n avoids 132 conditions (a) and (b) are fulfilled. Conversely, let n be a permutation containing an occurrence of 132. Let nk be this occurrence. Without loss of generality, suppose that n is the head of an ascending run. If nj is in the same ascending run, nk is surely in a different ascending run whose head we denote by h. If h > n.j, condition (a) is not satisfied. If h is smaller than n, the quadruple h, nj, nk, nj does not satisfy condition (b). If nj and nk are in different ascending runs, denote by h the head of the ascending run containing nk. If h > n.j, condition (a) is not satisfied. If h < nj, the triple h, nj, nk is an occurrence of 132 with h and nj in the same ascending run. This completes the proof. □ The result of the previous proposition induces a bijection between non-crossing partitions and Dyck paths. The same bijection can be found in [24, Proposition 2.1]. M. Barnabei at al.: Ascending runs in permutations and valued Dyck paths 457 4.3 Permutations avoiding 213 We now turn our attention to the pattern 213. We recall that, since RC(132) = 213, we have n G Sn(132) whenever RC(n) G Sn(213). Hence, Proposition 3.3 implies immediately the following results: Proposition 4.5. Let n G Sn and let r(n) = (d, l). Then n G Sn(213) if and only if l = m(d). Proposition 4.6. Let d be a Dyck path and n be the corresponding permutation in Sn (213), namely, n = A(d, m(d)). Consider the tagged Dyck path [d, (1,..., n)]. Every ascending run of n is given by the tags of the points of d which lie on the same odd multitunnel. The sequence of the tails of n is a decreasing sequence. The preceding results imply that the map when restricted to Sn(132), becomes a bijection onto Sn(213) that can be described as follows. Proposition 4.7. Consider a permutation n G Sn(132) whose decomposition into ascending runs is n = w\... wk. The corresponding permutation $(n) in Sn(213) is the permutation with the same ascending runs rearranged so that the tails are in decreasing order For example, if n = 56 23147 then $(n) = 147 56 23. To the best of our knowledge, this map is new. Let n G Sn. A left-to-right (LR) minimum of n is an element n of n such that n < nj for all j < i. Similarly, a right-to-left (RL) maximum is an element n such that nj < n for all j > i. The next proposition describes the behavior of the map $ with respect to the statistics "number of LR minima", "number of RL maxima", and "number of descents". Proposition 4.8. Let n be a permutation in Sn(132). Then the permutations n and $(n) have the same number of descents. Moreover, the number of LR minima of n equals the number ofRL maxima of $(n). Proof. Since n G Sn(132), the heads of its ascending runs are in decreasing order, hence they are precisely the LR minima of n. Similarly, the tails of $(n) are its RL maxima. Finally, we recall that a permutation with k ascending runs has k — 1 descents. The proof now follows immediately by Proposition 4.7. □ 5 Polynomials associated with permutations and their Hankel transform Now we associate with a permutation n G Sn the monomial 6(n) = H\sIHTnlBIBn' (tails are not considered because they are always in bijection with heads). Note that if Y (n) = Y (a ), namely, n and a correspond to the same Dyck path, then 6(n) = 0(a). Set Fn(H, S, B) = £ 0(n)= £ ah,s,b,nHhSsBb, nES„ h,s,b>0 where ah,Sjb,n is the number of permutations of Sn with h proper heads, s head-tails, and b boarders. Note that ahs^n = 0 when 2h + s + b = n. 458 Ars Math. Contemp. 16(2019)445-463 We want to study the generating function F (H, S, B, X ) — ^ F„Xn = ^ ah,sA„F hS sBb Xn. %>0 h,s,b,n> 0 We recall that every permutation in Sn can be obtained from a permutation in Sn-1 by adding the symbol n in any position. Table 1 shows how each insertion of the element n between the entries a and b into a permutation n G Sn-1 modifies the number of proper heads, proper tails, head-tails and boarders (in this table, e denotes the empty word). Table 1: The insertion of n between two symbols a and b of a G S n— 1. a b becomes a n b h t h t ht h b h t h ht h h t h ht ht h t ht b b b t h b t b t ht t h b t h t ht b t ht e h e ht h e ht e ht ht t e b t e ht e h t e We have the following mutually exclusive options: (i) n is placed immediately after a tail. In this case, the number of boarders increases by one. (ii) n is placed immediately before a tail. In this case, the number of head-tail increases by one. (iii) n is placed immediately before a boarder. In this case, the number of boarders decreases by one while the number of heads and tails increases by one. (iv) n is placed immediately after a head-tail. In this case, the number of head-tails decreases by one while the number of heads and tails increases by one. (v) n is placed at the first position. In this case, the number of head-tail increases by one. As a consequence we have ah,s,b,n — hah,s,b—1,n—1 + h ah,s — 1,b,n— 1 + bah—1,s,b+1,n—1 + s ah—1,s + 1,b,n —1 + ah,s —1,b,n—1, with the obvious boundary conditions. This recurrence relation shows that the polynomials Fn(H, S, B) satisfy (5.1) Fn (HB + HS) ^ + H^^1 + dFn—1 )+ S • Fn—1 dH dB dS Vn > 1, M. Barnabei at al.: Ascending runs in permutations and valued Dyck paths 459 with F0 = 1 . As a consequence we get the following functional equation for the generating function F (H, S, B, X): F = 1 + X 0 is given by Hm(m+1)/2 • ^(il)2 i=0 'm> 0 Proof. To prove the result we use the Gessel-Viennot lemma (see e.g. [2, p. 217]). Consider in the lattice plane the two sets of points {A0, A1,..., Am} and {B0, B1,..., Bm} with A = (—2i, 0) and Bj = (2j, 0). For every permutation p of the set {0,1,..., m} consider a set p0, p1,..., pm of m + 1 valued Dyck paths such that p» starts at A and ends at Bp(i). Each valued Dyck path with initial point A and ending point Bj corresponds to a permutation in Si+j, by the results of Section 2. As we noticed above, for any Dyck path d, all the permutations a such that 7(a) = d share the same monomial 0(a). For this reason, this monomial will be denoted by 0(d). Associate with the (m + 1)-tuple p0,p1,... ,pm, where p» = (dj, 1(j)), the monomial n™0 0(dj). This monomial will be called the weight of the (m + 1)-tuple. Consider the set of points = (0,2k), with 0 < k < m. Notice that every path do, d1,..., dm contains exactly a point . There are only two possibilities: (i) there are at least two paths among d0,..., dm that intersect in one of the points Ck, 0 < k < m - 1; (ii) p is the identity permutation and d = U2iD2i, i configuration the trivial (m + 1)-tuple. 0,..., m. We will call this bn = det Hn a n 460 Ars Math. Contemp. 16(2019)445-463 We define a weight-preserving involution over the set of non trivial (m + 1)-tuples of valued Dyck paths. This involution changes the sign of the corresponding permutation of {0,1,..., m}. Given a (m + 1)-tuplepo,p1,... ,pm, withpi = (dj, l(i)), find the greatest value of k such that there exist at least two paths intersecting at Ck, 0 < k < m - 1. Take the two paths di and dj that intersect in Ck with minimal indices. Then associate with the (m + 1)-tuple p0,p1,... ,pm anew (m + 1)-tuple q0, q1,...,qm as follows: © if s = i, j, qs = ps; (ii) qi goes from Ai to Ck along pi and along pj from Ck to Bpj). Similarly, qj goes from Aj to Ck along pj and along pi from Ck to Bp(i). The tags of the new paths are defined accordingly. By the construction of the map r and its inverse A, we have that £ 0(d) = Fn(H,S,B), (d,l)eVLn hence, the polynomial associated to the valued Dyck paths from Ai to Bj is precisely Fi+j. As a consequence, by the Gessel-Viennot lemma, the determinant of the m-th Hankel matrix of the sequence (Fn(H, S, B))n>0 is equal to the product of the monomials corresponding to non-intersecting valued Dyck paths, precisely, valued Dyck paths starting at Ai and ending at Bi, of the form U2iD2i, for all 0 < i < m. Note that there are ((i)!)2 such valued Dyck paths, each of which has monomial Hi. This completes the proof. □ Here we mention some specializations of the polynomials Fn. The preceding theorem allows us to compute the Hankel transform of all the following sequences, specializing the variable H accordingly. The first one of these Hankel transforms was previously obtained (see [6]). The other three are new, to the best of our knowledge. 1. Recalling that 2h + b + s = n, am,n • ^ ^ ah,s,n-2h-s,n h+s=m h,s>0 s+2h0 is given by { h m(m+1)/2\ V / m>0 Proof. The proof is similar to the previous one, keeping in mind that permutations avoiding the pattern 132 correspond bijectively to valued Dyck paths where the sequence l is identically zero. □ Also in this case suitable specializations yield well-known results. 1. Specializing B = 1 and H = S = t the polynomials Fn turns out to be the Narayana polynomials (see e.g. [16]). 2. If B = t and H = S =1, Fn(t) is the generating function of the set of n-permutations that avoid the pattern 132 where the variable t takes into account the occurrences of the consecutive pattern 123. An explicit formula for the generating function J2n>0 can be found in [5]. In particular, when t = 0, Fn is the n-th Motzkin number. Theorem 5.2 implies that this sequence is among the many sequences whose Hankel transform is the constant sequence (1)n>0. 3. When H = B = 2, S =1, (Fn) is the sequence of super-Catalan numbers or little Schroeder numbers (sequence A001003 in [20]). These numbers are known to count Motzkin paths of length n - 1 where every up step has two colors and every horizontal step has three colors. It is easy to find a bijection between this set and the set of Dyck path of semilength n where the diods UU and DU have two colors. 4. If H = t and B = S =1, where t is a positive integer, Fn turns out to be the number of lattice paths from (0,0) to (2n, 0) composed by steps of the form U = (1,1), D = (1, -1) and L = (3,1), where the L steps have t -1 colors. In fact it is possible 462 Ars Math. Contemp. 16(2019)445-463 to find a bijection between this last set and the set of Dyck paths of semilength n where diods UU have t colors. To define such a bijection consider a Dyck path of semilength n where each diod UU has t colors. Replace each diod UU labelled with the color k, 1 < k < t - 1 with an L step with the same color and replace the corresponding diod DD with a step D. If a diod UU is labelled with the color t, leave it and the corresponding DD unchanged. Leave also the diods UD and DU unchanged. This is the required bijection. Note that this last case reduces to sequence A052709 in [20] when t = 2 and to sequence A129147 when t = 3. Theorem 5.2, applied to the particular cases above, shows that the Hankel transform of all the previous sequences is given by specializing H accordingly. References [1] M. Aigner, Catalan and other numbers: a recurrent theme, in: H. Crapo andD. Senato (eds.), Algebraic Combinatorics and Computer Science: A tribute to Gian-Carlo Rota, Springer-Verlag Italia, Milan, pp. 347-390, 2001, doi:10.1007/978-88-470-2107-5_15. [2] M. Aigner, A Course in Enumeration, volume 238 of Graduate Texts in Mathematics, Springer, Berlin, 2007, doi:10.1007/978-3-540-39035-0. [3] J.-C. Aval, A. Boussicault and S. Dasse-Hartaut, Dyck tableaux, Theoret. Comput. Sci. 502 (2013), 195-209, doi:10.1016/j.tcs.2011.11.038. [4] M. Barnabei, F. Bonetti and M. Silimbani, The descent statistic on 123-avoiding permutations, Sém. Lothar. Combin. 63 (2010), Article B63a (8 pages), https://www.mat.univie. ac.at/-slc/wpapers/s6 3barnbosi.html. [5] M. Barnabei, F. Bonetti and M. Silimbani, The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2, European J. Combin. 31 (2010), 1360-1371, doi: 10.1016/j.ejc.2009.11.011. [6] P. Barry, Eulerian polynomials as moments, via exponential Riordan arrays, J. Integer Seq. 14 (2011), Article 11.9.5 (14 pages), https://cs.uwaterloo.ca/journals/JIS/ VOL14/Barry7/barry172.html. [7] M. Bona, Combinatorics of Permutations, Discrete Mathematics and Its Applications, Chapman & Hall/CRC, Boca Raton, Florida, 2004, doi:10.1201/9780203494370, with a foreword by Richard Stanley. [8] R. Cori, Indecomposable permutations, hypermaps and labeled Dyck paths, J. Comb. Theory Ser.A 116 (2009), 1326-1343, doi:10.1016/j.jcta.2009.02.008. [9] S. Elizalde and E. Deutsch, A simple and unusual bijection for Dyck paths and its consequences, Ann. Comb. 7 (2003), 281-297, doi:10.1007/s00026-003-0186-y. [10] S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125, doi:10.1016/s0196-8858(02)00527-4. [11] J. Francon and G. Viennot, Permutations selon leurs pics, creux, doubles montees et double descentes, nombres d'Euler et nombres de Genocchi, Discrete Math. 28 (1979), 21-35, doi: 10.1016/0012-365x(79)90182-1. M. Barnabei at al.: Ascending runs in permutations and valued Dyck paths 463 [12] S. Kitaev, Patterns in Permutations and Words, Monographs in Theoretical Computer Science, Springer, Heidelberg, 2011, doi:10.1007/978-3-642-17333-2, with a foreword by Jeffrey B. Remmel. [13] C. Krattenthaler, Advanced determinant calculus, Sem. Lothar. Combin. 42 (1999), Article B42q (67 pages), https://www.mat.univie.ac.at/ ~slc/wpapers/s42kratt. html. [14] C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005), 68-166, doi:10.1016/j.laa.2005.06.042. [15] G. Kreweras, Sur les partitions non croisees d'un cycle, Discrete Math. 1 (1972), 333-350, doi:10.1016/0012-365x(72)90041-6. [16] M. D. Petkovic, P. Barry and P. Rajkovic, Closed-form expression for Hankel determinants of the Narayana polynomials, Czechoslovak Math. J. 62 (2012), 39-57, doi:10.1007/ s10587-012-0015-8. [17] H. Prodinger, A correspondence between ordered trees and noncrossing partitions, Discrete Math. 46 (1983), 205-206, doi:10.1016/0012-365x(83)90255-8. [18] A. Randrianarivony, Correspondances entre les differents types de bijections entre le groupe symetrique et les chemins de Motzkin values, Sem. Lothar. Combin. 35 (1995), Article B35h (12 pages), https://www.mat.univie.ac.at/~slc/wpapers/ s35arthur.html. [19] R. Simion, Combinatorial statistics on non-crossing partitions, J. Comb. Theory Ser. A 66 (1994), 270-301, doi:10.1016/0097-3165(94)90066-3. [20] N. J. A. Sloane (ed.), The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org. [21] R. P. Stanley, Enumerative Combinatorics, Volume I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, California, 1986, doi:10.1007/978-1-4615-9763-6. [22] R. P. Stanley, Parking functions and noncrossing partitions, Electron. J. Combin. 4 (1997), #R20 (14 pages), https://www.combinatorics.org/ojs/index.php/eljc/ article/view/v4i2r2 0. [23] R. P. Stanley, Enumerative Combinatorics, Volume 2, volume 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1999, doi:10.1017/ cbo9780511609589. [24] C. Stump, More bijective Catalan combinatorics on permutations and on signed permutations, J. Comb. 4 (2013), 419-447, doi:10.4310/joc.2013.v4.n4.a3.