# On a conjecture of Lin and Kim concerning a refinement of Schröder numbers

Toufik Mansour  Department of Mathematics, University of Haifa, 3498838 Haifa,
Israel<EMAIL_ADDRESS>and  Mark Shattuck  Department of
Mathematics, University of Tennessee, 37996 Knoxville, TN
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we compute the distribution of the first letter statistic on
nine avoidance classes of permutations corresponding to two pairs of patterns
of length four. In particular, we show that the distribution is the same for
each class and is given by the entries of a new Schröder number triangle. This
answers in the affirmative a recent conjecture of Lin and Kim. We employ a
variety of techniques to prove our results, including generating trees, direct
bijections and the kernel method. For the latter, we make use of in a creative
way what we are trying to show in three cases to aid in solving a system of
functional equations satisfied by the associated generating functions.

###### Key words and phrases:

pattern avoidance, combinatorial statistic, kernel method

###### 2010 Mathematics Subject Classification:

05A15, 05A05

##  1\. Introduction

Given two permutations $\pi=\pi_{1}\cdots\pi_{n}\in\mathcal{S}_{n}$ and
$\tau=\tau_{1}\cdots\tau_{k}\in\mathcal{S}_{k}$, we say that $\pi$ _contains_
the pattern $\tau$ if there exist indices $i_{1}<i_{2}<\cdots<i_{k}$ such that
$\pi_{i_{1}}\cdots\pi_{i_{k}}$ is order isomorphic to $\tau$, that is,
$\pi_{i_{a}}>\pi_{i_{b}}$ if and only if $\tau_{a}>\tau_{b}$. Otherwise, $\pi$
is said to _avoid_ the pattern $\tau$. Moreover, we say that $\pi$ avoids a
set $L$ of patterns if it avoids each pattern in $L$, and let
$\mathcal{S}_{n}(L)$ denote the subset of $\mathcal{S}_{n}$ whose members
avoid $L$. In recent decades, the study of pattern avoidance in permutations
has been the object of considerable attention (see, e.g., [5] and references
contained therein).

An _inversion_ within a permutation
$\sigma=\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}_{n}$ is an ordered pair
$(a,b)$ such that $1\leq a<b\leq n$ and $\sigma_{a}>\sigma_{b}$. The inversion
sequence of $\sigma$ is given by $a_{1}\cdots a_{n}$, where $a_{i}$ records
the number of entries of $\sigma$ to the right of $i$ and less than $i$ for
each $i\in[n]$. The systematic study of patterns in inversion sequences was
initiated only recently in [2, 8].

The (large) Schröder number $S_{n}$ (see [12, A006318]) is defined recursively
by

$nS_{n}=3(2n-3)S_{n-1}-(n-3)S_{n-2},\qquad n\geq 3,$

with $S_{1}=1$ and $S_{2}=2$, and arises as the enumerator of several
avoidance classes of permutations corresponding to a pair of patterns of
length four. In particular, combining the results from [3, 6, 13], one has the
$S_{n}$ enumerates $\mathcal{S}_{n}(\sigma,\tau)$ for the following ten
inequivalent pairs $(\sigma,\tau)$:

$\displaystyle\text{I.}\leavevmode\nobreak\ (1234,2134)$
$\displaystyle\text{II.}\leavevmode\nobreak\ (1324,2314)$
$\displaystyle\text{III.}\leavevmode\nobreak\ (1342,2341)$
$\displaystyle\text{IV.}\leavevmode\nobreak\ (3124,3214)$
$\displaystyle\text{V.}\leavevmode\nobreak\ (3142,3214)\leavevmode\nobreak\ $
$\displaystyle\text{VI.}\leavevmode\nobreak\ (3412,3421)$
$\displaystyle\text{VII.}\leavevmode\nobreak\ (1324,2134)$
$\displaystyle\text{VIII.}\leavevmode\nobreak\ (3124,2314)$
$\displaystyle\text{IX.}\leavevmode\nobreak\ (2134,3124)$
$\displaystyle\text{X.}\leavevmode\nobreak\ (2413,3142).$

This answered in the affirmative a conjecture originally posed by Stanley (see
[6] for details). Moreover, outside of symmetry, there are no other such pairs
$(\sigma,\tau)$ for which $|\mathcal{S}_{n}(\sigma,\tau)|=S_{n}$. In this
paper, we obtain a refinement of this result in several cases by considering
distributions of certain statistics on the various classes. For other
refinements of the Schröder numbers, see, e.g., [1, 9, 10, 11].

$n\backslash k$ | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
1 | 1 |  |  |  |  |
2 | 1 | 1 |  |  |  |
3 | 2 | 2 | 2 |  |  |
4 | 4 | 6 | 6 | 6 |  |
5 | 8 | 16 | 22 | 22 | 22 |
6 | 16 | 40 | 68 | 90 | 90 | 90
Table 1. The new Schröder triangle $S_{n,k}$ for $1\leq k\leq n\leq 6$.

In a recent paper, Lin and Kim [7] introduced a new triangle $S_{n,k}$ for
Schröder numbers in their study of inversion sequences; see Table 1 above.
Here, we find it here more convenient for what follows to start from $k=1$
instead of $k=0$, as was done in [7]. Note that $S_{n,k}$ is given recursively
by

$S_{n,k}=S_{n,k-1}+2S_{n-1,k}-S_{n-1,k-1},\qquad 1\leq k\leq n-2,$

with $S_{n,n}=S_{n,n-1}=S_{n,n-2}$ for $n\geq 3$ and
$S_{1,1}=S_{2,1}=S_{2,2}=1$. Lin and Kim showed that $S_{n,k}$ enumerates the
inversion sequences $\pi_{1}\cdots\pi_{n}\in\\{I_{n}(021)\mid\pi_{n}=k\mod
n\\}$. Then they state the following conjecture which provides a connection
between inversion sequences and pattern avoidance in permutations.

######  Conjecture 1.

(Lin and Kim [7].) Let $(\nu,\mu)$ be a pair of patterns of length four. Then

$S_{n,k}=|\\{\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}_{n}(\nu,\mu)\mid\sigma_{n}=k\\}|$

for all $1\leq k\leq n$ if and only if $(\nu,\mu)$ is one of the following
nine pairs:

$\displaystyle(4321,3421),\,(3241,2341),\,(2431,2341),\,(4231,3241),\,(4231,2431),$
$\displaystyle(4231,3421),\,(2431,3241),\,(3421,2431),\,(3421,3241).$

Given $1\leq i\leq n$, let $\mathcal{S}_{n,i}(\sigma,\tau)$ denote the set of
permutations of length $n$ avoiding $\sigma$ and $\tau$ and starting with $i$.
Note that one may consider equivalently the distribution of the first letter
statistic on the set of permutations avoiding the reversal of the two patterns
in question in each case. Here, we confirm the conjecture by showing that
$|\mathcal{S}_{n,i}(\sigma,\tau)|=S_{n,i}$ for each of the nine pairs above
(where the patterns in each pair are reversed). It is seen that these nine
cases are derived from only six of the ten symmetry classes (I)-(X) above. It
should be remarked that the reversal, complement and inverse operations do not
respect the first letter statistic and thus members of the same symmetry class
do not have the same first letter distribution in general. Moreover, these are
the only nine pairs such that $|\mathcal{S}_{n,i}(\sigma,\tau)|=S_{n,i}$ for
all $i$; see Table 2 at the end of the introduction which rules out all other
possible pairs $(\sigma,\tau)$ for which
$|\mathcal{S}_{n}(\sigma,\tau)|=S_{n}$. Furthermore, we have also computed the
joint distribution with the descents statistic in six cases which confirms an
additional conjecture of Lin and Kim [7].

In several cases, we will make use of a generating function approach to
establish the result. Note that by the kernel method [4], one can show

(1) $\sum_{n\geq
1}\left(\sum_{k=1}^{n}S_{n,k}y^{k}\right)x^{n}=\frac{xy(2-3x-3y+3xy)+xy(x+y-xy)(xy+\sqrt{1-6xy+x^{2}y^{2}})}{2(1-2x-y+xy)},$

which reduces when $y=1$ to the well-known formula Schröder number generating
function given by

(2) $\sum_{n\geq 1}S_{n}x^{n}=\frac{1-x-\sqrt{1-6x+x^{2}}}{2}.$

$\sigma,\tau$ | $\\{|\\{\pi\in S_{8}(\sigma,\tau)\mid\pi_{1}=k\\}|\\}_{k=1}^{8}$ | $\sigma,\tau$ | $\\{|\\{\pi\in S_{8}(\sigma,\tau)\mid\pi_{1}=k\\}|\\}_{k=1}^{8}$
---|---|---|---
2413,4123 | 1584,1036,996,956,879,751,533,233 | 3142,4123 | 1584,1584,1252,912,637,443,323,233
3142,3214 | 1584,1584,736,396,292,304,488,1584 | 2341,2413 | 1584,488,304,292,396,736,1584,1584
2341,3142 | 1584,811,587,489,481,577,855,1584 | 2413,3214 | 1584,855,577,481,489,587,811,1584
2431,3421 | 1806,1022,710,614,644,795,1161,1806 | 2431,4231 | 1806,1092,1008,1045,1120,1134,924,429
2314,3124 | 1806,1092,752,629,629,752,1092,1806 | 2314,3214 | 1806,1092,752,629,629,752,1092,1806
2341,3241 | 1806,1092,752,629,629,752,1092,1806 | 2413,3142 | 1806,1092,752,629,629,752,1092,1806
2431,3241 | 1806,1092,752,629,629,752,1092,1806 | 2134,3124 | 1806,1161,795,644,614,710,1022,1806
3241,3421 | 1806,1806,1198,678,406,342,516,1806 | 3214,3241 | 1806,1806,1220,672,390,342,516,1806
3124,4123 | 1806,1806,1502,1152,840,594,429,429 | 3214,4213 | 1806,1806,1502,1152,840,594,429,429
3241,4231 | 1806,1806,1502,1152,840,594,429,429 | 3412,4312 | 1806,1806,1502,1152,840,594,429,429
3421,4231 | 1806,1806,1502,1152,840,594,429,429 | 3421,4321 | 1806,1806,1502,1152,840,594,429,429
4123,4132 | 1806,1806,1806,1412,928,512,224,64 | 4123,4213 | 1806,1806,1806,1412,928,512,224,64
4132,4213 | 1806,1806,1806,1412,928,512,224,64 | 4132,4231 | 1806,1806,1806,1412,928,512,224,64
4132,4312 | 1806,1806,1806,1412,928,512,224,64 | 4213,4231 | 1806,1806,1806,1412,928,512,224,64
4213,4312 | 1806,1806,1806,1412,928,512,224,64 | 4231,4312 | 1806,1806,1806,1412,928,512,224,64
4312,4321 | 1806,1806,1806,1412,928,512,224,64 | 3124,3214 | 1806,1806,788,540,484,540,788,1806
3412,3421 | 1806,1806,788,540,484,540,788,1806 | 2314,2341 | 1806,516,342,390,672,1220,1806,1806
2134,2314 | 1806,516,342,406,678,1198,1806,1806 | 2134,2143 | 1806,788,540,484,540,788,1806,1806
2341,2431 | 1806,788,540,484,540,788,1806,1806 | 1432,2413 | 233,323,443,637,912,1252,1584,1584
1432,3142 | 233,533,751,879,956,996,1036,1584 | 1234,2134 | 429,429,594,840,1152,1502,1806,1806
1243,2143 | 429,429,594,840,1152,1502,1806,1806 | 1324,2134 | 429,429,594,840,1152,1502,1806,1806
1324,2314 | 429,429,594,840,1152,1502,1806,1806 | 1342,2341 | 429,429,594,840,1152,1502,1806,1806
1432,2431 | 429,429,594,840,1152,1502,1806,1806 | 1324,3124 | 429,924,1134,1120,1045,1008,1092,1806
1423,4123 | 429,924,1344,1582,1582,1344,924,429 | 1432,4132 | 429,924,1344,1582,1582,1344,924,429
1234,1243 | 64,224,512,928,1412,1806,1806,1806 | 1243,1324 | 64,224,512,928,1412,1806,1806,1806
1243,1342 | 64,224,512,928,1412,1806,1806,1806 | 1243,1423 | 64,224,512,928,1412,1806,1806,1806
1324,1342 | 64,224,512,928,1412,1806,1806,1806 | 1324,1423 | 64,224,512,928,1412,1806,1806,1806
1342,1423 | 64,224,512,928,1412,1806,1806,1806 | 1342,1432 | 64,224,512,928,1412,1806,1806,1806
1423,1432 | 64,224,512,928,1412,1806,1806,1806 |  |
Table 2. All symmetries of classes I-X according to first letter statistic.
Note the 9 boldface cases corresponding to the conjecture and the 9 italicized
cases obtained by complementation.

