Universal cycles for permutation classes

Michael Albert<fnref n="1" /> and Julian West<fnref n="2" />

**Abstract.** We define a universal cycle for a class of *n*-permutations as a cyclic word in which each element of the class occurs exactly once as an *n*-factor. We give a general result for cyclically closed classes, and then survey the situation when the class is defined as the avoidance class of a set of permutations of length 3, or of a set of permutations of mixed lengths 3 and 4.

**Résumé.** Nous définissons un cycle universel pour une classe de *n*-permutations comme un mot cyclique dans lequel chaque élément de la classe apparaît une unique fois comme *n*-facteur. Nous donnons un résultat général pour les classes cycliquement closes, et détaillons la situation où la classe de permutations est définie par motifs exclus, avec des motifs de taille 3, ou bien à la fois des motifs de taille 3 et de taille 4.

**Keywords:** Restricted permutations. Universal cycles. Eulerian circuits. DeBruijn graphs.

<footnote n="1">¹University of Otago, Dunedin, New Zealand</footnote>

<footnote n="2">²University of Victoria, British Columbia, Canada</footnote>
# 1 Definitions and initial observations

Given a family $\mathcal{C}$ of combinatorial objects that can be represented as sequences of length $n$, a universal cycle for such a family is a sequence, whose length $n$ factors (read cyclically) represent all the elements of $\mathcal{C}$ without repetition. De Bruijn sequences ([3]) are the most well known such universal cycles, but their study was extended to other combinatorial families by Chung, Diaconis and Graham in [2]. Among the classes they considered was the set of all permutations of an $n$ set. In the present work, we consider a notion of universal cycles for permutation pattern classes.

To each sequence $s = a_1, a_2, \dots, a_k$ of distinct values, we associate a permutation $\tau \in S_k$ called its pattern or type, by choosing $\tau(i) < \tau(j)$ if and only if $a_i < a_j$. We will use the notation $\tau = \text{pat}(s)$ to express this relationship. Our interest is in observing the presence or absence of patterns in longer permutations; thus, regarding a permutation $\pi \in S_n$ as a sequence of $n$ elements, $\pi(1), \pi(2), \dots, \pi(n)$, we will say that $\pi$ contains $\tau$ if there is a selection of indices $1 \le i_1 < i_2 < \dots < i_k \le n$ such that $\text{pat}(\pi(i_1), \pi(i_2), \dots, \pi(i_k)) = \tau$. If $\pi$ does not contain $\tau$ then it is said to avoid $\tau$.

We will write $\text{Av}(\tau)$ for the *avoidance class* of all permutations (of any length) which avoid $\tau$, and use the obvious notation $\text{Av}_n(\tau) = \text{Av}(\tau) \cap S_n$. We extend this to multiple restrictions: $\text{Av}(\tau_1, \tau_2, \dots, \tau_r) = \text{Av}(\tau_1) \cap \text{Av}(\tau_2) \cap \dots \cap \text{Av}(\tau_r)$.

For example the permutation $\pi = 2314$ contains 123, as one of its subsequences is 234 and $\text{pat}(234) = 123$. But 2314 avoids both 132 and 312, so we will say that $\pi \in \text{Av}_4(132, 312)$.

Let $\mathcal{A} = \text{Av}(\tau_1, \dots, \tau_r)$ be an avoidance class, and let $m$ be the size of $\mathcal{A}_n$. Then a sequence of integers $c_1, c_2, \dots, c_m$ is a *universal cycle* for $\mathcal{A}_n$ if each of the $m$ substrings $c_j, c_{j+1}, \dots, c_{j+n-1}$ (taking the subscripts modulo $m$) has a distinct element of $\mathcal{A}_n$ as its pattern.

For instance, the sequence 1, 6, 7, 8, 4, 3, 2, 5 is a universal cycle for the class $\text{Av}_4(132, 312)$, as can be verified by taking each of the 8 substrings 1678, 6784, ..., 2516, 5167, reducing each one to a permutation, and checking that these are exactly the eight permutations of length four which avoid both 132 and 312.

