Thomas Schwentick

Klaus Barthelmann

Local Normal Forms for First-Order Logic with Applications to Games and Automata

Keywords: First-order logic, existential monadic second-order logic, games, automata, locality

Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃x1, . . . , x l ∀yϕ where ϕ is r-local around y, i. e. quantification in ϕ is restricted to elements of the universe of distance at most r from y.

From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs.

As another application, automata models are defined that have, on arbitrary classes of relational structures, exactly the expressive power of first-order logic and existential monadic second-order logic, respectively.

Introduction

First-order (FO) logic and its extensions play an important role in many branches of (theoretical) computer science. Examples that will be considered in this paper are automata theory and descriptive complexity. Since Büchi's and Elgot's famous characterization of the regular string languages as the sets of models of (existential) monadic second-order (MSO) sentences, (existential) MSO logic has been used as a guideline in the search for reasonable automata models for other kinds of structures like trees or graphs. In descriptive complexity, since Fagin [START_REF] Fagin | Generalized first-order spectra and polynomial-time recognizable sets[END_REF] showed that the complexity class NP coincides with the sets of models of existential secondorder (Σ 1 1 ) sentences, many complexity classes have been characterized by extensions of FO logic [Var82, Imm86, Imm87, AV89, Grä92] and there is still hope that separations of complexity classes might be possible by separating the expressive power of the respective logics. For a recent result in this direction see the paper of Libkin and Wong [START_REF] Libkin | Unary quantifiers, transitive closure, and relations of large degree[END_REF].

Despite its importance as an ingredient for more expressive logics, it is well-known that the expressive power of FO logic is rather limited. It can only express properties that depend on the local appearance of a structure. This intuition has been formalized in different ways by Hanf [Han65] and Gaifman [START_REF] Gaifman | On local and nonlocal properties[END_REF]. Hanf showed that, for every first-order formula ψ, there is an r such that whether ψ holds in a structure A ("A |= ψ") only depends on the multiset of isomorphism types of all r-spheres in A. Here an r-sphere is a substructure of A which is induced by all elements of A that have distance at most r from a fixed element of A. On the other hand, Gaifman showed that, for every first-order formula ψ, there are r and d such that whether A |= ψ holds depends only on how many elements with pairwise disjoint r-neighbourhoods exist that fulfil θ, for every formula θ of quantifier depth at most d.

The starting question for the present investigation was to which extent Hanf's and Gaifman's conditions could be combined. The goal was to replace the isomorphism types in Hanf's condition by something weaker and to get rid of the "disjoint r-neighbourhoods" constraint in Gaifman's condition. (For very interesting recent results concerning Hanf's and Gaifman's theorems from a different point of view see the papers of Libkin and Dong et al. [START_REF] Libkin | On the forms of locality over finite models[END_REF][START_REF] Dong | Local properties of query languages[END_REF].) It is easy to see that the straightforward attempt to replace the isomorphism type of a sphere S in Hanf's condition by its Hintikka-type for some d (i. e. by the set of formulas of quantifier depth at most d that hold in S) does not work. A counterexample is given by the set of clique graphs. For every d, the spheres of a graph consisting of one 2d-clique fulfil exactly the same formulas of quantifier depth at most d as those of a graph which consists of two disjoint d-cliques. Nevertheless, it turns out that it is indeed possible to combine the two approaches in the following sense. For every FO formula ψ there are l and r such that A |= ψ if and only if it is possible to put l pebbles onto A such that in the resulting structure all r-spheres fulfil the same FO formula ϕ. Put in another way, every FO formula is logically equivalent to a formula of the form ∃x 1 , . . . , x l ∀yϕ where ϕ is r-local around y, i. e. quantification in ϕ is restricted to elements of the universe with distance at most r from y. From this normal form one can easily derive normal forms for other logics like monadic second-order logic. For existential monadic second-order logic we can show a bit more. Every such formula is, on classes of connected structures, equivalent to a formula of the form ∃X 1 , . . . , X l ∃x∀yϕ where ϕ is restricted as above. If every structure has an element which is uniquely definable by a local formula, we can even achieve a formula of the form ∃X 1 , . . . , X l ∀yϕ.

As one application of the normal forms we get variants of the Ehrenfeucht game [START_REF] Ehrenfeucht | An application of games to the completeness problem for formalized theories[END_REF] for first-order logic and existential monadic second-order logic in which the spoiler has only restricted global access to the structures that are played. After a phase in which he can select some vertices of the first graph (before having seen the other one) and one vertex of the other graph, in the second phase all moves are restricted to the neighbourhoods of one vertex in each graph.

Another application concerns a form of automata on relational structures. It is well-known that regular sets of strings can be obtained as projections of locally testable sets, namely the sets of transition sequences of a (nondeterministic) automaton. Thomas [START_REF] Thomas | On logics, tilings and automata[END_REF] used this idea to extend the notion of recognizability to other objects like grids and graphs of uniformly bounded degree. The normal forms allow to generalize the method of local testing further to sets of arbitrary relational structures. Moreover, they maintain the correspondence to definability in a natural logic.

The paper is organized as follows. In Section 2 we give basic definitions and fix some notation. In Section 3 we show the normal form theorems. In Section 4 we define the simplified games for first-order logic and monadic Σ 1 1 -logic. The analogous results for automata are presented in Section 5. The ensuing automata models are also compared with the automata of [START_REF] Thomas | On logics, tilings and automata[END_REF][START_REF] Thomas | Elements of an automata theory over partial orders[END_REF][START_REF] Thomas | Automata theory on trees and partial orders[END_REF] and [START_REF] Courcelle | The monadic second-order logic of graphs. I. recognizable sets of finite graphs[END_REF]. Section 6 contains a conclusion.

Definitions and Notations

A relational signature σ is a finite set of relation symbols R, each with a fixed arity a(R), and constant symbols c. We do not use function symbols. A σ-structure A consists of a universe U A (the vertices of A), an a(R)-ary relation R A on U A , for every relation symbol R of σ and a constant c A , for every constant symbol c of σ. All theorems in this paper are valid for infinite and finite structures. We assume that all structures contain at least two elements.

Let the Gaifman graph of a σ-structure A have universe Let H d (A) denote the depth-d-Hintikka-type of A, i. e., the set of all FO sentences of quantifierdepth at most d that hold in A [START_REF] Ebbinghaus | Finite Model Theory[END_REF]. Recall that H d (A) contains only finitely many different formulas w. r. t. logical equivalence. The elementary type of a tuple a 1 , . . . , a k of vertices of A is the conjunction of all atomic σ-formulas with variables from x 1 , . . . , x k that hold in A, a 1 , . . . , a k . Now we are going to define our notions of locality, r-locality and basic locality. Informally, a formula is r-local around its free variables x, if its truth depends only on S r (x). More formally, a FO formula ϕ(x, u) with free variables from x = x 1 , . . . , x l and u = u 1 , . . . , u m is r-local around x if all variables that are quantified in ϕ are bounded to S r (x). I. e., if ∃yψ (resp. ∀yψ) is a subformula of ϕ then ψ is of the form (δ(y, x) ≤ r) ∧ χ (resp. (δ(y, x) ≤ r) → χ), for some χ which is r-local around x. A formula is local around x if it is r-local around x for some r.

Here, (δ(y, x) ≤ r) is an abbreviation for the straightforward FO formula which expresses that the distance of y from x is at most r. A formula ϕ is basic local around x if it is a Boolean combination of formulas each of which is local around some variable x i . I. e., properties that are expressed by basic formulas depend only on combinations of the properties of spheres. A formula is ∃ * ∀-local if it is of the form ∃x 1 , . . . , x l ∀yϕ where ϕ is basic local around x 1 , . . . , x l , y. It should be noted that in Gaifman's terminology [START_REF] Gaifman | On local and nonlocal properties[END_REF] a formula is local around a variable x only if x is its single free variable.

Normal Forms

By definition, every basic local formula around x is logically equivalent to a local formula around x. The following lemma shows that the converse is also true. This will be an important tool in the proof of the normal form theorem.

Lemma 3.1 Every first-order formula ϕ which is local around variables x = x 1 , . . . , x l is logically equivalent to a formula which is basic local around x.

Proof. Let ϕ be a first-order formula with free variables x = x 1 , . . . , x l and u = u 1 , . . . , u m that is local around x. The proof is by induction on the structure of ϕ. If ϕ is an atomic formula, it is basic local around x by definition. If ϕ is of the form ¬ψ or ψ 1 ∨ ψ 2 then the statement holds by the induction hypothesis.

In the only remaining case, ϕ is of the form ∃y((δ(y, x) ≤ r) ∧ χ) for some r and some formula χ which is local around x. By induction, χ is logically equivalent to a formula which is basic local around x. By writing χ in disjunctive normal form, we get that χ is logically equivalent to a formula of the form j i χ ji , where, for some r ′ , every χ ji is r ′ -local around x i . Hence, ϕ is logically equivalent to a disjunction of formulas ∃y((δ(y, x) ≤ r)

∧ i χ i ) , (*)
where every χ i is r ′ -local around x i . In the following, we assume w. l. o. g. that ϕ is of the form (*). In a sense, we have to distribute the quantification of y over the χ i . The problem which arises is that some of the x i might be close to each other, so that y might play a role for several χ i simultaneously. To get around this problem we choose, for every "cluster" C of vertices x i that are close to each other, a representative v(C) such that quantification around any x i of C can be replaced by quantification around v(C). More formally, we proceed as follows. We associate with every structure A and tuple a = a 1 , . . . , a l of vertices of A a graph G(A, a) with vertex set V = {1, . . . , l} and edge set E, which contains the edge (i, j) whenever δ(a i , a j ) ≤ R := r + r ′ + 1. We are going to construct, for every graph G on {1, . . . , l}, formulas θ G and ϕ G each of which is basic local around x, such that, for every A and a it holds that

• A |= θ G iff G(A, a) = G, and
• if G = G(A, a) then [A |= ϕ G ⇐⇒ A |= ϕ].
Once we have established the existence of such formulas the statement of the lemma follows immediately because ϕ ≡ G (θ G ∧ ϕ G ), where the disjunction is over all graphs G on {1, . . . , l}.

Let in the following a graph G = (V, E) be fixed. The definition of θ G is straightforward:

θ G := i∈V ( j∈V (i,j)∈E (δ(x i , x j ) ≤ R) ∧ j∈V (i,j) / ∈E (δ(x i , x j ) > R)) .
It is easy to see that, for every i, the i-th conjunct can be made R-local around x i . In order to construct ϕ G we choose from each connected component C of G a vertex v(C). Then ϕ G can be defined as

C,α (∃y[(δ(y, x v(C) ) ≤ R|C|) ∧ α ∧ i∈C (δ(y, x i ) ≤ r) ∧ i∈C χ ′ i,C ] ∧ i / ∈C χ ′ i,C,α ) .
Here, the disjunction is over all connected components C of G and all (finitely many) elementary types α of x, u, y.

If i ∈ C then χ ′ i,C is obtained from χ i by making all quantifications R-local around x v(C) . If i / ∈ C then χ ′ i,C
,α is obtained from χ i by • replacing every atomic subformula that contains the variable y and a variable that is bound in χ i with false, and

• rewriting all other atomic formulas that refer to y according to α.

These replacements assure that y does not occur in χ ′ i,C,α and that every χ ′ i,C and every χ ′ i,C,α is local around x i . It should be pointed out that the internal subformula [• • • ] can only become true if δ(, x i ) ≤ r holds, for some i ∈ C, hence if δ(y, x j ) ≤ r ′ + 1 does not hold. This justifies the replacement of atomic subformulas that contain the variable y and a variable that is bound in χ i with false. We note that already a smaller radius of y around x v(C) suffices if v(C) is chosen closer to the "center" of C.

Theorem 3.2 Every FO formula is logically equivalent to a ∃ * ∀-local formula.

Proof. Let Ψ be a first-order formula with free variables u = u 1 , . . . , u m . First we are going to show that Ψ is logically equivalent to a positive Boolean combination of ∃ * ∀-local formulas. In the following, if ϕ is r-local around its single variable, we write ∃ r l xϕ(x) as an abbreviation for

∃x 1 , . . . , x l [ l i=1 ϕ(x i ) ∧ i =j (δ(x i , x j ) > 2r)] .
Gaifman's theorem implies that Ψ is logically equivalent to a positive Boolean combination of formulas of the following three types.

1. ∃ r l xϕ(x), 2. ¬∃ r l xϕ(x), and 3. local formulas around u.

We are going to show that formulas of each of these types are logically equivalent to positive Boolean combinations of ∃ * ∀-local formulas. Formulas of type 1 are already ∃ * -local because δ(x i , x j ) > 2r can be easily expressed by a formula which is 2r-local around x i . A formula ϕ(u) of type 3 is logically equivalent to ∃x(x = u ∧ ϕ(x)). As, by Lemma 3.1, ϕ(x) is logically equivalent to a formula that is basic local around x we obtain again a ∃ * -local formula. We still have to consider formulas of type 2. Let ψ ≡ ¬∃ r l xϕ(x). ψ is logically equivalent to

¬∃xϕ(x) ∨ l-1 i=1 [∃ r i xϕ(x) ∧ ¬∃ r i+1 xϕ(x)] .
Of course, ¬∃xϕ(x) is equivalent to ∀x¬ϕ(x), which is of the required form. For every i,

∃ r i xϕ(x)∧ ¬∃ r i+1 xϕ(x) is logically equivalent to ∃x 1 , . . . , x i ∀y[ i ϕ(x i ) ∧ i =j (δ(x i , x j ) > 2r) ∧ ∀z 1 , . . . , z i+1 ¬( j (δ(z j , x) ≤ 2r) ∧ i =j (δ(z i , z j ) > 2r) ∧ j ϕ(z j )) ∧ ¬((δ(y, x) > 2r) ∧ ϕ(y))] ,
(**) expressing that there are x 1 , . . . , x i that fulfil ϕ, but

• neither there is a y which fulfils ϕ and is far from all the x j ,

• nor there exist different z 1 , . . . , z i+1 all of which fulfil ϕ and are close to the x j .

As the [• • • ] part of this formula can be made local around x 1 , . . . , x i , y, it is logically equivalent to a basic local formula around x 1 , . . . , x i , y by Lemma 3.1. We conclude that ψ is logically equivalent to a ∃ * ∀-local formula.

It remains to show that every positive Boolean combination of

∃ * ∀-local formulas is logically equivalent to a ∃ * ∀-local formula. Consider two ∃ * ∀-local formulas ψ 1 ≡ ∃x 1 , . . . , x k ∀yϕ 1 (x, y) and ψ 2 ≡ ∃x ′ 1 , . . . , x ′ m ∀y ′ ϕ 2 (x ′ , y ′ ). ψ 1 ∧ ψ 2 is equivalent to ∃x, x ′ ∀y[ϕ 1 (x, y) ∧ ϕ 2 (x ′ , y)] and ψ 1 ∨ ψ 2 is equivalent to ∃z, z ′ , x, x ′ ∀y(z = z ′ ∧ ϕ 1 (x, y)) ∨ (z = z ′ ∧ ϕ 2 (x ′ , y)) .
In fact, by a closer inspection of Theorem 3.2, we can go one step further and show that local quantification around one single variable is enough.

Theorem 3.3 Every first-order formula is logically equivalent to a formula of the form ∃x 1 , . . . , x l ∀yϕ(x, y), where ϕ is local around y.

Proof. We refer in the following to the threefold case distinction in the proof of Theorem 3.2. Formulas of type 1 can be transformed into