This paper is organized as follows. In the next section, we show six cases of
the conjecture above using various methods such as induction, bijections and
generating trees. In the third section, we prove the remaining three cases,
each of which involves $1243$ and another pattern, by considering the joint
distribution of the first and second letter statistics. This allows one to
write a system of recurrence relations in each case which may then be
expressed in terms of some auxiliary generating functions leading to a system
of functional equations. At this point, one can use the conjecture itself in
these particular cases along with the kernel method to ascertain a potential
solution to the aforementioned system, which may then be shown to be the
actual solution. Taking the variable that marks the second letter statistic to
be unity then recovers formula (1) and demonstrates the desired equality of
distributions.

In several instances, the distribution of the first letter statistic on the
pattern pair in question follows as a special case of a more general
distribution. For one’s reference, listed below are the places within the
paper where the specific cases are shown.

Pattern Pair | Reference | Pattern Pair | Reference | Pattern Pair | Reference
---|---|---|---|---|---
1234,1243 |  Theorem 2 | 1243,1324 |  Corollary 20 | 1243,1342 |  Corollary 15
1243,1423 |  Corollary 10 | 1324,1342 |  Theorem 2 | 1324,1423 |  Theorem 6
1342,1423 |  Theorem 6 | 1342,1432 |  Theorem 3 | 1423,1432 |  Theorem 2
Table 3. Places where specific cases of Conjecture 1 are proven.

##  2\. Pattern avoidance and the new Schröder triangle

In this section, we enumerate members of $\mathcal{S}_{n,i}(\sigma,\tau)$
confirming the conjecture in six of the cases, the first three of which we
treat together in the following result.

######  Theorem 2.

If $n\geq 1$ and $1\leq i\leq n$, then
$|\mathcal{S}_{n,i}(\sigma,\tau)|=S_{n,i}$ for $(\sigma,\tau)=(1234,1243)$,
$(1324,1342)$ and $(1423,1432)$.

###### Proof.

We prove the case when $(\sigma,\tau)=(1234,1243)$, the others being similar.
Let $\mathcal{A}_{n,i}=\mathcal{S}_{n,i}(1234,1243)$ and we first write a
recurrence for $a_{n,i}=|\mathcal{A}_{n,i}|$. Note that members of
$\mathcal{A}_{n,i}$ where $1\leq i\leq n-3$ must have second letter
$\ell\in[i-1]$ or $\ell=n-1,n$, for otherwise there would be an occurrence of
$1234$ or $1243$ starting with $i\ell$. Furthermore, the first letter $i$ is
seen to be extraneous concerning the avoidance of $1234$ or $1243$ if
$\ell\in[i-1]$ and thus may be deleted. Similarly, $\ell$ may deleted in cases
when $\ell=n-1$ or $n$. This implies the recurrence

$a_{n,i}=2a_{n-1,i}+\sum_{\ell=1}^{i-1}a_{n-1,\ell},\qquad 1\leq i\leq n-2,$

with $a_{n,n}=a_{n,n-1}=\sum_{i=1}^{n-1}a_{n-1,i}$ for $n\geq 3$.

Before proceeding further, note that

$\displaystyle S_{n,n-2}$
$\displaystyle=\sum_{k=1}^{n-2}(S_{n,k}-S_{n,k-1})=\sum_{k=1}^{n-2}(2S_{n-1,k}-S_{n-1,k-1})=2S_{n-1,n-2}+\sum_{k=1}^{n-3}S_{n-1,k}$
$\displaystyle=\sum_{k=1}^{n-1}S_{n-1,k}.$

Thus, the $a_{n,i}$ and $S_{n,i}$ are both given by the sum of the entries of
the previous row if $i\in[n-2,n]$, with the two arrays also agreeing for
$n=1,2$. Therefore, to complete the proof, it suffices to show

(3) $S_{n,i}=2S_{n-1,i}+\sum_{\ell=1}^{i-1}S_{n-1,\ell},\qquad 1\leq i\leq
n-2.$

To do so, we proceed by induction on $n$ and $i$, the $i=1$ case clearly
holding since $S_{n,1}=2S_{n-1,1}$ for all $n\geq 3$. So assume $n\geq 4$ and
$2\leq i\leq n-2$. Note further that (3) also holds when $i=n-1$ for $n\geq
3$, which follows from the work above. Then by the induction hypothesis, we
have

$\displaystyle S_{n,i}$
$\displaystyle=S_{n,i-1}+2S_{n-1,i}-S_{n-1,i-1}=2S_{n-1,i-1}+\sum_{\ell=1}^{i-2}S_{n-1,\ell}+4S_{n-2,i}+2\sum_{\ell=1}^{i-1}S_{n-2,\ell}$
$\displaystyle\quad-2S_{n-2,i-1}-\sum_{\ell=1}^{i-2}S_{n-2,\ell}$ (4)
$\displaystyle=2S_{n-1,i-1}+4S_{n-2,i}+\sum_{\ell=1}^{i-2}(S_{n-1,\ell}+S_{n-2,\ell}).$

Upon substituting (3) into (4), and simplifying the resulting equality, to
complete the induction, we must show

(5) $2S_{n-1,i}=S_{n-1,i-1}+4S_{n-2,i}+\sum_{\ell=1}^{i-2}S_{n-2,\ell}.$

Substituting $S_{n-1,i}=2S_{n-2,i}+\sum_{\ell=1}^{i-1}S_{n-2,\ell}$ into (5)
reduces it to

$2\sum_{\ell=1}^{i-1}S_{n-2,\ell}=S_{n-1,i-1}+\sum_{\ell=1}^{i-2}S_{n-2,\ell},$

i.e.,

$S_{n-1,i-1}=2S_{n-2,i-1}+\sum_{\ell=1}^{i-2}S_{n-2,\ell},$

which is true by the induction hypothesis. This establishes (3) and completes
the proof in the case of $(\sigma,\tau)=(1234,1243)$. Since the associated
$a_{n,i}$ can be shown to satisfy the same recurrence and initial conditions
for the other two pattern pairs, one obtains the same result in these cases as
well. ∎

To establish the case $(1342,1432)$, we define a bijection with a previous
case.

######  Theorem 3.

The members of $\mathcal{S}_{n,i}(1342,1432)$ having a prescribed set of left-
right minima in specified positions are in one-to-one correspondence with
members of $\mathcal{S}_{n,i}(1234,1243)$ having the same set of left-right
minima in the same positions. In particular,
$|\mathcal{S}_{n,i}(1342,1432)|=S_{n,i}$.

###### Proof.

We define a bijection $f$ between $\mathcal{S}_{n,i}(1342,1432)$ and
$\mathcal{S}_{n,i}(1234,1243)$ with the desired properties as follows. Let
$\pi=\pi_{1}\cdots\pi_{n}\in\mathcal{S}_{n,i}(1342,1432)$ have left-right
minima values $a_{r}>a_{r-1}>\cdots>a_{1}$, where $a_{r}=\pi_{1}$ and
$a_{1}=1$. Note that since the patterns in both pairs start with $1$, one may
always assume a left-right minima plays the role of the $1$. Suppose
$\pi=\alpha 1\beta$, where $\alpha$ or $\beta$ is possibly empty. Then let
$\pi_{1}$ be obtained by reversing the order of all letters in $\beta$ within
$\pi_{0}=\pi$, that is, $\pi_{1}=\alpha 1\beta^{\prime}$, where
$\beta^{\prime}$ denotes the reversal of $\beta$. Note that $\pi_{1}$ contains
no $1234$ or $1243$ starting with the actual element $1$ since all such
occurrences of $1234$ or $1243$ within $\pi_{0}$ have been replaced with
comparable occurrences of $1432$ or $1342$, respectively.

If $r=1$ (i.e., if $\pi$ starts with $1$), then we let $f(\pi)=\pi_{1}$ and we
are done, so assume $r\geq 2$. In this case, let $S$ denote the subsequence
comprising all elements of $[a_{2}+1,n]$ occurring to the right of $a_{2}$ in
the permutation $\pi_{1}$. Let $S^{*}$ denote the portion of $S$ to the right
of $a_{1}$ within $\pi_{1}$. We then let $\pi_{2}$ be the permutation obtained
from $\pi_{1}$ as follows. First remove all letters of $\pi_{1}$ corresponding
to $S$ and replace them with blanks. Within these blanks, from left to right,
we then write the elements of $S^{*}$ followed by the reversal of $S-S^{*}$ to
obtain $\pi_{2}$. That is, the elements between $a_{2}$ and $a_{1}$ in
$\pi_{1}$ that belong to $[a_{2}+1,n]$ have their relative order reversed when
they are written within the blanks and now follow (instead of precede) the
remaining elements of $S$. Observe that $\pi_{2}$ has no occurrences of $1234$
or $1243$ starting with $a_{2}$ as the relative order of all elements
belonging to $[a_{2}+1,n]$ to the right of $a_{2}$ in $\pi_{2}$ is the reverse
of the order of these same elements in $\pi$. To see this, note that only the
elements in $S-S^{*}$ have their order reversed in going from $\pi_{1}$ to
$\pi_{2}$ as the order of $S^{*}$ in $\pi_{1}$ is already the reversal of what
it was in $\pi$. Further, no occurrence of $1234$ or $1243$ starting with
$a_{1}$ can arise during the transition from $\pi_{1}$ to $\pi_{2}$ since the
positions of elements in $[2,a_{2}-1]$ do not change during this transition.

If $r=2$, then let $f(\pi)=\pi_{2}$. Otherwise, consider moving the letters
that belong to $[a_{3}+1,n]$ and lie to the right of $a_{3}$ within $\pi_{2}$
in a comparable manner as before, reversing the order of only those elements
occurring between $a_{3}$ and $a_{2}$. Continue on for subsequently larger $i$
where in the $r$-th step, one moves letters in $[a_{r}+1,n]$ in obtaining
$\pi_{r}$ from $\pi_{r-1}$. Let $f(\pi)=\pi_{r}$. Note that $\pi_{r}$ indeed
belongs of $\mathcal{S}_{n}(1234,1243)$ since as one may verify no occurrence
of $1234$ or $1243$ starting with $a_{j}$ for some $j<i$ can arise during the
$i$-th transition from $\pi_{i-1}$ to $\pi_{i}$ for any $i\in[r]$. Since each
step of the algorithm described above is seen to preserve both the positions
and values of left-right minima, then so does the mapping $f$ (in particular,
the first letter statistic is preserved by $f$). This implies that the inverse
of $f$ may be found by reversing each of the $r$ steps of the algorithm
starting with the last step and proceeding in reverse order. ∎