Suppose that such a universal cycle $c_1 \dots c_m$ contains, in order, substrings of patterns $\pi_1, \dots, \pi_m$. Then it is evident that a permutation $\pi_j = a_1, a_2, \dots, a_n$ cannot be followed by an arbitrary permutation $\pi_{j+1} = b_1, b_2, \dots, b_n$. Specifically, the overlapping parts of the two permutations, $a_2, \dots, a_n$ and $b_1, \dots, b_{n-1}$, must have the same pattern, say $\sigma \in S_{n-1}$.

This suggests that a useful tool for constructing universal cycles would be a deBruijn-type graph, in which a vertex corresponding to the overlapping part, $\sigma$, would be visited by an incoming edge $\pi_j$ and an outgoing edge $\pi_{j+1}$. A universal cycle $c_1, \dots, c_m$ of $\mathcal{A}_n$ would thus trace an Eulerian circuit in a directed graph $G(\mathcal{A}_n)$ containing $m$ edges, this graph being a subgraph of $G(S_n)$, which is a regular graph on $(n-1)!$ vertices, each having indegree $n$ and outdegree $n$, for a total of $n!$ directed edges.

The graph $G(S_4)$ is depicted in figure 1. The vertices are labelled with the six elements of $S_3$. The letter labelling each edge can be read in conjunction with the label of its trailing vertex to produce a 4-permutation by appending the letter to the vertex label and then taking the pattern of the resulting 4-sequence, using the order $a < b < c < d$. For instance the edge labelled $c$ from 123 to 132 corresponds to the 4-permutation 1243, whose 3-element prefix has pattern 123, and whose 3-element suffix has pattern 132.

As is well known, the necessary and sufficient conditions for the existence of an Eulerian circuit in a graph are that the graph be connected and that the indegrees and outdegrees match at each vertex, making it easy in general to test for the existence of an Eulerian circuit. However, the existence of Eulerian circuits does not guarantee that a universal cycle can be constructed. For instance, the deBruijn
<figure><img src="image_1.png" /><figcaption>Fig. 1: The directed graph $G(S_4)$.</figcaption></figure>

graph for $Av_4(132, 213)$ (figure 6) has an Eulerian circuit which visits the directed edges in the sequence 1234,2341,3412,4231,3421,4321,4312,4123. However, if this were to correspond to a universal cycle $c_1, c_2, \dots, c_8$, the second, fifth and seventh edges in the list would, respectively, force $c_2 > c_5, c_5 > c_8$ and $c_8 > c_2$, a contradiction. In fact, no Eulerian tour of the graph for $Av_4(132, 213)$ is realizable with a sequence of values.

We will distinguish these two cases by saying that the class $Av_4(132, 312)$ is *value cyclic*, but that $Av_4(132, 213)$ is merely *pattern cyclic*, i.e. that its associated directed graph is Eulerian. An Eulerian cycle in the graph of a pattern cyclic class can be realized by a sequence of values if and only if the order relations implied by the individual edges form a directed acyclic graph, and thus can be extended to a partial order, as then any extension to a total order will provide a realisation of a universal cycle.

In [2], it is shown that $S_n$ (the avoidance class of the empty set) is value cyclic for all $n$, and indeed conjectured that a universal cycle can always be constructed using just $n+1$ different values; this conjecture was proven in [9].

It is instructive to consider the graphs $G(S_n)$ and $G(S_{n+1})$ together. The first of these graphs has vertex set $S_{n-1}$ and edge set $S_n$, while the second has vertex set $S_n$ and edge set $S_{n+1}$. Now let $\pi = a_1, a_2, \dots, a_{n+1}$ be any permutation belonging to $S_{n+1}$ and let $\rho_1 = \text{pat}(a_1, \dots, a_n)$ and $\rho_2 = \text{pat}(a_2, \dots, a_{n+1})$ be the pattern types of its $n$-prefix and $n$-suffix respectively.

