format: text

text:
# Restricted Permutations, Fibonacci Numbers, and 𝑘-generalized Fibonacci Numbers

## 1 Introduction

Let $`S_n`$ denote the set of permutations of $`\{1,\mathrm{},n\}`$, written in one-line notation, and suppose $`\pi S_n`$ and $`\sigma S_k`$. We say $`\pi `$ avoids $`\sigma `$ whenever $`\pi `$ contains no subsequence with all of the same pairwise comparisons as $`\sigma `$. For example, the permutation 214538769 avoids 312 and 2413, but it has 2586 as a subsequence so it does not avoid 1243. If $`\pi `$ avoids $`\sigma `$ then $`\sigma `$ is sometimes called a pattern or a forbidden subsequence and $`\pi `$ is sometimes called a restricted permutation or a pattern-avoiding permutation. Pattern avoidance has proved to be a useful language in a variety of seemingly unrelated problems, from stack sorting \[14, Ch. 2.2.1\], to singularities of Schubert varieties , to Chebyshev polynomials of the second kind , to rook polynomials for a rectangular board .

One important and often difficult problem in the study of restricted permutations is the enumeration problem: given a set $`R`$ of permutations, enumerate the set $`S_n(R)`$ consisting of those permutations in $`S_n`$ which avoid every element of $`R`$. The earliest solution to an instance of this problem seems to be MacMahon’s enumeration of $`S_n(123)`$, which is implicit in chapter V of . The first explicit solution seems to be Hammersley’s enumeration of $`S_n(321)`$ in . In \[14, Ch. 2.2.1\] and \[15, Ch. 5.1.4\] Knuth shows that for any $`\sigma S_3`$, we have $`|S_n(\sigma )|=C_n`$, the $`n`$th Catalan number. Other authors considered restricted permutations in the 1970s and early 1980s (see, for instance, , , and ) but the first systematic study was not undertaken until 1985, when Simion and Schmidt  solved the enumeration problem for every subset of $`S_3`$. More recent work on various instances of the enumeration problem may be found in , , , , , , , , , , , , , , , , and .

In this paper we are concerned with instances of the enumeration problem whose solutions involve the Fibonacci numbers $`F_n`$ or the $`k`$-generalized Fibonacci numbers $`F_{k,n}`$. (See section 2 for definitions.) The earliest example of such a result is Simion and Schmidt’s proof \[32, Prop. 15\] that

$$|S_n(123,132,213)|=F_{n+1}(n1).$$
(1)
Somewhat later West used generating trees to show  that for many sets $`R`$ consisting of one pattern of length three and one of length four, $`|S_n(R)|=F_{2n1}`$. More recently Mansour expressed \[23, Thm. 3\] the ordinary generating function for $`|S_n(132,213,\tau )|`$ as a determinant for every $`\tau S_k(132,213)`$. Using this result, Mansour showed that

$$|S_n(132,213,2341)|=F_{n+2}1(n1)$$

and

$$|S_n(132,213,1234)|=T_{n+1}(n1).$$

Here $`T_n`$ is the $`n`$th Tribonacci number, defined by $`T_0=0`$, $`T_1=T_2=1`$, and $`T_n=T_{n1}+T_{n2}+T_{n3}`$ for $`n3`$. Mansour also expressed \[23, Thm. 1\] the ordinary generating function for $`|S_n(123,132,\tau )|`$ as a determinant for a large class of permutations $`\tau S_k(123,132)`$. Using this result, Mansour showed that

$$|S_n(123,132,3241)|=F_{n+2}1(n1)$$

and

$$|S_n(123,132,3214)|=T_{n+1}(n1).$$

In this paper we begin by using Mansour’s determinant formula \[23, Thm. 3\] to show that if $`a`$, $`b`$, and $`c`$ are nonnegative integers with $`b1`$ and $`a+c1`$ then

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,213,\beta _{a,b,c})|x^n=\frac{(1x)^{a+c}+x^b\left(\underset{i=0}{\overset{a+c1}{}}(1x)^ix^{a+ci+1}\right)}{(1x)^{a+c}(1x\mathrm{}x^{b1})},$$

where $`\beta _{a,b,c}`$ is the permutation in $`S_{a+b+c}`$ given by

$$\beta _{a,b,c}=a+b+c,a+b+c1,\mathrm{},b+c+1,c+1,c+2,\mathrm{},b+c,c,c1,\mathrm{},2,1.$$

We go on to give a bijective proof that for $`n1`$,

$$|S_n(132,213,\beta _{a,b,c})|=\underset{k=1}{\overset{a+c1}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)+\underset{k=a+c}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{k1}{a+c1}\right)F_{b1,nk+1}.$$

We then turn our attention to some of those permutations $`\gamma S_n(123,132)`$ to which Mansour’s determinant formula \[23, Thm. 1\] does not apply. For all nonnegative integers $`a`$, $`b`$, and $`c`$, we give recurrence relations for the generating function for $`|S_n(123,132,\gamma _{a,b,c})|`$, where $`\gamma _{a,b,c}`$ is the permutation in $`S_{a+b+c+1}`$ given by

$$\gamma _{a,b,c}=a+b+c+1,a+b+c,\mathrm{},b+c+2,b+c,b+c1,\mathrm{},c+1,b+c+1,c,c1,\mathrm{},2,1.$$

Using these relations, we show that for all $`n3`$ and all $`b3`$,

$$|S_n(132,123,\gamma _{0,2,2})|=F_{n+2}+F_n3$$
(2)
and

$$|S_n(132,123,\gamma _{0,b,2})|=\left(\frac{1}{b1}\right)\left(3F_{b,n+1}+(b4)F_{b,n1}+3\underset{i=3}{\overset{b1}{}}(bi)F_{b,ni+1}3\right).$$
(3)
We give several other explicit enumerations; for instance, we show that for all $`n3`$,

$$|S_n(132,123,\gamma _{1,2,2})|=F_{n+3}+F_{n+1}3n+2$$

and for all $`n5`$,

$$|S_n(132,123,\gamma _{2,2,2})|=5F_{n+1}9n+21.$$

We give bijective proofs of (2) and (3). We also enumerate $`S_n(132,123,\gamma _{1,b,1})`$ for all $`b2`$, obtaining a sum of $`b`$-generalized Fibonacci numbers plus a polynomial of degree one in $`n`$. Finding a bijective proof of these enumerations is an open problem.

Next we prove two generalizations of Simion and Schmidt’s result (1) which are not related to Mansour’s determinant formulas. For all $`k4`$, we give a recurrence relation for the generating function for $`|S_n(132,2341,\omega _k)|`$, where $`\omega _k`$ is the permutation in $`S_k`$ given by

$$\omega _k=k,k1,\mathrm{},4,2,1,3.$$

Using this relation we give several explicit enumerations. For example, we show that for all $`n2`$,

$$|S_n(132,2341,\omega _4)|=F_{n+5}\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)2\left(\genfrac{}{}{0pt}{}{n+1}{1}\right)2.$$

For all nonnegative integers $`a`$ and $`b`$, we give recurrence relations for the generating function for $`|S_n(132,3241,\mu _{a,b})|`$, where $`\mu _{a,b}`$ is the permutation in $`S_{a+b}`$ given by

$$\mu _{a,b}=b+a,b+a1,\mathrm{},b+1,1,2,\mathrm{},b.$$

Using these relations we give several explicit enumerations. For example, we show that for all $`n1`$,

$$|S_n(132,3241,\mu _{2,3})|=F_{n+8}\left(\genfrac{}{}{0pt}{}{n+1}{4}\right)3\left(\genfrac{}{}{0pt}{}{n+1}{3}\right)4\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)9\left(\genfrac{}{}{0pt}{}{n+1}{1}\right)11.$$

It is an open problem to find bijective proofs of these enumerations.

We conclude our main results by expanding our point of view to include all sequences which satisfy a linear homogeneous recurrence relation with constant coefficients, instead of restricting our attention to those sequences whose terms can be expressed in terms of Fibonacci numbers or $`k`$-generalized Fibonacci numbers. More specifically, let $`k`$ and $`l`$ denote positive integers such that $`lk`$ and let $`a_1,\mathrm{},a_l`$ denote a sequence of positive integers in which $`a_1,\mathrm{},a_{l1}`$ are distinct. For a certain set $`R_{a_1,\mathrm{},a_l}^kS_k`$, we show that for all $`nk`$,

$$|S_n(R_{a_1,\mathrm{},a_k}^k)|=\underset{j=1}{\overset{l}{}}(ka_j\eta _j)|S_{nj}(R_{a_1,\mathrm{},a_l}^k)|,$$

where $`\eta _j=\{i|a_i>a_j\text{and}i<j\}`$ for $`1jl`$. (See section 7 for a precise definition of $`R_{a_1,\mathrm{},a_l}^k`$.) This result includes Simion and Schmidt’s result (1) as a special case, and we give several other examples of specific enumerations which arise from this result. Among these examples is an infinite family of enumerations involving the Fibonacci numbers.

## 2 Background and Notation

Let $`S_n`$ denote the set of permutations of $`[n]=\{1,\mathrm{},n\}`$, written in one-line notation, and suppose $`\pi S_n`$ and $`\sigma S_k`$. We say a permutation $`\pi `$ avoids a permutation $`\sigma `$ whenever $`\pi `$ contains no subsequence with all of the same pairwise comparisons as $`\sigma `$. For example, the permutation 214538769 avoids 312 and 2413, but it has 2586 as a subsequence so it does not avoid 1243. We make this idea precise in the following definition.

###### Definition 2.1

For any permutation $`\pi S_n`$ and any $`i`$ $`(1in)`$, we write $`\pi (i)`$ to denote the element of $`\pi `$ in position $`i`$. We say a permutation $`\pi S_n`$ avoids a permutation $`\sigma S_k`$ whenever there is no sequence $`1i_{\sigma (1)}<i_{\sigma (2)}<\mathrm{}<i_{\sigma (k)}n`$ such that $`\pi (i_1)<\pi (i_2)<\mathrm{}<\pi (i_k)`$.

If $`\pi `$ avoids $`\sigma `$ then $`\pi `$ is sometimes called a restricted permutation or a pattern-avoiding permutation and $`\sigma `$ is sometimes called a forbidden subsequence. In this paper we will be interested in permutations which avoid several patterns, so for any set $`R`$ of permutations we write $`S_n(R)`$ to denote the elements of $`S_n`$ which avoid every element of $`R`$. For any set $`R`$ of permutations we take $`S_n(R)`$ to be the empty set whenever $`n<0`$ and we take $`S_0(R)`$ to be the set containing only the empty permutation. When $`R=\{\pi _1,\pi _2,\mathrm{},\pi _r\}`$ we often write $`S_n(R)=S_n(\pi _1,\pi _2,\mathrm{},\pi _r)`$.

For all integers $`k1`$, the $`k`$-generalized Fibonacci number $`F_{k,n}`$ satisfies the recurrence obtained by adding more terms to the recurrence for the Fibonacci numbers. More specifically, we set $`F_{k,n}=0`$ for all $`n0`$ and we set $`F_{k,1}=1`$. For all $`n2`$ we define $`F_{k,n}`$ recursively by setting

$$F_{k,n}=\underset{i=1}{\overset{k}{}}F_{k,ni}(n2).$$
(4)
The term “$`k`$-generalized Fibonacci number” alludes to the fact that $`F_{2,n}=F_n`$ for all $`n`$. It is routine to verify that the ordinary generating function for $`F_{k,n}`$ is given by

$$\underset{n=0}{\overset{\mathrm{}}{}}F_{k,n}x^n=\frac{x}{1xx^2\mathrm{}x^k}(k1).$$
(5)
We will also make use of the following combinatorial interpretation of $`F_{k,n}`$.

###### Proposition 2.2

The number of tilings of a $`1\times n`$ rectangle with tiles of size $`1\times 1`$, $`1\times 2`$, …, $`1\times k`$ is the $`k`$-generalized Fibonacci number $`F_{k,n+1}`$.

Proof.  The result is immediate for $`n1`$, so it suffices to show that the number of such tilings satisfies (4). To do this, observe there is a one-to-one correspondence between tilings of a $`1\times (ni)`$ rectangle and tilings of a $`1\times n`$ rectangle in which the rightmost tile has length $`i`$. Therefore, if we count tilings of a $`1\times n`$ rectangle according to the length of the rightmost tile, we find the number of such tilings satisfies (4), as desired. $`\mathrm{}`$