We next treat the cases $(1324,1423)$ and $(1342,1423)$ together using a
generating tree approach (see, e.g., [14]). Consider forming
$\pi\in\mathcal{S}_{n}(1324,1423)$ (or $\mathcal{S}_{n}(1342,1423)$) by
inserting the element $1$ within a member
$\rho\in\mathcal{S}_{n-1}(1324,1423)$ ($\mathcal{S}_{n-1}(1342,1423)$,
respectively), expressed using the letters in $[2,n]$. By an _active site_
within $\pi=\pi_{1}\cdots\pi_{n-1}$, we mean a position in which $1$ may be
inserted without introducing an occurrence of either $1324$ or $1423$ (and
likewise for $(1342,1423)$). Given either pair $(\sigma,\tau)$ of patterns
under consideration, let $u_{n}(i,j)$ denote the number of members of
$\mathcal{S}_{n,i}(\sigma,\tau)$ having exactly $j$ active sites. Note that
$u_{n}(i,j)$ for $n\geq 2$ can assume non-zero values only when $1\leq i\leq
n$ and $3\leq j\leq n+1$.

The $u_{n}(i,j)$ are given recursively as follows.

######  Lemma 4.

If $3\leq j\leq n$, then

(6) $u_{n}(i,j)=u_{n-1}(i-1,j-1)+\sum_{\ell=j-1}^{n}u_{n-1}(i-1,\ell),\qquad
2\leq i\leq n,$

with $u_{n}(1,j)=0$. If $j=n+1$, then we have

(7) $u_{n}(i,n+1)=u_{n-1}(i-1,n),\qquad i\geq 2,$

with $u_{n}(1,n+1)=2^{n-2}$ for $n\geq 2$ and $u_{1}(1,2)=1$.

###### Proof.

We treat the case $(1324,1423)$, with the same recurrences seen to hold for
$(1342,1423)$ by a comparable analysis. Let $\mathcal{U}_{n,i,j}$ denote the
subset of $\mathcal{S}_{n,i}(1324,1423)$ enumerated by $u_{n}(i,j)$. Note that
the (active) sites of $\pi\in\mathcal{U}_{n,i,j}$ correspond to the rightmost
$j$ possible positions of $\pi$ in which to insert a $1$ if $j\leq n$. For if
the $j$-th letter $x$ from the right within $\pi$ where $j\leq n$ starts
either a $213$ or $312$ and is the rightmost such letter to do so, then all
positions to the right of $x$ are sites. From this observation, we may
conclude that $\mathcal{U}_{n,1,j}$ is empty if $3\leq j\leq n$, upon
considering separately the cases $j=n$ or $j<n$. On the other hand, since $1$
starts both of the patterns that are being avoided, we have that
$\mathcal{U}_{n,1,n+1}$ is synonymous with $\mathcal{S}_{n-1}(213,312)$, which
has cardinality $2^{n-2}$ if $n\geq 2$. This establishes the initial
conditions when $i=1$, so assume henceforth that $i\geq 2$.

Let $\pi$ be formed from a precursor $\alpha\in\mathcal{U}_{n-1,a,b}$ for some
$a$ and $b$, expressed using $[2,n]$, by inserting $1$ as described. Let $(k)$
denote a precursor having $k$ sites. Then we have the succession rule
$(k)\rightarrow(3)(4)\cdots(k+1)(k+1)$ with root $(2)$, which follows from the
argument used in the proof of [6, Prop. 11] or can be reasoned directly in
this case. Note that no offspring of $\alpha$ if $b<n$ can arise by inserting
$1$ in the first position, for otherwise a $1324$ or $1423$ would be
introduced, whereas if $b=n$, an offspring so produced would have $n+1$ sites.
Since any offspring $\pi\in\mathcal{U}_{n,i,j}$ with $i\geq 2$ must have
precursor starting with $i-1$ and at least $j-1$ sites, recurrence (6)
follows. On the other hand, an offspring $\pi\in\mathcal{U}_{n,i,n+1}$ where
$i\geq 2$ can only come about by inserting $1$ in the final position within
its precursor $\rho\in\mathcal{U}_{n-1,i-1,n}$, for the other offspring of
$\rho$ having $n+1$ sites comes about by inserting $1$ in the first position.
This implies (7) and completes the proof. ∎

Given $n\geq 2$, let $v_{n}(i;q)=\sum_{j=3}^{n+1}u_{n}(i,j)q^{j-2}$ for $1\leq
i\leq n$, with $v_{1}(1;q)=1$. Define the joint distribution polynomial
$v_{n}(y,q)=\sum_{i=1}^{n}v_{n}(i;q)y^{i}$ for $n\geq 2$, with $v_{1}(y,q)=y$.

Then the $v_{n}(y,q)$ are given recursively as follows.

######  Lemma 5.

If $n\geq 3$, then

(8)
$v_{n}(y,q)=\frac{(1-y)(2^{n-1}y-y^{n})q^{n-1}}{2-y}+\frac{yq(v_{n-1}(y,1)+(1-2q)v_{n-1}(y,q))}{1-q},\qquad
n\geq 2,$

with $v_{1}(y,q)=y$.

###### Proof.

Note that (8) is seen to hold if $n=2$ since $v_{2}(y,q)=yq(1+y)$, so assume
$n\geq 3$. Multiplying both sides of (6) by $q^{j-2}$, summing over $3\leq
j\leq n$ and adding $q^{n-1}$ times (7) gives

$\displaystyle v_{n}(i;q)$
$\displaystyle=u_{n-1}(i-1,n)q^{n-1}+\sum_{j=3}^{n}u_{n-1}(i-1,j-1)q^{j-2}+\sum_{j=3}^{n}q^{j-2}\sum_{\ell=j-1}^{n}u_{n-1}(i-1,\ell)$
$\displaystyle=q\sum_{j=3}^{n}u_{n-1}(i-1,j)q^{j-2}+\sum_{\ell=2}^{n}u_{n-1}(i-1,\ell)\sum_{j=3}^{\ell+1}q^{j-2}-u_{n-1}(i-1,n)q^{n-1}$
$\displaystyle=qv_{n-1}(i-1;q)+\sum_{\ell=2}^{n}u_{n-1}(i-1,\ell)\frac{q-q^{\ell}}{1-q}-u_{n-1}(i-1,n)q^{n-1}$
$\displaystyle=qv_{n-1}(i-1;q)+\frac{q}{1-q}(v_{n-1}(i-1;1)-qv_{n-1}(i-1;q))-u_{n-1}(i-1,n)q^{n-1},$

for $2\leq i\leq n$, with $v_{n}(1;q)=2^{n-2}q^{n-1}$. Multiplying the last
recurrence by $y^{i}$, and summing over $i$, yields

$\displaystyle v_{n}(y,q)$
$\displaystyle=yqv_{n-1}(y,q)+\frac{yq(v_{n-1}(y,1)-qv_{n-1}(y,q))}{1-q}+2^{n-2}yq^{n-1}-q^{n-1}\sum_{i=2}^{n}u_{n-1}(i-1,n)y^{i}$
$\displaystyle=\frac{yq(v_{n-1}(y,1)+(1-2q)v_{n-1}(y,q))}{1-q}+2^{n-2}yq^{n-1}-q^{n-1}\left(y^{n}+\sum_{i=2}^{n-1}2^{n-i-1}y^{i}\right),$

where we have used the fact

$\displaystyle u_{m}(j,m+1)$
$\displaystyle=|\mathcal{S}_{m,j}(213,312)|=\begin{cases}2^{m-j-1},&\text{if
}1\leq j<m;\\\\[3.0pt] 1,&\text{if }j=m,\end{cases}$

which follows from elementary considerations. Simplifying and combining the
inhomogeneous terms in the last recurrence formula now gives (8). ∎

Note that (8) holds for both $(1324,1423)$ and $(1342,1423)$ since Lemma 4
applies to either pair. Let $f(x,y;q)=\sum_{n\geq 1}v_{n}(y,q)x^{n}$.

######  Theorem 6.

The generating function for the joint distribution of the first letter and
number of active sites statistics on $\mathcal{S}_{n}(1324,1423)$ and
$\mathcal{S}_{n}(1342,1423)$ is given by

(9)
$f(x,y;q)=\frac{xy(1-q)(1-xq)(1-2xyq)}{(1-2xq)(1-xyq)(1-(xy+1)q+2xyq^{2})}+\frac{xyq}{1-(xy+1)q+2xyq^{2}}A(x,y),$

where

$A(x,y)=\frac{xy(2-3x-3y+3xy)+xy(x+y-xy)(xy+\sqrt{1-6xy+x^{2}y^{2}})}{2(1-2x-y+xy)}.$

###### Proof.

Multiplying both sides of (8) by $x^{n}$, and summing over $n\geq 2$, yields

$\displaystyle f(x,y;q)-xy$
$\displaystyle=\frac{y(1-y)}{2-y}\cdot\frac{2x^{2}q}{1-2xq}-\frac{1-y}{2-y}\cdot\frac{x^{2}y^{2}q}{1-xyq}+\frac{xyq}{1-q}f(x,y;1)$
$\displaystyle\quad+\frac{xyq(1-2q)}{1-q}f(x,y;q),$

which may be rewritten as

(10)
$\displaystyle\left(1-\frac{xyq(1-2q)}{1-q}\right)f(x,y;q)=xy+\frac{x^{2}yq(1-y)}{(1-2xq)(1-xyq)}+\frac{xyq}{1-q}f(x,y;1).$

To solve (10), we apply the kernel method [4] and let

$q=q_{0}=\frac{1+xy-\sqrt{1-6xy+x^{2}y^{2}}}{4xy}.$

This gives

$\displaystyle f(x,y;1)$
$\displaystyle=\frac{q_{0}-1}{q_{0}}+\frac{x(1-y)(q_{0}-1)}{1-2xq_{0}-xyq_{0}+2x^{2}yq_{0}^{2}}=\frac{q_{0}-1}{q_{0}}+\frac{x(1-y)(q_{0}-1)}{1-x+x(xy-y-1)q_{0}},$

where we have used the fact $2xyq_{0}^{2}=(1+xy)q_{0}-1$. Substituting
$\frac{1}{q_{0}}=\frac{1+xy+\sqrt{1-6xy+x^{2}y^{2}}}{2}$ into

$f(x,y;1)=\left(1-\frac{1}{q_{0}}\right)\left(1+\frac{x(1-y)}{\frac{1-x}{q_{0}}+x(xy-y-1)}\right),$

and simplifying, leads to the formula $f(x,y;1)=A(x,y)$. Substituting this
back into (10) yields (9). ∎

##  3\. The remaining cases

In this section, we consider the remaining cases $(1243,1423)$, $(1243,1342)$
and $(1423,1324)$. We adopt a common approach for these three cases and
consider the joint distribution of the first and second letter statistics. For
the given pattern pair $(\sigma,\tau)$ under current consideration, let
$a_{n}(i,j)$ denote the number of members of $\mathcal{S}_{n,i}(\sigma,\tau)$
whose second letter is $j$. Let $a_{n}(i)=\sum_{j\neq i}a_{n}(i,j)$ and
$a_{n}=\sum_{i=1}^{n}a_{n,i}$. Note that $a_{n}=S_{n}$, the $n$-th Schröder
number (see, e.g., [6]). Clearly, we have

(11) $a_{n}(i,j)=a_{n-1}(j),\quad 1\leq j<i,$

for all pairs of patterns under consideration. If $i<j$ where $i\leq n-3$,
then in order to write a recurrence for $a_{n}(i,j)$ in this case, we consider
the position of the second ascent and further subcases based on the size of
the difference $j-i$. If $n\leq 3$, then all three pattern pairs have initial
values given by $a_{1}(1)=a_{2}(1,2)=a_{2}(2,1)=a_{3}(i,j)=1$ where
$i,j\in[3]$ with $i\neq j$.

###  3.1. The case $(1243,1423)$.

In this subsection, we enumerate the members of $\mathcal{S}_{n}(1243,1423)$
according to the joint distribution of the first and second letter statistics.

We first prove the following recurrence for $a_{n}(i,j)$ when $i<j$.

######  Lemma 7.

We have

(12)
$a_{n}(i,i+1)=a_{n-1}(i,i+1)+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\sum_{b=a+1}^{i-c}\binom{i-a-1}{c}a_{n-c-2}(a,b),\qquad
1\leq i\leq n-2,$

