Séminaire Lotharingien de Combinatoire 70 (2014), Article B70f

ANDRÉ PERMUTATIONS, RIGHT-TO-LEFT AND LEFT-TO-RIGHT MINIMA

FILIPPO DISANTO*

Abstract. We provide enumerative results concerning right-to-left minima and leftto-right minima in André permutations of the first and second kind. For both of the two kinds, the distribution of right-to-left and left-to-right minima is the same. We provide generating functions and associated asymptotic results. Our approach is based on the tree-structure of André permutations.

1. Introduction

André permutations have been introduced in [4] and extensively studied in the literature, especially because of their relations with other combinatorial structures [5, 6, 7, 8, 12]. For instance, the cd-index of the Boolean algebra may be computed by summing the cd-variation monomials of André permutations [12].

It is possible to distinguish among two types of André permutations: those of the first kind A^{(1)} and those of the second kind A^{(2)}. The two classes are equinumerous. The n-th Euler number e_{n} = [z^{n}] sec(z) + [z^{n}] tan(z) counts André permutations of size n. The first terms are e_{0} = 1, e_{1} = 1, e_{2} = 1, e_{3} = 2, e_{4} = 5, e_{5} = 16, … Classically, Euler numbers only refer to secant numbers, the (even) coefficients of the Taylor expansion of sec(z). The (odd) coefficients of the Taylor expansion of tan(z) are called tangent numbers. Here, by an abuse of terminology, we let the term “Euler numbers” refer to both sequences of numbers. Besides André permutations, Euler numbers give the enumeration of several other combinatorial structures. In particular, they also count rooted binary un-ordered increasing trees. In [4], the authors describe two bijections — denoted here by ϕ_{1} and ϕ_{2} — which map André permutations of both kinds onto this class of trees and vice versa. Based on this correspondence, two classical permutation statistics, such as right-to-left minima (rlm) and left-to-right minima (lrm), have a natural interpretation in terms of paths of the associated trees.

In the present paper, we indeed focus on the enumeration of André permutations with respect to the parameters ‘number of right-to-left minima’ and ‘number of leftto-right minima’. To the best of our knowledge, these permutation statistics have not been investigated before in this context.

In Section 3.1, we show that the statistic ‘number of right-to-left minima’ has the same distribution on each of the two sets A_{n}^{(1)} and A_{n}^{(2)}. The same holds for the number of left-to-right minima and, more generally, for the joint distribution of the two statistics. Without loss of generality, we then focus on one type of André permutations, those of the second kind A = A^{(2)}. For the joint enumeration according to right-to-left and left-to-right minima, a functional equation for the associated trivariate generating function is provided.

*Email: fdisanto@uni-koeln.de, fdisanto@stanford.edu.

In Section 3.2, we find the bivariate generating function which counts André permutations A with respect to the size and the number of right-to-left minima. As a result, fixing the number of right-to-left minima, we provide a combinatorial formula which describes the desired enumeration in terms of Euler numbers. As a corollary to the results of this section, we obtain a correspondence between the number of right-to-left minima in André permutations and the number of cycles in the so-called cycle-up-down permutations introduced in [1]. This will need to be further investigated.

In Section 3.3, we study the number of left-to-right minima. We give a functional equation for the associated bivariate generating function. We show how the number of permutations of size n+1 with two left-to-right minima is related to the total number of right-to-left minima in permutations of size n. Finally, we study André permutations with a generic — but fixed — number of left-to-right minima, providing asymptotic estimates.

2. Preliminaries

The set of permutations of size n is denoted by S_{n}. If π = (π_{1}π_{2} … π_{n}) ∈ S_{n}, the set of its left-to-right minima is denoted by lrm(π), and its elements are those entries π_{i} such that, if j < i, then π_{i} < π_{j}. We denote by rlm(π) the set of right-to-left minima, and we remind the reader that π_{i} ∈ rlm(π) if j > i implies π_{i} < π_{j}.

