Marina Groshaus
email: groshaus@dc.uba.ar

Jayme L Szwarcfiter

On Hereditary Helly Classes of Graphs

Keywords: Algorithms, bicliques, Helly property, graph classes

In graph theory, the Helly property has been applied to families of sets, such as cliques, disks, bicliques, and neighbourhoods, leading to the classes of clique-Helly, disk-Helly, biclique-Helly, neighbourhood-Helly graphs, respectively. A natural question is to determine for which graphs the corresponding Helly property holds, for every induced subgraph. This leads to the corresponding classes of hereditary clique-Helly, hereditary disk-Helly, hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. In this paper, we describe characterizations in terms of families of forbidden subgraphs, for the classes of hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. We consider both open and closed neighbourhoods. The forbidden subgraphs are all of fixed size, implying polynomial time recognition for these classes.

Introduction

In the scope of graph theory, the Helly property has been applied to families of sets as cliques, e.g. [START_REF] Bondy | Self-clique graphs and matrix permutations[END_REF], [START_REF] Escalante | Über iterierte Clique-Graphen[END_REF], [START_REF] Hamelink | A partial characterization of clique graphs[END_REF], [START_REF] Larrión | A hierarchy of self-clique graphs[END_REF], [START_REF] Roberts | A characterization of clique graphs[END_REF], bicliques [START_REF] Groshaus | Biclique-Helly graphs[END_REF], neighbourhoods [START_REF] Berge | Hypergraphs[END_REF] and disks [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF], [START_REF] Bandelt | Clique graphs and Helly graphs[END_REF], [START_REF] Bandelt | Dismantling absolute retracts of reflexive graphs[END_REF]. The corresponding graphs are the clique-Helly, biclique-Helly, neighbourhood-Helly and disk-Helly graphs, respectively. Bicliques, in general, have been considered in some different contexts, e.g. [START_REF] Müller | On edge perfectness and classes of bipartite graphs[END_REF][START_REF] Peeters | The maximum edge biclique problem is NP-complete[END_REF][START_REF] Prisner | Bicliques in graphs, I: Bounds on their number[END_REF][START_REF] Tuza | Covering of graphs by complete bipartite subgraphs: complexity of 0-1 matrices[END_REF].

Besides the interest of examining bicliques in the scope of the Helly property, these graphs should be of interest in the study of retracts [START_REF] Hell | Personal Communication[END_REF]. In fact, retracts of bipartite graphs are related to neighbourhood-Helly graphs and the latter are related to biclique-Helly graphs in some different aspects. See [START_REF] Bandelt | Absolute reflexive retracts and absolute bipartite graphs[END_REF]. We also mention that some optimization problems, as the edge modification problem, have been already studied for the class of biclique-Helly graphs [START_REF] Burzyn | NP-completeness results for edge modification problems[END_REF].

None of the above classes are closed under induced subgraphs. So, a question would be to characterize the graphs for which the Helly property is preserved for every induced subgraph. It leads to the hereditary classes of clique-Helly, biclique-Helly, neighbourhood-Helly and disk-Helly graphs. Hereditary clique-Helly graphs have been characterized in [START_REF] Prisner | Hereditary clique-Helly graphs[END_REF], while [START_REF] Dragan | Centers of Graphs and the Helly property[END_REF] (see [START_REF] Brandstädt | Graph Classes. A survey[END_REF]) contains a characterization of hereditary disk-Helly graphs. In this work, we describe forbidden subgraph characterizations for the Denote by G a finite simple graph, with vertex set V (G) and edge set E(G).

For v i , v j ∈ V (G), write v i v j ∈ E(G)
to denote an edge with ends v i and v j . A complete set is a subset V ′ ⊆ V (G) formed by pairwise adjacent vertices while in an independent set V ′ ⊆ V (G) every pair of its vertices is not adjacent. Denote by α(G) the size of the largest independent set of G. A clique is a maximal complete set. A biclique is a subset B ⊆ V (G) inducing a maximal complete bipartite graph in G, having at least one edge. Denote by

N (v i ) = {v j ∈ V (G)|v i v j ∈ E(G)}, and N [v i ] = N (v i ) ∪ {v i }, the open and closed neighbourhoods of G, respectively. For each non-negative integer k and v i ∈ V (G), a disk D k (v i ) of v i is the set of vertices lying at distance at most k from v i . For V ′ ⊆ V (G), denote by G[V ′ ] the subgraph of G induced by V ′ . Let B be a set of bicliques of G.
Represent by G B the biclique subgraph of B, that is, the subgraph of G formed exactly by the vertices and edges of B.

Let F be a family of subsets of some set. Say that F is intersecting when the subsets of F pairwise intersect. On the other hand, when every intersecting subfamily of F has a common element then F is a Helly family. A graph G is clique-Helly when its family of cliques is Helly. Similarly, G is biclique-Helly (open neighbourhood-Helly, closed neighbourhood-Helly) when its family of bicliques (open neighbourhoods, closed neighbourhoods) is Helly. Also, say that G is disk-Helly when the family of disks

{D k (v i )|v i ∈ V (G) and 1 ≤ k < |V (G)|} is Helly.
Finally, G is hereditary clique-Helly when every of its induced subgraphs is clique-Helly. Similarly, define hereditary biclique-Helly, hereditary open neighbourhood-Helly, hereditary closed neighbourhood-Helly and hereditary disk-Helly graphs.

Hereditary clique-Helly graphs have been characterized as follows.

Theorem 1.1 [START_REF] Prisner | Hereditary clique-Helly graphs[END_REF]: A graph G is hereditary clique-Helly if and only if it does not contain as induced subgraphs the Hajós graph and any graph obtained from the latter by inserting some edges joining its vertices of degree 2.

The following is a characterization for hereditary disk-Helly graphs.

Theorem 1.2 [9]: A graph G is hereditary disk-Helly if and only if it is chordal and does not contain the Hajós graph as an induced subgraph.

In Section 2, we describe a characterization for hereditary biclique-Helly graphs while the proposed characterizations for hereditary open and closed neighborhood-Helly graphs are in Section 3. Relations among these classes are formulated in Section 4. Lemma 2.1 [START_REF] Groshaus | Biclique-Helly graphs[END_REF]: Let G be a graph with neither triangles nor C 5 's. Then each of its extensions is a bipartite graph.

Next, the characterization is formulated.

Theorem 2.1 : A graph G is hereditary biclique-Helly if and only if it does not contain any of the graphs of Figure 2, as induced subgraphs.

Proof: To prove that the graphs of Figure 2 are not biclique-Helly, we show a pairwise intersecting family B of bicliques with no common vertex, in each case. For the triangle,

B = {{v 1 , v 2 }, {v 1 , v 3 },{v 2 , v 3 }} and for the C 5 , B = {{v 1 , v 2 , v 3 }, {v 3 , v 4 , v 5 }, {v 1 , v 2 , v 5 }}. For the C 6 , the family is B = {{v 1 , v 2 , v 3 } , {v 3 , v 4 , v 5 }, {v 1 , v 5 , v 6 }}. Finally, for the graphs Q 1 , Q 2 and Q 3 , B = {{v 1 , w 2 , v 3 , v 4 }, {v 2 , v 3 , v 4 , w 1 },{v 3 , w 4 , v 1 , v 2 }, {v 1 , v 2 , v 4 , w 3 }}.
Conversely, let G be a graph that does not contain any of the graphs of Figure 2, as an induced subgraph. Suppose it is not hereditary biclique-Helly. Let H be an induced subgraph that is not biclique-Helly, and B a non-Helly family of bicliques of H. We can choose B = {B 1 , . . . , B k } as a minimal such family. Clearly, k ≥ 3. As for every i, B \ B i is a Helly family, there exists a vertex v i that belongs to B j and not to B i , for all j = i. Let S = {v 1 , . . . , v k } be the collection of such vertices. Write α S = α(H[S]).

First, we show that α S ≤ 2. Assume this condition to be false and let {v 1 , v 2 , v 3 } ⊆ S be an independent set of H. Since H has no triangles and v i ∈ B i , there exists a vertex w i ∈ B i adjacent to v j and not to v i , for j = i and 1 ≤ i ≤ 3. See Figure 3. Then {w 1 , w 2 , w 3 } is also an independent set. In the latter situation, {v 1 , w 2 , v 3 , w 1 , v 2 , w 3 } induces a C 6 , which is forbidden. Consequently, indeed α S ≤ 2.

In the sequel, we discuss the possible values k can assume. Let k ≥ 5. Denote S ′ = {v 1 , v 2 , v 3 , v 4 }. Clearly, S ′ ⊆ B 5 . For this reason and considering that α S ≤ 2, we know that S ′ induces a C 4 in H. Let v 1 v 3 and v 2 v 4 be the non-adjacent pairs in S ′ . Again, because α S ≤ 2, v 5 must be adjacent to at least one vertex of S ′ , say adjacent to v 1 . Because H has no triangles, v 5 can be adjacent neither to v 2 , nor to v 4 . However, in this situation, {v 2 , v 4 , v 5 } is an independent set of size 3, a contradiction. Consequently, k < 5.

Next, discuss the case k = 4. Let S ′ = {v 1 , v 2 , v 3 } ⊆ S. Since S ′ ⊆ B 4 and α S ≤ 2, S ′ induces a P 3 in H. Let v 1 and v 2 be the non-adjacent vertices in S ′ . As v 1 , v 2 , v 4 ∈ B 3 and α S ≤ 2, it follows that S must induce a C 4 in H. On the other hand, since v i ∈ B i and v j ∈ B i for j = i, each B i has an additional vertex w i ∈ B i , 1 ≤ i ≤ 4 with the following properties: because v 1 ∈ B 1 and H has no triangles, w 1 is adjacent to v 2 and not adjacent to v 1 , v 3 , v 4 . Similarly, w 2 is adjacent to v 1 , and not to v 2 , v 3 , v 4 , and w 3 is adjacent to v 4 and not v 1 , v 2 , v 3 , while w 4 is adjacent to v 3 and not v 1 , v 2 , v 4 . See Figure 4.

Let us examine the possible adjacencies among the w i 's. If w 1 and w 2 are adjacent, then H contains a C 5 , which is forbidden. Similarly, if w 3 and w 4 are adjacent. So, assume these pairs are not adjacent. Let W = {w 1 w 3 , w 1 w 4 , w 2 w 3 , w 2 w 4 } be the set of the other possible pairs of w i 's and denote

P = {v 1 , v 2 , v 3 , v 4 , w 1 , w 2 , w 3 , w 4 }. If none of the pairs of W is adjacent, then P induces the graph Q 1 .
When exactly one of the pairs of W is adjacent, then P forms the graph Q 2 . When precisely the pairs w 1 w 3 and w 2 w 4 , or w 1 w 4 and w 2 w 3 are adjacent, then P induces Q 3 . Finally, if at least two consecutive pairs of the cyclic sequence w 1 , w 4 , w 2 , w 3 , w 1 are adjacent in H, then a C 6 exists. Consequently, k = 4 is not possible.

Next, consider the case k = 3, and let S = {v 1 , v 2 , v 3 }. Denote by B S the subset of bicliques of H containing at least two vertices of S. Then {B 1 , B 2 , B 3 } ⊆ B S . Discuss the possibilities for S. Clearly, S is not a triangle. Since α S ≤ 2, S is not an independent set. Suppose S induces a P 3 , with v 1 , v 2 , adjacent. As v 2 , v 3 ∈ B 1 , there is a vertex w 1 ∈ B 1 adjacent to v 2 and v 3 . Similarly, there exists w 2 ∈ B 2 , with w 2 adjacent to v 1 and v 3 . In this case if w 1 , w 2 are adjacent, then a triangle is formed, otherwise {v 1 , v 2 , w 1 , v 3 , w 2 } induces a C 5 , which is forbidden.

Let us examine the remaining alternative, that is S induces a P 3 . By Lemma 1, H[S * ] is bipartite. Let X ∪ Y be a bipartition of it. Let v 1 , v 3 be the non-adjacent pair of vertices of S. Let v 1 , v 3 ∈ X and v 2 ∈ Y . Because v i ∈ B i and v j ∈ B i , for j = i, there is a vertex w i ∈ B i , w i = v j , where i, j ∈ {1, 3}, such that w 1 ∈ Y is adjacent to v 3 and not adjacent to v 1 and v 2 , while the vertex w 3 ∈ Y is adjacent to v 1 and not to v 3 and v 2 . Also, as B 2 is a biclique, there exists some vertex w 2 ∈ Y adjacent to v 1 and v 3 . Because v 2 ∈ B 2 , there is also a vertex w ′ 2 ∈ X ∩ B 2 that is adjacent to w 2 and not to v 2 . Since {B 1 , B 2 , B 3 } is not a Helly family, w 2 is not common to these three bicliques. Without loss of generality, assume w 2 / ∈ B 3 . Then there exists a vertex w ′ 3 ∈ X that belongs to B 3 , w ′ 3 adjacent to v 2 and w 3 , and not to w 2 . See Figure 5.

