[Wait 15 seconds for the page to load completely,

or the math will be messed up.]

[Navigate slides using the left and right arrow keys.]

A *permutation class* is a set of permutations which is closed downward under the pattern containment relation.

A *2x4* class is a class which avoids exactly two permutations of length 4.

Up to the symmetries of a permutation, there are 56 different 2x4 classes which have been shown to have 38 different enumerations. This result (the enumeration of the $\oc$) brings the number of known enumerations to 27.

See Wikipedia for a summary of known enumerations.

An *interval* of a permutation is a consecutive group of indices whose entries are also consecutive.

We say that a permutation is *simple* if it contains no *intervals* other than those of length 1 or $n$.

The permutation on the left is not simple because it has an interval of length 4. The permutation on the right is simple.

The *inflation* of a permutation $\pi$ of length $n$ by a sequence of nonempty permutations $\tau_1, \ldots, \tau_n$ takes the entry $\pi(i)$ and turns it into set of entries $\tau_i$.

For example, $3142\left[231,21,123,1\right] = 564\;21\;789\;3$.

A *sum* $\sigma \oplus \tau$ is the inflation $12[\sigma,\tau]$ and a *skew sum* $\sigma \ominus \tau$ is the inflation $21[\sigma,\tau]$.

A permutation $\pi$ is *sum decomposable* if it can be written as $\pi = \sigma \oplus \tau$ for some nonempty permutations $\sigma$ and $\tau$. Otherwise, it is *sum indecomposable*.

A permutation $\pi$ is *skew decomposable* if it can be written as $\pi = \sigma \ominus \tau$ for some nonempty permutations $\sigma$ and $\tau$. Otherwise, it is *skew indecomposable*.

**Lemma: **(Albert and Atkinson) For every permutation $\pi$ there is a unique simple permutation $\sigma \leq \pi$ such that $\pi$ is an inflation of $\sigma$. The permutations by which the entries of $\pi$ are inflated are also uniquely determined, unless $\sigma = 12$ or $\sigma=21$. In this case, we just require that the first component is indecomposable.

There are basically 4 types of permutations in a class.

The sum decomposable permutations (inflations of the permutation 12). For uniqueness, the first component must be sum indecomposable.

The skew decomposable permutations (inflations of the permutation 21). For uniqueness, the first component must be skew indecomposable.

Inflations of the simple permutations in the class which have length at least 4.

The single permutation of length 1.

Let $f$ be the generating function for $\oc$. From the previous slide, we know that

$f = $ $x$ $+$ $\text{[sum dec.]}$ $+$ $\text{[skew dec.]}$ $+$ $\text{[other inflations].}$

Let

\[m := \frac{x}{1-x} = x + x^2 + x^3 + x^4 + \cdots\]

be the generating function for the nonempty increasing (or, decreasing) permutations.

Let

\[c := \frac{1-2x-\sqrt{1-4x}}{2x} = x + 2x^2 + 5x^3 + 14x^4 + \cdots\]

be the generating function for the nonempty permutations in $\operatorname{Av}(312)$.

Let $\pi = \sigma \oplus \tau \in \oc$. To assure uniqueness of decomposition, we require that $\sigma$ is sum indecomposable.

Since $\tau$ has at least one entry, we must have that $\sigma \in \Av_{\not{\oplus}}(312)$. $\tau$ can be any permutation in $\oc$.

Therefore, the sum decomposable permutations in $\oc$ are equal to \[\Av_{\not{\oplus}}(312) \oplus \oc.\]

Since $\Av_{\not{\oplus}}(312)$ is enumerated by the shifted Catalan numbers, we see that the sum decomposable permutations are counted by \[(xc+x)f.\]

Let $\pi = \sigma \ominus \tau \in \oc$. To assure uniqueness of decomposition, we require that $\sigma$ is skew indecomposable.

If $\sigma$ is increasing, then we can have $\tau \in \Av(312)$. If $\sigma$ has a descent, then $\tau$ must be decreasing. Therefore, the skew decomposable permutations are \[\left(\Av(21) \ominus \Av(312)\right) \cup \left(\Av_{\not{\ominus}}\left(3124,4312\right) \ominus \Av(12)\right).\]

Therefore \[f_{\ominus} = mc + (f-f_{\ominus})m - m^2\] and so \[f_{\ominus} = \frac{m(c+f-m)}{1+m}.\]

A geometric grid class is the set of permutations which can be drawn on an array of:

- increasing line segments with slope 1,

- decreasing line segments with slope -1,

- single points.

On the left, the permutation 827546319 is an element of the class of permutations which can be drawn on an X.

On the right, the permutation 578219364 is an element of the class of permutations which can be drawn on a diamond.