with $a_{n}(n-1,n)=a_{n-2}$,

$\displaystyle a_{n}(i,i+2)$ $\displaystyle=a_{n-1}(i,i+1)+a_{n-1}(i,i+2)$
(13)
$\displaystyle\quad+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\sum_{b=a+1}^{i-c+1}\binom{i-a-1}{c}a_{n-c-2}(a,b),\qquad
1\leq i\leq n-3,$

with $a_{n}(n-2,n)=a_{n-2}$, and

$\displaystyle a_{n}(i,j)$
$\displaystyle=a_{n-1}(i,j-1)+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-2)$
(14)
$\displaystyle\quad+(1-\delta_{j,n})\cdot\left(a_{n-1}(i,j)+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1)\right)$

for $4\leq i+3\leq j\leq n$.

###### Proof.

Let $k$ denote the third letter of a member of $\mathcal{A}_{n,i,j}$. We will
consider various cases based on $k$ in the proofs of (12)-(14). To show (12),
first observe that for members of $\mathcal{A}_{n,i,i+1}$ where $i\leq n-2$,
one has either $k=i+2$ or $k<i$, for $k>i+2$ would ensure an occurrence of
$1243$ which isn’t permissible. In the first case, the third letter is
superfluous concerning avoidance of either pattern and thus may be deleted
leading to $a_{n-1}(i,i+1)$ possibilities. On the other hand, in the latter
case, we have that $\pi\in\mathcal{A}_{n,i,i+1}$ can be decomposed as
$\pi=i(i+1)x_{1}\cdots x_{c}ad\rho$, where $a\in[i-1]$,
$x_{1},\ldots,x_{c}\in[a+1,i-1]$ with $x_{1}>\cdots>x_{c}$, $d>a$ and $\rho$
denotes the terminal section of $\pi$. Note that $d=i+2$ or
$d\in[a+1,i-1]-\\{x_{1},\ldots,x_{c}\\}$ since $d>i+2$ is again not allowed.
Further, the letters $x_{1},\ldots,x_{c},i,i+1$ may be removed from $\pi$ in
light of the ascent $a,d$, leading to a member
$\pi^{\prime}\in\mathcal{A}_{n-c-2,a,b}$ for some $b$ after reduction of
letters. Note that within $\pi^{\prime}$, the $b$ parameter value can range
over $[a+1,i-c]$ since the largest possible value it may assume is
$i+2-(c+2)=i-c$. As there are $\binom{i-a-1}{c}$ ways in which to choose the
$x_{i}$, considering all possible $a$, $c$ and $b$ implies that the number of
$\pi\in\mathcal{A}_{n,i,i+1}$ for which $k<i$ is given by
$\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\sum_{b=a+1}^{i-c}\binom{i-a-1}{c}a_{n-c-2}(a,b)$,
which establishes (12).

A similar argument applies to (13) except that now we have $k<i$ or
$k=i+1,i+3$ for members of $\mathcal{A}_{n,i,i+2}$ where $i\leq n-3$. Note
that $k=i+3$ leads to $a_{n-1}(i,i+2)$ possibilities, as $k$ may be deleted in
this case. If $k<i$, then making use of the previous notation, we have
$d\in[a+1,i-1]\cup\\{i+1,i+3\\}$ and thus $b$ may range in $[a+1,i-c+1]$ in
this case. Finally, to show (14), we consider first the case when $j<n$ within
a member of $\mathcal{A}_{n,i,j}$ where $j\geq i+3$. Here, we would have
$k\in[i-1]\cup\\{j-1,j+1\\}$, as $k\in[i+1,j-2]$ would lead to an occurrence
of 1423 as witnessed by $ijk(k+1)$. If $k=j-1$ or $k=j+1$, then $k$ may be
deleted in either case giving $a_{n-1}(i,j-1)$ and $a_{n-1}(i,j)$
possibilities, respectively. If $k<i$, then we must have $d=j-1$ or $d=j+1$,
for other values of $d$ would lead to an occurrence of $1243$ or $1423$.
Considering all possible $a$ and $c$ then yields the two double sum
expressions occurring in the $j<n$ case of (14). Combining this with the
preceding then implies (14) when $j<n$. On the other hand, if $j=n$, then
$k=j+1$ or $d=j+1$ does not occur in the preceding argument, which implies
(14) in this case and completes the proof. ∎

We will make use of the following generating functions:

$\displaystyle A(x,v,w)$ $\displaystyle=\sum_{n\geq
2}\sum_{a=1}^{n}\sum_{b=1}^{n}a_{n}(a,b)v^{a}w^{b}x^{n},$ $\displaystyle
A^{+}(x,v,w)$ $\displaystyle=\sum_{n\geq
2}\sum_{a=1}^{n-1}\sum_{b=a+1}^{n}a_{n}(a,b)v^{a}w^{b}x^{n},$ $\displaystyle
A^{-}(x,v,w)$ $\displaystyle=\sum_{n\geq
2}\sum_{a=2}^{n}\sum_{b=1}^{a-1}a_{n}(a,b)v^{a}w^{b}x^{n},$ $\displaystyle
C(x,v)$ $\displaystyle=\sum_{n\geq 2}\sum_{a=1}^{n-1}a_{n}(a,a+1)v^{a}x^{n},$
$\displaystyle D(x,v)$ $\displaystyle=\sum_{n\geq
2}\sum_{a=1}^{n-2}a_{n}(a,a+2)v^{a}x^{n},$ $\displaystyle B(x,v,w)$
$\displaystyle=\sum_{n\geq
4}\sum_{a=1}^{n-3}\sum_{b=a+3}^{n}a_{n}(a,b)v^{a}w^{b}x^{n}.$

Clearly, $A^{+}(x,v,w)=wC(x,vw)+w^{2}D(x,vw)+B(x,v,w)$, by the definitions.

Translating (11)-(14) in terms of generating functions yields

$\displaystyle A^{-}(x,v,w)$ $\displaystyle=\sum_{n\geq
2}\sum_{a=2}^{n}\sum_{b=1}^{a-1}a_{n-1}(b)v^{a}w^{b}x^{n}$
$\displaystyle=\sum_{n\geq
2}\sum_{b=1}^{n-1}a_{n-1}(b)\frac{v^{b+1}-v^{n+1}}{1-v}w^{b}x^{n}$
$\displaystyle=v^{2}wx^{2}+\frac{vx}{1-v}A(x,vw,1)-\frac{v^{2}x}{1-v}A(vx,w,1),$
$\displaystyle wC(x,vw)-vw^{2}x^{2}A(vwx,1,1)-vw^{2}x^{2}-v^{2}w^{3}x^{3}$
$\displaystyle=wxC(x,vw)+\sum_{n\geq
2}\sum_{i=1}^{n-2}\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\sum_{b=a+1}^{i-c}\binom{i-a-1}{c}a_{n-c-2}(a,b)v^{i}w^{i+1}x^{n}$
$\displaystyle=wxC(x,vw)+w\sum_{a\geq 1}\sum_{c\geq 0}\sum_{i\geq
1}\sum_{n\geq
i+c+a+2}\sum_{b=a+1}^{i+a}\binom{i+c-1}{c}a_{n-c-2}(a,b)(vw)^{i+a+c}x^{n}$
$\displaystyle=wxC(x,vw)+w\sum_{a\geq 1}\sum_{i\geq 1}\sum_{n\geq
a+i}\sum_{b=a+1}^{i+a}a_{n}(a,b)\frac{(vw)^{i+a}x^{n+2}}{(1-vwx)^{i}}$
$\displaystyle=wxC(x,vw)$ $\displaystyle+\frac{w}{vwx+vw-1}\sum_{n\geq
2}\sum_{a=1}^{n-1}\sum_{b=a+1}^{n}a_{n}(a,b)(\frac{x^{n+2}(vw)^{n+1}}{(1-vwx)^{n-a}}-\frac{x^{n+2}(vw)^{b}}{(1-vwx)^{b-a-1}})$
$\displaystyle=wxC(x,vw)$
$\displaystyle+\frac{vw^{2}x^{2}}{vwx+vw-1}A^{+}(\frac{vwx}{1-vwx},1-vwx,1)-\frac{(1-vwx)wx^{2}}{vwx+vw-1}A^{+}(x,1-vwx,\frac{vw}{1-vwx}),$
$\displaystyle w^{2}D(x,vw)-w^{2}x^{2}A(vwx,1,1)+v^{2}w^{4}x^{4}$
$\displaystyle=w^{2}x(C(x,vw)-vwx^{2}A(vwx,1,1))+w^{2}xD(x,vw)$
$\displaystyle+w^{2}\sum_{n\geq
3}\sum_{i=1}^{n-3}\sum_{a=1}^{i-1}\sum_{c=0}^{i-1-a}\sum_{b=a+1}^{i-c+1}\binom{i-1-a}{c}a_{n-2-c}(a,b)(vw)^{i}x^{n}$
$\displaystyle=w^{2}x(C(x,vw)-vwx^{2}A(vwx,1,1))+w^{2}xD(x,vw)$
$\displaystyle+w^{2}\sum_{a\geq 1}\sum_{c\geq 0}\sum_{i\geq 1}\sum_{n\geq
i+a+3}\sum_{b=a+1}^{i+a+1}\binom{i+c-1}{c}a_{n-2}(a,b)(vw)^{i+a+c}x^{n+c}$
$\displaystyle=w^{2}x(C(x,vw)-vwx^{2}A(vwx,1,1))+w^{2}xD(x,vw)$
$\displaystyle+w^{2}x^{2}\sum_{a\geq 1}\sum_{n\geq
a+2}\sum_{b=a+2}^{n}a_{n}(a,b)\frac{(vw)^{i+a}x^{n}}{(1-vwx)^{i}}+w^{2}x^{2}\sum_{a\geq
1}\sum_{n\geq
a+2}\sum_{i=1}^{n-a-1}a_{n}(a,a+1)\frac{(vw)^{i+a}x^{n}}{(1-vwx)^{i}}$
$\displaystyle=w^{2}x(C(x,vw)-vwx^{2}A(vwx,1,1))+w^{2}xD(x,vw)$
$\displaystyle+\frac{w^{2}x^{2}(1-vwx)}{vwx+vw-1}A^{+}(\frac{vwx}{1-vwx},1-vwx,1)-\frac{wx^{2}(1-vwx)^{2}}{v(vwx+vw-1)}A^{+}(x,1-vwx,\frac{vw}{1-vwx})$
$\displaystyle-w^{2}x^{2}C(x,vw),$

and