∃x 1 , . . . , x l ∀y l i=1 [y = x i → (ϕ(y) ∧ ∀z((δ(z, y) ≤ 2r) → j =i (z = x j )))] .
For formulas of type 3 we apply the same idea, obtaing a formula ∃x∀y(x = u∧ϕ ′ (x, y)), where ϕ ′ is obtained by applying Lemma 3.1 and replacing every local subformula θ(x i ) by y = x i → θ(y).

For formulas of type 2 we first note that in (**) the subformulas of line 1 and 3 can be transformed into the correct form easily. The subformula of the second line, which does not refer to y, can be made local around x and therefore, again by Lemma 3.1, basic local around x. By applying the same idea as in the cases 1 and 3 above, we obtain eventually a formula of the correct kind.

There are straightforward analogues of Theorem 3.2 for other logics. Of special interest is the case of monadic Σ 1 1 -logic, as quantification of unary relations does not change the locality properties of a structure. We get immediately that every monadic Σ 1 1 -formula is logically equivalent to a formula of the form ∃X 1 , . . . , X l ∃x 1 , . . . , x m ∀yϕ , where ϕ is local around y. For classes of structures that have a connected Gaifman graph we can show even stronger normal forms. The basic idea is that global information about the structure can be transported along the relations and collected in a designated place. This generalizes a similar procedure in [START_REF] Thomas | Elements of an automata theory over partial orders[END_REF][START_REF] Thomas | Automata theory on trees and partial orders[END_REF], where the transport is much more deterministic.

Theorem 3.4 Let C be a class of structures with a connected Gaifman graph. Then the following hold.

(a) On C every monadic Σ 1 1 formula is equivalent to a formula of the form ∃X 1 , . . . , X l ∃x∀yϕ, where ϕ is local around y.

(b) If there exists a formula ρ that is local around its one free variable such that, for every structure A of C, A |= ∃!xρ(x) then on C every monadic Σ 1 1 formula is equivalent to a formula ∃X 1 , . . . , X l ∀yϕ, where ϕ is local around y.

Proof. We only give sketches of the proofs.

(a) Let ψ ≡ ∃X 1 , . . . , X l ∃x 1 , . . . , x m ∀yϕ, where ϕ is basic r-local around y. We explain how the x i can be eliminated in favour of one x. We have to find a way to distinguish m vertices in a structure A. The idea is to guess a vertex x and m minimal paths p 1 , . . . , p m in the Gaifman graph of A such that, for every i, p i starts in x and ends in x i . Note that we view these graph as directed although the Gaifman graph is an undirected graph. Every p i is encoded by two unary relations Y i , Z i . Y i contains all vertices of p i . As p i is a shortest path we can conclude that x and x i have degree 1 w. r. t. p i and all other vertices of p i have degree 2 w. r. t. p i . Z i is used to give p i an orientation. v ∈ Z i just in case v is the j-th vertex of p i , for some j, (where x is the 0-th vertex) and j is congruent to one of 0,1,3 modulo 6.

It is straightforward that there exists a formula ρ(x, y) that is local around y such that A, Y, Z, x |= ∀yρ if and only if Y and Z encode m paths that have their starting point in x. (Y and Z might also encode some directed cycles but this does not matter.) It remains to show how in ϕ all references to variables x j can be replaced. All atomic formulas θ in which a x j occurs together with y or with a variable that is bound in ϕ (around y!) can be easily replaced by a formula ∃z((δ(z, y) ≤ r + 1) ∧ χ i (z) ∧ θ ′ ), where χ i (z) tests that z is the sink of p i (this can be checked 5-locally around z, hence (r + 6)-locally around y) and in θ ′ every occurrence of x j is replaced by z.

To replace atomic formulas that only refer to variables of x (and u, the free variables) we proceed as follows. For every atomic formula α which only contains variables from x and u we introduce a unary relation T α . The intention is that T α = U A in the case that A, x, u |= α and T α = ∅ otherwise. Because A is connected, the formula

∀y[y ∈ T α ↔ ∀z((δ(z, y) ≤ 1) → z ∈ T α )]
checks that T α contains either all or no vertices. It is also easy to check by a 6-local formula around y (using some χ i as needed) that T α contains all vertices just in case the endpoints of (some of) the m paths behave according to α.

(b) In the construction of part (a), x only occurs in θ. Instead of guessing x and paths that start in x we can guess paths that start in the vertex that is distinguished by ρ.

Theorem 3.4 (b) can be generalized in a straightforward way to classes of structures with a bounded number of connected components. In the respective generalization of Theorem 3.4 (a)

the number of connected components bounds the number of existentially quantified FO variables in the normal form. On the other hand, it can be seen by a simple game argument (cf. Section 4 below) that the set of two-vertex-graphs can not be characterized by a formula of the type considered in Theorem 3.4 (a). Of course, Theorem 3.2 is also true with ∀ * ∃-local formulas in place of ∃ * ∀-local formulas. Although it is easy to see that ∃ * -local formulas do not capture all first-order properties (e. g. they cannot express the property "every vertex is coloured black"), it follows from results of Compton [START_REF] Compton | Some useful preservation theorems[END_REF] that Boolean combinations (including negations!) of ∃ * -formulas do.

From Theorem 3.2 we can conclude that every first-order (and monadic Σ 1 1 ) formula on graphs (suitably represented by adjacency lists) can be evaluated by a nondeterministic Random-Access-Machine with unit-cost measure in time O(nd O(1) ), where n denotes the number of vertices and d the maximal vertex-degree.

Games

Ehrenfeucht games -invented in [START_REF] Ehrenfeucht | An application of games to the completeness problem for formalized theories[END_REF] building on work of Fraïssé [START_REF] Fraïssé | Sur quelques classifications des systèmes de relations[END_REF] -are an important tool for proving inexpressibility results in Mathematical Logic. In fact, in Finite Model Theory, where only finite structures are considered, they are the major tool available (cf. [START_REF] Fagin | Easier ways to win logical games[END_REF]). To show that a given property P of finite structures is not expressible in FO logic it is enough to prove that the duplicator, one of two players, has a winning strategy in the ordinary FO Ehrenfeucht game for P (for a definition see e. g. [START_REF] Ebbinghaus | Finite Model Theory[END_REF]). Variants of Ehrenfeucht games are available for proving inexpressibility results for many other logics, including second-order logics [START_REF] Tenney | Second-order Ehrenfeucht games and the decidability of the second-order theory of an equivalence relation[END_REF], existential second-order logics [Ten75, AF90], transitive closure logics [START_REF] Calò | The Ehrenfeucht-Fraïssé games for transitive closure logic[END_REF] and finite variable logics [START_REF] Barwise | On Moschovakis closure ordinals[END_REF][START_REF] Immerman | Upper and lower bounds for first-order expressibility[END_REF].