For more information concerning the $`k`$-generalized Fibonacci numbers, see , , , , and .

## 3 Generalizations of Simion and Schmidt Involving 132 and 213

In this section we generalize Simion and Schmidt’s result (1) by replacing 123 with a longer permutation. One natural way to do this is to replace 123 with $`123\mathrm{}k`$ for some $`k4`$. We go further, however, replacing 123 with the permutation given in the following definition.

###### Definition 3.1

For all positive integers $`k`$, $`m`$, and $`r_0,\mathrm{},r_m`$ such that $`k+1=r_0>r_1>\mathrm{}>r_m=1`$, we write $`\tau _{r_0,\mathrm{},r_m}`$ to denote the permutation in $`S_k`$ given by

$$\tau _{r_0,\mathrm{},r_m}=r_1,r_1+1,\mathrm{},k,r_2,r_2+1,\mathrm{},r_11,\mathrm{},1,2,\mathrm{}r_{m1}1.$$

In this section we consider $`|S_n(132,213,\tau _{r_0,\mathrm{},r_m})|`$ for certain sequences $`r_0>r_1>\mathrm{}>r_m`$. Since $`\tau _{4,1}=123`$, these results generalize Simion and Schmidt’s result (1). We begin with a result of Mansour concerning the ordinary generating function for $`|S_n(132,213,\tau _{r_0,\mathrm{},r_m})|`$.

###### Theorem 3.2

(\[23, Thm. 3\]) Fix positive integers $`k,m`$, and $`r_0,\mathrm{},r_m`$ such that $`k+1=r_0>r_1>\mathrm{}>r_m=1`$ and let $`\tau _{r_0,\mathrm{},r_m}`$ be as in Definition 3.1. Then

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,213,\tau _{r_0,\mathrm{},r_m})|x^n=det\left(\begin{array}{ccccc}f_{r_0r_1}& g_{r_0r_1}& 0& \mathrm{}& 0\\ f_{r_1r_2}& 1& g_{r_1r_2}& \mathrm{}& 0\\ f_{r_2r_3}& 0& 1& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& g_{r_{m2}r_{m1}}\\ f_{r_{m1}r_m}& 0& 0& \mathrm{}& 1\end{array}\right)$$
(6)
where $`f_i(x)={\displaystyle \frac{1x}{12x+x^i}}`$ and $`g_i(x)={\displaystyle \frac{x^i}{12x+x^i}}`$ for $`i0`$.

In  Mansour focuses on the case of this theorem in which $`k=4`$. Here we use the result to give explicit enumerations involving Fibonacci numbers and $`k`$-generalized Fibonacci numbers. Many such enumerations can be obtained from this theorem; we consider just a few of them. We begin by considering the case in which 123 is replaced with its most natural lengthening, $`12\mathrm{}k`$.

###### Corollary 3.3

For all integers $`n`$ and all $`k2`$,

$$|S_n(12\mathrm{}k,132,213)|=F_{k1,n+1}.$$
(7)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(12\mathrm{}k,132,213)|x^n=\frac{1}{1xx^2\mathrm{}x^{k1}}.$$
(8)
Proof.  Since $`12\mathrm{}k=\tau _{k+1,1}`$, we set $`m=1`$ and $`r_1=1`$ in (6) to obtain (8). Line (7) is immediate from (8), in view of (5). $`\mathrm{}`$

Throughout this section we will give bijective proofs of our explicit enumerations. All of these proofs are based on a certain constructive bijection between $`S_n(132,213)`$ and the set of tilings of a $`1\times n`$ rectangle with tiles of size $`1\times i`$, where $`i1`$. To describe this bijection, we first make an observation concerning the form of a permutation in $`S_n(132,213)`$.

###### Proposition 3.4

Fix $`n0`$ and suppose $`\pi S_n`$. Then $`\pi S_n(132,213)`$ if and only if there exists a positive integer $`m`$ and a sequence $`n+1=r_0>r_1>\mathrm{}>r_m=1`$ such that $`\pi =\tau _{r_0,r_1,\mathrm{},r_m}`$.

Proof.  It is routine to verify that $`\tau _{r_0,r_1,\mathrm{},r_m}`$ avoids 132 and 213. To prove the converse, suppose $`\pi S_n(132,213)`$. Since $`\pi `$ avoids 132, every element to the left of $`n`$ in $`\pi `$ is larger than every element to the right of $`n`$. Since $`\pi `$ avoids 213, the elements to the left of $`n`$ are in increasing order, so there exists $`r_1`$ such that $`\pi =r_1,r_1+1,\mathrm{},n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{r_11}(132,213)`$. By induction on $`n`$ there exists a positive integer $`m`$ and a sequence $`n+1=r_0>r_1>\mathrm{}>r_m=1`$ such that $`\pi =\tau _{r_0,\mathrm{},r_m}`$, as desired. $`\mathrm{}`$

We now describe our bijection between $`S_n(132,213)`$ and the set of tilings of a $`1\times n`$ rectangle with tiles of size $`1\times i`$, where $`i1`$.

###### Definition 3.5

For all $`n0`$, we write $`_n`$ to denote the map from $`S_n(132,213)`$ to the set of tilings of a $`1\times n`$ rectangle with tiles of size $`1\times i`$, where $`i1`$, for which $`_n(\tau _{r_0,\mathrm{},r_m})`$ is the tiling whose tiles, when read from left to right, have sizes $`1\times (r_0r_1),1\times (r_1r_2),\mathrm{},1\times (r_{m1}r_m)`$.

###### Example 3.6

We have

$$_9(978652341)=\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$

and

$$_8(56782341)=\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}.$$

###### Proposition 3.7

For all $`n0`$, the map $`_n`$ is a constructive bijection between $`S_n(132,213)`$ to the set of tilings of a $`1\times n`$ rectangle with tiles of size $`1\times i`$, where $`i1`$.

Proof.  To show $`_n`$ is a bijection, we construct $`_n^1`$. To do this, let $`G_n`$ denote the map from the set of tilings of a $`1\times n`$ rectangle with tiles of size $`1\times i`$, where $`i1`$, to $`S_n(132,213)`$, which is given as follows. For a given tiling, fill the rightmost tile with the numbers $`1,2,\mathrm{}`$ from left to right, up to the length of the tile. Fill the tile immediately to the left of the rightmost tile from left to right in the same way, beginning with the smallest available number. Repeat this process until every tile is filled. It is routine to verify that $`_n(G_n(\mu ))=\mu `$ for any tiling $`\mu `$, and that $`G_n(_n(\pi ))=\pi `$ for any $`\pi S_n(132,213)`$. Therefore $`G_n=_n^1`$, so $`_n`$ is a bijection, as desired. $`\mathrm{}`$

The function $`_n`$ gives us a bijective proof of (7).

###### Theorem 3.8

For all $`n1`$ and all $`k2`$, the restriction of $`_n`$ to the set
$`S_n(12\mathrm{}k,132,213)`$ is a bijection between $`S_n(12\mathrm{}k,132,213)`$ and the set of tilings of a $`1\times n`$ rectangle with tiles of size $`1\times 1`$, $`1\times 2`$, …, $`1\times (k1)`$.

Proof.  Observe that $`\tau _{r_0,\mathrm{},r_m}`$ avoids $`12\mathrm{}k`$ if and only if $`r_{i1}r_ik1`$ for $`1im`$. Now the result is immediate from Propositions 3.4 and 3.7. $`\mathrm{}`$

Next we consider a more complicated lengthening of 123, in which we increase every entry in $`12\mathrm{}k`$ by a fixed amount and then append a decreasing sequence to the result. This longer permutation is $`\tau _{s+t+2,s+1,s,\mathrm{},2,1}`$ for positive integers $`s`$ and $`t`$, but for notational convenience we abbreviate it as follows.

###### Definition 3.9

For all positive integers $`s`$ and $`t`$, we write $`\alpha _{s,t}`$ to denote the permutation in $`S_{s+t+1}`$ given by

$$\alpha _{s,t}=\tau _{s+t+2,s+1,s,s1,\mathrm{},2,1}.$$

###### Proposition 3.10

Let $`s`$ and $`t`$ denote positive integers. Then

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,213,\alpha _{s,t})|x^n=\frac{(1x)^s+x^{t+1}\left(\underset{i=0}{\overset{s1}{}}(1x)^ix^{si1}\right)}{(1x)^s(1x\mathrm{}x^t)}.$$
(9)
Proof.  In (6), set $`m=s+2`$, $`r_0=s+t+2`$, and $`r_i=s+2i`$ for $`1im1`$ to find

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,213,\alpha _{s,t})|x^n=det\left(\begin{array}{cccccc}f_{t+1}(x)& g_{t+1}(x)& 0& \mathrm{}& 0& 0\\ 1& 1& \frac{x}{1x}& \mathrm{}& 0& 0\\ 1& 0& 1& \mathrm{}& 0& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 1& 0& 0& \mathrm{}& 1& \frac{x}{1x}\\ 1& 0& 0& \mathrm{}& 0& 1\end{array}\right),$$

where the matrix on the right is $`s+1`$ by $`s+1`$. To evaluate this determinant, let

$$A_n(x)=det\left(\begin{array}{cccccc}f_{t+1}(x)& g_{t+1}(x)& 0& \mathrm{}& 0& 0\\ 1& 1& \frac{x}{1x}& \mathrm{}& 0& 0\\ 1& 0& 1& \mathrm{}& 0& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 1& 0& 0& \mathrm{}& 1& \frac{x}{1x}\\ 1& 0& 0& \mathrm{}& 0& 1\end{array}\right)(n2),$$

where the matrix on the right is $`n\times n`$. Expand this determinant along the bottom row to find

$$A_n(x)=A_{n1}(x)+g_{t+1}(x)\left(\frac{x}{1x}\right)^{n2}(n3).$$

Iterate this relation and use the fact that $`A_2(x)=f_{t+1}(x)+g_{t+1}(x)`$ to obtain

$$A_n(x)=f_{t+1}(x)+g_{t+1}(x)\underset{i=0}{\overset{n2}{}}\left(\frac{x}{1x}\right)^i(n2).$$

Since $`f_{t+1}(x)={\displaystyle \frac{1}{1x\mathrm{}x^t}}`$ and $`g_{t+1}(x)={\displaystyle \frac{x^{t+1}}{(1x)(1x\mathrm{}x^t)}}`$, we have

$$A_n(x)=\frac{(1x)^{n1}+x^{t+1}\underset{i=0}{\overset{n2}{}}x^i(1x)^{n2i}}{(1x)^{n1}(1x\mathrm{}x^t)}(n2).$$

Set $`n=s+1`$ in the last line to obtain (9), as desired. $`\mathrm{}`$

Rather than extract an explicit enumeration of $`S_n(132,213,\alpha _{s,t})`$ directly from (9), we use $`_n`$ to obtain one bijectively.

###### Theorem 3.11

Let $`s`$ and $`t`$ denote positive integers. Then the restriction of $`_n`$ to the set $`S_n(132,213,\alpha _{s,t})`$ is a constructive bijection between $`S_n(132,213,\alpha _{s,t})`$ and the set of tilings of a $`1\times n`$ rectangle in which all tiles except for the rightmost $`s`$ tiles have length at most $`t`$. In particular, for all $`n1`$,

$$|S_n(132,213,\alpha _{s,t})|=\underset{k=1}{\overset{s1}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)+\underset{k=s}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{k1}{s1}\right)F_{t,nk+1}.$$
(10)
Proof.  In view of Propositions 3.4 and 3.7, to prove the first part of the theorem it is sufficient to show that $`\tau _{r_0,\mathrm{},r_m}`$ avoids $`\alpha _{s,t}`$ if and only if $`r_{i1}r_i<t+1`$ for $`1ims`$. It is routine to verify that if $`r_{i1}r_i<t+1`$ for $`1ims`$ then $`\tau _{r_0,\mathrm{},r_m}`$ avoids $`\alpha _{s,t}`$. To show the converse, observe that if there exists $`i`$ with $`1ims`$ and $`r_{i1}r_it+1`$ then the subsequence $`r_i,r_i+1,\mathrm{},r_{i1}1,r_{i+1},r_{i+2},\mathrm{},r_{i+s}`$ forms a pattern of type $`\alpha _{s,t}`$.