Let

P = {v 1 , v 2 , v 3 , w 1 , w 2 , w ′ 2 , w 3 , w ′ 3 } and W = {w 1 w ′ 2 , w 1 w ′ 3 , w 3 w ′ 2 }.
The pairs listed in W are the only possible edges, and then w 1 w ′ 3 or w ′ 2 w 3 creates a C 6 , and otherwise P induces a Q 3 or a Q 2 depending on the presence or absence of edge w 1 w ′ 2 . All cases lead to forbidden subgraphs. Consequently, k = 3 is not possible. However, k ≥ 3. This contradiction completes the proof.

✷

Hereditary open and closed neighbourhood Helly graphs

We describe below characterizations for the classes of hereditary open and closed neighbourhood-Helly graphs.

Theorem 3.1 Let G be a graph. Then G is hereditary open neighbourhood-Helly if and only if G contains neither C 6 nor a triangle as induced subgraphs.

Proof: Let G be a hereditary open neighbourhood-Helly graph. Clearly, no subset

{v 1 , v 2 , v 3 } ⊆ V (G) induces a triangle in G, otherwise N (v 1 ), N (v 2 ), N (v 3 ) pairwise intersect, but there is no common vertex. Suppose G contains a C 6 . Let v 1 , v 2 , v 3 , v 4 , v 5 , v 6
be the ordering of the vertices in this cycle. Since N (v 1 ), N (v 3 ), N (v 5 ) pairwise intersect with no common vertex, we conclude that G contains no C 6 .

Conversely, assume the theorem is not true. Then G contains an induced subgraph H that is not open neighbourhood-Helly. Consider a minimal family N = {N (v 1 ), N (v 2 ), ..., N (v l )} of pairwise intersecting neighbourhoods with no common vertex in H. Then l ≥ 3. Because of the minimality, there is a vertex w i ∈ N (v j ) precisely when i = j, for all 1 ≤ i ≤ l. Since v i / ∈ N (v i ), we conclude that w i = v j , for all i = j. Moreover, we show that w i = v i for all i. Suppose that the latter assumption is not true and let let w i = v i . Then, v i and v j are adjacent. On the other hand, since N (v i ) and N (v j ) intersect, there is a vertex w forming a triangle with v i and v j , which is forbidden by hypothesis. Consequently, w i = v j , for 1 ≤ i, j ≤ l. We claim that w 1 , ..., w l form an independent set in G. The latter is true because, if w i , w j are adjacent, the fact that w i , w j ∈ N (v k ), for k = i, j, implies that w i , w j , v k form a triangle of G, contradicting the hypothesis. Similarly, v 1 , ..., v l also form an independent set, otherwise v i ∈ N (v j ) implies that v i , v j , w k , k = i, j are vertices of a triangle. In this situation,

w i , w j , w k , v i , v j , v k induce a C 6 in G,
= {N [v 1 ], N [v 2 ], ..., N [v l ]
} a minimal such intersecting family of G with no common vertex. Clearly, l ≥ 3. By the minimality of l, there exist vertices w i , such that w i ∈ N [v j ], exactly for i = j. Compare w i and v j . It is clear that, v i = w i . Suppose w i = v j , for some i, j. Without loss of generality, let w 1 = v 2 . Then, v 1 , v 2 are not adjacent, implying v 1 = w 3 . The latter means that w 1 , w 2 = v 3 . In this situation, if v 1 , v 3 are adjacent, the vertices w 1 , w 3 , v 1 , v 3 induce a C 4 , which is forbidden. Consequently, v 1 , v 3 are not adjacent. Consider vertex w 2 . It follows that when w 2 , w 3 are adjacent, the vertices w 1 , w 3 , w 2 , v 3 induce a C 4 , and otherwise w 1 , w 3 , v 1 , w 2 , v 3 induce a C 5 in G. Hence, this alternative cannot occur. Finally, assume w i = v j , for all i, j. Since G contains no C 6 , {v 1 , v 2 , v 3 } and {w 1 , w 2 , w 3 } cannot be both independent sets. Suppose w 2 , w 3 are adjacent. Since G contains neither C 4 nor C 5 , we conclude that w 1 must be adjacent to both w 2 , w 3 . In this situation, if {v 1 , v 2 , v 3 } is an independent set, w 1 , w 2 , w 3 , v 1 , v 2 , v 3 induce the Hajós graph, otherwise, they induce a C 4 . In any alternative, a forbidden subgraph arises. The alternative v 2 , v 3 to be adjacent instead of w 2 , w 3 , is similar, terminating the proof. ✷

Relations among the classes

The hereditary classes here considered can be related by employing the characterizations formulated before. The following lemma is useful.

Corollary 4.1 A graph is hereditary open neighbourhood-Helly if and only if it is open neighbourhood-Helly and has no C 6 .

The next lemma relates hereditary closed neighbourhood-Helly graphs to the closed neighbourhood-Helly graphs.

Fig. 1 :

 1 Fig. 1: The Hajós graph

Fig. 2 :

 2 Fig.2: A hereditary biclique-Helly graph does not contain any of these graphs as induced subgraphs.2 Hereditary biclique-Helly graphsIn this section, we describe a characterization for hereditary biclique-Helly graphs. Start with the following definition. Let S ⊆ V (G), |S| = 3. Denote by B S the family of bicliques of G, each of them containing at least two vertices of S. Consider the graph G B S and denote its vertex set by S * ⊆ V (G). The induced subgraph G[S * ] is called the extension of S. Clearly, G B S is a spanning subgraph of G[S * ]. The lemma below is useful.

Fig. 4 :

 4 Fig. 3: k = 5

Fig. 5 :

 5 Fig. 5: k = 3

Lemma 4 . 1

 41 [START_REF] Groshaus | Biclique-Helly graphs[END_REF]: Let G be an open neighbourhood-Helly graph. Then G has no triangles. The corollary below relates hereditary open neighbourhood-Helly graphs to the open neighbourhood-Helly graphs. It is a consequence of Theorem 3.1 and Lemma 4.1.

Lemma 4 . 2

 42 Let G be a closed neighbourhood-Helly graph, with no triangles. Then G is hereditary closed neighbourhood-Helly.Proof: To prove that G is hereditary closed neighbourhood-Helly, we show that G does not contain contain C 4 , C 5 or C 6 as induced subgraphs. Assume the contrary, that is, G contains a C 4 as an induced subgraph. Consider the intersecting family {N [v i ]}, 1 ≤ i ≤ 4. By hypothesis, it has a common intersection which implies that a triangle is formed, a contradiction. Then, C 4 is not an induced subgraph of G. Similarly, suppose G contains a C 5 . The family of closed neighbourhoods of the five vertices of the C 5 intersects in a vertex, forming a triangle, again a contradiction. Finally, consider the closed neighbourhoods of the three mutually non-adjacent vertices of a C 6 . As they have a common vertex, there exists an induced C 4 or a triangle, a contradiction. ✷As a consequence of Lemma 4.2, we obtain the following relation between closed neighbourhood-Helly graphs and other hereditary Helly classes.

Corollary 4 . 2

 42 If G is closed neighbourhood-Helly with no triangles, then it is hereditary biclique-Helly, hereditary open neighbourhood-Helly and hereditary closed neighbourhood-Helly.Finally we can also conclude: Corollary 4.3 Let G be a graph with girth at least 7. Then G is hereditary biclique-Helly, hereditary open neighbourhood-Helly and hereditary closed neighbourhood-Helly.

  which is impossible. The proof is complete. ✷ Next we consider the closed neighbourhood-Helly class. Theorem 3.2 A graph G is hereditary closed neighbourhood-Helly if and only if it contains neither C 4 , C 5 , C 6 nor the Hajós graph as induced subgraphs. Proof: Suppose G contains the Hajós graph H. The family of the closed neighbourhoods of the three vertices with degree two in H is intersecting and has no common vertex. Consequently, G cannot contain the Hajós graph. Suppose G contains a C 4 . The family of closed neighbourhoods of its four vertices violates the Helly Property. Therefore, no C 4 ′ s can exist. Similarly, the families of the closed neighbourhoods of three vertices in a C 5 , two of them non-adjacent, and the closed neighbourhoods of the three mutually non-adjacent vertices in a C 6 , are both intersecting and have no common vertex. Consequently, G contains neither C 5 nor C 6 .Conversely, by hypothesis G contains neither the Hajós graph, nor any of C 4 , C 5 ,C 6 as induced subgraphs. Assume that the theorem is false and that G is not a hereditary closed neighbourhood-Helly graph. Denote by N

Acknowledgements

To Pavol Hell, for the helpful discussions on the subject.

Grants X036, X184, X127, PICT ANPCyT Grant 11-09112 and PID Conicet Grant, Argentina. ‡ Partially supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq, and Fundac ¸ão de Amparo à Pesquisa do Estado do Rio de Janeiro, FAPERJ, Brasil 1365-8050 c 2008


Hamamache Kheddouci
email: hkheddou@bat710.univ-lyon1.fr

Olivier Togni
email: olivier.togni@u-bourgogne.fr

Bounds for Minimum Feedback Vertex Sets in Distance Graphs and Circulant Graphs

Keywords: Feedback Vertex Set, Distance graph, Circulant graph. 1 Introduction

For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i -j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D.

The (infinite) distance graph P (D) with distance set D = {d 1 , d 2 , . . . , d k }, where d i being positive integers, has the set N of integers as vertex set, with two distinct vertices i, j ∈ N being adjacent if and only if |i -j| ∈ D. The finite distance graph P n (D) is the subgraph of P (D) induced by vertices 0, 1, . . . , n -1. Remark that there are nd i chords of length d i ≤ n in P n (D). Thus the number of edges of P n (D) is |E| = kn -k i=1 d i . The study of distance graphs was initiated by Eggleton et al. [START_REF] Eggleton | Coloring the real line[END_REF]. A large amount of work has focused on colorings of distance graphs [START_REF] Eggleton | Colouring prime distance graphs[END_REF][START_REF] Voigt | Colouring of distance graphs[END_REF][START_REF] Effantin | The b-chromatic number of some power graphs[END_REF].

The circulant graph can be defined as follows: let n be a natural number and let D = {d 1 , d 2 , . . . , d k }, with 1 ≤ d 1 < d 2 < . . . < d k ≤ n/2. Then the vertex set of the circulant graph C n (D) is {0, 1, . . . , n -1} and the set of neighbors of the vertex i is {(i ± d j ) mod n, j = 1, 2 . . . , k}. Circulant graphs (also called loop networks) have been widely studied for their interesting properties in terms of diameter, symmetry and connectivity. A survey paper about loop networks is given in [START_REF] Bermond | Distributed Loop Computer Networks: A Survey[END_REF].

To simplify, we will sometimes omit the brackets thus writing P n (d 1 , d 2 , . . . , d k ) (C n (d 1 , d 2 , . . . , d k ), respectively) instead of P n ({d 1 , d 2 , . . . , d k }) (C n ({d 1 , d 2 , . . . , d k }), respectively).

Notice that the distance graph P n (D) is a subgraph of the circulant graph C n (D). Using this fact, we will first find feedback vertex sets for finite distance graphs P n (D), for different values of D in Section 2 and then transform these results to find feedback vertex sets for circulant graphs C n (D) with the same sets D in Section 3.

Our main results are summarized in Table 1.

F (P n (D)) F (C n (D)) D Lower bound Upper bound Lower bound Upper bound {1, 2} ⌈ n-2 3 ⌉ ⌊ n+4 3 ⌋ {1, t} ⌈ n-t 3 ⌉ ⌈ n-2 3 ⌉ * ⌈ n+1 3 ⌉ ⌈ n+t 3 ⌉ + 1 {1, 2, 4} 4⌊ n 8 ⌋ ⌈ n 2 ⌉ 4⌊ n 8 ⌋ ⌈ n+4 2 ⌉ {1, s, t} ⌈ 2n-s-t 5 ⌉ ⌈ n 2 ⌉ ⌈ 2n+1 5 ⌉ ⌈ n+t 2 ⌉ {1, 2, 3, . . . , t} ⌊ n t+1 ⌋(t -1), if n ≡ 0, 1 mod (t + 1) n -2⌊ n t+1 ⌋ -2, otherwise n -2⌊ n t+1 ⌋ -1 * * n -2⌊ n t+1 ⌋ * * graph G ′ cannot be acyclic if m ′ ≥ n ′ i.e. if f < m-n+1 ∆-1
. Thus any FVS must have at least m-n+1

∆-1

vertices. ✷

2 Feedback vertex sets of distance graphs

2.1 D = {1, t}
Proposition 1 For any integer t ≥ 2,

F (P n (1, t)) =        0 if n ≤ t, n-t 2 if n 2 ≤ t < n, n+2 4 if n 3 ≤ t < n 2 .
Proof:

Let G = P n (1, t). If t ≥ n then G is a path. If n 2 ≤ t < n then the maximum degree of G is 2 if n = t + 1 and 3 otherwise. P t+1 (1, t) is a cycle, thus F (P t+1 (1, t)) = 1 = 1 2 . For n ≥ t + 2, applying Lemma 1 with m = 2n -t -1 gives F (P n (1, t)) ≥ n-t

