$\newcommand{\Av}{\operatorname{Av}}$ $\newcommand{\oc}{\Av(3124,4312)}$ $\newcommand{\pa}[1]{\left({#1}\right)}$

Enumeration of Av(3124,4312)

Permutation Patterns 2013

Jay Pantone

University of Florida


[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.]

2x4 Classes

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.

Simple Permutations

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.

examples of intervals

Inflations of Permutations

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$.
inflation example

Inflations of Permutations

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

examples of sums and skew sums

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.

A Decomposition Lemma

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.

Types of Permutations

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.
inflation example
The skew decomposable permutations (inflations of the permutation 21). For uniqueness, the first component must be skew indecomposable.
inflation example
Inflations of the simple permutations in the class which have length at least 4.
inflation example
The single permutation of length 1.
inflation example

Generating Functions

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)$.



Sum Decomposable Permutations

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$.

Sum Decomposable Permutations

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.\]

Skew Decomposable Permutations

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}.\]

Geometric Grid Classes

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.


Examples:
examples of geometric grid classes

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.


Geometric Grid Classes

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 have rational generating functions.


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

Geometric Grid Classes

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.

examples of geometric grid classes

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$.

examples of geometric grid classes

Geometric Grid Classes

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:

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

Relevance of Geometric Grid Classes

Consider the following three geometric grid classes.

our three 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)$.

Counting Simple Permutations

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$.

Regular Language 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$.

Regular Language for $\mathcal{G}_2$


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\}^*$.

Regular Language for $\mathcal{G}_2$

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\]

Regular Language for $\mathcal{G}_2$

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\}^*$.

Regular Language for $\mathcal{G}_2$

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$.

Allowed Inflations of $\mathcal{G}_2$

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).\]

Allowed Inflations of $\mathcal{G}_2$

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.

Allowed Inflations of $\mathcal{G}_2$

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).\]

Allowed Inflations of $\mathcal{G}_2$

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).\]

Counting Permutations

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.\]

Final Calculation

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*}$

A Few Remarks

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.

Thanks!