Line (10) follows from the first part of the theorem by a routine counting argument. $`\mathrm{}`$

We conclude this section by using (6) and $`_n`$ to obtain the following general result, which is analogous to Proposition 3.10 and Theorem 3.11. For notational convenience, in this result we abbreviate

$$\beta _{a,b,c}=\tau _{a+b+c+1,a+b+c,\mathrm{},b+c+1,c+1,c,\mathrm{},2,1}$$

for all nonnegative integers $`a,b,`$ and $`c`$ such that $`a+c1`$ and $`b1`$.

###### Theorem 3.12

Let $`a`$ and $`c`$ denote nonnegative integers such that $`a+c1`$ and let $`b`$ denote a positive integer. Then the restriction of $`_n`$ to the set $`S_n(132,213,\beta _{a,b,c})`$ is a constructive bijection between $`S_n(132,213,\beta _{a,b,c})`$ and the set of tilings of a $`1\times n`$ rectangle in which all tiles except for the leftmost $`a`$ tiles and the rightmost $`c`$ tiles have length at most $`b1`$. In particular, for $`n1`$,

$$|S_n(132,213,\beta _{a,b,c})|=\underset{k=1}{\overset{a+c1}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)+\underset{k=a+c}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{k1}{a+c1}\right)F_{b1,nk+1}.$$
(11)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,213,\beta _{a,b,c})|x^n=\frac{(1x)^{a+c}+x^b\left(\underset{i=0}{\overset{a+c1}{}}(1x)^ix^{a+ci+1}\right)}{(1x)^{a+c}(1x\mathrm{}x^{b1})}.$$
(12)
Proof.  In view of Propositions 3.4 and 3.7, to prove the first part of the theorem it is sufficient to show that $`\tau _{r_0,\mathrm{},r_m}`$ avoids $`\beta _{a,b,c}`$ if and only if $`r_{i1}r_i<b`$ for $`a+1imc`$. It is routine to verify that if $`r_{i1}r_i<b`$ for $`a+1imc`$ then $`\tau _{r_0,\mathrm{},r_m}`$ avoids $`\beta _{a,b,c}`$. To show the converse, observe that if there exists $`i`$ with $`a+1imc`$ and $`r_{i1}r_ib`$ then the subsequence

$$r_1,r_2,\mathrm{},r_a,r_i,r_i+1,\mathrm{},r_i+b1,r_{mc}+1,r_{mc}+2,\mathrm{},r_m$$

forms a pattern of type $`\beta _{a,b,c}`$. It follows that $`\tau _{r_0,\mathrm{},r_m}`$ avoids $`\beta _{a,b,c}`$ if and only if $`r_{i1}r_i<b`$ for $`a+1imc`$, so the first part of the theorem holds.

Line (11) follows from the first part of the theorem by a routine counting argument.

To obtain (12), observe that if we set $`s=a+c`$ and $`t=b1`$ in the expression on the right side of (10) then we obtain the expression on the right side of (11). Therefore, in view of (9), line (12) follows from (11). $`\mathrm{}`$

## 4 Generalizations of Simion and Schmidt Involving 123 and 132

In section 3 we generalized Simion and Schmidt’s result (1) by replacing 123 with a longer permutation. In this section we generalize (1) by replacing 213 with a longer permutation. The generalizations we obtain in this way are equivalent to those we would obtain by replacing 132 with a longer permutation, since 132 is the image of 213 under the reverse-complement map and 123 is fixed by this map. We begin by setting some notation.

###### Definition 4.1

For all nonnegative integers $`a`$, $`b`$, and $`c`$, we write $`\gamma _{a,b,c}`$ to denote the permutation in $`S_{a+b+c+1}`$ given by

$$\gamma _{a,b,c}=a+b+c+1,a+b+c,\mathrm{},b+c+2,b+c,b+c1,\mathrm{},c+1,b+c+1,c,c1,\mathrm{},2,1$$

We write $`f_{a,b,c}(x)`$ to denote the generating function

$$f_{a,b,c}(x)=\underset{n=0}{\overset{\mathrm{}}{}}|S_n(123,132,\gamma _{a,b,c})|x^n.$$

In this section we give a recursive formula for $`f_{a,b,c}(x)`$, which we use to give explicit enumerations of $`S_n(123,132,\gamma _{a,b,c})`$ for certain values of $`a`$, $`b`$, and $`c`$. Since $`\gamma _{0,2,0}=213`$, these results generalize Simion and Schmidt’s result (1). We begin by considering the case in which $`a=b=0`$.

###### Proposition 4.2

Let $`c`$ denote a positive integer. Then $`f_{0,0,0}(x)=1`$ and

$$f_{0,0,c}(x)=1+xf_{0,0,c1}(x)+\underset{r=2}{\overset{c+1}{}}x^rf_{0,0,cr+1}(x).$$
(13)
Proof.  To see that $`f_{0,0,0}(x)=1`$, first observe that $`\gamma _{0,0,0}=1`$. Since the empty permutation is the only permutation (of any length) which avoids $`1`$, we have $`f_{0,0,0}(x)=1`$.

To prove (13), first observe that the empty permutation avoids 123, 132, and $`\gamma _{0,0,c}`$. For $`n1`$, observe that every permutation $`\pi S_n(123,132,\gamma _{0,0,c})`$ for which $`\pi (1)=n`$ has the form $`n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_n(123,132,\gamma _{0,0,c})`$, and the resulting map is a bijection between $`S_n(123,132,\gamma _{0,0,c})`$ and the set of permutations in $`S_n(123,132,\gamma _{0,0,c})`$ which begin with $`n`$. Similarly, observe that if $`2i<n`$ then every permutation $`\pi S_n(123,132,\gamma _{0,0,c})`$ for which $`\pi (i)=n`$ has the form $`n1,n2,\mathrm{},ni+1,n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(123,132,\gamma _{0,0,ci+1})`$, and the resulting map is a bijection between $`S_{ni}(123,132,\gamma _{0,0,ci+1})`$ and the set of permutations in $`S_n(123,132,\gamma _{0,0,c})`$ in which $`n`$ is in the $`i`$th position. Combine these observations to obtain (13). $`\mathrm{}`$

We now consider $`f_{0,b,0}(x)`$.

###### Proposition 4.3

For any positive integer $`b`$,

$$f_{0,b,0}(x)=\frac{1}{1x\mathrm{}x^b}.$$
(14)
In particular,

$$|S_n(123,132,\gamma _{0,b,0})|=F_{b,n+1}(n1).$$
(15)
Proof.  Line (14) is immediate from \[23, Thm. 1\], but for completeness we include a proof here.

First observe that the empty permutation avoids 123, 132, and $`\gamma _{0,b,0}`$. Now observe that for $`1ib`$, every permutation $`\pi S_n(123,132,\gamma _{0,b,0})`$ with $`\pi (i)=n`$ has the form $`n1,n2,\mathrm{},ni+1,n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(123,132,\gamma _{0,b,0})`$, and the resulting map is a bijection between $`S_{ni}(123,132,\gamma _{0,b,0})`$ and the set of permutations in $`S_n(123,132,\gamma _{0,b,0})`$ in which $`n`$ is in the $`i`$th position. Finally, observe that if $`\pi `$ avoids 123 and 132 and has $`\pi (i)=n`$ for $`b+1in`$ then $`\pi `$ does not avoid $`\gamma _{0,b,0}`$. Combine these observations to obtain

$$f_{0,b,0}(x)=1+f_{0,b,0}(x)\underset{r=1}{\overset{b}{}}x^r.$$

Solve this equation for $`f_{0,b,0}(x)`$ to obtain (14).

Line (15) is immediate from (14), in view of (5). $`\mathrm{}`$

We also give a bijective proof of (15).

###### Theorem 4.4

For all $`n1`$ and all $`b2`$ there exists a constructive bijection between $`S_n(123,132,\gamma _{0,b,0})`$ and the set of tilings of a $`1\times n`$ rectangle with tiles of size $`1\times 1`$, $`1\times 2`$, …, $`1\times b`$.

Proof.  Suppose we are given such a tiling. We construct its corresponding permutation as follows. Let $`m`$ denote the length of the rightmost tile. Fill this tile with the numbers $`1,2,\mathrm{},m`$ from left to right in the order $`m1,m2,\mathrm{},1,m`$. Fill the tile immediately to the left of the rightmost tile in the same way, using the smallest available numbers. Repeat this process until every tile is filled. It is routine to verify that this map is invertible, and that the permutation constructed avoids 123, 132, and $`\gamma _{0,b,0}`$. $`\mathrm{}`$

###### Example 4.5

Under the bijection given in the proof of Theorem 4.4, the permutation
876954231 corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$ and the permutation 986743512 corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$.

We now find $`f_{0,b,c}(x)`$ in terms of $`f_{0,0,c}(x)`$.

###### Proposition 4.6

For any positive integers $`b`$ and $`c`$,

$$f_{0,b,c}(x)=\frac{1x+x^{b+1}f_{0,0,c1}(x)}{(1x)(1x\mathrm{}x^b)}.$$
(16)
Proof.  First observe that the empty permutation avoids 123, 132, and $`\gamma _{0,b,c}`$. Now observe that for $`1ib`$, every permutation $`\pi S_n(123,132,\gamma _{0,b,c})`$ with $`\pi (i)=n`$ has the form $`n1,n2,\mathrm{},ni+1,n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(123,132,\gamma _{0,b,c})`$, and the resulting map is a bijection between $`S_{ni}(123,132,\gamma _{0,b,c})`$ and the set of permutations in $`S_n(123,132,\gamma _{0,b,c})`$ in which $`n`$ is in the $`i`$th position. Similarly, observe that for $`b+1in`$, every permutation $`\pi S_n(123,132,\gamma _{0,b,c})`$ with $`\pi (i)=n`$ has the form $`n1,n2,\mathrm{},ni+1,n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(123,132,\gamma _{0,0,c1})`$, and the resulting map is a bijection between $`S_{ni}(123,132,\gamma _{0,0,c1})`$ and the set of permutations in $`S_n(123,132,\gamma _{0,b,c})`$ in which $`n`$ is in the $`i`$th position. Combine these observations to find

$$f_{0,b,c}(x)=1+\underset{i=1}{\overset{b}{}}x^if_{0,b,c}(x)+\frac{x^{b+1}}{1x}f_{0,0,c1}(x).$$

Solve this equation for $`f_{0,b,c}(x)`$ to obtain (16). $`\mathrm{}`$

We now obtain our recurrence relation for $`f_{a,b,c}(x)`$.

###### Proposition 4.7

For any positive integers $`a`$ and $`b`$ and any nonnegative integer $`c`$,

$$f_{a,b,c}(x)=1+xf_{a1,b,c}(x)+\underset{r=2}{\overset{a}{}}x^rf_{ar+1,b,c}(x)+\frac{x^{a+1}}{1x}f_{0,b,c}(x).$$
(17)
Proof.  First observe that the empty permutation avoids 123, 132, and $`\gamma _{a,b,c}`$. Now observe that every permutation $`\pi S_n(123,132,\gamma _{a,b,c})`$ for which $`\pi (1)=n`$ has the form $`n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{n1}(123,132,\gamma _{a1,b,c})`$, and the resulting map is a bijection between $`S_{n1}(123,132,\gamma _{a1,b,c})`$ and the set permutations in $`S_n(123,132,\gamma _{a,b,c})`$ which begin with $`n`$. Similarly, observe that for $`2ia`$, every permutation $`\pi S_n(123,132,\gamma _{a,b,c})`$ with $`\pi (i)=n`$ has the form $`n1,n2,\mathrm{},ni+1,n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(123,132,\gamma _{ai+1,b,c})`$, and the resulting map is a bijection between $`S_{ni}(123,132,\gamma _{ai+1,b,c})`$ and the set of permutations in $`S_n(123,132,\gamma _{a,b,c})`$ in which $`n`$ is in the $`i`$th position. Finally, observe that for $`a+1in`$, every permutation $`\pi S_n(123,132,\gamma _{a,b,c})`$ for which $`\pi (i)=n`$ has the form $`n1,n2,\mathrm{},ni+1,n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(123,132,\gamma _{0,b,c})`$, and the resulting map is a bijection between $`S_{ni}(123,132,\gamma _{0,b,c})`$ and the set of permutations in $`S_n(123,132,\gamma _{a,b,c})`$ in which $`n`$ is in the $`i`$th position. Combine these observations to obtain (17). $`\mathrm{}`$