A binary increasing tree is a rooted, un-ordered tree with nodes of outdegree 0, 1 or 2. Nodes of outdegree 0 are also called the leaves of the tree. Moreover, for such a tree, we require that each of the n nodes is bijectively labelled by a number in {1, 2, …, n} in a way that, going from the root to any leaf, we always find an increasing sequence of labels. If x and y are two nodes, we write x ≺ y when the label of x is less than the label of y. The linear order ≺ naturally corresponds to a geometric ranking of the nodes of a binary increasing tree. The smaller is the value of the label of a node the closer is the node to the root of the tree, which is indeed labelled by 1. Thus, if x ≺ y in a tree t, we will also say that x is placed above y (or y below x) in the ranking of t. The set of binary increasing trees is denoted by B, while we use the symbol B_{n} to denote the subset of B made of the trees with n nodes.

Observe that each tree in B can be drawn in the plane in a unique way respecting the following two conditions:

(A_{2}) if a node has only one child, then this child is drawn on the right of its direct

ancestor; (B_{2}) if a node x has two children y and z, with y ≺ z, then y is drawn on the right

of x, while z on the left. In Figure 1 we show the trees belonging to B_{4}, drawn respecting the previous two conditions.

The pair of conditions (A_{2}, B_{2}) is not the only possible one that allows a unique planar representation for each tree in B. Another pair of conditions is for instance:

(A_{1}) if a node has only one child, then this child is drawn on the right of its direct

ancestor; (B_{1}) if a node x has two children y and z, let t_{y} (respectively t_{z}) be the set of nodes

in the subtree generated by y (respectively by z). If max(t_{y}) ≺ max(t_{z}), then z is drawn on the right of x, while y on the left.

Figure 1. The trees in B_{4} and the associated André permutations of the second kind.

The sets of André permutations A^{(2)} and A^{(1)} can be defined in several equivalent ways, see for instance Section 2 of [7]. Since they are both subsets of S_{n} equinumerous with B_{n}, we choose to characterize their permutations with the help of two injective maps ϕ_{2}, ϕ_{1} : B_{n} → S_{n} (see [4]). For ϕ_{2} (respectively ϕ_{1}), the procedure is:

(1) given t ∈ B_{n}, draw t according to (A_{2}, B_{2}) (respectively (A_{1}, B_{1}));

(2) each leaf collapses into its direct ancestor whose label is then modified receiving on the left the label of the left child (if any) and on the right the label of its right child. We obtain in this way a new tree whose nodes are labelled with sequences of numbers;

(3) starting from the obtained tree go to step (2).

The algorithms ϕ_{2} and ϕ_{1} terminate when the tree t is reduced to a single node whose label is then a permutation ϕ_{2}(t), respectively ϕ_{1}(t), of size n. Note that, without considering step (1) but only (2) and (3), the procedures give a well-known [11] bijection ψ between ordered binary increasing trees B̃_{n} and the entire set of permutations of size n.

The sets A_{n}^{(i)} can be defined as A_{n}^{(i)} = {ϕ_{i}(t) ∈ S_{n} : t ∈ B_{n}} (with i = 2, 1). Inspecting Figure 1, the corresponding permutations in A_{4}^{(2)} are (from left to right) (4123), (1234), (3412), (1423), and (3124). For the same size n = 4, the permutations in A_{4}^{(1)} are (2314), (1234), (2134), (1324), and (3124).

An equivalent definition of André permutations can be given in terms of the so-called x-factorizations of permutations, see Definition 1 and Definition 2 of [8] and the related references. The equivalence is easily seen by observing that — following notations of [8]

— the λ-part of the x-factorization of a permutation π corresponds to the left subtree of the node x in the ordered binary increasing tree ψ^{−1}(π). Similarly, the ρ-part of the x-factorization corresponds to the right subtree of x in ψ^{−1}(π).

André permutations, as binary increasing trees, are enumerated, with respect to size, by the so called Euler numbers (e_{n})_{n≥0} whose exponential generating function satisfies^{1}

∫ E^{2} = 2E − z − 2,

and therefore is equal to