Finally let $\sigma = \text{pat}(a_2, \dots, a_n)$, from which it is apparent that $\sigma$ is simultaneously the pattern type for the $(n-1)$-suffix of $\rho_1$ and for the $(n-1)$-prefix of $\rho_2$. In graph terms, this means that $\pi$ is an edge leading from $\rho_1$ to $\rho_2$ in $G(S_{n+1})$, while $\sigma$ is a vertex in $G(S_n)$ which has $\rho_1$ leading in and $\rho_2$ leading out. The option in $G(S_n)$ to follow the edge $\rho_1$ by $\rho_2$ thus corresponds to an option in $G(S_{n+1})$ to move from the vertex $\rho_1$ to $\rho_2$; specifically, any Eulerian circuit of $G(S_n)$ corresponds exactly to a Hamiltonian tour of $G(S_{n+1})$.

For a given set $T = \tau_1, \tau_2, \dots, \tau_r$ of forbidden patterns, we will be interested in two questions. Is it true that $S_n(T)$ is pattern cyclic for all values of $n$? Is it true that $S_n(T)$ is value cyclic for all values of $n$?
<figure><img src="image_2.png" /><figcaption>Fig. 2: The directed graph $G(S_3)$.</figcaption></figure>

We begin by settling the pattern-cyclic question in the affirmative for a special infinite set of avoidance classes. We will say that a set of permutations is cyclically closed if, given any permutation in the set, its head-to-tail shift is also in the set. Thus, for instance, 1243, 2431, 4312, 3124 is a cyclically closed set.

**Proposition 1** If the set of forbidden patterns *T* is cyclically closed, and *G*(Av<sub>*n*</sub>(*T*)) is connected, then Av<sub>*n*</sub>(*T*) is pattern cyclic.

**Proof:** First note that if $T$ is cyclically closed, then $\text{Av}(T)$ is also cyclically closed. Then note that $\pi = x, a_1, a_2, \dots, a_n$ belongs to $\text{Av}_{n+1}(T)$ if and only if $\sigma = a_1, a_2, \dots, a_n, x$ does as well. This means that $a_1, a_2, \dots, a_n$, as a vertex in $G(\text{Av}_n(T))$, has the same number of incoming edges as outgoing edges. Together with the connectedness condition, this establishes that $G(\text{Av}_n(T))$ is Eulerian. $\square$

## 2 Classes defined by restrictions of length 3

For each $n$, $\text{Av}_n(12)$ (and, symmetrically, $\text{Av}_n(21)$) contains only a single permutation, so the first non-trivial restrictions are of length 3. We therefore begin by considering all possible sets of restrictions comprised of permutations from $S_3$.

Consider $T \subset S_3$. The pattern-cyclic question asks whether $G(\text{Av}_n(T))$ has a universal cycle for all $n \ge 3$; in order to be able to settle this in the affirmative, we must, to begin, have a universal cycle for $n=3$, and therefore it is necessary that $G(\text{Av}_3(T))$ be Eulerian. The graph of $G(S_3)$, given in Figure 2 allows us to identify possible sets of edges whose removal would leave the graph connected and Eulerian. There are certain symmetries which allow us to reduce the number of cases we need to consider. In particular, the reversal of a class $\text{Av}_n(T)$ in which each element of $\tau = a_1, \dots, a_k$ of $T$ is replaced by a $\tau^r = a_k, \dots, a_1$ is pattern or value cyclic exactly $\text{Av}_r(T)$ is, because it suffices simply to reverse any given cycle, and a similar property holds for complements $\tau^c = k+1-a_1, \dots, k+1-a_k$. These two symmetries are visible in the symmetric construction of Figure 1, in which reflection in a horizontal mirror corresponds to complementation, while reflection in a vertical mirror corresponds to reverse complementation, and rotation through 180 degrees corresponds to reversal. However, the third operation which preserves the enumeration of pattern classes, inverse, does not preserve cyclic properties; for instance, $\text{Av}_3(132, 312)$ is value cyclic, but $\text{Av}_3(132, 231)$ is not even pattern cyclic.

Up to symmetry, there are six non-empty cases, which are displayed in the table below. Recall that the case for the empty set was shown to be value-cyclic in [2]. Also, we don't consider any case which
involves both loops, as avoiding both 123 and 321 leaves empty permutation classes for large enough $n$, by a famous theorem of Erdős and Szekeres[5].