We now use our recurrence relations (13), (16), and (17) to obtain explicit enumerations of $`S_n(132,123,\gamma _{a,b,c})`$ for various values of $`a`$, $`b`$, and $`c`$. We begin with the case in which $`a=0`$, $`c=1`$, and $`b`$ is arbitrary.

###### Proposition 4.8

Let $`b`$ denote a positive integer. Then

$$|S_n(132,123,\gamma _{0,b,1})|=\underset{k=1}{\overset{n}{}}F_{b,k}(n1).$$
(18)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,123,\gamma _{0,b,1})|x^n=1+\frac{x}{12x+x^{b+1}}.$$
(19)
Proof.  To prove (19), set $`c=1`$ in (16), obtaining

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,123,\gamma _{0,b,1})|x^n=\frac{1x+x^{b+1}}{(1x)(1x\mathrm{}x^b)}=1+\frac{x}{12x+x^{b+1}},$$

as desired. To prove (18) observe that in view of (5),

$`{\displaystyle \frac{x}{12x+x^{b+1}}}`$ $`=`$ $`\left({\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}x^n\right)\left({\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}F_{b,n}x^n\right)`$
$`=`$ $`{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}\left({\displaystyle \underset{k=1}{\overset{n}{}}}F_{b,k}\right)x^n.`$
Now (18) is immediate from (19). $`\mathrm{}`$

Remark Line (19) is also immediate from \[23, Thm. 1\].

We also give a bijective proof of (18).

###### Theorem 4.9

Let $`b`$ denote a positive integer. There exists a constructive bijection between $`S_n(132,123,\gamma _{0,b,1})`$ and the set of tilings of a $`1\times (n+1)`$ rectangle with tiles of size $`1\times i`$ $`(i1)`$ in which all tiles except the rightmost tile have length at most $`b`$, and the rightmost tile has length at least 2.

Proof.  Suppose we are given such a tiling. We construct its corresponding permutation as follows. Let $`m`$ denote the length of the rightmost tile. Fill this tile with the numbers $`1,2,\mathrm{},m`$ from left to right in the order $`m2,m3,\mathrm{},1,m1`$, leaving the rightmost square empty. Fill the tile immediately to the left of the rightmost tile using the smallest available numbers and in the same pattern as the rightmost tile, but put a number in every square. Repeat this process until every square of every remaining tile is filled. It is routine to verify that this map is invertible, and that the permutation constructed avoids 123, 132, and $`\gamma _{0,b,1}`$. $`\mathrm{}`$

###### Example 4.10

Fix $`b=3`$. Under the bijection given in the proof of Theorem 4.9, the permutation 879653214 corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$ and the permutation $`976845231`$ corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$.

Next we enumerate $`S_n(132,123,\gamma _{a,b,c})`$ when $`a=0`$, $`c=2`$, and $`b`$ is arbitrary. We first consider the case in which $`b=2`$.

###### Proposition 4.11

For all $`n3`$,

$$|S_n(132,123,\gamma _{0,2,2})|=F_{n+2}+F_n3.$$
(20)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,123,\gamma _{0,2,2})|x^n=3+x+x^2+\frac{x^2+4x2}{12x+x^3}.$$
(21)
Proof.  To obtain (21), set $`c=2`$ in (16) and use (13) to obtain

$`{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}|S_n(132,123,\gamma _{0,2,2})|x^n`$ $`=`$ $`{\displaystyle \frac{1x+x^3+x^4+x^5}{(1x)(1xx^2)}}`$
$`=`$ $`3+x+x^2+{\displaystyle \frac{x^2+4x2}{12x+x^3}},`$
as desired. To obtain (20), observe that

$$\frac{x^2+4x2}{12x+x^3}=\frac{3}{1x}+\frac{2x+1}{1xx^2}.$$

Now (20) is immediate in view of (5). $`\mathrm{}`$

We now handle the case in which $`b3`$.

###### Proposition 4.12

Let $`b`$ denote a positive integer such that $`b3`$. Then for all $`n3`$,

$$|S_n(132,123,\gamma _{0,b,2})|=\left(\frac{1}{b1}\right)\left(3F_{b,n+1}+(b4)F_{b,n1}+3\underset{i=3}{\overset{b1}{}}(bi)F_{b,ni+1}3\right).$$
(22)
Alternatively, for all $`n3`$,

$$|S_n(132,123,\gamma _{0,b,2})|=\underset{k=1}{\overset{n1}{}}F_{b,k}+2\underset{k=1}{\overset{n2}{}}F_{b,k}.$$
(23)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,123,\gamma _{0,b,2})|x^n=1+x+x^2+\frac{x^2+2x^3}{12x+x^{b+1}}.$$
(24)
Proof.  To obtain (24), set $`c=2`$ in (16) and use (13) to obtain

$`{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}|S_n(132,123,\gamma _{0,b,2})|x^n`$ $`=`$ $`{\displaystyle \frac{1x+x^{b+1}+x^{b+2}+x^{b+3}}{(1x)(1x\mathrm{}x^b)}}`$
$`=`$ $`1+x+x^2+{\displaystyle \frac{x^2+2x^3}{12x+x^{b+1}}},`$
as desired. To obtain (22), observe that if $`b3`$ then

$$\frac{x^2+2x^3}{12x+x^{b+1}}=\left(\frac{1}{b1}\right)\left(\frac{3}{1x}+\frac{3+(b4)x^2+3\underset{i=3}{\overset{b1}{}}(bi)x^i}{1x\mathrm{}x^b}\right).$$

Now (22) is immediate in view of (5). To obtain (23), observe that

$`{\displaystyle \frac{x^2+2x^3}{(1x)(1x\mathrm{}x^b)}}`$ $`=`$ $`\left({\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}x^n\right)\left({\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}\left(F_{b,n1}+2F_{b,n2}\right)x^n\right)`$
$`=`$ $`{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}\left({\displaystyle \underset{k=0}{\overset{n1}{}}}F_{b,k}+2{\displaystyle \underset{k=0}{\overset{n2}{}}}F_{b,k}\right)x^n.`$
Now (23) is immediate in view of (5). $`\mathrm{}`$

We also give a bijective proof of (20) and (23).

###### Theorem 4.13

Let $`b2`$. For all $`n1`$, let $`B_n`$ denote the set of tilings of a $`1\times n`$ rectangle for which the following hold.

1. There is at most one tile with length greater than $`b`$; call this tile the long tile.
2. There is at most one tile to the right of the long tile.
3. The tile to the right of the long tile has length 1 or 2.

Then there exists a constructive bijection between $`B_n`$ and $`S_n(132,132,\gamma _{0,b,2})`$.

Proof.  Suppose we are given such a tiling. We construct its corresponding permutation as follows. Let $`m`$ denote the length of the rightmost tile. Fill this tile with the numbers $`1,2,\mathrm{},m`$ from left to right in the order $`m1,m2,\mathrm{},1,m`$. Fill the tile immediately to the left of the rightmost tile in the same way, using the smallest available numbers. Repeat this process until every tile is filled. It is routine to verify that this map is invertible, and that the permutation constructed avoids 132, 123, and $`\gamma _{0,b,2}`$. $`\mathrm{}`$

###### Example 4.14

Fix $`b=3`$. Under the bijection given in Theorem 4.13, the permutation 879643251 corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$, the permutation $`978643215`$ corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$, and the permutation $`6543712`$ corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$.

Next we enumerate $`S_n(132,123,\gamma _{a,b,c})`$ when $`a=1`$, $`c=1`$, and $`b`$ is arbitrary.

###### Proposition 4.15

Let $`b`$ denote a positive integer such that $`b2`$. Then for all $`n1`$,

$$|S_n(132,123,\gamma _{1,b,1})|=\left(\frac{1}{b1}\right)^2\left(\frac{b^23b}{2}+(1b)n+g_b(n)\right),$$
(25)
where

$$g_b(n)=\frac{b^2b+2}{2}F_{b,n+1}+(b1)F_{b,n}+\underset{i=2}{\overset{b1}{}}\left[(1b)\left(\genfrac{}{}{0pt}{}{i}{2}\right)+\frac{b^2b2}{2}i\frac{b^23b}{2}\right]F_{b,ni+1}.$$

Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,123,\gamma _{1,b,1})|x^n=\frac{12x+x^2+x^{b+1}}{(1x)^2(1x\mathrm{}x^b)}.$$
(26)
Proof.  To obtain (26), set $`a=c=1`$ in (17) and use (19) to obtain

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,123,\gamma _{1,b,1})|x^n=\frac{1}{1x}+\frac{x^2}{12x+x^{b+1}}+\frac{x^3}{13x+2x^2+x^{b+1}x^{b+2}}.$$

Now (26) is immediate. To obtain (25), first observe that

$$\frac{x^2}{12x+x^{b+1}}=\left(\frac{1}{b1}\right)\left(\frac{1}{1x}+\frac{1+\underset{i=2}{\overset{b1}{}}(bi)x^i}{1x\mathrm{}x^b}\right)$$

and

$$\frac{x^3}{13x+2x^2+x^{b+1}x^{b+2}}=\left(\frac{1}{b1}\right)^2\left(\frac{\left(\genfrac{}{}{0pt}{}{b2}{2}\right)}{1x}+\frac{1b}{(1x)^2}+\frac{h_b(x)}{1x\mathrm{}x^b}\right),$$

where

$$h_b(x)=\frac{b^23b+4}{2}+(b1)x+\underset{i=2}{\overset{b1}{}}\left[(i2)(b1)^2\left(\left(\genfrac{}{}{0pt}{}{i}{2}\right)1\right)(b1)(i1)\left(\genfrac{}{}{0pt}{}{b2}{2}\right)\right]x^i.$$

Now (25) is immediate in view of (5). $`\mathrm{}`$

We conclude this section with several other explicit enumerations of $`S_n(132,123,\gamma _{a,b,c})`$ for small values of $`a`$, $`b`$, and $`c`$.

###### Proposition 4.16

For all $`n3`$,

$$|S_n(132,123,\gamma _{1,2,2})|=F_{n+3}+F_{n+1}3n+2.$$
(27)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,123,\gamma _{1,2,2})|x^n=42xx^2+\frac{6x^3+4x^212x+5}{(1x)^2(1xx^2)}.$$
(28)
Proof.  To obtain (28), set $`a=1`$, $`b=2`$, and $`c=2`$ in (17) and use (21). To obtain (28), observe that

$$\frac{6x^3+4x^212x+5}{(1x)^2(1xx^2)}=\frac{5}{1x}\frac{3}{(1x)^2}+\frac{x+3}{1xx^2}.$$

Now (28) is immediate in view of (5). $`\mathrm{}`$

We omit the proofs of the remaining propositions in this section, since they are similar to the proof of Proposition 4.16.

###### Proposition 4.17

For all $`n5`$,

$$|S_n(132,123,\gamma _{2,2,2})|=5F_{n+1}9n+21.$$
(29)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,123,\gamma _{2,2,2})|x^n=2516x11x^25x^32x^4+\frac{30x^3+14x^261x+26}{(1x)^2(1xx^2)}.$$

###### Proposition 4.18

For all $`n7`$,

$$|S_n(132,123,\gamma _{3,2,2})|=3F_{n+2}+3F_n24n+91.$$
(30)
Moreover,

$`{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}|S_n(132,123,\gamma _{3,2,2})|x^n=`$
$`9375x53x^236x^320x^49x^52x^6+{\displaystyle \frac{121x^3+15x^2206x+94}{(1x)^2(1xx^2)}}.`$
###### Proposition 4.19

For all $`n3`$,

$$|S_n(132,123,\gamma _{1,3,2})|=\frac{1}{2}\left(F_{3,n+2}+2F_{3,n}+F_{3,n1}3n+5\right).$$
(31)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,123,\gamma _{1,3,2})|x^n=22xx^2+\frac{5x^4+x^36x+3}{(1x)^2(1xx^2x^3)}.$$

###### Proposition 4.20

For all $`n5`$,

