# Number of cycles in the graph of 312-avoiding permutations

Richard Ehrenborg<fnref n="1" />* Sergey Kitaev<fnref n="2" />† Einar Steingrímsson<fnref n="2" />‡

The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. However, instead of requiring the tail of one permutation to equal the head of another for them to be connected by an edge, we require that the head and tail in question have their letters appear in the same order of size. We give a formula for the number of cycles of length $d$ in the subgraph of overlapping 312-avoiding permutations. Using this we also give a refinement of the enumeration of 312-avoiding affine permutations.

Le graphique de permutations qui se chevauchent est définie d'une manière analogue à celle du graphe de De Bruijn sur des chaînes de symboles. Cependant, au lieu d'exiger la queue d'une permutation d'égaler la tête d'un autre pour qu'ils soient reliés par un bord, nous avons besoin que la tête et la queue en question ont leurs lettres apparaissent dans le même ordre de grandeur. Nous donnons une formule pour le nombre de cycles de longueur $d$ dans le sous-graphe de chevauchement 312-évitant permutations. L'utilisation de ce nous donnent également un raffinement de l'énumération de 312-évitant permutations affines.

**Keywords:** permutation pattern, graph of overlapping permutations, number of cycles, affine permutations

## 1 Introduction and preliminaries

One of the classical objects in combinatorics is the *De Bruijn graph*. This is the directed graph on vertex set $\{0, 1, \dots, q-1\}^n$, the set of all strings of length $n$ over an alphabet of size $q$, whose directed edges go from each vertex $x_1 \cdots x_n$ to each vertex $x_2 \cdots x_{n+1}$. That is, there is a directed edge from a string $x$ to $y$ if and only if the last $n-1$ coordinates of $x$ agree with the first $n-1$ coordinates of $y$.

The De Bruijn graph has been much studied, especially in connection with combinatorics on words, and one of its well known properties is the fact that its number of directed cycles of length $d$, for $d \le n$, is given by

$$ \frac{1}{d} \sum_{e|d} \mu(d/e) q^e, \qquad (1.1) $$

<footnote n="1">¹Department of Mathematics, University of Kentucky, Lexington, KY 40506-0027, USA</footnote>

<footnote n="2">²Department of Computer and Information Sciences, University of Strathclyde, Glasgow G1 1XH, UK</footnote>

<footnote>*Email: jrge@ms.uky.edu. Partially supported by National Science Foundation grant DMS 0902063 and National Security Agency grant H98230-13-1-0280.</footnote>

<footnote>†Email: sergey.kitaev@cis.strath.ac.uk.</footnote>

<footnote>‡Email: einar@alum.mit.edu. Supported by grant no. 090038013 from the Icelandic Research Fund.</footnote>
where the sum is over all divisors $e$ of the length $d$, and where $\mu$ denotes the number theoretic Möbius function. Recall that $\mu(n)$ is $(-1)^k$ if $n$ is a product of $k$ distinct primes and is zero otherwise.

A natural variation on the De Bruijn graphs is obtained by replacing words over an alphabet by permutations of the set of integers $\{1, 2, \dots, n\}$, where the overlapping condition determining directed edges in De Bruijn graphs is replaced by the condition that the head and tail of two permutations have the same *standardization*, that is, that their letters appear in the same order of size. As an example, this is the case with the permutations 24513 and 35124, since 4513 and 3512 both have their letters appearing in the same order of size, namely as 3412. This *graph of overlapping permutations*, denoted $G(n)$, is what we study in this paper. Note that, apart from the path and cycle graphs mentioned in Section 3, all graphs in this paper are directed, although we don't explicitly refer to them as directed graphs.

The graph $G(n)$ appeared in [4] in connection with *universal cycles on permutations*. It has also appeared in [7], where it was used as a tool in determining the asymptotic behavior of consecutive pattern avoidance, and in [2], where it is called the *graph of overlapping patterns* (see also [11, Section 5.6]).

A natural question about this graph, which does not seem to have been studied so far, is what its number of directed cycles is, the analogue to the question for which (1.1) is the answer. We have not been able to solve that problem (and we do not recognize the associated number sequences). We do here, however, solve that problem when the graph is restricted to permutations of length $n$ avoiding the pattern 312, that is, permutations containing no three letters the first of which is the largest and the second one the smallest. We show here that the number of directed cycles of length $d$ is

$$ \frac{1}{d} \sum_{e|d} \mu(d/e) \binom{2e}{e}, \qquad (1.2) $$

for $d$ not exceeding $n$. Note the similarity between this and the expression in (1.1): the power $q^e$ in (1.1) is replaced here by the central binomial coefficient $\binom{2e}{e}$.

It is easy to see, due to straightforward symmetries, that permutations avoiding a particular one of the patterns 132, 213 and 231 yield a graph isomorphic to the one for 312, which is the representative we have chosen. It is also easy to see that permutations avoiding 123 (or, equivalently, 321) give rise to a nonisomorphic graph. For this latter case we have no solution for the number of cycles, and we do not recognize the number sequences counting the cycles in that graph.

Using similar techniques, we prove that the number of 312-avoiding *affine permutations* in $\tilde{\mathfrak{S}}_d$ with $k$ cut-points is given by the binomial coefficient $\binom{2d-k-1}{d-1}$. This refines a result of Crites [6] who showed that the number of 312-avoiding affine permutations is $\binom{2d-1}{d-1}$. As a corollary to our results we show that each affine permutation has a cut-point or is, in other words, decomposable.

