We give a formula to compute the number of permutations with a prescribed descent set in quadratic time. We give the generating function of the number of permutations with a periodic descent set. We introduce the density method algorithm, which generates uniformly distributed random permutations with a prescribed descent set.
Theorem 1.1 Fix an integer N 2 and a set A polynomials (fi; 1 i N ) as follows: fN = 1 1]. De ne by descending induction a sequence of fi(x) =
fi+1(y) dy 0 x QN (A) = N !
The reason why we use descending induction, rather than regular induction, will appear in Theorem 3. An easy inclusion-exclusion argument (see for instance [Bon12], Chapter 1) gives where the function gN is de ned as follows. If B = ;, then gN (B) = 1. Otherwise, there exists k 2 [1; N such that B has the form B = fi1 < i2 < : : : < ikg and in that case gN (B) =
N ! (N ik)!(ik ik 1)! : : : (i2 i1)!i1! However, in order to use (1), one needs to compute 2N jAj terms. By comparison, Theorem 1 only requires the computations of the coe cients of N polynomials of degree 0 to N 1, which means computing O(N 2) coe cients. Moreover, each coe cient can be computed using only one elementary computation, except for the constant coe cients. It is easily seen that calculating the constant coe cient of fd requires N d elementary computations. Hence the number of elementary computations in Theorem 1 is O(N 2). Another e cient method to compute QN is given by Viennot [Vie79].
Theorem 1 also gives access to comparison results. For a permutation of [1; N ], say that m 2 [2; N 1] is a local extremum if either (m 1) < (m) > (m + 1) or (m 1) > (m) < (m + 1). Then we have
B. Then F : P(f2; 3; : : : n [2; N 1], let F (B) be the number of permutations of [1; N ] with set of local extrema
1g) ! N is an increasing function.
Of course, such results are more di cult to derive using alternating sums such as (1). The fact that the maximum of F is achieved for alternating permutations was rst observed by Niven [Niv68], see also [BR70]. Our next result deals with the case of a periodic descent set.
2 be an integer, x a set A f1; 2; : : : pg and put (1)
If i 2= A, For each integer n
1, let dn be the number of permutations of f1; : : : ; ng with descent set Let !1; : : : ; !p be the p-th roots of 1 (resp. -1) if p
jAj is even (resp. odd). For k; l 2 [1; p], put A1 = 1 [ (A + np) n=0 A1 \ [1; n gk;l(t) = Then there exists a rational function RA 2 Z(X1; : : : ; Xp(p+1)), such that Theorem 2 generalizes the classical theorem by Andre [And1879] for alternating permutations: where we agree that d0 = 1. More recent results were established by Carlitz (see [Car75] for instance) and Mendes-Remmel-Riehl [MRR10] in the case = 1, and later by Luck [Luc14] and Basset [Bas16]. We shall see how to recover these results from our method in Section 3.
For the rst-order asymptotics, see [LM83] and [BHR03]. For every set A, one can compute RA and derive the asymptotics from the zeros of the denominator, using the classical tools of analytic combinatorics. See for instance the analysis of alternating permutations as Example IV.35 in [FS09]. However, our approach does not provide the general form of the denominator.
Finally, we introduce an algorithm generating uniform random permutations with a given descent set. We begin by a simple remark, which was already used in [ELR02] among others. Let Y = (Y1; : : : YN ) be a sequence of distinct reals in [0; 1]. We can construct from Y a permutation Y as follows. Let k1 2 f1; 2; : : : N g be the integer such that Yk1 is minimal in fY1; : : : YN g and put Y (k1) = 1. Then, let k2 2 f1; 2; : : : N g fk1g be the integer such that Yk2 is minimal in fY1; : : : YN g fYk1 g, put Y (k2) = 2 and so on. To recover Y from Y , one can use a sorting algorithm.
One can de ne the descent set D(Y ) of a sequence of reals Y as for a permutation and clearly, D(Y ) = D( Y ). Moreover, if Y is chosen according to the Lebesgue measure on [0; 1]N , then Y is uniformly distributed over all permutations of f1; 2; : : : N g. As a consequence, if Y is chosen uniformly at random among all sequences with descent set A, that is, if its density with respect to the Lebesgue measure on [0; 1]N is for some constant C > 0, then Y is uniformly distributed over all permutations with descent set A. Therefore, we want to nd an algorithm constructing a random sequence with descent set A.
Algorithm Using iid random variables (U1; : : : UN ), uniform on [0; 1], and the functions fi de ned in Theorem 1, construct a sequence Y = (Y1; : : : YN ) as follows:
For i 2 [1; N 1], Yi+1 is the only solution in [0; 1] of the equation
C1fD(Y )=Ag Z Y1 0 f1(y)dy = U1 Finally, recover the permutation Y from Y by sorting.
Theorem 1.3 The algorithm described above yields a random permutation of f1; 2; : : : N g, uniformly distributed over all permutations with descent set A.
To see that the algorithm is well-de ned, suppose for instance that i 2 A. Then (3) becomes Z Yi+1 0
fi+1(y) dy = Ui+1fi(Yi) Since the functions fi; fi+1 are nonnegative on the interval [0; 1], (4) clearly has a unique solution on [0; 1].
We shall not study in detail the complexity of the algorithm. Nevertheless, let us make a few comments.
First, remark that a simple rejection algorithm would have exponential complexity. Indeed, if we draw a permutation at random, the most likely pro le is the alternating case, and the probability for a random permutation of length N to be alternating is 4 (2= )N (see Example IV.35 in [FS09]). Therefore, the average number of times one has to draw a permutation before nding one with the prescribed descent set is at least c( =2)N .
Using our algorithm, we need to compute the functions fi, which can be done using O(N 2) elementary computations, as already seen. The last step, namely sorting the sequence Y to deduce Y , has an average complexity O(N log N ) if one uses randomized quicksort. What is more intricate is to evaluate the time needed to generate the variables Yi, which amounts to solving N equations of the form (4). We shall not discuss this from a theoretical point of view. However, some experimental results are given at the end of the paper. Typically, our algorithm can generate permutations of length a few thousands.
In the particular case of alternating permutations, other algorithms with a better complexity can be found in [BRS12].
We now proceed to the proof of the results. We rst prove Theorem 3 in Section 2 and deduce Theorem 1 and Corollary 1 in Section 3. In Section 4, we give an outline of the proof of Theorem 2. In the last section , we comment on the implementation in Maple of our algorithm. 2
First, observe that there are obvious symmetries in the problem. If one replaces (i) with N + 1 (i) for each i, then A is replaced with its complement. If (i) is replaced with (N + 1 i) for each i, then A is replaced with N A.
Let us prove Theorem 1.3. One can re-formulate the algorithm, using the notion of conditional density of a random variable, as follows:
Y1 has density f1= R01 f1(y) dy.
If i 2 A, conditionally on Yi, Yi+1 has density 1[0;Yi]fi+1=fi(Yi).
If i 2= A, conditionally on Yi, Yi+1 has density 1[Yi;1]fi+1=fi(Yi).
As a consequence, the density of the sequence Y = (Y1; : : : ; YN ) with respect to the Lebesgue measure on [0; 1]N is equal to the telescopic product
f1(Y1) R01 f1(y) dy f2(Y2) f1(Y1) : : :
fN (YN ) fN 1(YN 1) 1fD(Y )=Ag =
1
R01 f1(y) dy 1fD(Y )=Ag which is exactly the form required in (2). Therefore, Y is uniformly distributed over all permutations with descent set A. This proves Theorem 3. 3
Let us deduce Theorem 1. If a permutation of f1; : : : ng is drawn uniformly at random, the probability that its descent set is A is
dyN 1fD(Y )=Ag
dy1 : : :
dyN 1fD(y)=Ag = 1 QN (A) = N ! which proves Theorem 1.
Finally, let us prove Corollary 1. It su ces to prove that if B; B~ are two subsets of [2; N 1] with B~ = B [fmg, m 2= B, then the number of permutations with set of extrema B is smaller than the number of permutations with set of extrema B~. Using the symmetries of the problem, it su ces to count permutations with set of extrema B; B~ ending with a descent. If we impose this condition, let A; A~ be the corresponding descent sets. Using A; A~ we de ne by descending induction the polynomials fi; f~i as in Theorem 1.
Now de ne the polynomials hi, 1 i N by hN = 1 and hi(x) = fi(x) if i 2 A while hi(x) = fi(1 x) if i 2= A. Remark that for i N 1, the hi are increasing functions on [0; 1] such that hi(0) = 0. Besides, one can directly de ne the hi by descending induction as follows. First, hN = 1 and then, if i 2= B, while if i 2 B,
Z x
0 Z x
0 hi(x) =
hi+1(y) dy hi(x) = hi+1(1 y) dy (5) (6)
Likewise, de ne the polynomials h~i, 1 i N by h~N = 1, h~i(x) = f~i(x) if i 2 A~ and h~i(x) = f~i(1 x) if i 2= A~.
Since B~ = B [ fmg, we have h~i = hi for i > m. Moreover, using (5) and (6), we get that h~m(x) > hm(x) for every x 2 (0; 1] and by induction, for every i < m and every x 2 (0; 1], h~i(x) > hi(x). Integrating this inequality for i = 1, we get the result.
Remark 3.1 The coe cients of the polynomials fi can be computed by induction. Put i fN i(x) = X a(ki)xk
k=0 a(ki++11) = a(i)
k k + 1 a(ki++11) =
i a(i+1) = X 0 k=0 a(i)
k k + 1 a(i)
k k + 1 i 2 A, then a(0i+1) = 0 and for k 0,
i 2= A, then for k and
i 2= A, f0 = 1 If i 2 A1, i If i 2= A1, i 1 1 a(i+1) = Xi a(0i j) 0 j=0 (j + 1)! ( 1)jAc\[N i+1;N 1]j By recursion, this leads to (1), which provides an alternative proof of Theorem 1. 4
De ne by induction the sequence of polynomials (fn) by
0 Indeed, Theorem 1 tells us that the right-hand side is the number of permutations with length N and descent set N DN . Using the symmetries of the problem, we see that this is equal to the number of permutations with length N and descent set DN .
Consider the bivariate generating function
We want to prove that the right-hand side of this equality has the form given by Theorem 2. Let number of ascents in a period, = p jAj. By di erentiating, be the Solutions of this di erential equation have the general form where the !k are the p-th roots of 1 if is even and the p-th roots of 1 if is odd, and where the ak are power series: 1 F (x; t) = X tnfn(x)
n=0 X1 dn tn = Z 1 n=1 n! 0
tF (x; t)dx = ( 1) tpF (x; t)
p F (x; t) = X ak(t)e!ktx
k=1 ak(t) = X ak;ntn
n 0 p X ak;n = 0 k=1 p p X ak;n!kj = X ak;n!kj+1 k=1 k=1
1 is a descent, fn(0) = 0 whence and moreover f n0+1 =
fn, whence If n
1 is an ascent, fn(0) = 1 whence
It is thus possible to compute the the coe cients ak;n using the fact that
and moreover f n0+1 = fn, whence All these equations can be summarized in a matrix system with integer coe cients. We skip the details of the resolution of this system (this is a bit long but only uses elementary linear algebra) but eventually we nd n=1 where, for all k; l 2 [1; p], the function has a rational expression, with integer coe cients, in terms of the !k and of the functions p X ak;n!kj = k=1 We have implemented our algorithm in Maple1. The length of the permutation is nmax. The random variables U [n], which are drawn independently at random, represent the descent pro le: U [n] = 0 or 1 according as whether nmax n is a descent or an ascent. The reals V [n] in the code correspond to the random variables Yi in the algorithm.
As pointed out in the introduction, generating the variables Yi amounts to solving N equations of the form (4). Of course, we can only get approximate solutions and since the Yi are computed recursively, there is a propagation of errors. We shall not discuss this point from a theoretical point of view here. Observe, however, that these errors do not a ect the permutation we generate as long as, for each i, the di erence between Yi and its approximation is smaller than the minimal value of 2jYi Yj j over all i; j 2 [1; nmax].
Since equations of the form (4) are polynomial and since fi0 = fi 1, we can directly implement Newton's method in the algorithm. We stop the iterations in Newton's method as soon as two successive approximations of the solution are at distance less that 10 p, where p is a parameter that can be tuned. We give the time needed to generate permutations of variable length and for various values of p. For a permutation of length 2000, we have run the algorithm for the values p = 4 and p = 5 and we observe empirically that this yields the same permutation.
Here are some tables giving the run time of the algorithm for permutations of various lengths. In the rst table, we have also let the parameter p vary. The rst line is the length of the permutation, the second line the run time (in seconds) for p=4 and the third line the run time for p=5.
100 200 300 400 500 600 700 800 900 1000 0.18 0.93 2.21 4.46 6.75 11.36 16.14 23.36 31.73 37.93 0.19 0.97 2.52 4.65 7.36 12.29 17.70 24.66 34.59 41.15 In the next simulations, we have taken p=4 and we only give the integer part of the run time (in seconds). 1200 1400 1600 1800 2000 2200 2400 2600 2800 3000 68 90 119 174 213 269 351 627 678 766 descent pro le would be su cient, since the other polynomials can be obtained by di erentiation. However, this would mean computing these polynomials twice.
I am very grateful to Cyril Banderier for his help in the implementation of the algorithm. I also thank Olivier Bodini and Michael Wallner for useful comments and references. This work is partially supported by the research project \Combinatoire a Paris".