$$|S_n(132,123,\gamma _{2,3,2})|=\frac{1}{2}\left(4F_{3,n+1}+F_{3,n}3F_{3,n1}9n+30\right).$$
(32)
Moreover,

$`{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}|S_n(132,123,\gamma _{2,3,2})|x^n=`$
$`1612x7x^25x^32x^4+{\displaystyle \frac{18x^4+8x^3+4x^238x+17}{(1x)^2(1xx^2x^3)}}.`$
###### Proposition 4.21

For all $`n7`$,

$$|S_n(132,123,\gamma _{3,3,2})|=\frac{1}{2}\left(3F_{3,n}+10F_{3,n1}3F_{3,n2}24n+115\right).$$
(33)
Moreover,

$`{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}|S_n(132,123,\gamma _{3,3,2})|x^n=`$
$`5546x38x^224x^316x^49x^52x^6+{\displaystyle \frac{76x^4+2x^3+11x^2121x+56}{(1x)^2(1xx^2x^3)}}.`$
## 5 Generalizations of Simion and Schmidt Involving Two Longer Permutations

In sections 3 and 4 we generalized Simion and Schmidt’s result (1) by replacing one of the three forbidden subsequences with a longer forbidden subsequence. In this section we generalize (1) by replacing two of the forbidden subsequences with longer forbidden subsequences in several ways. We begin by setting some notation.

###### Definition 5.1

For all $`k4`$, we write $`\omega _k`$ to denote the permutation in $`S_k`$ given by

$$\omega _k=k,k1,\mathrm{},5,4,2,1,3,$$

and we write $`g_k(x)`$ to denote the generating function

$$g_k(x)=\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,2341,\omega _k)|x^n.$$

As in the previous section, we give a recurrence relation for $`g_k(x)`$.

###### Proposition 5.2

We have

$$g_3(x)=\frac{x^3x+1}{(1x)(1xx^2)}.$$
(34)
Moreover, for all $`k>3`$,

$$g_k(x)=\left(\frac{1}{1x}\right)\left(1+x(g_{k1}(x)1)+\underset{r=2}{\overset{k2}{}}x^r(g_{kr+1}(x)1)+\frac{x^{k1}}{1x}(g_3(x)1)\right).$$
(35)
Proof.  Using the notation of section 3, observe that $`\omega _3=213`$ and $`\tau _{5,2,1}=2341`$. Now (34) is immediate from (6).

To obtain (35), first observe that the empty permutation avoids 132, 2341, and $`\omega _k`$. For $`n1`$, observe that every permutation $`\pi S_n(132,2341,\omega _k)`$ for which $`\pi (n)=n`$ has the form $`\stackrel{~}{\pi },n`$, where $`\stackrel{~}{\pi }S_{n1}(132,2341,\omega _k)`$, and the resulting map is a bijection between $`S_{n1}(132,2341,\omega _k)`$ and the set of permutations in $`S_n(132,2341,\omega _k)`$ which end with $`n`$. Similarly, observe that if $`1ik2`$ and $`i<n`$ then every permutation $`\pi S_n(132,2341,\omega _k)`$ with $`\pi (i)=n`$ has the form $`n1,n2,\mathrm{},ni+1,n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(132,2341,\omega _{ki+1})`$, and the resulting map is a bijection between $`S_{ni}(132,2341,\omega _{ki+1})`$ and the set of permutations in $`S_n(132,2341,\omega _k)`$ in which $`n`$ is in the $`i`$th position. Finally, observe that if $`k1in1`$ then every permutation $`\pi S_n(132,2341,\omega _k)`$ with $`\pi (i)=n`$ has the form $`n1,n2,\mathrm{},ni+1,n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(132,2341,\omega _3)`$, and the resulting map is a bijection between $`S_{ni}(132,2341,\omega _3)`$ and the set of permutations in $`S_n(132,2341,\omega _k)`$ in which $`n`$ is in the $`i`$th position. Combine these observations to find

$$g_k(x)=1+xg_k(x)+x(g_{k1}(x)1)+\underset{r=2}{\overset{k2}{}}x^r(g_{kr+1}(x)1)+\frac{x^{k1}}{1x}\left(g_3(x)1\right).$$

Solve this equation for $`g_k(x)`$ to obtain (35). $`\mathrm{}`$

We now use (34) and (35) to obtain explicit enumerations of $`S_n(132,2341,\omega _k)`$ for $`k6`$. We will use the following identities, whose proofs we omit.

$$\underset{n=0}{\overset{\mathrm{}}{}}F_{n+k}x^n=\frac{F_{k1}x+F_k}{1xx^2}(k2)$$
(36)
$$\underset{n=0}{\overset{\mathrm{}}{}}\left(\genfrac{}{}{0pt}{}{n+1}{k}\right)x^n=\frac{x^{max(k1,0)}}{(1x)^{k+1}}(k0)$$
(37)
We begin with $`S_n(132,2341,\omega _3)`$.

###### Proposition 5.3

For all $`n1`$,

$$|S_n(132,2341,\omega _3)|=F_{n+2}1.$$
(38)
Proof.  This result is proved in , but for completeness we give a proof here. Observe that

$$g_3(x)=1\frac{1}{1x}+\frac{F_1x+F_2}{1xx^2}.$$

Now (38) is immediate from (36) and (37). $`\mathrm{}`$

We also give a bijective proof of (38).

###### Theorem 5.4

For all $`n1`$, there exists a constructive bijection between $`S_n(132,213,2341)`$ and the set of tilings of a $`1\times (n+1)`$ rectangle with tiles of size $`1\times 1`$ and $`1\times 2`$ using at least one $`1\times 2`$ tile.

Proof.  Suppose we are given such a tiling. We construct its corresponding permutation as follows. Replace the rightmost $`1\times 2`$ tile with a 1, and fill the (necessarily $`1\times 1`$) tiles to the right of the 1 with $`2,3,\mathrm{}`$ from left to right. Now fill the rightmost empty tile with the smallest numbers available, placing them in the tile from left to right in increasing order. Repeat this process until every tile is filled. It is routine to verify that this map is invertible, and that the permutation constructed avoids 132, 213, and 2341, as desired. $`\mathrm{}`$

###### Example 5.5

Under the bijection given in the proof of Theorem 5.4, the permutation
87564123 corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$ and the permutation 86745321 corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$.

###### Proposition 5.6

For all $`n1`$,

$$|S_n(132,2341,\omega _4)|=F_{n+5}\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)2\left(\genfrac{}{}{0pt}{}{n+1}{1}\right)2.$$
(39)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,2341,\omega _4)|=\frac{13x+3x^2+x^3x^4}{(1xx^2)(1x)^3}.$$
(40)
Proof.  To obtain (40), set $`k=4`$ in (35) and use (34) to simplify the result. To obtain (39), observe that

$$\frac{x^4x^33x^2+3x1}{(x^2+x1)(1x)^3}=\frac{F_4x+F_5}{1xx^2}\frac{2}{1x}\frac{2}{(1x)^2}\frac{x}{(1x)^3}.$$

Now (39) is immediate from (36) and (37). $`\mathrm{}`$

We omit the proofs of the next two propositions, since they are similar to the proof of Proposition 5.6.

###### Proposition 5.7

For all $`n2`$,

$$|S_n(132,2341,\omega _5)|=3F_{n+5}2\left(\genfrac{}{}{0pt}{}{n+1}{3}\right)4\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)3\left(\genfrac{}{}{0pt}{}{n+1}{1}\right)14.$$
(41)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,2341,\omega _5)|x^n=\frac{14x+6x^22x^3x^4+3x^5x^7}{(1xx^2)(1x)^4}.$$

###### Proposition 5.8

For all $`n2`$,

$$|S_n(132,2341,\omega _6)|=5F_{n+6}+F_{n+4}4\left(\genfrac{}{}{0pt}{}{n+1}{4}\right)7\left(\genfrac{}{}{0pt}{}{n+1}{3}\right)5\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)27\left(\genfrac{}{}{0pt}{}{n+1}{1}\right)8.$$
(42)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,2341,\omega _k)|x^n=\frac{15x+10x^28x^3+x^4+5x^5+x^6+x^72x^8}{(1xx^2)(1x)^5}.$$

We now consider another way of replacing two of the forbidden subsequences in Simion and Schmidt’s result (1) with longer permutations. We begin by setting some notation.

###### Definition 5.9

For all nonnegative integers $`a`$ and $`b`$ we write $`\mu _{a,b}`$ to denote the permutation in $`S_{a+b}`$ given by

$$\mu _{a,b}=b+a,b+a1,\mathrm{},b+1,1,2,\mathrm{},b$$

and we write $`h_{a,b}(x)`$ to denote the generating function

$$h_{a,b}(x)=\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,3241,\mu _{a,b})|x^n.$$

We now give a recurrence relation for $`h_{0,b}(x)`$.

###### Proposition 5.10

Let $`b`$ denote a positive integer. Then

$$h_{0,1}(x)=1$$
(43)
and if $`b2`$ then

$$h_{0,b}(x)=1+\frac{xh_{0,b1}(x)}{1x\mathrm{}x^{b1}}.$$
(44)
Proof.  To obtain (43), observe that $`\mu _{0,1}=1`$; only the empty permutation avoids 1.

To obtain (44), first observe that the empty permutation avoids 132, 3241, and $`\mu _{0,b}`$. For $`n1`$, observe that every permutation $`\pi S_n(132,3241,\mu _{0,b})`$ for which $`\pi (n)=n`$ has the form $`\stackrel{~}{\pi },n`$, where $`\stackrel{~}{\pi }S_{n1}(132,3241,\mu _{0,b1})`$, and the resulting map is a bijection between $`S_{n1}(132,3241,\mu _{0,b1})`$ and the set of permutations in $`S_n(132,3241,\mu _{0,b})`$ which end with $`n`$. Similarly, observe that if $`1ib1`$ and $`i<n`$ then every permutation $`\pi S_n(132,3241,\mu _{0,b})`$ with $`\pi (i)=n`$ has the form $`ni+1,ni+2,\mathrm{},n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(132,3241,\mu _{0,b})`$, and the resulting map is a bijection between $`S_{ni}(132,3241,\mu _{0,b})`$ and the set of permutations in $`S_n(132,3241,\mu _{0,b})`$ in which $`n`$ is in the $`i`$th position. Finally, observe that if $`\pi S_n`$ avoids 132 and 3241 and $`\pi (i)=n`$ for $`ib`$ then $`\pi `$ does not avoid $`\mu _{0,b}`$. Combine these observations to find

$$h_{0,b}(x)=1+xh_{0,b1}(x)+\left(\underset{i=1}{\overset{b1}{}}x^i\right)\left(h_{0,b}(x)1\right).$$

Solve this equation for $`h_{0,b}(x)`$ to obtain (44). $`\mathrm{}`$

We now give a recurrence relation for $`h_{a,b}(x)`$.

###### Proposition 5.11

Let $`a`$ and $`b`$ denote positive integers. Then

$$h_{a,b}(x)=\frac{12x+xh_{a1,b}(x)}{(1x)^2}.$$
(45)
Proof.  First observe that the empty permutation avoids 132, 3241, and $`\mu _{a,b}`$. For $`n1`$, observe that every permutation $`\pi S_n(132,3241,\mu _{a,b})`$ for which $`\pi (n)=n`$ has the form $`\stackrel{~}{\pi },n`$, where $`\stackrel{~}{\pi }S_{n1}(132,3241,\mu _{a,b})`$, and the resulting map is a bijection between $`S_{n1}(132,3241,\mu _{a,b})`$ and the set of permutations in $`S_n(132,3241,\mu _{a,b})`$ which end with $`n`$. Similarly, observe that if $`1in1`$ then every permutation $`\pi S_n(132,3241,\mu _{a,b})`$ with $`\pi (i)=n`$ has the form $`ni+1,ni+2,\mathrm{},n,\stackrel{~}{\pi }`$, where $`\stackrel{~}{\pi }S_{ni}(132,3241,\mu _{a,b})`$, and the resulting map is a bijection between $`S_{ni}(132,3241,\mu _{a1,b})`$ and the set of permutations in $`S_n(132,3241,\mu _{a,b})`$ in which $`n`$ is in the $`i`$th position. Combine these observations to find