Proving the existence of a winning strategy for the duplicator is often very difficult. To simplify such proofs the following approaches have been taken. There have been developed several conditions that assure that the duplicator has a winning strategy on two given structures: the Hanf-condition [START_REF] Fagin | On monadic NP vs. monadic co-NP[END_REF], the Arora-Fagin condition [START_REF] Arora | On winning strategies in Ehrenfeucht-Fraïssé games[END_REF] and the condition of Schwentick [START_REF] Schwentick | On winning Ehrenfeucht games and monadic NP[END_REF] (for a survey see [START_REF] Fagin | Easier ways to win logical games[END_REF]). All of these conditions exploit the fact that FO logic can only express combinations of local properties, i. e. properties of regions of bounded size. On the other hand there have been attempts to make the game easier to play for the duplicator. An important example is the invention of the Ajtai-Fagin game for existential second-order logic which allows the duplicator to choose the second structure after the spoiler (the duplicator's opponent) has selected relations for the first structure. The idea behind that game can be used whenever all formulas of a logic have an existential quantifier-prefix.

In this section we introduce local Ehrenfeucht games for FO logic and monadic Σ 1 1 logic. Additionally, we characterize the mentioned logics in terms of Hintikka-types (cf. Section 2). First of all, we describe the local first-order Ehrenfeucht game for a class C of σ-structures. Like the ordinary Ehrenfeucht game it is played by two players, called the spoiler and the duplicator. It has three parameters, l, r and d and consists of three stages.

Stage 1

The duplicator chooses a σ-structure A ∈ C. The spoiler selects vertices x 1 , . . . , x l from A. Then the duplicator chooses a σ-structure A ′ / ∈ C and vertices x ′ 1 , . . . , x ′ l from A ′ .

Stage 2

The spoiler chooses a vertex y ′ from A ′ , then the duplicator chooses a vertex y from A.

Stage 3 The spoiler and the duplicator play an ordinary d-round Ehrenfeucht game on the structures N r (y), x 1 , . . . , x l and N r (y ′ ), x ′ 1 , . . . , x ′ l . Here N r (y), x 1 , . . . , x l denotes the structure that is induced by S r (y) and x and has x 1 , . . . , x l and y as distinguished elements. The spoiler wins the game if he wins the game of stage 3 in the usual sense. Otherwise, the duplicator wins. 1. C is first-order definable.

2. For some l, r and d, the spoiler has a winning strategy in the local FO Ehrenfeucht game on C with parameters l, r and d.

3. There exists a set H of Hintikka-types such that, for some l, r and d, for every σ-structure A it holds that A ∈ C if and only if there exist x 1 , . . . ,

x l ∈ A with {H d ( N r (y), x 1 , . . . , x l ) | y ∈ U A } ⊆ H.
Proof.

(1) =⇒ ( 2): If C is first-order definable, by Theorem 3.2, there is a formula ∃x 1 , . . . , x l ∀yϕ that characterizes the structures of C. Furthermore ϕ is basic r-local around x, y, for some r.

Let d denote the quantifier-depth of ϕ. It follows in a straightforward manner that the spoiler has a winning strategy in the local first-order Ehrenfeucht game on C with parameters l, r and d (compare with [START_REF] Ajtai | Reachability is harder for directed than for undirected finite graphs[END_REF]).

(2) =⇒ (1): From a winning strategy of the spoiler in the local first-order Ehrenfeucht game on C with parameters l, r and d one can easily derive a winning strategy in the ordinary (l+1+r+d)round Ehrenfeucht game on C. The spoiler simply plays l + 1 + r rounds according to his winning strategy in the local game. The additional d rounds assure that the spoiler immediately has a win if, in stage 3, the duplicator does not play in the d-neighbourhoods of y and y ′ .

(1) =⇒ (3): This follows immediately from Theorem 3.3.

(3) =⇒ (1): This holds because Hintikka-types can be described by first-order formulas.

The local FO Ehrenfeucht game can be easily adapted for the case of monadic Σ 1 1 -logic. The resulting game has one additional parameter m. In stage 1 of the local monadic Σ 1 1 Ehrenfeucht game the spoiler chooses, before the duplicator chooses A ′ , unary relations X 1 , . . . , X m and vertices x 1 , . . . , x l in A and the duplicator has to choose corresponding relations X ′ 1 , . . . , X ′ m and vertices x ′ 1 , . . . , x ′ l in A ′ . Theorem 4.2 Let C be a class of σ-structures. The following are equivalent.

1. C is monadic Σ 1 1 definable. 2.
For some m, l, r and d, the spoiler has a winning strategy in the local monadic Σ 1 1 Ehrenfeucht game on C with parameters m, l, r and d.

3. There exists a set H of Hintikka-types such that, for some m, l, r and d, for every σstructure A it holds that A ∈ C ⇐⇒ there exist unary relations X 1 , . . . , X m and elements x 1 , . . . , x l

with {H d ( N r (y), X 1 , . . . , X m , x 1 , . . . , x l ) | y ∈ U A } ⊆ H .
The proof is an easy generalization of the proof of Theorem 4.1.

In a similar manner one can derive respective games from Theorem 3.4. Although we have not used Theorems 4.1 and 4.2 to derive any new inexpressibility results we are optimistic that the local Ehrenfeucht games will turn out to be a useful tool to get such results. One indication in this direction is the fact that many of the inexpressibility proofs that are given in the literature can be proved by using these games (e. g. [START_REF] Fagin | On monadic NP vs. monadic co-NP[END_REF][START_REF] Schwentick | Graph connectivity, monadic NP and built-in relations of moderate degree[END_REF]).

One particular example is the proof of Ajtai and Fagin [START_REF] Ajtai | Reachability is harder for directed than for undirected finite graphs[END_REF], which has already been simplified by Arora and Fagin in [START_REF] Arora | On winning strategies in Ehrenfeucht-Fraïssé games[END_REF]. In both of these proofs the notion of the (r, d)-colour of a vertex or an edge is used. As the graphs that were used in those proofs do not contain small cycles all r-spheres are rooted trees. The definition assures that if two vertices have the same (r, d)-colour their r-neighbourhoods have the same d-Hintikka-type. As in the construction of [START_REF] Ajtai | Reachability is harder for directed than for undirected finite graphs[END_REF] both structures have exactly the same multisets of (r, d)-colours Theorem 4.2 implies their result. It should be noted that the additional choice of vertices x 1 , . . . , x l does not make the construction of the graphs more difficult, as they can almost be treated like l additional unary relations with the proviso that each of these colours appears in every graph exactly once.

Automata

The conditions (3) of Theorems 4.1 and 4.2 give rise to a generalized form of automata. In this section we are going to introduce automata models for FO logic and monadic Σ 1 1 logic, respectively. Vaguely similar machine models are known for relational databases [START_REF] Leivant | Descriptive characterizations of computational complexity[END_REF][START_REF] Gemis | A computational model for generic graph functions[END_REF][START_REF] Abiteboul | Computing with first-order logic[END_REF]. Informally the FO automaton works as follows. First it nondeterministically pebbles vertices b 1 , . . . , b g of its input structure A, for some g. Then, for every vertex a of A, it inspects in a constant number of steps (alternating between nondeterminism and parallelism) the neighbourhood of a. Navigation through the neighbourhood is only along edges.

We now define the model more formally. Let σ be a relational signature. A first-order σ-automaton M consists of a tuple (g, l, I, ϕ), where g ≥ 0 is the size of the global read-only store, l ≥ 0 is the size of the local store, I is a finite sequence of instructions and ϕ is a test. The store will hold a vector of (pointers to) elements of the structure. Instructions are of the form any i, j or all i, j , where 1 ≤ i, j ≤ l. The test is a quantifier-free formula with variables from x 1 , . . . , x l , y 1 , . . . , y g . A configuration (J, b, a) consists of a (possibly empty) sequence J of instructions yet to be executed and the contents b and a of the global and local store, respectively. Let b ∈ A l and v ∈ A. A configuration tree of M for b and v is defined as follows. It is a rooted tree, directed from the root to the leaves, and has configurations of M as vertices. It has the start configuration (I, b, v l ) as its root. The leaves are terminal configurations (ε, b, a). An inner vertex (ιJ, b, a) has

• one child (J, b, a ′ ), where a ′ j is a i or a neighbour of a i and a ′ k = a k for every k = i, if ι is any i, j , and

• all children (J, b, a ′ ), where a ′ j is a i or a neighbour of a i and a ′ k = a k for every k = i, if ι is all i, j . A terminal configuration (ε, b, a) is accepting, if A, a, b |= ϕ(x,
y), otherwise rejecting. A configuration tree is accepting, if all its leaves are accepting. We say that M accepts A if there is a b ∈ A g such that for every v ∈ A there is an accepting configuration tree of M with b and a.

A monadic Σ 1 1 σ-automaton similarly consists of a tuple (Q, g, l, I, ϕ), where g, l, I, ϕ are as before and Q is a finite set of states. It starts by nonterministically selecting a mapping f : U A → Q (represented by unary relations F q , one for each q ∈ Q). Afterwards it continues like the FO automaton (where the input structure is extended by the F q ). Theorem 5.1 A class of σ-structures is first-order definable if and only if it is accepted by a first-order σ-automaton.

Proof. "only if": By Theorem 3.3, C can be defined by a ∃ * ∀-local formula ∃x 1 , . . . , x g ∀yψ (without free variables), where ψ is in prenex normal form with d quantifiers (r-local around y) numbered from left to right with 1, . . . , d. Let l = d + 1 and let I consist of the subsequences J 1 , . . . , J d , where

• J i is any l, i followed by r -1 times any i, i (nondeterministic choice of an element of distance ≤ r from a) if the i-th quantifier is existential, and

• J i is all l, i followed by r -1 times all i, i otherwise.

ϕ is the quantifier-free part of ψ. "if": Consider an automaton (g, l, I, ϕ). We use one variable y i for each of the l local pointers. We assign inductively a formula ψ J to every suffix J of I as follows:

• ψ ε ≡ ϕ
• ψ ιJ ≡ ∃y((δ(y i , y) ≤ 1) ∧ ∃y j ((y j = y) ∧ ψ J )) if ι is any i j . (The extra variable y ensures that this construction also works for i = j.)

• ψ ιJ ≡ ∀y((δ(y i , y) ≤ 1) ∧ ∀y j ((

y j = y) ∧ ψ J )) if ι is all i j .
The acceptance condition is then equivalent to ∃x 1 , . . . , x g ∀y∃y 1 , . . . , y l ( 1≤m≤l (y m = y) ∧ ψ I ) .

Corollary 5.2 A class of σ-structures is monadic Σ 1 1 definable if and only if it is accepted by a monadic Σ 1 1 automaton. For structures of bounded degree, the monadic Σ 1 1 automata generalize those of Thomas [START_REF] Thomas | On logics, tilings and automata[END_REF][START_REF] Thomas | Elements of an automata theory over partial orders[END_REF][START_REF] Thomas | Automata theory on trees and partial orders[END_REF]. In this case a Hintikka-type of a small neighbourhood boils down to an isomorphism type, called tile. The automata of Thomas check that each vertex possesses a neighbourhood of one among a finite number of allowed isomorphism types. Moreover, some of them must occur at least a certain number of times and others at most a certain number of times. (This is the remainder of Hanf's condition, from which it is actually derived.) Inspecting Theorem 3.3 again with this in mind, one finds that ϕ describes all admissible tiles, while the center y runs over all vertices. The variables x are used to distinguish a finite number of vertices. It is therefore clear that it suffices to require that some tiles (namely those with a center in x) occur exactly once. Moreover, for structures with a connected Gaifman graph, Theorem 3.4 implies that one occurrence constraint of this form suffices.

We would also like to compare monadic Σ 1 1 automata to the algebraic automata introduced by Courcelle [START_REF] Courcelle | The monadic second-order logic of graphs. I. recognizable sets of finite graphs[END_REF]. On general finite relational structures these automata are very powerful. They capture MSO logic with a built-in linear order [START_REF] Courcelle | The monadic second-order logic of graphs VII: Graphs as relational structures[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs X: Linear orderings[END_REF]. And on grids, for example, this inclusion is strict. More suitable for a comparison are sets of unordered, unranked trees, which we simply call trees in the sequel. On these structures, the recognizing power of algebraic automata is exactly the same as definability in monadic Σ 1 1 logic with a built-in linear order, as will be shown below. Hence the difference between algebraic automata and monadic Σ 1 1 automata corresponds to the difference between monadic Σ 1 1 with and without a built-in linear order, two logics which have different expressive power [START_REF] Courcelle | The monadic second-order logic of graphs. I. recognizable sets of finite graphs[END_REF]. (For example, the linear order allows to count branches.) That such a linear order comes into play on an intentionally unordered structure is obviously due to the fact that trees must be encoded as terms before they are input to an automaton. The parallel inspection of local neighbourhoods in monadic Σ 1 1 automata avoids such side-effects. This is remarkable because Theorem 3.4 (b) applies and ensures that monadic Σ 1 1 automata do not need a global store in this case. Therefore, global information about a tree can be collected at the root without referring to some arbitrary order.

We now introduce trees and algebraic automata more formally. (Compare [START_REF] Courcelle | The monadic second-order logic of graphs. I. recognizable sets of finite graphs[END_REF].) A tree contains a distinguished vertex, its root. Edges are directed from the root to the leaves. They carry labels from a finite set L E . Vertices are labelled with sets of elements from a finite set L V . There is no a priori upper bound on the degree of a vertex. In particular, the degree of a vertex is not determined by its labelling. The class of trees (up to isomorphism) over L V , L E can be obtained inductively as follows. A few simple trees are assumed to be given. They consist solely of their root, which can be unlabelled or carry a label l ∈ L V . We denote these one-vertex trees by constants 1 and l, respectively. Then certain operations allow to construct new trees out of one or two others. For every label l ∈ L E there is a unary operation l adding to its argument a new (unlabelled) root and an l-labelled edge to the old root. Finally, a binary operation • glues its arguments at their roots, taking the union of their respective sets of root labels. It is easy to see that these operations can generate all trees and only those. In general, there is more than one way to obtain a particular tree.

An algebraic automaton recognizing a set of trees is an ordinary deterministic tree automaton working on the inductive representations of the trees (their derivation trees with respect to a grammar generating all trees). It is required that it accepts or rejects a tree independently of its representation, that is, all runs on different representations of the same tree produce the same answer. (Because logical formulas are also compatible to these inductive representations, algebraic automata are useful to obtain decision procedures.) Formally, an algebraic automaton consists of a finite set A = {1, . . . , m} of states, a transition function δ :

({1} ∪ L V ∪ { l | l ∈ L E } × A ∪ A × {•} × A) → A
and a subset F ⊆ A of accepting states. δ turns A into an algebra with respect to the tree-building operations: We write t for δ(t), t ∈ {1} ∪ L V , l(a) for δ( l, a), and a 1 • a 2 for δ(a 1 , •, a 2 ). The information contained in all the possible runs of the automaton can conveniently be expressed as a homomorphism from the set of all terms into A. We may assume that the homomorphism is surjective, that is, A does not contain superfluous states. Therefore, because results do not depend on representations, A is a commutative monoid with respect to • and has 1 as its neutral element. Moreover, l • l = l for every l ∈ L V . For all a 1 , . . . , a n ∈ A, n ≥ 0, the value of n i=1 a i only depends on the "Parikh image"

a 1 • • • a n ∈ N m , where the ith component is |{k | a k = i}|. This means that there is a mapping f : N m → A such that n i=1 a i = f ( a 1 • • • a n ).
Theorem 5.3 A set of trees is recognizable (by algebraic automata) if and only if it is definable in monadic Σ 1 1 logic with the help of a built-in linear order. That is, we consider monadic Σ 1 1 formulas which may use a linear order on the vertices of a tree but must remain invariant if the linear order is replaced with a different one.

We adapt the proof in [START_REF] Courcelle | The monadic second-order logic of graphs. I. recognizable sets of finite graphs[END_REF], which started from slightly different operations and aimed at a slightly different statement. There is no substantial new idea, only the defining formula has a more restricted form. Proof. The only-if part was shown in [START_REF] Courcelle | The monadic second-order logic of graphs VII: Graphs as relational structures[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs X: Linear orderings[END_REF]. Since our operations are derivable from the general (so-called quantifier-free definable) operations on graphs [START_REF] Courcelle | The monadic second-order logic of graphs VII: Graphs as relational structures[END_REF], a tree which is recognizable as a graph is a fortiori recognizable with respect to tree operations. For the if-part consider a tree T with set of vertices V , set of edges E ⊆ V × V and root r. Let V l ⊆ V be the set of vertices labelled with l ∈ L V , and let E l ⊆ E be the set of vertex pairs which are connected by an edge labelled with l ∈ L E . We write T v for the subtree of T rooted at v ∈ V . Of course, T r = T . We determine a mapping ∂ : V → A inductively, moving from the leaves to the root. Since we can choose the representation of T such that

T v = l∈L V v∈V l l • l∈L E v ′ ∈V (v,v ′ )∈E l l(T v ′ ) ,
we have

∂(v) = l∈L V v∈V l l • l∈L E v ′ ∈V (v,v ′ )∈E l l(∂(v ′ )) = l∈L V v∈V l l • f ( l(∂(v ′ )) | l ∈ L E , v ′ ∈ V, (v, v ′ ) ∈ E l ) . ( * )
Acceptance of T is equivalent to the existence of ∂ satisfying ( * ) and the condition ∂(r) ∈ F . This can be expressed in monadic Σ 1 1 logic with the help of a built-in linear order. As usual, the existence of pairwise disjoint sets X i = ∂ -1 (i), i ∈ A, is required. Besides that, each set v∈Xi Y i,v , i ∈ A, where

Y i,v = {v ′ ∈ X j | j ∈ A, (∃l ∈ L E ) ((v, v ′ ) ∈ E l ∧ l(j) = i)}
is partitioned into q i sets such that they can be used (together with the built-in linear order) to determine the cardinality of Y i,v modulo q i for every v ∈ X i . For suitable q i ≥ 1, i ∈ A, this is enough to compute f , hence express ( * ).

For every a ∈ A, the sequence a 0 , a 1 , a 2 , . . . becomes ultimately periodic. Let p a ≥ 0, q a ≥ 1 be the smallest values such that a pa = a pa+qa . It is easy to see that f -1 (a) is a finite union of sets of the form {(n 1 , . . . , n m ) ∈ N m | n i = pi + k i qi , k i ≥ 0} with pi , qi ≥ 0. More precisely, for each i ∈ A independently, either pi < p i and qi = 0, or p i ≤ pi < p i + q i and qi = q i . Therefore, f -1 (a) can be described by a first-order formula for every a ∈ A.

Conclusion

We introduced a normal form for first-order logic that formalizes the intuition that this logic is only able to express properties of the form "there are some important parts of the structure that fulfil given conditions and everywhere else nothing forbidden happens". Although our normal forms are mainly useful when structures of unbounded diameter are considered (otherwise the whole structure is contained in the neighbourhood of all of its vertices and local formulas are just general first-order formulas) their translation into the language of automata gives uniform means of evaluating first-order properties "along the edges" of structures. On the other hand it is applicable to structures of unbounded degree, even in situations where the Hanf argument does not work.

Our main open question is whether the normal forms have other meaningful applications and to find new inexpressibility results with the help of the simplified games. Another question is whether automata models can be designed that inspect the neighbourhoods of vertices in a more deterministic fashion.

  U A and edges between vertices a and b whenever a and b occur in a common tuple of a relation of A. The distance δ(a, b) of the vertices a and b of A is given by their (standard graph) distance in the Gaifman graph of A. For a tuple b = b 1 , . . . , b l of vertices of A we define δ(a, b) := min{δ(a, b i ) | i ≤ l}. For a tuple b = b 1 , . . . , b l of vertices of A and r ≥ 0 we define S r (b) := {a ∈ U A | δ(a, b) ≤ r}. We let N r (b) (resp. N r (a), for a = a 1 , . . . , a l ) denote the substructure of A which is induced by the vertices of S r (b) (resp. S r (a)) and has b (the a i ) as distinguished elements.

Theorem 4. 1

 1 Let C be a class of σ-structures. The following are equivalent.

Acknowledgements

This investigation was inspired by a talk that was given by Wolfgang Thomas in Mainz in December 1996. We would like to thank him, Clemens Lautemann, Juha Nurmonen, Ron Fagin for many fruitful discussions and suggestions. Thanks also to the anonymous referees.


Elena Barcucci

Alberto Del Lungo
email: dellungo@dsi.unifi.it

Elisa Pergola

Renzo Pinzani
email: pinzani@dsi.unifi.it

Permutations avoiding an increasing number of length-increasing forbidden subsequences

Keywords: Permutations, Forbidden subsequences, Catalan numbers, Schröder numbers

A permutation is said to be ✁ -avoiding if it does not contain any subsequence having all the same pairwise com- parisons as ✁ . This paper concerns the characterization and enumeration of permutations which avoid a set ✂ ☎✄ of subsequences increasing both in number and in length at the same time. Let ✂ ✄ be the set of subsequences of the form "✆ ✞✝ ✠✟ ☛✡ ✌☞ ✎✍ ✏✝ ✠✟ ✑✡ ✓✒ ✔✍ ", ✆ being any permutation on ✕ ✖☞ ✘✗ ✚✙ ✛✙ ✛✙ ✛✗ ✜✟ ✣✢ . For ✟ ✥✤ ✦☞ the only subsequence in ✂ ★✧ is ☞ ✎✒ ✪✩ and the ☞ ✎✒ ✪✩ -avoiding permutations are enumerated by the Catalan numbers; for ✟ ✫✤ ✬✒ the subsequences in ✂ ☛✭ are ☞ ✚✒ ✔✩ ✪✮ , ✒ ✣☞ ✯✩ ✔✮ and the (☞ ✎✒ ✔✩ ✪✮ ✰✗ ✱✒ ✲☞ ✚✩ ✔✮ ✖✍ -avoiding permutations are enumerated by the Schröder numbers; for each other value of ✟ greater than ✒ the subsequences in ✂ ✄ are ✟ ✰✳ and their length is ✝ ✠✟ ✴✡ ✵✒ ✘✍ ; the permutations avoiding these ✟ ✰✳ subsequences are enumerated by a number sequence ✕ ✎✶ ✰✷ ✸✢ ✷ ✣✹ ✧ such that ✺ ✻✷ ✽✼ ✾✶ ✿✷ ✫✼ ✾❀ ❁✳ , ✺ ✻✷ being the ❀ -th Catalan number. For each ✟ we determine the generating function of permutations avoiding the subsequences in ✂ ❂✄ , according to the length, to the number of left minima and of non-inversions.

Introduction

The study of permutations represents an interesting and relevant discipline in Mathematics which began with Euler who first analyzed permutation statistics related to the study of parameters different from their length [START_REF] Euler | Institutiones calculi differentialis[END_REF]. MacMahon in [START_REF] Macmahon | Combinatory Analysis[END_REF] further developed this vast field but meaningful progress has been only made in the last thirty years.

Recently, the new problems coming from Computer Science led to the development of the concept of permutations with forbidden subsequences. They arise in sorting problems [START_REF] Bousquet-Mélou | Multi-statistic enumeration of two-stack sortable permutations[END_REF][START_REF] Knuth | The art of computer programming[END_REF][START_REF] Rotem | Stack sortable permutations[END_REF][START_REF] West | Permutations with forbidden subsequences and stack-sortable permutations[END_REF][START_REF] West | Sorting twice through a stack[END_REF], in the analysis of regularities in words [START_REF] Berstel | Axel Thue's papers on repetitions in words: translation[END_REF][START_REF] Lothaire | Combinatorics and words[END_REF], in particular instances of pattern matching algorithms optimization [START_REF] Bose | Pattern matching for permutations[END_REF]; just to mention some examples. The enumeration of permutations with specific forbidden subsequences has also applications in areas such as Algebraic Geometry and Combinatorics. The ❃ ❅❄ ✪❆ ❈❇ - avoiding permutations, called vexillary permutations, are relevant to the theory of Schubert polynomials. In Combinatorics, permutations with forbidden subsequences play an important role as they present bijections with a great number of non-trivial combinatorial objects [START_REF] Cori | Shuffle of parenthesis systems and Baxter permutations[END_REF][START_REF] Dulucq | Permutations à motifs exclus et cartes planaires non séparables, Proceedings of ✗ ✟ ☎✄ FPSAC[END_REF][START_REF] Dulucq | Mots de piles, tableaux standards et permutations de Baxter[END_REF][START_REF] Gire | Arbres, permutations a motifs exclus et cartes planaires: quelques problemes algorithmiques et combinatoires[END_REF][START_REF] Guibert | Combinatoires des permutations a motifs exclus en liaison avec mots, cartes planaires et tableaux de Young[END_REF][START_REF] Goulden | Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations[END_REF] and moreover their enumeration gives rise to classical number sequences. The -th Catalan number is the common value of permutations with a single forbidden subsequence of length three [START_REF] Knuth | The art of computer programming[END_REF]. More precisely Knuth shows that ❇ ❄ ✘❃ -avoiding permutations are the one stack sortable permutations. The problem of avoiding more than one restriction was first studied by Simion and Schmidt [START_REF] Simion | Restricted permutations[END_REF] and they determined the number of permutations avoiding two or three subsequences of length three.

As far as forbidden subsequences of length four are concerned, new enumeration results concern the subsequence ❄ ✘❃ ✿❇ ✣❆ [START_REF] Gessel | Symmetric functions and P-recursiveness[END_REF], ❄ ✔❇ ✣❆ ✸❃ [START_REF] Bóna | Exact enumeration of ❄ ✔❇ ✿❆ ❈❃ -avoiding permutations; a close link with labelled trees and planar maps[END_REF] and all the ones behaving identically [START_REF] Babson | The permutations ❄ ✖❃ ✣❇ ✔ ✁ ✁ ✁ ✔ ✂✁ and ❇ ✰❃ ❅❄ ✔ ✂✁[END_REF][START_REF] Stankova | Forbidden Subsequences[END_REF][START_REF] West | Permutations with forbidden subsequences and stack-sortable permutations[END_REF], while for ❄ ✔❇ ❈❃ ✲❆ -avoiding permutations the only result is proved by Bóna in [START_REF] Bóna | Permutations avoiding certain patterns. The case of length 4 and some generalizations[END_REF] and it gives only a numerical lower bound. Permutations avoiding some couples of subsequences of length four give the Schröder numbers [START_REF] Guibert | Combinatoires des permutations a motifs exclus en liaison avec mots, cartes planaires et tableaux de Young[END_REF]; results concerning permutations avoiding more than one forbidden subsequence of length four exist; we refer to [START_REF] Guibert | Combinatoires des permutations a motifs exclus en liaison avec mots, cartes planaires et tableaux de Young[END_REF] for an exhaustive survey of the results available on permutations with forbidden subsequences.

Regarding permutations avoiding a single subsequence of length greater than four the most important result solves the problem of one increasing subsequence of any length giving an asymptotic value of the number of permutations avoiding the subsequence ❄ ✂✁ ✄✁ ☎✁ ✆ ✞✝ ❄ [START_REF] Regev | Asymptotic values for degrees associated with strips of Young diagrams[END_REF]. In [START_REF] Chow | Forbidden subsequences and Chebyshev polynomials[END_REF] Chow and West study ✟ ❄ ✘❃ ✿❇ ✡✠ ✆ ✁ ☎✁ ✄✁ ✪❄ ✟ ✆ ☛✝ ❄ ✌☞ ✍☞ -avoiding permutations; their generating functions can be expressed as a quotient of modified Chebyshev polynomials and they give rise to number sequences lying between the well-known Fibonacci and Catalan numbers. In [START_REF] Barcucci | From Motzkin to Catalan permutations[END_REF] the authors study

✟ ❇ ❈❃ ❅❄ ✎✠ ✟ ✆ ✏✝ ❃ ✑☞ ✄✒ ❄ ✟ ✆ ✓✝ ❇ ✔☞ ❃ ✕✁ ☎✁ ✄✁ ✟ ✆ ✏✝ ❄ ✌☞ ✖☞ -avoiding
permutations where the latter forbidden subsequence means that the subsequence

✟ ✆ ✗✝ ❄ ✌☞ ✟ ✆ ✘✝ ❃ ✎☞ ✚❄ ✙✁ ✄✁ ✄✁ ✆ [that is ✟ ✆ ✘✝ ❃ ✑☞ ✟ ✆ ✘✝ ❇ ✑☞ ❃ ✚✁ ✄✁ ✄✁ ✆ ✘✝ ❄ restricted on ✛ ❈❄ ✎✠ ✄✁ ☎✁ ✄✁ ✜✠ ✆ ☛✝ ❃ ✣✢ ] is allowed only in the case it is part of a longer subsequence of type ✟ ✆ ✤✝ ❃ ✎☞ ✎❄ ✟ ✆ ✥✝ ❇ ✔☞ ❃ ✕✁ ☎✁ ✄✁ ✆ ✏✝ ❄ .
Their generating functions are algebraic and give rise to sequences of numbers lying between the well-known Motzkin and Catalan numbers involving the left-Motzkin factor numbers as a particular case.

A natural generalization of sequence avoidance is the restricted sequence inclusion. In this case a prescribed number of occurences of a sequence in the permutations is required. Noonan [START_REF] Noonan | The number of permutations containing exactly one increasing subsequence of length three[END_REF] and Bona [START_REF] Bona | Permutations with one or two 132-sequences[END_REF] determined a simple expression for the number of permutations containing exactly one 123, respectively one 132 sequence. Robertson [START_REF] Robertson | Permutations Containing and Avoiding 123 and 132 Patterns[END_REF] proved that the number of ❄ ✖❃ ✣❇ -avoiding permutations containing exactly one 132 sequence is given by ✟ ✧✦ ❃ ✎☞ ✱❃ ✑★ ✪✩ ✬✫ . There are some other recent interesting results. Robertson, Wilf and Zeilberger [START_REF] Robertson | Permutation Patterns and Continued Fractions[END_REF] express the generating function for the number of ❄ ✔❇ ✰❃ -avoiding permutations which have a given number of 123 sequences in form of a continued fraction. Mansour and Vainshtein [START_REF] Mansour | Restricted permutations, continued fractions, and Chebyshev polynomials[END_REF] extend the previous result to determine the generating function of the number of 132-avoiding permutations having a given number of ❄ ✘❃ ✚✁ ✄✁ ✄✁ ✆ sequences. Mansour [START_REF] Mansour | Permutations avoiding a set of patterns from ✰ ✫ and a pattern from ✰[END_REF] studies the permutations avoiding a sequence of length four and a nonempty set of sequences of length three. Mansour [START_REF] Mansour | Permutations containing and avoiding certain patterns[END_REF] provides a simple espression for the number of permutations which avoid all the sequences of ✛ ✌✭ ✯✮ ✱✰ ✳✲ ✗✴ ✵✭ ✌✶ ✸✷ ✺✹ ✻✢ (i.e., the sequences of length

✆

having the first element equal to ✹ ). Moreover, he gives a generalization of Robertson's result.

In this paper, we continue this line of research in counting permutations which avoid a set of restrictions. We study a case which is similar to the problem studied by Mansour [START_REF] Mansour | Permutations containing and avoiding certain patterns[END_REF], that is the set of permutations which avoid all the sequences of ✛ ☎✭ ✼✮ ✽✰ ✿✾ ✖❀ ❂❁ ✤✴ ❃✭ ❃✾ ✖❀ ❄✶ ✥✷ ❆❅ ✝ ❄ ✑✠ ❇✭ ❃✾ ✖❀ ❇❁ ✥✷ ❈❅ ✝ ❃ ✣✢ .

Section 2 of this paper contains the basic definitions about permutations with forbidden subsequences. In Section 3, we describe the tools used to obtain the enumerative results, which are succession rules and generating trees. The former ones consist of rules describing the growing behavior of an object with a fixed parameter value, the latter ones are schematic representations of the former. In Section 4, we express the permutations we are studying in terms of succession rules. We translate the construction, represented by the generating tree, into formulae, thus obtaining a set of functional equations. Their solution gives the generating function of the permutations according to the length, number of left minima, non-inversions and active sites. We are able to determine the generating function according to the length of the permutations, number of left minima and non-inversions. This result allows us to show that the generating function is algebraic of degree two, except for ❅ ✘✷ .

Notations and definitions

In this section we recall the basic definitions about permutations with forbidden subsequences that will be referred to in the next sections.

A permutation ✁ ✷ ✂✁ ✟ ✭ ✌✶ ✠ ☎✁ ✄✁ ✄✁ ☎✠ ✍✭ ★✧ ✎☞ . We call the family ✬ ✷ ✛ ☎✭ ✶ ✠ ☎✁ ✄✁ ☎✁ ✄✠ ✍✭ ✔✧ ✪✢ a family of forbidden subsequences, the set ✰ ★ ✟ ✬ ✓☞ a family of permutations with forbidden subsequences and ✭ ★ ✄✮ ✶ ✰ ★ ✟ ✬ ✓☞ a class of permutations with forbidden subsequences.

Given ✁ ✮ ✧✰ ★ , we call the position on the left of ✁ ✟ ❄ ☞ position ✯ , the position between ✁ ✟ ✠ ☞ and ✁ ✟ ✠ ✝ ❄ ✌☞ , ❄ ✰✞ ✱✠ ✲✞ ✼✦ ❄ , position ✠ , and the position on the right of ✁ ✟ ☞ , position . We will refer to any of these positions as the sites of ✁ .

Definition 2.1 Let ✬ ✷ ✛ ✄✭ ✶ ✠ ☎✁ ✄✁ ✄✁ ☎✠ ✍✭ ★✧ ✪✢ . The position ✠ , ✯ ✳✞ ✴✠ ✵✞ , of a permutation ✁ ✮ ✯✰ ★ ✟ ✬ ✓☞ is an active site if the insertion of ✝ ❄ into position ✠ gives a permutation belonging to the set ✰ ★ ❀ ❄✶ ✟ ✬ ✓☞ ;
otherwise it is said to be an inactive site.

Example 2.2

The permutation ✁ ✷ ✡✖ ❄ ✪❆ ✘✗ ✘✙ ✲❇ ❈❃ ✮ ❆✰ ✛ ✟ ❃ ✣❆ ❄ ✔❇ ✔☞ has ✗ active sites (the positions ✯ , ❆ , ✗ , ✖ and ✙ ) and ❇ inactive sites (the positions ❄ , ❃ and ❇ ) as ✖ ❄ ✪❆ ✄✗ ✷✶ ✄✙ ✲❇ ✰❃ ✞✮ ✰ ✜✸ ✟ ❃ ✣❆ ❄ ✘❇ ✑☞ while ✖ ❄ ✹✶ ✣❆ ✄✗ ✚✙ ✣❇ ✰❃ ✻✺ ✮ ✰ ✼✸ ✟ ❃ ✣❆ ❄ ✔❇ ✔☞ , just to give an example.

Definition 2.2 Let ✁ ✮ ✰ ★ . The pair of indices ✟ ✠ ❃✠ ❅ ✪☞ , ✠ ✑ ❅ , is a non-inversion if ✁ ✟ ✠ ☞ ✑ ✁ ✟ ❅ ✔☞ ✜✁ An element ✁ ✟ ✠ ☞ is a left minimum if ✁ ✟ ✠ ☞ ✑ ✁ ✟ ❅ ✪☞ , ✽ ✣❅ ✗✮ ☎ ❄ ✑✠ ✕✠ ✦ ❄ ✆ . Example 2.3 The permutation of Example 2.2 has ✾ non-inversions: ✟ ❄ ✑✠ ✿✗ ✑☞ ✟ ❃ ✡✠ ✱❇ ✔☞ ✟ ❃ ✡✠ ❆ ✪☞ ✟ ❃ ✡✠ ✿✗ ✑☞ ✟ ❃ ✡✠ ✓✖ ✔☞ ✟ ❃ ✣✠ ✔✙ ✵☞ ✟ ❇ ✡✠ ✱❆ ✔☞ ✟ ❇ ✡✠ ★✗ ✎☞ ✟ ❆ ✠ ★✗ ✎☞ and ❃ left minima: ✁ ✟ ❄ ☞ ✂✷ ❀✖ and ✁ ✟ ❃ ✎☞ ✂✷ ❄ .

Succession rules and generating trees

In this section we briefly describe the tools used to deduce our enumerative results, namely succession rules and generating trees. They were introduced in [START_REF] Chung | The number of Baxter permutations[END_REF] for the study of Baxter permutations and further applied to the study of permutations with forbidden subsequences by West [START_REF] Chow | Forbidden subsequences and Chebyshev polynomials[END_REF][START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF][START_REF] West | Generating trees and forbidden subsequences[END_REF]. Definition 3.1 A generating tree is a rooted, labelled tree such that the labels of the set of children of each node v can be determined from the label of v itself. Thus, any particular generating tree can be specified by a recursive definition consisting of:

1. basis: the label of the root,

inductive step: a set of succession rules that yields a multiset of labelled children depending solely on the label of the parent.

A succession rule contains at least the information about the number of children. Let ✭ be a forbidden subsequence. Following the idea developed in [START_REF] Chung | The number of Baxter permutations[END_REF], the generating tree for ✭ -avoiding permutations is a rooted tree such that the nodes on level are exactly the elements of ✰ ★ ✟ ✭ ☞ ; the children of a permutation

✁ ✷ ❀✁ ✟ ❄ ☞ ✿✁ ✄✁ ☎✁ ✕✁ ✟
☞ are all the ✭ -avoiding permutations obtained by inserting ✝ ❄ into ✁ . Labels must be assigned to the nodes and they record the number of children of a given node.

Example 3.1 The Catalan tree and ❄ ✘❃ ✿❇ -avoiding permutations are obtained by the succession rule:

✂✁ ☎✄ ✝✆ ✠ ✆ ✟✞ ✟ ❃ ✎☞ ✠ ✡✠ ☞☛ ✍✌ ☎✎ ✠ ✑✏ ✓✒ ✆ ✎ ✒ ✕✔ ✞ ✟ ✆ ☞ ✗✖ ✟ ✆ ☛✝ ❄ ☞ ✟ ❃ ✎☞ ✿✁ ☎✁ ✄✁ ✟ ✆ ☞ ✁ (3.1)
The permutation of length one has two active sites (basis in rule

(3.1)). Let ✁ ✷ ✁ ✟ ❄ ✌☞ ✁ ✁ ✁ ✁ ✟ ☞ ✚✮ ✻✰ ★ ✟ ❄ ✘❃
✘ ✙ ✚ ✁ ☎✄ ✝✆ ✠ ✆ ✟✞ ✟ ❃ ✑☞ ✠ ✡✠ ✛☛ ✜✌ ☎✎ ✠ ✑✏ ✓✒ ✆ ✎ ✒ ✕✔ ✞ ✟ ❃ ✑☞ ✢✖ ✟ ❇ ✔☞ ✟ ❇ ✔☞ ✠ ✡✠ ✛☛ ✜✌ ☎✎ ✠ ✑✏ ✓✒ ✆ ✎ ✒ ✕✔ ✞ ✟ ✆ ☞ ✢✖ ✟ ✆ ✓✝ ❄ ✌☞ ✟ ✆ ☛✝ ❄ ☞ ✟ ❇ ✔☞ ✿✁ ✄✁ ☎✁ ✟ ✆ ☞ ✠ ✆ ✤✣ ❇ ✁ (3.2)
The permutation of length one has two active sites (basis in rule

(3.2)). Let ✁ ✧✷ ❀✁ ✟ ❄ ✌☞ ✜✁ ✁ ✁ ✁ ✟ ☞ ✚✮ ✰ ★ ✟ ❄ ✖❃ ✣❇ ✣❆ ✠ ❃ ❅❄ ✔❇ ✿❆ ✔☞ ; and let ✆ , ❇ ✞ ✆ ✞ , be the minimum index in ✁ such that there exist ✠ ✶ ✑ ✠ ❁ ✑ ✆ for which ✁ ✟ ✠ ✍✶ ✜☞ ✏✁ ✟ ✠ ❁ ✌☞ ✏✁ ✟ ✆ ☞ is of type ❄ ✖❃ ✣❇ ,
2 -3 -1 - (4) (3) -2 -1 -3 -2 -1 - (3) -1 - (2) -4 -3 -2 -1 - -3 -2 -1 -4 -3 -2 -4 1 -3 -2 -1 - (4) -3-4 -2 -1 - -4 -2 -3 -1 - -2 -4 -3 -1 - (5) (5) (3) (4) (5) (5) -2 -3 -4 1 -2 -3 -1 -4 (4) (3) -4 -2 -1 -3 -2 -1 -4 3 -2 -4 -1 -3 -4 -3 -1 -2 - (4) (4) (3) (5) (5) (3) -3 -1-4 2 -3 -1 -2 -4 (4) -4 -1 -3 -2 - (5) -1 -4 -3 -2 - -1 -3 -4 2 (3) (4) -4 -1 -2 -3 (4) -1 -4 -2 -3 (4) -1 -2 -4 3 (3) -3 -4 -1 -2 - -3 -1 -2 - (4) -1 -3 -2 - (4) -1 -3 -2 -4 -1 -2 -3 (3) (5) (3) -1 -2 -
✙ ✚ ✚ ✚ ✛ ❄ ✯ ✜ ✢✜ ✢✜ ✯ ✯ ✯ ✯ ✜ ✢✜ ✢✜ ✯ ✯ . . . . . . ✯ ✯ ✜ ✢✜ ✢✜ ✯ ❄ ✣ ✢✤ ✤ ✤ ✥
with as many as ❅ ✽❄ 's appearing in both above and to the left of this structure.

These permutations are enumerated by number sequences such that the -th term is between the -th Catalan number and ✕ (see Figure 2). We describe the structure of their generating tree and use this construction to obtain a set of functional equations satisfied by the generating function of the class of permutations ✏ ✾ . Some computations allow us to determine this generating function according to the length of the permutations, number of left minima and non-inversions.

The generating tree for

✂✁ permutations

The class of permutations ✏ ✾ contains permutations avoiding configurations of the form ✁ ✄✁ ☎✁ ☎✄ ✓✁ ☎✁ ✄✁ ☎✆ ✥✁ ✄✁ ☎✁ such that ✄ ✑ ✆ and ✄ is preceded by at least ❅ elements all of them less than ✄ . As a matter of fact, the set Let ✁ ✮ ✰ ★ ✟ ✬ ✾ ☞ , ❅ ✣ ❄ , be a permutation with ✆ active sites, the positions ✯ ✡✠ ☎✁ ✄✁ ☎✁ ✜✠ ✆ ✦ ❄ , so there is

a sequence of indices ✠ ✶ ✠ ☎✁ ✄✁ ☎✁ ✄✠ ✕✠ ✾ ✖❀ ❄✶ ✷ ✆ such that ✠ ✶ ✑ ✜ ✢✜ ✢✜ ✑ ✠ ✾ ✑ ✆ and ✹ ✄ ✄ ✶ ✞✝ ✠✟ ✡✝ ✾ ✁ ✟ ✠ ✟ ☞ ✑ ✁ ✟ ✆ ☞ .

By inserting

✝ ❄ into the position ✠ , ✯ ✞ ✠ ✞ ❅ ✦ ❄ , we obtain a new permutation, ✁ ☞☛ , with ✟ ✆ ✘✝ ❄ ☞ active sites as the new element is not relevant to the existence of the sequence of indices ✠ ✶ ✠ ☎✁ ✄✁ ✄✁ ☎✠ ✕✠ ✾ ✠ ✕✠ ✾ ✖❀ ❄✶ , and the minimum index that gives such a sequence is ✟ ✆ ✝ ❄ ✌☞ as the . . (n+1) . . i = 0, . . . , j-1 i = j+1, . . . , k-1

✟ ✆ ✥✝ ❄ ☞ -th element of ✁ ☞☛ is equal to ✁ ✟ ✆ ☞ . By inserting ✝ ❄ into the position ✠ , ❅ ✞ ✠ ✞ ✆ ✦ ❄ ,
Π (n) . . . . . . . Π(k) Π(k+1) . . Π(k) Π(k+1) Π Π(1) Π(j) Π (n) . . . . . . Π(k) Π(k+1) 0 j-1 j k-1 Π Π(1) i Π Π(1) j (n+1) Π(k) Π(k+1) Π Π(1) i 0 i i+1 j k 0 j-1 j 0 j-1 j i
Fig. 3: The active sites in the children of .

The above arguments prove the following proposition:

Proposition 4.1 Let ✁ ✱✮ ✰ ★ ✒✑ ✬ ✾ ✓ ✠ ❅ ✣ ❄ ,
✍☛ is ✟ ✆ ✏✝ ❄ ✌☞ for ✯ ✞ ✠ ✞ ❅ ✦ ❄ and ✟ ✠ ✝ ❄ ☞ for ❅ ✞ ✠ ✞ ✆ ✦ ❄ .
The succession rule for the generating tree of ✏ ✾ permutations follows immediately:

✘ ✙ ✚ ✁ ☎✄ ✝✆ ✠ ✆ ✞ ✟ ❃ ✎☞ ✠ ✡✠ ☞☛ ✍✌ ☎✎ ✠ ✑✏ ✒ ✆ ✎ ✒ ✕✔ ✞ ✟ ✆ ☞ ✗✖ ✟ ✆ ☛✝ ❄ ☞ ✲ ✠ ✆ ✑ ❅ ✠ ✡✠ ☞☛ ✍✌ ☎✎ ✠ ✑✏ ✒ ✆ ✎ ✒ ✕✔ ✞ ✟ ✆ ☞ ✗✖ ✟ ✆ ☛✝ ❄ ☞ ✾ ✟ ❅ ✝ ❄ ✌☞ ✁ ✁ ✁ ✁ ✁ ✟ ✆ ☞ ✠ ✆ ✣ ❅ ✑✁ (4.3)
In a "Catalan permutation" ✁ a position ✠ , ✯ ✻✞ ✂✠ ✞ , is an active site if and only if there do not exist any ✠ ☛ ✑ ✠ ❁ ✞ ✠ such that ✁ ✟ ✠ ✍✶ ✜☞ ✑ ✁ ✟ ✠ ❁ ✌☞ ; in a "Schröder permutation" ✁ a position ✠ , ✯ ✞ ✠ ✞ , is an active site if and only if there do not exist any ✠ ✶ ✑ ✠ ❁ ✑ ✠ ✫ ✞ ✠ such that ✹ ✄ ✄ ☛✛ ✁ ✟ ✠ ✖✶ ✄☞ ✜✠ ✕✁ ✟ ✠ ❁ ☞ ❃✢ ✑ ✁ ✟ ✠ ✫ ☞ . By comparing these conditions with the definition of active site for a permutations ✁ ✮ ✏ ✾ ; we realise that the role of the parameter ❅ is to increase the length of the index sequence ✠ ✶ ✠ ☎✁ ✁ ✁ ✠ ✓✠ ✾ ✖❀ ❄✶ such that ✠ ✶ ✑ ✁ ✁ ✁ ✑ ✠ ✾ ✑ ✠ ✾ ✖❀ ❄✶ and each ✁ ✟ ✠ ✡✟ ✍☞ , ✎ ✷ ❄ ✎✠ ☎✁ ✁ ✁ ✠ ❅ , is smaller than ✁ ✟ ✠ ✾ ✖❀ ❄✶ ☎☞ . Observe that no constraint is required on the order of the elements of the set ✛ ✁ ✟ ✠ ✶ ✄☞ ✠ ☎✁ ✁ ✁ ✠ ✓✁ ✟ ✠ ✾ ☞ ✢ . Once the permutations in ✏ ✾ are established we are interested in the results concerning their enumeration.

The generating function

For each ❅ , we are interested in the generating function for the permutations in ✏ ✾ according to the length, number of left minima and non-inversions. Let ✁ ✯✮ ✏ ✾ ; we denote the length of ✁ by ✟ ✁ ❇☞ , the number of its left minima by ✹ ✟ ✁ ❇☞ , the number of its non-inversions by ✠ ✟ ✁ ❇☞ and the number of its active sites by ✄ ✟ ✁ ❇☞ . The generating function of ✏ ✾ according to the above mentioned parameters is the following:

✾ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✪✠ ✆ ☞ ✷ ☎✄ ✆ ✞✝ ✠✟ ☛✡ ✄ ★ ✌ ✆ ✎ ✆ ✌☞ ✌ ✆ ✎ ✁ ★ ☛ ✌ ✆ ✎ ✆ ☛✍ ✌ ✆ ✎ . From (4.
3) we deduce that a permutation ✁ ✮ ✘✏ ✾ is the father of ✄ ✟ ✁ ❇☞ permutations, namely ✁ ✏✎ ✑✠ ☎✁ ✁ ✁ ✠ ✁ ✍ ✌ ✆ ✎ ✩ ✶ in ✏ ✾ , obtained by inserting a new element into the positions ✯ ✡✠ ☎✁ ✄✁ ☎✁ ✜✠ ✄ ✟ ✁ ❇☞ ✦ ❄ which are active sites. If we look at the parameter changes in each permutation ✁ ☞☛ , ✯ ✞ ✠ ✞ ✄ ✟ ✁ ❇☞ ✦ ❄ , then we find:

a) if ✯ ✞ ✠ ✲✞ ✹ ✻✠ ✛ ✖❅ ✑✠ ✄ ✟ ✁ ❇☞ ❃✢ ✦ ❄ then: ✟ ✁ ✍☛ ☞ ✂✷ ✟ ✁ ❇☞ ✝ ❄ ✑✠ ✹ ✟ ✁ ✑✎ ✌☞ ✙✷ ✹ ✟ ✁ ❇☞ ✝ ❄ ✎✠ ✹ ✟ ✁ ✍☛ ☞ ✂✷ ✯✹ ✟ ✁ ❇☞ ✓✒ ✕✔ ✠ ✗✖ ✱✯ ✡✠ ✠ ✟ ✁ ✍☛ ☞ ✂✷ ✠ ✟ ✁ ❇☞ ✝ ✠ ❃✠ ✄ ✟ ✁ ✍☛ ☞ ✂✷ ✄ ✟ ✁ ❇☞ ✝ ❄ ✑✁ b) if ✹ ✻✠ ✛ ✖❅ ✑✠ ✄ ✟ ✁ ❇☞ ❃✢ ✞ ✠ ✞ ✄ ✟ ✁ ❇☞ ✦ ❄ then: ✟ ✁ ✍☛ ☞ ✂✷ ✟ ✁ ❇☞ ✝ ❄ ✑✠ ✹ ✟ ✁ ✍☛ ☞ ✂✷ ✯✹ ✟ ✁ ❇☞ ✠ ✠ ✟ ✁ ✍☛ ☞ ✂✷ ✠ ✟ ✁ ❇☞ ✝ ✠ ❃✠ ✄ ✟ ✁ ✍☛ ☞ ✂✷ ✠ ✝ ❄ ✑✁
The set ✏ ✾ can be partitioned into ❅ subsets: ✏ ✌ ✾ ✂✘ ❁ ✿✎ ✠ ✄✁ ☎✁ ✄✁ ☎✠ ✏ ✌ ✾ ✂✘ ✾ ✓✎ ✠ ✏ ✌ ✾ ✂✘ ✚✙ ✝✎ , where ✏ ✌ ✾ ✂✘ ✲ ✔✎ ✷ ✛ ✹✁ ✺✮ ✏ ✾ ✞ ✄ ✟ ✁ ❇☞ ✷ ✆ ✢ , ❃ ✻✞ ✆ ✞ ❅ , and ✏ ✌ ✾ ✛✘ ✚✙ ✎ ✷ ✢✜ ✚✁ ✮ ✏ ✾ ✞ ☞✄ ✟ ✁ ❇☞ ✣✖ ❅ ✥✤ . In terms of generating functions we obtain the decomposition:

✾ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✪✠ ✆ ☞ ✂✷ ✾ ✄ ✲ ✧✦ ❂❁ ✌ ✾ ✂✘ ✲ ✔✎ ✟ ✄ ❇✠ ✆ ✬✠ ✛✁ ✪✠ ✪❄ ☞ ✆ ✲ ✝ ✌ ✾ ✛✘ ✚✙ ✎ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✪✠ ✆ ☞ .
Let ✏ ✌ ✾ ✂✘ ✶ ✕✎ be the set representing the permutation of length ✯ . Observe that each permutation ✁ such that ✄ ✟ ✁ ❇☞ ✞ ❅ ✦ ❄ gives ✄ ✟ ✁ ❇☞ permutations with ✟ ✄ ✟ ✁ ❇☞ ✝ ❄ ☞ active sites; so ✏ ✌ ✾ ✂✘ ✲ ✔✎ is given by modifying ✏ ✌ ✾ ✂✘ ✲ ✩ ✶ ✏✎ , ❃ ✵✞ ✆ ✞ ❅ , and the parameter changes are described in a). This means that a permutation of ✏ ✾ having exactly ✆ ✞ ❅ active sites is just any permutation of length ✆ ✦ ❄ . Therefore each permutation ✁ such that ✄ ✟ ✁ ❇☞ ✣ ❅ gives ✄ ✟ ✁ ❇☞ permutations with at least ✟ ❅ ✝ ❄ ✌☞ active sites and the parameter changes are described in a) for the ❅ leftmost active sites and in b) for the remaining ones. By translating the above arguments into formulae we obtain:

✌ ✾ ✛✘ ✶ ✏✎ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✪✠ ✆ ☞ ✷ ✆ ✌ ✾ ✛✘ ✲ ✔✎ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✪✠ ✆ ☞ ✷ ✁ ✄ ✆ ✆ ✝ ✄✂ ✆☎ ✞✝ ☎ ✩ ✶ ✟ ✁ ✲ ✩ ❁ ✦ ❄ ✌☞ ✞✟ ✌ ✾ ✛✘ ✲ ✩ ✶ ✕✎ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✪✠ ✆ ☞ ✠ ❃ ✒✞ ✆ ✞ ❅ ✌ ✾ ✛✘ ✚✙ ✎ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✪✠ ✆ ☞ ✷ ✁ ✄ ✆ ✆ ✝ ✄✂ ✆☎ ✞✝ ☎ ✩ ✶ ✟ ✁ ✾ ✩ ✶ ✦ ❄ ✌☞ ✠✟ ✌ ✾ ✛✘ ✾ ✓✎ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✪✠ ✆ ☞ ✝ ✝ ✁ ✄ ✠✆ ✆ ✝ ✂ ✆☎ ✞✝ ☎ ✩ ✶ ✟ ✁ ✾ ✩ ✶ ✦ ❄ ✌☞ ✟ ✌ ✾ ✛✘ ✚✙ ✎ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✪✠ ✆ ☞ ✝ ✝ ✂ ✡✝ ✡ ☞☛ ✥ ☎ ✡ ✶ ✩ ✝ ✠☎ ✌ ✾ ✂✘ ✚✙ ✎ ✟ ✄ ❇✠ ✆ ✬✠ ✛✁ ✪✠ ✪❄ ☞ ✦ ✂ ✆✝ ✶ ✩ ✝ ✞☎ ✌ ✾ ✛✘ ✚✙ ✎ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✪✠ ✆ ✁ ✵☞ ✁
Using the standard notation for the ✁ -analogue of the number ✠ :