E(z) = sec(z) + tan(z).

The first terms of the sequence are 1, 1, 1, 2, 5, 16, 61, 272, 1385, …, and they correspond to entry A000111 in [10]. Furthermore, expanding E(z) near the dominant singularity Figure 2. Recursive decomposition of t_{i} = ϕ_{i}^{−1}(π_{i}), with π_{i} ∈ A^{(i)} (i = 2, 1). The min-node and max-node of each root subtree are highlighted. The left corner of these subtrees can be empty according to the right orientation of single nodes (conditions A_{i}).

1We will often adopt the notation ∫ f(z) = ∫_{0}^{z} f(a) da.

z = π/2, we easily obtain an asymptotic approximation for the coefficients, namely

\frac{e_{n}}{n!} ∼ \frac{4}{π} (\frac{2}{π} )^{n} .  (2.1)

3. Enumeration of right-to-left minima and left-to-right minima

In this section we study enumerative properties of right-to-left minima and left-to-right minima in André permutations. In Section 3.1, these statistics are jointly studied. In Section 3.2, we focus on the number of right-to-left minima, while, in Section 3.3, we investigate left-to-right minima.

3.1. Joint enumeration. Through the bijection ψ : B̃_{n} → S_{n} described in Section 2, we see that, for any given permutation π, the set rlm(π) corresponds to the nodes visited in the tree ψ^{−1}(π) starting from the root and performing only right-steps. Similarly, the set lrm(π) corresponds to the nodes visited in the tree ψ^{−1}(π) starting from the root and performing only left-steps.

Let π_{2} ∈ A_{n}^{(2)} and π_{1} ∈ A_{n}^{(1)}, consider t_{2} = ϕ_{2}^{−1}(π_{2}) and t_{1} = ϕ_{1}^{−1}(π_{1}). If n > 1 then, for i = 2, 1, the tree t_{i} consists of two trees, t_{i,left} and t_{i,right}, appended to its root on the left and on the right respectively. Clearly, rlm(ϕ_{i}^{−1}(t_{i})) = 1 + rlm(ϕ_{i}^{−1}(t_{i,right})) and lrm(ϕ_{i}^{−1}(t_{i})) = 1 + lrm(ϕ_{i}^{−1}(t_{i,left})), see Figure 2.

Furthermore, observe that, in both cases i = 2, 1, there are exactly

\binom{|t_{i,left}| + |t_{i,right}| − 1}{|t_{i,left}|}

ways of merging the ranking (i.e., labelling) of t_{i,left} with the ranking of t_{i,right} that create a tree drawn according to conditions (A_{i}, B_{i}). When i = 2, we have to put the root of t_{i,right} above the root of t_{i,left} while, when i = 1, we put the max-node of t_{i,right} below the max-node of t_{i,left} (the max-node is always a leaf). Also note that, when |t_{i,left}| = 0, the previous binomial expression returns 1.

From these considerations, it follows that, from an enumerative point of view, the same recursive construction describes the distribution of right-to-left minima and leftto-right minima in André permutations of the first and second kind.

Without loss of generality, we decide to focus on André permutations of the second kind. We thus set A = A^{(2)}, ϕ = ϕ_{2}, and, if not specified otherwise, we draw each tree t ∈ B according to (A_{2}, B_{2}).

The exponential generating function

H = H(x, y, z) = ∑_{π∈A} \frac{x^{r}y^{l}z^{n}}{n!} ,

where r = |rlm(π)|, l = |lrm(π)|, and n = size(π), satisfies the functional equation

H = 1 + xyz + ∑_{π_{1}=t_{right}≠∅} ∑_{π_{2}=t_{left}} x^{r_{1}+1}y^{l_{2}+1} \frac{z^{n_{1}+n_{2}+1}}{(n_{1} + n_{2} + 1)!} · \binom{n_{1} + n_{2} − 1}{n_{2}}.

Taking twice the derivative with respect to z, we obtain

\frac{∂^{2}H}{∂z^{2}} = xy \frac{∂H(x, 1, z)}{∂z} H(1, y, z),  (3.1)