$$h_{a,b}(x)=1+xh_{a,b}(x)+\frac{x}{1x}(h_{a1,b}(x)1).$$

Solve this equation for $`h_{a,b}(x)`$ to obtain (45). $`\mathrm{}`$

We now use (44) and (45) to obtain explicit enumerations of $`S_n(132,3241,\mu _{a,b})`$ for various small values of $`a`$ and $`b`$.

###### Proposition 5.12

For all $`n1`$,

$$|S_n(132,3241,\mu _{0,3})|=F_{n+2}1.$$
(46)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,3241,\mu _{a,b})|x^n=1+\frac{x}{(1x)(1xx^2)}.$$
(47)
Proof.  This result is proved in , but for completeness we give a proof here. To obtain (47), first use (43) and (44) to find

$$h_{0,2}(x)=\frac{1}{1x}.$$

Now set $`b=3`$ in (44) and use the last equation to simplify the result, obtaining (47). To obtain (46), observe that

$$\frac{x}{(1x)(1xx^2)}=\frac{F_1x+F_2}{1xx^2}\frac{1}{1x}.$$

Now (46) is immediate from (36) and (37). $`\mathrm{}`$

We also give a bijective proof of (46).

###### Theorem 5.13

For all $`n1`$ there exists a constructive bijection between $`S_n(132,3241,\mu _{0,3})`$ and the set of tilings of a $`1\times (n+1)`$ rectangle with tiles of size $`1\times 1`$ and $`1\times 2`$ using at least one $`1\times 2`$ tile.

Proof.  Suppose we are given such a tiling. To construct the corresponding permutation, we consider two cases: the rightmost tile is $`1\times 2`$ or the rightmost tile is $`1\times 1`$.

If the rightmost tile is $`1\times 2`$, then first place a 1 in the rightmost tile. Now fill the rightmost empty tile with the smallest available numbers, placing them in the tile from left to right in increasing order. Repeat this process until every tile is filled.

If the rightmost tile is $`1\times 1`$, then let $`m`$ denote the number of $`1\times 1`$ tiles to the right of the rightmost $`1\times 2`$ tile. Place an $`m`$ in the rightmost $`1\times 2`$ tile. Fill the (necessarily $`1\times 1`$) tiles to the right of the rightmost $`1\times 2`$ with the numbers $`m1,m2,\mathrm{},1,m+1`$, in this order. Now fill the rightmost empty tile with the smallest available numbers, placing them in the tile from left to right in increasing order. Repeat this process until every tile is filled.

It is routine to verify that this map is invertible, and that the permutation constructed avoids 132, 3241, and $`\mu _{0,3}`$. $`\mathrm{}`$

###### Example 5.14

Under the bijection given in the proof of Theorem 5.13, the permutation 7563214 corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$ and the permutation 897564321 corresponds to the tiling $`\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}`$.

We omit the proofs of the remaining propositions in this section, since they are similar to the proof of Proposition 5.12.

###### Proposition 5.15

For all $`n1`$,

$$|S_n(132,3241,\mu _{0,4})|=\frac{1}{2}\left(2F_{3,n+3}+F_{3,n+2}+F_{3,n}2F_{n+4}+1\right).$$
(48)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,3241,\mu _{0,4})|=1+\frac{xx^2+x^4}{(1x)(1xx^2)(1xx^2x^3)}.$$

###### Proposition 5.16

For all $`n1`$,

$`|S_n(132,3241,\mu _{0,5})|=`$
$`{\displaystyle \frac{1}{6}}\left(14F_{4,n+4}+8F_{4,n+3}+4F_{4,n+2}+2F_{4,n}6F_{3,n+6}3F_{3,n+5}3F_{3,n+3}+6F_{n+5}1\right).`$
Moreover,

$`{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}|S_n(132,3241,\mu _{0,5})|x^n=`$
$`1+{\displaystyle \frac{x2x^2+2x^4+2x^5x^6x^7}{(1x)(1xx^2)(1xx^2x^3)(1xx^2x^3x^4)}}.`$
###### Proposition 5.17

For all $`n1`$,

$$|S_n(132,3241,\mu _{1,3})|=F_{n+5}\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)2\left(\genfrac{}{}{0pt}{}{n+1}{1}\right)2.$$
(49)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,3241,\mu _{1,3})|x^n=\frac{13x+3x^2+x^3x^4}{(1x)^3(1xx^2)}.$$

Comparing (49) with (39) we find that for $`n1`$,

$$|S_n(132,3241,\mu _{1,3})|=|S_n(132,2341,\omega _4)|.$$

This is no surprise, however, since $`S_n(132,2341,\omega _4)`$ is precisely the set of inverses of the elements of $`S_n(132,3241,\mu _{1,3})`$.

###### Proposition 5.18

For all $`n1`$,

$$|S_n(132,3241,\mu _{2,3})|=F_{n+8}\left(\genfrac{}{}{0pt}{}{n+1}{4}\right)3\left(\genfrac{}{}{0pt}{}{n+1}{3}\right)4\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)9\left(\genfrac{}{}{0pt}{}{n+1}{1}\right)11.$$
(50)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,3241,\mu _{2,3})|x^n=\frac{15x+10x^28x^3+x^4+4x^52x^6}{(1x)^5(1xx^2)}.$$

###### Proposition 5.19

For all $`n1`$,

$$|S_n(132,3241,\mu _{1,4})|=\frac{1}{2}\left(F_{3,n+5}+2F_{3,n+4}\right)F_{n+7}+\frac{1}{2}\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)+\frac{3}{2}\left(\genfrac{}{}{0pt}{}{n+1}{1}\right)+5.$$
(51)
Moreover,

$$\underset{n=0}{\overset{\mathrm{}}{}}|S_n(132,3241,\mu _{1,4})|x^n=\frac{14x+5x^2x^4x^5+x^7}{(1x)^3(1xx^2)(1xx^2x^3)}.$$

## 6 Extended Restrictions

Let $`R`$ denote a set of permutations. In this section we describe a method of building sets of forbidden subsequences from $`R`$ for which the associated sets of restricted permutations can be easily enumerated in terms of $`|S_n(R)|`$. We then use this method to produce some specific enumerations, several of which involve Fibonacci numbers or $`k`$-generalized Fibonacci numbers. We begin by describing our technique for building on $`R`$.

###### Definition 6.1

Suppose $`\alpha S_{n1}`$ and $`\beta S_n`$. We say $`\beta `$ is an extension of $`\alpha `$ whenever $`\alpha `$ is the permutation obtained by removing $`n`$ from $`\beta `$. We observe that every permutation in $`S_n`$ has exactly $`n+1`$ extensions.

###### Definition 6.2

Let $`R`$ denote a set of permutations. We write $`E(R)`$ to denote the set of permutations $`\pi `$ such that $`\pi `$ is an extension of an element of $`R`$, and we refer to $`E(R)`$ as the extension of $`R`$. More generally, we write $`E^0(R)=R`$ and for any $`k2`$ we define $`E^k(R)`$ inductively, so that $`E^k(R)=E(E^{k1}(R))`$.

Our results in this section are based on the following observation.

###### Theorem 6.3

Let $`R`$ denote a set of permutations. Then for all $`n1`$,

$$S_n(E(R))=E(S_{n1}(R)).$$
(52)
Moreover, for all $`k0`$,

$$|S_n(E^k(R))|=\frac{n!}{(nk)!}|S_{nk}(R)|(nk)$$
(53)
and

$$|S_n(E^k(R))|=n!(0n<k).$$
(54)
Proof.  To obtain (52), suppose $`\pi ^{}S_{n1}`$, $`\pi `$ is an extension of $`\pi ^{}`$, and $`\sigma ^{}S_m`$. Observe that $`\pi ^{}`$ contains a subsequence of type $`\sigma ^{}`$ if and only if there exists an extension $`\sigma `$ of $`\sigma ^{}`$ such that $`\pi `$ contains a subsequence of type $`\sigma `$. Now (52) is immediate.

To obtain (53), we argue by induction on $`k`$. Since $`E^0(R)=R`$, the result is immediate for $`k=0`$. Now observe that every permutation in $`S_n`$ has exactly $`n+1`$ extensions, and every permutation in $`S_{n+1}`$ is the extension of exactly one permutation in $`S_n`$. Therefore, using (52) and induction we find

$`|S_n(E^k(R))|`$ $`=`$ $`|E(S_{n1}(E^{k1}(R)))|`$
$`=`$ $`n|S_{n1}(E^{k1}(R))|`$
$`=`$ $`{\displaystyle \frac{n!}{(nk)!}}|S_{nk}(R)|,`$
as desired.

To obtain (54), observe that every permutation in $`R`$ has length at least $`k`$, so $`S_n(R)=S_n`$ when $`n<k`$. $`\mathrm{}`$

We now give several applications of this theorem.

###### Proposition 6.4

For all $`k0`$ and all $`nk`$,

$$|S_n(E^k(123,132,213))|=\frac{n!}{(nk)!}F_{n+1k}.$$

In particular, for all $`n1`$,

$$|S_n(1234,1243,1423,4123,1324,1342,1432,4132,2134,2143,2413,4213)|=nF_n.$$

Proof.  Set $`R=\{123,132,213\}`$ in (53) and use (1) to simplify the result. $`\mathrm{}`$

###### Proposition 6.5

Let $`R`$ denote one of the following sets of permutations.

$$\begin{array}{c}\{123,1432\};\{123,2143\};\{123,2413\};\{132,1234\};\{132,2134\};\\ \{132,2314\};\{132,2341\};\{132,3241\};\{132,3412\}\end{array}$$

For all $`k0`$ and all $`nk`$,

$$|S_n(E^k(R))|=\frac{n!}{(nk)!}F_{2(nk)1}.$$
(55)
Proof.  In  West shows that for each of the sets listed, $`S_n(R)=F_{2n1}`$. Combine this with (53) to obtain (55). $`\mathrm{}`$

###### Proposition 6.6

(see Guibert ) Fix $`\tau S_3`$. For all $`k0`$ and all $`nk`$,

$$|S_n(E^k(\tau ))|=\frac{n!}{(nk+1)!}\left(\genfrac{}{}{0pt}{}{2n2k}{nk}\right).$$
(56)
Proof.  It is well known that for all $`\tau S_3`$ we have $`S_n(\tau )=C_n`$, where $`C_n={\displaystyle \frac{1}{n+1}}\left({\displaystyle \genfrac{}{}{0pt}{}{2n}{n}}\right)`$ is the $`n`$th Catalan number. Combine this with (53) to obtain (56). $`\mathrm{}`$

## 7 Generalizations of Simion and Schmidt Involving Larger Sets of Restrictions

Let $`R`$ denote a set of permutations. Up to this point we have singled out those $`R`$ for which $`|S_n(R)|`$ can be expressed in terms of Fibonacci numbers or $`k`$-generalized Fibonacci numbers. Put another way, we have considered those $`R`$ for which $`|S_n(R)|`$ is closely related to certain linear homogeneous recurrence relations with constant coefficients. In this section we describe a family of sets of permutations such that if $`R`$ is a set in the family then $`|S_n(R)|`$ satisfies a linear homogeneous recurrence relation with constant coefficients. We begin with some terminology.

###### Definition 7.1

Let $`k`$ and $`l`$ denote positive integers such that $`lk`$ and let $`a_1,\mathrm{},a_l`$ denote a sequence of positive integers. We say a permutation $`\sigma S_k`$ agrees with $`a_1,\mathrm{},a_l`$ to length $`j`$ whenever $`\sigma (i)=a_i`$ for $`1ij`$. If $`\sigma (1)a_1`$ then we say $`\sigma `$ agrees with $`a_1,\mathrm{},a_l`$ to length 0.

We now define our sets of forbidden subsequences.

###### Definition 7.2

Let $`k`$ and $`l`$ denote positive integers such that $`lk`$ and let $`a_1,\mathrm{},a_l`$ denote a sequence of positive integers. We write $`R_{a_1,\mathrm{},a_l}^k`$ to denote the set of permutations in $`S_k`$ such that $`\sigma R_{a_1,\mathrm{},a_l}^k`$ whenever one of the following holds.

1. $`\sigma `$ agrees with $`a_1,\mathrm{},a_l`$ to length $`l`$.
2. There exists $`i`$, $`0il1`$, such that $`\sigma `$ agrees with $`a_1,\mathrm{},a_l`$ to length $`i`$ and $`\sigma (i+1)<a_{i+1}`$.