<table><thead><tr><th>Class</th><th>Size of Class</th><th>Properties</th></tr></thead><tbody><tr><td>Av<sub>n</sub>(123)</td><td>C<sub>n</sub> = (2n)!/n!(n + 1)!</td><td>not cyclic: {c,d}213{a,b,c}</td></tr><tr><td>Av<sub>n</sub>(132, 312)</td><td>2<sup>n-1</sup></td><td>value cyclic</td></tr><tr><td>Av<sub>n</sub>(132, 213)</td><td>2<sup>n-1</sup></td><td>pattern cyclic</td></tr><tr><td>Av<sub>n</sub>(132, 312, 123)</td><td>n</td><td>pattern cyclic</td></tr><tr><td>Av<sub>n</sub>(132, 213, 123)</td><td>Fibonacci</td><td>not cyclic: {d}231{a,b}</td></tr><tr><td>Av<sub>n</sub>(132, 213, 321)</td><td>n</td><td>value cyclic</td></tr></tbody></table>

The easiest cases to dispose of are those in which the pattern-class property fails to hold in general, as it suffices to give a counterexample. We have provided one in each case, in the form of a vertex (in each case, in $G(Av_4(T))$) together with its attendant directed edges. Here, our notation is slightly different from that used in Figure 1, as we here label both incoming and outgoing edges relative to the vertex shown. Thus, in $Av_4(123)$, we can prepend either a 3 or a 4 to the permutation 213, to produce 3214 and 4213 respectively, both of these being in the avoidance class. But we can add any of the three symbols 1, 2 or 3 at the end, to produce 3241, 3142 or 2143. Thus the indegrees and outdegrees fail to match, and $G(Av_4(123))$ is not Eulerian. (Indeed, this example readily extends to show that $G(Av_n(123))$ for $n \ge 4$: the permutation $n-2, n-3, \dots, 1, n-1$ can be extended only by prepending an $n$ or an $n-1$, but at the other end can be extended by appending anything from 1 to $n-1$.)

Now consider $Av_n(132, 213, 321)$, which is the cyclically closed set consisting of $123 \dots n$ and its cyclic shifts. This is automatically pattern cyclic by Proposition 1, and indeed a universal cycle can be obtained from the sequence $1, 2, 3, \dots, n$ itself, so the class is value cyclic. This is, up to symmetry, the only cyclically-closed class of size $n$, because for large $n$ any non-empty class must contain either the all-increasing or the all-decreasing permutation, and thus, if cyclically closed, be a superset of $Av_n(132, 213, 321)$ or of its reverse.

It is easy to check that the permutations belonging to $Av_n(132, 312, 123)$ are those in which $n-1, n-2, \dots, 2, 1$ form a decreasing subsequence (and the largest value, $n$, can be inserted into this in any one of $n$ places). Each sequence in $Av_{n-1}(132, 312, 123)$ has outdegree one (by adding in each case a new smallest element), except for the all-decreasing sequence, which has outdegree two, because one can add a new smallest element (creating a loop back to the same vertex) or a new largest element. And, symmetrically, each vertex has indegree one (by prepending a new largest element) except for the all-decreasing sequence, to which either $n$ or $n-1$ can be prepended. The graph therefore consists of a single directed cycle, with a loop added at one vertex. It is easy to see that this class is not value cyclic, because a universal cycle would consist of only $n$ values, $a_1, \dots, a_n$, and each of the permutations, being of length $n$, would imposes a total order on this cycle; only for the all-descending permutation and the one which follows it, $n-1, \dots, 1, n$, do these total orders coincide.

**Proposition 2** *The class $Av(132, 312)$ is value cyclic for all $n$.*

**Proof:** There are $2^{n-1}$ permutations in $A_n = Av_n(132, 312)$, which are constructed as follows. Assign a bit freely to each position from 2 to $n$. Now, beginning on the right, replace the 1s sequentially by $n, n-1, n-2, \dots$ to form an *upper sequence*, and replace the 0s sequentially by $1, 2, 3, \dots$ to form a
*lower sequence.* Arriving at the (unlabelled) first position, assign it the sole remaining value, which could be viewed as belonging to either the upper sequence or the lower sequence.