2

. On the other hand, we construct a FVS V in this way: we skip the t first vertices and we pick alternately one on two of the nt last vertices (see Figure 1). More precisely, Note that the t first vertices of G do not induce any cycle and the nt remaining vertices have degree at most 1 in G \ V . So V is a FVS.

V = {t + 2i, 0 ≤ i < ⌈ n-t 2 ⌉}. 0 1 2 3 t-1 t t+1 0 removed vertices ⌈ n-t 2 ⌉ removed vertices
If n 3 ≤ t < n 2 , let n i be the number of vertices of degree i in G. It is clear that the first and the last vertices of G are of degree two, so n 2 = 2. Moreover, vertices 1, 2, . . . t -1 and nt, nt + 1, . . . , n -2 are of degree 3, thus n 3 = 2t -2. Therefore,

n 4 = n -n 3 -n 2 = n -2t.
Let V be a MFVS of G. Assume that the vertices of V are removed from G one by one in a certain order. Suppose that |V | = α + β, where α is the number of vertices that were of degree 4 just before they were removed (i.e. each removed vertex contributes to decrease the number of edges by 4) and β is the number of vertices that were of degree less than 4 just before they were removed (i.e. each removed vertex contributes to decrease the number of edges by 3 or less). Notice that these α vertices are of degree 4 in G and form an independent set. There are n 4 = n -2t vertices of degree 4 in G that are consecutive on the graph, thus α ≤ ⌈ n-2t 2 ⌉. Let n ′ (m ′ , respectively) be the number of vertices (edges, respectively) of

G ′ = G \ V . We have n ′ = n -α -β and m ′ ≥ |E(G)| -4α -3β = 2n -t -1 -4α -3β. As G ′ is a forest, we have m ′ ≤ n ′ -1 and thus 2n -t -1 -4α -3β ≤ n -α -β -1 or equivalently, 3α + 2β ≥ n -t.
As V is a MFVS, we want α + β to be minimized subject to the above constraints. In order to do so we must maximize α. Therefore the solution is given by setting α = ⌈ n-2t 2 ⌉ and β = ⌈ n-t-3α 2 ⌉. Thus

F (G) ≥ ⌈ n-2t 2 ⌉ + ⌈ n-t-3⌈ n-2t 2 ⌉ 2 ⌉ = ⌊ n+2
4 ⌋. Now, we have to construct a FVS of cardinality ⌊ n+2 4 ⌋: we begin, as for the case t < n ≤ 2t, by skipping the t first vertices and picking alternately one on two of the next t vertices. For the n -2t remaining vertices, if t is odd then we skip three vertices and pick one and so on for the last n -2t vertices (see Part a) of Figure 2) and if t is even, we skip one vertex then pick one, then skip three and pick one repetitively until the end (see Part b) of Figure 2).

More precisely,

V = {2i + t, 0 ≤ i ≤ t-1 2 } ∪ {2t + 3 + 4i, 0 ≤ i ≤ ⌊ n-2t-4
4 ⌋} for t odd and

V = {2i + t, 0 ≤ i ≤ t-2 2 } ∪ {2t + 1 + 4i, 0 ≤ i ≤ ⌊ n-2t-2 4 ⌋} for t even. Thus |V | = t-1 2 + 1 + ⌊ n-2t-4 4 ⌋ + 1 = ⌊ n+2 4 ⌋ for odd t and |V | = t-2 2 + 1 + ⌊ n-2t-2 4 ⌋ + 1 = ⌊ n+2 4 ⌋ for even t. t-1 t t+1 2t-1 2t 0 1 2 t-1 t t+1 2t-1 2t 0 1 2 Part a): t is odd Part b): t is even 0 0 ⌊ n-2t 4 ⌋ t 2 t+1 2 ⌊ n-2t-2 4 ⌋ + 1
Fig. 2: Structure of the FVS V (non filled circles represent vertices in the FVS).

The set V is a FVS because the first block of t vertices does not induce any cycle in G ′ = G \ V , vertices of the second block of t vertices are of degree 2 in G ′ and the third block of n -2t vertices induces disjoint subgraphs P 3 . Moreover, each P 3 consists in two vertices of even indices and one vertex of odd index and each vertex of the second block has the same parity as (t + 1). Hence, only the vertex of odd index of each P 3 is linked by a chord with a vertex of the second block. ✷ Proposition 2 For any n and any t, with t ≥ 2 and n ≥ t,

n -t 3 ≤ F (P n (1, t)) ≤ n -2 3 . Proof: Let G = P n (1, t).
The lower bound comes from Lemma 1 as G is of order n, size 2nt -1 and maximum degree at most 4.

For the upper bound, we cut the proof in two parts:

Case 1: t ≡ 0 mod 3. Let V = {3j -1, 1 ≤ j ≤ ⌊ n 3 ⌋} be the vertex set which we remove from G. By contradiction, suppose that G ′ = G \ V contains a cycle C.
Let i be the vertex of C of minimum index. Then vertex i must be adjacent to vertices i + 1 and i + t in C. We have i ≡ 2 mod 3 and i + 1 ≡ 2 mod 3 thus i ≡ 0 mod 3 and i + 2 cannot be a vertex of C. Therefore, vertex i + 1 must be adjacent to vertex i + t + 1 in C and thus C is a cycle of order 4 (see Figure 3). As t ≡ 0 mod 3, it turns out that either i+t ≡ 2 mod 3 or i+t+1 ≡ 2 mod 3, which is a contradiction.

Thus in that case, V is a FVS of G of cardinality |V | = ⌊ n 3 ⌋ = ⌈ n-2 3 ⌉.
Case 2: t ≡ 0 mod 3. Let q be the integer such that t = 3q. We are going to construct a FVS with a periodic pattern of period 2t: First observe that A j ∩ B j = ∅ for any j. Next, to prove that V is a FVS, as for the previous case, suppose that G \ V contains a cycle C. Let α be the vertex of C of minimum index. The neighbors of α on the cycle C are α + 1 and α + t; then the only cases to study are when α ∈ V , α + 1 ∈ V and α + t ∈ V . If, for some j, 0 ≤ j ≤ ⌈ n 2t ⌉ -1, the vertex α is of the form:

Let V = {x ∈ W , x ≤ n -1}, with W = ⌈ n 2t ⌉-1 j=0 (A j ∪ B j ), where A j = {2tj + 3i, 1 ≤ i ≤ q} and B j = {2tj + 3(q + i) -1, 1 ≤ i ≤ q}.
1. α = 2tj then α + t = 2tj + 3q ∈ V . 2. α = 2tj + 3i for some i, 1 ≤ i ≤ q then α ∈ V . 3. α = 2tj + 3i + 1 for some i, 0 ≤ i ≤ q -1, then α + 2 = 2tj + 3(i + 1) ∈ V ; the cycle C must be C = (α, α + 1, α + t + 1, α + t, α). But α + t + 1 = 2tj + 3(q + i) + 2 = 2tj + 3(q + i + 1) -1 ∈ V , a contradiction.
4. α = 2tj + 3i + 2 for some i, 0 ≤ i ≤ q -1 then α + 1 = 2tj + 3(i + 1) ∈ V .

5. α = (2j + 1)t + 3i for some i, 1 ≤ i ≤ q -1 then α + t = 2(j + 1)t + 3i ∈ V .

6. α = (2j + 1)t + 3i + 1 for some i, 0 ≤ i ≤ q -1 then α + 1 = 2tj + 3(q + i + 1) -1 ∈ V .

7. α = (2j + 1)t + 3i + 2 for some i, 0 ≤ i ≤ q -1 then α ∈ V . Now we have to show that |V | ≤ n 3 . By definition, we have |A j | = |B j | = q. Thus, on a period of 2t = 6q vertices, the feedback vertex set has cardinality 2q = 2t 3 . It remains to see that for the last

k vertices of G (k < 2t), at most k-2 3 of them are in V . If k ≤ t then ⌈ k-3
3 ⌉ of these k vertices are in V since in each set A j , we skip the three first vertices and then we pick one on three repetitively. If t < k < 2t then the number of removed vertices is q

+ ⌈ k-t-2 3 ⌉ = ⌈ k-2
3 ⌉ (since for the t + 1 first vertices we remove q of them and for the last kt -1 vertices, we skip one and then we pick one on three repetitively, thus removing ⌈ k-t-2 3 ⌉ of them). In both cases, we proved that V is a feedback set of cardinality at most n 3 = ⌈ n-2 3 ⌉, which proves the proposition. ✷

For the particular case t = 2, the previous proposition gives a sharp result:

Corollary 1 For any n ≥ 3,

F (P n (1, 2)) = n -2 3 .
We shall now give an algorithm to find another feedback set for P n (1, t). This new set has cardinality closer to the optimal for specific values of n compared to t.

Proposition 3 For any t ≥ 2, and any n > 3t, let t ′ = 2⌈ t 2 ⌉ and let r be the integer such that n ≡ r mod 3t ′ , 0 ≤ r < 3t ′ . Then

F (P n (1, t)) ≤ n-r 3 if 0 ≤ r ≤ t, ⌊ n 3 -t 6 ⌋ + 3 if t < r < 3t ′ . Proof: Let n = 3t ′ q + r, let G = P n (1, t), let G ′ = P 3t ′ q (1, t) and let G ′′ = P r (1, t).
The idea is to construct a periodic feedback set V ′ of period 3t ′ for the 3t ′ q first vertices of G (i.e. for G ′ ) and to use Proposition 1 to complete the FVS for the remaining r vertices (i.e. for G ′′ ). We now distinguish two cases depending on the parity of t.

If t is even then t ′ = t. The FVS is constructed as follows: cut the set of 3t consecutive vertices starting from vertex 0 in three blocks of size t, skip the first block, pick alternately one on two vertices of the second block and then again pick alternately one on two vertices of the last block, but starting from the second vertex of the block. Repeat the process for the next block of 3t vertices, and so on. An illustration of this method is given in Part a) of Figure 5.

Precisely, the FVS is defined by: Hence, the cardinality of V ′ satisfies |V ′ | = 2( t-2 2 + 1)q = tq = t ′ q = n-r 3 . To see that V ′ is a FVS, observe that in each block of 3t vertices, the first block B 1 of t vertices does not induce any cycle, and there is only one edge between the next block B 2 of t vertices and the last block B 3 of t vertices since the removed vertices are of different parity in B 2 and B 3 . Thus, no cycle in G \ V ′ can cross a block of 3t vertices. Furthermore, as the vertices of the block B 3 are of degree one except the first vertex who has degree 2, then they cannot form a cycle with the t first vertices of the next block of 3t vertices.

V ′ = q-1 j=0 {3tj + t + 2i, 0 ≤ i ≤ t -2 2 } ∪ {3tj + 2t + 2i + 1, 0 ≤ i ≤ t -2 2 } . 0 1 t-1 t t+1 2t-1 0 1 t-1 t t+1 2t-1 2t 3t 4t-1 2t 2t+1 2t+2 2t+3 3t+2 3t+3 3t-1 t/2 b) a) 0 0 0 t/2 (t+1)/2 (t+1)/2 0
If t is odd then t ′ = t + 1. The FVS is constructed as follows: take a block of 3t ′ = 3t + 3 consecutive vertices starting at vertex 0, skip the t first ones, pick alternately one on two of the next t vertices, skip three vertices and then again pick alternately one on two of the last t vertices. Repeat the process for the next block of 3t ′ vertices, and so on. An illustration of this method is given in Part b) of Figure 5.

Precisely, the FVS is defined by:

V ′ = q-1 j=0 {3t ′ j + t + 2i, 0 ≤ i ≤ t -1 2 } ∪ {3t ′ j + 2t + 2i + 3, 0 ≤ i ≤ t -1 2 } .
Hence, the cardinality of V ′ satisfies |V ′ | = 2( t-1 2 +1)q = t ′ q = n-r 3 . Among the three vertices between the first 2t vertices (block B 1 and B 2 ) and the last t vertices (block B 3 ) of any block of 3t ′ vertices, only one has degree 4 (but with two pendant edges incident to him) and the two other have degree 1. Moreover, removed vertices from the block B 2 and B 3 have the same parity. Thus, as the length of the chord is odd, there is no chordal edge between block B 2 and block B 3 . Consequently, no cycle can cross a block of 3t ′ vertices.

For 0 ≤ r ≤ t, G ′′ is a path and thus V ′′ = ∅ is a FVS. For t < r ≤ 3t, by Proposition 1, there exists a FVS V ′′ of G ′′ . If t is odd and 3t + 1 ≤ r ≤ 3t ′ -1 = 3t + 2 then we add the one or two last vertices of G ′′ in the FVS V ′′ .