which gives

H = 1 + xyz + xy ∫ ∫ \frac{∂H(x, 1, z)}{∂z} H(1, y, z).  (3.2)

Equation (3.2) can be used recursively to compute the polynomials

H_{i}(x, y) = ∑_{π∈A_{i}} x^{r}y^{l}.

For 0 ≤ i ≤ 5, we have

H_{0} = 1;
H_{1} = xy;
H_{2} = x^{2}y;
H_{3} = x^{3}y + x^{2}y^{2};
H_{4} = x^{4}y + 2x^{3}y^{2} + x^{3}y + x^{2}y^{2};
H_{5} = x^{5}y + 3x^{4}y^{2} + 3x^{4}y + 6x^{3}y^{2} + x^{3}y + x^{2}y^{3} + x^{2}y^{2}.

Furthermore, taking into account that H(1, 1, z) = E(z) and that E′(z) = \frac{1}{1−sin(z)}, Equation (3.1) becomes

\frac{∂^{2}H(x, 1, z)}{∂z^{2}} = x\frac{∂H(x, 1, z)}{∂z} E(z)  (3.3)

when we take y = 1, while it gives

\frac{∂^{2}H(1, y, z)}{∂z^{2}} = yE′(z) H(1, y, z)  (3.4)

when we take x = 1. In the following sections, we will study (3.3) and (3.4) as they provide the enumeration of André permutations with respect to the number of rightto-left minima and left-to-right minima, respectively.

3.2. Right-to-left minima. Here we focus on the right-to-left minima statistic using the symbol A_{n,r}^{R} to denote the subset of A_{n} made of those permutations π with |rlm(π)| = r.

Defining

F (x, z) = (\frac{1}{1 − sin(z)})^{x} ,

it is easy to check that

\frac{∂F (x, z)}{∂z} = xF (x, z) · E(z).

Thus, setting

F (x, z) = \frac{1}{x} \frac{∂H(x, 1, z)}{∂z},

we see that H(x, 1, z) satisfies (3.3). The series F (1, z) provides the (shifted) exponential generating function for Euler numbers. In other words, we have the following result.

Proposition 1. The (shifted) exponential generating function counting André permutations with respect to the size n and the number of right-to-left minima r is given by

F (x, z) = (\frac{1}{1 − sin(z)})^{x} = ∑_{π∈A} \frac{x^{r−1}z^{n−1}}{(n − 1) !} .

The first terms of |A_{n,r}^{R}| are thus given by the following table.

n/r 2  3  4  5  6  7  8 9 10
2  1  0  0  0  0  0  0 0 0
3  1  1  0  0  0  0  0 0 0
4  1  3  1  0  0  0  0 0 0
5  2  7  6  1  0  0  0 0 0
6  5  20  25  10  1  0  0 0 0
7 16 70 105  65  15  1  0 0 0
8 61 287 490 385 140 21 1 0 0
9 272 1356 2548 2345 1120 266 28 1 0
10 1385 7248 14698 15204 8715 2772 462 36 1

Note that Euler numbers are the entries in the first column. Furthermore, observe that, looking at the table column by column, we have

(\frac{∂^{r} F}{∂x^{r}} )_{x=0} = [ − log (1 − sin(z))]^{r}

and

\frac{1}{r!}[ − log (1 − sin(z))]^{r} = ∑_{π:|rlm(π)|=r+1} \frac{z^{n−1}}{(n − 1)!}.  (3.5)

Given that ∫ E(z) = − log (1 − sin(z)), as a corollary we obtain the following result.

Proposition 2. For every fixed r ≥ 1, we have

\frac{1}{r!} [∑_{n≥1} \frac{e_{n−1}}{n!} z^{n}]^{r} = ∑_{n≥l} \frac{|A_{n+1,r+1}^{R}|}{n!}z^{n},  (3.6)

where e_{0} = 1, e_{1} = 1, e_{2} = 1, e_{3} = 2, e_{4} = 5, e_{5} = 16, e_{6} = 61, … are Euler numbers.