A class is said to be *geometrically griddable* if it's a subclass of a geometric grid class.

**Theorem: **(Albert, Atkinson, Bouvel, Ruškuc, and Vatter) Every geometrically griddable class has a finite basis, is partially well ordered (has no infinite antichains), and ** has a rational generating function**. Additionally, the simple, sum indecomposable, and skew indecomposable permutations in every geometrically griddable class each

In particular, given a geometrically griddable class $\mathcal{C}$, we can construct a regular language which is in (length-preserving) bijection with $\mathcal{C}$.

For each line segment, we pick a direction. (We have to be slightly careful in how we pick these.) Then, we pick one letter to represent each nonempty cell and let $\Sigma$ be the alphabet of letters.

To go from a word to a permutation, we take each letter (from left to right) and place it along the corresponding arrow, increasing the distance between the entry and the base point of the arrow each time. This is a surjective map $\Phi : \Sigma^* \to \mathcal{C}$, but *not* a bijection. For example, $\Phi(bacddb) = 234165$.

To get a bijection, we find a regular language $\mathcal{L}\subseteq\Sigma^*$ such that $\Phi\big|_{\mathcal{L}}$ is a bijection. There are two obstacles to overcome:

- Pairs of letters may "commute", so that we can move the entries around in their own cells and still have the same permutation.
- We may be able to move entries to different cells and get the same permutation.

Consider the following three geometric grid classes.

**Proposition: **$\mathcal{G}_1 \cap \mathcal{G}_2 = \mathcal{G}_3$

**Theorem: **$\operatorname{Simples}\left(\mathcal{G}_1 \cup \mathcal{G}_2\right) = \operatorname{Simples}\left(\operatorname{Av}\left(3124,4312\right)\right)$.

**Theorem: **$\operatorname{Simples}\left(\mathcal{G}_1 \cup \mathcal{G}_2\right) = \operatorname{Simples}\left(\operatorname{Av}\left(3124,4312\right)\right)$.

Therefore, we can enumerate the simple permutations in $\operatorname{Av}\left(3124,4312\right)$ by counting the simple permutations in these geometric grid classes. We do this by finding the regular languages which are in bijection with the simple permutations in each class.

Then, we determine how a simple permutation in each class can be inflated to yield permutations still in $\operatorname{Av}\left(3124,4312\right)$.

In this talk, we'll go through this process only for $\mathcal{G}_2$.

Recall $\mathcal{G}_2 = \;$, so that $\Sigma = \{a,b,c,d,e,f\}$.

Every cell in $\{a,e,f\}$ commutes with every cell in $\{b,c,d\}$. Additionally, $a$ commutes with $f$ and $b$ commutes with $d$.

Hence, to prevent duplicate permutations due to commuting cells, we forbid all words which contain any $\{b,c,d\}$ before any $\{a,e,f\}$. Furthermore, we forbid any words which contain the patterns $fa$ or $db$.

If we can get the same permutation from two words by moving some entry from one cell to another, then we choose to prefer the word which has entries in cells as far to the left as possible, and then entries in cells as far down as possible.

For example, if a word begins with an $e$, then this entry could be moved into cell $c$, which is a preferred configuration. Therefore, we forbid all words which begin with an $e$.

If a $d$ has no $c$ before it, and the word has no $f$, then the $d$ can be moved to cell $b$. Thus, we forbid all words of the form $\{a,b,d,e\}^*d\{a,b,c,d,e\}^*$.

There are 7 such rules that restrict the set of all words $\Sigma^*$ to a regular language $\mathcal{L}_2$ which is in (length-preserving) bijection with the permutation class $\mathcal{G}_2$.

Using GAP, we can calculate that the generating function for $\mathcal{G}_2$ is \[\frac{{x-7x^2+19x^3-22x^4+9x^5-x^6}}{{\left(1-x\right)} {\left(1-2x\right)} {\left(1-3x+x^2\right)}^{2}}\]

\[= x + 2x^2 + 6x^3 + 21x^4 + 73x^5 + 244x^6 + 786x^7 + \cdots\]

Next, we restrict the language further so that we're left with only simple permutations.

To eliminate any intervals which occur within a cell, we forbid all words which contain any of the patterns $aa$, $bb$, $cc$, $dd$, $ee$, or $ff$.

There are five intervals involving multiple cells that can occur. For example, to avoid the interval shown here, we forbid words of the form $\{a,b,c,e,f\}^*f\{a,b,c\}^*$.

When we add all five rules, we're left with a regular language which is in (length-preserving) bijection with $\operatorname{Simples}\left(\mathcal{G}_2\right)$. It has multivariate generating function:

\[\frac{{x_{d} x_{f}(1 + x_{c})} {( x_{a} x_{e} + x_{c} x_{d} + x_{b} x_{c} x_{d} - x_{a} x_{b} x_{c} x_{e} - x_{a} x_{c} x_{d} x_{e}- x_{a} x_{b} x_{c} x_{d} x_{e})} }{{(1 - x_{b} x_{c} - x_{c} x_{d} - x_{b} x_{c} x_{d})} {(1 - x_{a}x_{e} - x_{e} x_{f} - x_{a} x_{e} x_{f} )}}\]

and univariate generating function:

\[M_2(x) := \frac{{x^4(1-x)} {(2+x)} }{{(1-x-x^2)}^{2}} = 2 x^{4} + 3 x^{5} + 7 x^{6} + 13 x^{7} + 25 x^{8} + 46 x^{9} + \cdots\]

Interestingly, this sequence is given by

\[\left[x^n\right]M_2(x) = F_{n-3} + \sum_{i=1}^{n-3} F_iF_{n-i-2}\]

where $F_i$ is the $i^\text{th}$ Fibonacci number, with $F_1=F_2=1$.

Given a simple permutation in $\mathcal{G}_2$, how can we inflate each entry to yield a permutation still in $\operatorname{Av}\left(3124,4312\right)$?

For example, if an entry in cell $d$ is inflated by $21$, then to avoid a $4312$ pattern, any entry in cell $e$ can only be inflated by decreasing permutations.

Not all entries in a cell can be inflated by the same permutations. For $\mathcal{G}_2$, we must split $c$ into $c_1$ and $c_2$ and split $d$ into $d_1$ and $d_2$ (we omit the rules here) and get the new generating function \[S_2\left(x_a, x_b, x_{c_1}, x_{c_2}, x_{d_1}, x_{d_2}, x_e, x_f\right).\]

Entries in cell $a$ can be inflated by any permutation which avoids $312$.

Entries in cell $b$ can be inflated by any permutation which avoids $312$.

The $c_1$ entries in cell $c$ can be inflated by decreasing permutations only, while any $c_2$ entry in cell $c$ can be inflated by permutations which avoid $312$.

The $d_1$ entries in cell $d$ can be inflated by increasing permutations only. The $d_2$ entries in cell $d$ will be handled separately in cases.

The entries in cell $e$ can be inflated by decreasing permutations only.

If there is no $d_2$, or there is a $d_2$ which is inflated only by an increasing permutation, then entries in cell $f$ can be inflated by permutations which avoid $312$.

If there is a $d_2$ which is inflated by a permutation in $\oc$ which contains a descent, then any entries in cell $f$ can only be inflated by decreasing permutations.

The generating function for the permutations that contain a $d_2$ is \[S_{2,[\text{has $d_2$}]} := S_2 - S_2\left(d_2=0\right).\]

The generating function for the permutations in $\operatorname{Av}(3124,4312)$ which are inflations of simple permutations of length at least 4 is hence given by

\[I_2 := S_2(c,c,m,c,m,m,m,c)\]
\[\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; + \;\; S_{2,{[\text{has $d_2$}]}}(c,c,m,c,m,f-m,m,m).\]

The work we just did computed the enumeration of the permutations in $\operatorname{Av}(3124,4312)$ which are inflations of simple permutations in $\mathcal{G}_2$, denoted $I_2$.

Similarly, we can find the enumerations for the permutations which are inflations of simple permutations in $\mathcal{G}_1$ and $\mathcal{G}_3$, denoted $I_1$ and $I_3$, respectively.

Since $\mathcal{G}_1 \cap \mathcal{G}_2 = \mathcal{G}_3$, the set of all permutations in $\operatorname{Av}(3124,4312)$ which are inflations of any simple permutation of length at least 4 is enumerated by \[I_1 + I_2 - I_3.\]

So, the generating function $f$ of $\oc$ satisfies

\[f = x + (xc+x)f + \frac{m(f+c-m)}{1+m} + \left(I_1 + I_2 - I_3\right).\]

Using SAGE, we find that

$\begin{align*}
f(x) &= \frac{\pa{8x^5 - 16x^4 + 28x^3 - 26x^2 + 9x -1} + \sqrt{1-4x}\pa{2x^4-8x^3+14x^2-7x+1}}{2x^2(1-6x+9x^2-4x^3)}\\[6pt]
&= x + 2x^2 + 6x^3 + 22x^4 + 88x^5 + 363x^6 + 1507x^7 + 6241x^8 + 25721x^9 + \cdots.
\end{align*}$

We don't have an algorithm to determine when the simple permutations of a class are geometrically griddable. However, of the remaining 11 2x4 classes which have not been enumerated, none of them seem to fit this criterion.

We have investigated a few ways to do parts of this algorithmically, but so far we are limited by computational power.