The connection between cycles in the graph of overlapping permutations and affine permutations goes through bi-infinite sequences. A bi-infinite sequence $(\dots, f(-1), f(0), f(1), f(2), \dots)$ of distinct real numbers yields a bi-infinite walk where the $i$th edge is given by the standardization of $f = (f(i), f(i+1), \dots, f(i+n))$, that is, the unique permutation of $\{1, 2, \dots, n+1\}$ whose letters appear in the same order of size as the numbers in $f$. This walk is a closed walk of length $d$ if the sequence is periodic, in the sense that $f(i) < f(j)$ if and only if $f(i+d) < f(j+d)$. Thus, infinite $d$-periodic sequences correspond to $d$-cycles.

The paper is organized as follows. In Section 2 we introduce some definitions related to pattern avoidance, affine permutations and infinite sequences. The last of these play an important role in the proof of the main result, as do ordinary and cyclic compositions of an integer, which are introduced in Section 3. In Section 4 we give results on the number of affine 312-avoiding permutations with a given number of cut-points and show that every such permutation does have a cut-point. In Section 5 we present the main
result, about the number of d-cycles in G(n, 312) and subsequently give a bijection that proves this, in Sections 6 and 7. The full version of the paper is available as [8], where we list several open problems in this area.

## 2 Pattern-avoiding permutations, affine permutations and infinite sequences

We first introduce some formal definitions that are needed later on.

For a permutation $x = x_1 \cdots x_n$ consisting of distinct real numbers, let $\Pi(x)$ denote the *standardization of x*, also known as the *reduced form of x*, that is, the unique permutation $\pi = \pi_1 \cdots \pi_n$ in the symmetric group $S_n$ whose elements have the same relative order as those in $x$. In other words, $x_i < x_j$ if and only if $\pi_i < \pi_j$ for all $1 \le i < j \le n$ and $\pi$ is built on the set $\{1, 2, \dots, n\}$. For example, $\Pi(3(-2)02) = 4123$.

The graph of overlapping permutations $G(n)$ has the elements of the symmetric group $S_n$ as its vertex set and for every permutation $\sigma = \sigma_1 \cdots \sigma_{n+1}$ in $S_{n+1}$ there is a directed edge from $\Pi(\sigma_1 \cdots \sigma_n)$ to $\Pi(\sigma_2 \cdots \sigma_{n+1})$.

A permutation $\pi = \pi_1\pi_2\cdots\pi_n \in S_n$ avoids a permutation $\tau \in S_k$ if there are no integers $1 \le i_1 < i_2 < \cdots < i_k \le n$ such that $\Pi(\pi_{i_1}\pi_{i_2}\cdots\pi_{i_n}) = \tau$. In this context, $\tau$ is called a *pattern* and we say that $\pi$ avoids the pattern $\tau$. Let $S_n(\tau)$ denote the set of $\tau$-avoiding permutations in $S_n$. Especially, we are interested in 312-avoiding permutations, which are those that have no indices $i < j < k$ such that $\pi_j < \pi_k < \pi_i$. It is well-known that the number of 312-avoiding permutations in $S_n$ is given by the nth *Catalan number* $C_n = \frac{1}{n+1}\binom{2n}{n}$.