The sequence $`|S_n(R_{a_1,\mathrm{},a_l}^k)|`$ satisfies a certain linear homogeneous recurrence relation with constant coefficients.

###### Theorem 7.3

Let $`k`$ and $`l`$ denote positive integers such that $`lk`$ and let $`a_1,\mathrm{},a_l`$ denote a sequence of positive integers in which $`a_1,\mathrm{},a_{l1}`$ are distinct. Then for all $`n<k`$ we have

$$|S_n(R_{a_1,\mathrm{},a_l}^k)|=n!$$
(57)
and for all $`nk`$ we have

$$|S_n(R_{a_1,\mathrm{},a_l}^k)|=\underset{j=1}{\overset{l}{}}(ka_j\eta _j)|S_{nj}(R_{a_1,\mathrm{},a_l}^k)|,$$
(58)
where $`\eta _j=\{i|a_i>a_j\text{and}i<j\}`$ for $`1jl`$.

Proof.  To obtain (57), observe that $`R_{a_1,\mathrm{},a_l}^kS_k`$, so $`S_n(R_{a_1,\mathrm{},a_l}^k)=S_n`$ when $`n<k`$.

To prove (58), we first set some notation. For any $`j`$, $`0jl`$, let $`P_{n,j}`$ denote the set of permutations $`\pi R_{a_1,\mathrm{},a_l}^k`$ such that $`\pi (i)=nk+a_i`$ for $`1ij`$. We observe that $`P_{n,0}=S_n(R_{a_1,\mathrm{},a_l}^k)`$. We also observe that if $`\pi S_n`$ satisfies $`\pi (i)=nk+a_i`$ for $`1il`$ then the subsequence $`nk+a_1,nk+a_2,\mathrm{},nk+a_l`$ of $`\pi `$, together with the remaining elements of $`\pi `$ which are greater than $`nk`$, forms a pattern in $`R_{a_1,\mathrm{},a_l}^k`$. Therefore $`P_{n,l}`$ is empty.

We make the following claim concerning $`P_{n,j}`$.

Claim One For all $`j`$, $`0jl1`$,

$$|P_{n,j}|=(ka_{j+1}\eta _{j+1})|S_{nj1}(R)|+|P_{n,j+1}|,$$
(59)
where $`\eta _j=\{i|a_i>a_j\text{and}i<j\}`$ for $`1jl`$.

Assuming for the moment that claim one holds, we complete the proof of (58). Set $`j=0`$ in (59) and recall that $`P_{n,0}=S_n(R_{a_1,\mathrm{},a_l}^k)`$ to find

$$|S_n(R_{a_1,\mathrm{},a_l}^k)|=(ka_1\eta _1)|S_{n1}(R_{a_1,\mathrm{},a_l}^k)|+|P_{n,1}|.$$

Now use (59) with $`j=1`$ to eliminate $`|P_{n,1}|`$ in the last equation. Repeat the process to obtain

$$|S_n(R_{a_1,\mathrm{},a_l}^k)|=\underset{j=1}{\overset{l}{}}(ka_j\eta _j)|S_{nj}(R_{a_1,\mathrm{},a_l}^k)|+|P_{n,l}|.$$

Since $`P_{n,l}`$ is empty, (58) follows.

Proof of Claim One. First observe that $`P_{n,j+1}P_{n,j}`$, so we restrict our attention to those $`\pi P_{n,j}`$ for which $`\pi (j+1)nk+a_{j+1}`$. We consider two cases: $`\pi (j+1)<nk+a_{j+1}`$ and $`\pi (j+1)>nk+a_{j+1}`$.

Suppose $`\pi (j+1)<nk+a_{j+1}`$. Then the subsequence $`nk+a_1,nk+a_2,\mathrm{},nk+a_j,\pi (j+1)`$ of $`\pi `$, together with the remaining elements of $`\pi `$ which are greater than $`nk+1`$, forms a pattern in $`R_{a_1,\mathrm{},a_l}^k`$. This contradicts the fact that $`\pi `$ avoids every pattern in $`R_{a_1,\mathrm{},a_l}^k`$, so there is no $`\pi P_{n,j}`$ for which $`\pi (j+1)<nk+a_{j+1}`$.

Suppose $`\pi (j+1)>nk+a_{j+1}`$. Observe that if there exists $`i`$, $`1ij`$, for which $`\pi (i)`$ participates in a pattern in $`R_{a_1,\mathrm{},a_k}^k`$, then that pattern must involve all of those entries of $`\pi `$ which are greater than $`nk`$. For instance, that pattern must involve $`\pi (1),\pi (2),\mathrm{},\pi (j)`$, since each of these is greater than $`nk`$. Similarly, such a pattern must involve $`\pi (j+1)`$, since $`\pi (j+1)>nk+a_{j+1}>nk`$. However, because $`\pi (j+1)>nk+a_{j+1}`$, there is no pattern in $`R_{a_1,\mathrm{},a_l}^k`$ whose first $`j+1`$ entries have the same relative order as $`\pi (1),\mathrm{},\pi (j+1)`$. Therefore if $`\pi P_{n,j}`$ and $`\pi (j+1)>nk+a_{j+1}`$ then $`\pi `$ has the form $`nk+a_1,nk+a_2,\mathrm{},nk+a_j,r,\stackrel{~}{\pi }`$, where $`nk+a_{j+1}<rn`$ and $`\stackrel{~}{\pi }`$ is a permutation of the remaining numbers which avoids $`R_{a_1,\mathrm{},a_l}^k`$. Since there are $`ka_{j+1}\eta _{j+1}`$ choices for $`r`$, and $`|S_{nj1}(R_{a_1,\mathrm{},a_l})|`$ choices for $`\stackrel{~}{\pi }`$, the number of permutations $`\pi P_{n,j}`$ for which $`\pi (j+1)>nk+a_{j+1}`$ is equal to $`(ka_{j+1}\eta _{j+1})|S_{nj1}(R_{a_1,\mathrm{},a_l})|`$. Now (59) follows. $`\mathrm{}`$

Simion and Schmidt’s result (1) is a special case of Theorem 7.3. To see this, first observe that $`R_{2,2}^3=\{123,132,213\}`$. In view of this, we set $`k=3`$, $`l=2`$, $`a_1=2`$, and $`a_2=2`$ in (58) to obtain

$$|S_n(123,132,213)|=|S_{n1}(123,132,213)|+|S_{n2}(123,132,213)|$$

for $`n3`$. Since $`F_2=1!`$ and $`F_3=2!`$, we find that $`|S_n(123,132,213)|=F_{n+1}`$ for $`n1`$.

Theorem 7.3 has many other interesting special cases. We conclude this section by mentioning just a few of them.

###### Proposition 7.4

(\[22, Thm. 1\]) Let $`k`$ denote a positive integer and fix $`a`$ such that $`1ak`$. Then for all $`nk1`$,

$$|S_n(R_a^k)|=(k1)!(ka)^{nk+1}.$$
(60)
Proof.  Set $`l=1`$ and $`a_1=a`$ in (58) to find

$$|S_n(R_a^k)|=(ka)|S_{n1}(R_a^k)|$$

for $`nk`$. Combine this with (57) to obtain (60). $`\mathrm{}`$

###### Proposition 7.5

For all $`n1`$,

$$|S_n(1234,1243,1324,1342,1423,1432,2134,2143,2314,2341)|=p_n+p_{n2},$$

where $`p_n`$ is the $`n`$th Pell number, which is defined by $`p_0=0`$, $`p_1=1`$, and $`p_n=2p_{n1}+p_{n2}`$ for $`n2`$.

Proof.  For notational convenience, we abbreviate

$$b_n=|S_n(1234,1243,1324,1342,1423,1432,2134,2143,2314,2341)|.$$

Setting $`l=2`$, $`k=4`$, $`a_1=2`$, and $`a_2=3`$ in Theorem 7.3 we find that $`b_n=2b_{n1}+b_{n2}`$ for $`n4`$. Since $`p_n+p_{n2}=n!`$ for $`n=1,2,3`$, the result follows. $`\mathrm{}`$

For more information on the Pell numbers, see , \[4, pp. 122–125\], , and .

We conclude the paper with one more generalization of Simion and Schmidt’s result (1).

###### Proposition 7.6

Let $`k`$ denote a positive integer such that $`k3`$. Then for all $`nk`$,

$$|S_n(R_{k1,k1}^k)|=(k2)!(F_{nk+4}+(k3)F_{nk+2}).$$

Proof.  Consider the sequence $`x_{k2},x_{k1},\mathrm{}`$ in which

$$x_n=|S_n(R_{k1,k1}^k)|.$$

By (57) the first two terms in this sequence are $`(k2)!`$ and $`(k1)!`$. By (58) this sequence satisfies $`x_n=x_{n1}+x_{n2}`$ for all $`nk`$. Now consider the sequence $`y_{k2},y_{k1},\mathrm{}`$ in which $`y_{k2}=(k2)!`$, $`y_{k1}=(k1)!`$, and $`y_n=(k2)!(F_{nk+4}+(k3)F_{nk+2})`$ for $`nk`$. Clearly $`x_{k2}=y_{k2}`$ and $`x_{k1}=y_{k1}`$. Moreover, it is routine to verify that $`y_n=y_{n1}+y_{n2}`$ for all $`nk`$. Therefore $`y_n=x_n`$ for all $`nk`$, as desired. $`\mathrm{}`$


text:
# Mode locking of vortex matter driven through mesoscopic channels

## Abstract

We investigated the driven dynamics of vortices confined to mesoscopic flow channels by means of a dc-rf interference technique. The observed mode-locking steps in the $`IV`$-curves provide detailed information on how both the number of vortex rows and the lattice structure in each flow channel change with magnetic field. Minima in flow stress occur when an integer number of rows is moving coherently, while maxima appear when incoherent motion of mixed $`n`$ and $`n\pm 1`$ row configurations is predominant. Simulations show that the enhanced pinning at mismatch originates from quasi-static fault zones with misoriented edge dislocations induced by disorder in the channel edges.

During the last decades, vortex matter in superconductors has been widely recognized as model system for investigating driven, periodic media in various pinning potentials. One of the intriguing phenomena it can display is a non-monotonous behavior of the depinning current density $`J_c`$ with magnetic field. The best known example of such behavior is the so called peak effect occurring in weak pinning superconductors near $`H_{c2}`$ . Non-monotonous behavior of $`J_c`$ also occurs in superconductors with (artificial) periodic pinning arrays due to the possibility of (in)commensurability between the pinning structures and the vortex arrays . In both cases, the change in $`J_c`$ is accompanied by pronounced structural transitions in the static as well as the driven ”lattice”. For periodic pinning, it was predicted theoretically  and confirmed by experiments  that defects due to incommensurability can cause a drastic reduction of $`J_c`$. For the case of the peak effect in presence of random pinning the consensus is that the opposite happens: here plastic deformations cause an increase in $`J_c`$. However, the role of defects in the plastic flow regime above the pinning threshold remains largely unknown.

A powerful tool to obtain time averaged, small scale information on the moving structure is to probe the dc current-voltage (I-V) characteristics in presence of superimposed rf-currents . When a vortex lattice moves coherently at average velocity $`v`$ through a pinning potential, a microscopically periodic velocity modulation  is induced at the washboard frequency $`f_{int}=v/a`$ and, generally, at integer multiples $`qf_{int}`$. Here, $`a`$ is the lattice period in the direction of motion. In presence of an rf-force with frequency $`f`$ these modulations get mode-locked when $`f_{int}/f=p/q`$ where $`p`$, like $`q`$, is an integer, giving rise to interference plateaus in the I-V curves. The appearance of this phenomenon was shown to depend sensitively on the structure of the moving lattice .

In this Letter we report the results of mode-locking experiments on vortex matter driven through mesoscopic channels. The channel device  consists of an amorphous (a-)NbxGe1-x film ($`x0.3`$, $`T_c=2.68`$ K and thickness $`d=550`$ nm) with a NbN film ($`T_c=12`$ K, $`d=50`$ nm) on top. Straight parallel channels (width $`w=230`$ nm and length $`300`$ $`\mu `$m) were etched in the NbN layer. Pinning in a-NbGe is very weak, while in NbN it is very strong , providing easy vortex flow channels with strong pinning channel edges (CE’s) (see lower inset to Fig. 1). Importantly, the structure of vortex matter in the channel can be tuned on the ’atomic’ scale by changing, through the applied field, the (mis)matching conditions between the lattice period and channel width.