It is clear that these permutations belong to the avoidance class: in any subsequence $x, y, z$, the element $z$ must be either the largest of the three elements (if it belongs to the upper sequence), or the smallest (if it belongs to the lower sequence).

Now note that if $\sigma$ follows $\pi$ in an Eulerian tour of $G(\mathcal{A}_n)$, then $\sigma$ is obtained from $\pi$ by deleting the first element and appending either a new maximal or a new minimal element. In terms of the bitstring, this means deleting the first bit and adding a new bit, either a 1 or a 0, to the end. So, if each edge were labelled not by a permutation but by its corresponding bitstring (and each vertex, therefore, labelled, by the bitstring which corresponds to the tail of each of its incoming edges and the head of each of its outgoing edges), the resulting graph would simply be the usual deBruijn graph on binary words. The graph $G(\mathcal{A}_n)$ is thus isomorphic to the usual deBruijn graph on bitstrings of length $n-1$.

Any Eulerian tour of the usual deBruijn graph thus corresponds to an Eulerian tour of $G(\mathcal{A}_n)$. (In general a deBruijn graph has a large number of Eulerian circuits, $2^{2^{n-2}-(n-1)}$. This formula is well-known and was rediscovered at least once; for an interesting history lesson see [3, 4, 6].) Moreover, any deBruijn cycle (obtained from an Eulerian circuit by writing down the new bits in order) can be converted into a universal cycle for $\mathcal{A}_n$ as follows.

The deBruijn cycle contains a unique run of $n-1$ 1s. Let $m = 2^{n-2}$, which is half the length of the sequence. Write the numbers $m, m-1, m-2, \dots, 3, 2, 1$, in order, below the 0s in the cycle, beginning immediately after this run of 1s (and ending immediately before it). Likewise, write the numbers $m+1, m+2, \dots, 2m-1, 2m$ in order below the 1s in the cycle, beginning immediately after the unique run of $n-1$ 0s (and ending again immediately before it).

Here is an example for $n=5$:

```
0  0  0  0  1  1  1  1  0  0  1  0  1  1  0  1
4  3  2  1  9 10 11 12  8  7 13  6 14 15  5 16
```

Any consecutive run of $n$ values from this (cyclic) sequence will reduce to a permutation in the class $Av_n(132, 312)$. For the $n$ values cannot include numbers corresponding to all of the $n-1$ consecutive 0s as well as 1s both before and after them; therefore those corresponding to 1s must all be (large and) increasing. Similarly those corresponding to 0s must be (small and) decreasing. As each bitstring of length $n-1$ occurs uniquely in the deBruijn cycle, each of the $2^{n-1}$ possible 01-codes for positions 2, 3, ..., $n$ occurs. The bit in the first position might be either a 1 or a 0 (and is dependent on the choice of deBruijn cycle), but regardless the value at this position will be smaller than all the later values corresponding to 1s and larger than all those corresponding to 0s.

This construction shows that $Av_n(132, 312)$ is value cyclic for all $n$. $\square$

The final entry in the table is for $Av_n(132, 213)$, which is the well-known class of *layered permutations* (see [1]), those consisting of an initial increasing run containing all the largest elements in the permutation, followed by another increasing run containing all the largest remaining elements, and so on. The graph $G(Av_n(132, 213))$ is regular of indegree 2 and outdegree 2, because any layered permutation on $n-1$ elements can be extended at the front end in one of two ways, by prepending a new first entry into the first layer, or by creating a new layer by prepending $n$, and likewise can be extended at the back end in either of two ways.
## 3 Classes defined by restrictions of lengths 3 and 4

In this section we look at pattern classes which are defined by avoiding at least one restriction of length 3 and at least one of length 4. In order to have a hope of being pattern cyclic for all $n$, such a class must first of all be pattern cycle at length 3, which means that the 3-restrictions must be of one of the forms considered in the previous section. (The table in that section may be a convenient reference.)

To these we wish to add some 4-restrictions, which we should do in such a way as to produce an Eulerian graph at length 4. To assist with this selection process, Figures 3, 4, 5, 6, 7, and 8 show the length-4 graphs for the various sets of 3-restrictions.