For a fixed r ≥ 2, the asymptotic behaviour of the sequence |A_{n,r}^{R}| can also be examined at this point. Observe that near the dominant singularity z = π/2, we have

− log (1 − sin(z)) = log(2) − 2 log(z − π/2) + 1/12(z − π/2)^{2} + O((z − π/2)^{4}) ,

from which the following approximation results:

[ − log (1 − sin(z))]^{r} = [ log(2) − 2 log(z − π/2)]^{r} + O(z − π/2)

= 2^{r}[ − log(z − π/2)]^{r} + 2^{r−1}r log(2)[ − log(z − π/2)]^{r−1}

+ O([ − log(z − π/2)]^{r−2}) .  (3.7)

Rewriting log(z − π/2) = log(−π/2) + log (1 − \frac{2z}{π}), by Theorem VI.2 of [3] (see the special case discussed in Formula (27) on page 387) we have

[z^{n}][ − log(z − π/2)]^{r} ∼ (2/π)^{n}n^{−1} [C_{1} log^{r−1}(n) + O(log^{r−2}(n))] ,

and similarly

[z^{n}][ − log(z − π/2)]^{r−1} ∼ (2/π)^{n}n^{−1} [C_{2} log^{r−2}(n) + O(log^{r−3}(n))] ,

where C_{1}, C_{2} are positive constants.

Furthermore, by using Theorem VI.3 from [3] for the O-transfer, we have

[z^{n}][O([ − log(z − π/2)]^{r−2}) ] = O((2/π)^{n}n^{−1} log^{r−2}(n)) .

Finally, by applying Theorem VI.4 from [3] to (3.7) and recalling (3.5), we obtain the following result.

Proposition 3. For a fixed r ≥ 1 and n → ∞, we have the asymptotic approximation

\frac{|A_{n+1,r+1}^{R}|}{n!} = [z^{n}][ − log (1 − sin(z))]^{r} ∼ k_{r} · n^{−1} (\frac{2}{π} )^{n} log^{r−1}(n),  (3.8)

where k_{r} is a positive constant depending on r.

We conclude this section by recalling that in Chapter 7 of [9] the author studies a family of polynomials corresponding to the rows of the previous table. He also shows a criterion according to which each row defines a partition of the set of up-down permutations of a given size. Furthermore, in [1] the authors prove that the rows of the previous table also provide the enumeration of the so-called cycle-up-down permutations with respect to the size and the number of cycles. It is then natural to ask for a bijection between the permutations in A_{n+1} and the cycle-up-down permutations of size n which would explain the correspondence between right-to-left minima and cycles.

Figure 3. Decomposition of a tree with two left-to-right minima.

3.3. Left-to-right minima. In the previous section we have enumerated the permutations in A with respect to the size and the number of right-to-left minima. Here we study the cardinality of A_{n,l}^{L}, that is, the subset of A_{n} consisting of the permutations π with |lrm(π)| = l.

Using the polynomials H_{i} of Section 3.1, we have computed the entries of the following table showing, for all (n, l) ∈ {1, …, 10}^{2}, the number of permutations in A_{n,l}^{L}.

n/l 1  2  3  4 5 6 7 8 9 10
1 1  0  0  0 0 0 0 0 0 0
2 1  0  0  0 0 0 0 0 0 0
3 1  1  0  0 0 0 0 0 0 0
4 2  3  0  0 0 0 0 0 0 0
5 5  10  1  0 0 0 0 0 0 0
6 16  38  7  0 0 0 0 0 0 0
7 61 165  45  1 0 0 0 0 0 0
8 272 812 288 13 0 0 0 0 0 0
9 1385 4478 1936 136 1 0 0 0 0 0
10 7936 27408 13836 1320 21 0 0 0 0 0

In the first column we find (shifted) Euler numbers. It is also interesting to observe that the entries in the second column,

1, 3, 10, 38, 165, 812, 4478, 27408, 184529, 1356256, 10809786, 92892928, …,