☎ ✠ ✆ ☎ ✷ ✶ ✩ ☎ ✠✌ ✶ ✩ ☎ ,
✾ ✟ ✄ ❇✠ ✆ ✿✠ ✂✁ ✪✠ ✆ ☞ ✙✷ ✾ ✍ ☛ ✦ ❂❁ ✌ ✾ ✂✘ ☛ ✎ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✪✠ ✆ ☞ ✝ ✌ ✾ ✂✘ ✚✙ ✎ ✟ ✄ ❇✠ ✆ ✬✠ ✛✁ ✪✠ ✆ ☞ ✠
where:

✌ ✾ ✛✘ ✶ ✏✎ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✪✠ ✆ ☞ ✷ ✆ ✌ ✾ ✛✘ ✲ ✔✎ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✪✠ ✆ ☞ ✷ ✄ ✲ ✩ ✶ ✆ ✲ ✆ ✲ ✩ ❁ ✎ ☛ ✦ ❄✶ ✟ ✆ ✝ ✁ ☎ ✠ ✆ ☎ ☞ ✿✠ ❃ ✵✞ ✆ ✞ ❅ ✌ ✾ ✛✘ ✚✙ ✎ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✪✠ ✆ ☞ ✷ ✂ ✡✝ ✌ ✑✏ ❀ ☎ ✓✒ ✾ ✩ ✶ ✕✔ ✗✖ ✿✎ ✶ ✩ ✂ ✆✝ ✌ ✘✏ ❀ ☎ ✓✒ ✾ ✩ ✶ ✙✔ ✗✖ ✕✎ ✌ ✾ ✂✘ ✾ ✓✎ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✪✠ ✆ ☞ ✝ ✝ ✂ ✆✝ ✌ ✶ ✩ ✝ ✠☎ ✎ ✌ ✶ ✩ ✂ ✡✝ ✌ ✘✏ ❀ ☎ ✚✒ ✾ ✩ ✶ ✕✔ ✖ ✎ ✎ ✜✛ ✆ ✾ ✁ ✾ ✌ ✾ ✂✘ ✚✙ ✝✎ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✪✠ ✔❄ ✌☞ ✦ ✌ ✾ ✂✘ ✚✙ ✝✎ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✪✠ ✆ ✁ ✵☞ ✙✢ ✁
★ ✶ ✘ ✾ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✵☞ ✂✷ ✄ ★ ✄✮ ✎ ✌ ✩ ✶ ✕✎ ✪✩ ✂ ✩ ☛ ✥ ☎ ✡ ✩ ☛ ✟ ✩ ☛ ✥ ✫ ☞ ✌ ☎ ✎ ✩ ✌ ✂ ✌ ✘✏ ❀ ☎ ✓✒ ✾ ✩ ✶ ✙✔ ✖ ✎ ✎ ✩ ☛ ✥ ✟ ✆ ✝ ✁ ☎ ❅ ✦ ❄ ✆ ☎ ☞ ✌ ✾ ✂✘ ✾ ✓✎ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✵☞ , ★ ✎ ✘ ✾ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✵☞ ✙✷ ❄ ✝ ✄ ★ ✄✮ ✎ ✌ ✩ ✶ ✕✎ ✪✩ ☛ ✥ ✂ ✩ ☛ ✥ ☎ ✡ ☞✬ ✩ ☛ ✥ ✮✭ ☛ ✟ ✩ ☛ ✥ ✫ ☞ ✌ ☎ ✎ ✩ ☛ ✥ ✌ ✂ ✌ ✘✏ ❀ ☎ ✓✒ ✾ ✩ ✶ ✙✔ ✗✖ ✕✎ ✎ ✩ ☛ ✥ with ✟ ✄ ☞ ★ ✷ ★ ✪✩ ✶ ✎ ✲ ✦ ✎ ✑ ❄ ✦ ✄ ✁ ✲ ✓ .
From Proposition 4.3 it follows:

