Permutation statistics for a percolation model on Z2 with imposed symmetries Henri Derycke Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France henri.derycke@labri.fr Abstract Let C = (ci,j )(i,j)∈Z2 where ci,j are independently distributed Bernoulli variables with parameter (1 − q). We study the law of the semiperime- ter of the smallest rectangle for which all neighbours have value 0 and that contains the origin. Assuming symmetries on the distribution (for instance ci,j = cj,i ) leads to a hierarchy of systems of equations de- scribing the probability that the semiperimeter of this rectangle is n. We propose a probabilistic algorithm common to all symmetries, lead- ing to these equations. This algorithm is related to a local bootstrap percolation model presented by Gravner and Holroyd. For cases with most symmetries, this probability is also described by statistics such as the number of inversions on (partial) permutations. As a byproduct, we propose a positivity result concerning a polynomial involving inv and maj statistics on some linear extensions of some partial orders and a symmetric statistic on partial permutation inherited from a simple symmetry on the algorithm. 1 Introduction 2 Let C = (ci,j )(i,j)∈Z2 ∈ {0, 1}Z be a configuration of the square lattice Z2 . A rectangle is a interval product Ji, jK × Jk, lK. A segment is a rectangle with at least one dimension equal to 1. Each vertex (x, y) ∈ Z2 has four neighbours {(x ± 1, y), (x, y ± 1)}. The neighbourhood of a rectangle is the set of the neighbours of the rectangle’s vertices that are outside the rectangle. Then this neighbourhood, called border, is an union of 4 segments. A rectangle is stable in C if it contains the origin and all vertices of its border have value 0. For instance, the blue rectangle of fig. 1 is a stable rectangle of the underlying configuration and the gray vertices are its neighbourhood. Given a configuration C, we have a deterministic algorithm to find this rectangle that terminates if and only if such rectangle exists. Assuming C is a random variable given by independent Bernoulli random variables ci,j of parameter 1 − q ∈ [0, 1]. Then the probability that the rectangle associated to C has semiperimeter n is also the probability that the algorithm terminates on a rectangle of semiperimeter n. The study of the algorithm induces a system of linear q-difference equations that describes the probability (similar to those in section 3). We can evaluate the power series of probability by iteration of this system but we do not have any direct formula for each probability. Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at http://ceur-ws.org 140 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 1 Figure 2: Example certificate with all the square Figure 1: Smallest stable rectangle J−3, 2K×J−1, 2K symmetries with corresponding permutation with the origin in black (1, 6, 5, 9, 2, 11, 8, 4, 3, 7, 10) This problem comes from a study on the sandpile model [Dha95] in the square lattice. A stable rectangle is related to the bounding box of the stabilization when 4 grains are placed to the origin in a random configuration where each vertex independently has 2 grains with probability q and 3 grains otherwise. Hough, Jerison and Levine [HJL17] list known results in a slightly different setting. This problem can also be seen as a percolation model presented by Gravner and Holroyd [GH08] as the local Froböse model. The related non-zero probability of undefined stable rectangle is bounded by the [GH08][Theorem 1]. We consider here simplified models imposing some square’s symmetries on the sampling of values. More explicitly, in these models, we restrict the original distribution of values toward i.i.d. Bernoulli only on a part of Z2 and repeat these values according to the symmetries on the remaining part. For example with all the square symmetries (fig. 3), for 0 ≤ j ≤ i the ci,j are independent Bernoulli with parameter 1 − q and c±j,±i = c±i,±j (= ci,j ) (illustrated by the black boxes on the figure). Our main results are that the exact probabilities in several of these models are also described by classical statistics on some (partial) permutations. A statistic on the permutations is an integer given to every permutation. A first classical statistic on the permutation σ is the statistic counting the number of inversions, denoted inv σ P= |{(i, j) | i < j, σ(i) > σ(j)}|. We define desc σ = {i | σ(i) > σ(i + 1)} the set of descents of σ and maj σ = i∈desc σ i the major index of σ. MacMahon [Mac15] P the statistics inv and maj are equally distributed on the set Sn of permutations showed that of size n, ie σ∈Sn q inv σ = σ∈Sn q maj σ . P The main results are the following theorems (if needed, see section 2 for details on examples of symmetries). Proposition 1.1. When having the symmetries of axes x = y and y = 0 (fig. 3). The probability that the smallest stable rectangle has semi-perimeter 4n + 2 is X q n+1 (1 − q)n q inv σ . σ∈Sn Proposition 1.2. The symmetries x = y and x = −y (fig. 5), and the rotational symmetry by an angle of π/2 (fig. 4) reveal fixed point free involution. The probability that the smallest stable rectangle has semi-perimeter 4n + 2 is X inv σ−n q 2n+1 (1 − q)n q 2 σ∈I2n where I2n is the set of fixed point free involutions of S2n . 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 Figure 3: Sampling for all symme- Figure 4: Sampling for rotation π/2 Figure 5: Sampling for symmetries tries x = y and x = −y 141 The symmetry x = −y (fig. 6) leads to a close result to the case of the axes x = y and y = 0 (Proposition 1.1). It involves all the permutations with a multiplicity which is the number of decreasing subsequences in each permutation. Each subsequence can be seen as a marking on the permutation. Theorem 1.1. With symmetry x = −y (fig. 6), the probability that the smallest stable rectangle has semi- perimeter 2n + 2 is X q 2n+2 (1 − q)n mult(σ)q inv σ σ∈Sn where mult(σ) is the number of decreasing subsequences in σ including the empty subsequence. 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 Figure 6: Sampling for symmetry x = −y Figure 7: Sampling for symmetry y = 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 Figure 8: Sampling for symmetries x = 0 and Figure 9: Sampling for rotation π y=0 Roughly speaking, these results can be obtain by identify the expected permutations with runs of the algorithm computing the stable rectangle. We only present the algorithm in a specialization for the axial symmetry in the line x + y = 0 (see section 3.1). With the axes x = 0 and y = 0 (fig. 8), we similarly identify permutations of size n sorted in 2n−1 − 1 stepŝ by Homing sort from Elizalde and Winkler [EW09] but unlike the previous results, we didn’t find any statistic counted by q to get an expression of the probability of semi-perimeter 2n + 2. The rotational symmetry by π (fig. 9) gives close results to the precedent case in terms of equation. The relation between those two is the same as the relation between the case with all symmetries and the case with the rotational symmetry by π/2 (Propositions 1.1 and 1.2). But the rotational symmetry by π does not lead us to relation with permutations. We have no result about the remaining axial symmetry in the line y = 0 (fig. 7). This enumerative study also has two byproducts on the study of permutations. First, the Theorem 1.1 may be refined to take into account the relative position of the origin inside the stable rectangle via its distances to the top and right sides. Our proof translates these two distances into statistics on related permutations with a marked decreasing subsequence: stat1 := |{i | ∃j ≤ i, σ(j) is marked , σ(j) ≤ σ(i)}| and stat2 := |{i | ∀j ≤ i, σ(j) is marked , σ(j) > σ(i)}|. A compatibility not detailed here of our algorithm with the symmetry of axis x = −y (see section 3.4), implies an involution on those permutations which exchange the two statistics while preserving the number of inversions. Then still following Theorem 1.1, more work was given to the expression of the probability. We are interested in σ∈Snd q inv (σ) where d is a subsequence of (n, n − 1, . . . 2, 1) and Snd the set of permutations of Sn that contain P the subsequence d. This kind of sum can be found in Björner and Wachs [?] with either the number of inversions or the major index statistic. The section 4 presents the following result. Theorem 1.2. Let n ∈ N, d is a subsequence of (n, n − 1, . . . 2, 1) and D ⊂ {1, 2, . . . n − 1}, then the following sum is a polynomial with positive integer coefficients, where Snd,D is the set of permutations of Snd whose descent set of the inverse desc (σ −1 ) is D. X q maj σ − q inv σ d,D 1−q σ∈Sn 142 In section 2 we sketch the proofs of Propositions 1.1 and 1.2. In section 3 we present the proof of Theorem 1.1 based on a parallel between runs of an algorithm and insertion rules on relevant permutations. 2 Permutation statistics We let R(C) be the smallest stable rectangle with respect to C and |R(C)| its semiperimeter. Then the probability that the semiperimeter of the smallest stable rectangle of C is n ≥ 2 is P[|R(C)| = n]. 2.1 Square symmetries When assuming all symmetries of the square, the smallest stable rectangle is a square with centre the origin. The problem is reduced to the first octant. Then P[|R(C)| = 4n + 2] is the probability that there is at least one 1 in each one of the n first segments and Pn Pn i that the n + 1 segment contains only 0’s. Thus P[|R(C)| = 4n + 2] = q n+1 i=1 (1 − q i ). The sum i=1 (1−q 1−q ) is well known to be σ∈Sn q inv σ . P We denote by certificate the set of position of the first 1’s in each segment, from the bottom. This certificate can be interpreted as an inversion table of a permutation on n elements. The figure 2 illustrates an example certificate. The certificate is the sequence of vertices of ordinates ci where c = (0, 0, 0, 1, 3, 4, 0, 3, 5, 0, 5). The probability to Q11 Q11 obtain it is q 12 i=1 (1 − q)q ci = q 12 (1 − q)11 i=1 q ci . The vector c is also the inversion table of the permutation σ = (1, 6, 5, 9, 2, 11, 8, 4, 3, 7, 10). Thus the probability to observe this certificate c is q 12 (1 − q)11 q inv σ . In the general case we have the Proposition 1.1. 2.2 Axial symmetries in the lines x = y and x = −y As the previous case, the smallest stable rectangle is square with centre the origin. Here, the problem is reduced to the sector {(x, y) | 0 ≤ |y| ≤ x} (fig. 5). P n We have that P[|R(C)| = 4n + 2] = q 2n+1 i=1 (1 − q 2i−1 ). We can define the certificate the same way. Then there are (2n − 1)!! different certificates. A subset of permutations of size (2n − 1)!! is the set of fixed point free permutations on {1 . . . 2n}. In the same way as before, we showed a bijection between certificates and fixed point free involutions with an insertion rule. This leads to the Proposition 1.2. 3 Axial symmetry in the line x + y = 0 In this case, we only consider the upper half-plane delimited by x = −y (fig. 6). We prove the following theorem. X Theorem 1.1. P[|R(C)| = 2n + 2] = q 2n+2 (1 − q)n mult(σ)q inv σ where mult(σ) is the number of decreasing σ∈Sn subsequences in σ including the empty subsequence. First, we demonstrate that the probability P[|R(C)| = 2n + 2] follows a linear recurrence from a system of q-linear equations. Then we remark that this recurrence corresponds to a q − analogue of the recurrence satisfied by the number of partial permutations. Finally we show that this q − analogue counts the number of inversions of the permutations involving in the theorem. 3.1 Algorithm In the previous cases, it is enough to read C on the right border. We read the grid from the origin to the right, expanding a rectangle until the right border contains only 0’s. In the case of axial symmetry in the line x+y = 0, we have to read two border. In order to compute the size of a rectangle R(C), we define the deterministic algorithm 1 running on the grid. The algorithm reads the right border and the top border. Starting from the rectangle [0, 0]2 , at each step, if a 1 is found in the right border or the top border, we know that this border is in R(C) so we expand the rectangle by merging the border to it. The fig. 10 shows an example of configuration with the segments (red boxes) and the associated certificate (in blue) given by the algorithm. The algorithm consists on 3 states describing the knowledge of the border of the expanding rectangle. In State A, we did not read the border. In State B, we read the right border and it contains only 0’s. In State C, we read the right border and the top border and they contains only 0’s. 143 Algorithm 1 Axis symmetry x = −y 1: procedure SmallestStableRectangle(C) 2: Let certif icate the certificate 3: i, j ← 0 the size of the current rectangle 4: State A: 5: if the right border {i + 1} × J−i, jK contains a 1 then 6: y ← min{y ∈ J−i, jK | Ci+1,y = 1} 7: Add (i + 1, y) to certif icate 8: i←i+1 9: goto State A 10: State B : 11: if the top border J−j, iK × {j + 1} contains a 1 then 12: x ← min{x ∈ J−j, iK | Cx,j+1 = 1} 13: Add (x, j + 1) to certif icate 14: j ←j+1 15: if Ci+1,j = 1 then 16: Add (i + 1, y) to certif icate 17: i←i+1 18: goto State A 19: goto State B 20: State C : 21: return certif icate From State A, either the right border contains only 0’s and we go to State B, or we read a 1 in the right border so we go back to State A. From State B, either the top border contains only 0’s and we go to State C, or we read a 1 in the top border. Then since we expand the rectangle toward the top, the whole right border except its top vertex has been read. Either this vertex has value 0, then and we go to State B, or we read a 1 in the top-right corner and we go to State A. The State C is the final state since we found a stable rectangle. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 H5 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 H4 0 1 0 1 1 1 1 0 1 1 0 0 0 0 0 H3 1 1 0 0 0 0 0 0 0 1 0 0 0 H2 0 0 1 0 0 0 1 0 0 0 0 H1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 V1 0 0 0 V2 0 V3 Figure 10: Segment partitioning from algorithm 1 Figure 11: Symmetry on the reads 3.2 System of q-linear equations We refine the states Ai,j , Bi,j and Ci,j from the algorithm with the size of the expanding rectangle J−j, −iK×Ji, jK. Then the probability to enter a state from another is straightforward. From state Ai,j , we enter state Ai+1,j with probability (1 − q i+j+1 ), and state Bi,j with probability q i+j+1 otherwise. From state Bi,j , we enter state Bi,j+1 with probability q(1 − q i+j+1 ), state Ai+1,j+1 with probability (1 − q)(1 − q i+j+1 ), and state Ci,j with probability q i+j+1 otherwise. Hence we deduce this equations: Ai,j = (1 − q i+j )Ai,j−1 + (1 − q i+j−1 )(1 − q)Bi−1,j−1 Bi,j = q(1 − q i+j )Bi−1,j + q i+j+1 Ai,j and Ci,j = q i+j+1 Bi,j where Ai,j and Bi,j are 0 if i or j are negative and A0,0 = 1 and B0,0 = q. With two substitutions, we get a relation on Ci,j Ci,j = q 2 (Ci−1,j + Ci,j−1 )(1 − q i+j ) − q 4 Ci−1,j−1 (1 − q i+j−1 )2 144 This probability corresponds to the probability that the percolation algorithm terminates on the square of side i + j + 1 withPthe right border at distance j of the origin. n Let Cn = i=0 Ci,n−i = P[|R(C)| = 2n + 2] the probability to terminate in a square of semi-perimeter 2n + 2. Then Cn = 2q 2 (1 − q n )Cn−1 − q 2 (q(1 − q n−1 ))2 Cn−2 where C0 = q 2 and C1 = 2q 4 (1 − q). The polynomial Cn can be factored by (1 − q)n : Cn = q 2n+2 (1 − q)n Pn where Pn satisfies 2 1 − qn 1 − q n−1  Pn = 2 Pn−1 − Pn−2 (1) 1−q 1−q 3.3 Partial permutations and insertion rules The recurrence (1) is a q − analogue of the recurrence satisfied by the number of partial permutations of {1 . . . n} shown by Borwein, Rankin and Renner [BRR89], since its limit for q → 1 is: |Rn | = 2n|Rn−1 | − (n − 1)2 |Rn−2 | (2) where we denote by Rn the set of partial permutations of {1 . . . n}. A partial permutation is an injective partial self-maps on a set of n elements. In order to count the number of inversions to refine the recurrence (2), we map bijectively each partial permutation to a permutation with a decreasing subsequence marked constructed by completing the holes in the partial permutation by the missing elements marked in decreasing order. Then we denote by the number of inversions of a partial permutation the number of inversions of the corresponding permutation with a decreasing subsequence marked. For instance, the partial permutation σ =?26?1? where question marks denote undefined values maps to σ = 526413 since the missing values are {3, 4, 5}. We will note σ = 526413. The number of inversions of σ is 10. Now, we refine the proof of [BRR89] following the number of inversions. The sketch of the proof is to build Rn from Rn−1 by using three insertion rules and to count the number of inversions that are created by each rule. We denote by Tn the set of partial permutations that are not defined P in 1. We denote by rn and tn the q −analogues of |Rn | and |Tn | defined by: rn = σ∈Rn q inv (σ) and tn = σ∈Tn q inv (σ) . For instance, r2 = 3+4q P and t2 = 1 + 2q. We first get the following lemma. n+1 n Lemma 3.1. Let n ≥ 0, then rn+1 = 1−q n 1−q 1−q rn + q rn + 1−q tn . Proof. Let σ ∈ Rn seen as a marked permutation. The insertion rules defined on permutations with a decreasing subsequence marked will be denoted by π1 , π2 and π3 , and defined as follow (with σ some partial permutation): π1 Let k ∈ {1 . . . n + 1}, we shift the value of σ that are greater or equal to k and we insert k at the first position. Example: σ = 526413, the rule π1 with k = 2 leads to 2637514 π2 We insert a marked n + 1 at the first position. Example: f = 526413, the rule π2 leads to 6526413 π3 Let k ∈ {2 . . . n + 1}, if σ1 is marked, we insert n + 1 at position k in σ. Example: f = 526413, the rule π3 with k = 4 leads to 5267413 We note that π3 is only defined on Tn . The co-domains of the rules π1 , π2 and π3 form a partition of Rn+1 . Since the rules π1 , π2 and π3 are bijective, we proved the relation |Rn+1 | = (n + 1)|Rn | + |Rn | + n|Tn |. Moreover, we can follow the number of new inversions when we insert an value in a permutation of size n. The rule π1 with parameter k adds k − 1 inversions. The rule π2 adds n inversions. The rule π3 with parameter k adds n + 1 − k inversions. Thus, we have n+1 X n+1 X rn+1 = q k−1 rn + q n rn + q n+1−k tn . k=1 k=2 Noticing that the co-domains of π2 and π3 form a partition of Tn , we also get in the same way the following lemma. 145 n Lemma 3.2. Let n ≥ 0, then tn+1 = q n rn + 1−q 1−q tn . Using the equations of the lemma 3.1 at ranks n and n − 1 and the lemma 3.2 at rank n − 1 we obtain the expected relation: 2 1 − q n+1 1 − qn  rn+1 = 2 rn − rn−1 . 1−q 1−q Thus Pn and rn satisfy the same recurrence and the same initialization. That concludes the proof of the Theorem 1.1. 3.4 Bijection with certificates We can construct a bijection from the set of certificates to the partial permutations using the rules π1 , π2 and π3 . The rule π3 corresponds to the transition Ai,j → Ai+1,j , π2 to the transitions Bi,j → Ai+1,j+1 and Ai,j → Ai+1,j and π1 corresponds to the transition Bi,j → Bi,j+1 . We note that if we take the reflection across the line x = y, the algorithm produces the same certificate up to a permutation and reads the same vertices (fig. 11). Thanks to the precedent bijection, we have an involution on the partial permutations exchanging the statistics stat1 and stat2 presented in the introduction, and preserving the number of inversions, which is also the number of read 0’s. 4 Decreasing subsequences and q-positivity We let the word sn = (n, n − 1, . . . , 1). Given two words u and v, u is a subsequence of v if u derives from v by deleting some letters, denoted by u ≺ v. We reformulate the probability given by Theorem 1.1 by interchanging the summations: X X X X P[|R(C)| = 2n + 2] = q 2n+2 (1 − q)n q inv σ = q 2n+2 (1 − q)n q inv σ . σ∈Sn d≺sn d≺sn σ∈Sn d≺σ d≺σ We let Snd the set of permutations σ in Sn such that d ≺ σ. For some d, the sum σ∈S d q inv σ factorizes P n according to a more general study of linear extensions of partial orders [?]. The number of inversions of permutations was extended by Björner and Wachs towards labelled forests. The [n] ! [?, Theorem 1.1] gives a simple relation if d has no hole, d = [min d, max d], σ∈Snd q inv σ = q |d|(|d|−1)/2 [|d|]qq ! . P Otherwise, there is no known formula for other d. However, the [?, Theorem 1.2] gives a similar formula if [n] ! maj σ = q |d|(|d|−1)/2 [|d|]qq ! This suggests to P the major index statistic replaces the number of inversions: σ∈Snd q consider   X X X q inv σ = q maj σ −  q maj σ − q inv σ   d σ∈Sn d σ∈Sn d σ∈Sn The second term of the right hand side is a polynomial of which 1 is a root, thus it can be factored by (1 − q). Moreover, it satisfies the following theorem. Theorem 4.1. Let n ∈ N, d ≺ sn , then the following sum is a polynomial with positive integer coefficients. X q maj σ − q inv σ d 1−q σ∈Sn In order to prove this affirmation, we use intermediate statistics on permutations. Let W = (wi,j )1≤i,j≤n be an upper triangular matrix, Kadell [Kad85] defined the weighted inversion number invW (σ) of σ with respect to (k,l) the weight matrix W by invW (σ) = 1≤i σ(j)). We define for 1 ≤ k < l ≤ n, W (k,l) = (wi,j ) P (k,l) (k,l) (k,l) (k,l) where wi,j = 1 for 1 ≤ i < j < l, wi,i+1 = i for l < i < n, wi,l = 1 for k < i < l, wk,l = k and (k,l) wi,j = 0 otherwise. The [Kad85][Corollary 2] holds so W (k,l) is equally distributed with the inversion number. Note that invW (1,n) = inv and invW (1,2) = maj . We can easily show that for any σ and any 1 < k < l ≤ n, invW (k,l) (σ) − invW (k−1,l) (σ) = (k − 1) [χ(σ(k) > σ(l)) − χ(σ(k − 1) > σ(l))]. 146 inv (σ) inv (σ) P q W (k,l) −q W (k−1,l) Lemma 4.1. Let 1 < k < l ≤ n, d σ∈Sn 1−q is a polynomial with positive integer coeffi- cients. Proof. We defined the involution σ → σ ? by σ ? = σ ◦(k −1, k) if σ(k −1) < σ(l) < σ(k) or σ(k) < σ(l) < σ(k −1) and σ ? = σ otherwise. This is an instance of [Kad85][Lemma 1], thus for any σ we have invW (k,l) (σ) = invW (k−1,l) (σ ? ). Let σ ∈ Snd such that σ(k − 1) < σ(l) < σ(k), since σ(k − 1) < σ(k), σ(k − 1) and σ(k) are not both in d. Then σ ? still contains the subsequence d and σ ? (k) < σ ? (l) < σ ? (k − 1). So, the sum is a sum on the permutations σ such that invW (k,l) (σ) < invW (k−1,l) (σ) and such that σ ? is not in Snd . Proof of the Theorem 4.1. For 1 < l < n, W (1,l) = W (l,l+1) . Then X q maj σ − q inv σ X X q invW (k,l) (σ) − q invW (k−1,l) (σ) = d 1−q 1−q σ∈Sn d 1