belong to sequence A186367 of [10]. This sequence counts the number of cycles in all cycle-up-down permutations of size n (see also [1]) and, furthermore, it is strongly related to the total number of right-to-left minima in the permutations of A having fixed size. Indeed, we will prove that the exponential generating function associated with the non-zero entries of the column r = 2 of the table above is given by

(\frac{∂F}{∂x} )_{x=1} = \frac{− log (1 − sin(z))}{1 − sin(z)},

where F is the same series as in Proposition 1.

In order to prove the correspondence, we observe that each tree ϕ^{−1}(π) such that |lrm(π) = 2| can be decomposed as shown in Figure 3. In particular, note that tree t_{1} must contain at least one node (labelled by 2) while tree t_{2} could be empty. The class of trees consisting of a (possibly empty) tree appended to a node — denoted by k in Figure 3 — is counted by the exponential generating function

f_{t_{2}}(z) = ∑_{m>0} \frac{ẽ_{m}z^{m}}{m!} = ∫ E(z) = − log(1 − sin(z)) (with ẽ_{m} = e_{m−1}),

while

f_{t_{1}}(z) = ∑_{n>0} \frac{e_{n}z^{n}}{n!} = E(z) − 1

counts those trees having at least one node. Appending t_{1} of size n and t_{2} of size m − 1 as shown in Figure 3, we can build exactly \binom{n+m−1}{m} different trees. It follows that, in the previous table, the entries n ≥ 1 of the column r = 2 correspond to the coefficients of the exponential generating function

g_{2}(z) = ∑_{n>0} ∑_{m>0} \frac{e_{n}ẽ_{m}z^{n+m+1}}{(n + m)(n + m + 1)(m!)(n − 1)!}.

Finally, observe that

g′′_{2} = f_{t_{2}} · f′_{t_{1}} = log (\frac{1}{1 − sin(z)}) · (\frac{1}{1 − sin(z)}) = (\frac{∂F}{∂x} )_{x=1} .

Given the above calculations, we obtain the following result.

Proposition 4. For all n ≥ 2, we have

|A_{n+1,2}^{L}| = ∑_{r≥2}(r − 1) · |A_{n,r}^{R}|

= (n − 1)! · [z^{n−1}] (\frac{− log (1 − sin(z))}{1 − sin(z)}) .

As a corollary, we obtain the following result.

Corollary 5. For n ≥ 2, we have

|A_{n+1,2}^{L}| + |A_{n}| = ∑_{r≥2} r · |A_{n,r}^{R}|,  (3.9)

and therefore the expected number of right-to-left minima in a random permutation of A_{n} is given by 1 + |A_{n+1,2}^{L}|/|A_{n}|.

3.3.1. Fixing the number of left-to-right minima. It is interesting to investigate in more detail what happens when we fix the number of left-to-right minima in A_{n}. Let

G_{l}(z) = ∑_{n} \frac{|A_{n,l}^{L}|}{n!} · z^{n}

and

G(y, z) = ∑_{l≥0} y^{l}G_{l}(z).

Thus G = H(1, y, z) and, from (3.4), we see that

\frac{∂^{2}G}{∂z^{2}} = yE′(z) · G,  (3.10)

where E′(z) = \frac{1}{1−sin(z)}.

From (3.10) we may derive a recursion for G_{l}.

Proposition 6. The family of generating functions (G_{l})_{l} satisfies

G_{l}(z) = ∫ ∫ G_{l−1}(z) · E′(z),  (3.11)

where E′(z) = \frac{1}{1−sin(z)} and G_{1}(z) = ∫ E(z) = − log (1 − sin(z)).

Unfortunately, Equation (3.10) does not give an explicit solution for G. Still, as we will see later, it can be used to explore the structure of the solution in a neighbourhood of the singularity z = π/2.

Let us now focus on the exact computation of G_{l}. To do so, one can apply the result of Proposition 6 together with the fact that E = E(z) satisfies ∫ E^{2} = 2E −z −2. Here we compute explicitly the generating functions G_{l} for the first values of l, say l = 1, 2, 3, elucidating the correspondence with the generating function for Euler numbers. If we define