Here is our table for mixed groups of restrictions from $S_3$ and $S_4$, again taking advantage of symmetries and including only those for which $G(Av_3(T))$ and $G(Av_4(T))$ are Eulerian. We have only indicated the class sizes where Eulerian cycles exist.

<table><thead><tr><th>Class</th><th>Size of Class</th><th>Properties</th></tr></thead><tbody><tr><td>Av<sub>n</sub>(123, 3142, 3412)</td><td>2<sup>n</sup> - n</td><td>value cyclic</td></tr><tr><td>Av<sub>n</sub>(123, 3142, 2413)</td><td></td><td>not cyclic: {c,d,e}4312{a,b}</td></tr><tr><td>Av<sub>n</sub>(123, 3142, 3421, 4312)</td><td></td><td>not cyclic: {}4213{a,c}</td></tr><tr><td>Av<sub>n</sub>(123, 2143, 3412)</td><td></td><td>not cyclic: {e}4132{a,b}</td></tr><tr><td>Av<sub>n</sub>(123, 2143, 2413)</td><td></td><td>not cyclic: {c,d,e}4312{a,b}</td></tr><tr><td>Av<sub>n</sub>(123, 2143, 3421, 4312)</td><td></td><td>not cyclic: {}4213{a}</td></tr><tr><td>Av<sub>n</sub>(132, 312, 1234)</td><td>(n/2) + 1</td><td>pattern cyclic</td></tr><tr><td>Av<sub>n</sub>(132, 312, 3241, 2314)</td><td>2(n-1)</td><td>pattern cyclic</td></tr><tr><td>Av<sub>n</sub>(132, 312, 3241, 2314, 1234)</td><td></td><td>not cyclic: {c}2134{}</td></tr><tr><td>Av<sub>n</sub>(132, 213, 1234)</td><td></td><td>not cyclic: {d,e}4123{a}</td></tr><tr><td>Av<sub>n</sub>(132, 213, 3412, 4231)</td><td>2(n-1)</td><td>pattern cyclic</td></tr><tr><td>Av<sub>n</sub>(132, 213, 4321)</td><td>(n/2) + 1</td><td>pattern cyclic</td></tr><tr><td>Av<sub>n</sub>(132, 213, 3412, 4231, 1234)</td><td></td><td>not cyclic: {e}4123{}</td></tr><tr><td>Av<sub>n</sub>(132, 213, 3412, 4231, 4321)</td><td></td><td>not cyclic: {}4312{c}</td></tr><tr><td>Av<sub>n</sub>(132, 213, 123, 3412)</td><td>n</td><td>pattern cyclic</td></tr></tbody></table>

There are no lines in the table corresponding to the two classes of size $n$ in the previous section. The graphs of these classes, seen for $n = 4$ in Figure 5 and 8, each consist (for all $n$) of a single cycle. Therefore no addition of any further restrictions (of any length $n$) could leave these graphs Eulerian (or even connected) except for the removal of the loop. This, however, would eventually lead to empty pattern classes by the Erdős-Szekeres theorem.

The addition of the restriction 3412 to the avoidance class $Av(132, 213, 123)$ leaves a similar set of graphs which are simply $n$-cycles (and so are not subject to further modification). The $n$-permutations belonging to $Av_n(132, 213, 123, 3412)$ consist of the all-decreasing permutation, plus those permutations obtained from it by a single adjacent transposition. It is pattern cyclic: from the all-decreasing sequence, transition to $n, n-1, \dots, 4, 3, 1, 2$, while from every other permutation in the class, transition by appending a new smallest element.

The class $Av(132, 213, 4321)$ is interesting. As we saw in the previous section, $Av(132, 213)$ is the class of layered permutations, and each has indegree 2 and outdegree 2, the two options being to extend the final layer, or to add a new layer. The addition of the restriction 4321 modifies the class by restricting
<figure><img src="image_3.png" /><figcaption>Fig. 3: The directed graph $G(Av_4(123))$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 4: The directed graph $G(Av_4(132, 312))$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 5: The directed graph $G(Av_4(132, 312, 123))$.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Fig. 6: The directed graph $G(Av_4(132, 213))$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 7: The directed graph $G(Av_4(132, 213, 123))$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 8: The directed graph $G(Av_4(132, 213, 321))$.</figcaption></figure>
the number of layers to at most 3, so that in the new class a permutation with one or two layers has indegree and outdegree 2, while a permutation with three layers has outdegree only 1.