Theorem 4. [START_REF] Berstel | Axel Thue's papers on repetitions in words: translation[END_REF] The generating function ✾ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✵☞ of permutations in ✏ ✾ according to the length, number of left minima and non-inversions is:

✾ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✵☞ ✙✷ ✄ ✾ ✆ ✾ ✟ ✄ ❇✠ ✆ ✿✠ ✂✁ ✵☞ ✾ ✩ ✶ ✎ ☛ ✦ ❄✶ ✟ ✆ ✝ ✁ ☎ ✠ ✆ ☎ ☞ ✝ ✾ ✄ ✲ ✦ ❂❁ ✄ ✲ ✩ ✶ ✆ ✲ ✩ ❁ ✎ ☛ ✦ ❄✶ ✟ ✆ ✝ ✁ ☎ ✠ ✆ ☎ ☞ ✿✠ ❅ ✣ ❄ ; with: ✾ ✟ ✄ ❇✠ ✆ ✿✠ ✂✁ ✵☞ ✂✷ ✄ ✩ ✂✁ ✦ ✬ ☎✄ ✥ ✭ ✩ ✝✆ ✩ ✖ ✡ ✩ ☛ ✟ ✩ ☛ ✥ ✫ ☞ ✬ ✖ ☞✭ ✩ ✬ ✆ ✬ ✟✞ ✞☛ ✖ ✡✠ ✡ ☛✄ ✥ ✌☞ ✖ ✭ ✘✭ ✩ ☛ ✥ ✄ ✩ ✂✁ ✦ ✬ ☎✄ ✥ ✭ ✩ ✆ ✩ ✖ ✡ ✩ ☛ ✟ ✩ ✫ ☞ ✬ ✖ ☞✭ ✩ ✬ ✆ ✬ ✟✞ ✞☛ ✖ ✡✠ ✡ ☛✄ ✥ ✌☞ ✖ ✭ ✘✭ ✩ ✁ We denote
✍ ✕✾ ✟ ✄ ✁ ✪✠ ☎✆ ✿✠ ✂✁ ✵☞ ✷ ✶ ✩ ✂ ✌ ✘✏ ❀ ☎ ✓✒ ✾ ✩ ✶ ✙✔ ✗✖ ✕✎ ✂ ✫ ☎ ✡ ✮☛ ✥ ✌ ✘✏ ❀ ☎ ✓✒ ✾ ✩ ✶ ✙✔ ✖ ✎ ✛ ✑ ❄ ✦ ✄ ✟ ✆ ✝ ✁ ☎ ❅ ✦ ❄ ✆ ☎ ✝ ✁ ✾ ☞ ✓ ✍ ✚✾ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✵☞ ✦ ✎ ✾ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✵☞ ✢ ✠ ✎ ✾ ✟ ✄ ✁ ✪✠ ☎✆ ✿✠ ✂✁ ✵☞ ✂✷ ✟ ❄ ✦ ✄ ✟ ✆ ✝ ✁ ☎ ❅ ✦ ❄ ✆ ☎ ☞ ✍☞ ✏✍ ✚✾ ✟
✄ ❄✠ ☎✆ ✿✠ ✂✁ ✵☞ ✜✁ Lemma 4.5 allows us to find the ✁ -equation satisfied by ✾ ✟ ✄ ❇✠ ✆ ✿✠ ✂✁ ✵☞ :

✄ ❁ ✁ ✾ ✖❀ ❄✶ ✟ ✆ ✝ ✁ ☎ ❅ ✦ ❄ ✆ ☎ ☞ ✾ ✟ ✄ ✁ ✪✠ ✆ ✿✠ ✂✁ ✵☞ ✾ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✵☞ ✦ ✑ ❄ ✦ ✄ ✟ ✆ ✝ ✁ ☎ ❅ ✦ ❄ ✆ ☎ ✝ ✁ ✾ ☞ ✓ ✾ ✟ ✄ ❇✠ ✆ ✬✠ ✛✁ ✵☞ ✝ ❄ ✷ ✂✯ ✡✁ (4.4) If ✆ ✷ ✁ ✓✷ ❄ then Equation (4.4) gives: ✾ ✟ ✄ ❇✠ ✔❄ ✎✠ ✔❄ ✌☞ ✂✷ ❄ ✦ ✟ ❅ ✝ ❄ ✌☞ ✄ ✦ ✒✑ ❄ ✦ ❃ ✟ ❅ ✝ ❄ ☞ ✄ ✝ ✟ ❅ ✦ ❄ ☞ ❁ ✄ ❁
❃ ✄❅ ✄ ❁ ✠ so from Theorem 4.4 we obtain:

✾ ✟ ✄ ❄✠ ✪❄ ✑✠ ✪❄ ✌☞ ✂✷ ✄ ✾ ✩ ❁ ✟ ❅ ✦ ❄ ✌☞ ✕ ❄ ✦ ✟ ❅ ✝ ❄ ✌☞ ✄ ✦ ✓✑ ❄ ✦ ❃ ✟ ❅ ✝ ❄ ✌☞ ✄ ✝ ✟ ❅ ✦ ❄ ☞ ❁ ✄ ❁ ❃ ✝ ✾ ✩ ✶ ✍ ✲ ✦ ❄✶ ✆ ✕ ✄ ✲ ✁
This means that the generating function of ✏ ✾ permutations according to the length is algebraic and quadratic, except for ❅ ✷ . In this case we obtain the expected result for the generating function of permutations according to the length, number of left minima and non-inversions, that is:

✕✔ ✟ ✄ ❇✠ ✆ ✿✠ ✂✁ ✵☞ ✙✷ ✍ ★ ✄✮ ✶ ✄ ★ ✆ ★ ✣✩ ✶ ✖ ☞ ✦ ❄✶ ✟ ✆ ✝ ✁ ☎ ✹ ✆ ☎ ☞ ✁

Related results

The classes of permutations described in this paper are enumerated by numbers lying between the Catalan numbers and the factorial (see Figure 2). The present result is an extension of previously known results for ❅ ✞✷ ❄ and ❅ ✞✷ ❃ . It is easy to prove that the

✟ ❅ ✝ ❃ ✑☞ -th number of the ✟ ❅ ✝ ❄ ☞ -th sequence is obtained from the ✟ ❅ ✝
❃ ✎☞ -th term of the ❅ -th sequence by adding ❅ ✖✕ .

In [START_REF] Chow | Forbidden subsequences and Chebyshev polynomials[END_REF], permutations with the forbidden subsequnces (❄ ✘❃ ✿❇ , (5.5)

✟ ❅ ✝ ❄ ☞ ❅ ✑✁ ✁ ✁ ❄ ✟ ❅ ✝ ❃ ✑☞ ), ❅ ✣ ❄ ,
The parameter ❅ allows us to obtain classes of permutations such that the number of permutations of length is a number lying between ❃ ✑★ ✪✩ ✶ and the -th Catalan number, ★ . The generating functions of these number sequences are all rational, except for ❅ ✗✷ as ❄ ✘❃ ✣❇ -avoiding permutations are enumerated by the Catalan numbers whose generating function is algebraic.

In [START_REF] Barcucci | From Motzkin to Catalan permutations[END_REF], permutations with the forbidden subsequnces (❇ ✰❃ ❄ ,

✟ ❅ ✝ ❄ ☞ ✒ ❄ ✟ ❅ ✝ ❇ ✑☞ ✱❃ ✣✁ ✁ ✁ ✟ ❅ ✝ ❄ ✌☞ ), ❅ ✣
❄ , are studied. Their generating tree can be expressed in terms of the following succession rule:

✘ ✙ ✚ ✁ ☎✄ ✝✆ ✠ ✆ ✟✞ ✟ ❃ ✎☞ ✠ ✡✠ ☞☛ ✍✌ ☎✎ ✠ ✑✏ ✓✒ ✆ ✎ ✒ ✕✔ ✞ ✟ ✆ ☞ ✗✖ ✟ ✆ ☞ ✿✁ ☎✁ ✄✁ ✟ ❃ ✎☞ ✟ ✆ ☛✝ ❄ ✌☞ ✠ ✆ ✑ ❅ ✝ ❄ ✠ ✡✠ ☞☛ ✍✌ ☎✎ ✠ ✑✏ ✓✒ ✆ ✎ ✒ ✕✔ ✞ ✟ ✆ ☞ ✗✖ ✟ ✆ ✦ ❄ ☞ ✿✁ ✄✁ ☎✁ ✟ ❅ ✔☞ ✟ ❅ ✪☞ ✿✁ ☎✁ ✄✁ ✟ ❃ ✎☞ ✟ ✆ ✓✝ ❄ ✌☞ ✠ ✆ ✤✣ ❅ ✝ ❄ ✑✁ (5.6)
The parameter ❅ allows us to obtain classes of permutations enumerated by numbers lying between the Motzkin and the Catalan numbers whose generating functions are both algebraic.

In [START_REF] Pergola | Bell permutations and Stirling numbers interpolation[END_REF], the set of permutations ✰

✘ ✙ ✚ ✁ ✄ ✓✆ ✠ ✆ ✟✞ ✟ ❃ ✑☞ ✠ ✡✠ ✛☛ ✜✌ ✎ ✠ ✏ ✓✒ ✆ ✎ ✒ ✔ ✞ ✟ ✆ ☞ ✢✖ ✟ ✆ ☞ ✁ ✄✁ ✄✁ ✟ ✆ ✓✝ ❄ ✌☞ ✲ ✠ ✆ ✑ ❅ ✝ ❄ ✠ ✡✠ ✛☛ ✜✌ ✎ ✠ ✏ ✓✒ ✆ ✎ ✒ ✔ ✞ ✟ ✆ ☞ ✢✖ ✟ ✆ ✦ ❄ ✌☞ ✲ ✩ ✾ ✟ ✆ ✓✝ ❄ ☞ ✾ ✠ ✆ ✣ ❅ ✝ ❄ ✎✁
(5.7)

The parameter ❅ allows us to obtain classes of permutations enumerated by numbers lying between the Bell numbers and the factorial both having transcendent generating functions.

Let us note that we describe countably many succession rules which lead to rational, algebraic and transcendent generating functions. These are instances of the general theory developed by C. Banderier et al. in [START_REF] Banderier | On generating functions of generating trees[END_REF].

  l'Informatique et des Mathématiques Discrètes (MIMD), Paris, France

Example 3 . 2

 32 ✿❇ ✑☞ ; and let ✆ , ❃ ✞ ✆ ✞ , be the minimum index in ✁ such that ✠ ✶ ✑ ✆ exists and ✁ ✟ ✠ ✍✶ ✜☞ ✑ ✁ ✟ ✆ ☞ ; then the active sites of ✁ are the positions ✯ ✠ ✄✁ ☎✁ ✄✁ ✜✠ ✆ ✦ ❄ . The insertion of ✝ ❄ into each other site on the right of the position ✆ ✦ ❄ gives the subsequence ✁ ✟ ✠ ✶ ✄☞ ✏✁ ✟ ✆ ☞ ✟ ✝ ❄ ✌☞ that is forbidden. This means that the active sites of ✁ are all the positions lying among any pair of elements of ✁ constituting the longest initial decreasing subsequence. If ✁ has ✆ active sites then its longest initial decreasing subsequence has length ✆ ✦ ❄ . The permutation obtained by inserting ✝ ❄ into the position ✯ gives a new permutation with ✟ ✆ ✘✝ ❄ ✌☞ active sites; the permutation obtained by inserting ✝ ❄ into the position ✠ , ❄ ✰✞ ✱✠ ✞ ✆ ✦ ❄ , gives ✟ ✠ ✝ ❄ ✌☞ active sites, (inductive step in rule (3.1)). The generating tree representing ❄ ✖❃ ✣❇ -avoiding permutations can be obtained by developing rule (3.1) and by labelling each permutation with the right label ✟ ✆ ☞ . The Schröder tree and ✟ ❄ ✘❃ ✿❇ ✣❆ ✠ ✯❃ ❅❄ ✘❇ ✣❆ ✔☞ -avoiding permutations are obtained by the succession rule:

  or ❃ ❅❄ ✔❇ ; then the active sites of ✁ are the positions ✯ ✡✠ ☎✁ ✄✁ ☎✁ ✜✠ ✆ ✦ ❄ . The insertion of ✝ ❄ into each other site, that is the positions ✆ ✠ ☎✁ ✄✁ ☎✁ ✜✠ , gives at least one of the forbidden subsequences ❄ ✘❃ ✣❇ ✿❆ ✠ ✯❃ ❅❄ ✔❇ ✿❆ . Let ✁ be a permutation with ✆ active sites; the permutations obtained by inserting ✝ ❄ into the position ✯ and ❄ have ✟ ✆ ✝ ❄ ☞ active sites; the permutation obtained by inserting ✝ ❄ into the position ✠ , sites, each other site gives at least one of the two forbidden subsequences because ✝ ❄ has at least two smaller elements on its left (inductive step in rule (3.2)). The generating tree related to rule (3.2) and representing ✟ ❄ ✘❃ ✿❇ ✣❆ ✠ ✯❃ ❅❄ ✘❇ ✣❆ ✔☞ -avoiding permutations is shown in Figure 1.