To see that the set V = V ′ ∪ V ′′ is a FVS of G, it remains to show that no cycle is formed when making the union of G ′ \ V ′ and G ′′ \ V ′′ . In fact, for both even and odd t, among the last t -1 vertices of G ′ , the remaining vertices in G ′ \ V ′ are of degree 0. Therefore, only one chordal edge will link a vertex of degree greater than 0 in G ′ to a vertex of G ′′ and no cycle can be formed.

If 0 ≤ r ≤ t then V satisfies |V | = n-r 3 . If t < r ≤ 2t then |V | = n-r 3 + ⌈ r-t 2 ⌉ ≤ 2n-2r+3r-3t+6 6 ≤ n 3 -t 6 + 1 ≤ ⌊ n 3 -t 6 ⌋ + 3. If 2t < r < 3t ′ then |V | ≤ n-r 3 + ⌊ r+2 4 ⌋ + 2 ≤ 4n-4r+3r+6 12 + 2 ≤ n 3 -t 6 + 3. As |V | is an integer, then |V | ≤ ⌊ n 3 -t 6 ⌋ + 3. ✷ Remark 1
The result of Proposition 3 is sharp when n ≡ t mod 3t ′ , with t ′ = 2⌈ t 2 ⌉. We have then

F (P n (1, t)) = n-t 3 .

D = {1, s, t}

Proposition 4 For any integers n, s and t, with t ≤ n -1 and 2 ≤ s < t,

2n -s -t 5 ≤ F (P n (1, s, t)) ≤ n 2 .
Proof: Let G = P n (1, s, t). Notice that, for any d ∈ D, there are exactly nd chords of length d in P n (D). Thus the lower bound comes from Lemma 1 as G is of order n, size 3nst -1 and maximum degree 6.

To prove the upper bound we will discuss two cases. In each one, we remove a vertex set from G which generates a feedback.

Case 1: s or t is odd. Let V = {2j + 1, 0 ≤ j ≤ ⌊ n-2
2 ⌋} be the vertex set which we remove from G. As a chord of odd length always joins two vertices of different parity and as we remove all vertices of odd index, then the subgraph induced by V \ V is either an independent set (if both s and t are odd) or a disjoint union of paths. So V is a FVS and |V | = ⌊ n ⌋. Case 2: s and t even.

For each k, 1 ≤ k ≤ n t , if k is even we remove from G the set V k = {u = 2j + 1 + (k -1)t, u ≤ n -1, 0 ≤ j ≤ t-2 2 }, otherwise we remove V k = {u = 2j + (k -1)t, u ≤ n -1, 0 ≤ j ≤ t-2
2 }. See Figure 6 for an illustration when s = 4 and t = 6. One can see that, as s and t are even, the chords of length s or t of G always join vertices of the same parity. Moreover, as we remove alternately odd and even vertices by blocks of t vertices, all chords of length t are removed and all chords of length s between two consecutive blocks of t vertices are removed too. Thus in each block we obtain a forest and since chords of length one are all removed except those between some consecutive blocks, the set V = k V k is a FVS.

Notice that we have |V k | = t 2 and |V | ≤ ⌈ n 2 ⌉ since in each block of t vertices, we alternately remove one vertex on two starting from the first or the second vertex of the block. ✷ Proposition 5 For any integer n ≥ 4

4 n 8 ≤ F (P n (1, 2, 4)) ≤ n 2 .
Proof: To prove the lower bound, let V be any FVS of G = P n (1, 2, 4). Consider the first 6 vertices of G. Note that three consecutive vertices in G form a cycle. Thus we have two cases to study: if only two vertices over the six are in V , then the only possibility is to remove vertices 1 and 4 (see Figure 7). But in this case, the two following vertices (6 and 7) must be in V , otherwise a cycle is produced. Then, among the 8 first vertices of G, 4 of them are in V . If three or more vertices among the first 6 one are in V then half or more than half of the vertices are removed on this part of G. Therefore, on the first six or eight vertices of G, at least half of them are in V . Next, iterating this process on the six next vertices of G and so on until the end of the graph, we obtain the desired lower bound. Proof: Let G = P n ({1, 2, . . . , t}) and let n = p(t + 1) + q, with 0 ≤ q < t + 1 and p ≥ 1.

The subgraphs G i , 0 ≤ i ≤ p -1 of G induced by vertices {(t + 1)i + j, 0 ≤ j ≤ t} and G p induced by vertices {p(t + 1) + j, 0 ≤ j ≤ q -1} are cliques. So any FVS of G must contain at least t -1 vertices of each G i , 0 ≤ i ≤ p -1 and at least q -2 vertices of

G p if q ≥ 2. Thus, if q ≤ 1 then F (G) ≥ p(t -1) = ⌊ n t+1 ⌋(t -1), otherwise, F (G) ≥ p(t -1) + q -2 = p(t + 1) + q -2p -2 = n -2⌊ n t+1 ⌋ -2.
To show the equality, we give a FVS with the desired number of vertices (see Figure 8):

V = {i + k(t + 1), 2 ≤ i ≤ t, 0 ≤ k ≤ p -1} ∪ {p(t + 1) + i, 2 ≤ i ≤ q -1}.
By construction, there is only one chord between two consecutive blocks of (t + 1) vertices (a chord of length t between the second vertex of the block and the first vertex of the next block). Thus the graph G \ V is a path. Moreover, we have

|V | = p(t -1) if q ≤ 1 and |V | = p(t -1) + q -2 if q ≥ 2. ✷ 1
V = {2j + 1, 0 ≤ j ≤ n-2 2 } is a feedback vertex set.
3 Feedback vertex sets of circulant graphs

In this section, we shall always assume that t ≤ n 2 .

Proposition 7 Let n be an integer and let D ⊂ Z n and m ≥ max d∈D {d}. Then

F (P n (D)) ≤ F (C n (D)) ≤ F (P n-m (D)) + m.
Proof: The lower bound is trivial as P n (D) is a partial subgraph of C n (D). For the upper bound, if we cut m consecutive vertices of C n (D), we obtain a graph isomorphic to P n-m (D). As m ≥ max d∈D {d}, no chord can cross this block of m vertices. Thus it is sufficient to add these m vertices to a MFVS of P n-m (D) to obtain a FVS of the circulant graph C n (D). ✷

D = {1, t}

Proposition 8 For any n ≥ 5 and t < n 2 ,

n + 1 3 ≤ F (C n (1, t)) ≤ ⌈ n+t 3 ⌉ + 1 if t ≡ 0 mod 3, ⌈ n+t 3 ⌉ if t ≡ 0 mod 3. Proof: Let G = C n (1, t).
The lower bound comes from Lemma 1 as G is of order n, size 2n and maximum degree 4. In order to prove the upper bound, we consider the circulant graph as a distance graph plus some vertices and edges: Let B be the subgraph of G induced by vertices t, t + 1, . . . , n -1. B is the distance graph P n-t (1, t) and since nt > t, by Proposition 2, there exists a FVS V B of B of size ⌈ n-t-2 3 ⌉. A FVS V G for G can be constructed by adding to V B a subset N of the remaining t vertices 0, 1, . . . , t -1: N = {j, 0 ≤ j ≤ t -1, (j + t) ∈ V B }. Then V G = V B ∪ N .

B \ V B induces a forest in G and by the choice of N , there is no edge between a vertex of the first block of t vertices and a vertex of the second block of t vertices. Moreover, as it can be seen in the proof of Proposition 2, no two consecutive vertices of P n-t (1, t) are in V B . Thus, among the t first vertices of G, at least one of any two consecutive vertices is in N . Consequently, there is no possibility to form a cycle since the t first vertices of G become of degree at most one.

Conclusion

We have derived several bounds for the cardinality of a minimum feedback vertex set of distance and circulant graphs. The approximation ratios of our algorithms are in many cases equal or asymptotically close to one for circulant graphs and for distance graphs with chords of length at most half the number of vertices.

For isomorphism reasons, our results concerning circulant graphs defined by the set D = {1, t} can also be applied to many other circulants of degree 4. For instance, the following isomorphism is easy to observe: if gcd(d 1 , n) = 1 or gcd(d 2 , n) = 1 then there exists t such that C n (d 1 , d 2 ) ≡ C n (1, t).

Fig. 1 :

 1 Fig. 1: Structure of the FVS V (non filled circles represent vertices in the FVS).

Fig. 3 :

 3 Fig. 3: The cycle C

  Figure4gives an example of such a set.

Fig. 4 :

 4 Fig. 4: FVS in P24(1, 6) (non filled circles represent vertices in the FVS)

Fig. 5 :

 5 Fig. 5: Structure of the FVS V ′ for even t on Part a) and for odd t on Part b)

Fig. 6 :

 6 Fig. 6: A FVS of Pn(1, 4, 6).

Fig. 7 :

 7 Fig. 7: The graph P6(1, 2, 4) with two vertices removed. The three configurations on the top of the figure produce a cycle.

  For the general distance graph F (P n (d 1 , d 2 , . . . , d t )) and for any n ≥ 5 and 1 ≤ d 1 < d 2 < . . . < d t , with d t ≤ n -1 and at most one d i even, we have that F (P n (d 1 , d 2 , . . . , d t )) ≤ n 2 . Effectively, if we remember that a chord of odd length always joins vertices of different parity, we can see that the set

	0	2	3	t	t+1	2t+2
				Fig. 8: A FVS of Pn(1, 2, 3, . . . , t)
	Remark 2

  Remark 3 From Proposition 7 and Remark 2, the following can be easily obtained: for any n ≥ 5 and1 ≤ d 1 < d 2 < . . . < d t , with d t ≤ n-1 2 , i) if n is even and if all d i are odd, then F (C n (d 1 , d 2 , . . . , d t )) ≤ n 2 , ii) ifn is odd and if all d i are odd, then F (C n (d 1 , d 2 , . . . , d t )) ≤ n+dt 2 , iii) if n is even and if there exists only one even d i , with 1 ≤ i ≤ t, then F (C n (d 1 , d 2 , . . . , d t )) ≤ n+di

2

.

Acknowledgements

We wish to thank the anonymous referees for helpful comments that allow to improve the paper.

Moreover, by the construction of V B (see proof of Proposition 2), if t ≡ 0 mod 3 then we have

For the special case t = 2, the previous proposition gives a quasi optimal result. The exact value is determined in the following proposition:

Proposition 9 For any n ≥ 4, we have

3 ⌉, thus Proposition 8 gives the result. So let us study the case where n = 3k + 2. The proof is done by contradiction. Assume that

Then there exists a subset of vertices, say S, such that the induced subgraph G \ S is a forest. Give a clockwise orientation to the cycle C = C n (1). Let S = {s 0 , s 1 , . . . , s q-1 }, with 1 ≤ q ≤ k + 1 such that these vertices hold in this order on C. Let s + i (s - i , respectively) be the successor (predecessor, respectively) of vertex s i in C n with respect to the orientation (indices are taken modulo q).

Denote by C i the part of cycle given by the segment (s + i Cs - i+1 ). Suppose first that there exists 0 ≤ j ≤ q -1, such that the edge

Now suppose that for all 0 ≤ i ≤ q -1, |C i | > 0. Observe that there does not exist C j , with 0 ≤ j ≤ q -1, such that |C j | ≥ 3, otherwise we obtain a cycle of size 3. We deduce that for each i, 0 ≤ i ≤ q -1, we have 1 ≤ |C i | ≤ 2. It means that it is possible, in this case, to construct a cycle which passes by each C i by taking all vertices of each segment: let x i and y i be the vertices of C i , where

Then the cycle is given by (x 0 , y 0 , x 1 , y 1 , . . . , x q-1 , y q-1 , x 0 ). Therefore G \ S is not a forest, a contradiction. Then any MFVS has cardinality at least k + 2 = ⌈ n+2 3 ⌉. Thus, Proposition 8 gives

If n = 2p is even and t = n 2 = p, then the circulant graph C 2p (1, p) is cubic. In that case, it is easy to compute the cardinality of a MFVS.

Proposition 10 for any p ≥ 2,

. , t}

Proposition 12 For any n ≥ 5 and 3 ≤ t ≤ n-1 2 , let p and q be integers such that n = p(t + 1) + q, q < t + 1. Then