This observation generalizes to the following simple proposition, which gives us an infinite family of pattern cyclic, but non-cyclically-closed, avoidance classes.

**Proposition 3** For all $j \ge 3$, the class $Av_n(132, 213, j \dots 321)$ is pattern cyclic for all $n$.

**Proof:** The class consists of layered permutations with fewer than $j$ layers. An $(n-1)$-permutation with $j-1$ layers will have indegree and outdegree 1, while one with $j-2$ or fewer layers will have indegree and outdegree 2. $\square$

The class $Av_n(132, 213, 3412, 4231)$ is the union of two sets of permutations, those of form $(j+1, j+2, \dots, n, j, j-1, \dots, 1)$ for some $j$, and those of form $(n, n-1, \dots, j+1, 1, 2, \dots, j)$ for some $j$. Each permutation in the class has outdegree 1 if it is of the first type, then only a new minimum element can be added, while if it is of the second type, only an element just larger than the final element can be added. Thus they are easily cycled by running through the permutations of the first kind, always adding a new smallest element, until arriving at the all-descending permutation, and then switching to the other type, adding new elements between $j$ and $j+1$ until arriving at the all-increasing permutation. It is easy to see that this class is not value cyclic.

The class $Av_n(132, 312, 3241, 2314)$ is very similar; the permutations in this class are those of the form $(j+1, j+2, \dots, n, j, j-1, \dots, 1)$ or of form $(j, j-1, \dots, 1, j+1, j+2, \dots, n)$. This class is also not value cyclic, as can be seen by examining the case for $n=4$.

The permutations in the class $Av_n(132, 312, 1234)$ are built by taking the elements $n-2, n-3, \dots, 2, 1$ in a descending sequence, and then inserting $n-1$ and $n$ somewhere along the sequence, with $n-1$ on the left. These thus correspond to all the 2-element subsets of $n$. They can be cycled by taking the large element $n-2$ off the front, putting a new small element at the end, and, when $n-1$ reaches the front, managing the separation between $n-1$ and $n$.

The final example is $Av_n(123, 3142, 3412)$. The permutations in this class are in fact similar to those in the class $Av_n(132, 312)$ studied in the previous section.

**Proposition 4** The class $Av(123, 3142, 3412)$ is value cyclic for all $n$.

**Proof:** Beginning with a bitstring of length $n$, replace all the 1s in the string with a decreasing *upper sequence*, $n, n-1, n-2, \dots, j+1$, then replace all the 0s with a decreasing *lower sequence*, $j, j-1, \dots, 1$. This gives a priori $2^n$ permutations, but there is an overcount of $n$ because the all-decreasing permutation is constructed by all of the $n+1$ bitstrings of the special form `111...11000...00`. To see that the class is pattern-cyclic, observe that an ordinary vertex (i.e. with a bitstring not in the special form) has indegree 2 and outdegree 2, by prepending or appending a bit, while the special vertex $n-1, n-2, \dots, 2, 1$ has indegree and outdegree $n$, because we can choose any of its $n$ forms and append a 1 (not a 0 as this would simply loop back to the special vertex; the correct way to follow the loop is to append a 1 to the all-1s string). To express the same thing at the level of permutations, if both an upper and a lower sequence are really present, either can be extended, giving indegree and outdegree 2, while the all-descending sequence can be preceded or followed by a new element of any value.