-

Fig. 1 :

 1 Fig. 1:The generating tree for ✝ ☞ ✚✒ ✔✩ ✪✮ ✰✗ ✏✒ ✣☞ ✯✩ ✔✮ ✲✍ -avoiding permutations.

  1806 8558 41586 .............. 1 2 6 24 114 600 3372 19824 120426 .............. 1 2 6 24 120 696 4440 30168 214200 ..............

Fig. 2 :

 2 Fig. 2: First numbers of the sequences counting the permutations in ✦ ✄ .

✬✾

  contains subsequences having length ✟ ❅ ✝ ❃ ✑☞ such that the two largest elements, that is -th elements of the sequences, while the other ❅ elements ✛ ✿❄ ✎✠ ☎✁ ✄✁ ☎✁ ✄✠ ❅ ✢ can be in any order. This means that the position ✠ , ✯ ✞ ✠ ✞ , in a permutation ✁ ✮ ✱✰ ★ ✟ ✬ ✾ ☞ , is an active site if and only if a sequence of indices ✠ ✶ ✠ ☎✁ ✄✁ ☎✁ ✜✠ ✕✠ ✾ ✎✠ ✕✠ ✾ ✖❀ ❄✶ such that ✠ ✍✶ ✑ ✜ ✢✜ ✝✜ ✑ ✠ ✾ ✑ ✠ ✾ ✖❀ ❄✶ ✞ ✠ and✹ ✄ ✄ ✿✶ ✞✝ ✠✟ ✡✝ ✾ ✟ ✁ ✟ ✠ ✡✟ ✍☞ ✖☞ ✑ ✁ ✟✠ ✾ ✖❀ ✶ ✄☞ does not exist. It follows that the active sites lie on the left of the minimum index ✠ ✾ ✖❀ ❄✶ that gives such a sequence. This, in turn, means that the ✟ ❅ ✝ ❄ ✌☞ leftmost sites of a permutation are always active, if they exist.

  we obtain a new permutation ✁ ☞☛ with ✟ ✠ ✝ ❄ ✌☞ active sites.As a matter of fact, the sequence of indices ❄ ✑✠ ✄✁ ☎✁ ✄✁ ✜✠ ❅ ✎✠ ✟ ✠ ✝ ❄ ☞ satisfies the required properties and moreover ✟ ✠ ✝ ❄ ✌☞ is the minimum index leading to such a sequence (see Figure3).

  ✜✠ ✄✁ ✄✁ ☎✁ ✜✠ ✪❄ ✎✢ is introduced. The resulting generating tree is described by the succession rule:

  ✟ ❄ ✌☞ ✄✁ ✟ ❃ ✑☞ ✿✁ ✄✁ ☎✁ ✜✁ ✁ ✟ ☞ on ☎ ✝✆ ✷ ✛ ✰❄ ✎✠ ✏❃ ✡✠ ✄✁ ☎✁ ✄✁ ✜✠ ✢ is a bijection between ☎ ✝✆ and ☎ ✝✆ . Let ✰ ★ be the set of permutations on ☎ ✝✆ . A permutation ✁ ✮ ✱✰ ★ contains a subsequence of type ✭ ✮ ✱✰ ✲ if and only if a sequence of indices ❄ ✟✞ ✡✠ ☞☛ ✍✌ ✶ ✏✎ ✒✑ ✠ ☞☛ ✍✌ ❁ ✓✎ ✒✑ ✁ ✄✁ ✄✁ ✑ ✠ ☞☛ ✍✌ ✲ ✔✎ ✞ exists such that ✁ ✟ ✠ ✶ ☞ ✄✁ ✟ ✠ ❁ ☞ ❂✁ ✄✁ ✄✁ ✕✁ ✟ ✠ ✲ ☞ has all the same pairwise comparisons as ✭ . We denote the set of permutations of ✰ ★ not containing subsequences of type ✭ by ✑☞ ☞✁ ✟ ✗ ✑☞ ☞✁ ✟ ✖ ✑☞ ✙✷ ✂✖ ❄ ✣✙ ✲❇ , ✁ ✟ ❄ ✌☞ ✏✁ ✟ ❃ ✎☞ ✏✁ ✟ ✗ ✑☞ ☞✁ ✟ ✙ ✎☞ ✙✷ ✂✖ ❄ ✤✙ ✿❃ . If we have the set ✭ ✶ ✮ ✰ ❇✲ ✦✥ ✠ ✄✁ ☎✁ ✄✁ ✜✠ ✖✭ ★✧ ✮ ✰ ❇✲ ✓✩ of permutations, we denote the set ✰ ★ ✟ ✭ ✌✶ ✄☞ ✫✪ ✁ ☎✁ ✄✁ ✣✪ ✻✰ ★ ✟ ✭ ★✧ ✑☞

	✰ ★ ✟ ✭ ☞ . Example 2.1 The permutation ✖ ❄ ✔❆ ✘✗ ✚✙ ✣❇ ✰❃ belongs to ✰ ✜✛ ✟ ❃ ✣❆ ❄ ✘❇ ✑☞ because all its subsequences of length ❆ are not of type ❃ ✣❆ ❄ ✘❇ . This permutation does not belong to ✰ ✢✛ ✟ ❇ ❄ ✪❆ ❈❃ ✑☞ because there exist subsequences of type ❇ ❄ ✪❆ ✸❃ , namely ✁ ✟ ❄ ✌☞ ✏✁ ✟

❃

by ✰ ★

  the numerator and the denominator of ✾ ✟ ✄ ❇✠ ☎✆ ✿✠ ✛✁ ✵☞ by ✍ ✚✾ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✵☞ and ✎ ✾ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✵☞ , respectively. After some computations we obtain:

	Lemma 4.5 The functions ✍ ✾ ✟ ✄ ❄✠ ☎✆ ✿✠ ✂✁ ✵☞ and ✎ ✚✾ ✟ ✄ ❇✠ ✆ ✬✠ ✛✁ ✵☞ satisfy the following equalities:

  are studied. Their generating tree can be expressed in terms of the following succession rule:

	✘ ✙ ✚ ✁ ☎✄ ✝✆ ✠ ✆ ✞ ✠ ✡✠ ☞☛ ✍✌ ☎✎ ✠ ✑✏ ✒ ✠ ✡✠ ☞☛ ✍✌ ☎✎ ✠ ✑✏ ✒	✟ ❃ ✎☞ ✆ ✎ ✒ ✕✔ ✆ ✎ ✒ ✕✔	✞ ✞	✟ ✆ ✟ ❅ ✪☞ ✢✖ ☞ ✢✖	✟ ❃ ✎☞ ✿✁ ☎✁ ✄✁ ✟ ❃ ✑☞ ✿✁ ✄✁ ☎✁	✟ ✆ ✟ ❅ ✪☞	☞ ✟ ✆ ✓✝ ✟ ❅ ✪☞ ✠	❄ ☞ ✠ ✆ ✤✣ ❅ ✆ ✝ ✑ ❅ ✝ ❄ ✎✁	❄


Toufik Mansour
email: tmansur@study.haifa.ac.il

Alek Vainshtein

Avoiding maximal parabolic subgroups of S k

Keywords: permutations, forbidden patterns, parabolic subgroups, Laguerre polynomials, rook polynomials

We find an explicit expression for the generating function of the number of permutations in S n avoiding a subgroup of S k generated by all but one simple transpositions. The generating function turns out to be rational, and its denominator is a rook polynomial for a rectangular board.

Introduction and Main Result

Let [p] = {1, . . . , p} denote a totally ordered alphabet on p letters, and let α = (α 1 , . . . , α m ) ∈ [p 1 ] m , β = (β 1 , . . . , β m ) ∈ [p 2 ] m . We say that α is order-isomorphic to β if for all 1 ≤ i < j ≤ m one has α i < α j if and only if β i < β j . For two permutations π ∈ S n and τ ∈ S k , an occurrence of τ in π is a subsequence 1 ≤ i 1 < i 2 < . . . < i k ≤ n such that (π i 1 , . . . , π i k ) is order-isomorphic to τ; in such a context τ is usually called the pattern. We say that π avoids τ, or is τ-avoiding, if there is no occurrence of τ in π. Pattern avoidance proved to be a useful language in a variety of seemingly unrelated problems, from stack sorting [START_REF] Knuth | The Art of Computer Programming[END_REF]Ch. 2.2.1] to singularities of Schubert varieties [LS]. A natural generalization of single pattern avoidance is subset avoidance; that is, we say that π ∈ S n avoids a subset T ⊂ S k if π avoids any τ ∈ T . The set of all permutations in S n avoiding T ⊂ S k is denoted S n (T ). A complete study of subset avoidance for the case k = 3 is carried out in [SS]. For k > 3 the situation becomes more complicated, as the number of possible cases grows rapidly. Recently, several authors have considered the case of general k when T has some nice algebraic properties. Paper [BDPP] treats the case when T is the centralizer of k -1 and k under the natural action of S k on [k] (see also Sec. 3 for more detail). In [AR], T is a Kazhdan-Lusztig cell of S k , or, equivalently, the Knuth equivalence class (see [START_REF] Stanley | Enumerative Combinatorics[END_REF]vol. 2,Ch. A1]). In this paper we consider the case when T is a maximal parabolic subgroup of S k .

Let s i denote the simple transposition interchanging i and i + 1. Recall that a subgroup of S k is called parabolic if it is generated by s i 1 , . . . , s i r . A parabolic subgroup of S k is called maximal if the number of its generators equals k -2. We denote by P l,m the (maximal) parabolic subgroup of S l+m generated by s 1 , . . . , s l-1 , s l+1 , . . . , s l+m-1 , and by f l,m (n) the number of permutations in S n avoiding all the patterns in P l,m . In this note we find an explicit expression for the generating function of the sequence { f l,m (n)}. † Partially supported by HIACS. To be more precise, we prove the following more general result. Let us denote σ = s 1 s 2 . . . s k-1 , that is, σ = (2, 3, . . . , k, 1) (written in one-line notation), and let a be an integer, 0 ≤ a ≤ k -1 (here and in what follows k = l + m). We denote by f a l,m (n) the number of permutations in S n avoiding the left coset σ a P l,m ; in particular,

f 0 l,m (n) coincides with f l,m (n). Let F a l,m (x) denote the generating function of { f a l,m (n)}, F a l,m (x) = ∑ n≥0 f a l,m (n)x n .
Recall that the Laguerre polynomial L α n (x) is given by

L α n (x) = 1 n! e x x -α d n dx n e -x
x n+α , and the rook polynomial of the rectangular s × t board is given by R s,t (x) = s!x s L t-s s (-x -1 ) for s ≤ t and by R s,t (x) = R t,s (x) otherwise (see [START_REF] Riordan | An Introduction to Combinatorial Analysis[END_REF]Ch. 7.4]).

Main Theorem. Let λ = min{l, m}, µ = max{l, m}, then

F a l,m (x)R l,m (-x) = λ-1 ∑ r=0 x r r! r ∑ j=0 (-1) j l j m j r j + (-1) λ x λ λ! µ-λ-1 ∑ r=0 x r r! µ -r -1 λ , or, equivalently, F a l,m (x) = k-1 ∑ r=0 x r r! - (-1) λ x µ λ!L µ-λ λ (x -1 ) λ-1 ∑ r=0 (k + r)!x r λ ∑ j=r+1 (-1) j l j m j k+r j
,

where k = l + m = λ + µ.
The proof of the Main Theorem is presented in the next section.

As a corollary we immediately get the following result (see [START_REF] Mansour | Permutations containing and avoiding certain patterns[END_REF]Theorem 1]).

Corollary 1 Let 0 ≤ a ≤ k -1, then f a 1,k-1 (n) = (k -2)!(k -1) n+2-k for n ≥ k n! for n < k. Proof. Since R 1,k-1 = 1 + (k -1)x, the Main Theorem implies F a 1,k-1 (x) = 1 -∑ k-3 r=0 x r+1 (k -r -2)r! 1 -(k -1)x = x k-2 (k -2)! 1 -(k -1)x + k-3 ∑ r=0 x r r!,
and the result follows. ✷

Another immediate corollary of the Main Theorem gives the asymptotics for

f a l,m (n) as n → ∞. Corollary 1.2. f a l,m (n) ∼ cγ n
, where c is a constant depending on l and m, and γ is the maximal root of L µ-λ λ ; in particular, γ ≤ k -2 + 1 + 4(l -1)(m -1). Proof. Follows from standard results in the theory of rational generating functions (see e.g. [START_REF] Stanley | Enumerative Combinatorics[END_REF]vol. 1,Ch. 4]) and the fact that all the roots of Laguerre polynomials are simple (see [START_REF] Szego | Orthogonal Polynomials[END_REF]Ch. 3.3]). The upper bound on γ is obtained in [IL]. ✷

Proofs

First of all, we make the following simple, though useful observation.

Lemma 2 For any natural a, l, m, n such that

1 ≤ a ≤ l + m -1 one has f a l,m (n) = f m+l-a m,l (n).
Proof . Denote by ρ n and κ n the involutions S n → S n that take

(i 1 , i 2 , . . . , i k ) to (i k , . . . , i 2 , i 1 ) (reversal) to (n + 1 -i 1 , n + 1 -i 2 , . . . , n + 1 -i n ) (complement)
, respectively. It is easy to see that for any T ⊂ S k , the involutions ρ n and κ n provide natural bijections between the sets S n (T ) and S n (ρ k T ), and between S n (T ) and S n (κ k T ), respectively. It remains to note that ρ k κ k σ a P l,m = σ l+m-a P m,l . ✷

From now on we assume that a ≥ 0, l ≥ 1, m ≥ 1 are fixed, and denote b = nm + a. It follows from Lemma 2 that we may assume that a ≤ m, and hence b ≤ n. This means, in other words, that τ ∈ S k belongs to σ a P l,m if and only if (τ 1 , . . . , τ l ) is a permutation of the numbers a + 1, . . . , a + l. In what follows we usually omit the indices a, l, m whenever appropriate; for example, instead of f a l,m (n) we write just f (n). For any n ≥ k and any d such that 1 ≤ d ≤ n, we denote by

g n (i 1 , . . . , i d ) = g a n;l,m (i 1 , . . . , i d ) the number of permutations π ∈ S n (σ a P l,m ) such that π j = i j for j = 1, . . . , d. It is natural to extend g n to the case d = 0 by setting g n ( / 0) = f (n).
The following properties of the numbers g n (i 1 , . . . , i d ) can be deduced easily from the definitions.