A cut-point for a permutation $\pi \in S_n$ is an index $j$ with $1 \le j \le n-1$ such that for all $i$ and $k$ satisfying $1 \le i \le j < k \le n$ we have that $\pi_i < \pi_k$. The cut-points split a permutation into *components*, each ending at a cut-point. A permutation without cut-points is said to be *indecomposable* (or, sometimes, *irreducible*). As an example, the permutation 31246758 has three cut-points, namely 3, 4, and 7, and components 312, 4, 675 and 8, whereas 2413 is indecomposable. The following result is well-known (see, for instance, [5] or Stanley's list of Catalan interpretations [15]), and is easy to prove using the fact that every 312-avoiding permutation is of the form $A1B$, where each element of $B$ is larger than every element of $A$, which implies that a 312-avoiding permutation is indecomposable precisely when $B$ is empty.

**Proposition 2.1** *The number of 312-avoiding indecomposable permutations in $S_n$ is given by the Catalan number $C_{n-1}$.*

An extension of the notion of permutations is affine permutations. While the symmetric group $S_d$ is the Weyl group $A_{d-1}$, the group of affine permutations $\tilde{S}_d$ is the affine Weyl group $\tilde{A}_{d-1}$. However, the combinatorial description of affine permutations is due to Lusztig (unpublished) and the first combinatorial study of them was conducted in [3, 9]. An *affine permutation* is a bijection $\pi : \mathbb{Z} \to \mathbb{Z}$ such that

$$ \pi(i+d) = \pi(i) + d, \qquad (2.1) $$

$$ \sum_{i=0}^{d-1} (\pi(i) - i) = 0. \qquad (2.2) $$

Note that the first condition implies that the values $\pi(0)$ through $\pi(d-1)$ determine the whole affine permutation. The set of all affine permutations is denoted by $\tilde{S}_d$.
We now extend the notion of an affine permutation to infinite sequences. An infinite sequence is defined to be an injective function $f : \mathbb{Z} \to \mathbb{R}$. Alternatively, one can think of an infinite sequence as a bi-infinite list $(\dots, f(-1), f(0), f(1), f(2), \dots)$ of distinct real numbers. We say that two infinite sequences $f$ and $g$ are equivalent if there is a strictly increasing continuous function $T : \mathbb{R} \to \mathbb{R}$ such that $g(i) = T(f(i))$. It is straightforward that this is an equivalence relation. We think about the equivalence classes as bi-infinite permutations. Hence, it is natural to extend notions from permutation patterns theory to (bi-)infinite sequences.

A cut-point for a bi-infinite sequence $f$ is an index $j$ such that for all integers $i \le j < k$ we have that $f(i) < f(k)$. The inversion set for a bi-infinite sequence $f$ is the set

$$ \mathrm{Inv}(f) = \{(i, j) \in \mathbb{Z}^2 : i < j, f(i) > f(j)\}. $$

A bi-infinite sequence is periodic with period $d$, if for all integers $i$ and $j$, $f(i) < f(j)$ is equivalent to $f(i + d) < f(j + d)$. Equivalently, a bi-infinite sequence is periodic with period $d$ if the inversion set satisfies the condition $(i, j) \in \mathrm{Inv}(f)$ is equivalent to $(i + d, j + d) \in \mathrm{Inv}(f)$. Extending the notion of pattern-avoidance, we say that a bi-infinite sequence $f$ avoids the pattern $\sigma \in \mathfrak{S}_n$ if there are no integers $i_1 < i_2 < \dots < i_n$ such that $\Pi(f(i_1)f(i_2)\dots f(i_n)) = \sigma$.

## 3 Compositions and cyclic compositions

A composition of a non-negative integer $d$ into $k$ parts is a list of $k$ positive integers $(a_1, a_2, \dots, a_k)$ such that their sum is $d$. Let $\alpha_1, \alpha_2, \dots$ be a sequence of numbers and $f(t) = \sum_{i \ge 1} \alpha_i t^i$ be the associated generating function. Form a new sequence $(\beta_{d,k})_{d \ge 1}$ by the relation

$$ \beta_{d,k} = \sum_{(a_1, a_2, \dots, a_k)} \alpha_{a_1} \alpha_{a_2} \cdots \alpha_{a_k} $$

where the sum is over all compositions of $d$ into $k$ parts. Additionally, we set $\beta_{0,k}$ to be the Kronecker delta $\delta_{0,k}$, which is equal to 1 if $k = 0$ and 0 otherwise. Also, let the sequence $(\beta_d)_{d \ge 0}$ be defined by the sum $\beta_d = \sum_{k \ge 0} \beta_{d,k}$. The following relations are classical generating functionology:

$$ \sum_{d \ge 0} \beta_{d,k} t^d = (f(t))^k \quad \text{and} \quad \sum_{d \ge 0} \beta_d t^d = \frac{1}{1 - f(t)}. \qquad (3.1) $$

If $\alpha_i$ is the cardinality of a set $S_i$, we can give a combinatorial interpretation to the number $\beta_{d,k}$, hence also $\beta_d$. An enriched composition is a pair $(\mathbf{a}, \mathbf{s})$ where $\mathbf{a}$ is a composition $(a_1, a_2, \dots, a_k)$ of $d$ into $k$ parts and $\mathbf{s} = (s_1, s_2, \dots, s_k)$ is a list of the same length such that the element $s_i$ belongs to the set $S_{a_i}$. Now $\beta_{d,k}$ is the number of enriched compositions of $d$ into $k$ parts, and $\beta_d$ is the number of enriched compositions of $d$.

A composition of $d$ can be thought of as a subgraph of the path on $d$ vertices. Note that each connected component of a subgraph of a path is also a path. The number of connected components of the subgraph is the number of parts of the composition. With this analogue in mind we define a cyclic composition to be a subgraph of the cycle on $d$ vertices where each component is a path. Note that we rule out the case of the cycle being a subgraph of itself. Yet again, the number of paths is the number of components $k$. Observe that $k$ is also the number of edges removed to obtain the subgraph. Since there are $d$ edges in a
cycle, we have $\binom{d}{k}$ cyclic compositions of $d$ into $k$ parts for $k \ge 1$. For instance, there are $\binom{4}{2} = 6$ cyclic compositions of 4 into two parts, namely, two consisting of two 2s and four consisting of 1 and 3.

To be more formal, let $\mathbb{Z}_d$ denote both the integers modulo $d$ and the cycle of length $d$, where we connect $i$ and $i + 1$ modulo $d$. A cyclic composition is a set partition $P = \{B_1, B_2, \dots, B_k\}$ where each block $B_i$ is a path in the cycle $\mathbb{Z}_d$. Equivalently, each block $B_i$ is the image of an interval $[p_i, q_i]$ of integers under the quotient map $\mathbb{Z} \to \mathbb{Z}_d$ with the restriction $0 \le q_i - p_i \le d - 1$. Also, let $a_i$ be $q_i - p_i + 1$, that is, the cardinality of the interval $[p_i, q_i]$ and the associated path.

Similarly to compositions, we construct new sequences $(\gamma_{d,k})_{d \ge 1}$ and $(\gamma_d)_{d \ge 1}$ as follows:

$$ \gamma_{d,k} = \sum_{P} \alpha_{a_1} \alpha_{a_2} \cdots \alpha_{a_k} $$

where the sum is over all cyclic compositions $P$ of $d$ into $k$ parts and $a_i$ is the size of the $i$th part. Also, let $\gamma_d$ denote the sum $\gamma_d = \sum_{k \ge 1} \gamma_{d,k}$.

**Proposition 3.1** The generating functions for $\gamma_{d,k}$ and $\gamma_d$ are given by

$$ \sum_{d \ge k} \gamma_{d,k} t^d = tf'(t)(f(t))^{k-1} = \frac{t}{k} D((f(t))^k) \quad \text{and} \quad (3.2) $$

$$ \sum_{d \ge 1} \gamma_d t^d = \frac{tf'(t)}{1 - f(t)}, \quad (3.3) $$

where $D$ is the differential operator with respect to $t$.

**Proof:** To observe the first relation, consider the component containing the vertex 1 of the cycle. Also, assume that this component has size $i$. Then there are $i$ possibilities how to choose the component. This is encoded by the generating function $\sum_{i \ge 1} i \alpha_i t^i = tf'(t)$. Next we have to choose a composition of $d - i$ into $k - 1$ parts, which is given by $(f(t))^{k-1}$. The first result follows from multiplication of generating functions. The second result follows from summing (3.2) over all $k$. $\square$

As a brief example of equation (3.3), note that setting $\alpha_i = 1$ enumerates the number of cyclic compositions. We have $f(t) = 1/(1-t) - 1$ and obtain $\sum_{d \ge 1} \gamma_d t^d = 1/(1-2t) - 1/(1-t)$, yielding the answer of $2^d - 1$ for the number of cyclic compositions of $d$.

Combining generating functions (3.1) and (3.2) we have the following result.

**Corollary 3.2** The two quantities $\beta_{d,k}$ and $\gamma_{d,k}$ are related by

$$ \gamma_{d,k} = \frac{d}{k} \beta_{d,k}. \quad (3.4) $$

An enriched cyclic composition is a pair $(P, s)$ where $P$ is a cyclic composition $\{B_1, B_2, \dots, B_k\}$ of $d$ into $k$ parts and $s = (s_1, s_2, \dots, s_k)$ is a list of the length $k$ such that the element $s_i$ belongs to the set $S_{|B_i|}$. Now $\gamma_{d,k}$ has the combinatorial interpretation as the number of enriched cyclic compositions of $d$ into $k$ parts, and $\beta_d$ is the number of enriched cyclic compositions of $d$.
Let $C(t)$ and $CB(t)$ denote the generating functions for the Catalan numbers and the central binomial coefficients, that is,

$$C(t) = \sum_{d \ge 0} C_d t^d = \frac{1 - \sqrt{1 - 4t}}{2t},$$ $$CB(t) = \sum_{d \ge 0} \binom{2d}{d} t^d = \frac{1}{\sqrt{1 - 4t}}.$$

**Lemma 3.3** Let $\alpha_i = C_{i-1} + \delta_{i,1}$ where $\delta_{i,1}$ denotes the Kronecker delta. Then the central binomial coefficient is given by the sum

$$\binom{2d}{d} = \sum_{P} \alpha_{a_1} \alpha_{a_2} \cdots \alpha_{a_k},$$

where the sum is over all cyclic compositions $P$ of $d$ and $d \ge 1$.

**Proof:** First, observe that $\sum_{i \ge 1} \alpha_i t^i = t + tC(t)$. The result now follows from equation (3.3) and the identity

$$CB(t) - 1 = \frac{t(t + tC(t))'}{1 - t - tC(t)}.$$

□

The following two well-known identities involving the Catalan numbers are worth keeping in mind in the next section, where we prove similar results regarding affine 312-avoiding permutations. We have

$$\sum_{(a_1, a_2, \dots, a_k)} C_{a_1-1} C_{a_2-1} \cdots C_{a_k-1} = \frac{k}{d} \binom{2d-k-1}{d-1}, \qquad (3.5)$$

where the sum is over all compositions of $d$ into $k$ parts. The numbers in the right hand side give Catalan's triangle, sequence A009766 in [12]. One of many things they enumerate is the set of 312-avoiding permutations of length $d$ that split into (at most) $k$ components. Namely, such a permutation can be decomposed as $A_1A_2 \cdots A_k$ where every letter of $A_i$ is smaller than each letter of $A_j$ for $i < j$. Since each component is an indecomposable 312-avoiding permutation, these permutations with $k$ components are counted by the left hand side. By a similar argument we have

$$\sum_{(a_1, a_2, \dots, a_k)} C_{a_1-1} C_{a_2-1} \cdots C_{a_k-1} = C_d,$$

where the sum is over all compositions of $d$.

By combining Corollary 3.2 and (3.5) we have:

**Lemma 3.4** The following identity holds

$$\sum_{P} C_{a_1-1} C_{a_2-1} \cdots C_{a_k-1} = \binom{2d-k-1}{d-1}, \qquad (3.6)$$

where the sum is over all cyclic compositions $P$ of $d$ into $k$ parts.
## 4 312-avoiding affine permutations

Before we continue, we take a detour to study 312-avoiding affine permutations. Recall that an affine permutation $\pi \in \tilde{\mathfrak{S}}_d$ is 312-avoiding if there are no indices $x < y < z$ such that $\pi(y) < \pi(z) < \pi(x)$. Crites [6] proved the following result for affine permutations.

**Theorem 4.1 (Theorem 6 in [6])** *The number of 312-avoiding affine permutations in $\tilde{\mathfrak{S}}_d$ is given by $\binom{2d-1}{d}$.*

We give a refinement of this result. Recall that a cut-point for an affine permutation $\pi$ is an index $j$ such that for $i \le j < k$ the inequality $\pi(i) < \pi(k)$ holds. Especially, if $j$ is a cut-point, then so is any index congruent to $j$ modulo $d$. Hence, we count the number of equivalence classes of cut-points.

**Theorem 4.2 ([8])** Let $k$ be a positive integer and $k \le d$. The number of 312-avoiding affine permutations in $\tilde{\mathfrak{S}}_d$ that have $k$ cut-points modulo $d$ is given by

$$ \binom{2d - k - 1}{d - 1}. $$

**Corollary 4.3** Every 312-avoiding affine permutation in $\tilde{\mathfrak{S}}_d$ has a cut-point.

*Proof:* Since the sum of $\binom{2d-k-1}{d-1}$ for $k$ from 1 to $d$ is $\binom{2d-1}{d}$, and by Theorem 4.1, all the 312-avoiding affine permutations have been accounted for. $\square$

## 5 The graph of 312-avoiding permutations

Recall that $G(n)$ denotes the directed graph of overlapping permutations, that is, it has the vertex set $\mathfrak{S}_m$ and for every permutation $\sigma = \sigma_1 \cdots \sigma_{m+1}$ in $\mathfrak{S}_{m+1}$ there is a directed edge from $\Pi(\sigma_1 \cdots \sigma_m)$ to $\Pi(\sigma_2 \cdots \sigma_{m+1})$ labelled $\sigma$. Furthermore, let $G(n, \tau)$ be the graph of overlapping $\tau$-avoiding permutations, that is, it is the subgraph of $G(n)$ having the vertex set $\mathfrak{S}_n(\tau)$ and the edge set $\mathfrak{S}_{n+1}(\tau)$.

A closed walk of length $d$ in a graph is a list of $d$ edges $(e_1, e_2, \dots, e_d)$ such that $\text{head}(e_i) = \text{tail}(e_{i+1})$ for $1 \le i \le d-1$ and $\text{head}(e_d) = \text{tail}(e_1)$, where for a directed edge $e$, $\text{head}(e)$ is the node the edge points to, while $\text{tail}(e)$ is the other node incident to $e$. Thus, (1342, 2314, 2134) and its cyclic shift (2134, 1342, 2314) are two different closed walks.

Define an equivalence on the set of closed walks by cyclic shifting, that is, the two closed walks $(e_1, e_2, \dots, e_d)$ and $(e_i, e_{i+1}, \dots, e_d, e_1, e_2, \dots, e_{i-1})$ are equivalent for any $i$. Then a $d$-cycle is defined to be an equivalence class of size $d$. For instance, the graph $G(3, 312)$ has six closed walks of length 2, namely,

$$ (1234, 1234), (4321, 4321), (1324, 2143), (2143, 1324), (2314, 3241) \text{ and } (3241, 2314). $$

However, the graph $G(3, 312)$ has only two 2-cycles, since the first two closed walks yield 1-cycles while the fourth (resp., sixth) walk is equivalent to the third (resp., fifth) walk.

The number of closed walks is given by the following result.

**Theorem 5.1** The number of closed walks of length $d$ in $G(n, 312)$, for $d \le n$, is given by $\binom{2d}{d}$.

A bijective proof of Theorem 5.1 will be given in the following two sections.
**Theorem 5.2** The number of d-cycles in G(n, 312), for d ≤ n, is given by

$$ \frac{1}{d} \sum_{e|d} \mu(d/e) \binom{2e}{e}. $$

**Proof:** Let $h(d)$ denote the number of d-cycles. A closed walk of length $d$ can be obtained by choosing a divisor $e$ of $d$, an $e$-cycle and a starting point on the cycle. By repeating the $e$-cycle $d/e$ times we obtain a closed walk of length $d$. Hence, we have $\binom{2d}{d} = \sum_{e|d} e \cdot h(e)$. The result now follows by classical Möbius inversion. $\square$

# 6 The bijection

It remains to show that the number of closed walks of length $d$ in $G(n, 312)$ is given by $\binom{2d}{d}$. We do this by constructing a bijection between closed walks and enriched cyclic compositions. This bijection goes via infinite sequences. Let $Q_d$ denote the set of all closed walks of length $d$ in the graph $G(n, 312)$.

Given a cyclic composition on $\mathbb{Z}_d$, we enrich each part of size $a$ either with a 312-avoiding indecomposable permutation from the symmetric group $S_a$, or, if $a = 1$, with the symbol $D$ (for “Down”). Note that if $a = 1$, then the enrichment is either the identity permutation 1 in $S_1$ or the symbol $D$. Let $E_d$ denote the set of all these enriched cyclic compositions. Note that the number of enrichments of a part of size $a$ is the Catalan number $C_{a-1}$ plus the Kronecker delta $\delta_{a,1}$. Hence, by Lemma 3.3, we know that the total number of these structures is the central binomial coefficient $\binom{2d}{d}$.

We now describe a bijection $\Phi: E_d \to Q_d$. Let $B = (B_1, B_2, \dots, B_k)$ be an enriched cyclic composition in $E_d$. Recall that the $i$th block $B_i$ is the image of the interval $[p_i, q_i]$ under the quotient map $\mathbb{Z} \to \mathbb{Z}_d$. If the enrichment on the part $B_i$ is a permutation, we view it as a permutation $\pi_i$ on the set $[p_i, q_i]$. Let $\bar{B}_i$ be the set $\bar{B}_i = \cup_{j \in \mathbb{Z}} [p_i + jd, q_i + jd]$. Note that $\bar{B}_1, \bar{B}_2, \dots, \bar{B}_k$ is a partition of the integers $\mathbb{Z}$. Furthermore, extend $\pi_i$ by the relation $\pi_i(j+d) = \pi_i(j) + d$. That is, now $\pi_i$ is a bijection on the set $\bar{B}_i$. Next we use the fact that the exponential function $\exp: \mathbb{R} \to \mathbb{R}_{>0}$ is strictly increasing and its negative $-\exp: \mathbb{R} \to \mathbb{R}_{<0}$ is strictly decreasing, where $\mathbb{R}_{>0}$ (resp., $\mathbb{R}_{<0}$) is the set of all possible (resp., negative) real numbers. Construct an infinite sequence $f$ by

$$ f(j) = \begin{cases} \exp(\pi_i(j)) & \text{if } j \in \bar{B}_i \text{ and part } B_i \text{ is enriched with a permutation,} \\ -\exp(j) & \text{if } j \in \bar{B}_i \text{ and part } B_i \text{ is enriched with the symbol } D. \end{cases} $$

By construction, the infinite sequence $f$ is $d$-periodic. Furthermore, we claim that $f$ is 312-avoiding. Assume not, that is, there are three integers $x < y < z$ such that $f(y) < f(z) < f(x)$. If $f(y) < 0$ then so is $f(z)$. But the negative values of $f$ form a decreasing sequence, since this is a subsequence of $-\exp(j)$. This contradicts $f(y) < f(z)$. Now assume that $f(y) > 0$. Since $f(x) > f(y)$, $x$ has to belong to the same interval $B_i + j \cdot d$ as $y$. Similarly, since $f(x) > f(z)$, $z$ has to belong to the same interval $B_i + j \cdot d$ as $x$. This contradicts to the fact that the block $B_i$ was enriched with a 312-avoiding permutation.

Finally, we construct an infinite walk $(\dots, \sigma_{-1}, \sigma_0, \sigma_1, \sigma_2, \dots)$ in the graph $G(n, 312)$ by letting $\sigma_i$ be the standardization $\Pi(f(i), f(i+1), \dots, f(i+n))$. Note that this permutation is 312-avoiding
and as an edge in the graph it has the tail $\Pi(f(i), f(i+1), \dots, f(i+n-1))$ and the head $\Pi(f(i+1), f(i+2), \dots, f(i+n))$. Since $f$ is $d$-periodic the infinite walk has period $d$. Restricting the walk to $(\sigma_1, \sigma_2, \dots, \sigma_d)$ gives a closed walk in the set $Q_d$. This completes the description of the map $\Phi$.

One can always lift an infinite walk in the graph to an infinite sequence. However, as Remark 6.1 shows, an infinite walk could lift to several non-equivalent sequences, and they do not all have the desired properties. Thus, when lifting a walk to a sequence we have the additional requirements in Conditions (7.1) and (7.2). Their interpretation is that we do not introduce an inversion in the infinite sequence, unless we are required to do so by a local condition.

**Remark 6.1** Consider the two infinite sequences

$$h_1(n) = n + (-1)^n \quad \text{and} \quad h_2(n) = n + 2(-1)^n.$$

Observe that they both encode the same 2-cycle in $G(2, 312)$. That is,

$$\Pi(h_1(n), h_1(n+1), h_1(n+2)) = \Pi(h_2(n), h_2(n+1), h_2(n+2)) = \begin{cases} 132 & \text{if } n \text{ is odd,} \\ 213 & \text{if } n \text{ is even.} \end{cases}$$

However, note that $h_2$ is not 312-avoiding, whereas $h_1$ is. Furthermore, $h_2$ does not have any cut-points, whereas $h_1$ does. Hence, when constructing the inverse map to $\Phi$ we have to be careful in constructing an infinite sequence which is 312-avoiding. This is the reason for the appearance of the two conditions (7.1) and (7.2) in the next section.

# 7 The inverse bijection

We now construct the inverse map of $\Phi$. Given the closed walk $(\sigma_1, \sigma_2, \dots, \sigma_d)$ in $Q_d$ we extend it to an infinite walk by letting $\sigma_{j+d} = \sigma_j$ for all integers $j$.

We are going to find a sequence $\dots, g(-1), g(0), g(1), g(2), \dots$ such that $\Pi(g(i), g(i+1), \dots, g(i+n)) = \sigma_i$ for all integers $i$. To find such a sequence, let $g(k) = \sigma_1(k)$ for $1 \le k \le n+1$. Now alternate the following two steps to extend $g$ to all of the integers.

(+) Assume that we have picked the values $g(i), g(i+1), \dots, g(j-1)$ of the sequence. We will now pick the value of $g(j)$. That is, we are extending the sequence in the positive direction. Let $\sigma$ be the permutation $\sigma_{i-n}$. Let $a$ and $b$ be the real numbers (including $\pm\infty$) given by

$$\begin{align*} a &= \begin{cases} g(\sigma^{-1}(\sigma(n+1) - 1) + s) & \text{if } \sigma(n+1) > 1, \\ -\infty & \text{if } \sigma(n+1) = 1, \end{cases} \\ b &= \begin{cases} g(\sigma^{-1}(\sigma(n+1) + 1) + s) & \text{if } \sigma(n+1) < n+1, \\ \infty & \text{if } \sigma(n+1) = n+1, \end{cases} \end{align*}$$

where $s$ is the shift $s = j - n - 1$. Then any real number $x$ in the open interval $(a, b)$ satisfies $\Pi(g(j-n), \dots, g(j-1), x) = \sigma$. However, we have one more requirement, we will pick $x$ as large as possible with respect to the already picked values $g(i), g(i+1), \dots, g(j-n-1)$. That is, we pick $g(j) = x$ such that

$$\max(a, \{g(k) : g(k) < b, i \le k \le j-1\}) < x < b. \qquad (7.1)$$
(–) Now we extend the sequence in the negative direction. Assume that we have picked the values $g(i+1), g(i+2), \dots, g(j)$ of the sequence. We will now pick the value of $g(i)$. Let $\sigma$ now denote the permutation $\sigma_i$. Let the two bounds $a$ and $b$ be given by

$$ 
\begin{aligned}
a &= \begin{cases} g(\sigma^{-1}(\sigma(1) - 1) + s) & \text{if } \sigma(1) > 1, \\ -\infty & \text{if } \sigma(1) = 1, \end{cases} \\ 
b &= \begin{cases} g(\sigma^{-1}(\sigma(1) + 1) + s) & \text{if } \sigma(1) < n + 1, \\ \infty & \text{if } \sigma(1) = n + 1, \end{cases}
\end{aligned}
$$

where $s = i - 1$. Yet again, any real number $x$ in the open interval $(a, b)$ satisfies $\Pi(x, g(i+1), \dots, g(i+n)) = \sigma$. However, now we pick $x$ as small as possible with the already picked values $g(i+1), \dots, g(j)$. That is, we pick $g(i) = x$ such that

$$ a < x < \min(b, \{g(k) : g(k) > a, i+1 \le k \le j\}) \quad (7.2) $$

The purpose of the two conditions (7.1) and (7.2) is to avoid introducing any extra inversions in the sequence $g$. These conditions will come into play at the end of this construction in the case when the set $D$ (to be defined soon) is empty.

**Claim 7.1** The sequence $g$ is locally 312-avoiding, that is, if $i < j < k$, where $k - i \le n$ then $\Pi(g(i), g(j), g(k)) \ne 312$.

This holds true since $\sigma_i$ is 312-avoiding.

**Claim 7.2** For all $i$ we have $g(i) \ne g(i+d)$.

Since $d \le n$ and $\Pi(g(i), g(i+1), \dots, g(i+d), \dots, g(i+n))$ is a permutation, $g(i)$ and $g(i+d)$ are distinct.

**Claim 7.3** For $i < j$ and $j - i < n$ the inequality $g(i) < g(j)$ is equivalent to $g(i+d) < g(j+d)$.

Since $\sigma_i = \sigma_{i+d}$ we have the string of the equivalences $g(i) < g(j) \iff \sigma_i(1) < \sigma_i(j - i + 1) \iff \sigma_{i+d}(1) < \sigma_{i+d}(j - i + 1) \iff g(i+d) < g(j+d)$.

Hence, the infinite sequence $g$ decomposes into $d$ sequences, each of which is monotone. We now partition the integers $\mathbb{Z}$ into two sets $D = \{i : g(i) > g(i+d)\}$ and $U = \{i : g(i) < g(i+d)\}$. Note that since $d \le n$ we have that $i \in D$ is equivalent to $i+d \in D$. That is, $D$ consists of the sequences that are decreasing and $U$ of the increasing sequences.

**Claim 7.4** The subsequence $\{g(i)\}_{i \in D}$ is decreasing.

Assume that it is not decreasing. Then there are two entries $i, j \in D$ such that $i < j, j - i \le d - 1$ and $g(i) < g(j)$. Also, we have that $g(j - d) > g(j)$. Combining the last two inequalities we have that $\Pi(g(j - d), g(i), g(j)) = 312$, contradicting that the sequence is not decreasing.

**Claim 7.5** The values of the sequence $\{g(i)\}_{i \in D}$ are all smaller than the values of $\{g(j)\}_{j \in U}$.
We begin when $i$ and $j$ are close to each other, that is, when $i < j < i+d$, $i \in D$ and $j \in U$. Assume that $g(i) > g(j)$. Then we have the string of inequalities $g(i-d) > g(i) > g(j) > g(j-d)$ implying that $\Pi(g(i-d), g(j-d), g(i)) = 312$, a contradiction. Hence, we conclude that $g(i) < g(j)$. Now pick $i' \in D$ and $j' \in U$. If $i' < j'$ let $i = i'$ and $j = j' - d \cdot \lfloor(j'-i')/d\rfloor$. If $i' > j'$ let $i = i' - d \cdot \lceil(i'-j')/d\rceil$ and $j = j'$. (Here $\lfloor \cdot \rfloor$ and $\lceil \cdot \rceil$ are the usual floor and ceiling functions.) In both cases we have $i \in D$, $j \in U$ and $i < j < i+d$. Furthermore, we have that $g(i') \le g(i) < g(j) \le g(j')$, proving the claim.

Now assume that $D$ is non-empty. The case when $D$ is empty requires an extra argument, which we postpone to the end of this section. Pick $p_1$ to be an element in the set $D$. Decompose the interval $[p_1, p_1 + d - 1]$ of cardinality $d$ into smaller intervals, according to the rules:

(d) If $i \in D \cap [p_1, p_1 + d - 1]$ then let the singleton $\{i\} = [i, i]$ be an interval in the decomposition. Moreover, enrich this singleton with the symbol $D$.

(u) If $i \le j$, $i - 1, j + 1 \in D$ and $[i, j] \subseteq U \cap [p_1, p_1 + d - 1]$ then we use the argument at the end of Section 3 to decompose the interval $[i, j]$ into smaller intervals, each enriched with an indecomposable 312-avoiding permutation. That is, we use the permutation $\Pi(g(i), g(i+1), \dots, g(j))$ to decompose the interval.

Let the decomposition of the interval $[p_1, p_1 + d - 1]$ be $\{[p_1, q_1], [p_2, q_2], \dots, [p_\ell, q_\ell]\}$, where $q_i + 1 = p_{i+1}$. Extend this decomposition to a decomposition $\{[p_i, q_i]\}_{i \in \mathbb{Z}}$ of the integers $\mathbb{Z}$ by letting $p_{i+\ell} = p_i+d$ and $q_{i+\ell} = q_i+d$. Note that under the quotient map $\mathbb{Z} \to \mathbb{Z}_d$ we obtain a cyclic composition.

**Claim 7.6** If the intervals $[p_i, q_i]$ and $[p_k, q_k]$ are not enriched with the symbol $D$, $i < k$, $x \in [p_i, q_i]$ and $z \in [p_k, q_k]$ then we have $g(x) < g(z)$.

First assume that $z - x \le d$. If there is no interval $[p_j, q_j]$ between these two intervals ($i < j < k$) which is enriched with the symbol $D$ then the inequality follows by the decomposition into indecomposable permutations in part (u) above. If there is an interval $[p_j, q_j]$ in between which is enriched with the symbol $D$, then consider the pattern $\Pi(g(x), g(p_j), g(z))$. Since $[p_j, q_j]$ is enriched by $D$ we have that $g(p_j) < g(x)$ and $g(p_j) < g(z)$. Hence, if $g(x) > g(z)$, we obtain the pattern 312, a contradiction. Finally, if $z - x > d$, we obtain the inequality by using that $U$ consists of the increasing sequences.

The last claim states that we do not lose information if we view the permutation enriching the interval $[p_i, q_i]$ as a bijection on this interval. The resulting composition, viewed as a cyclic composition with its enrichment, is the inverse image of the map $\Phi$.

When the set $D$ is empty, we need to be more careful to show that the sequence $g$ has a cut-point. We will use an argument similar to that in the second proof of Corollary 4.3. However, there is an added complication since all we know is that $g$ is locally 312-avoiding. By condition (7.1) we have the following lemma.

**Lemma 7.7** Assume that $j < k$ and $g(j) > g(k)$. Then there is a chain $j = j_0 < j_1 < \dots < j_\ell = k$ such that $g(j_0) > g(j_1) > \dots > g(j_\ell)$ and $j_{h+1} - j_h \le n$ for all indices $h$.

**Proof:** When we selected the value of $g(j_\ell)$, we picked this value in an interval $(a, b)$ where $b$ was one of the values from the list $g(j_\ell - n), \dots, g(j_\ell - 2), g(j_\ell - 1)$. Hence, let $j_{\ell-1}$ be the index such that $g(j_{\ell-1}) = b$.

Assume that $g(j) < g(j_{\ell-1})$. Condition (7.1) states that we picked $g(j_\ell)$ as large as possible in the interval $(a, b)$. Hence, the assumption $g(j) < g(j_{\ell-1})$ implies that $g(j) < g(j_\ell)$, a contradiction. We conclude that $g(j) > g(j_{\ell-1})$. By iterating this argument we obtain the chain. $\square$
Let $P$ be the poset $\{(i, g(i)) : i \in \mathbb{Z}\}$ with the order defined by $(x, y) \le_P (z, w)$ if $x \ge z$ and $y \le w$. Let $(i, g(i))$ be a minimal element in this poset and let $(j, g(j))$ be an element larger than or equal to the minimal element $(i, g(i))$ maximizing the second coordinate. Observe that $i - j \le d$. The local 312-avoidance condition implies that the poset order between $(i, g(i))$ and $(j, g(j))$ is a chain. That is, we have the string of inequalities $g(j) > g(j+1) > \cdots > g(i-1) > g(i)$.

The remaining case is to show that there is no index $k$ such that $i < k$ and $g(i) < g(k) < g(j)$. First pick $j'$ in the interval $[j, i-1]$ such that $g(j'+1) < g(k) < g(j')$. Next use Lemma 7.7 to pick the first element of the chain $j_1'$ such that $j' < j_1' \le j' + n$ and $g(j'+1) < g(j_1') < g(j')$. However, this is a 312-pattern, contradicting the assumption that there is such a $k$. Hence, we conclude that the sequence $g$ has a cut-point.

Let the cut-point be $p_1 - 1$. Consider the composition of the interval $[p_1, p_1 + d - 1]$ consisting of one part. That is, this part is the interval $[p_1, p_1 + d - 1]$. Now, in a way similar to part (u) above, we decompose this interval into smaller intervals, each enriched with an indecomposable 312-avoiding permutations using the permutation $\Pi(g(p_1), g(p_1+1), \ldots, g(p_1+d-1))$. This completes the inverse of $\Phi$ in the case when the set $D$ is empty.

## References

[1] T. VAN AARDENNE-EHRENFEST AND N. G. DE BRUIJN, Circuits and trees in oriented linear graphs, *Simon Stevin*, **28** (1951), 203–217.

[2] S. AVGUSTINOVICH AND S. KITAEV, On uniquely $k$-determined permutations, *Discrete Math.*, **308** (2008), 1500–1507.

[3] A. BJÖRNER AND F. BRENTI, Affine Permutations of Type A, *Electron. J. Combin.*, **3** (1996), R18.

[4] F. R. K. CHUNG, P. DIACONIS AND R. GRAHAM, Universal cycles for combinatorial structures, *Discrete Math.*, **110** (1992), 43–59.

[5] A. CLAESSON AND S. KITAEV, Classification of bijections between 321- and 132-avoiding permutations, *Sém. Lothar. Combin.*, **60** (2008/09), Art. B60d, 30pp.

[6] A. CRITES, Enumerating pattern avoidance for affine permutations, *Elec. J. Comb.*, **17** (2010), R127.

[7] R. EHRENBORG, S. KITAEV AND P. PERRY, A spectral approach to consecutive pattern-avoiding permutations, *J. Comb.*, **2** (2011), 305–353.

[8] R. EHRENBORG, S. KITAEV AND E. STEINGRÍMSSON, Number of cycles in the graph of 312-avoiding permutations, *arXiv:1310.1520*.

[9] R. EHRENBORG AND M. READDY, Juggling and applications to $q$-analogues, *Discrete Math.*, **157** (1996), 107–125.

[10] C. FLYE SAINT-MARIE, Solution to question 48, *l'Intermédiare des Mathématiciens*, **1** (1894), 107–110.

[11] S. KITAEV, “Patterns in Permutations and Words,” Monographs in TCS, Springer, Heidelberg, 2011.

[12] OEIS Foundation Inc. (2011), The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[13] Y. PURI AND T. WARD, A dynamical property unique to the Lucas sequence, *Fibonacci Quart.*, **39** (2001), 398–402.

[14] Y. PURI AND T. WARD, Arithmetic and growth of periodic orbits, *J. Integer Seques.*, **4** (2001), #01.2.1.

[15] R. P. STANLEY, Catalan addendum, http://www-math.mit.edu/~rstan/ec/.