Proof: Let G = C n (1, 2, . . . , t) and let n = (t + 1)p + q, with q < t + 1. We cut up the vertices of G successively into p + 1 sets of vertices, in other words we have B i = {(i(t + 1), i(t + 1) + 1, . . . , (i + 1)(t + 1) -1}, for 0 ≤ i ≤ p -1, and B p = {p(t + 1), p(t + 1) + 1, . . . , p(t + 1) + q -1}.

As |B i | ≤ t + 1, any subgraph of G induced by B i , for 0 ≤ i ≤ p, is a clique. Thus any triplet of vertices of this subgraph forms a cycle. So a FVS in this case must contain at least t -1 vertices of each set B i , for 0 ≤ i ≤ p -1 and q -2 vertices of B p if q ≥ 2.

However, there is still a "big" cycle since if it remains two vertices in each block B i (one vertex in B p if q = 1), then there is at least an edge between any two successive blocks. Thus any FVS must contain an extra vertex.

Consequently, if q = 0 then we have

We construct a FVS V by taking the t -1 first vertices of each B i , with 0 ≤ i ≤ p -1, and the q vertices of B p . By construction, there is only one chord between two consecutive blocks (the chord of length t joining the last vertex of the first block with the last but one vertex of the next block). If q = 0 then G \ V is the path P = (t -1, t, 2t, 2t + 1, 3t + 1, 3t + 2, . . . , p(t + 1) -2, p(t + 1) -1). Otherwise, if q = 0 then G \ V consists in the cycle C = P ∪ {p(t + 1) -1, t -1}. In this case, we add any vertex of the cycle C to V .

Observe that if q = 0 then |V | ≤ p(t-1)+1 = n-2p+1 and if q ≥ 1 then |V | ≤ p(t-1)+q = n-2p. Hence we obtain the desired result. ✷


Sergey Kitaev

Toufik Mansour

Jeff Remmel

Counting descents, rises, and levels, with prescribed first element, in words

Keywords: descent, level, rise, set partition, word, composition, multivariate generating function

Recently, Kitaev and Remmel refined the well-known permutation statistic "descent" by fixing parity of one of the descent's numbers which was extended and generalized in several ways in the literature. In this paper, we shall fix a set partition of the natural numbers N, (N1, . . . , Ns), and we study the distribution of descents, levels, and rises according to whether the first letter of the descent, rise, or level lies in Ni over the set of words over the alphabet [k] = {1, . . . , k}. In particular, we refine and generalize some of the results by Burstein and Mansour.

Introduction

The descent set of a permutation π = π 1 • • • π n ∈ S n is the set of indices i for which π i > π i+1 . This statistic was first studied by MacMahon [START_REF] Macmahon | Combinatory Analysis[END_REF] almost a hundred years ago and it still plays an important role in the field of permutation statistics. The number of permutations of length n with exactly m descents is counted by the Eulerian number A m (n). The Eulerian numbers are the coefficients of the Eulerian polynomials A n (t) = π∈Sn t 1+des (π) . It is well-known that the Eulerian polynomials satisfy the identity m≥0 m n t m = An(t)

(1-t) n+1 . For more properties of the Eulerian polynomials see [START_REF] Comtet | Advanced Combinatorics[END_REF]. Recently, Kitaev and Remmel [START_REF] Kitaev | Classifying descents according to parity[END_REF] studied the distribution of a refined "descent" statistic on the set of permutations by fixing parity of (exactly) one of the descent's numbers. For example, they showed that the number of permutations in S 2n (resp. S 2n+1 ) with exactly k descents such that the first entry of the descent is an even number is given by n k 2 n! 2 (resp. 1 k+1 n k 2 (n + 1)! 2 ). In [START_REF] Kitaev | Classifying Descents According to Equivalence mod k[END_REF], the authors generalized results of [START_REF] Kitaev | Classifying descents according to parity[END_REF] by studying descents according to whether the first or the second element in a descent pair is congruent to 0 mod k ≥ 2.

Subsequently, Hall and Remmel [START_REF] Hall | Counting descent pairs with prescribed tops and bottoms[END_REF] generalized results of [START_REF] Kitaev | Classifying Descents According to Equivalence mod k[END_REF] by considering "X, Y -descents," which are descents whose "top" (first element) is in X and whose "bottom" (second element) is in Y where X and Y are any subsets of the natural numbers N. In particular, Hall and Remmel [START_REF] Hall | Counting descent pairs with prescribed tops and bottoms[END_REF] showed that one can reduce the problem of counting the number of permutations σ with k X, Y -descents to the problem of computing the k-th hit number of a Ferrers board in many cases. Liese [START_REF] Liese | Classifying ascents and descents with specified equivalences mod k[END_REF] also considered the situation of fixing equivalence classes of both descent numbers simultaneously. Also, papers [START_REF] Hall | q-analogues of formulas counting descent pairs with prescribed tops and bottoms[END_REF] and [START_REF] Liese | q-analogues of formulas f or the number of ascents and descents with specified equivalences mod K, Permutation Patterns Conference[END_REF] discuss q-analogues of some of the results in [START_REF] Hall | Counting descent pairs with prescribed tops and bottoms[END_REF][START_REF] Kitaev | Classifying descents according to parity[END_REF][START_REF] Kitaev | Classifying Descents According to Equivalence mod k[END_REF][START_REF] Liese | Classifying ascents and descents with specified equivalences mod k[END_REF].

Hall and Remmel [START_REF] Hall | Counting descent pairs with prescribed tops and bottoms[END_REF] extended their results on counting permutations with a given number of X, Ydescents to words. That is, let R(ρ) be the rearrangement class of the word 1 ρ1 2 ρ2 • • • m ρm (i.e., ρ 1 copies of 1, ρ 2 copies of 2, etc.) where ρ 1 + • • • + ρ m = n. For any set X ⊆ N and any set [m] = {1, 2, . . . , m}, we let X m = X ∩ [m] and X c m = [m] -X. Then given X, Y ⊆ N and a word w Hall and Remmel [START_REF] Hall | Counting descent pairs with prescribed tops and bottoms[END_REF] proved the following theorem by purely combinatorial means.

= w 1 • • • w n ∈ R(ρ), define Des X,Y (w) = {i : w i > w i+1 & w i ∈ X & w i+1 ∈ Y },
β Y,ρ,x = z / ∈ Y 1 ≤ z < x ρ z .
In this paper, we shall study similar statistics over the set [k] n of n-letter words over a fixed finite alphabet [k] = {1, 2, . . . , k}. In what follows, E = {2, 4, 6, . . .} and O = {1, 3, 5, . . .} are the sets of even and odd numbers respectively. Also, we let x[t] = (x 1 , . . . , x t ). Then given a word π = π 1 π 2 . . . π n ∈ [k] n and a set X ⊆ N, we define the following statistics:

• ← -- Des X (π) = {i : π i > π i+1 and π i ∈ X} and ← - des X (π) = | ← -- Des X (π)|, • ← - Ris X (π) = {i : π i < π i+1 and π i ∈ X} and ← - ris X (π) = | ← - Ris X (π)|, • Lev X (π) = {i : π i = π i+1 and π i ∈ X} and lev X (π) = | Lev X (π)|.
Let (N 1 , . . . , N s ) be a set partition of the natural numbers N, i.e. N = N 1 ∪ N 2 ∪ . . . ∪ N s , N i = ∅ for all i, and N i ∩ N j = ∅ for i = j. Then the main goal of this paper is to study the following multivariate generating function (MGF)

A k = A k (x[s]; y[s]; z[s]; q[s]) = π s i=1 x ← - des N i (π) i y ← - ris N i (π) i z lev N i (π) i q i(π) i (1.2)
where i(π) is the number of letters from N i in π and the sum is over all words over [k].

The outline of this paper is as follows. In Section 2, we shall develop some general methods to compute (1.2). In Section 3, we shall concentrate on computing generating functions for the distribution of the number of levels. That is, we shall study A k where set x i = y i = 1 for all i. In Section 4, we shall find formulas for the number of words in [k] n that have s descents that start with an element less than or equal to t (greater than t) for any t ≤ k. Note that if we replace a word

w = w 1 • • • w n ∈ [k] n by its complement w c = (k + 1 -w 1 ) • • • (k + 1 -w n ), then it is easy to see that ← - des [t] (w) = ← - ris {k+1-t,...,k} (w)
and ←des {t+1,...,k} (w) = ←ris [k-t] (w). Thus we will also obtain formulas for the number of words in [k] n that have s rises that start with an element less than or equal to t (greater than t) for any t ≤ k. In Section 5, we shall apply our results to study the problem of counting the number of words in [k] n with p descents (rises) that start with an element which is congruent to i mod s for any s ≥ 2 and i = 1, . . . , s. In particular, if s ≥ 2 and (N 1 , . . . , N s ) is the set partition of N where N i = {x ∈ N : x ≡ i mod s} for i = 1, . . . , s, then we shall study the generating functions

A (s) k (x[s]; y[s]; z[s]; q[s]) = π s i=1 x ← - des N i (π) i y ← - ris N i (π) i z lev N i (π) i q i(π) i (1.3) and A (s) k (x[s]; y[s]; z[s]; q) = π q |π| s i=1 x ← - des N i (π) i y ← - ris N i (π) i z lev N i (π) i .
(1.4)

Our general results in Section 2 allow us to derive an explicit formula for

A (s) k (x[s]; y[s]; z[s]; q[s]
) depending on the equivalence class of k mod s.

For example, in the case where s = 2, our general result implies that

A (2) 2k (q 1 , q 2 ) = A k (x 1 , x 2 , y 1 , y 2 , z 1 , z 2 , q 1 , q 2 ) = (1.5) = π x ← - des O (π) 1 x ← - des E (π) 2 y ← - ris O (π) 1 y ← - ris E (π) 2 z lev O (π) 1 z lev E (π) 2 q odd(π) 1 q even(π) 2 = 1 + (λ 1 µ 2 + λ 2 ) 1-µ k 1 µ k 2 1-µ1µ2 1 -(ν 1 µ 2 + ν 2 ) 1-µ k 1 µ k 2 1-µ1µ2
where the sum is over all words over [2k], even(π) (resp. odd(π)) is the number of even (resp. odd) numbers in π, λ j = qj (1-yj )

1-qj (zj -yj ) , µ i = qi(zi-xi) 1-qi(zi-yi) , and ν j = qj yj 1-qj (zj -yj ) for j = 1, 2. Then by specializing the variables appropriately, we will find explicit formulas for the number of words w ∈ (-1) n+p+i 2 j j ki i n nj p .

[2k] n such that ← - des E (π) = p, ← - des O (π) = p, ← - ris E (π) = p, ← - ris O (π) = p,
In fact, we shall show that similar formulas hold for the number of words π ∈ [k] n with p descents (rises, levels) whose first element is congruent to t mod s for any s ≥ 2 and 0 ≤ t ≤ s -1. Our results refine and generalize the results in [START_REF] Burstein | Counting occurrences of some subword patterns[END_REF] related to the distribution of descents, levels, and rises in words. Finally, in Section 6, we shall discuss some open questions and further research.

The general case

We need the following notation:

A k (i 1 , . . . , i m ) = A k (x[t]; y[t]; z[t]; q[t]; i[m]) = π t i=1 x ← - des N i (π) i y ← - ris N i (π) i z lev N i (π) i q i(π) i
where the sum is taken over all words π = π

1 π 2 • • • over [k] such that π 1 • • • π m = i 1 • • • i m .
From our definitions, we have that

A k = 1 + k i=1 A k (i). (2.1)
Thus, to find a formula for A k , it is sufficient to find a formula for A k (i) for each i = 1, 2, . . . , k. First let us find a recurrence relation for the generating function A k (i).

Lemma 2.1 For each s ∈ N i , 1 ≤ s ≤ k and 1 ≤ i ≤ t, we have

A k (s) = q i y i 1 -q i (z i -y i ) A k + q i (1 -y i ) 1 -q i (z i -y i ) + q i (x i -y i ) 1 -q i (z i -y i ) s-1 j=1 A k (j).
(2.2)

Proof: From the definitions we have that

A k (s) = q i + k j=1 A k (s, j) = q i + s-1 j=1 A k (s, j) + A k (s, s) + k j=s+1 A k (s, j).
Let π be any n-letter word over [k] where n ≥ 2 and

π 1 = s > π 2 = j. If we let π ′ = π 2 π 3 . . . π n , then it is easy to see that ← - des Ni (π) = 1 + ← - des Ni (π ′ ), i(π) = 1 + i(π ′ ).
It is also easy to see that remaining 4t -2 statistics of interest take the same value on π and π ′ .

This implies that A k (s, j) = q i x i A k (j) for each 1 ≤ j < s. Similarly, A k (s, s) = q i z i A k (s) and A k (s, j) = q i y i A k (j) for s < j ≤ k. Therefore,

A k (s) = q i + q i x i s-1 j=1 A k (j) + q i z i A k (s) + q i y i k j=s+1 A k (j).
Using (2.1), we have

k j=s+1 A k (j) = A k - s-1 j=1 A k (j) -A k (s) -1, and thus A k (s) = q i y i 1 -q i (z i -y i ) A k + q i (1 -y i ) 1 -q i (z i -y i ) + q i (x i -y i ) 1 -q i (z i -y i ) s-1 j=1 A k (j), as desired. ✷ Lemma 2.2 For each k ≥ 1 and s ∈ [k], s j=1 A k (j) = s j=1 γ j s i=j+1 (1 -α i ) (2.3)
where, for i ∈ N m and i ≥ 1,

γ i = qmym 1-qm(zm-ym) A k + qm(1-ym) 1-qm(zm-ym) and α i = qm(ym-xm) 1-qm(zm-ym) .
Proof: We proceed by induction on s. Note, that given our definitions of γ i and α i , we can rewrite (2.2) as

A k (s) = γ s -α s s-1 j=1
A k (j).

(2.4)

It follows that A k (1) = γ 1
so that (2.3) holds for s = 1. Thus the base case of our induction holds. Now assume that (2.3) holds for s where 1 ≤ s < k. Then using our induction hypothesis and (2.4), it follows that

A k (1) + • • • + A k (s) + A k (s + 1) = s j=1 γ j s i=j+1 (1 -α i ) + γ s+1 -α s+1   s j=1 γ j s i=j+1 (1 -α i )   = γ s+1 - s j=1 γ j s+1 i=j+1 (1 -α i ) = s+1 j=1 γ j s+1 i=j+1 (1 -α i ).
Thus the induction step also holds so that (2.3) must hold in general. ✷ Lemma 2.1 gives that the A k (i)'s, for 1 ≤ i ≤ k, are the solution to the following matrix equation

         1 0 0 0 0 . . . 0 α 2 1 0 0 0 . . . 0 α 3 α 3 1 0 0 . . . 0 α 4 α 4 α 4 1 0 . . . 0 . . . . . . . . . α k α k α k α k α k . . . 1          •      A k (1) A k (2) . . . A k (k)      =      γ 1 γ 2 . . . γ k      , (2.5)
where, for i ∈ N m and i ≥ 1,

γ i = qmym 1-qm(zm-ym) A k + qm(1-ym)
1-qm(zm-ym) , and, for i ∈ N m and i ≥ 2,

α i = qm(ym-xm)
1-qm(zm-ym) . Notice that α i = α j and γ i = γ j whenever i and j are from the same set N m for some m. In fact, it is easy to see that (2.2) and (2.3) imply that

A k (i) = γ i -α i i-1 j=1 γ j i-1 i=j+1 (1 -α i ) (2.6)
holds for i = 1, . . . , k so that (2.5) has an explicit solution. By combining (2.1) and (2.6), we can obtain the following result.

Theorem 2.3 For α i and γ i as above (defined in Lemma 2.2), we have

A k = 1 + k j=1 γ j k i=j+1 (1 -α i )
solving which for A k gives

A k = 1 + k j=1 qj (1-yj ) 1-qj (zj -yj ) k i=j+1 1-qi(zi-xi) 1-qi(zi-yi) 1 - k j=1 qj yj 1-qj (zj -yj ) k i=j+1 1-qi(zi-xi) 1-qi(zi-yi) (2.7)
where for each variable a ∈ {x, y, z, q} we have

a i = a m if i ∈ N m .
Even though we state Theorem 2.3 as the main theorem in this paper, its statement can be (easily) generalized if one considers compositions instead of words (see [START_REF] Heubach | Counting rises, levels, and drops in compositions[END_REF]). Indeed, let

B k = B k (x[t]; y[t]; z[t]; q[t]; v) = π v |π| t i=1 x ← - des N i (π) i y ← - ris N i (π) i z lev N i (π) i q i(π) i
where the sum is taken over all

compositions π = π 1 π 2 • • • with parts in [k] and |π| = π 1 + π 2 + • • • is the weight of the composition π. Also, we let B k (i 1 , . . . , i m ) = B k (x[t]; y[t]; z[t]; q[t]; i[m]; v) = π v |π| t i=1 x ← - des N i (π) i y ← - ris N i (π) i z lev N i (π) i q i(π) i
where again the sum is taken over all compositions π = π

1 π 2 • • • with parts in [k].
Next, one can copy the arguments of Lemma 2.1 substituting q i by v s q i to obtain the following generalization of Lemma 2.1:

B k (s) = v s q i y i 1 -q i (z i -y i ) B k + v s q i (1 -y i ) 1 -q i (z i -y i ) + v s q i (x i -y i ) 1 -q i (z i -y i ) s-1 j=1 B k (j).
One can then prove the obvious analogue of Lemma 2.1 by induction and apply it to prove the following theorem.

Theorem 2. [START_REF] Burstein | Counting occurrences of some subword patterns[END_REF] We have

B k = 1 + k j=1 γ j k i=j+1 (1 -α i )
where

γ i = v i qmym 1-qm(zm-ym) B k + v i qm(1-ym)
1-qm(zm-ym) , and

α i = v i qm(ym-xm) 1-qm(zm-ym) if i belongs to N m . Thus, B k = 1 + k j=1 v j qj (1-yj ) 1-qj (zj -yj ) k i=j+1 1-qi(zi-yi+v i (yi-xi)) 1-qi(zi-yi) 1 - k j=1 v j qj yj 1-qj (zj -yj ) k i=j+1 1-qi(zi-yi+v i (yi-xi)) 1-qi(zi-yi)
where for each variable a ∈ {x, y, z, q} we have

a i = a m if i ∈ N m .
Theorem 2.4 can be viewed as a q-analogue of Theorem 2.3.

(Set v = 1 in Theorem 2.4 to get Theo- rem 2.3.)
3 Counting words by the types of levels Suppose we are given a set partition

N = N 1 ∪ N 2 ∪ • • • ∪ N s .
First observe that for any fixed i, if we want the distribution of words in [k] n according to the number of levels which involve elements in N i , then it is easy to see by symmetry that the distribution will depend only on the cardinality of

N i ∩ [k].
Thus we only need to consider the case where s = 2 and N 1 = {1, . . . , t} for some t ≤ k. Let

λ j = q j (1 -y j ) 1 -q j (z j -y j ) , (3.1)
ν j = q j y j 1q j (z jy j )

, and (3.2)

µ i = 1 -q i (z i -x i ) 1 -q i (z i -y i ) . (3.3)
Then we can rewrite (2.7) for any arbitrary set partition

N = N 1 ∪ N 2 ∪ • • • ∪ N s as A k = 1 + k j=1 λ j k i=j+1 µ i 1 - k j=1 ν j k i=j+1 µ i (3.4)
where for each variable a ∈ {x, y, z, q}, we have

a i = a m if i ∈ N m .
Suppose we set x 1 = x 2 = y 1 = y 2 = z 2 = 1 and q 1 = q 2 = q in (3.4) in the special case where s = 2 and N 1 = [t] for some t ≤ k. Then λ 1 = λ 2 = 0, ν 1 = q 1-q(z1-1) , ν 2 = q, and µ 1 = µ 2 = 1. It follows in this case that

A k = 1 1 - tq 1-q(z1-1) + q(k -t) = m≥0 q m t 1 -q(z 1 -1) + (k -t) m = m≥0 q m m i=0 m i (k -t) m-i t i 1 1 -q(z 1 -1) i . Since 1 1 -q(z 1 -1) i = a≥0 (i) a a! q a (z 1 -1) a = a≥0 i + a -1 a q a (z 1 -1) a , (3.5)
it follows that

A k = n≥0 q n n m=0 m i=0 m i i + n -m -1 n -m (k -t) m-i t i (z 1 -1) n-m . (3.6)
Thus taking the coefficient of z s 1 on both sides of (3.6), we obtain the following result.

Theorem 3.1 Let N = N 1 ∪ N 2 where N 1 = [t] and N 2 = N -N 1 . Then if t ≤ k, the number of words in [k] n with s levels that start with elements in N 1 is n m=0 m i=0 (-1) n-m-s m i i + n -m -1 n -m n -m s (k -t) m-i t i . (3.7)
Going back to the general set partition

N = N 1 ∪ N 2 ∪ • • • ∪ N s ,
we can obtain a general formula for the number of words in [k] n for which there are t i levels which start with an element of N i for i = 1, . . . , s as follows. Let

n i = |N i ∩ [k]| for i = 1, . . . , n.
Then if set x j = y j = 1 and q j = q for all j, then it will be the case that λ j = 0 and µ j = 1 and ν j = q 1-q(zj -1) for all j. It easy follows that in this case,

A k = 1 1 - s i=1 niq 1-q(zi-1) = m≥0 q m s i=1 n i 1 -q(z i -1) m = m≥0 q m a 1 +•••as =m a1,...,as≥0 m a 1 , . . . , a m s i=1 n i 1 -q(z i -1) ai .
Then using (3.5), we see that

A k = m≥0 q m a 1 +•••+as =m a1,...,as≥0 m a 1 , . . . , a m n a1 1 • • • n as s s i=1 bi≥0 (a i ) bi b i ! q bi (z 1 -1) bi = n≥0 q n n m=0 a 1 +•••+as =m a1,...,as≥0 b 1 +•••+bs =n-m b1,...,bs≥0 m a 1 , . . . , a m n a1 1 • • • n as s s i=1 a i + b i -1 b i (z i -1) bi . (3.8)
Taking the coefficient of z t1 1 • • • z ts s on both sides of (3.8), we obtain the following result.

Theorem 3.2 Let N = N 1 ∪ • • • ∪ N s be a set partition of N. Let n i = |N i ∩ [k]| for i = 1, . . . , s.
Then the number of words in [k] n with t i levels that start with elements in

N i for i = 1, . . . , s is n m=0 a 1 +•••+as =m a1,...,as≥0 b 1 +•••+bs =n-m b1,...,bs≥0 m a 1 , . . . , a m n a1 1 • • • n as s s i=1 a i + b i -1 b i b i t i . (3.9)
4 Classifying words by the number of descents that start with elements ≤ t (≥ t + 1).

In this section, we shall consider the set partition N = N 1 ∪ N 2 where N 1 = [t]. Now if t ≤ k, then it is easy to see that we can rewrite (2.7) as

A k = 1 + k j=1 λ j k i=j+1 µ i 1 - k j=1 ν j k i=j+1 µ i (4.1)
where

λ j = q 1 (1 -y 1 ) 1 -q 1 (z 1 -y 1 ) , ν j = q 1 y 1 1 -q 1 (z 1 -y 1 )
, and

µ j = 1 -q 1 (z 1 -x 1 ) 1 -q 1 (z 1 -y 1 ) if j ≤ t and λ j = q 2 (1 -y 2 ) 1 -q 2 (z 2 -y 2 ) , ν j = q 2 y 2 1 -q 2 (z 2 -y 2 )
, and

µ j = 1 -q 2 (z 2 -x 2 ) 1 -q 2 (z 2 -y 2 ) if j > t.
Now if we want to find formulas for the number of words in [k] n with s descents that start with an element less than or equal to t, then we need to set x 2 = y 1 = y 2 = z 1 = z 2 = 1 and q 1 = q 2 = q in (4.1). In that case, we will have λ j = 0 and ν j = q for all j, µ j = 1 + q(x 1 -1) for j ≤ t, and µ j = 1 for j > t. It follows that

A k = 1 1 - k j=t+1 q + t j=1 q t i=j+1 (1 + q(x 1 -1)) = 1 1 -(k -t)q + q (1+q(x1-1)) t -1 (1+q(x1-1))-1 = 1 1 -1 (x1-1) ((k -t)q(x 1 -1) -1 + (1 + q(x 1 -1)) t ) = m≥0 1 (x 1 -1) m (k -t)q(x 1 -1) -1 + (1 + q(x 1 -1)) t m = m≥0 1 (x 1 -1) m m a=0 m a ((k -t)q(x 1 -1) -1) m-a (1 + q(x 1 -1)) ta = m≥0 1 (x 1 -1) m m a=0 m-a b=0 ta c=0 m a m -a b ta c (-1) m-a-b q b (k -t) b (x 1 -1) b q c (x 1 -1) c .
If we want to take the coefficient of q n , then we must have b

+ c = n or c = n -b. Thus A k = n≥0 q n m≥0 m a=0 m-a b=0 m a m -a b ta n -b (-1) m-a-b (k -t) b (x 1 -1) n-m . (4.2)
Taking the coefficient of q n of both sides of (4.2), we see that

π∈[k] n x ← - des [t] (π) 1 = m≥0 m a=0 m-a b=0 m a m -a b ta n -b (-1) m-a-b (k -t) b (x 1 -1) n-m (4.3)
for all n. However, if we replace x 1 by z + 1 in (4.3), we see that the polynomial

π∈[k] n (z + 1) ← - des [t] (π)
has the Laurent expansion

m≥0 m a=0 m-a b=0 m a m -a b ta n -b (-1) m-a-b (k -t) b z n-m .
It follows that it must be the case that

m≥n+1 m a=0 m-a b=0 m a m -a b ta n -b (-1) m-a-b (k -t) b z n-m = 0, so that A k = n≥0 q n n m=0 m a=0 m-a b=0 (-1) m-a-b m a m -a b ta n -b (k -t) b (x 1 -1) n-m . (4.4)
Thus if we take the coefficient of x s 1 on both sides of (4.4) and we use the remark in the introduction that ← -

des [t] (w) =
←ris {k+1-t,...,k} (w) for all w ∈ [k] n , then we see that the number of words w ∈

[k] n such that ← - des [t] (w) = s ( ← - ris {k+1-t,...,k} (w) = s) is equal to n-s m=0 m a=0 m-a b=0 (-1) n-a-b-s m a m -a b ta n -b n -m s (k -t) b . (4.5)
Reordering the summands, we see that (4.5) is equal to

n-s b=0 (k -t) b n-s a=b (-1) n-a-b-s ta n -b n-s m=a+b m a m -a b n -m s . (4.6)
However it is the case that

n-s m=a+b m a m -a b n -m s = n + 1 a + b + s + 1 a + b a . (4.7)
This is easy to see combinatorially. That is, we can interpret the RHS of (4.7) as the number of ways of choosing a

+ b + 1 + s points, 1 ≤ x 1 < x 2 < • • • < x a+b+1+s ≤ n + 1, from the set [n + 1]
and then circling a of the points from x 1 < • • • < x a+b . However if we classify our choices by the value m + 1 of x a+b+1 , then we see that m a can be viewed as the number of ways to pick the circled points from [m], m-a b can be viewed as the number of ways to pick the non-circled chosen points from [m], and the binomial coefficient n-m s can be viewed as the number of ways to pick the points x a+b+2 < • • • < x a+b+1+s from the interval {m + 2, . . . , n + 1}.

Thus we have proved the following theorem.

Theorem 4.1 If t ≤ k, then the number of words w ∈ [k] n such that ← - des [t] (w) = s ( ← - ris {k+1-t,...,k} (w) = s) is equal to n-s b=0 (k -t) b n-s a=b (-1) n-a-b-s ta n -b n + 1 a + b + s + 1 a + b a . (4.8)
If we want to find formulas for the number of words in [k] n with s descents that start with an element greater than t, then we need to set x 1 = y 1 = y 2 = z 1 = z 2 = 1 and q 1 = q 2 = q in (4.1). In that case, we will have λ j = 0 and ν j = q for all j, µ j = 1 + q(x 2 -1) for j > t, and µ j = 1 for j ≤ t. It follows that

A k = 1 1 - t j=0 q(1 + q(x 2 -1)) k-t + k j=t+1 q k i=j+1 (1 + q(x 2 -1)) = 1 1 -qt(1 + q(x 2 -1)) k-t + q (1+q(x2-1)) k-t -1 (1+q(x2-1))-1 = 1 1 -1 (x2-1) (qt(x 2 -1)(1 + q(x 2 -1)) k-t + (1 + q(x 1 -1)) k-t -1) = 1 1 -1 (x2-1) ((qt(x 2 -1) + 1)(1 + q(x 2 -1)) k-t -1) = m≥0 1 (x 2 -1) m (qt(x 2 -1) + 1)(1 + q(x 2 -1)) k-t -1 m = m≥0 1 (x 2 -1) m m a=0 m a (-1) m-a (qt(x 2 -1) + 1) a (1 + q(x 2 -1)) (k-t)a = m≥0 1 (x 2 -1) m m a=0 a b=0 (k-t)a c=0 (-1) m-a m a a b (k -t)a c q b t b (x 2 -1) b q c (x 2 -1) c .
Again, if we want to take the coefficient of q n , then we must have b

+ c = n or c = n -b. Thus A k = n≥0 q n m≥0 m a=0 a b=0 (-1) m-a m a a b (k -t)a n -b t b (x 2 -1) n . (4.9)
Taking the coefficient of q n of both sides of (4.9), we see that

π∈[k] n
(k -t)a n -b t b z n-m .
It follows that it must be the case that

m≥n+1 m a=0 a b=0 (-1) m-a m a a b (k -t)a n -b t b z n-m = 0, so that A k = n≥0 q n n m=0 m a=0 a b=0 (-1) m-a m a a b (k -t)a n -b t b (x 1 -1) n-m . (4.11)
Thus if we take the coefficient of x s 2 on both sides of (4.11) and we use the remark in the introduction that ←des {t+1,...,k} (w) = ←ris [k-t] (w) for all w ∈ [k] n , then we have that the number of words w ∈

[k] n such that ← - des {t+1,...,k} (w) = s ( ← - ris [k-t] (w) = s) is equal to n-s m=0 m a=0 a b=0 (-1) n-a-s m a a b (k -t)a n -b n -m s t b . (4.12)
Reordering the summands, we see that (4.12) is equal to

n-s b=0 t b n-s a=b (-1) n-a-s a b (k -t)a n -b n-s m=a m a n -m s . (4.13)
However it is easy to see that

n-s m=a m a n -m s = n + 1 a + 1 + s . ( 4
+ • • • + y s+1 = n -b + 1 which is clearly n-b
s . We can give a similar combinatorial proof of Theorem 4.1 in the special case when t = 2.

5 Classifying descents and rises by their equivalence classes mod s for s ≥ 2.

In this section we study the set partition N = N 1 ∪ N 2 ∪ • • • ∪ N s where s > 2 and N i = {j | j = i mod s} for i = 1, . . . , s. In this case, we shall denote N i = sN + i for i = 1, . . . , s -1 and N s = sN.

Recall that we can rewrite (2.7) as

A k = 1 + k j=1 λ j k i=j+1 µ i 1 - k j=1 ν j k i=j+1 µ i (5.1)
where

λ j = qj (1-yj ) 1-qj (zj -yj ) , µ i = 1-qi(zi-xi)
1-qi(zi-yi) , and ν j = qj yj 1-qj (zj -yj ) . We let A (s) k denote A k under the substitution λ si+j = λ j , µ si+j = µ j , and ν si+j = ν j for all i and j = 1, . . . , s. Then it is easy to see that for k ≥ 1,

A (s) sk = 1 + s j=1 λ j s i=j+1 µ i k-1 r=0 (µ 1 µ 2 • • • µ s ) r 1 - s j=1 ν j s i=j+1 µ i k-1 r=0 (µ 1 µ 2 • • • µ s ) r = 1 + s j=1 λ j s i=j+1 µ i (µ1µ2•••µs) k -1 (µ1µ2•••µs)-1 1 - s j=1 ν j s i=j+1 µ i (µ1µ2•••µs) k -1 (µ1µ2•••µs)-1 . Similarly for 1 ≤ t ≤ s -1, A (s) sk+t =
(5.2)

1 + ( t j=1 λ j t i=j+1 µ i ) k r=0 (µ 1 • • • µ s ) r + (µ 1 µ 2 • • • µ t )( s j=t+1 λ j s i=j+1 µ i ) k-1 r=0 (µ 1 • • • µ s ) r 1 -( t j=1 ν j t i=j+1 µ i ) k r=0 (µ 1 • • • µ s ) r -(µ 1 µ 2 • • • µ t )( s j=t+1 ν j s i=j+1 µ i ) k-1 r=0 (µ 1 • • • µ s ) r 1 + ( t j=1 λ j t i=j+1 µ i ) (µ1µ2•••µs) k+1 -1 (µ1µ2•••µs)-1 + (µ 1 µ 2 • • • µ t )( s j=t+1 λ j s i=j+1 µ i ) (µ1µ2•••µs) k -1 (µ1µ2•••µs)-1 1 -( t j=1 ν j t i=j+1 µ i ) (µ1µ2•••µs) k+1 -1 (µ1µ2•••µs)-1 -(µ 1 µ 2 • • • µ t )( s j=t+1 ν j s i=j+1 µ i ) (µ1µ2•••µs) k -1 (µ1µ2•••µs)-1
.

5.1

The case where k is equal to 0 mod s.

First we shall consider formulas for the number of words in [sk] n with p descents whose first element is congruent to r mod s where 1 ≤ r ≤ s. Note that if we consider the complement map comp sk :

[sk] n → [sk] n given by comp(π 1 • • • π n ) = (sk + 1 -π 1 ) • • • (sk + 1 -π n ), then it is easy to see that ← - des sN+r (π) = ← - ris sN+s+1-r (comp sk (π)) for r = 1, . . . , s.
Thus the problem of counting the number of words in [sk] n with p descents whose first element is congruent to r mod s is the same as counting the number of words in [sk] n with p rises whose first element is congruent to s + 1r mod s Now consider the case where z i = y i = 1 and q i = q for i = 1, . . . , s and x i = 1 for i = r. In this case, A

= n≥0 q n π∈[sk] n x ← - des sN+r (π) r (s) sk
.

Substituting into our formulas for A (s)

sk , we see that in this case λ i = 0 and ν i = q for i = 1, . . . , s and µ i = 1 for i = r and µ r = 1 + q(x r -1). Thus under this substitution, (5.2) becomes

A (s) sk = 1 1 -((r -1)qµ r + (s -r + 1)q) µ k r -1 q(xr-1) = 1 1 -1 (xr-1) (s + (r -1)q(x r -1))(µ k r -1) = ∞ j=0 1 (x r -1) j (s + (r -1)q(x r -1)) j (µ k r -1) j = ∞ j=0 1 (x r -1) j j i1,i2=0 j i 1 s j-i1 (r -1) i1 q i1 (x r -1) i1 j i 2 (-1) j-i2 µ ki2 r = ∞ j=0 1 (x r -1) j j i1,i2=0 j i 1 s j-i1 (r -1) i1 q i1 (x r -1) i1 j i 2 (-1) j-i2 ki2 t=0 ki 2 t q t (x r -1) t .
Taking the coefficient of q n in (5.3), we see that n = t + i 1 so that

A (s) sk = n≥0 q n ∞ j=0 j i1,i2=0 (-1) j-i2 s j-i1 (r -1) i1 j i 1 j i 2 ki 2 n -i 1 (x r -1) n-j . (5.3)
Thus we must have

π∈[sk] n x ← - des sN+r (π) r = ∞ j=0 j i1,i2=0 (-1) j-i2 s j-i1 (r -1) i1 j i 1 j i 2 ki 2 n -i 1 (x r -1) n-j (5.4)
for all n. However, if we replace x r by z + 1 in (5.4), we see that the polynomial

π∈[sk] n (z + 1) ← - des sN+r (π)
has the Laurent expansion

∞ j=0 j i1,i2=0 (-1) j-i2 s j-i1 (r -1) i1 j i 1 j i 2 ki 2 n -i 1 z n-j .
It follows that it must be the case that

∞ j=n+1 j i1,i2=0 (-1) j-i2 s j-i1 (r -1) i1 j i 1 j i 2 ki 2 n -i 1 z n-j = 0 so that A (s) sk = n≥0 q n n j=0 j i1,i2=0 (-1) j-i2 s j-i1 (r -1) i1 j i 1 j i 2 ki 2 n -i 1 (x r -1) n-j . (5.5)
Thus we have the following theorem by taking the coefficient of x p r on both sides of (5.5).

Theorem 5.1 The number of words

π ∈ [sk] n with ← - des sN+r (π) = p ( ← - ris sN+s+1-r (π) = p) is n-p j=0 j i1,i2=0 (-1) n+p+i2 s j-i1 (r -1) i1 j i 1 j i 2 ki 2 n -i 1 n -j p . (5.6)
In the case s = 2, our formulas simplify somewhat. For example, putting s = 2 and r = 2 in Theorem 5.1, we obtain the following.

Corollary 5.2 The number of n-letter words π on

[2k] having ← - des E (π) = p (resp. ← - ris O (π) = p) is given by n-s j=0 j i1,i2=0 (-1) n+p+i2 2 j-i1 j i 1 j i 2 ki 2 n -i 1 n -j p .
Similarly, putting s = 2 and r = 1 in Theorem 5.1, we obtain the following.

Corollary 5.3 The number of n-letter words π on

[2k] having ← - des O (π) = p (resp. ← - ris E (π) = p) is given by n-p j=0 j i=0
(-1) n+p+i 2 j j i ki n nj p .

5.2

The cases where k is equal to t mod s for t = 1, . . . , s -1.

Fix t where 1 ≤ t ≤ s -1. First we shall consider formulas for the number of words in [sk + t] n with p descents whose first element is congruent to r mod s where 1 ≤ r ≤ s. We shall see that we have to divide this problem into two cases depending on whether r ≤ t or r > t. Note that if we consider the complement map comp sk+t : [sk + t] n → [sk + t] n given by comp(π

1 • • • π n ) = (sk + t + 1 -π 1 ) • • • (sk + t + 1 -π n )
, then it is easy to see that ←des sN+r (π) = ←ris sN+t+1-r (comp sk (π)) for r = 1, . . . , t and ←des sN+r (π) = ←ris sN+s+r-t-1 (comp sk (π)) for r = t + 1, . . . , s.

First consider the case where y i = z i = 1 for i = 1, . . . , s and x i = 1 for i = r where r > t. In this case,

A (s) sk+t = n≥0 q n π∈[sk+t] n x ← - des sN+r (π) r .
Substituting into our formulas for A (s) sk+t , we see that in this case λ i = 0 and ν i = q for i = 1, . . . , s and µ i = 1 for i = r and µ r = 1 + q(x r -1). Thus under this substitution, (5.2) becomes

A (s) sk+t = 1 1 -qt µ k+1 r -1 q(xr-1) -((r -1 -t)qµ r + (s -r + 1)q) µ k r -1 q(xr-1) = 1 1 -1 (xr-1) [t(µ k+1 r -1) + (s -t + (r -1 -t)q(x r -1))(µ k r -1)] = 1 1 -1 (xr-1) [µ k r [s + (r -1)q(x r -1)] -[s + (r -1 -t)q(x r -1)]] = ∞ m=0 1 (x r -1) m [µ k r [s + (r -1)q(x r -1)] -[s + (r -1 -t)q(x r -1)]] m = ∞ m=0 m j=0
(-1) m-j (x r -1) m m j (s + (r -1t)q(x r -1)) m-j (s + (r -1)q(x r -1)) j µ kj r .

Using the expansions

(s + (r -1 -t)q(x r -1)) m-j = m-j i1=0 m -j i 1 s m-j-i1 (r -1 -t) i1 q i1 (x r -1) i1 ,
(s + (r -1)q(x r -1)) j = j i2=0 j i 2 s j-i2 (r -1) i2 q i2 (x r -1) i2 , and

µ kj r = kj i3=0 kj i 3 q i3 (x r -1) i3 ,
and setting i 1 + i 2 + i 3 = n, we see that (5.7) becomes

A (s) sk+t = (5.7) n≥0 q n ∞ m=0 m j=0 m-j i1=0 j i2=0 (-1) m-j s m-i1-i2 (r -1 -t) i1 (r -1) i2 × m j m -j i 1 j i 2 kj n -i 1 -i 2 (x r -1) n-m .
Thus we must have

π∈[skt] n x ← - des sN+r (π) r = (5.8) ∞ m=0 m j=0 m-j i1=0 j i2=0 (-1) m-j s m-i1-i2 (r -1 -t) i1 (r -1) i2 × m j m -j i 1 j i 2 kj n -i 1 -i 2 (x r -1) n-m .
for all n. However, if we replace x r by z + 1 in (5.8), we see that the polynomial

π∈[sk+t] n (z + 1) ← - des sN+r (π)
has the Laurent expansion

∞ m=0 m j=0 m-j i1=0 j i2=0 (-1) m-j s m-i1-i2 (r -1 -t) i1 (r -1) i2 m j m -j i 1 j i 2 kj n -i 1 -i 2 z n-m .
It follows that

∞ m=n+1 m j=0 m-j i1=0 j i2=0 (-1) m -js m-i1-i2 (r -1 -t) i1 (r -1) i2 m j m -j i 1 j i 2 kj n -i 1 -i 2 z n-m = 0 so that A (s) sk+t = (5.9) n m=0 m j=0 m-j i1=0 j i2=0 (-1) m-j s m-i1-i2 (r -1 -t) i1 (r -1) i2 m j m -j i 1 j i 2 kj n -i 1 -i 2 (x r -1) n-m .
Thus we have the following theorem by taking the coefficient of x p r on both sides of (5.9). Theorem 5.4 If t = 1, . . . , s -1 and t < r ≤ s, then the number of words π ∈ [sk + t] n with ←des sN+r (π) = p ( ← -

ris sN+s+r-t-1 (π) = p) is n-p m=0 m j=0 m-j i1=0 j i2=0 (-1) n+p+j s m-i1-i2 (r-1-t) i1 (r-1) i2 m j m -j i 1 j i 2 kj n -i 1 -i 2 n -m p .
(5.10)

In the case s = 2, our formulas simplify somewhat. For example, putting s = 2, r = 2 and t = 1 in Theorem 5.4, we obtain the following.

Corollary 5.5 The number of n-letter words π over

[2k + 1] having ← - des E (π) = p (resp. ← - ris E (π) = p) is given by n-p m=0 m j=0 j i=0 (-1) n+p+j 2 m-i m j j i kj n -i n -m p .
Next consider the case where y i = z i = 1 for i = 1, . . . , s and x i = 1 for i = r where r ≤ t. In this case,

A (s) sk+t = n≥0 q n π∈[sk+t] n x ← - des sN+r (π) r .
Substituting into our formulas for A (s) sk+t , we see that in this case λ i = 0 and ν i = q for i = 1, . . . , s and µ i = 1 for i = r and µ r = 1 + q(x r -1). Thus, under this substitution, (5.2) becomes

A (s) sk+t = 1 1 -((r -1)qµ r ) + q(t -r + 1)) µ k+1 r -1 q(xr-1) -(s -t)qµ r µ k r -1 q(xr-1) = 1 1 -1 (xr-1) [(t + (r -1)q(x r -1))(µ k+1 r -1) + (s -t)µ r (µ k r -1)] = 1 1 -1 (xr-1) [µ k+1 r [s + (r -1)q(x r -1)] -[s + (s -t + r -1)q(x r -1)]] = ∞ m=0 1 (x r -1) m [µ k+1 r [s + (r -1)q(x r -1)] -[s + (s -t + r -1)q(x r -1)]] m = ∞ m=0 m j=0 (-1) m-j (x r -1) m m j (s + (s -t + r -1)q(x r -1)) m-j (s + (r -1)q(x r -1)) j µ kj+j r .
Using the expansions

(s + (s -t + r -1)q(x r -1)) m-j = m-j i1=0 m -j i 1 s m-j-i1 (s -t + r -1) i1 q i1 (x r -1) i1 , (s + (r -1)µ j r = j i2=0 j i 2 s j-i2 (r -1) i2 q i2 (x r -1) i2 , and
µ kj+j r = kj+j i3=0 kj + j i 3 q i3 (x r -1) i3 ,
and setting i 1 + i 2 + i 3 = n, we see that (5.11) becomes

A (s) sk+t = (5.11) n≥0 q n ∞ m=0 m j=0 m-j i1=0 j i2=0 (-1) m-j s m-i1-i2 (s -t + r -1) i1 (r -1) i2 × m j m -j i 1 j i 2 kj + j n -i 1 -i 2 (x r -1) n-m .
Thus we must have

π∈[skt] n x ← - des sN+r (π) r = (5.12) ∞ m=0 m j=0 m-j i1=0 j i2=0 (-1) m-j s m-i1-i2 (s -t + r -1) i1 (r -1) i2 × m j m -j i 1 j i 2 kj + j n -i 1 -i 2 (x r -1) n-m .
for all n. However, if we replace x r by z + 1 in (5.12), we that the polynomial

π∈[sk+t] n (z + 1) ← - des sN+r (π) has the Laurent expansion ∞ m=0 m j=0 m-j i1=0 j i2=0 (-1) m -js m-i1-i2 (s-t+r -1) i1 (r -1) i2 m j m -j i 1 j i 2 kj + j n -i 1 -i 2 z n-m .
It follows that it must be the case that

∞ m=n+1 m j=0 m-j i1=0 j i2=0 (-1) m-j s m-i1-i2 (s -t + r -1) i1 (r -1) i2 m j m -j i 1 j i 2 kj + j n -i 1 -i 2 z n-m = 0 so that A (s) sk+t = n m=0 m j=0 m-j i1=0 j i2=0 (-1) m-j s m-i1-i2 (s -t + r -1) i1 (r -1) i2 m j m -j i 1 j i 2 kj + j n -i 1 -i 2 (x r -1) n-m .
Thus we have the following theorem by taking the coefficient of x p r on both sides of (5.9). Theorem 5.6 If k ≥ 0, s ≥ 2, t = 1, . . . , s -1, and t < r ≤ s, then the number of words π ∈

[sk + t] n with ← - des sN+r (π) = p ( ← - ris sN+s+r-t-1 (π) = p ) is n-p m=0 m j=0 m-j i1=0 j i2=0 (-1) n+p+j s m-i1-i2 (s-t+r-1) i1 (r-1) i2 m j m -j i 1 j i 2 kj + j n -i 1 -i 2 n -m p .
In the case s = 2, our formulas simplify somewhat. For example, putting s = 2, r = 1 and t = 1 in Theorem 5.4, we obtain the following.

Concluding remarks

A particular case of the results obtained by Burstein and Mansour in [START_REF] Burstein | Counting occurrences of some subword patterns[END_REF] is the distribution of descents (resp. levels, rises), which can be viewed as occurrences of so called generalized patterns 21 (resp. 11, 12) in words. To get these distributions from our results, we proceed as follows (we explain only the case of descents; rises and levels can be considered similarly). Set x 1 = x 2 = x, y 1 = y 2 = z 1 = z 2 = 1, and q 1 = q 2 = q in A (2) 2k and A

(2)

2k+1 to get the distribution in [4, Theorem 2.2] for ℓ = 2 (the case of descents/rises). Thus, our results refine and generalize the known distributions of descents, levels, and rises in words.

It is interesting to compare our formulas with formulas of Hall and Remmel [START_REF] Hall | Counting descent pairs with prescribed tops and bottoms[END_REF]. For example, suppose that X = E and Y = N and ρ = (ρ 1 , . . . , ρ 2k ) is a composition of n. Then Theorem 1.1 tells that the number of words π of compositions of n into k parts but that has the disadvantage of having the outside sum have a large range as n and k get large. Nevertheless, we note that for (6.1) Hall and Remmel have a direct combinatorial proof via a signreversing involution. It is therefore natural to ask whether one can find similar proofs for our formulas in Sections 3 and 4.

There are several ways in which one could extend our research. For example, one can study our refined statistics ( ← --Des X (π), ← -Ris X (π), Lev X (π)) on the set of all words avoiding a fixed pattern or a set of patterns (see [START_REF] Burstein | Enumeration of words with forbidden patterns[END_REF][START_REF] Burstein | Words restricted by patterns with at most 2 distinct letters[END_REF][START_REF] Burstein | Words restricted by 3-letter generalized multipermutation patterns[END_REF][START_REF] Burstein | Counting occurrences of some subword patterns[END_REF] for definitions of "patterns in words" and results on them). More generally, instead of considering the set of all words, one can consider a subset of it defined in some way, and then to study the refined statistics on the subset. Also, instead of considering refined descents, levels, and rises (patterns of length 2), one can consider patterns of length 3 and more in which the equivalence class of the first letter is fixed, or, more generally, in which the equivalence classes of more than one letter (possibly all letters) are fixed. Once such a pattern (or set of patterns) is given, the questions on avoidance (or the distribution of occurrences) of the pattern in words over [k] can be raised.

  des X,Y (w) = |Des X,Y (w)|, andP X,Y ρ,s = |{w ∈ R(ρ) : des X,Y (w) = s}| .

Theorem 1. 1 P

 1 X,Y ρ,s = a ρ v1 , ρ v2 , . . . , ρ v b s r=0 (-1) s-r a + r r n + 1 sr x∈X ρ x + r + α X,ρ,x + β Y,ρ,x ρ x ,(1.1)whereX c m = {v 1 , v 2 , . . . , v b }, a = b i=1ρ vi , and for any x ∈ X m , α X,ρ,x = z / ∈ X x < z ≤ m ρ z , and

  t b (x 2 -1) n-m (4.10) for all n. However, if we replace x 2 by z + 1 in (4.3), we see that the polynomial π∈[k] n (z + 1) ←des {t+1,...,k} (π)

  .14) because the LHS of (4.14) is the result of classifying the ways to pick a + 1 + s points from [n + 1] by the value m + 1 of the (a + 1)-st point reading from left to right. Thus we have obtain the following theorem.

Theorem 4 . 2

 42 If t ≤ k, then the number of words w ∈ [k] n such that ←des {t+1,...,k} (w) = s ( ←ris [k-t] (w) = s) is equal to cases, we can give direct combinatorial proofs of Theorems 4.1 and 4.2. For example, in the special case of Theorem 4.2 where t = k -1, one can use the Pfaff-Saalschütz Theorem to show that b to see that (4.17) is the result of classifying the words such that ←des {k} (w) = s by the number of letters which are not equal to k in the word. That is, if there are b such letters, then we can pick a word of length b in the alphabet {1, . . . , k -1} in (k -1) b ways. Next we insert a k directly in front of s different letters in u in b s ways to create s descents that start with k. Finally we can place the remaining nbs k's either in a block with one of the k's that start a descent or at the end of u. The number of ways to place the remaining k's is the number of non-negative integer valued solutions to x 1 + • • • + x s+1 = nbs or, equivalently, the number of positive integer valued solutions to y 1

Corollary 5 . 7

 57 The number of n-letter words π over[2k + 1] having ←des O (π) = p (resp. ←ris O (π) = p) is given by

ρ

  [2k] n such that ←des E (π) = p is a ρ 2 , ρ 4 , . . . , ρ 2k 2i + r + (ρ 2i+1 + ρ 2i+3 + • • • + ρ 2k-1 ) ρ 2i ,(6.1) where a = ρ 2 + ρ 4 + • • • + ρ 2k . This shows that once we are given the distribution of the letters for words in [2k] n , we can find an expression for the number of words π such that ←des E (π) = p with a single alternating sum of products of binomial coefficients. This contrasts with Corollary 5.2 where we require a triple alternating sum of products of binomial coefficients to get an expression for the number of words of [2k] n such that ←des E (π) = p. Of course, we can get a similar expression for the number of words of [2k] n such that ←des E (π) = p by summing the formula in (6.1) over all n+k-1 k-1

† The work presented here was supported by grant no. 060005012/3 from the Icelandic Research Fund. ‡ The work presented here was partially supported by NSF grant DMS 0654060 1365-8050 c 2008