Lemma 3

(i) Let n ≥ k and 1 ≤ i ≤ n, then g n (. . . , i, . . . , i, . . .) = 0. (ii) Let n ≥ k and a + 1 ≤ i j ≤ b for j = 1, . . . , l, then g n (i 1 , . . . , i l ) = 0. (iii) Let n ≥ k, 1 ≤ r ≤ d ≤ l, and a + 1 ≤ i j ≤ b for j = 1, . . . , d, j = r, then g n (i 1 , . . . , i d ) = g n-1 (i 1 -1, . . . , i r-1 -1, i r+1 -1, . . . , i d -1) if 1 ≤ i r ≤ a g n-1 (i 1 , . . . , i r-1 , i r+1 , . . . , i d ) if b + 1 ≤ i r ≤ n.
Proof . Property (i) is evident. Let us prove (ii). By (i), we may assume that the numbers i 1 , . . . , i l are distinct. Take an arbitrary π ∈ S n such that π j = i j for j = 1, . . . , l. Evidently, for any r ≤ a there exists a position j r > l such that π j r = r; the same is true for any r ≥ b + 1. Therefore, the restriction of π to the positions 1, 2, . . . , l, j 1 , j 2 , . . . , j a , j b+1 , j b+2 , . . . , j n (in the proper order) gives an occurrence of τ ∈ σ a P l,m in π. Hence, π / ∈ S n (σ a P l,m ), which means that g n (i 1 , . . . , i l ) = 0. To prove (iii), assume first that 1 ≤ i r ≤ a. Let π ∈ S n and π j = i j for j = 1, . . . , d. We define π * ∈ S n-1 by

π * j =    π j -1 for 1 ≤ j ≤ r -1, π j+1 -1 for j ≥ r and π j+1 > i r , π j+1
for j ≥ r and π j+1 < i r .

(1)

We claim that π ∈ S n (σ a P l,m ) if and only if π * ∈ S n-1 (σ a P l,m ). Indeed, the only if part is trivial, since any occurrence of τ ∈ σ a P l,m in π * immediately gives rise to an occurrence of τ in π. Conversely, any occurrence of τ in π that does not include i r gives rise to an occurrence of τ in π * . Assume that there exists an occurrence of τ in π that includes i r . Since r ≤ d ≤ l, this occurrence of τ contains a entries that are situated to the right of i r and are strictly less than i r . However, the whole π contains only a -1 such entries, a contradiction. It now follows from (1) that property (iii) holds for 1 ≤ i r ≤ a. The case b + 1 ≤ i r ≤ n is treated similarly with the help of the transformation (π ∈ S n ) → (π • ∈ S n-1 ) given by

π • j =    π j for 1 ≤ j ≤ r -1, π j+1 -1
for j ≥ r and π j+1 > i r , π j+1

for j ≥ r and π j+1 < i r .

✷

Now we introduce the quantity that plays the crucial role in the proof of the Main Theorem. For n ≥ k and 1 ≤ d ≤ l we put

A(n, d) = A a l,m (n, d) = b ∑ i 1 ,...,i d =a+1 g n (i 1 , . . . , i d ).
As before, this definition is extended to the case d = 0 by setting

A(n, 0) = g n ( / 0) = f (n). Theorem 4 Let n ≥ k + 1 and 1 ≤ d ≤ l -1, then A(n, d + 1) = A(n, d) -(m -d)A(n -1, d) -dA(n -1, d -1). ( 2
)
Proof . First of all, we introduce two auxiliary sums:

B(n, d) = B a l,m (n, d) = b+1 ∑ i 1 ,...,i d =a+1 g n (i 1 , . . . , i d ), C(n, d) = C a l,m (n, d) = b ∑ i 1 ,...,i d =a g n (i 1 , . . . , i d )
,

where b = n -m + a; once again, B(n, 0) = C(n, 0) = f (n).
Let us prove three simple identities relating together the sequences {A(n, d)}, {B(n, d)}, {C(n, d)}.

Lemma 5 Let n ≥ k and 1 ≤ d ≤ l, then:

A(n, d) = A(n, d -1) -(m -a)B(n -1, d -1) -aC(n -1, d -1), (m -a)A(n, d) = (m -a)B(n, d) -(m -a)dB(n -1, d -1), aA(n, d) = aC(n, d) -adC(n -1, d -1).
Proof . To prove the first identity, observe that by definitions and Lemma 3(iii) for the case r = d, one has

A(n, d -1) -A(n, d) = b ∑ i 1 ,...,i d-1 =a+1 n ∑ i d =1 g n (i 1 , . . . , i d ) -A(n, d) = b ∑ i 1 ,...,i d-1 =a+1 a ∑ i d =1 g n (i 1 , . . . , i d ) + n ∑ i d =b+1 g n (i 1 , . . . , i d ) = b ∑ i 1 ,...,i d-1 =a+1 ag n-1 (i 1 -1, . . . , i d-1 -1) + (m -a)g n-1 (i 1 , . . . , i d-1 ) = aC(n -1, d -1) + (m -a)B(n -1, d -1),
and the result follows.

The second identity is trivial for a = m, so assume that 0 ≤ a ≤ m -1 and observe that by definitions and Lemma 3(ii) and (iii), one has

B(n, d) = b ∑ i 1 ,...,i d =a+1 g n (i 1 , . . . , i d ) + d ∑ j=1 b ∑ i 1 ,...,î j ,...,i d =a+1 g n (i 1 , . . . , i j-1 , b + 1, i j+1 . . . , i d ) = A(n, d) + d ∑ j=1 b ∑ i 1 ,...,î j ,...,i d =a+1 g n-1 (i 1 , . . . , i j-1 , i j+1 , . . . , i d ) = A(n, d) + dB(n -1, d -1),
and the result follows.

Finally, the third identity is trivial for a = 0, so assume that 1 ≤ a ≤ m and observe that by definitions and Lemma 3(ii) and (iii), one has

C(n, d) = b ∑ i 1 ,...,i d =a+1 g n (i 1 , . . . , i d ) + d ∑ j=1 b ∑ i 1 ,...,î j ,...,i d =a+1 g n (i 1 , . . . , i j-1 , a, i j+1 . . . , i d ) = A(n, d) + d ∑ j=1 b ∑ i 1 ,...,î j ,...,i d =a+1 g n-1 (i 1 -1, . . . , i j-1 -1, i j+1 -1, . . . , i d -1) = A(n, d) + dC(n -1, d -1),
and the result follows. ✷

Now we can complete the proof of Theorem 4. Indeed, using twice the first identity of Lemma 5, one gets

A(n, d + 1) = A(n, d) -(m -a)B(n -1, d) -aC(n -1, d -1), dA(n -1, d) = dA(n -1, d -1) -d(m -a)B(n -2, d -1) -daC(n -2, d -1).
Next, the other two identities of Lemma 5 imply

A(n, d + 1) -dA(n -1, d) = A(n, d) -dA(n -1, d -1) -(m -a)B(n -1, d) -(m -a)dB(n -2, d -1) -aC(n -1, d) -adC(n -2, d -1) = A(n, d) -dA(n -1, d -1) -(m -a)A(n -1, d) -aA(n -1, d),
and the result follows. ✷

The next result relates the sequence {A(n, d)} to the sequence { f (n)}.

Theorem 6 Let n ≥ k and 1 ≤ d ≤ l, then A(n, d) = d ∑ j=0 (-1) j j! m j d j f (n -j).
Proof . Let D(n, d) = D a l,m (n, d) denote the right hand side of the above identity. We claim that for n ≥ k +1 and 1 ≤ d ≤ l -1, D(n, d) satisfies the same relation (2) as A(n, d) does. Indeed,

D(n -1, d) = d ∑ j=0 (-1) j j! m j d j f (n -1 -j) = - d ∑ j=1 (-1) j ( j -1)! m j -1 d j -1 f (n -j) + (-1) d d! m d f (n -d -1),
and

D(n -1, d -1) = d-1 ∑ j=0 (-1) j j! m j d -1 j f (n -1 -j) = - d ∑ j=1 (-1) j ( j -1)! m j -1 d -1 j -1 f (n -j),
and hence

D(n, d) -(m -d)D(n -1, d) -dD(n -1, d -1) = f (n) + (m -d)(-1) d+1 d! m d f (n -d -1) + d ∑ j=1 (-1) j j! m j d j + m -d j m j -1 d j -1 + d j m j -1 d -1 j -1 f (n -j) = f (n) + d ∑ j=1 (-1) j j! m j d + 1 j f (n -j) + (-1) d+1 (d + 1)! m d + 1 f (n -d -1) = D(n, d + 1).
It follows that D(n, d) (as well as A(n, d)) are defined uniquely for n ≥ k and 1 ≤ l ≤ d by initial values D(k, d), D(n, 0), and D(n, 1) (A(k, d), A(n, 0), and A(n, 1), respectively). It is easy to see that for n ≥ k one has A(n, 0) = D(n, 0) = f (n). Next, the first identity of Lemma 5 for d = 1 gives

A(n, 1) = A(n, 0) -(m -a)B(n -1, 0) -aC(n -1, 0) = f (n) -m f (n -1) for n ≥ k.
On the other hand, by definition,

D(n, 1) = f (n) -m f (n -1) for n ≥ k,
and hence A(n, 1) = D(n, 1). Finally, a simple combinatorial argument shows that

A(k, d) = d! l d (k -d)! -l!m! for 1 ≤ d ≤ l.
On the other hand,

D(k, d) = d ∑ j=0 (-1) j j! m j d j (k -j)! -l!m!, since f (r) = r! for 1 ≤ r ≤ k -1 and f (k) = k! -l!m!. To prove A(k, d) = D(k, d) it remains to check that d ∑ j=0 (-1) j j! m j d j (k -j)! = d! l d (k -d)!,
which follows from Lemma 7 below. ✷

Finally, we are ready to prove the Main Theorem stated in Sec. 1. First of all, by Lemma 3(ii), A(n, l) = 0 for n ≥ k. Hence, by Theorem 6,

l ∑ j=0 (-1) j j! m j l j f (n -j) = 0 for n ≥ k, or, equivalently, l ∑ j=0 (-1) j j! m j l j x j f (n -j)x n-j = 0 for n ≥ k.
As was already mentioned,

f (r) = r! for 1 ≤ r ≤ k -1, therefore, summing over n ≥ k yields l ∑ j=0 (-1) j j! m j l j x j F a l,m (x) - k-j-1 ∑ i=0 x i i! = 0. (3)
Recall that the rook polynomial of the rectangular s × t board, s ≤ t, satisfies relation

R s,t (x) = s ∑ j=0 j! t j s j x j
(see [START_REF] Riordan | An Introduction to Combinatorial Analysis[END_REF]Ch. 7.4]). Hence, (3) is equivalent to

F a l,m (x)R λ,µ (-x) = l ∑ j=0 (-1) j j! m j l j x j k-j-1 ∑ i=0 x i i! = k-1 ∑ r=0 x r r! r ∑ j=0 (-1) j l j m j r j .
Let us divide the external sum in the above expression into three parts: the sum from r = 0 to λ -1, the sum from r = λ to µ -1, and the sum from r = µ to k -1. By Lemma 7 below, the third sum vanishes, while the second sum is equal to

µ-1 ∑ r=λ x r r!(-1) λ (r -λ)!(k -r -1)! (µ -r -1)!r! ,
and the first expression of the Main Theorem follows. The second expression is obtained easily from (3) and relation between rook polynomials and Laguerre polynomials given in Sec. 1. ✷

It remains to prove the following technical result, which is apparently known; however, we failed to find a reference to its proof, and decided to present a short proof inspired by the brilliant book [PWZ].

Lemma 7 Let 1 ≤ s ≤ t and let M(s,t) = s ∑ i=0 (-1) i s i t i n i . Then: M(s,t) =          ( n-t s ) ( n s ) if n ≥ s + t, 0 if t ≤ n ≤ s + t -1, (-1) s ( s+t-n-1 s ) ( n s ) if s ≤ n ≤ t -1.
Proof . Direct check reveals that M(s,t) is a hypergeometric series; to be more precise,

M(s,t) = 2 F 1 -t,-s -n ; 1 .
Since -s is a nonpositive integer, the Gauss formula applies (see [START_REF] Petkovšek | [END_REF]Ch. 3.5]), and we get

M(s,t) = lim z→n Γ(-z + t + s)Γ(-z) Γ(t -z)Γ(s -z) . Recall that Γ(x)Γ(1 -x) = π sin πx . (4)
If n ≥ s + t, we apply (4) for x = -z + t + s, x = tz, x = sz, x = -z, and get

M(s,t) = - Γ(n -t + 1)Γ(n -s + 1) Γ(n -t -s + 1)Γ(n + 1) lim z→n sin π(t -z) sin π(s -z) sin πz sin π(t + s -z) = n-t s n s
.

If t ≤ n ≤ s + t -1, we apply (4) for x = tz, x = sz, x = -z, and get

M(s,t) = - Γ(n -t + 1)Γ(n -s + 1)Γ(s + t -n) Γ(n + 1) lim z→n sin π(t -z) sin π(s -z) sin πz = 0.
Finally, if s ≤ n ≤ t -1, we apply (4) for x = sz, x = -z, and get

M(s,t) = - Γ(s + t -n)Γ(n -s + 1) Γ(t -n)Γ(n + 1) lim z→n sin π(s -z) sin πz = (-1) s s+t-n-1 s n s . ✷ 3

Concluding remarks

Observe first, that according to the Main Theorem, F a l,m (x) does not depend on a; in other words, |S n (P l,m )| = |S n (σ a P l,m )| for any a. We obtained this fact as a consequence of lengthy computations. A natural question would be to find a bijection between S n (P l,m ) and S n (σ a P l,m ) that explains this phenomenon.

Second, it is well known that rook polynomials (or the corresponding Laguerre polynomials) are related to permutations with restricted positions, see [START_REF] Riordan | An Introduction to Combinatorial Analysis[END_REF]Ch.7,8]. Laguerre polynomials also arise in a natural way in the study of generalized derangements (see [FZ] and references therein). It is tempting to find a combinatorial relation between permutations with restricted positions and permutations avoiding maximal parabolic subgroups, which could explain the occurrence of Laguerre polynomials in the latter context.

Finally, one can consider permutations avoiding nonmaximal parabolic subgroups of S k . The first natural step would be to treat the case of subgroups generated by k -3 simple transpositions. It is convenient to denote by P l 1 ,l 2 ,l 3 (with l 1 + l 2 + l 3 = k) the subgroup of S k generated by all the simple transpositions except for s l 1 and s l 1 +l 2 ; further on, we set f l 1 ,l 2 ,l 3 (n) = |S n (P l 1 ,l 2 ,l 3 )|, and F l 1 ,l 2 ,l 3 (x) = ∑ n≥0 f l 1 ,l 2 ,l 3 (n)x n . It is easy to see that F l 1 ,l 2 ,l 3 (x) = F l 3 ,l 2 ,l 1 (x), so one can assume that l 1 ≤ l 3 . This said, the main result of [BDPP] can be formulated as follows: let k ≥ 3, then

F 1,1,k-2 (x) = k-3 ∑ r=1 x r r! + (k -3)!x k-4 2 1 -(k -1)x -1 -2(k -1)x + (k -3) 2 x 2 .
To the best of our knowledge, this is the only known instance of F l 1 ,l 2 ,l 3 (x). It is worth noting that even in this, simplest case of nonmaximal parabolic subgroup, the generating function is no longer rational.

  1365-8050 c 2000 Maison de l'Informatique et des Mathématiques Discrètes (MIMD), Paris, France