We will show how to select an Eulerian cycle in $G(Av_n(123, 3142, 3412))$ in a careful way which allows the construction of a universal cycle. The special vertex $n-1, \dots, 1$ has $n$ incoming edges, namely the loop $n, \dots, 1$ (which can be coded in $n+1$ different ways as a bitstring) and the $n-1$
permutation corresponding to bitstrings of the form $01^k0^{n-1-k}$ for $k$ ranging from 1 to $n-1$. Note that $k$ cannot be zero, because this would be the all-zero bitstring, one of the possible codings for the loop. Similarly, the special vertex has $n$ outgoing edges, the loop plus the $n-1$ edges of the form $1^k0^{n-1-k}1$ for $k$ ranging from 0 to $n-2$. As far as the rules by which permutations may succeed permutations in Eulerian cycles, any incoming edge may be followed by any outgoing edge, but now we will insist that an incoming edge $01^k0^{n-1-k}$ be followed by an outgoing edge $1^k0^{n-1-k}1$ with the same value of $k$ (in permutation terms this means that the element removed from the front of the permutation is immediately reattached at the end).

Thus every incoming edge has a corresponding outgoing edge, for $k$ between 2 and $n-1$. This leaves the incoming $01^{n-1}$ and the outgoing $0^{n-1}1$, which will be matched with one another, with the loop-edge $n, \dots, 1$ intervening. Now we will construct an Eulerian circuit, beginning with the loop-edge. Write down $0^n$ (one of the codes for the loop-edge), and then append a 1 to move on to edge $0^{n-1}1$, and continue to construct an Eulerian circuit, appending a bit each time, taking care that each time the special vertex is visited, the succession rule for bitstrings is followed.

This assures that the final edge in our Eulerian circuit will be the one corresponding to the bitstring $01^{n-1}$. Add one more 1 at the end, so that now we have a long bitstring of length $2^n$, beginning with $n$ zeroes and ending with $n$ ones. Replace the zeroes, from left to right, with the decreasing values $2^{n-1}, \dots, 1$, and replace the ones, from left to right, with the decreasing values $2^n - n, \dots, 2^{n-1} - n + 1$. Noting that the $n$ zeroes at the beginning and the $n$ ones at the end have thus been assigned the same values, identify them to form a cycle. Using the construction, it is easy to verify that this is a universal cycle for the given pattern class. $\square$

We observe an interesting phenomenon in our table, and in the table for length-3 permutations given in the previous section. When a class failed to be pattern cyclic for all $n$, we were always able to give a counterexample of the shortest possible length. This leads us to the following tentative conjecture.

**Conjecture 5** Let $T$ be a set of patterns including some of length $k$ and possibly some of shorter lengths. If $Av_k(T)$ and $Av_{k+1}(T)$ are pattern (value) cyclic, then $Av_n(T)$ is pattern (value) cyclic for all $n$.

Another potentially interesting question is the one settled in [9] for the case of $S_n$, namely for value-cyclic classes, what is the minimum number of distinct values necessary to construct a universal cycle? That is, given $n$, what is the least $c_n$ such that there is a sequence of positive integers bounded above by $c_n$ that represents the class?

## References

[1] M. Bona (1999), M. The solution of a conjecture of Stanley and Wilf for all layered patterns, *J. Combin. Th. Ser. A* 85, 96-104.

[2] F. Chung, P. Diaconis and R. Graham (1992), Universal cycles for combinatorial structures, *Discrete Math.* 110, 43-59.

[3] N. G. de Bruijn (1946), A combinatorial problem, *Koninklijke Nederlandse Akademie v. Wetenschap-pen* 49, 758764.

[4] N. G. de Bruijn (1975), Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of $2n$ zeros and ones that show each $n$-letter word exactly once, *T.H.-Report 75-WSK-06, Technological University Eindhoven*, 13 pages.
[5] P. Erdős and G. Szekeres (1935), A combinatorial problem in geometry, *Compositio Mathematica* 2, 463-470.

[6] C. Flye Sainte-Marie (1894), Solution to question nr. 48., *L'intermédiaire des Mathématiciens* 1, 107110.

[7] G. Hurlbert and G. Isaak (1996), Equivalence class universal cycles for permutations, *Discrete Math.* 149, 123-129.

[8] B. Jackson (1993), Universal cycles of *k*-subsets and *k*-permutations, *Discrete Math.* 117, 114-150.

[9] J. R. Johnson (2008), Universal cycles for permutations, *Discrete Math.*, in press, corrected proof

[10] A. Leitner and A. Godbole (2008), Universal cycles of classes of restricted words, arXiv:0808.1309v1