∫ ^{(i)} f =\overbrace{∫ ∫ … ∫} f^{i times},

for l = 1, 2 we have

G_{1} = ∫ E

G_{2} = (∫ ^{(2)} (∫ E) E′) = (∫ (E ∫ E)) − ∫ ^{(2)} E^{2}

= \frac{1}{2} · (∫ E)^{2} − ∫ (2E − z − 2)

= \frac{1}{2} · (∫ E)^{2} − 2 (∫ E) + \frac{z^{2}}{2} + 2z,

while, for l = 3, we obtain

G_{3} = (∫ ^{(2)} \frac{(∫ E)^{2}}{2} E′) − 2 (∫ ^{(2)} (∫ E) E′) + (∫ ^{(2)} (\frac{z^{2}}{2} + 2z) E′)

= (∫ E \frac{(∫ E)^{2}}{2} ) − (∫ ^{(2)} E^{2} (∫ E)) − 2 [(∫ E (∫ E)) − ∫ ^{(2)} E^{2}]

+ (\frac{z^{2}}{2} + 2z) (∫ E) + (−2z − 4) (∫ ^{(2)} E) + 3 (∫ ^{(3)} E)

= \frac{1}{6} · (∫ E)^{3} − [(∫ (2E − z − 2) (∫ E)) − (∫ ^{(2)}(2E − z − 2)E)]

− 2 [\frac{1}{2} · (∫ E)^{2} − ∫ (2E − z − 2)] + (\frac{z^{2}}{2} + 2z) (∫ E)

+ (−2z − 4) (∫ ^{(2)} E) + 3 (∫ ^{(3)} E)

= \frac{1}{6} (∫ E)^{3} − 2 (∫ E)^{2} + (8 + 2z + \frac{z^{2}}{2} ) (∫ E) − 2z^{2} − 8z

+ (−2z − 4) (∫ ^{(2)} E) + 4 (∫ ^{(3)} E) .

Recalling that

[z^{n}] (∫ ^{(i)} E(z)) = \frac{e_{n−i}}{n!} ,

the previous calculations express |A_{n,l}^{L}| (l = 1, 2, 3) in terms of Euler numbers e_{n}.

For values of l greater than 3 the computation of G_{l} becomes more difficult. In these cases, we can still use the results of Proposition 6 to obtain asymptotic estimates of the coefficients [z^{n}]G_{l}(z). Using standard methods of analytic combinatorics (see [3]), it is sufficient to know an approximation of the function G_{l} near its dominant singularity to describe the behaviour of [z^{n}]G_{l}(z) for n → ∞. In this case, the idea is to iteratively compute an approximation for G_{l+1} by integration of an approximation for (G_{l} · E′).

Near the dominant singularity z = π/2 we have

E′(z) = \frac{1}{1 − sin(z)} = \frac{2}{(\frac{π}{2} − z)^{2}} + O(1) ,  (3.12)

and, for every A > 0,

G_{1} = ∫ E(z) = log (\frac{1}{1 − sin(z)}) = −2 log (\frac{π}{2} − z) + O(1) = O((\frac{π}{2} − z)^{−A}) .

(3.13)

Then, as a first approximation, one has

(G_{1} · E′)(z) = O((\frac{π}{2} − z)^{−2−A}) ,

which gives by Proposition 6 and Theorem VI.9 from [3] (see Case (i))

G_{2}(z) = O((\frac{π}{2} − z)^{−A}) .

We remark that, by the mentioned theorem, we can obtain a singular expansion of G_{2} by integrating, according to classical rules, the singular expansion of (G_{1} ·E′). Iterating the procedure one has that, independently of l, for every A > 0

G_{l}(z) = O((\frac{π}{2} − z)^{−A}) .  (3.14)

Applying Theorem VI.3 of [3] to (3.14) gives the following bound.

Proposition 7. When n is large, for every A > 0 and independently of l, we have