$\displaystyle B(x,v,w)$ $\displaystyle=wxB(x,v,w)+w^{3}xD(x,vw)$
$\displaystyle+\sum_{n\geq
3}\sum_{i=1}^{n-3}\sum_{j=i+3}^{n}\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-2)v^{i}w^{j}x^{n}$
$\displaystyle+\sum_{n\geq
3}\sum_{i=1}^{n-3}\sum_{j=i+3}^{n}\biggl{(}(1-\delta_{j,n})(a_{n-1}(i,j)v^{i}w^{j}x^{n}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1)v^{i}w^{j}x^{n}\biggr{)}$
$\displaystyle=wxB(x,v,w)+w^{3}xD(x,vw)$ $\displaystyle+\sum_{n\geq
3}\sum_{i=1}^{n-3}\sum_{j=i+3}^{n}\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-2)v^{i}w^{j}x^{n}$
$\displaystyle+\sum_{n\geq
3}\sum_{i=1}^{n-3}\sum_{j=i+3}^{n-1}\left(a_{n-1}(i,j)v^{i}w^{j}x^{n}+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1)v^{i}w^{j}x^{n}\right)$
$\displaystyle=wxB(x,v,w)+w^{3}xD(x,vw)$ $\displaystyle+\sum_{a\geq
1}\sum_{n\geq
a+2}\sum_{j=a+2}^{n}\sum_{i=1}^{j-a-1}a_{n}(a,j)\frac{v^{i+a}w^{j+2}x^{n+2}}{(1-vwx)^{i}}$
$\displaystyle+\sum_{n\geq
3}\sum_{i=1}^{n-3}\sum_{j=i+3}^{n-1}\left(a_{n-1}(i,j)v^{i}w^{j}x^{n}+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1)v^{i}w^{j}x^{n}\right)$
$\displaystyle=wxB(x,v,w)+w^{3}xD(x,vw)$
$\displaystyle+\frac{w^{2}x^{2}(1-vwx)}{vwx+v-1}A^{+}(x,1-vwx,\frac{vw}{1-vwx})-\frac{vw^{2}x^{2}}{vwx+v-1}A^{+}(x,v,w)$
$\displaystyle+\sum_{n\geq
3}\sum_{i=1}^{n-3}\sum_{j=i+3}^{n-1}\left(a_{n-1}(i,j)v^{i}w^{j}x^{n}+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1)v^{i}w^{j}x^{n}\right)$
$\displaystyle=wxB(x,v,w)+w^{3}xD(x,vw)$
$\displaystyle+\frac{w^{2}x^{2}(1-vwx)}{vwx+v-1}A^{+}(x,1-vwx,\frac{vw}{1-vwx})-\frac{vw^{2}x^{2}}{vwx+v-1}A^{+}(x,v,w)$
$\displaystyle+xB(x,v,w)+\frac{1}{vwx+v-1}\sum_{a\geq 1}\sum_{n\geq
a+3}\sum_{j=a+3}^{n}a_{n}(a,j)(\frac{v^{j-1}w^{j+1}x^{nn+2}}{(1-vwx)^{j-2-a}}-v^{a+1}w^{j+1}x^{nn+2})$
$\displaystyle=wxB(x,v,w)+w^{3}xD(x,vw)$
$\displaystyle+\frac{w^{2}x^{2}(1-vwx)}{vwx+v-1}A^{+}(x,1-vwx,\frac{vw}{1-vwx})-\frac{vw^{2}x^{2}}{vwx+v-1}A^{+}(x,v,w)$
$\displaystyle+xB(x,v,w)+\frac{wx^{2}(1-vwx)^{2}}{v(vwx+v-1)}B(x,1-vwx,\frac{vw}{1-vwx})-\frac{vwx^{2}}{vwx+v-1}B(x,v,w).$

Hence, one gets the following system of functional equations.

######  Proposition 8.

We have

$\displaystyle A^{+}(x,v,w)$ $\displaystyle=wC(x,vw)+w^{2}D(x,vw)+B(x,v,w),$
$\displaystyle A^{-}(x,v,w)$
$\displaystyle=v^{2}wx^{2}+\frac{vx}{1-v}A(x,vw,1)-\frac{v^{2}x}{1-v}A(vx,w,1),$
$\displaystyle C(x,vw)$
$\displaystyle=vwx^{2}A(vwx,1,1)+vwx^{2}+v^{2}w^{2}x^{3}+xC(x,vw)$
$\displaystyle+\frac{vwx^{2}}{vwx+vw-1}A^{+}(\frac{vwx}{1-vwx},1-vwx,1)$
$\displaystyle-\frac{(1-vwx)x^{2}}{vwx+vw-1}A^{+}(x,1-vwx,\frac{vw}{1-vwx}),$
$\displaystyle D(x,vw)$
$\displaystyle=x^{2}A(vwx,1,1)-v^{2}w^{2}x^{4}+x(C(x,vw)-vwx^{2}A(vwx,1,1))+xD(x,vw)$
$\displaystyle+\frac{x^{2}(1-vwx)}{vwx+vw-1}A^{+}(\frac{vwx}{1-vwx},1-vwx,1)$
$\displaystyle-\frac{x^{2}(1-vwx)^{2}}{vw(vwx+vw-1)}A^{+}(x,1-vwx,\frac{vw}{1-vwx})-x^{2}C(x,vw),$
$\displaystyle B(x,v,w)$ $\displaystyle=wxB(x,v,w)+w^{3}xD(x,vw)$
$\displaystyle+\frac{w^{2}x^{2}(1-vwx)}{vwx+v-1}A^{+}(x,1-vwx,\frac{vw}{1-vwx})-\frac{vw^{2}x^{2}}{vwx+v-1}A^{+}(x,v,w)$
$\displaystyle+xB(x,v,w)+\frac{wx^{2}(1-vwx)^{2}}{v(vwx+v-1)}B(x,1-vwx,\frac{vw}{1-vwx})-\frac{vwx^{2}}{vwx+v-1}B(x,v,w).$

By Proposition 8, one may express $B(x,v,w)$ in terms the generating functions
$A,C,D$ and $C,D$ in terms of $A$. Substituting these relations into the last
equation from Proposition 8, one obtains

(15) $\displaystyle\frac{vx-wx-v-x+1}{vwx+v-1}A^{+}(x,v,w)$
$\displaystyle=\frac{w^{2}x^{2}(vwx-v-1)A^{+}(\frac{vwx}{1-vwx},1-vwx,1)}{vwx+vw-1}$
$\displaystyle+\frac{vwx^{2}(w^{2}-1)(vwx-1)A^{+}(x,1-vwx,\frac{vw}{1-vwx})}{(vwx+v-1)(vwx+vw-1)}$
$\displaystyle+w^{2}x^{2}(vwx-v-1)A(vwx,1,1)+x^{2}vw^{2}(vw^{2}x^{2}-vwx-1).$

Replacing $w$ by $w/v$ in (15), we have

(16) $\displaystyle\frac{v^{2}x-wx-v^{2}-vx+v}{v(wx+v-1)}A^{+}(x,v,w/v)$
$\displaystyle=\frac{w^{2}x^{2}(wx-v-1)A^{+}(\frac{wx}{1-wx},1-wx,1)}{v^{2}(wx+w-1)}+\frac{wx^{2}(w^{2}-v^{2})(wx-1)A^{+}(x,1-wx,\frac{w}{1-wx})}{v^{2}(wx+v-1)(wx+w-1)}$
$\displaystyle+\frac{w^{2}x^{2}}{v^{2}}(wx-v-1)A(wx,1,1)+\frac{x^{2}w^{2}}{v^{2}}(w^{2}x^{2}-vwx-v).$

We now seek to determine a formula for $A^{+}(x,v,w)$ using (16). First note
that by (2) and the main result from [6], we have

(17) $\displaystyle A(x,1,1)=\frac{1-3x-\sqrt{1-6x+x^{2}}}{2},$

which implies $A^{+}(x,v,1)$ may determined independently of $A^{-}(x,v,1)$
since $A$ occurs in (16) only through the $A(wx,1,1)$ term. Suppose for a
moment that $A(x,v,1)$ is as in Corollary 10 below. Then the second equation
in Proposition 8 above at $w=1$, together with the fact
$A(x,v,1)=A^{+}(x,v,1)+A^{-}(x,v,1)$, gives a linear system of equations in
the quantities $A^{+}$ and $A^{-}$. This yields

(18) $\displaystyle
A^{+}(x,v,1)=\frac{vx^{2}(1+v-vx)}{2(vx-v-2x+1)}\sqrt{1-6vx+v^{2}x^{2}}-\frac{vx^{2}(v^{2}x^{2}-v^{2}x-4vx+3v-1)}{2(vx-v-2x+1)},$

which we will assume for now to aid in solving (16).

Then taking $v=v_{0}=\frac{1-x+\sqrt{1-2(1+2w)x+(1+4w)x^{2}}}{2(1-x)}$ in
(16), and using (17) and (18), implies

$\displaystyle A^{+}(x,1-wx,\frac{w}{1-wx})$
$\displaystyle=\frac{(1-x)(wx+w-1)}{4(wx-w-2x+1)(wx-1)}\sqrt{1-6wx+w^{2}x^{2}}\sqrt{(1-x)(1-x-4vwx)}$
$\displaystyle+\frac{1-w+(2w^{2}-w-2)x-(w-1)(2w^{2}+4w+1)x^{2}+w(2w^{2}-2w-1)x^{3}}{4(wx-w-2x+1)(wx-1)}\sqrt{1-6wx+w^{2}x^{2}}$
$\displaystyle-\frac{(wx+w-1)(wx^{2}-wx-3x+1)}{4(wx-w-2x+1)(wx-1)}\sqrt{(1-x)(1-x-4vwx)}$
$\displaystyle+\frac{w-1-(3w^{2}-4)x+(8w^{3}+w^{2}-9w-3)x^{2}}{4(wx-w-2x+1)(wx-1)}$
$\displaystyle+\frac{-w(2w^{3}+8w^{2}-9w-4)x^{3}+w^{2}(2w^{2}-2w-1)x^{4}}{4(wx-w-2x+1)(wx-1)}.$

Substituting this expression into (15), and using (17) and (18), we obtain

(19) $\displaystyle A^{+}(x,v,w)$
$\displaystyle=\frac{(w^{2}-1)(1-x)vwx^{2}\sqrt{1-6vwx+v^{2}w^{2}x^{2}}\sqrt{(1-x)(1-x-4vwx)}}{4(vwx-
vw-2x+1)(vx-wx-v-x+1)}$
$\displaystyle+\frac{(1-x-2vwx)vw(1-x)x^{2}\sqrt{1-6vwx+v^{2}w^{2}x^{2}}}{4(vwx-
vw-2x+1)(vx-wx-v-x+1)}$
$\displaystyle+\frac{(1-2v^{2}x^{2}+4v^{2}x-2v^{2}-x^{2}-2x-2vwx(1-x))vw^{3}x^{2}\sqrt{1-6vwx+v^{2}w^{2}x^{2}}}{4(vwx-
vw-2x+1)(vx-wx-v-x+1)}$
$\displaystyle+\frac{(1-w^{2})(vwx^{2}-vwx-3x+1)vwx^{2}\sqrt{(1-x)(1-x-4vwx)}}{4(vwx-
vw-2x+1)(vx-wx-v-x+1)}$
$\displaystyle+\frac{(3(w^{2}-1)x^{2}+4(1-2w)x-w^{2}+4w-1)vwx^{2}}{4(vwx-
vw-2x+1)(vx-wx-v-x+1)}$
$\displaystyle-\frac{((w^{2}-1)x^{3}+8(w^{2}+1)x^{2}-(7w^{2}+4w+11)x+4w+4)v^{2}w^{2}x^{2}}{4(vwx-
vw-2x+1)(vx-wx-v-x+1)}$
$\displaystyle-\frac{2((1-x)(w^{2}x^{2}+x^{2}+3x-3)+vwx(1-x)^{2})v^{3}w^{3}x^{2}}{4(vwx-
vw-2x+1)(vx-wx-v-x+1)}.$

One may verify using programming that this expression for $A^{+}(x,v,w)$
indeed satisfies (15) and (18) and thus is the solution of (15) that is
sought. We may now determine $A^{-}(x,v,w)$. By the second equation in
Proposition 8, we have

$\displaystyle A^{-}(x,v,1)$
$\displaystyle=v^{2}x^{2}+\frac{vx}{1-v}A(x,v,1)-\frac{v^{2}x}{1-v}A(vx,1,1)$
$\displaystyle=v^{2}x^{2}+\frac{vx}{1-v}(A^{+}(x,v,1)+A^{-}(x,v,1))-\frac{v^{2}x}{1-v}A(vx,1,1).$

Solving for $A^{-}(x,v,1)$ in this last equation, and using (17) and (18),
yields

$A^{-}(x,v,1)=\frac{v^{2}x(x-1)(vx^{2}-vx-3x+1+(x-1)\sqrt{1-6vx+v^{2}x^{2}})}{2(vx-v-2x+1)}.$

Hence, by Proposition 8, we get the following explicit formula for
$A^{-}(x,v,w)$:

(20) $\displaystyle A^{-}(x,v,w)$
$\displaystyle=\frac{((1+v-2vx)x+(v^{2}x-v^{2}+vx-1)wx-(1-x)(1-vx)vw^{2})v^{2}wx^{2}}{2(vwx-2vx-w+1)(vwx-
vw-2x+1)}\sqrt{1-6vwx+v^{2}w^{2}x^{2}}$
$\displaystyle+\frac{(6vx^{2}-3(v+1)x+2-(2v^{2}x^{3}+2v(v+1)x^{2}-(3v^{2}+2v+3)x+2v+2)w)v^{2}wx^{2}}{2(vwx-2vx-w+1)(vwx-
vw-2x+1)}$
$\displaystyle+\frac{(v^{2}x^{3}-v^{2}x^{2}+vx^{3}+3vx^{2}-3vx-x^{2}-3x+3-(1-x)(1-vx)vwx)v^{3}w^{3}x^{2}}{2(vwx-2vx-w+1)(vwx-
vw-2x+1)}.$

We then have the following formula for $A(x,v,w)$.

######  Theorem 9.

The generating function for the joint distribution of the first and second
letter statistics on $\mathcal{S}_{n}(1243,1423)$ for $n\geq 1$is given by

$A^{+}(x,v,w)+A^{-}(x,v,w),$

where $A^{+}(x,v,w)$ and $A^{-}(x,v,w)$ are as in (19) and (20), respectively.

Substituting $w=1$ in the prior theorem and finding $vx+A(x,v,1)$, one obtains
the following result.

######  Corollary 10.

The generating function for the distribution of the first letter statistic on
$\mathcal{S}_{n}(1243,1423)$ for $n\geq 1$ is given by

$\frac{vx(2-3v-3x+3vx)+vx(v+x-vx)(vx+\sqrt{1-6vx+v^{2}x^{2}})}{2(1-v-2x+vx)}.$

###  3.2. The case $(1243,1342)$.

We first write a recurrence for $a_{n}(i,j)$ when $i<j$.

######  Lemma 11.

If $1\leq i<j\leq n-1$, then

$\displaystyle a_{n}(i,j)$
$\displaystyle=\sum_{k=i+1}^{j-1}a_{n-1}(i,k)+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\sum_{b=a+1}^{j-c-2}\binom{i-a-1}{c}a_{n-c-2}(a,b)$
(21)
$\displaystyle\quad+\delta_{i+1,j}\cdot\left(a_{n-1}(i,i+1)+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,i-c)\right),$

with $a_{n}(i,n)=a_{n-1}(i)$ for $1\leq i\leq n-1$.

###### Proof.

The formula when $j=n$ is obvious, so assume $j<n$. Let $\mathcal{A}_{n,i,j}$
denote the subset of $\mathcal{S}_{n,i}(1243,1342)$ having second letter $j$.
Let $\pi\in\mathcal{A}_{n,i,j}$ where $1\leq i<j\leq n-1$ and $k$ denote the
third letter of $\pi$. Suppose $k<j$, noting that this is indeed a requirement
if $j\geq i+2$, for otherwise $j<n$ would imply a $1342$ would occur. If
$i+1\leq k\leq j-1$, then the letter $j$ is extraneous and thus may be deleted
from $\pi$ since all elements of $[k+1,n]-\\{j\\}$ must occur in increasing
order with all elements of $[i+1,k]$ occurring to the left of those in
$[k+1,n]-\\{j\\}$. This implies the first summation formula in (11). Otherwise
$k<i$ and we may write $\pi=ijx_{1}\cdots x_{c}ad\rho$, where $1\leq
a<x_{1}<\cdots<x_{c}\leq i-1$ and $d>a$. Note that $d<j$ if $j\geq i+2$ in
order to avoid a $1342$ of the form $ijdt$ for some $t\in[i+1,j-1]$.

We argue now that $d<j$ implies that $i$ and $j$ may be deleted from $\pi$.
Clearly, the letters $i$ and $j$ are extraneous concerning the avoidance of
$1243$ in light of the ascent $a,d$ where $a<i$. They are also irrelevant
concerning $1342$, whence they may be deleted. To see this, note that if
$d<i$, then members of $[d+1,n]$ occurring to the right of $d$ must form an
increasing subsequence due to $a$ preceding $d$ and thus no $1342$ can start
with $ij$. The same conclusion is reached if $i<d<j$, for in this case all
letters in $[i+1,d-1]$ occur to the left of those in $[d+1,n]-\\{j\\}$, with
the latter forming an increasing subsequence. Since $x_{1},\ldots,x_{c}$ may
clearly also be deleted from $\pi$ as $a<x_{c}$, one is left with
$\pi^{\prime}\in\mathcal{A}_{n-c-2,a,b}$ for some $a$ and $b$. Note that
$b\in[a+1,j-c-2]$ (after reducing letters) since
$d\in[a+1,j-1]-\\{x_{1},\ldots,x_{c},i\\}$. Considering all possible $a$, $c$
and $b$ then yields the triple sum expression in (11) and finishes the case
when $j\geq i+2$. On the other hand, if $j=i+1$, then $k=j+1$ is possible
without introducing an occurrence of $1342$, in which case $k$ may be deleted
resulting in a member of $\mathcal{A}_{n-1,i,i+1}$. Likewise, $d=j+1$ is also
possible in the decomposition of $\pi$ above. Combining these two additional
cases then accounts for the second line in formula (11) and completes the
proof. ∎

From (11), we may deduce the following further useful formulas.

######  Lemma 12.

If $1\leq i\leq n-2$, then

(22) $a_{n}(i,i+1)=a_{n}(i,i+2)$

and

(23) $a_{n}(i,i+1)=\sum_{\ell=1}^{i}a_{n-1}(\ell,i+1).$

###### Proof.

Both equalities are easily seen to hold if $i=n-2$, so assume $1\leq i\leq
n-3$. Taking $j=i+1$ and $j=i+2$ in (11), and comparing the results, then
completes the proof of (22). For (23), first observe

$\displaystyle\sum_{\ell=1}^{i-1}a_{n-1}(\ell,i+1)$
$\displaystyle=\sum_{\ell=1}^{i-1}\sum_{k=\ell+1}^{i}a_{n-2}(\ell,k)+\sum_{\ell=1}^{i-1}\sum_{a=1}^{\ell-1}\sum_{c=0}^{\ell-a-1}\sum_{b=a+1}^{i-c-1}\binom{\ell-a-1}{c}a_{n-c-3}(a,b)$
$\displaystyle=\sum_{\ell=1}^{i-1}\sum_{k=\ell+1}^{i}a_{n-2}(\ell,k)+\sum_{a=1}^{i-2}\sum_{c=0}^{i-a-2}\sum_{b=a+1}^{i-c-1}a_{n-c-3}(a,b)\sum_{\ell=a+c+1}^{i-1}\binom{\ell-a-1}{c}$
$\displaystyle=\sum_{\ell=1}^{i-1}\sum_{k=\ell+1}^{i}a_{n-2}(\ell,k)+\sum_{a=1}^{i-2}\sum_{c=1}^{i-a-1}\sum_{b=a+1}^{i-c}\binom{i-a-1}{c}a_{n-c-2}(a,b).$

Then by (22) and (11) when $j=i+2$, we have

$\displaystyle
a_{n}(i,i+1)-\sum_{\ell=1}^{i-1}a_{n-1}(\ell,i+1)=a_{n}(i,i+2)-\sum_{\ell=1}^{i-1}a_{n-1}(\ell,i+1)$
$\displaystyle=a_{n-1}(i,i+1)-\sum_{\ell=1}^{i-1}\sum_{k=\ell+1}^{i}a_{n-2}(\ell,k)$
$\displaystyle\quad+\left(\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\sum_{b=a+1}^{i-c}-\sum_{a=1}^{i-2}\sum_{c=1}^{i-a-1}\sum_{b=a+1}^{i-c}\right)\binom{i-a-1}{c}a_{n-c-2}(a,b)$
$\displaystyle=a_{n-1}(i,i+1)-\sum_{\ell=1}^{i-1}\sum_{k=\ell+1}^{i}a_{n-2}(\ell,k)+\sum_{a=1}^{i-1}\sum_{b=a+1}^{i}a_{n-2}(a,b)=a_{n-1}(i,i+1),$

which completes the proof of (23). ∎

To summarize, we have the following recurrence for $a_{n}(i,j)$:

$\displaystyle a_{n}(i,j)$ $\displaystyle=a_{n-1}(j),\quad 1\leq j<i\leq n,$
$\displaystyle a_{n}(i,n)$ $\displaystyle=a_{n-1}(i),\quad 1\leq i\leq n-1,$
(24) $\displaystyle a_{n}(i,i+1)$
$\displaystyle=\sum_{\ell=1}^{i}a_{n-1}(\ell,i+1),\quad 1\leq i\leq n-2,$
$\displaystyle a_{n}(i,i+2)$ $\displaystyle=a_{n}(i,i+1),\quad 1\leq i\leq
n-2,$ $\displaystyle a_{n}(i,j)$
$\displaystyle=\sum_{k=i+1}^{j-1}a_{n-1}(i,k)+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\sum_{b=a+1}^{j-c-2}\binom{i-a-1}{c}a_{n-c-2}(a,b),$

for $4\leq i+3\leq j\leq n-1$.

In this case, we state the recurrence formulas satisfied by the corresponding
distribution polynomials which will aid in translating (3.2) to functional
equations as they are not too lengthy. Define
$A_{n}^{+}(v,w)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}a_{n}(i,j)v^{i}w^{j}$,
$A_{n}^{-}(v,w)=\sum_{i=2}^{n}\sum_{j=1}^{i-1}a_{n}(i,j)v^{i}w^{j}$ and
$A_{n}(v,w)=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{n}(i,j)v^{i}w^{j}$ for $n\geq 2$.
Clearly, $A_{n}(v,w)=A^{+}_{n}(v,w)+A^{-}_{n}(v,w)$ for all $n\geq 2$.
Further, we define

$C_{n}(v)=\sum_{i=1}^{n-2}a_{n}(i,i+1)v^{i}\quad\text{and}\quad
B_{n}(v,w)=\sum_{i=1}^{n-4}\sum_{j=i+3}^{n-1}a_{n}(i,j)v^{i}w^{j}.$

Then (3.2) may be rewritten in terms of these distributions as

$\displaystyle A_{n}^{-}(v,w)$
$\displaystyle=\frac{v}{1-v}A_{n-1}(vw,1)-\frac{v^{n+1}}{1-v}A_{n-1}(w,1),$
$\displaystyle A_{n}^{+}(v,w)$
$\displaystyle=B_{n}(v,w)+w^{2}(C_{n}(vw)-(vw)^{n-2}A_{n-2}(1,1))+wC_{n}(vw)+w^{n}A_{n-1}(1,w),$
$\displaystyle C_{n}(v)$ $\displaystyle=\frac{1}{v}A^{+}_{n-1}(1,v),$
$\displaystyle B_{n}(v,w)$
$\displaystyle=\frac{w}{1-w}(B_{n-1}(v,w)+w^{2}(C_{n-1}(vw)-A_{n-3}(1,1)(vw)^{n-3}))$
$\displaystyle-\frac{w^{n}}{1-w}(B_{n-1}(v,1)+C_{n-1}(v)-A_{n-3}(1,1)v^{n-3})$
$\displaystyle+\frac{w^{3}}{1-w}(C_{n-1}(vw)-A_{n-3}(1,1)v^{n-3}w^{n-3})-\frac{w^{n}}{1-w}(C_{n-1}(v)-A_{n-3}(1,1)v^{n-3})$
$\displaystyle+\sum_{i=1}^{n-4}\sum_{j=i+3}^{n-1}\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\sum_{b=a+1}^{j-c-2}\binom{i-1-a}{c}a_{n-c-2}(a,b)v^{i}w^{j}.$