In our system the dc-critical current at which vortices in the channel start to move is determined by the (shear) interaction with pinned vortices in the CE’s. Phenomenologically, $`J_c`$ follows from $`F_c=J_cB=2Ac_{66}/w_{eff}`$ , with $`F_c`$ the critical force density, $`B`$ the induction, $`c_{66}`$ the vortex lattice shear modulus and $`w_{eff}`$ the effective channel width. The parameter $`A`$ depends crucially on the microscopic structure of the vortex arrays. In fields for which the arrays in the channel and the CE’s are commensurate ($`a=a_0`$ and $`w_{eff}/b_0`$ integer in the inset to Fig. 1 with $`a_0=2b_0/\sqrt{3}=(2\mathrm{\Phi }_0/\sqrt{3}B)^{1/2}`$ the equilibrium lattice spacing), one expects a large flow stress, whereas it should be small for incommensurate fields due to the occurrence of misfit dislocations . This picture seems correct, since $`J_c`$ shows oscillations and is globally proportional to $`c_{66}`$ . However, recent studies  indicate that this picture is very sensitive to positional disorder of the vortex arrays in the CE’s, particularly when this disorder is sufficient to cause spontaneous formation of dislocations. Recent STM experiments  on vortices in NbN indeed show strong deviations from the regular lattice arrangement.

This new ingredient turns out to have intruiging consequences. By means of the mode-locking technique we were for the first time able to determine unambiguously the number of moving vortex rows, the evolution of the microstructure and, from simulations, the microscopic origin of the flow-impedance oscillations in the channels.

The measurements were performed in a conventional four-probe geometry. The rf-current was applied through an rf-transformer with balanced transmission lines and a matching circuit. We used frequencies from $`1`$ to $`200`$ MHz and amplitudes $`I_{rf}<5`$ mA. To avoid heating, the sample was immersed in superfluid 4He. All data shown here was obtained at $`T=1.9`$ K. Since strong field-history effects exist , we focus for simplicity on results of field down measurements where first a field $`\mu _0H_{c2}`$ of NbGe is applied after which we slowly ($`\mu _0dH/dt2`$ mT/s) sweep to the field under consideration.

Figure 1 shows a series of $`IV`$ curves measured at $`60`$ mT with superimposed $`6`$ MHz rf-currents of various amplitudes. The dc-$`IV`$ curve ($`I_{rf}=0`$) shows a nonlinear voltage upturn from which $`I_c`$ was determined using a $`100`$ nV criterion. The application of sufficiently large rf-currents leads to clear mode-locking steps at equidistant voltage levels $`V_p`$ which are indicated for $`p=1,2,3`$. As shown below, $`q=1`$ and thus $`p=1`$ refers to the fundamental and $`p=2,3`$ to higher harmonics. These voltage levels depend linearly on $`f`$, as follows for $`p=1,2`$ from the upper inset to Fig. 1. The interference step width $`\mathrm{\Delta }I`$ for each harmonic shows Bessel function-like oscillations with $`I_{rf}`$ which will be discussed in detail elsewhere.

Next we turn to the field dependence of the mode-locking phenomenon. The characteristics are better displayed by plotting the differential conductance $`dI/dV`$ versus $`V`$, as done in Fig. 2 for the $`f=6`$ MHz data. The results shown are obtained at constant $`I_{rf}10I_c`$ in fields from $`300`$ mT (bottom) to $`60`$ mT(top) with steps of $`10`$ mT. The interference steps, now appearing as peaks in $`dI/dV`$, change in amplitude and in voltage position with field. Focusing on the fundamental peak at $`V_1`$, it is seen that in certain field intervals $`V_1`$ is field independent, e.g. from $`60100`$ mT $`V_1`$ is $`4.6`$ $`\mu `$V. At $`90`$ mT another fundamental peak appears at a voltage of $`6.9`$ $`\mu `$V, which lies between the $`p=1`$ and $`p=2`$ interference peaks in lower fields. The second harmonic now coincides with the $`p=3`$ peak at 60 mT. Between 100 and 110 mT, the lower voltage $`p=1`$ peak vanishes while the $`6.9`$ $`\mu `$V peak (and its higher harmonics) grow and remain detectable up to $`180`$ mT.

The described sequence of appearances and disappearances of the peaks continues for larger fields. The resulting variation of $`V_1`$ with field is shown in more detail in Fig. 3(a). We plot the ratio of $`V_1`$ over $`f`$ to also include data taken at $`f=60`$ MHz. Both data sets collapse on distinct voltage plateaus separated by abrupt steps. Around the steps two consecutive fundamental interferences can coexist. This behavior is independent of frequency and $`I_{rf}`$. The voltage separation between adjacent plateaus corresponds to the value of $`V_1/f`$ of the lowest plateau. Therefore we labelled the plateaus by integers $`n`$. This staircase-like behavior suggests that $`V_1/f`$ reflects a process in which the number of vortex rows in each channel changes with field in a discrete manner.

The relation between interference voltage and number of moving rows can be derived as follows: the general interference condition for the velocity of an ordered array with average longitudinal vortex spacing $`a`$ and row spacing $`b`$ (see inset to Fig. 1) is $`v_{p,q}=(p/q)fa`$. Thus the interference voltage per channel $`\stackrel{~}{V}_{p,q}=w_{eff}Bv_{p,q}`$, with $`B=\mathrm{\Phi }_0/ab`$ the induction, is:

$`\stackrel{~}{V}_{p,q}={\displaystyle \frac{p}{q}}\mathrm{\Phi }_0fw_{eff}/b={\displaystyle \frac{p}{q}}\mathrm{\Phi }_0fn,`$ (1)
where $`w_{eff}/b=n`$ is the number of moving rows. Taking into account that we measure the voltage $`V`$ over $`200`$ channels, the height of the jumps in $`V_1/f`$ in Fig. 3(a) corresponds to $`\mathrm{\Phi }_0`$, validating the identification of the peaks at $`V_1`$ as fundamental. We note that, regardless of field, no subharmonic peaks ($`q1`$) could be resolved. Such subharmonics have been observed in dc-rf driven charge density waves and bulk vortex lattices . Here, their absence might be explained by the fact that our pinning potential, which stems from the interaction with pinned vortices in the CE’s with average spacing $`a_0`$, predominantly contains modes with wave vector $`2\pi /a_0`$ .

The data in Fig. 3(a) combined with Eq. (1) shows unambiguously that in those parts of the flow where vortices show mode locking, the number of moving rows $`n`$ changes with field by one. We consider now in more detail the field dependence of the amplitude $`\mathrm{\Delta }I`$ of the mode locked steps, i.e. the area under the interference peaks (see the inset to Fig. 3(b)). Figure 3(b) shows $`\mathrm{\Delta }I`$ associated with the voltage plateaus for consecutive $`n`$ in (a), normalized by $`I_c`$. At fields around the middle of the plateaus, $`\mathrm{\Delta }I/I_c`$ is large. This indicates a large degree of coherency in the motion and implies that a unique, integer number of rows $`n`$ is moving, corresponding to a matching configuration as in the lower inset to Fig. 1. Approaching the edges of the plateaus, $`\mathrm{\Delta }I/I_c`$ decreases, signalling a reduction of the coherency in the moving arrays. At the plateau edges, $`\mathrm{\Delta }I/I_c`$ is strongly suppressed, even if $`I_{rf}`$ is varied. The coexistence of a residual signal from $`n`$ and $`n\pm 1`$ row configurations at the transition fields evidences that these fields correspond to the maximum mismatch situation.

It is clear that upon approaching a mismatch condition, a moving $`n`$ row configuration experiences increasing lattice strains which will progressively induce misfit dislocations in the structure. Let us now compare the observed transitions to the oscillations in $`I_c`$ in Fig. 3(c). It is seen that maxima in $`I_c`$ appear at the $`nn\pm 1`$ transition fields, while the minima in $`I_c`$ are located near matching fields . Therefore we conclude that, upon increasing the density of misfit dislocations in the channel, $`I_c`$ is enhanced. This result contrasts the picture in which dislocations lower the flow stress and is strongly reminiscent of the mechanism expected for the traditional peak effect in a random potential.

As mentioned, the positional disorder of vortex arrays in the CE’s, which is quenched for fixed field, plays a crucial role for understanding the relation between mismatch and the dc-depinning current $`I_c`$. We address this issue now in more detail by molecular dynamics simulations  of dc-driven channel vortices in the geometry of the lower inset to Fig. 1. Vortex interactions were modelled by the London potential with $`\lambda /a_0=2`$ ($`\lambda `$ is the penetration depth) . The CE vortices were assigned random shifts $`𝐝`$ with respect to the ideal lattice configuration, such that $`\sqrt{(𝐝)^2}0.12`$. We keep the average orientation of the CE arrays with a principal axis parallel to the channel. The vortex density in the channel and the CE’s were both $`(a_0b_0)^1`$, while the matching condition was tuned by the ratio $`w_{eff}/b_0`$.

First we discuss the results of simulations around matching of a $`3`$ row configuration ($`w_{eff}/b_0=3.05`$). The (rescaled) $`J_c`$ obtained in such simulations attains a value $`J_c=2Ac_{66}/(Bw_{eff})(A/A^0)J_c^0`$ with $`A0.2A^0`$  where $`A^0=(\pi \sqrt{3})^1`$ is the theoretical value for shear flow of perfectly matching vortex arrays along ordered CE’s . To understand the origin of this reduced flow stress we turn to Fig. 4(a) and (b). In (a) we show vortex trajectories during motion over $`5a_0`$ for a dc-drive $`J3J_c^0`$. The trajectories are essentially parallel to the CE’s and clearly show motion of $`3`$ rows. A Delauney triangulation (Fig. 4(b)) of a snapshot of (a), shows that vortices in the channel are mostly sixfold coordinated and elastically coupled. However, at the CE’s, dislocations are present with Burgers vectors (denoted by arrows) along the flow direction. These dislocations, which are mainly induced by disorder in the CE’s, are responsible for the reduction of $`J_c`$ with respect to $`J_c^0`$.

To study a mismatch situation we consider the case $`w_{eff}/b_0=3.55`$. The critical current we find is characterized by $`A=0.0650.4A^0`$, indeed enhanced compared to matching. Figure 4(c) shows the corresponding trajectories for $`J3.5J_c^0`$. Here, one observes coexistence of $`3`$ and $`4`$ moving rows and in addition substantial transverse displacements and switching of vortices between rows. Importantly, the $`3`$ and $`4`$ row regions remain quasi-static during motion and their location is determined by static disorder in the CE’s. The triangulation in (d) of a snapshot of the flow reveals numerous dislocations inside the channel. In contrast to the matching case, their Burgers vectors assume all possible orientations and are mostly misoriented to the flow direction. The motion of these misoriented dislocations is blocked by the interaction with disorder in the CE’s and with neighboring misoriented dislocations. This results in quasi-static fault zones where during the flow the dislocation pattern changes irregularly and the vortex trajectories are jammed. These phenomena form the mechanism underlying the enhanced flow impedance at mismatch.

The overall picture that has emerged from these simulations is that on approaching a matching state, the fault zones gradually heal, yielding a gradual decrease of the critical current. Simultaneously the size of coherent $`n`$-row regions grows, providing an explanation for the experimentally observed increase in the rf-dc interference signal. On changing the field, vortex dynamics in the channels thus exhibits a series of smooth structural transitions from quasi-1D coherent motion to quasi-2D disordered flow in a disordered potential.

In summary, we investigated the flow of vortices in mesoscopic channels bounded by pinned vortices. The rf-dc interference measurements yield unambiguous information on the field evolution of the number of moving rows and coherency in the channel. The depinning current oscillations exhibit maxima at mismatch conditions. Simulations show that this behavior originates from blocking of misoriented dislocations in quasi-static fault zones, which gradually heal on approaching a matching state.

This work was supported by the ’Stiching voor Fundamenteel Onderzoek der Materie’ (FOM). N.K. was supported by JSPS. V.M.V. was supported by the DOE Office of Science.