\frac{|A_{n,l}^{L}|}{n!} = [z^{n}]G_{l}(z) = O((\frac{2}{π} )^{n} · n^{A−1}) .  (3.15)

Recalling that \frac{|A_{n}|}{n!} ∼ \frac{4}{π} (\frac{2}{π})^{n} (see (2.1)), Equation (3.15) gives a measure of how strong the effect of fixing the number of left-to-right minima in André permutations is. Structural properties of G near the singularity. To conclude our asymptotic analysis, we go back to Equation (3.10) to describe a structural property of the solution G. Indeed, treating y as a constant, we can apply Theorem VII.9 of [3] to find that near the regular singular point z = π/2 the desired solution G can be expressed as

G = a_{y} · (\frac{π}{2} − z)^{\frac{1+\sqrt{1+8y}}{2}} A_{y} (z − \frac{π}{2} ) + b_{y} · (\frac{π}{2} − z)^{\frac{1−\sqrt{1+8y}}{2}} B_{y} (z − \frac{π}{2} ) ,

where y could in principle appear in a_{y}, A_{y}(z), b_{y}, B_{y}(z), and the functions A_{y}(z), B_{y}(z) are analytic at z = 0.

It is interesting to note that, taking a_{y} = 0 and b_{y} = B_{y} = 1, one obtains

G_{α} = (\frac{π}{2} − z)^{\frac{1−\sqrt{1+8y}}{2}} ,

whose expansion at y = 0 reads

G_{α} = 1 − 2y log(π/2 − z) + y^{2} (4 log(π/2 − z) + 2 [log(π/2 − z)]^{2})

+ y^{3} (−16 log(π/2 − z) − 8 log^{2}(π/2 − z) − \frac{4}{3} log^{3}(π/2 − z)) + · · · .

Based on the approximation for ∫ E given in (3.13), this reflects the asymptotic behaviour of the expressions for G_{1}, G_{2}, and G_{3} which have been previously computed. This can be justified by observing that G_{α} satisfies

\frac{∂^{2}G_{α}}{∂z^{2}} = y · \frac{2}{(π/2 − z)^{2}} · G_{α},

which is obtained by substituting 2/(π/2 − z)^{2} for E′(z) (the former being the main part of the singular expansion (3.12)) in (3.10), i.e., the defining equation for G.

Acknowledgement

This work was financially supported by grant DFG-SPP1590 from the German Research Foundation.

References

[1] E. Deutsch and S. Elizalde, Cycle-up-down permutations, Australas. J. Combin. 50 (2011), 187– 199.

[2] J. A. Fill, P. Flajolet and N. Kapur, Singularity analysis, Hadamard products and tree recurrences, J. Comput. Appl. Math. 174 (2005), 271–313.

[3] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University press, 2009.

[4] D. Foata and M.-P. Schützenberger, Nombres d’Euler et permutations alternantes, unabriged version, 71 pages, University of Florida, Gainesville (1971), available at

http://www.mat.univie.ac.at/∼slc/.

[5] D. Foata and V. Strehl, Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers, Math. Z. 137 (1974), 257–264.

[6] D. Foata and V. Strehl, Euler numbers and variations of permutations. In: Colloquio Internazionale sulle Teorie Combinatorie, 1973, Tome I (Atti Dei Convegni Lincei 17, 119–131), Accademia Nazionale dei Lincei, Rome, 1976.

[7] G. Hetyei, On the cd-variation polynomials of André and Simsun permutations, Discrete Comput. Geom. 16 (1996), 259–275.

[8] G. Hetyei and E. Reiner, Permutation trees and variation statistics, Europ. J. Combin. 19 (1998), 847–866.

[9] W. P. Johnson, Some polynomials associated with up-down permutations, Discrete Math. 210 (2000), 117–136.

[10] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, available at: http://oeis.org/.

[11] R. P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Monterey, CA, 1986.

[12] R. P. Stanley, Flag f-vectors and the cd-index, Math. Z. 216 (1994), 483–499.