Define $A^{\pm}(x,v,w)=\sum_{n\geq 2}A_{n}^{\pm}(v,w)x^{n}$ and
$A(x,v,w)=\sum_{n\geq 2}A_{n}(v,w)x^{n}$. Further, define
$B(x,v,w)=\sum_{n\geq 2}B_{n}(v,w)x^{n}$ and $C(x,v)=\sum_{n\geq
2}C_{n}(v)x^{n}$. Rewriting the preceding recurrences in terms of generating
functions yields the following result.

######  Proposition 13.

We have

$\displaystyle A^{-}(x,v,w)$
$\displaystyle=v^{2}wx^{2}+\frac{vx}{1-v}A(x,vw,1)-\frac{v^{2}x}{1-v}A(vx,w,1),$
$\displaystyle A^{+}(x,v,w)$
$\displaystyle=vw^{2}x^{2}-vw^{3}x^{3}+B(x,v,w)+w^{2}(C(x,vw)-x^{2}A(vwx,1,1))$
$\displaystyle+wC(x,vw)+wxA(wx,v,1),$

where

$\displaystyle C(x,v)$ $\displaystyle=\frac{x}{v}A^{+}(x,1,v),$ $\displaystyle
B(x,v,w)$ $\displaystyle=\frac{wx(1-v)}{(1-v-vwx)(1-w)}(B(x,v,w)-B(wx,v,1))$
$\displaystyle+\frac{2(1-vw)w^{3}x}{(1-vw-
vwx)(1-w)}C(x,vw)-\frac{2wx(1-v)}{(1-v-vwx)(1-w)}C(wx,v)$
$\displaystyle+\frac{x^{2}w^{2}(1-vwx)^{2}}{(1-v-vwx)(1-vw-
vwx)}(B(\frac{vwx}{1-vwx},1-vwx,1)-B(x,1-vwx,\frac{vw}{1-vwx}))$
$\displaystyle+\frac{2x^{2}w^{2}(1-vwx)^{2}}{(1-v-vwx)(1-vw-
vwx)}C(\frac{vwx}{1-vwx},1-vwx).$

By mathematical programming, one may verify the following solution of the
foregoing system of functional equations.

######  Theorem 14.

The generating function for the joint distribution of the first and second
letter statistics on $\mathcal{S}_{n}(1243,1342)$ for $n\geq 1$is given by
$A(x,v,w)=A^{+}(x,v,w)+A^{-}(x,v,w)$, where

$\displaystyle A^{+}(x,v,w)$
$\displaystyle=\frac{(1-v+(v^{2}x-2v^{2}+vx-x)w-vx(x-2)(v-1)w^{2})vw^{2}x^{2}}{2(1-v+wx(v-2))(1-2vw-x(1-vw))}\sqrt{v^{2}w^{2}x^{2}-6vwx+1}$
$\displaystyle+\frac{(1-v+(6v^{2}-4v-x(4v^{2}-2v+1))w+xv(x(v^{2}+4v-4)-2v^{2}-6v+6)w^{2})vw^{2}x^{2}}{2(1-v+wx(v-2))(1-2vw-x(1-vw))}$
$\displaystyle-\frac{(x-2)(v-1)v^{3}w^{5}x^{4}}{2(1-v+wx(v-2))(1-2vw-x(1-vw))}$
$\displaystyle=vw^{2}x^{2}+w^{2}v(vw+w+1)x^{3}+w^{2}v(2v^{2}w^{2}+2vw^{2}+2vw+2w^{2}+w+1)x^{4}+\cdots$

and

$\displaystyle A^{-}(x,v,w)$
$\displaystyle=\frac{(x(1+v-2vx)+x(v^{2}x-v^{2}+vx-1)w-v(x-1)(vx-1)w^{2})v^{2}wx^{2}}{2(1-vw-x(2-vw))(1-w-vx(2-w))}\sqrt{v^{2}w^{2}x^{2}-6vwx+1}$
$\displaystyle+\frac{((3x-2)(w-1)+(-w^{2}x^{2}-3w^{2}x-2wx^{2}+3w^{2}+2wx+6x^{2}-2w-3x)v)v^{2}wx^{2}}{2(1-vw-x(2-vw))(1-w-vx(2-w))}$
$\displaystyle+\frac{(w^{2}x+wx^{2}-w^{2}+3wx-2x^{2}-3w-2x+3-(x-1)(w-1)vwx)v^{4}w^{2}x^{3}}{2(1-vw-x(2-vw))(1-w-vx(2-w))}$
$\displaystyle=v^{2}wx^{2}+(vw+v+1)v^{2}wx^{3}+2(v^{2}w^{2}+v^{2}w+v^{2}+vw+v+1)v^{2}wx^{4}+\cdots.$

Moreover, the generating functions counting the members of
$\mathcal{S}_{n}(1243,1342)$ starting with an ascent of size greater than two
or of size exactly one and whose second letter is not $n$ in either case
according to the first and second letter statistics are given respectively by

$\displaystyle B(x,v,w)$
$\displaystyle=\frac{(vwx-2wx^{2}+2wx+x-1)w^{2}x^{2}}{2(1-2vw-x(1-vw))(1-v-wx(2-v))}\sqrt{v^{2}w^{2}x^{2}-6vwx+1}$
$\displaystyle+\frac{(1-x+(3vx-4v+2x-2)wx-(2x+v-6)vw^{2}x^{2})w^{2}x^{2}}{2(1-2vw-x(1-vw))(1-v-wx(2-v))}$
$\displaystyle=2vw^{4}x^{5}+2(4vw+2w+1)vw^{4}x^{6}+2\big{(}17v^{2}w^{2}+10vw^{2}+5vw+4w^{2}$
$\displaystyle\quad+2w+1\big{)}vw^{4}x^{7}+\cdots$

and

$\displaystyle C(x,v)$
$\displaystyle=\frac{-vx^{2}(vx^{2}-2vx-3x+2+(x-2)\sqrt{v^{2}x^{2}-6vx+1})}{2(1-x-2v+vx)}$
$\displaystyle=vx^{3}+(2v+1)vx^{4}+(6v^{2}+3v+1)vx^{5}+(22v^{3}+11v^{2}+4v+1)vx^{6}+\cdots.$

Substituting $w=1$ in the prior theorem and finding $vx+A(x,v,1)$, one obtains
the following result.

######  Corollary 15.

The generating function for the distribution of the first letter statistic on
$\mathcal{S}_{n}(1243,1342)$ for $n\geq 1$ is given by

$\frac{vx(2-3v-3x+3vx)+vx(v+x-vx)(vx+\sqrt{1-6vx+v^{2}x^{2}})}{2(1-v-2x+vx)}.$

###  3.3. The case $(1243,1324)$.

We first write a recurrence for $a_{n}(i,j)$ when $i<j$.

######  Lemma 16.

We have

(25)
$a_{n}(i,i+1)=a_{n-1}(i,i+1)+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\sum_{b=a+1}^{i-c}\binom{i-a-1}{c}a_{n-c-2}(a,b),\quad
1\leq i\leq n-2,$

and

(26)
$a_{n}(i,j)=a_{n-1}(i,j)+\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1),\quad
3\leq i+2\leq j\leq n-1,$

with $a_{n}(i,n)=a_{n-1}(i)$ for $1\leq i\leq n-1$.

###### Proof.

A similar proof may be given as in the prior two cases. Note that the formula
for $a_{n}(i,n)$ is obvious since an $n$ in the second position may clearly be
removed. Let $k$ denote the third letter of a member of
$\mathcal{S}_{n,i}(1243,1324)$. If $j=i+1$ where $1\leq i\leq n-2$, then
either $k=i+2$ or $k<i$, where clearly $k$ may be deleted in the former case.
Assuming the latter, let $a,d$ denote the second leftmost ascent. Then we must
have $a+1\leq d\leq i+2$, for otherwise a $1243$ would occur. Thus, each
letter prior to $a$ may be deleted in this case and considering all possible
$a$, $b$ and $c$, where $b$ and $c$ are as before, implies formula (25). If
$i+2\leq j<n$, then we have $k=j+1$ or $k<i$, the former leading to
$a_{n-1}(i,j)$ possibilities. On the other hand, if $k<i$ and $a,d$ denotes
the second ascent, then we must have $d=j+1$. To see this, note that elements
of $[d+1,n]$ to the right of $d$ must form an increasing subsequence and thus
$d<j<n$ would imply an occurrence of $1324$ of the form $ijxn$ where
$x\in[i+1,j-1]$. Therefore $d=j+1$ implies all letters prior to $a$ again may
be deleted, resulting in a permutation that starts $a,j-c-1$. Considering all
possible $a$ and $c$ then accounts for the double sum expression in (26) and
completes the proof. ∎

From this, one may deduce the following further useful formula.

######  Lemma 17.

If $1\leq i\leq n-3$ and $i+2\leq j\leq n-1$, then

(27)
$a_{n}(i,j)=a_{n-1}(1,j-1)+a_{n-1}(2,j-1)+\cdots+a_{n-1}(i-1,j-1)+a_{n-1}(i,j).$

###### Proof.

Note that (27) is clearly true on combinatorial grounds if $i=1$ since the
third letter of a member of $\mathcal{S}_{n}(1243,1324)$ starting with $1,j$
where $j<n$ must be $j+1$. So let $i\geq 2$ and $j\in[i+2,n-1]$. Then by (26),
we have

(28)
$\sum_{\ell=1}^{i-1}a_{n-1}(\ell,j-1)=\sum_{\ell=1}^{i-1}\left(a_{n-2}(\ell,j-1)+\sum_{a=1}^{\ell-1}\sum_{c=0}^{\ell-a-1}\binom{\ell-a-1}{c}a_{n-c-3}(a,j-c-2)\right).$

If $i\geq 3$, then

$\displaystyle\sum_{\ell=2}^{i-1}\sum_{a=1}^{\ell-1}\sum_{c=0}^{\ell-a-1}\binom{\ell-a-1}{c}a_{n-c-3}(a,j-c-2)$
$\displaystyle=\sum_{a=1}^{i-2}\sum_{c=0}^{i-a-2}a_{n-c-3}(a,j-c-2)\sum_{\ell=a+c+1}^{i-1}\binom{\ell-a-1}{c}$
$\displaystyle=\sum_{a=1}^{i-2}\sum_{c=0}^{i-a-2}a_{n-c-3}(a,j-c-2)\binom{i-a-1}{c+1}$
$\displaystyle=\sum_{c=1}^{i-2}\sum_{a=1}^{i-c-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1).$

Thus, the right-hand side of (28) is given by

$\displaystyle\sum_{\ell=1}^{i-1}a_{n-2}(\ell,j-1)+\sum_{c=1}^{i-2}\sum_{a=1}^{i-c-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1)$
$\displaystyle=\sum_{c=0}^{i-2}\sum_{a=1}^{i-c-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1)$
$\displaystyle=\sum_{a=1}^{i-1}\sum_{c=0}^{i-a-1}\binom{i-a-1}{c}a_{n-c-2}(a,j-c-1)$
$\displaystyle=a_{n}(i,j)-a_{n-1}(i,j),$

again by (26), which completes the proof. ∎

Summarizing, we have the following recurrence relations satisfied by
$a_{n}(i,j)$:

(35) $\displaystyle\left\\{\begin{array}[]{ll}a_{n}(i,j)&=a_{n-1}(j),\quad
1\leq j<i\leq n,\\\\[4.0pt] a_{n}(i,n)&=a_{n-1}(i),\quad 1\leq i\leq n-1,\\\
a_{n}(i,j)&=\sum_{\ell=1}^{i-1}a_{n-1}(\ell,j-1)+a_{n-1}(i,j),\\\
&\qquad\qquad\qquad\qquad\qquad\qquad\quad 1\leq i\leq n-3\mbox{ and }i+2\leq
j\leq n-1,\\\\[4.0pt]
a_{n}(i,i+1)&=a_{n-1}(i,i+1)+\sum_{a=1}^{i-1}\sum_{b=a+1}^{i}\sum_{c=0}^{i-b}\binom{i-a-1}{c}a_{n-c-2}(a,b),\\\
&\qquad\qquad\qquad\qquad\qquad\qquad\quad 1\leq i\leq n-2.\end{array}\right.$

Define $A_{n}(v,w)$, $A_{n}^{\pm}(v,w)$ and $C_{n}(v)$ as in the previous
subsection, but with $B_{n}(v,w)$ now given by
$B_{n}(v,w)=\sum_{i=1}^{n-3}\sum_{j=i+2}^{n-1}a_{n}(i,j)v^{i}w^{j}$.
Translating (35) then yields the following recurrences:

$\displaystyle A_{n}^{-}(v,w)$
$\displaystyle=\sum_{i=2}^{n}\sum_{j=1}^{i-1}a_{n-1}(j)v^{i}w^{j}=\frac{v}{1-v}A_{n-1}(vw,1)-\frac{v^{n+1}}{1-v}A_{n-1}(w,1),$
$\displaystyle A_{n}^{+}(v,w)$
$\displaystyle=\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}a_{n}(i,j)v^{i}w^{j}+\sum_{i=1}^{n-1}a_{n}(i,j)v^{i}w^{n}$
$\displaystyle=\sum_{i=1}^{n-3}\sum_{j=i+2}^{n-1}a_{n}(i,j)v^{i}w^{j}+w\sum_{i=1}^{n-2}a_{n}(i,i+1)(vw)^{i}+w^{n}A_{n-1}(v,1)$
$\displaystyle=B_{n}(v,w)+wC_{n}(vw)+w^{n}A_{n-1}(v,1),$

with

$\displaystyle B_{n}(v,w)$
$\displaystyle=\sum_{i=2}^{n-3}\sum_{j=i+2}^{n-1}\sum_{k=1}^{i-1}a_{n-1}(i,j-1)v^{i}w^{j}+\sum_{i=1}^{n-3}\sum_{j=i+2}^{n-1}a_{n-1}(i,j)v^{i}w^{j}$
$\displaystyle=w\sum_{k=1}^{n-4}\sum_{j=k+3}^{n-1}\sum_{i=k+1}^{j-2}a_{n-1}(i,j-1)v^{i}w^{j}+\sum_{i=1}^{n-4}\sum_{j=i+2}^{n-2}a_{n-1}(i,j)v^{i}w^{j}+\sum_{i=1}^{n-3}a_{n-2}(i)v^{i}w^{n-1}$
$\displaystyle=\frac{wv}{1-v}B_{n-1}(v,w)-\frac{w}{1-v}B_{n-1}(1,vw)+B_{n-1}(v,w)+w^{n-1}A_{n-2}(v,1)$
$\displaystyle-w^{n-1}v^{n-2}A_{n-3}(1,1)$

and

$\displaystyle C_{n}(v)$
$\displaystyle=C_{n-1}(v)+v^{n-2}A_{n-3}(1,1)+\sum_{i=1}^{n-2}\sum_{a=1}^{i-1}\sum_{b=a+1}^{i}\sum_{c=0}^{i-b}\binom{i-a-1}{c}a_{n-2-c}(a,b)v^{i}$
$\displaystyle=C_{n-1}(v)+v^{n-2}A_{n-3}(1,1)+\sum_{a=1}^{n-3}\sum_{b=a+1}^{n-2}\sum_{c=0}^{n-2-b}\sum_{i=b+c}^{n-2}\binom{i-a-1}{c}a_{n-2-c}(a,b)v^{i}.$

Define $A(x,v,w)$, $A^{\pm}(x,v,w)$ and $C(x,v)$ as in the previous
subsection, with $B(x,v,w)=\sum_{n\geq 2}B_{n}(v,w)x^{n}$ per the new
definition for $B_{n}(v,w)$. From the preceding recurrences, we obtain the
following system of functional equations.

######  Proposition 18.

We have

$\displaystyle A^{-}(x,v,w)$
$\displaystyle=v^{2}wx^{2}+\frac{vx}{1-v}A(x,vw,1)-\frac{v^{2}x}{1-v}A(vx,w,1),$
$\displaystyle A^{+}(x,v,w)$
$\displaystyle=vw^{2}x^{2}+B(x,v,w)+wC(x,vw)+wxA(wx,v,1),$

where

$\displaystyle B(x,v,w)$
$\displaystyle=\frac{wx}{1-v}(vB(x,v,w)-B(x,1,vw))+xB(x,v,w)+wx^{2}A(wx,v,1)$
$\displaystyle-vw^{2}x^{3}A(vwx,1,1)-v^{2}w^{3}x^{4},$ $\displaystyle C(x,v)$
$\displaystyle=\frac{vx^{3}(1+vx)}{1-x}+\frac{vx^{3}}{1-x}A(vx,1,1)$
$\displaystyle+\frac{x^{2}}{(vx+v-1)(1-x)}(vA^{+}(\frac{vx}{1-vx},1-vx,1)-(1-vx)A^{+}(x,1-vx,\frac{v}{1-vx})).$

By programming, one may verify that the solution of the foregoing system is
given as follows.

######  Theorem 19.

We have $A(x,v,w)=A^{+}(x,v,w)+A^{-}(x,v,w)$, where

$\displaystyle A^{+}(x,v,w)$
$\displaystyle=\frac{(1-v+(v^{2}x-2v^{2}+vx-x)w-vx(x-2)(v-1)w^{2})vw^{2}x^{2}}{2(1-v+wx(v-2))(1-2vw-x(1-vw))}\sqrt{v^{2}w^{2}x^{2}-6vwx+1}$
$\displaystyle+\frac{(1-v+(6v^{2}-4v-x(4v^{2}-2v+1))w+xv(x(v^{2}+4v-4)-2v^{2}-6v+6)w^{2})vw^{2}x^{2}}{2(1-v+wx(v-2))(1-2vw-x(1-vw))}$
$\displaystyle-\frac{(x-2)(v-1)v^{3}w^{5}x^{4}}{2(1-v+wx(v-2))(1-2vw-x(1-vw))}$
$\displaystyle=vw^{2}x^{2}+w^{2}v(vw+w+1)x^{3}+w^{2}v(2v^{2}w^{2}+2vw^{2}+2vw+2w^{2}+w+1)x^{4}+\cdots$

and

$\displaystyle A^{-}(x,v,w)$
$\displaystyle=\frac{(x(1+v-2vx)+x(v^{2}x-v^{2}+vx-1)w-v(x-1)(vx-1)w^{2})v^{2}wx^{2}}{2(1-vw-x(2-vw))(1-w-vx(2-w))}\sqrt{v^{2}w^{2}x^{2}-6vwx+1}$
$\displaystyle+\frac{((3x-2)(w-1)+(-w^{2}x^{2}-3w^{2}x-2wx^{2}+3w^{2}+2wx+6x^{2}-2w-3x)v)v^{2}wx^{2}}{2(1-vw-x(2-vw))(1-w-vx(2-w))}$
$\displaystyle+\frac{(w^{2}x+wx^{2}-w^{2}+3wx-2x^{2}-3w-2x+3-(x-1)(w-1)vwx)v^{4}w^{2}x^{3}}{2(1-vw-x(2-vw))(1-w-vx(2-w))}$
$\displaystyle=v^{2}wx^{2}+(vw+v+1)v^{2}wx^{3}+2(v^{2}w^{2}+v^{2}w+v^{2}+vw+v+1)v^{2}wx^{4}+\cdots.$

Moreover,

$\displaystyle B(x,v,w)$
$\displaystyle=-\frac{vw^{2}x^{2}(wx^{2}-2wx-x+1)}{2(vwx-2vw-x+1)(vwx-2wx-v+1)}\sqrt{v^{2}w^{2}x^{2}-6vwx+1}$
$\displaystyle-\frac{vw^{2}x^{2}(vw^{2}x^{3}-2vw^{2}x^{2}-vwx^{2}+3vwx-3wx^{2}+2wx+x-1)}{2(vwx-2vw-x+1)(vwx-2wx-v+1)}$
$\displaystyle=vw^{3}x^{4}+w^{3}v(3vw+2w+1)x^{5}+w^{3}v(11v^{2}w^{2}+8vw^{2}+4vw+4w^{2}+2w+1)x^{6}+\cdots$

and

$\displaystyle
C(x,v)=\frac{-vx^{2}(vx^{2}-2vx-3x+2+(x-2)\sqrt{v^{2}x^{2}-6vx+1})}{2(1-x-2v+vx)}.$

Taking $w=1$ in the prior theorem yields the following result.

######  Corollary 20.

The generating function for the distribution of the first letter statistic on
$\mathcal{S}_{n}(1243,1324)$ for $n\geq 1$ is given by

$\frac{vx(2-3v-3x+3vx)+vx(v+x-vx)(vx+\sqrt{1-6vx+v^{2}x^{2}})}{2(1-v-2x+vx)}.$

##  4\. Conclusion

In this paper, we have shown that each of the nine classes in Conjecture 1
above has last letter statistic distribution given by the array $S_{n,k}$,
making use of a variety of techniques. In most of these cases, a more general
result is established from which the desired equivalence follows as a specific
case. We have also demonstrated by numerical evidence that there are no other
avoidance classes for which the conjecture applies. We remark that concerning
the final six pattern pairs in Conjecture 1, we have shown further that the
ascents and last letter statistics has the same joint distribution on the
avoidance class in question as does the dist and last letter (plus one)
statistics on the class $I_{n}(\geq,-,>)$ of inversion sequences, where dist
records the number of distinct positive letters in an inversion sequence. This
confirms a further conjecture of Lin and Kim (see [7, Conjecture 3.3]). In
these cases, we count equivalently, by the number of descents, members of
$\mathcal{S}_{n,i}(\sigma,\tau)$, where $\sigma,\tau$ denotes (the reversal
of) one of the last six pattern pairs in Conjecture 1. The arguments used to
establish these further $q$-results, where $q$ marks the number of descents,
are however quite technical and differ when $q=1$ from the arguments presented
here in the respective cases. Details in the proof of these further results
will be given in a forthcoming paper.

## References

  * [1] J. Bonin, L. Shapiro and R. Simion, Some $q$-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, _J. Statist. Plann. Inference_ 34 (1993), 35–55.
  * [2] S. Corteel, M. Martinez, C. D. Savage and M. Weselcouch, Patterns in inversion sequences I, _Discrete Math. Theor. Comput. Sci._ 18 (2016), #2.
  * [3] S. Gire, Arbres, permutations à motifs exclus et cartes planaire: quelques problèmes algorithmiques et combinatoires, Ph.D. These, University of Bordeaux, 1993.
  * [4] Q. Hou and T. Mansour, Kernel method and linear recurrence system, J. Comput. Appl. Math. 216(1) (2008), 227–242.
  * [5] S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, Berlin, 2011.
  * [6] D. Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Discrete Math. 218 (2000), 121–130.
  * [7] Z. Lin and D. Kim, Refined restricted inversion sequences, arXiv:1706.07208v2, accepted, Ann. Comb. (2021).
  * [8] T. Mansour and M. Shattuck, Pattern avoidance in inversion sequences, _Pure Math. Appl. (PU.M.A.)_ 25 (2015), 157–176.
  * [9] E. Pergola and R. A. Sulanke, Schröder triangles, paths and parallelogram polyominoes, _J. Integer Seq._ 1 (1998), Art. 98.1.7.
  * [10] J. L. Ramírez and V. F. Sirvent, Generalized Schröder matrix and its combinatorial interpretation, _Linear Multilinear Algebra_ 66 (2018), 418–433.
  * [11] D. G. Rogers, A Schröder triangle: Three combinatorial problems, _Combinatorial Mathematics V, Lecture Notes in Mathematics_ 622, Springer, Berlin, 1977, 175–196.
  * [12] N. J. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org, 2010.
  * [13] J. West, Generating trees and the Catalan and Schröder numbers, _Discrete Math._ 146 (1995), 247–262.
  * [14] J. West, Generating trees and forbidden subsequences, _Discrete Math._ 157 (1996), 363–374.