format: text

text:
# Restricted even permutations and Chebyshev polynomials

## Abstract

We study generating functions for the number of even (odd) permutations on $`n`$ letters avoiding $`132`$ and an arbitrary permutation $`\tau `$ on $`k`$ letters, or containing $`\tau `$ exactly once. In several interesting cases the generating function depends only on $`k`$ and is expressed via Chebyshev polynomials of the second kind.

2000 Mathematics Subject Classification: Primary 05A05, 05A15; Secondary 30B70, 42C05

## 1. Introduction

The aim of this paper is to give analogies of enumerative results on certain classes of permutations characterized by pattern-avoidance in the symmetric group $`\mathrm{SS}_n`$. In the set of even (odd) permutations we identify classes of restricted even (odd) permutations with enumerative properties analogous to results on permutations. More precisely, we study generating functions for the number of even (odd) permutations avoiding $`132`$ and avoiding (or containing exactly once) an arbitrary permutation $`\tau \mathrm{SS}_k`$. Moreover we consider statistics of the increasing pattern. In the remainder of this section we present a brief account of earlier works which motivated our investigation, we give the basic definitions used throughout the paper, and the organization of this paper.

Let $`[p]=\{1,\mathrm{},p\}`$ denote a totally ordered alphabet on $`p`$ letters, and let $`\alpha =(\alpha _1,\mathrm{},\alpha _m)[p_1]^m`$, $`\beta =(\beta _1,\mathrm{},\beta _m)[p_2]^m`$. We say that $`\alpha `$ is order-isomorphic to $`\beta `$ if for all $`1i<jm`$ one has $`\alpha _i<\alpha _j`$ if and only if $`\beta _i<\beta _j`$. For two permutations $`\pi \mathrm{SS}_n`$ and $`\tau \mathrm{SS}_k`$, an occurrence of $`\tau `$ in $`\pi `$ is a subsequence $`1i_1<i_2<\mathrm{}<i_kn`$ such that $`(\pi _{i_1},\mathrm{},\pi _{i_k})`$ is order-isomorphic to $`\tau `$; in such a context $`\tau `$ is usually called the pattern. We say that $`\pi `$ avoids $`\tau `$, or is $`\tau `$-avoiding, if there is no occurrence of $`\tau `$ in $`\pi `$, and we say that $`\pi `$ contains $`\tau `$ exactly $`r`$ times if there is $`r`$ different occurrences of $`\tau `$ in $`\pi `$. For example, the permutation $`598376412\mathrm{SS}_9`$ avoids $`123`$ and contains $`1432`$ exactly twice.

While the case of permutations avoiding a single pattern has attracted much attention, the case of multiple pattern avoidance remains less investigated. In particular, it is natural, as the next step, to consider permutations avoiding pairs of patterns $`\tau _1`$, $`\tau _2`$. This problem was solved completely for $`\tau _1,\tau _2\mathrm{SS}_3`$ (see \[SimSch\]), and for $`\tau _1\mathrm{SS}_3`$ and $`\tau _2\mathrm{SS}_4`$ (see \[W\]). Several recent papers \[CW, MV1, Kr, MV2, MV3, MV4, BCS\] deal with the case $`\tau _1\mathrm{SS}_3`$, $`\tau _2\mathrm{SS}_k`$ for various pairs $`\tau _1,\tau _2`$. Another natural question is to study permutations avoiding $`\tau _1`$ and containing $`\tau _2`$ exactly $`t`$ times. Such a problem for certain $`\tau _1,\tau _2\mathrm{SS}_3`$ and $`t=1`$ was investigated in \[Ro\], and for certain $`\tau _1\mathrm{SS}_3`$, $`\tau _2\mathrm{SS}_k`$ in \[RWZ, MV1, Kr, MV2, MV3, MV4\]. For example, several authors \[RWZ, MV1, Kr, BCS\] have shown that generating functions for the number $`132`$-avoiding permutations in $`\mathrm{SS}_n`$ with respect to number of occurrences of the pattern $`12\mathrm{}k`$ can be expressed as either continued fractions or Chebyshev polynomials of the second kind.

Chebyshev polynomials of the second kind (in what follows just Chebyshev polynomials) are defined by $`U_r(\mathrm{cos}\theta )=\frac{\mathrm{sin}(r+1)\theta }{\mathrm{sin}\theta }`$ for $`r0`$. The Chebyshev polynomials satisfy the following recurrence $`U_r(t)=2tU_{r1}(t)U_{r2}(t)`$ for $`r2`$ together with $`U_0(t)=1`$ and $`U_1(t)=2t`$. Evidently, $`U_r(x)`$ is a polynomial of degree $`r`$ in $`x`$ with integer coefficients. Chebyshev polynomials were invented for the needs of approximation theory, but are also widely used in various other branches of mathematics, including algebra, combinatorics, and number theory (see \[Ri\]). Apparently, for the first time the relation between restricted permutations and Chebyshev polynomials was discovered by Chow and West in \[CW\], and later by Mansour and Vainshtein \[MV1, MV2, MV3, MV4\] and Krattenthaler \[Kr\]. These results are related to a rational function

(1.1)
$$R_k(x)=\frac{U_{k1}\left(\frac{1}{2\sqrt{x}}\right)}{\sqrt{x}U_k\left(\frac{1}{2\sqrt{x}}\right)}$$

for all $`k1`$. For example, $`R_1(x)=1`$, $`R_2(x)=\frac{1}{1x}`$, and $`R_3(x)=\frac{1x}{12x}`$. It is easy to see that for any $`k`$, $`R_k(x)`$ is rational in $`x`$ and satisfies the following equation (see \[MV1, MV3, MV4\]) for $`k1`$,

(1.2)
$$R_k(x)=\frac{1}{1xR_{k1}(x)}.$$

Let $`\pi \mathrm{SS}_n`$. The number of inversions of $`\pi `$ is given by $`|\{(i,j):\pi _i>\pi _j,1i<jn\}|`$. The sign of $`\pi `$, $`\text{sign}(\pi )`$, is given by the number of inversions of $`\pi `$ modulo $`2`$ (equals $`1`$ if the number inversions of $`\pi `$ is given by even number, otherwise equals $`1`$). We say $`\pi `$ is an even permutation \[respectively; odd permutation\] if $`\text{sign}(\pi )=1`$ \[respectively; $`\text{sign}(\pi )=1`$\]. We say $`\pi `$ is an involution if $`\pi =\pi ^1`$. We denote the set of all even \[respectively; odd\] permutations in $`\mathrm{SS}_n`$ by $`𝔈_n`$ \[respectively; $`𝔒_n`$\]. For example, if $`\pi =4132\mathrm{SS}_4`$ then the number of inversions of $`\pi `$ equals $`4`$, so $`\text{sign}(\pi )=1`$ and $`\pi 𝔈_4`$.

The paper of Simion and Schmidt \[SimSch\] generalized and considered for many directions. Here we give two examples. The first one is paper of Chow and West \[CW\], which had dealt with three cases of avoiding $`132`$ or $`123`$ and avoiding $`\tau \mathrm{SS}_k`$. In particular, they found the generating function for the number of permutations in $`\mathrm{SS}_n(132,12\mathrm{}k)`$ which given by $`R_k(x)`$. The second one is papers of Guibert and Mansour \[GM1, GM2\], which had dealt with the cases of avoiding $`132`$ (or containing exactly once) and avoiding $`\tau \mathrm{SS}_k`$ (or containing exactly once). More precisely, the paper \[GM1\] dealt with the case of the generating function for number of involutions in $`\mathrm{SS}_n`$ avoiding $`132`$ (or containing exactly once) and avoiding $`\tau \mathrm{SS}_k`$ (or containing exactly once). The paper \[GM2\] dealt with the case of the generating function for number of even (odd) involutions in $`\mathrm{SS}_n`$ avoiding $`132`$ (or containing exactly once) and avoiding $`\tau \mathrm{SS}_k`$ (or containing exactly once).

###### Theorem 1.1.

(see \[CW, GM1, GM2\]) For all $`k0`$,

(i) The generating function for the number of permutations in $`\mathrm{SS}_n`$ avoiding both $`132`$ and $`12\mathrm{}k`$ is given by

$$R_k(x).$$

(ii) The generating function for the number of involutions in $`\mathrm{SS}_n`$ avoiding both $`132`$ and $`12\mathrm{}k`$ is given by

$$I_k(x)=\frac{1}{xU_k\left(\frac{1}{2x}\right)}\underset{j=0}{\overset{k1}{}}U_j\left(\frac{1}{2x}\right).$$

(iii) The generating function for the number of even involutions in $`\mathrm{SS}_n`$ avoiding both $`132`$ and $`12\mathrm{}k`$ is given by

$$\underset{j=0}{\overset{k1}{}}\left(x^j\left(1+\frac{x^2}{2}(R_{k1j}(x^2)+R_{k1j}(x^2))I_{kj}(x)\right)\underset{i=kj}{\overset{k}{}}R_i(x^2)\right).$$

The above theorem invites the following question: Find explicitly the generating function for the number even (odd) permutations avoiding both $`132`$ and $`12\mathrm{}k`$ in terms of Chebyshev polynomials? In this paper we give a complete answer for this question (see Subsection 2.2).

As a consequence of \[MV2, MV4\], we present a general approach to the study of even (odd) permutations avoiding $`132`$ and avoiding an arbitrary pattern $`\tau `$ of length $`k`$, or containing $`\tau `$ exactly once. We derive all the previously known results for this kind of problems, as well as many new results.

The paper is organized as follows. The case of even (odd) permutations avoiding both $`132`$ and $`\tau `$ is treated in Section 2. We derive a simple recursion for the corresponding generating functions for general $`\tau `$. This recursion can be solved explicitly for several interesting cases, including $`12\mathrm{}k`$, $`(d+1)(d+2)\mathrm{}k12\mathrm{}d`$, and odd-wedge patterns defined below. In particularly, we prove the generating function for the number of even (odd) permutations avoiding both $`132`$ and $`\tau S_k(132)`$ is a rational function for every nonempty pattern $`\tau `$. Observe that if $`\tau `$ itself contains $`132`$, then any $`132`$-avoiding permutation avoids $`\tau `$ as well, so in what follows we always assume that $`\tau S_k(132)`$. The case of permutations avoiding $`132`$ and containing $`\tau `$ exactly once is treated in Section 3. Here again we start from a general recursion, and then solve it for several particular cases. Finally, in Section 4 we describe several directions to extend and to generalize the results of the pervious sections.

Most of the explicit solutions obtained in the next sections involve Chebyshev polynomials of the second kind.

## 2. Avoiding an arbitrary pattern

Consider an arbitrary pattern $`\tau =(\tau _1,\mathrm{},\tau _k)\mathrm{SS}_k(132)`$. Recall that $`\tau _i`$ is said to be a right-to-left maximum if $`\tau _i>\tau _j`$ for any $`j>i`$. Let $`m_0=k,m_1,\mathrm{},m_r`$ be the right-to-left maxima of $`\tau `$ written from left to right. Then $`\tau `$ can be represented as

$$\tau =(\tau ^0,m_0,\tau ^1,m_1,\mathrm{},\tau ^r,m_r),$$

where each of $`\tau ^i`$ may be possibly empty, and all the entries of $`\tau ^i`$ are greater than $`m_{i+1}`$ and all the entries of $`\tau ^{i+1}`$. This representation is called the canonical decomposition of $`\tau `$. Given the canonical decomposition, we define the $`i`$th prefix of $`\tau `$ by $`\pi ^i=(\tau ^0,m_0,\mathrm{},\tau ^i,m_i)`$ for $`1ir`$ and $`\pi ^0=\tau ^0`$, $`\pi ^1=\mathrm{}`$. Besides, the $`i`$th suffix of $`\tau `$ is defined by $`\sigma ^i=(\tau ^i,m_i,\mathrm{},\tau ^r,m_r)`$ for $`0ir`$ and $`\sigma ^{r+1}=\mathrm{}`$. Strictly speaking, prefixes and suffices themselves are not patterns, since they are not permutations (except for $`\pi ^r=\sigma ^0=\tau `$). However, any prefix or suffix is order-isomorphic to a unique permutation, and in what follows we do not distinguish between a prefix (or suffix) and the corresponding permutation.

The set of all $`T`$-avoiding even \[respectively; odd\] permutations in $`\mathrm{SS}_n`$ we denote by $`𝔈_n(T)`$ \[respectively; $`𝔒_n(T)`$\]. Let $`e_\tau (n)`$ \[respectively; $`o_\tau (n)`$\] be the cardinality of the set $`𝔈_n(132,\tau )`$ \[respectively; $`𝔒_n(132,\tau )`$\]. The corresponding generating function let us denote by $`𝔈_\tau (x)`$ \[respectively; $`𝔒_\tau (x)`$\], that is,

$$𝔈_\tau (x)=\underset{n0}{}e_\tau (n)x^n\left[\text{respectively; }𝔒_\tau (x)=\underset{n0}{}o_\tau (n)x^n\right].$$

The generating function for the number of permutations avoiding both $`132`$ and $`\tau `$ we denote by $`_\tau (x)`$. Clearly,

(2.1)
$$_\tau (x)=𝔈_\tau (x)+𝔒_\tau (x).$$

The following proposition which is the base of all the results in this section.

###### Proposition 2.1.

Let $`k1`$ and $`n1`$, then

$$\begin{array}{c}e_\tau (2n+1)=\underset{d=0}{\overset{r}{}}\underset{j=0}{\overset{2n}{}}(e_{\pi ^d}(j)e_{\pi ^{d1}}(j))e_{\sigma ^d}(2nj)+\underset{d=0}{\overset{r}{}}\underset{j=0}{\overset{2n}{}}(o_{\pi ^d}(j)o_{\pi ^{d1}}(j))o_{\sigma ^d}(2nj),\hfill \\ \\ e_\tau (2n)=\underset{d=0}{\overset{r}{}}\underset{j=0,2,4,\mathrm{},2n2}{}(e_{\pi ^d}(j)e_{\pi ^{d1}}(j))o_{\sigma ^d}(2nj1)+(o_{\pi ^d}(j)o_{\pi ^{d1}}(j))e_{\sigma ^d}(2nj1)\hfill \\ +\underset{d=0}{\overset{r}{}}\underset{j=1,3,5,\mathrm{},2n1}{}(e_{\pi ^d}(j)e_{\pi ^{d1}}(j))e_{\sigma ^d}(2nj1)+(o_{\pi ^d}(j)o_{\pi ^{d1}}(j))o_{\sigma ^d}(2nj1).\hfill \end{array}$$

###### Proof.

We use induction. Clearly, the result holds for $`n=1`$. Now let $`\pi \mathrm{SS}_n(132)`$ such that $`\pi _{j+1}=n`$, $`0jn1`$. Then $`\beta =(\pi _1,\mathrm{},\pi _j)`$ is a $`132`$-avoiding permutation on the letters $`n1,n2,\mathrm{},nj`$ and $`\gamma =(\pi _{j+1},\mathrm{},\pi _n)`$ is a $`132`$-avoiding permutation on the letters $`nj1,nj2,\mathrm{},1`$. If we assume that $`\beta `$ avoids $`\pi ^d`$ and contains $`\pi ^{d1}`$, then $`\gamma `$ avoids $`\sigma ^d`$, where $`d=0,1,2\mathrm{},r`$. Besides,

$$\text{sign}(\pi )=(1)^{(j+1)(nj1)}\text{sign}(\beta )\text{sign}(\gamma )=(1)^{(j+1)(n1)}\text{sign}(\beta )\text{sign}(\gamma ),$$

equivalently,

$$\text{sign}(\pi )=\{\begin{array}{cc}\text{sign}(\beta )\text{sign}(\gamma ),\hfill & \text{if}n\text{odd}\hfill \\ (1)^{j+1}\text{sign}(\beta )\text{sign}(\gamma ),\hfill & \text{if}n\text{even}\hfill \end{array}$$

Hence, if summing over all $`d=0,1,\mathrm{},r`$ and $`j=0,1,2\mathrm{},n`$ together with use of the fact that the number of even \[respectively; odd\] permutations in $`𝔈_n`$ \[respectively; $`𝔒_n`$\] avoiding $`\beta `$ and containing $`\gamma `$ is given by $`e_\beta (n)e_{\beta ,\gamma }(n)`$ \[respectively; $`o_\beta (n)o_{\beta ,\gamma }(n)`$\] we get the desired result. ∎

Similarly to Proposition 2.1 we obtain the following result.

###### Proposition 2.2.

Let $`k1`$ and $`n1`$, then

$$\begin{array}{c}o_\tau (2n+1)=\underset{d=0}{\overset{r}{}}\underset{j=0}{\overset{2n}{}}(e_{\pi ^d}(j)e_{\pi ^{d1}}(j))o_{\sigma ^d}(2nj)+\underset{d=0}{\overset{r}{}}\underset{j=0}{\overset{2n}{}}(o_{\pi ^d}(j)o_{\pi ^{d1}}(j))e_{\sigma ^d}(2nj),\hfill \\ \\ o_\tau (2n)=\underset{d=0}{\overset{r}{}}\underset{j=0,2,4,\mathrm{},2n2}{}(e_{\pi ^d}(j)e_{\pi ^{d1}}(j))e_{\sigma ^d}(2nj1)+(o_{\pi ^d}(j)o_{\pi ^{d1}}(j))o_{\sigma ^d}(2nj1)\hfill \\ +\underset{d=0}{\overset{r}{}}\underset{j=1,3,5,\mathrm{},2n1}{}(e_{\pi ^d}(j)e_{\pi ^{d1}}(j))o_{\sigma ^d}(2nj1)+(o_{\pi ^d}(j)o_{\pi ^{d1}}(j))e_{\sigma ^d}(2nj1).\hfill \end{array}$$

Our present aim is to find the generating functions $`𝔈_\tau (x)`$ and $`𝔒_\tau (x)`$; thus we need the following lemma which holds immediately by definitions.

###### Lemma 2.3.

let $`\{a_n\}_{n0}`$ and $`\{b_n\}_{n0}`$ be two sequences, and the corresponding generating functions are $`a(x)`$ and $`b(x)`$; respectively. Then

1. $`\underset{n0}{}a_{2n}x^{2n}=\frac{1}{2}(a(x)+a(x))`$;
2. $`\underset{n1}{}a_{2n1}x^{2n1}=\frac{1}{2}(a(x)a(x))`$;
3. $`\underset{n1}{}\underset{j=0,2,4,\mathrm{},2n2}{}a_jb_{2n1j}x^{2n1}=\frac{1}{4}(a(x)+a(x))(b(x)b(x))`$;
4. $`\underset{n1}{}\underset{j=1,3,5,\mathrm{},2n1}{}a_jb_{2n1j}x^{2n1}=\frac{1}{4}(a(x)a(x))(b(x)+b(x))`$.

###### Theorem 2.4.

For any nonempty pattern $`\tau \mathrm{SS}_k(132)`$, the generating functions $`𝔈_\tau (x)`$ and $`𝔒_\tau (x)`$ are a rational functions in $`x`$ satisfying the relations

(2.2)
$$\begin{array}{c}𝔈_\tau (x)𝔈_\tau (x)=x\underset{d=0}{\overset{r}{}}(𝔈_{\pi ^d}(x)𝔈_{\pi ^{d1}}(x))𝔈_{\sigma ^d}(x)+(𝔈_{\pi ^d}(x)𝔈_{\pi ^{d1}}(x))𝔈_{\sigma ^d}(x)\hfill \\ +x\underset{d=0}{\overset{r}{}}(𝔒_{\pi ^d}(x)𝔒_{\pi ^{d1}}(x))𝔒_{\sigma ^d}(x)+(𝔒_{\pi ^d}(x)𝔒_{\pi ^{d1}}(x))𝔒_{\sigma ^d}(x)),\hfill \end{array}$$

(2.3)
$$\begin{array}{c}𝔒_\tau (x)𝔒_\tau (x)=x\underset{d=0}{\overset{r}{}}(𝔈_{\pi ^d}(x)𝔈_{\pi ^{d1}}(x))𝔒_{\sigma ^d}(x)+(𝔈_{\pi ^d}(x)𝔈_{\pi ^{d1}}(x))𝔒_{\sigma ^d}(x)\hfill \\ +x\underset{d=0}{\overset{r}{}}(𝔒_{\pi ^d}(x)𝔒_{\pi ^{d1}}(x))𝔈_{\sigma ^d}(x)+(𝔒_{\pi ^d}(x)𝔒_{\pi ^{d1}}(x))𝔈_{\sigma ^d}(x)),\hfill \end{array}$$

(2.4)
$$\begin{array}{c}𝔈_\tau (x)+𝔈_\tau (x)2=\hfill \\ =\frac{x}{2}\underset{d=0}{\overset{r}{}}(𝔈_{\pi ^d}(x)+𝔈_{\pi ^d}(x)𝔈_{\pi ^{d1}}(x)𝔈_{\pi ^{d1}}(x))(𝔒_{\sigma ^d}(x)𝔒_{\sigma ^d}(x))\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r}{}}(𝔒_{\pi ^d}(x)+𝔒_{\pi ^d}(x)𝔒_{\pi ^{d1}}(x)𝔒_{\pi ^{d1}}(x))(𝔈_{\sigma ^d}(x)𝔈_{\sigma ^d}(x))\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r}{}}(𝔈_{\pi ^d}(x)𝔈_{\pi ^d}(x)𝔈_{\pi ^{d1}}(x)+𝔈_{\pi ^{d1}}(x))(𝔈_{\sigma ^d}(x)+𝔈_{\sigma ^d}(x))\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r}{}}(𝔒_{\pi ^d}(x)𝔒_{\pi ^d}(x)𝔒_{\pi ^{d1}}(x)+𝔒_{\pi ^{d1}}(x))(𝔒_{\sigma ^d}(x)+𝔒_{\sigma ^d}(x)),\hfill \end{array}$$

and

(2.5)
$$\begin{array}{c}𝔒_\tau (x)+𝔒_\tau (x)=\hfill \\ =\frac{x}{2}\underset{d=0}{\overset{r}{}}(𝔈_{\pi ^d}(x)+𝔈_{\pi ^d}(x)𝔈_{\pi ^{d1}}(x)𝔈_{\pi ^{d1}}(x))(𝔈_{\sigma ^d}(x)𝔈_{\sigma ^d}(x))\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r}{}}(𝔒_{\pi ^d}(x)+𝔒_{\pi ^d}(x)𝔒_{\pi ^{d1}}(x)𝔒_{\pi ^{d1}}(x))(𝔒_{\sigma ^d}(x)𝔒_{\sigma ^d}(x))\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r}{}}(𝔈_{\pi ^d}(x)𝔈_{\pi ^d}(x)𝔈_{\pi ^{d1}}(x)+𝔈_{\pi ^{d1}}(x))(𝔒_{\sigma ^d}(x)+𝔒_{\sigma ^d}(x))\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r}{}}(𝔒_{\pi ^d}(x)𝔒_{\pi ^d}(x)𝔒_{\pi ^{d1}}(x)+𝔒_{\pi ^{d1}}(x))(𝔈_{\sigma ^d}(x)+𝔈_{\sigma ^d}(x)).\hfill \end{array}$$

###### Proof.

Using Propositions 2.1 and 2.2 together with Lemma 2.3 we get Equations 2.2-2.5. Rationalities of $`𝔈_\tau (x)`$ and $`𝔒_\tau (x)`$ for $`\tau \mathrm{}`$ follows easily by induction. ∎

As a remark, the above theorem holds for the empty pattern without rationalities of $`𝔈_\tau (x)`$ and $`𝔒_\tau (x)`$.

Using Theorem 2.4 we get the main result of \[MV2\].

###### Corollary 2.5.

(see Mansour and Vainshtein \[MV2, Theorem 2.1\]) For any nonempty pattern $`\tau \mathrm{SS}_k(132)`$, the generating function $`_\tau (x)`$ is a rational function in $`x`$ satisfying the relation

$$_\tau (x)=1+x\underset{d=0}{\overset{r}{}}(_{\pi ^d}(x)_{\pi ^{d1}}(x))_{\sigma ^d}(x).$$

###### Proof.

If adding Equations 2.2 and 2.3 we have

(2.6)
$$_\tau (x)_\tau (x)=x\underset{d=0}{\overset{r}{}}(_{\pi ^d}(x)_{\pi ^{d1}}(x))_{\sigma ^d}(x)+(_{\pi ^d}(x)_{\pi ^{d1}}(x))_{\sigma ^d}(x).$$

If adding Equations 2.4 and 2.5 we get

$$\begin{array}{c}_\tau (x)+_\tau (x)2=\hfill \\ =\frac{x}{2}\underset{d=0}{\overset{r}{}}(_{\pi ^d}(x)+_{\pi ^d}(x)_{\pi ^{d1}}(x)_{\pi ^{d1}}(x))(_{\sigma ^d}(x)_{\sigma ^d}(x))\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r}{}}(_{\pi ^d}(x)_{\pi ^d}(x)_{\pi ^{d1}}(x)+_{\pi ^{d1}}(x))(_{\sigma ^d}(x)+_{\sigma ^d}(x)).\hfill \end{array}$$

equivalently,

(2.7)
$$_\tau (x)+_\tau (x)2=x\underset{d=0}{\overset{r}{}}(_{\pi ^d}(x)_{\pi ^{d1}}(x))_{\sigma ^d}(x)(_{\pi ^d}(x)_{\pi ^{d1}}(x))_{\sigma ^d}(x).$$

Hence, if adding Equations 2.6 and 2.7 then we obtain that

$$_\tau (x)=1+x\underset{d=0}{\overset{r}{}}(_{\pi ^d}(x)_{\pi ^{d1}}(x))_{\sigma ^d}(x).$$

Rationality of $`_\tau (x)`$ for $`\tau \mathrm{}`$ follows easily by rationalities of $`𝔒_\tau (x)`$ and $`𝔈_\tau (x)`$ (see Theorem 2.4 and Equation 2.1). ∎

Our present aim is to find explicitly the generating functions $`𝔈_\tau (x)`$ and $`𝔒_\tau (x)`$ for several cases of $`\tau `$; thus we need the following notation. We denote the generating function $`𝔈_\tau (x)𝔒_\tau (x)`$ by $`𝔐_\tau (x)`$ for any pattern $`\tau `$.

###### Theorem 2.6.

For any $`\tau \mathrm{SS}_k(132)`$,

(2.8)
$$𝔐_\tau (x)𝔐_\tau (x)=x\underset{d=0}{\overset{r}{}}(𝔐_{\pi ^d}(x)𝔐_{\pi ^{d1}}(x))𝔐_{\sigma ^d}(x)+(𝔐_{\pi ^d}(x)𝔐_{\pi ^{d1}}(x))𝔐_{\sigma ^d}(x),$$

and

(2.9)
$$𝔐_\tau (x)+𝔐_\tau (x)2=x\underset{d=0}{\overset{r}{}}(𝔐_{\pi ^d}(x)𝔐_{\pi ^{d1}}(x))𝔐_{\sigma ^d}(x)(𝔐_{\pi ^d}(x)𝔐_{\pi ^{d1}}(x))𝔐_{\sigma ^d}(x).$$

###### Proof.

If subtracting Equation 2.3 from Equation 2.2 then we get Equation 2.8, and if subtracting Equation 2.5 from Equation 2.4 then we get Equation 2.9. ∎

###### Corollary 2.7.

Let $`\tau =(\beta ,k)\mathrm{SS}_k(132)`$. Then

$$𝔐_\tau (x)=\frac{2(1+x𝔐_\beta (x))}{(1x𝔐_\beta (x))^2+(1+x𝔐_\beta (x))^2}.$$

###### Proof.

Equation 2.8 for $`\tau =(\beta ,k)`$ yields

$$(1x𝔐_\beta (x))𝔐_\tau (x)(1+x𝔐_\beta (x))𝔐_\tau (x)=0,$$

and Equation 2.9 for $`\tau =(\beta ,k)`$ yields

$$(1+x𝔐_\beta (x))𝔐_\tau (x)+(1x𝔐_\beta (x))𝔐_\tau (x)=2.$$

Hence, the rest is easy to check by the above two equations. ∎

###### Example 2.8.

Let $`\tau =12`$ and $`\beta =1`$. Since $`𝔈_\beta (x)=1`$ and $`𝔒_\beta (x)=0`$ we get that $`𝔐_\beta (x)=1`$. Corollary 2.7 for $`\tau =12`$ yields

$$𝔐_{12}(x)=𝔈_{12}(x)𝔒_{12}(x)=\frac{2(1+x)}{(1x)^2+(1+x)^2}=\frac{1+x}{1+x^2}.$$

On the other hand, Corollary 2.5 together with Equation 2.1 we have

$$_{12}(x)=𝔈_{12}(x)+𝔒_{12}(x)=\frac{1}{1x}.$$

Hence,

$$𝔈_{12}(x)=\frac{1+x}{1x^4}\text{ and }𝔒_{12}(x)=\frac{x^2(1+x)}{1x^4}.$$

### 2.1. Pattern $`\tau =\mathrm{}`$

Let us consider the case $`\tau =\mathrm{}`$ as the first case which examined by Simion and Schmidt \[SimSch\].

###### Theorem 2.9.

We have

$$𝔈(x)=\frac{1}{2}(C(x)+1)+\frac{x}{2}C(x^2)\text{ and }𝔒(x)=\frac{1}{2}(C(x)1)\frac{x}{2}C(x^2).$$

In other words, for all $`n1`$,

1. $`|𝔈_{2n2}(132)|=\frac{1}{2}C_{2n2}`$;
2. $`|𝔒_{2n2}(132)|=\frac{1}{2}C_{2n2}`$;
3. $`|𝔈_{2n1}(132)|=\frac{1}{2}(C_{2n1}+C_{n1})`$;
4. $`|𝔒_{2n1}(132)|=\frac{1}{2}(C_{2n1}C_{n1})`$.

###### Proof.

First of all, let us define $`𝔐(x)=𝔐_{\mathrm{}}(x)`$, $`(x)=_{\mathrm{}}(x)`$, $`𝔈(x)=𝔈_{\mathrm{}}(x)`$, and $`𝔒(x)=𝔒_{\mathrm{}}(x)`$. Using the same arguments in the proof of Corollary 2.7 we get

$$\{\begin{array}{c}(1x𝔐(x))𝔐(x)(1+x𝔐(x))𝔐(x)=0,\hfill \\ (1+x𝔐(x))𝔐(x)+(1x𝔐(x))𝔐(x)=2,\hfill \end{array}$$

therefore,

$$𝔐(x)=𝔈(x)𝔒(x)=1+xC(x^2).$$

On the other hand, Corollary 2.5 for $`\tau =\mathrm{}`$ yields $`(x)=1+x(x)^2`$, so by Equation 2.1 we have that

$$(x)=𝔈(x)+𝔒(x)=C(x).$$

The rest is easy to check. ∎

### 2.2. Pattern $`\tau =12\mathrm{}k`$

Let us start be the following example.

###### Example 2.10.

(see Simion and Schmidt \[SimSch, Proposition 7\]) Corollary 2.7 together with Example 2.8 yield

$$𝔐_{123}(x)=1+x.$$

On the other hand, using the fact that $`_{123}(x)=𝔈_{123}(x)+𝔒_{123}(x)=\frac{1x}{12x}`$ (see \[SimSch\]) we get

$$𝔈_{123}(x)=1+x+\frac{x^2}{12x}\text{ and }𝔒_{123}(x)=\frac{x^2}{12x}.$$

The case of varying $`k`$ is more interesting. As an extension of Example 2.10, let us consider the case $`\tau =[k]`$, where we define $`[k]=12\mathrm{}k`$.

###### Theorem 2.11.

For all $`k1`$,

(i) $`𝔈_{[2k1]}(x)={\displaystyle \frac{1}{2}}(R_{2k1}(x)+xR_{k1}(x^2)+1)\text{ and }𝔈_{[2k]}(x)={\displaystyle \frac{1}{2}}\left(R_{2k}(x)+{\displaystyle \frac{(1+xR_k(x^2))R_k(x^2)}{1+x^2R_k^2(x^2)}}\right)`$,

(ii) $`𝔒_{[2k1]}(x)={\displaystyle \frac{1}{2}}(R_{2k1}(x)xR_{k1}(x^2)1)\text{ and }𝔒_{[2k]}(x)={\displaystyle \frac{1}{2}}\left(R_{2k}(x){\displaystyle \frac{(1+xR_k(x^2))R_k(x^2)}{1+x^2R_k^2(x^2)}}\right)`$.

###### Proof.

We use induction on $`k`$. Using Example 2.8 we get that $`𝔐_1(x)=1`$ and $`𝔐_{12}(x)=\frac{1+x}{1+x^2}`$. Now, let us fix $`k`$ and assume that

$$𝔐_{[2k1]}(x)=1+xR_{k1}(x^2)\text{ and }𝔐_{[2k]}(x)=\frac{(1+xR_k(x^2))R_k(x^2)}{1+x^2R_k^2(x^2)}.$$

Therefore, by the hypothesis of the induction and Corollary 2.7 we get

$`\begin{array}{c}𝔐_{[2k+1]}={\displaystyle \frac{2\left(1+\frac{x(1xR_k(x^2))R_k(x^2)}{1+x^2R_k^2(x^2)}\right)}{\left(1\frac{x(1+xR_k(x^2))R_k(x^2)}{1+x^2R_k^2(x^2)}\right)^2+\left(1+\frac{x(1xR_k(x^2))R_k(x^2)}{1+x^2R_k^2(x^2)}\right)^2}}\hfill \\ \\ ={\displaystyle \frac{\frac{2(1+xR_k(x^2))}{1+x^2R_k^2(x^2)}}{\frac{(1xR_k(x^2))^2}{(1+x^2R_k^2(x^2))^2}+\frac{(1+xR_k(x^2))^2}{(1+x^2R_k^2(x^2))^2}}}=1+xR_k(x^2).\hfill \end{array}`$

Also, by the induction hypothesis, Corollary 2.7, and Identity 1.2 we have that

$`\begin{array}{c}𝔐_{[2k+2]}={\displaystyle \frac{2(1+x(1xR_k(x^2)))}{\left(1x(1+xR_k(x^2))\right)^2+\left(1+x(1xR_k(x^2))\right)^2}}\hfill \\ \\ ={\displaystyle \frac{2\left(x+\frac{1}{R_{k+1}(x^2)}\right)}{\left(\frac{1}{R_{k+1}(x^2)}x\right)^2+\left(\frac{1}{R_{k+1}(x^2)}+x\right)^2}}\hfill \\ \\ ={\displaystyle \frac{2(1+xR_{k+1}(x^2))R_{k+1}(x^2)}{(1xR_{k+1}(x^2))^2+(1+xR_{k+1}(x^2))^2}}={\displaystyle \frac{(1+xR_{k+1}(x^2))R_{k+1}(x^2)}{1+x^2R_{k+1}^2(x^2)}}.\hfill \end{array}`$

Hence, for all $`k1`$,

$$𝔐_{[2k1]}(x)=1+xR_{k1}(x^2)\text{ and }𝔐_{[2k]}(x)=\frac{(1+xR_k(x^2))R_k(x^2)}{1+x^2R_k^2(x^2)}.$$

On the other hand, in \[CW\] (see also \[MV1, Kr, MV2, MV4\]) was proved

$$_{[m]}(x)=𝔈_{[m]}(x)+𝔒_{[m]}(x)=R_m(x),$$

for all $`m1`$. Hence, by the above two equations we get the desired result. ∎

###### Example 2.12.

Theorem 2.11 for $`k=3,4,5`$ yields

$$\begin{array}{c}e_{[5]}(n)o_{[5]}(n)=\frac{1}{2}\left(1+(1)^{n+1}\right);\hfill \\ e_{[7]}(n)o_{[7]}(n)=\sqrt{2}^{n5}\left(1+(1)^{n+1}\right);\hfill \\ e_{[9]}(n)o_{[9]}(n)=\frac{F_{n3}}{2}\left(1+(1)^{n+1}\right);\hfill \end{array}$$

where $`F_{n3}`$ is the $`(n3)`$th Fibonacci number.

### 2.3. Pattern $`\tau =213\mathrm{}k`$

Let us start by the following example.

###### Example 2.13.

(see Simion and Schmidt \[SimSch, Proposition 7\]) Corollary 2.7 for $`\tau =213`$ together with the fact that $`𝔐_{21}(x)=𝔈_{21}(x)=\frac{1}{1x}`$ and $`𝔒_{21}(x)=0`$ yield

$$𝔈_{213}(x)=\frac{(1x)(14x^2+4x^4)}{(12x)(13x^2+4x^4)},𝔒_{213}(x)=\frac{(1x)x^2}{(12x)(13x^2+4x^4)}.$$

The case of varying $`k`$ is more interesting. As an extension of Example 2.13, by using Corollary 2.7, and induction on $`k`$ (Similarly to Theorem 2.11) we get

###### Theorem 2.14.

For all $`k1`$,

$$\begin{array}{c}𝔐_{2134\mathrm{}(2k)}(x)=\frac{(1+2x)\left(U_{2k1}\left(\frac{1}{2x}\right)U_{2k}\left(\frac{1}{2x}\right)+\frac{x^2+2x1}{13x^2}\right)}{U_{2k}\left(\frac{1}{2x}\right)2xU_{2k+1}\left(\frac{1}{2x}\right)+\frac{4x^4}{13x^2}},\hfill \\ \\ 𝔐_{2134\mathrm{}(2k1)}(x)=\frac{(1+2x)\left(U_{2k2}\left(\frac{1}{2x}\right)U_{2k1}\left(\frac{1}{2x}\right)+\frac{x^2+2x1}{13x^2}\right)}{U_{2k1}\left(\frac{1}{2x}\right)2xU_{2k}\left(\frac{1}{2x}\right)\frac{2x(15x^2)}{13x^2}}.\hfill \end{array}$$

By Theorem 2.14 together with use of the fact that $`_{2134\mathrm{}k}(x)=R_k(x)`$ (see \[MV2, Theorem 2.6\]) we get

###### Corollary 2.15.

For all $`k1`$,

(i) $`𝔈_{2134\mathrm{}(2k)}(x)=\frac{1}{2}\left[\frac{U_{2k1}\left(\frac{1}{2\sqrt{x}}\right)}{\sqrt{x}U_{2k}\left(\frac{1}{2\sqrt{x}}\right)}+\frac{(1+2x)\left(U_{2k1}\left(\frac{1}{2x}\right)U_{2k}\left(\frac{1}{2x}\right)+\frac{x^2+2x1}{13x^2}\right)}{U_{2k}\left(\frac{1}{2x}\right)2xU_{2k+1}\left(\frac{1}{2x}\right)+\frac{4x^4}{13x^2}}\right]`$;

(ii) $`𝔒_{2134\mathrm{}(2k)}(x)=\frac{1}{2}\left[\frac{U_{2k1}\left(\frac{1}{2\sqrt{x}}\right)}{\sqrt{x}U_{2k}\left(\frac{1}{2\sqrt{x}}\right)}\frac{(1+2x)\left(U_{2k1}\left(\frac{1}{2x}\right)U_{2k}\left(\frac{1}{2x}\right)+\frac{x^2+2x1}{13x^2}\right)}{U_{2k}\left(\frac{1}{2x}\right)2xU_{2k+1}\left(\frac{1}{2x}\right)+\frac{4x^4}{13x^2}}\right]`$;

(iii) $`𝔈_{2134\mathrm{}(2k1)}(x)=\frac{1}{2}\left[\frac{U_{2k2}\left(\frac{1}{2\sqrt{x}}\right)}{\sqrt{x}U_{2k1}\left(\frac{1}{2\sqrt{x}}\right)}+\frac{(1+2x)\left(U_{2k2}\left(\frac{1}{2x}\right)U_{2k1}\left(\frac{1}{2x}\right)+\frac{x^2+2x1}{13x^2}\right)}{U_{2k1}\left(\frac{1}{2x}\right)2xU_{2k}\left(\frac{1}{2x}\right)\frac{2x(15x^2)}{13x^2}}\right]`$;

(iv) $`𝔒_{2134\mathrm{}(2k1)}(x)=\frac{1}{2}\left[\frac{U_{2k2}\left(\frac{1}{2\sqrt{x}}\right)}{\sqrt{x}U_{2k1}\left(\frac{1}{2\sqrt{x}}\right)}\frac{(1+2x)\left(U_{2k2}\left(\frac{1}{2x}\right)U_{2k1}\left(\frac{1}{2x}\right)+\frac{x^2+2x1}{13x^2}\right)}{U_{2k1}\left(\frac{1}{2x}\right)2xU_{2k}\left(\frac{1}{2x}\right)\frac{2x(15x^2)}{13x^2}}\right]`$.

### 2.4. Pattern $`(d+1)(d+2)\mathrm{}k12\mathrm{}d`$

In this subsection we consider the case $`\tau =[k,d]`$ where $`[k,d]=(d+1)(d+2)\mathrm{}k12\mathrm{}d`$. Following to Theorem 2.11, our present aim is to find explicitly the generating functions $`𝔈_\tau (x)`$ and $`𝔒_\tau (x)`$ where $`\tau =[k,d]`$; thus we need to consider four cases either $`k`$ even or odd, and either $`d`$ even or odd. First of all, using Theorem 2.6 for $`\tau =[k,d]`$ we state the following fact.

###### Lemma 2.16.

Let $`k2`$, $`1dk1`$, and $`\tau =[k,d]`$. Then

$$\{\begin{array}{c}(1+x𝔐_{[kd1]}(x)x𝔐_{[d]}(x))𝔐_\tau (x)+(1x𝔐_{[kd1]}(x)+x𝔐_{[d]}(x))𝔐_\tau (x)\hfill \\ =2+x𝔐_{[kd1]}(x)𝔐_{[d]}(x)x𝔐_{[kd1]}(x)𝔐_{[d]}(x),\hfill \\ \\ (1x𝔐_{[kd1]}(x)x𝔐_{[d]}(x))𝔐_\tau (x)(1+x𝔐_{[kd1]}(x)+x𝔐_{[d]}(x))𝔐_\tau (x)\hfill \\ =x𝔐_{[kd1]}(x)𝔐_{[d]}(x)x𝔐_{[kd1]}(x)𝔐_{[d]}(x).\hfill \end{array}$$

#### 2.4.1. $`k`$ and $`d`$ are odd numbers

Now, we ready to consider the first case $`k`$ and $`d`$ are odd numbers.

###### Theorem 2.17.

Let $`0dk`$. Then

$$𝔐_{[2k+1,2d+1]}(x)=1+xR_k(x^2).$$

###### Proof.

Theorem 2.11 yields $`𝔐_{2k2d1}(x)=1+xR_{kd1}(x^2)`$ and $`𝔐_{2d+1}(x)=1+xR_d(x^2)`$. Therefore, by use of Lemma 2.16 for $`\tau =[2k+1,2d+1]`$ we get

$$\{\begin{array}{c}𝔐_\tau (x)+𝔐_\tau (x)=2,\hfill \\ \\ (12xx^2R_d(x^2)x^2R_{kd1}(x^2))𝔐_\tau (x)(1+2xx^2R_d(x^2)x^2R_{kd1}(x^2))𝔐_\tau (x)\hfill \\ =2x2x^3R_d(x^2)R_{kd1}(x^2),\hfill \end{array}$$

so,

$$𝔐_\tau (x)=1+\frac{x(1x^2R_d(x^2)R_{kd1}(x^2))}{1x^2(R_d(x^2)+R_{kd1}(x^2))}.$$

By using the following identities (see \[MV2\])

(2.10)
$$1x^2R_p(x^2)R_q(x^2)=\frac{U_{p+q}\left(\frac{1}{2x}\right)}{U_p\left(\frac{1}{2x}\right)U_q\left(\frac{1}{2x}\right)}\text{ and }1x^2(R_p(x^2)+R_q(x^2))=\frac{xU_{p+q+1}\left(\frac{1}{2x}\right)}{U_p\left(\frac{1}{2x}\right)U_q\left(\frac{1}{2x}\right)},$$

we have

$$𝔐_\tau (x)=1+\frac{U_{k1}\left(\frac{1}{2x}\right)}{U_k\left(\frac{1}{2x}\right)},$$

and by Identity 1.1 we get the desired result. ∎

By Theorem 2.17 together with use of the equation $`_{[k,d]}(x)=R_k(x)`$ (see \[MV2, Theorem 2.4\]) we get

###### Corollary 2.18.

For all $`0dk`$,

$$𝔈_{[2k+1,2d+1]}(x)=\frac{1}{2}(R_{2k+1}(x)+xR_k(x^2)+1)\text{ and }𝔒_{[2k+1,2d+1]}(x)=\frac{1}{2}(R_{2k+1}(x)xR_k(x^2)1).$$

A comparison of Corollary 2.18 for values of $`d`$ suggests that there should exist a bijection between the sets $`𝔈_n(132,2\mathrm{}(2k+1)1)`$ and $`𝔈_n(132,(2d+2)(2d+3)\mathrm{}(2k+1)12\mathrm{}(2d+1))`$ for any $`d`$. However, we failed to produce such a bijection, and finding it remains a challenging open question.

#### 2.4.2. $`k`$ odd number and $`d`$ even number

Now, let us consider the case where $`k`$ odd number and $`d`$ even number.

###### Theorem 2.19.

Let $`1dk`$. Then

$$𝔐_{[2k+1,2d]}(x)=1+xR_k(x^2).$$

###### Proof.

Let $`m=kd`$; solving the system equations in Lemma 2.16 for $`\tau =[2k+1,2d]`$ together with use of Theorem 2.11 we get

$$𝔐_{[2k+1,2d]}(x)=1+\frac{x(R_m(x^2)+R_d(x^2)R_m(x^2)R_d(x^2))}{1x^2R_m(x^2)R_d(x^2)}.$$

Using Identities 2.10 we get the desired result. ∎

By Theorem 2.19 together with use of the equation $`_{[k,d]}(x)=R_k(x)`$ (see \[MV2, Theorem 2.4\]) we get

###### Corollary 2.20.

For all $`1dk`$,

$$𝔈_{[2k+1,2d]}(x)=\frac{1}{2}(R_{2k+1}+1+xR_k(x^2))\text{ and }𝔒_{[2k+1,2d]}(x)=\frac{1}{2}(R_{2k+1}1xR_k(x^2).$$

A comparison of Corollary 2.18 with Corollary 2.20 suggests that there should exist a bijection between the sets $`𝔈_n(132,12\mathrm{}(2k+1))`$ and $`𝔈_n(132,[2k+1,d])`$ for any $`d`$. However, we failed to produce such a bijection, and finding it remains a challenging open question.

#### 2.4.3. $`k`$ even number and $`d`$ odd number

Similarly as above subsections, we can consider the case where $`k`$ even number and $`d`$ odd number.

###### Theorem 2.21.

Let $`0dk1`$ and $`m=kd1`$. Then the generating function $`𝔐_{[2k,2d+1]}(x)`$ is given by

$$\frac{\left(1x^2(R_m(x^2)+R_d(x^2))+x(1x^2R_m(x^2)R_d(x^2))\right)(1+x^2R_m(x^2)R_d(x^2))}{1x^2(1+R_m^2(x^2))(1+x^2R_m^2(x^2))}.$$

By Theorem 2.21 together with use of the equation $`_{[k,d]}(x)=R_k(x)`$ (see \[MV2, Theorem 2.4\]) we get

###### Corollary 2.22.

Let $`0dk1`$ and $`m=kd1`$.

(i) The generating function $`𝔈_{[2k,2d+1]}(x)`$ is given by

$$\frac{1}{2}\left(R_{2k}(x)+\frac{\left(1x^2(R_m(x^2)+R_d(x^2))+x(1x^2R_m(x^2)R_d(x^2))\right)(1+x^2R_m(x^2)R_d(x^2))}{1x^2(1+R_m^2(x^2))(1+x^2R_m^2(x^2))}\right).$$

(ii) The generating function $`𝔒_{[2k,2d+1]}(x)`$ is given by

$$\frac{1}{2}\left(R_{2k}(x)\frac{\left(1x^2(R_m(x^2)+R_d(x^2))+x(1x^2R_m(x^2)R_d(x^2))\right)(1+x^2R_m(x^2)R_d(x^2))}{1x^2(1+R_m^2(x^2))(1+x^2R_m^2(x^2))}\right).$$

#### 2.4.4. $`k`$ and $`d`$ even numbers

Similarly as above subsections, we can consider the case where $`k`$ and $`d`$ even numbers.

###### Theorem 2.23.

Let $`1dk1`$ and $`m=kd1`$. Then the generating function $`𝔐_{[2k,2d]}(x)`$ is given by

$$\frac{1}{x}\frac{\left(1x^2(R_m(x^2)R_d(x^2))\right)\left(1x^2(R_d(x^2)+R_m(x^2))x(1x^2R_d(x^2)R_m(x^2))\right)}{x+x^3(1+x^2R_d^2(x^2))(12R_m(x^2)+x^2R_m^2(x^2))}.$$

By Theorem 2.23 together with use of the equation $`_{[k,d]}(x)=R_k(x)`$ (see \[MV2, Theorem 2.4\]) we get

###### Corollary 2.24.

Let $`1dk1`$ and $`m=kd1`$.

(i) The generating function $`𝔈_{[2k,2d+1]}(x)`$ is given by

$$\frac{1}{2}(R_{2k}(x)+\frac{1}{x}\frac{\left(1x^2(R_m(x^2)R_d(x^2))\right)\left(1x^2(R_d(x^2)+R_m(x^2))x(1x^2R_d(x^2)R_m(x^2))\right)}{x+x^3(1+x^2R_d^2(x^2))(12R_m(x^2)+x^2R_m^2(x^2))}.$$

(ii) The generating function $`𝔒_{[2k,2d+1]}(x)`$ is given by

$$\frac{1}{2}\left(R_{2k}(x)\frac{1}{x}+\frac{\left(1x^2(R_m(x^2)R_d(x^2))\right)\left(1x^2(R_d(x^2)+R_m(x^2))x(1x^2R_d(x^2)R_m(x^2))\right)}{x+x^3(1+x^2R_d^2(x^2))(12R_m(x^2)+x^2R_m^2(x^2))}\right).$$

### 2.5. Wedge patterns

For a further generalization of the results in the pervious subsections, consider the following definition. We say that $`\tau \mathrm{SS}_k`$ is a wedge pattern if it can be represented as $`\tau =(\tau ^1,\rho ^1,\mathrm{},\tau ^r,\rho ^r)`$ so that each of $`\tau ^i`$ is nonempty, $`(\rho ^1,\rho ^2,\mathrm{},\rho ^r)`$ is a layered permutation of $`1,\mathrm{},s`$ for some $`s`$, and $`(\tau ^1,\tau ^2,\mathrm{},\tau ^r)=(s+1,s+2,\mathrm{},k)`$. For example, $`645783912`$ and $`456378129`$ are wedge patterns. Evidently, $`[k,d]`$ is a wedge pattern for any $`d`$. We say that $`\tau \mathrm{SS}_k`$ is an odd-wedge pattern if it a wedge pattern such that the length of $`(\tau ^1,\rho ^1,\mathrm{},\tau ^p,\rho ^p)`$ is given by odd number for all $`p=1,2,\mathrm{},r`$. For example, $`23145`$ and $`34251`$ are odd-wedge patterns. Evidently, $`[2k+1,d]`$ is an odd-wedge pattern for any $`d`$.

###### Theorem 2.25.

$`𝔐_\tau (x)=1+xR_k(x^2)`$ for any odd-wedge pattern $`\tau \mathrm{SS}_{2k+1}(132)`$.

###### Proof.

We proceed by induction on $`r`$. If $`r=1`$ then $`\tau =[2k+1,d]`$ for some $`d`$, and the result is true by Theorems 2.17 and 2.19. For an arbitrary $`r>1`$, $`\tau `$ looks like either

$$\tau =(\tau ^{},2p+2d+2,2p+2d+3,\mathrm{},2k+1,1,2,\mathrm{},2d),$$

or

$$\tau =(\tau ^{},2p+2d+3,2p+2d+4,\mathrm{},2k+1,1,2,\mathrm{},2d+1),$$

for some $`d`$ and $`p`$, where $`\tau ^{}=(\tau ^1,\rho ^1,\mathrm{},\tau ^{r1},\rho ^{r1})`$.

The first case; $`\tau ^{}`$ contains $`2p+1`$ elements and it is an odd-wedge pattern, so by induction $`𝔐_\tau ^{}(x)=1+xR_p(x^2)`$, so Corollary 2.7 gives

$$𝔐_{(\tau ^{},2p+2d+2)}(x)=\frac{(1+xR_{p+1}(x^2))R_{p+1}(x^2)}{1+x^2R_{p+1}^2(x^2)},$$

and then

$$𝔐_{(\tau ^{},2p+2d+2,2p+2d+3)}(x)=1+xR_{p+1}(x^2).$$

Therefore, by induction we have

$$𝔐_{(\tau ^{},2p+2d+2,2p+2d+3,\mathrm{},2k)}(x)=\frac{(1+xR_{kd}(x^2))R_{kd}(x^2)}{1+x^2R_{kd}^2(x^2)}.$$

Hence, Theorem 2.6 for $`\tau =(\tau ^{},2p+2d+2,2p+2d+3,\mathrm{},2k+1,1,2,\mathrm{},2d)`$ yields (similarly as Theorem 2.19)

$$𝔐_\tau (x)=1+\frac{x(R_{kd}(x^2)+R_d(x^2)R_{kd}(x^2)R_d(x^2))}{1x^2R_{kd}(x^2)R_d(x^2)},$$

and using Identities 2.10 we have that $`𝔐_\tau (x)=1+xR_k(x^2)`$.

The second case; similarly as the first case we have that

$$𝔐_{(\tau ^{},2p+2d+3,2p+2d+4,\mathrm{},2k)}(x)=1+xR_{kd1}(x^2).$$

Hence, Theorem 2.6 for $`\tau =(\tau ^{},2p+2d+3,2p+2d+4,\mathrm{},2k+1,1,2,\mathrm{},2d+1)`$ yields (similarly as Theorem 2.17)

$$𝔐_\tau (x)=1+\frac{x(1x^2R_d(x^2)R_{kd1}(x^2))}{1x^2(R_d(x^2)+R_{kd1}(x^2))},$$

and using Identities 2.10 we have that $`𝔐_\tau (x)=1+xR_k(x^2)`$. ∎

A comparison of Theorem 2.11 with Theorem 2.25 suggests that there should exist a bijection between the sets $`𝔈_n(132,12\mathrm{}(2k+1))`$ \[respectively; $`𝔒_n(132,12\mathrm{}(2k+1))`$\] and $`𝔈_n(132,\tau )`$ \[respectively; $`𝔒_n(132,\tau )`$\] for any odd-wedge pattern $`\tau `$. However, we failed to produce such a bijection, and finding it remains a challenging open question.

###### Corollary 2.26.

For any odd-wedge pattern $`\tau \mathrm{SS}_{2k+1}(132)`$,

$$𝔈_\tau (x)=\frac{1}{2}(R_{2k+1}(x)+xR_k(x^2)+1)\text{ and }𝔒_\tau (x)=\frac{1}{2}(R_{2k+1}(x)xR_k(x^2)1).$$

## 3. Containing a pattern exactly once

Let $`e_{\tau ;r}(n)`$ \[respectively; $`o_{\tau ;r}(n)`$\] denote the number of even \[respectively; odd\] permutations in $`\mathrm{SS}_n(132)`$ that contain $`\tau \mathrm{SS}_k(132)`$ exactly $`r`$ times, and $`e_{\tau ;1}^\rho (n)`$ \[respectively; $`o_{\tau ;r}^\rho (n)`$\] denote the number of even \[respectively; odd\] permutations in $`𝔈_n(132,\rho )`$ that contain $`\tau \mathrm{SS}_k(132)`$ exactly $`r`$ times. We denote by $`𝔈_{\tau ;r}(x)`$ and $`𝔈_{\tau ;r}^\rho (x)`$ \[respectively; $`𝔒_{\tau ;r}(x)`$ and $`𝔒_{\tau ;r}^\rho (x)`$\] the corresponding ordinary generating functions. Using the argument proof of Theorem 2.4 we get as follows.

###### Theorem 3.1.

For any $`\tau =(\tau ^0,m_0,\mathrm{},\tau ^r,m_r)`$ be the canonical decomposition of nonempty $`\tau S_k(132)`$, then

(3.1)
$$\begin{array}{c}𝔈_{\tau ;1}(x)𝔈_{\tau ;1}(x)=x\underset{d=0}{\overset{r+1}{}}𝔈_{\pi ^{d1};1}^{\pi ^d}(x)𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x)+𝔈_{\pi ^{d1};1}^{\pi ^d}(x)𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x)+\hfill \\ +x\underset{d=0}{\overset{r+1}{}}𝔒_{\pi ^{d1};1}^{\pi ^d}(x)𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x)+𝔒_{\pi ^{d1};1}^{\pi ^d}(x)𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x),\hfill \end{array}$$

(3.2)
$$\begin{array}{c}𝔒_{\tau ;1}(x)𝔒_{\tau ;1}(x)=x\underset{d=0}{\overset{r+1}{}}𝔈_{\pi ^{d1};1}^{\pi ^d}(x)𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x)+𝔈_{\pi ^{d1};1}^{\pi ^d}(x)𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x)+\hfill \\ +x\underset{d=0}{\overset{r+1}{}}𝔒_{\pi ^{d1};1}^{\pi ^d}(x)𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x)+𝔒_{\pi ^{d1};1}^{\pi ^d}(x)𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x),\hfill \end{array}$$

(3.3)
$$\begin{array}{c}𝔈_{\tau ;1}(x)+𝔈_{\tau ;1}(x)=\frac{x}{2}\underset{d=0}{\overset{r+1}{}}(𝔈_{\pi ^{d1};1}^{\pi ^d}(x)+𝔈_{\pi ^{d1};1}^{\pi ^d}(x))(𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x)𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x))+\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r+1}{}}(𝔒_{\pi ^{d1};1}^{\pi ^d}(x)+𝔒_{\pi ^{d1};1}^{\pi ^d}(x))(𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x)𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x))+\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r+1}{}}(𝔈_{\pi ^{d1};1}^{\pi ^d}(x)𝔈_{\pi ^{d1};1}^{\pi ^d}(x))(𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x)+𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x))+\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r+1}{}}(𝔒_{\pi ^{d1};1}^{\pi ^d}(x)𝔒_{\pi ^{d1};1}^{\pi ^d}(x))(𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x)+𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x)),\hfill \end{array}$$

and

(3.4)
$$\begin{array}{c}𝔒_{\tau ;1}(x)+𝔒_{\tau ;1}(x)=\frac{x}{2}\underset{d=0}{\overset{r+1}{}}(𝔈_{\pi ^{d1};1}^{\pi ^d}(x)+𝔈_{\pi ^{d1};1}^{\pi ^d}(x))(𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x)𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x))+\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r+1}{}}(𝔒_{\pi ^{d1};1}^{\pi ^d}(x)+𝔒_{\pi ^{d1};1}^{\pi ^d}(x))(𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x)𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x))+\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r+1}{}}(𝔈_{\pi ^{d1};1}^{\pi ^d}(x)𝔈_{\pi ^{d1};1}^{\pi ^d}(x))(𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x)+𝔒_{\sigma ^d;1}^{\sigma ^{d1}}(x))+\hfill \\ +\frac{x}{2}\underset{d=0}{\overset{r+1}{}}(𝔒_{\pi ^{d1};1}^{\pi ^d}(x)𝔒_{\pi ^{d1};1}^{\pi ^d}(x))(𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x)+𝔈_{\sigma ^d;1}^{\sigma ^{d1}}(x)),\hfill \end{array}$$

###### Remark 3.2.

Strictly speaking, Theorem 3.1, unlike Theorem 2.4, is not a recursion for $`𝔈_{\tau ;1}(x)`$ or $`𝔒_{\tau ;1}(x)`$, since it involves functions of type $`𝔈_{\tau ;1}^\rho (x)`$ and $`𝔒_{\tau ;1}^\rho (x)`$ (unless $`r=0`$; see the next subsection). However, for these functions one can write further recursions involving similar objects. For example,

$$\begin{array}{c}𝔈_{\pi ^{j1};1}^{pi^j}(x)𝔈_{\pi ^{j1};1}^{\pi ^j}(x)=x\underset{i=0}{\overset{j}{}}𝔈_{\pi ^{i1};1}^{\pi ^i}(x)𝔈_{\sigma _{j1}^i;1}^{\sigma _{j1}^{i1}}(x)+𝔈_{\pi ^{i1};1}^{\pi ^i}(x)𝔈_{\sigma _{j1}^i;1}^{\sigma _{j1}^{i1}}(x)+\hfill \\ +x\underset{i=0}{\overset{j}{}}𝔒_{\pi ^{i1};1}^{\pi ^i}(x)𝔒_{\sigma _{j1}^i;1}^{\sigma _{j1}^{i1}}(x)+𝔒_{\pi ^{i1};1}^{\pi ^i}(x)𝔒_{\sigma _{j1}^i;1}^{\sigma _{j1}^{i1}}(x),\hfill \end{array}$$

and

$$\begin{array}{c}𝔒_{\pi ^{j1};1}^{pi^j}(x)𝔒_{\pi ^{j1};1}^{\pi ^j}(x)=x\underset{i=0}{\overset{j}{}}𝔈_{\pi ^{i1};1}^{\pi ^i}(x)𝔒_{\sigma _{j1}^i;1}^{\sigma _{j1}^{i1}}(x)+𝔈_{\pi ^{i1};1}^{\pi ^i}(x)𝔒_{\sigma _{j1}^i;1}^{\sigma _{j1}^{i1}}(x)+\hfill \\ +x\underset{i=0}{\overset{j}{}}𝔒_{\pi ^{i1};1}^{\pi ^i}(x)𝔈_{\sigma _{j1}^i;1}^{\sigma _{j1}^{i1}}(x)+𝔒_{\pi ^{i1};1}^{\pi ^i}(x)𝔈_{\sigma _{j1}^i;1}^{\sigma _{j1}^{i1}}(x),\hfill \end{array}$$

where $`\sigma _{j1}^i`$ is the $`i`$th suffix of $`\pi ^{j1}`$. Though we have not succeeded to write down a complete set of equations in the general case (for $`𝔈_\tau ^\rho (x)`$ and $`𝔒_\tau ^\rho (x)`$), it is possible to do this in certain particular cases.

As a corollary of Theorem 3.1 we obtain the main result of \[MV2\].

###### Corollary 3.3.

(see Mansour and Vainshtein \[MV2, Theorem 3.1\]) Let $`\tau =(\tau ^0,m_0,\mathrm{},\tau ^r,m_r)`$ be the canonical decomposition of $`\tau S_k(132)`$, then for all $`r0`$,

$$G_\tau (x)=x\underset{j=0}{\overset{r+1}{}}G_{\pi ^{j1}}^{\pi ^j}(x)G_{\sigma ^j}^{\sigma ^{j1}}(x),$$

where $`G_\tau (x)`$ is the generating function for the number of permutations in $`\mathrm{SS}_n(132)`$ containing $`\tau `$ exactly once, and $`G_\tau ^\rho (x)`$ is the generating function for the number of permutations in $`\mathrm{SS}_n(132,\rho )`$ containing $`\tau `$ exactly once.

###### Proof.

If adding Equations 3.1 and 3.2 together with use of the fact that $`G_\tau ^\rho (x)=𝔈_\tau ^\rho (x)+𝔒_\tau ^\rho (x)`$ for any $`\tau `$ and $`\rho `$, we get

(3.5)
$$G_\tau (x)G_\tau (x)=x\underset{d=0}{\overset{r+1}{}}G_{\pi ^{d1}}^{\pi ^d}(x)G_{\sigma ^d}^{\sigma ^{d1}}(x)+G_{\pi ^{d1}}^{\pi ^d}(x)G_{\sigma ^d}^{\sigma ^{d1}}(x),$$

and if adding Equations 3.3 and 3.4 we have

(3.6)
$$G_\tau (x)+G_\tau (x)=x\underset{d=0}{\overset{r+1}{}}G_{\pi ^{d1}}^{\pi ^d}(x)G_{\sigma ^d}^{\sigma ^{d1}}(x)G_{\pi ^{d1}}^{\pi ^d}(x)G_{\sigma ^d}^{\sigma ^{d1}}(x).$$

Hence, by adding the Equations 3.5 and 3.6 we get the desired result. ∎

Our present aim is to find explicitly the generating functions $`𝔈_{\tau ;1}(x)`$ and $`𝔒_{\tau ;1}(x)`$ for several patterns $`\tau `$, thus we the following notations. We define $`𝔐_{\tau ;r}(x)=𝔈_{\tau ;r}(x)𝔒_{\tau ;r}(x)`$ and $`𝔐_{\tau ;r}^\rho (x)=𝔈_{\tau ;r}^\rho (x)𝔒_{\tau ;r}^\rho (x)`$ for any $`\tau `$ and $`\rho `$, and $`𝔐_{\mathrm{};r}^\rho (x)=𝔐_\rho (x)`$ for any $`\rho `$.

###### Theorem 3.4.

For any $`\tau =(\tau ^0,m_0,\mathrm{},\tau ^r,m_r)`$ be the canonical decomposition of nonempty $`\tau S_k(132)`$, then

(3.7)
$$𝔐_{\tau ;1}(x)𝔐_{\tau ;1}(x)=x\underset{d=0}{\overset{r+1}{}}𝔐_{\pi ^{d1};1}^{\pi ^d}(x)𝔐_{\sigma ^d;1}^{\sigma ^{d1}}(x)+𝔐_{\pi ^{d1};1}^{\pi ^d}(x)𝔐_{\sigma ^d;1}^{\sigma ^{d1}}(x),$$

and

(3.8)
$$𝔐_{\tau ;1}(x)+𝔐_{\tau ;1}(x)=x\underset{d=0}{\overset{r+1}{}}𝔐_{\pi ^{d1};1}^{\pi ^d}(x)𝔐_{\sigma ^d;1}^{\sigma ^{d1}}(x)𝔐_{\pi ^{d1};1}^{\pi ^d}(x)𝔐_{\sigma ^d;1}^{\sigma ^{d1}}(x).$$

###### Proof.

If subtracting Equation 3.2 from Equation 3.1 then we get Equation 3.7, and if subtracting Equation 3.4 from Equation 3.3 then we get Equation 3.8. ∎

### 3.1. Pattern $`\tau =[k]`$

One can try to obtain results similar to Theorems 2.11, 2.14, and 2.17-2.23, but expressions involved become extremely cumbersome. So we just consider a simplest wedge pattern, which is the pattern $`[k]`$.

###### Theorem 3.5.

For all $`m0`$,

(i) $`𝔐_{[2m+1];1}(x)={\displaystyle \frac{x}{U_m^2\left(\frac{1}{2x}\right)}}`$,

(ii) $`𝔐_{[2m+2];1}(x)={\displaystyle \frac{x^2R_{m+1}^2(x^2)}{(1+x^2R_{m+1}^2(x^2))^2U_m^2\left(\frac{1}{2x}\right)}}\left(1+2xR_{m+1}(x^2)x^2R_{m+1}^2(x^2)\right)`$.

###### Proof.

Let $`\tau =[k]`$, then $`r=0`$, and it follows from Theorem 3.4 that

(3.9)
$$\begin{array}{c}𝔐_{[k];1}(x)𝔐_{[k];1}(x)=x𝔐_{[k1]}(x)𝔐_{[k];1}(x)+x𝔐_{[k1]}(x)𝔐_{[k];1}(x)\hfill \\ +x𝔐_{[k1];1}(x)𝔐_{[k]}(x)+x𝔐_{[k1];1}(x)𝔐_{[k]}(x),\hfill \\ \\ 𝔐_{[k];1}(x)+𝔐_{[k];1}(x)=x𝔐_{[k1]}(x)𝔐_{[k];1}(x)x𝔐_{[k1]}(x)𝔐_{[k];1}(x)\hfill \\ +x𝔐_{[k1];1}(x)𝔐_{[k]}(x)x𝔐_{[k1];1}(x)𝔐_{[k]}(x).\hfill \end{array}$$

Now, let us consider two cases either $`k=2m`$ or $`k=2m+1`$ as follows. (i) Let $`k=2m`$, Equation 3.9 for $`k=2m`$ and Theorem 2.11 together with Identity 1.2 we get

$$\begin{array}{c}(1xR_m(x^2))𝔐_{[2m];1}(x)(1+xR_m(x^2))𝔐_{[2m];1}(x)=\hfill \\ =\frac{x(1+xR_m(x^2))R_m^2(x^2)}{1+x^2R_m^2(x^2)}𝔐_{[2m1];1}(x)+\frac{x(1xR_m(x^2))R_m^2(x^2)}{1+x^2R_m^2(x^2)}𝔐_{[2m1];1}(x)\hfill \\ \\ (1+xR_m(x^2))𝔐_{[2m];1}(x)+(1xR_m(x^2))𝔐_{[2m];1}(x)=\hfill \\ =\frac{x(1xR_m(x^2))R_m^2(x^2)}{1+x^2R_m^2(x^2)}𝔐_{[2m1];1}(x)\frac{x(1+xR_m(x^2))R_m^2(x^2)}{1+x^2R_m^2(x^2)}𝔐_{[2m1];1}(x).\hfill \end{array}$$

If solving the above system of Equations, then using Identity 1.2 we have

(3.10)
$$𝔐_{[2m];1}(x)=\frac{xR_m^2(x^2)}{(1+x^2R_m^2(x^2))^2}\left((1x^2R_m^2(x^2))𝔐_{[2m1];1}(x)2xR_m(x^2)𝔐_{[2m1];1}(x)\right).$$

(ii) Let $`k=2m+1`$, similarly as first case (i) we get

(3.11)
$$𝔐_{[2m+1];1}(x)=x\left((1x^2R_m^2(x^2))𝔐_{[2m];1}(x)2xR_m(x^2)𝔐_{[2m];1}(x)\right).$$

If using Equations 3.10 and 3.11, then we have that for $`m1`$,

$$𝔐_{[2m+1];1}(x)=x^2R_m^2(x^2)𝔐_{[2m1];1}(x).$$

Besides, by definitions we have that $`𝔐_{[1];1}(x)=x`$, hence $`𝔐_{[2m+1];1}(x)=\frac{x}{U_m^2\left(\frac{1}{2x}\right)}`$. Using Equation 3.10 together with the property $`U_p^2(t)=U_p^2(t)`$ for all $`p`$, we get the desired result. ∎

Theorem 3.5 together with the fact that the generating function for the number permutations in $`\mathrm{SS}_n(132)`$ containing $`[k]`$ exactly once is given by $`\frac{1}{U_k^2\left(\frac{1}{2\sqrt{x}}\right)}`$ (see \[MV1\]) we have

###### Corollary 3.6.

For all $`m0`$,

(i) $`𝔈_{[2m+1];1}(x)=\frac{1}{2}\left(\frac{1}{U_{2m+1}^2\left(\frac{1}{2\sqrt{x}}\right)}+\frac{x}{U_m^2\left(\frac{1}{2x}\right)}\right)`$,

(ii) $`𝔒_{[2m+1];1}(x)=\frac{1}{2}\left(\frac{1}{U_{2m+1}^2\left(\frac{1}{2\sqrt{x}}\right)}\frac{x}{U_m^2\left(\frac{1}{2x}\right)}\right)`$,

(iii) $`𝔈_{[2m+2];1}(x)=\frac{1}{2}\left(\frac{1}{U_{2m+2}^2\left(\frac{1}{2\sqrt{x}}\right)}+\frac{x^2R_{m+1}^2(x^2)}{(1+x^2R_{m+1}^2(x^2))^2U_m^2\left(\frac{1}{2x}\right)}\left(1+2xR_{m+1}(x^2)x^2R_{m+1}^2(x^2)\right)\right)`$,

(iv) $`𝔒_{[2m+2];1}(x)=\frac{1}{2}\left(\frac{1}{U_{2m+2}^2\left(\frac{1}{2\sqrt{x}}\right)}\frac{x^2R_{m+1}^2(x^2)}{(1+x^2R_{m+1}^2(x^2))^2U_m^2\left(\frac{1}{2x}\right)}\left(1+2xR_{m+1}(x^2)x^2R_{m+1}^2(x^2)\right)\right)`$.

## 4. Furthermore results

In this section, we present several directions to generalize and to extend the results of the previous sections.

### 4.1. Statistics on the set $`𝔈_n(132)`$ and on the set $`𝔒_n(132)`$

The first of these directions is to consider statistics on the set $`𝔈_n(132)`$ (or on the set $`𝔒_n(132)`$). First of all, let us define

$$\begin{array}{c}(x_1,x_2,\mathrm{})=_{n0}_{\pi \mathrm{SS}_n(132)}_{j1}x_j^{12\mathrm{}j(\pi )},\hfill \\ 𝔈(x_1,x_2,\mathrm{})=_{n0}_{\pi 𝔈_n(132)}_{j1}x_j^{12\mathrm{}j(\pi )},\hfill \\ 𝔒(x_1,x_2,\mathrm{})=_{n0}_{\pi 𝔒_n(132)}_{j1}x_j^{12\mathrm{}j(\pi )},\hfill \end{array}$$

where $`12\mathrm{}j(\pi )`$ is the number occurrences of the pattern $`12\mathrm{}j`$ in $`\pi `$. We denote the function $`𝔈(x_1,x_2,\mathrm{})𝔒(x_1,x_2,\mathrm{})`$ by $`𝔐(x_1,x_2,\mathrm{})`$. Using the same arguments in the proof Corollary 2.7 together with the main result of \[BCS\] we get as follows.

###### Theorem 4.1.

We have

$$𝔐(x_1,x_2,\mathrm{})=\frac{2(1+x_1𝔐(x_1x_2,x_2x_3,\mathrm{}))}{(1x_1𝔐(x_1x_2,x_2x_3,\mathrm{}))^2+(1+x_1𝔐(x_1x_2,x_2x_3,\mathrm{}))^2},$$

and

$$(x_1,x_2,\mathrm{})=𝔈(x_1,x_2,\mathrm{})+𝔒(x_1,x_2,\mathrm{})=\frac{1}{1x_1(x_1x_2,x_2x_3,\mathrm{})}.$$

An application for Theorem 4.1 we get the distribution of the number right to left maxima on the set $`𝔈_n(132)`$ or on the set $`𝔒_n(132)`$. Let $`\pi \mathrm{SS}_n`$; we say $`\pi _j`$ is right to left maxima of $`\pi `$ if $`\pi _j>\pi _i`$ for all $`j<i`$. The number of right to left maxima of $`\pi `$ we denote by $`rlm_\pi `$.

###### Corollary 4.2.

We have

(i) $`\underset{n0}{}\underset{\pi 𝔈_n(132)}{}x^ny^{rlm_\pi }={\displaystyle \frac{1}{2}}\left({\displaystyle \frac{1}{1xyC(x)}}+{\displaystyle \frac{1+xyx^2yC(x^2)}{12x^2yC(x^2)+x^2y^2C(x^2)}}\right),`$

(ii) $`\underset{n0}{}\underset{\pi 𝔒_n(132)}{}x^ny^{rlm_\pi }={\displaystyle \frac{1}{2}}\left({\displaystyle \frac{1}{1xyC(x)}}{\displaystyle \frac{1+xyx^2yC(x^2)}{12x^2yC(x^2)+x^2y^2C(x^2)}}\right).`$

###### Proof.

Using Theorem 2.9 together with definitions we have $`𝔐(x,1,1,\mathrm{})=1+xC(x^2)`$. So, Theorem 4.1 yields

$$𝔐(xy,y^1,y,\mathrm{})=𝔈(xy,y^1,y,\mathrm{})𝔒(xy,y^1,y,\mathrm{})=\frac{1+xyx^2yC(x^2)}{12x^2yC(x^2)+x^2y^2C(x^2)},$$

and

$$(xy,y^1,y,y^1,\mathrm{})=𝔈(xy,y^1,y,y^1,\mathrm{})+𝔒(xy,y^1,y,y^1,\mathrm{})=\frac{1}{1xyC(x)}.$$

On the other hand, using \[BCS, Proposition 5\] we get

$$\begin{array}{c}\underset{n0}{}\underset{\pi \mathrm{SS}_n(132)}{}x^ny^{rlm_\pi }=(xy,y^1,y,y^1,\mathrm{}),\hfill \\ \underset{n0}{}\underset{\pi 𝔈_n(132)}{}x^ny^{rlm_\pi }=𝔈(xy,y^1,y,y^1,\mathrm{}),\hfill \\ \underset{n0}{}\underset{\pi 𝔒_n(132)}{}x^ny^{rlm_\pi }=𝔒(xy,y^1,y,y^1,\mathrm{}).\hfill \end{array}$$

By combining all these equations we get the desired result. ∎

An another application for Theorem 4.1 we get an explicit expressions for the generating function $`_{n0}_{\pi 𝔈_n(132)}x^ny^{12\mathrm{}k(\pi )}`$ for given $`k`$ and $`12\mathrm{}k(\pi )`$. The following result is true by using Theorem 4.1.

###### Theorem 4.3.

Let $`k1`$; we have

(i) $`𝔐_{[2k+1];0}(x)=1+xR_k(x^2)=\frac{U_k\left(\frac{1}{2x}\right)+U_{k1}\left(\frac{1}{2x}\right)}{U_k\left(\frac{1}{2x}\right)}`$;

(ii) $`𝔐_{[2k+1];1}(x)=\frac{x}{U_k^2\left(\frac{1}{2x}\right)}`$;

(iii) $`𝔐_{[2k+1];2}(x)=\frac{x^2}{U_k^2\left(\frac{1}{2x}\right)}(xR_k(x^2)1)=\frac{x^2(U_{k1}\left(\frac{1}{2x}\right)U_k\left(\frac{1}{2x}\right))}{U_k^3\left(\frac{1}{2x}\right)}`$.

Therefore, by \[MV1, Theorem 4.1\] together with the above theorem we get the number of even (or odd) permutations avoiding $`132`$ and containing $`[2k+1]`$ exactly $`r=0,1,2`$. For example, for $`r=2`$ we get (for $`r=1`$ see Corollary 3.6)

###### Corollary 4.4.

Let $`k1`$. Then

(i) the generating function for the number $`132`$-avoiding even permutations containing $`12\mathrm{}(2k+1)`$ exactly twice is given by

$$\frac{1}{2}\left(\frac{\sqrt{x}U_{k1}\left(\frac{1}{2\sqrt{x}}\right)}{U_k^3\left(\frac{1}{2\sqrt{x}}\right)}+\frac{x^2(U_{k1}\left(\frac{1}{2x}\right)U_k\left(\frac{1}{2x}\right))}{U_k^3\left(\frac{1}{2x}\right)}\right),$$

(ii) the generating function for the number $`132`$-avoiding odd permutations containing $`12\mathrm{}(2k+1)`$ exactly twice is given by

$$\frac{1}{2}\left(\frac{\sqrt{x}U_{k1}\left(\frac{1}{2\sqrt{x}}\right)}{U_k^3\left(\frac{1}{2\sqrt{x}}\right)}\frac{x^2(U_{k1}\left(\frac{1}{2x}\right)U_k\left(\frac{1}{2x}\right))}{U_k^3\left(\frac{1}{2x}\right)}\right),$$

### 4.2. Two restrictions

The second of these directions is to consider more than one additional restriction. For example, the following results is true. Let $`B_{\tau ^1,\tau ^2}(x)`$ be the generating function for the number of even permutations in $`𝔈_n(132,\tau ^1,\tau ^2)`$. Assume $`\tau ^1=12\mathrm{}k`$ and $`\tau ^2=2134\mathrm{}k`$, then we get as follows.

###### Theorem 4.5.

Let $`V_m(x)=(1xW_m(x))W_{m+1}(x)`$ such that

$$W_m(x)=\frac{(1x^2R_{m2}(x)R_{m3}(x))R_{m1}(x)}{1x^2R_{m1}(x)R_{m2}(x)}.$$

Then, for all $`k2`$,

1. The generating function $`𝔈_{12\mathrm{}2k,2134\mathrm{}2k}(x)`$ is given by

$$\frac{1}{2}\left(W_{2k}(x)+1+xR_k(x^2)\right).$$
2. The generating function $`𝔒_{12\mathrm{}2k,2134\mathrm{}2k}(x)`$ is given by

$$\frac{1}{2}\left(W_{2k}(x)1xR_k(x^2)\right).$$
3. The generating function $`𝔈_{12\mathrm{}(2k+1),2134\mathrm{}(2k+1)}(x)`$ is given by

$$\frac{1}{2}\left(\frac{2(1+xR_{k+1}(x^2))V_{2k}(x)xR_{k+1}(x^2)V_{2k}(x)}{1+x^2R_{k+1}^2(x^2)}R_{k+1}(x^2)+W_{2k+1}(x)\right).$$
4. The generating function $`𝔒_{12\mathrm{}(2k+1),2134\mathrm{}(2k+1)}(x)`$ is given by

$$\frac{1}{2}\left(W_{2k+1}(x)\frac{2(1+xR_{k+1}(x^2))V_{2k}(x)xR_{k+1}(x^2)V_{2k}(x)}{1+x^2R_{k+1}^2(x^2)}R_{k+1}(x^2)\right).$$

Another example to consider the case of avoiding $`\tau ^1`$ and counting occurrences of $`\tau ^2`$. For example, the following result is true. Let $`𝔈_{\tau ^1}^{\tau ^2}(x,y)`$ \[respectively; $`𝔒_{\tau ^1}^{\tau ^2}(x,y)`$\] be the generating function for the number of even \[respectively; odd\] permutations in $`\mathrm{SS}_n(132,\tau ^2)`$ containing $`\tau ^1`$ exactly $`r`$ times.

###### Theorem 4.6.

Let $`G_k(x,y)=𝔈_{[k]}^{[k+1]}(x,y)𝔒_{[k]}^{[k+1]}(x,y)`$. For all $`k1`$,

$$G_k(x,y)=1+x\frac{D_{k1}(x)x^k+B_k(x)(1y)+x^2(D_{k3}(x)x^{k2})(1y)^2}{D_k(x)+E_k(x)(1y)+x^2D_{k2}(x)(1y)^2},$$

where $`E_m(x)=((1)^m1)x^{m+1}`$; $`B_{2m}(x)=x^{2m1}`$ and $`B_{2m+1}=x^{2m}+2x^{2m+1}`$; and

$$\begin{array}{c}D_{2m}(x)=\frac{x^{2m+1}}{14x^2}(U_{2m+1}\left(\frac{1}{2x}\right)2xU_{2m}\left(\frac{1}{2x}\right)2x),\hfill \\ D_{2m+1}(x)=\frac{x^{2m+3}}{14x^2}(U_{2m+3}\left(\frac{1}{2x}\right)U_{2m+1}\left(\frac{1}{2x}\right)4x),\hfill \end{array}$$

for all $`m0`$.

Acknowledgments. The final version of this paper was written while the author was visiting University of Haifa, Israel in January 2003. He thanks the HIACS Research Center and the Caesarea Edmond Benjamin de Rothschild Foundation Institute for Interdisciplinary Applications of Computer Science for financial support, and professor Alek Vainshtein for his generosity.


text:
# Kinematic simulation of multi point turbulent dispersion

## 1 Introduction

The transport of scalar fields by turbulent flows is an important process in many physical situations ranging from the dynamics of the atmosphere and the ocean to chemical engineering. Specific examples of scalars are provided by pollutant density, temperature or humidity fields and the concentration of chemical and biological species .

Issues of transport and mixing in turbulence are directly related to the properties of fluid trajectories. The problem is thus often addressed using Lagrangian techniques . There is an established formal connection between the statistics of fluid particle motion and the concentration field of a diffusing scalar . Hence the important modeling issue of predicting passive scalar transport in turbulence can be addressed by following the evolution of Lagrangian particles .

The dispersion problem of one or two particles in the flow has been studied in great detail. In particular, the seminal work of Richardson  leads to the prediction that the separation between two particles grows according to $`R^2\epsilon t^3`$, where $`\epsilon `$ is the rate of energy dissipation in the flow. Much less work has been devoted to the dispersion of $`3`$ or more particles. The remarkable organization of the flow, which leads to the formation of very sharp fronts of scalar concentration , has a non trivial signature on the $`3`$-point correlation function of the flow . This, together with the well-established relation between the properties of the $`n`$-point correlation function and the properties of the evolution of $`n`$ fluid particles advected by the flow, provides the motivation for studying the problem of dispersion of $`3`$ particles or more. Despite recent progress both theoretically  and experimentally , little is known about the dispersion of $`3`$ particles or more.

An extra motivation to study dispersion of more than two particles comes from recent theoretical attempts to model turbulent velocity fluctuations in terms of small sets of Lagrangian particles

The evolution of three particles configuration in turbulent flows has been considered numerically in direct numerical simulations (DNS) of $`3`$-dimensional flows, at moderate Reynolds number . Because of the limited range of inertial scales available in DNS, the numerical studies are unable to answer questions about shape statistics in the inertial range. A phenomenological model, introduced to describe the shape deformation in the inertial range, in high Reynolds number flows, lead to the prediction of a non trivial shape distribution . This model provided both the motivation and the theoretical background to analyze the experimental results of . This experiment provided important insight on the statistics of deformation, although the experimental setup also suffered from the limited inertial range.

In this paper, we consider the problem of Lagrangian dispersion of $`3`$ particles with the help of the Kinematic Simulation (KS) method, introduced in . KS provides a Lagrangian model of turbulent diffusion, based on a simplified incompressible velocity field, with a proper energy spectrum and no assumption of delta correlation in time made at any level. This model reproduces very well the Lagrangian properties observed in laboratory experiments , as well as in DNS . The computational simplicity of the KS allows us to consider very large inertial ranges : a ratio of scales of $`10^4`$ is easily accessible with moderate computer resources. KS thus turns out to be an ideal tool to study issues of dispersion in turbulent flows.

This paper is therefore devoted to the study of Lagrangian dispersion of $`3`$ points in a $`2`$ dimensional turbulent flow using the KS. We will demonstrate that the numerical results effectively reproduce the experimental results of , and we will explore the large Reynolds number limit with the help of the KS.

In section II, we briefly discuss the parameterization used to characterize the size and shape of the triangles, and we review the theoretical and experimental results on shape dynamics. Technical aspects of the simulation methods are described in section 3. The comparison between the experimental results of  and the KS simulations are presented in section 4. Section 5 contains our results concerning the large Reynolds number limit. In section 6 we discuss the effects of persistence of flow structures on shape dynamics. Last, we present our concluding remarks in section VII.

## 2 Previous results on shape dynamics

In this section, we briefly review the previous work on shape dynamics .

### 2.1 Kinematics

The evolution of a cluster of particles is described both by the overall scale, and by the shape of the object. In the case of a set of $`n=3`$ particles, located at $`𝐱_i`$ ($`i=1,2,3`$), we define a set of reduced vectors involving relative separations only, defined by  :

$`𝝆_1`$ $`=`$ $`{\displaystyle \frac{(𝐱_2𝐱_1)}{\sqrt{2}}}`$ (1)
$`𝝆_2`$ $`=`$ $`{\displaystyle \frac{(2𝐱_3𝐱_2𝐱_1)}{\sqrt{6}}}`$ (2)
The radius of gyration is defined as

$$R^2=\underset{i=1}{\overset{2}{}}𝝆_i^2=\frac{1}{3}\underset{jk}{}𝐫_{jk}^2$$
(3)
where $`𝐫_{ij}^2=|𝐱_i𝐱_j|^2`$ are the distances between the vertices of the triangle. The quantity $`R`$ measures the spatial extent of the swarm of particles. In order to characterize the shape, we introduce a moment of inertia like tensor

$$g^{ab}=\underset{i=1}{\overset{2}{}}\rho _i^a\rho _i^b,$$
(4)
where $`\rho _i^a`$ is the $`a`$-th spatial component of the vector $`𝝆_i`$. For a triangle in $`2`$-dimensions, the tensor $`g`$ has two eigenvalues, $`g_1>g_2`$ (note that $`g_1+g_2=R^2`$). These eigenvalues characterize the spatial extent of the swarm in the two principal directions. The ratio $`I_2`$ between the smallest eigenvalue, $`g_2`$, and $`R^2`$ :

$$I_2=\frac{g_2}{R^2}$$
(5)
provides us with a quantitative measure of the shape of the object. An equilateral triangle corresponds to $`I_2=1/2`$. The smaller $`I_2`$, the more elongated the triangle is. The moment of inertia tensor can be used both in $`2`$ and $`3`$ dimensions to characterize a set consisting of an arbitrary number of particles.

In the case of a triangle, a full parametrization of the shape is provided by the quantities $`w`$ and $`\chi `$, defined by :

$$\chi =\frac{1}{2}\mathrm{arctan}\left[\frac{2𝝆_1𝝆_2}{\rho _1^2\rho _2^2}\right];w=2\frac{|𝝆_1\times 𝝆_2|}{R^2}$$
(6)
By taking into account the symmetries of the triangle under any reparametrization of its vertices, the parameter space is restricted to $`0w1`$ and $`0\chi \pi /6`$. The variables $`w`$ and $`I_2`$ are related by the relation : $`I_2=(1/2)(1\sqrt{1w^2})`$. A small value of $`w`$ corresponds to a nearly collinear set of points. The quantity $`\chi `$ is small when the separation between two particles, say $`1`$ and $`2`$, is much smaller than their separation with the third one : $`r_{12}<<r_{13},r_{23}`$.

We consider in this work the statistical properties of the shape distribution. To this end, we study the probability distribution functions of the various quantities $`R`$, $`I_2`$, $`w`$ and $`\chi `$ characterizing the shape. The Gaussian distribution : $`P_G(\rho _1,\rho _2)=𝒩\mathrm{exp}\left((\rho _1^2+\rho _2^2)\right)`$ provides an interesting distribution of reference. It can be shown  that the distributions of $`\chi `$ and $`w`$ are uniform (in $`2`$ dimensions) : $`P_G(\chi )=\frac{6}{\pi }`$ and $`P_G(w)=1`$. In particular, the corresponding mean values are : $`\chi _G=\frac{\pi }{12}`$, $`w_G=\frac{1}{2}`$ and $`I_2_G=(1\frac{\pi }{4})/2`$.

### 2.2 Monte-Carlo model

In order to study theoretically the distortion of sets of $`3`$ or $`4`$ particles by a turbulent flow in the inertial range of scales, a stochastic model based on phenomenological considerations was proposed in . At the heart of the model is a simplified scale decomposition of the full turbulent velocity field, on the scale of the global size of the triangle measured by the radius of gyration $`R`$ . Namely, the velocity field is written as:

$$𝐯𝐯_<+𝐯_{}+𝐯_>,$$
(7)
where $`𝐯_<`$ is the contribution due to the small wavenumbers or large scales in the usual Fourier decomposition ($`|k|1/2R`$), $`𝐯_>`$ comes from the large wavenumbers ($`|k|2/R`$) or small scales and $`𝐯_{}`$ originates from the scales of the flow comparable to the global scale $`R`$ ($`2/R|k|1/2R`$). The large scale contribution is uniform over the triangular configuration of particles, and is therefore assumed in  not to distort the set of particles. The $`𝐯_{}`$ part of the velocity field acts coherently over the scale of the triangles with correlation time of the order of the characteristic time of turbulence at scale $`R`$, defined by :

$$\tau (R)=R^{2/3}ϵ^{1/3}$$
(8)
The small scale component $`𝐯_>`$ is often assumed to be completely incoherent on the scale $`R`$ of the three points and its correlation time is short compared to the characteristic time of turbulence at scale $`\tau (R)`$. It is modeled in  by a white noise term.

The action of $`𝐯_{}`$ is approximated by a (coarse-grained) strain matrix, $`M_{ab}=_av_b`$, acting on the vectors $`𝝆_i`$. The rapidly fluctuating, incoherent component $`𝐯_>`$ is modeled by a Gaussian, white in time, random process. This leads to the following stochastic model :

$`{\displaystyle \frac{d\rho _i^a}{dt}}`$ $`=`$ $`\rho _i^bM_{ab}+u_i^a,`$ (9)
$`{\displaystyle \frac{dM_{ab}}{dt}}`$ $`=`$ $`{\displaystyle \frac{M_{ab}}{\tau (R)}}+\eta _{ab},`$ (10)
where the indices $`i,j=1,2`$ for $`3`$ particles labels the relative vectors, see Eq. (2), and $`a,b`$ labels the spatial components. The velocity fields $`𝐮`$ and the $`\eta _{ab}`$ term are random Gaussian terms, delta-correlated in time with variances

$$\eta _{ab}(t)\eta _{cd}(t^{})=C_\eta ^2\delta (tt^{})\left(\delta _{ac}\delta _{bd}\frac{1}{2}\delta _{ab}\delta _{cd}\right)/\tau (R)$$
(11)
$$u_i^a(t)u_j^b(t^{})=\left(\frac{C_v}{2}\right)^2\delta (tt^{})\delta _{ij}\delta _{ab}R^2/\tau (R)$$
(12)
The stochastic model has been constructed in such a way that the matrix $`M`$ is traceless (incompressibility) and correlated with a time scale $`\tau (R)`$. Its amplitude is of the order of $`|M|R^{1/3}`$. The dimensionless parameter $`C_v`$ (respectively $`C_\eta `$) controls the importance of the incoherent jitter (respectively of the coherent term) in the model.

Physically, the term $`\rho _i^bM_{ab}`$ in equation (10) stretches and aligns the set of points. This distorting action is opposed by the action of the $`𝐮`$ term, which tends to make the shape distribution Gaussian. The shape distribution resulting from these two effects is non trivial, and depends continuously on the ratio $`C_v/C_\eta `$. A-priori, this number is of order $`1`$. In the limit $`C_v/C_\eta \mathrm{}`$, the shape distribution becomes Gaussian.

The model turns out to reproduce qualitatively several important aspects of the experimental results. A detailed analysis of the experimental data however pointed out several shortcomings of the stochastic approach . In particular, it was found that whereas the stochastic model predicts a uniform distribution of the variable $`\chi `$, the experimental distribution of $`\chi `$ shows a peak near $`\chi =0`$.

## 3 Kinematic simulations

In contrast to the stochastic model described above, KS defines explicitly the velocity field which advects the particles. Following , we define the turbulent velocity field $`𝐯(𝐱,t)`$ by summing over a set of Fourier modes, $`𝐤_n`$ :

$`𝐯(𝐱,t)=`$ $`{\displaystyle \underset{n=1}{\overset{N_k}{}}}[𝐀_n𝐤_n\mathrm{cos}(𝐤_n𝐱+\omega _nt)`$
$`+`$ $`𝐁_n𝐤_n\mathrm{sin}(𝐤_n𝐱+\omega _nt)]`$ (13)
where $`N_k`$ is the number of modes in the simulations, $`𝐤_n`$ are the wave vectors, $`𝐀_n`$ and $`𝐁_n`$ are the amplitude vectors and $`\omega _n`$ the frequency. The norms of the wavevector are chosen of the form $`k_n=|𝐤_n|=k_0b^n`$ with a parameter $`b`$ typically chosen to be $`b=(L/\eta )^{1/(N_k1)}`$. The large (integral) scale, $`L`$, and the small (Kolmogorov) scale, $`\eta `$ of the flow verify : $`L=1/k_1`$ and $`\eta =1/k_{N_k}`$ ($`L/\eta =b^{N_k}`$). The direction of the wave vector, $`\widehat{k}_n=𝐤_n/|𝐤_n|`$ is uniformly distributed along the unit circle. Similarly, the directions of the vectors $`𝐀_n`$ and $`𝐁_n`$ are randomly distributed, and their amplitudes are chosen so that the energy spectrum is of the form $`E(k)k^p`$. The frequencies $`\omega _n`$ are taken to be $`\omega _n=\lambda \sqrt{k_n^3E(k_n)}`$, where $`\lambda `$ is a dimensionless parameter, a-priori of $`𝒪(1)`$. The definition Eq. (13) makes the velocity field explicitly incompressible. Note that no delta correlation in time is used in KS at any level and that the parameter $`\lambda `$ controls the unsteadiness of the flow.

To investigate the geometry of clusters of $`n=3`$ Lagrangian particles, we simply advect numerically Lagrangian particles in the velocity field $`𝐯(𝐱,t)`$ defined by Eq. (13). This is done by solving a set of ordinary differential equations for the position vectors $`𝐗(𝐱_0,t)`$ :

$$\frac{d}{dt}𝐗(𝐱_0,t)=𝐯(𝐱=𝐗,t)$$
(14)
with the initial condition $`𝐗(𝐱_0,0)=𝐱_0`$. We start with an isotropic object, i.e. with an equilateral triangle, of a given size, and follow its evolution over time. The quantities characterizing the deformation of the object, such as $`I_2`$, $`w`$, $`\chi `$ are monitored as a function of time. We then perform ensemble averages over many triangles in different realizations of the velocity field to obtain the relevant particle statistics.

We firstly validate the predictions from KS with the experimental results . To this end, we choose the power of the spectrum $`p=5/3`$, the ratio of inner to outer scales as suggested by the experiment, and we take $`\lambda =𝒪(1)`$. We then extrapolate our results to higher values of the ratio of inner to outer scales $`L/\eta `$, to study dispersion in a high Reynolds number flow.

We stress that KS is a model of the Eulerian velocity field, used to advect the particles. The KS velocity field, (13) has an interesting spatio-temporal flow structure, which varies with the parameters of the flow $`p`$ and $`\lambda `$ . Investigating systematically how the changes in the parameters $`p`$ and $`\lambda `$ affects advection of particles is intrinsically interesting in the context of this study.

## 4 Validation of KS

Before making any predictions with KS regarding multi-particle statistics we firstly validate the model by comparing with the experimental results . We are interested here in reproducing qualitatively the experimental results of . This does not mean that KS is not able to reproduce quantitative predictions, at the cost of fitting the parameter $`\lambda `$. We are merely interested in the trends of the shape evolution, that is, in the behaviors of the distributions of $`w`$, $`\chi `$ etc as a function of time.

An experimental investigation of the problem of dispersion of triangles by a turbulent flow was carried out in $`2`$-dimensions, in the inverse cascade regime . The flow was confined in a small container, $`15\times 15cm^2`$. Permanent magnets were placed under the bottom of the cell. The flow was stirred by running a current through a salted solution. The energy was injected at the scale $`l_i=1.5cm`$. The velocity field was recorded by using standard Particle Image Velocimetry techniques, and was then stored on a $`64\times 64`$ grid every $`0.04s`$. The resulting spatial resolution was good enough to describe all the relevant scales of the flow. A Kolmogorov $`k^{5/3}`$ regime was observed, over the limited range of scales $`1.5\mathrm{cm}l5.5\mathrm{cm}`$. The time resolution was also amply sufficient to follow numerically the evolution of particles. The evolution of a large number ($`2\times 10^4`$) of triangles was then followed numerically. In this section we compare our results produced from KS with the experimental results of  and validate our model in the process.

It was observed (see Fig.3-5 of ) that the typical size measured by the radius of gyration $`R`$ of the triangles increased until it reached the largest scale $`9cm`$ of the experimental setup where it started to fluctuate around this value. The evolution in time of the mean values of $`w`$ and $`\chi `$ (see Figs.4,5 of ) showed a rapid decrease of these parameters corresponding to strong shape distortions of the triangles. The smaller the initial separation $`r_0`$ the lower the minimal value of this parameter was observed. The shape distortion was maximum when $`R`$ reached the lower value $`\sqrt{R^2}=1.5cm`$ of the inertial range. The mean values of these variables tend to an asymptotic value when $`R`$ increases above the upper bound $`\sqrt{R^2}=5.5cm`$ of the inertial range. Specifically, it was found that $`w_{asm}=0.5`$, $`I_2_{asm}0.11`$ and $`\chi _{asm}0.26`$ These asymptotic values for $`w`$, $`I_2`$ and $`\chi `$ correspond to a Gaussian distribution of the $`𝝆_1`$ and $`𝝆_2`$, which implies a uniform distribution for $`w`$, $`I_2`$ and $`\chi `$ with the Gaussian values $`w_{Gau}=1/2`$, $`I_2_{Gau}=(1\pi /4)/2=0.107`$ and $`\chi _{Gau}=\pi /12=0.262`$ and a corresponding Gaussian distribution for $`R`$: $`P_{Gau}(R)=(8R^3/R^2^2)\mathrm{exp}(2R^2/R^2)`$.

The PDF of $`R`$ and $`w`$, see Fig.6 of , can be well approximated by the Gaussian distribution for large values of time $`t=80sec`$ and $`t=100sec`$ corresponding to values of the radius of gyration larger than the integral scale $`L`$. At later times, the finite size of the experimental system induces a saturation of the triangle size, so the tails of the distribution of $`R`$ could no longer be correctly fitted by $`P_{Gau}(R)`$ . A very slow relaxation of the value of $`\chi `$ towards its asymptotic, Gaussian value was observed. The fact that $`\chi =0`$ is more probable than $`\chi =\pi /6`$ implies that triangles with one edge much shorter than the two other ones has a large probability. This effect should ultimately disappear at later time, in the diffusive regime.

The numerical experiment, consists of generating KS flows in two dimensions, with an energy spectrum $`E(k)k^{5/3}`$, similar to the one observed experimentally, characterized by a ratio $`L/\eta =3.67`$, and with an unsteadiness factor $`\lambda =0.5`$. The smallest and the largest time scales of the flow are defined to be $`t_\eta =2\pi /\sqrt{k_\eta ^3E(k_\eta )}`$ and $`t_E=L/u^{}`$ respectively, where $`u^{}`$ is the r.m.s velocity of the flow field. In this flow, we follow the evolution of three points, initialized as the vertices of an equilateral triangle of size $`r_0`$. The results were averaged over $`10^4`$ configurations.

The results obtained from KS show the same tendencies as the one observed in the experiment, as we now demonstrate.

The behaviors as functions of time of the mean values of $`R`$ (see Fig. 1), $`w`$ (see Fig. 2) and $`\chi `$ (see Fig. 3), as well as the evolution of the PDFs of $`R`$, $`w`$ and $`\chi `$ (see Fig. 4) computed from KS are very close to the ones observed experimentally (see Figs. 3-6 of ). Contrary to the laboratory experiment, where the spatial confinement of the setup induced a saturation of the growth of the radius of gyration, $`R^2`$ grows like $`t`$ at very long times. The distribution of sizes, $`R`$, as well as the distribution of $`w`$ and $`\chi `$ are Gaussian in this regime. The relaxation of the peak of probability for $`\chi 0`$ is faster in the KS than in the experiment. This small discrepancy is conceivably due to the large scale limitations of the flow.

At intermediate time scales, when $`R^2^{1/2}`$ is in the inertial range, the mean values and the distribution of $`w`$ are very close to the ones observed in .

These results demonstrate that KS reproduces very well the main properties of the evolution of three Lagrangian particles. A similar conclusion was reached in  by comparing laboratory and KS results in two dimensions, and in  by comparing DNS and KS results in $`3`$-dimensions. KS is thus a potentially very useful tool both for fundamental studies, and for dispersion studies in a more applied context.

## 5 Predictions of KS in the large Reynolds number limit

The results of the previous subsection demonstrate that the KS model reproduces quite satisfactorily the laboratory results concerning the evolution of three particles in a turbulent $`2`$-dimensional flow. We now investigate the large Reynolds number limit with the help of the KS. This is achieved by increasing the ratio of the largest to the smallest scale, $`L/\eta `$ irrespective of initial conditions.

A previous study  has shown that the separation between two particles in the inertial regime shows sizable differences compared to the famous Richardson’s scaling, according to which the separation grows according to $`R^2ϵt^3`$ irrespective of initial conditions. Specifically a strong dependence of two-particle dispersion statistics on the initial separation the particles was found . In the case of three particles studied here, it is of obvious interest to investigate the statistics of the radius of gyration of the set of particles. Also, the existence of a non trivial, time independent distribution of shapes, predicted by  when the separation between particles is in the inertial range of scales, remains to be tested. We address these questions in turn, with the help of KS.

We stress that there is no guarantee that the evolution of $`3`$ particles is correctly predicted by the KS with $`p=5/3`$ when the ratio $`L/\eta `$ becomes large. In spite of this uncertainty, the numerical results presented here are intrinsically interesting since the KS flow shares with real turbulence a number of important properties.

The evolution of three particles has been followed numerically, using several KS flows, corresponding to different Reynolds numbers, or equivalently, to different values of $`L/\eta `$ ($`L/\eta =1691`$, $`3381`$, $`16909`$). Our runs, with the values of the parameters characterizing the flows, are listed in Table 1.

The results of these simulations (Fig. 5, corresponding to $`L/\eta =1691`$ and Fig. 6, corresponding to $`L/\eta =16909`$) show some resemblance with the small $`L/\eta `$ case, see section 4). As the Reynolds number is increased, the dependence of the variables describing geometry, $`I_2`$, $`W`$, and $`\chi `$ becomes weaker, both as a function of the initial size of the triangle and as a function of time. The values of these variables is always significantly different from the Gaussian values.

The PDF of $`R`$, $`w`$ and $`\chi `$ at the value $`L/\eta =1691`$ also show trends which are similar to the ones observed at smaller values of $`L/\eta `$ (Fig. 7). We have not followed particles long enough to see the Gaussian distribution of shapes at very large values of $`L/\eta `$; the study has been restricted to the non trivial inertial range. In this range of scales, the variation of the PDF as a function of time is considerably weaker than observed in section 4, and in this sense, the results suggest that one may be getting close to the self similar shape distribution predicted in . A visible deformation of the PDF of $`R`$ can be observed as a function of time, reflecting the fact that at the later times, large excursions in the radius of gyration are getting close to the value of the largest available scale, $`L`$.

Although still finite, the value of $`L/\eta `$ for run $`13`$ is significantly larger than it is in any engineering, industrial or laboratory flow. Even so, our numerical results show persistent differences with the picture of a simple truly self similar regime.

In all the reported DNS, in $`2`$  and in $`3`$ dimensions , a dependence of the behavior of $`R(t)`$ on the initial separation $`r_0`$ has been reported. We observe a similar behavior in our KS calculation. Fig. 8 shows that the $`t^3`$ Richardson regime is never really reached. Instead, a continuous dependence of the variation of $`R^2/t^3`$ on the initial separation $`r_0`$ is observed. This effect is clearly seen, even at our largest Reynolds number. This behavior suggests that the set of three particles always remembers its initial condition, which represents a departure with respect to the Richardson prediction. Also, at a fixed value of the initial size of the triangle, a non trivial power seems to emerge as the Reynolds number increases. A similar behavior was observed for the separation between two particles .

To investigate further this effect, we consider the PDFs of the radius of gyration, $`R`$. Fig. 9 shows a superposition of the PDFs of $`R/R`$ for three different initial values of $`r_0/\eta =0.1,\mathrm{1.0\; 5.0}`$, and at different values of time. The distribution of the large values of $`R/R`$ are expected to be independent of time and Fig. 9 does not disprove this expectation. However, the distribution at small values of $`R/R`$ seems to vary throughout the entire evolution.

To compare different values of $`r_0`$, we have plotted the PDFs of $`R/R`$ corresponding to two different values of $`r_0`$, but with similar values of $`R`$ (Fig. 10, 11). For large enough times the PDF of $`R/R`$ seem to collapse at large values of $`R/R`$ within statistical errors. However, serious deviations are observed at small values of $`R/R`$. In particular the peaks of the PDF at very small values of $`R/R`$ are much sharper at smaller values than at larger values of $`r_0`$.

These results suggest that the distributions of $`R`$ are influenced throughout the entire evolution by the initial value $`r_0`$, insofar as a significant number of triplets do not really separate, and remain at a value $`Rr_0`$. In the case of two particles this behavior has indeed been observed by Jullien et al.  in the laboratory for low Reynolds number flows, by Fung et al.  and Nicolleau et al.  in high Reynolds number KS simulations. In this way, the evolution depends in an essential way on the value of $`r_0`$.

The evolution of other geometric quantities, such as $`w`$, $`\chi `$ reflects to some extent the behavior described above (see Fig. 5, 6). Indeed, the lack of exact self similarity observed in the evolution of the radius of gyration, $`R`$, shows that the prediction of a truly time independent shape distribution is at best valid at Reynolds numbers impossible to attain. Although this prediction might constitute a good first order approximation, which becomes better as the Reynolds number increases, Fig. 6 shows that the mean values of $`w`$, $`I_2`$ and $`\chi `$ do  vary with time, even at $`L/\eta =16909`$. In addition, a systematic variation with $`r_0`$ is seen in Fig. 5, 6. The distributions are observed to remain non Gaussian as long as $`R`$ remains in the inertial range, and do correspond to a higher probability of observing elongated objects, as anticipated in the stochastic model proposed in . In the light of the KS results, the stochastic model correctly predicts the main qualitative feature (the increased probability of elongated objects), but it doesn’t incorporate the lack of self-similarity of multi-particle diffusion observed in KS. As we discuss in the next paragraph, memory effects relating to this lack of self-similarity are observed in laboratory experiments . They are also observed in KS because, unlike stochastic models, KS incorporates the persistence of flow structures. Whether this lack of self-similarity persists in the laboratory and in nature at extremely high Reynolds numbers remains an open question.

The results obtained so far suggest that the lack of self-similarity in the evolution of the radius of gyration, $`R`$, is due to the fact that particles stay together, at a distance of order $`r_0`$ with a high probability. Even if the radius of gyration grows to a value $`Rr_0`$, it was observed in  that two particles of the triplet can remain close to each other, with a large probability. We interpret the lack of a stationary distribution of shapes to reflect a similar cause : when one particle of the triplet separates from the two other ones, which remain at a mutual distance $`r_0`$, a very elongated shape is created. The relaxation of the distribution of shapes towards a stationary distribution will depend on how the two particles that are close together eventually separate. Our observations suggest that, the smaller $`r_0`$, the longer particles will stay together, hence, the longer it will take the transient to relax. This lack of self-similarity is absent in stochastic models, such as the one proposed by , and is consistent with the view that coherent streamline structures are persistent enough to cause a dependence of turbulent diffusion on initial conditions.

## 6 Effects of persistence of the flow structure

The KS model allows us to modify some of the characteristics of the advecting flow, both spatially and temporally. This is achieved by modifying the parameters $`\lambda `$ and $`p`$. The purpose of this section is to investigate the effect of changing the spatio-temporal structure of the flow, and in this way, to gain insight into the mechanisms involved in multi-particle dispersion.

We firstly change the temporal structure of the flow by varying the persistence parameter $`\lambda `$ (see Fig. 12 ). This controls how fast the streamlines of the flow are jittered in comparison to the relevant eddy turn over time at the corresponding scale. This jittering makes the particles in the flow to be rapidly swept from one streamline to the other. Since in KS there is no interaction among modes of the velocity field, this jittering mimics the sweeping effects that are present in a real flow field. The minima of $`I_2(t)`$ and $`w(t)`$ increase with increasing unsteadiness parameter $`\lambda `$ within the inertial range of time scales which means triangles are less elongated for larger values of $`\lambda `$ (Fig.12). This happens because the paths of neighboring particles decorrelate faster for larger values of $`\lambda `$ and triangles quickly forget their memory of the initial state. Hence increased values of $`\lambda `$ should cause the triangle shape parameters to relax faster to their corresponding Gaussian values.

Secondly we change the spatial structure of the flow field by changing the energy spectrum i.e. changing the exponent $`p`$ in $`E(k)k^p`$ (see Fig. 13 ). This has the effect of changing the density of straining regions in the flow field  thereby modifying the separation mechanism of particle pairs and clusters. The minimum of $`I_2(t)`$ and $`w(t)`$ decreases with increasing $`p`$ ($`E(k)k^p`$) within the inertial range of time and scales. This means that the clusters are more/less elongated during the inertial range of times when $`p`$ is made larger/smaller. An explanation of this effect can be given in terms of randomness: as $`p`$ increases there is less energy in the smaller scales of the turbulence which may mean less randomness leading to clusters remaining more elongated during the inertial range of times. In the context of KS as $`p`$ increases there is indeed less energy in the small scales leading to smaller unsteadiness frequency $`\omega _nk_n^{(3p)/2}`$ and therefore less randomness and more elongated clusters. However, a more searching explanation should invoke the spatio-temporal flow mechanism causing cluster elongation. One such mechanism already proposed in the literature  is based on persistent effects of straining regions. The spatial density of straining regions decreases as $`p`$ is made larger .

However, the simple calculation, presented in the Appendix, indicates that the average straining rate per straining region increases faster than the number of such regions decreases when $`p`$ is made larger. Provided that the effect of increased strain rate per strain region overwhelms that of the decreased number of such regions, then the same conclusion is reached: clusters should remain more/less elongated during the inertial range of times when $`p`$ is made larger/smaller.

## 7 Conclusions

We have investigated the Lagrangian shape dynamics and the corresponding statistics of multiple particles namely of three particles advected by a two dimensional turbulent flow. We have used kinematic simulation (KS) to generate a turbulent velocity field and follow numerically sets of three particles in this flow field. The results of the simulation have been compared with the results of a two dimensional experiment . We have identified a mechanism for the shape evolution of three particles depending on the underlying flow structure and the effect of persistence of these structures on the statistics of these shapes.

Two regimes with well-characterized distributions have been identified in our simulation with KS. These regimes have also been observed in the two dimensional experiments of Castiglione et al. . Two different regimes can be identified, according to the fact that the mean separation is large compared to the largest scale (diffusion regime) or in the inertial regime. The diffusion regime is characterized by a Gaussian shape distribution.

In the inertial regime the scale $`\eta ^2R^2L^2`$, we have observed what might be described as a trend, at best, towards a Richardson’s law $`R(t)^2t^3`$. But the appearance of this regime was found to be dependent on the initial scale or size $`r_0`$ of the triangles. This has also been observed in the experiment .

The temporal evolution of $`I_2(t)`$ , $`w(t)`$ and $`\chi (t)`$ match with the experimental results of . KS predicts the correct temporal evolution and the distribution functions of the above quantities. Monte Carlo simulation can do as well except for the PDF of $`\chi `$ .

It is found that the clusters are more/less elongated during the inertial range of times when $`\lambda `$ is made smaller/larger (Fig. 12). The reason for this result must be that the persistence of the straining action of the flow is diminished when the flow is made more unsteady by increasing $`\lambda `$.

It is also found that the clusters are more/less elongated during the inertial range of times when $`p`$ is made larger/smaller. An explanation of this effect can be given in terms of randomness: as $`p`$ increases there is less energy in the smaller scales of the turbulence which may mean less randomness leading to clusters remaining more elongated during the inertial range of times. However, we also discuss a more searching explanation which invokes the straining mechanisms causing cluster elongation.

The dependence of the shape of clusters on the initial separation between marked fluid elements is clearly demonstrated by the PDF of the radius of gyration of particle clusters with different initial separations not collapsing within the inertial range (see Figs.10,11). Our KS numerical experiments indicate that clusters tend to have memory of the initial state even when the turbulence has an extremely wide inertial range of more than four decades.

This result is in agreement with the observed dependence  on the initial pair separation of the apparent power law governing the growth of inter-particle distances. If these effects are transient and due to a finite range of inertial scales, then our results indicate that they might only disappear at extremely high Reynolds numbers. However, the possibility should also be retained that these effects are not finite range transient effects, and are caused, instead, by the persistence of spatial flow structures at all scales, assuming this persistence remains at asymptotically high Reynolds numbers.

## Acknowledgements

We acknowledge the European contract HPRN-CT-2002-00300 and ECTMR network on intermittency in turbulent systems. MAIK acknowledges support from the Cambridge commonwealth trust (CCT), overseas research scheme (ORS), DAMTP and Wolfson College, Cambridge. JCV acknowledges financial support from the Royal Society, UK and the Hong Kong research grant council (project number HKUST6121/00P). AP acknowledges support from IDRIS, France.

## Appendix

Assume we are given the spectrum $`E(k)=E_0L(kL)^p`$ defined in the range $`1/Lk1/\eta `$ of an isotropic turbulence. The mean square straining rate $`\left(u/x\right)^2`$ is proportional to $`_{1/L}^{1/\eta }k^2E(k)𝑑k`$. Substituting the form of the spectrum and integrating we get for $`p<3`$,

$$\left(\frac{u}{x}\right)^2\frac{E_0}{(3p)L^2}\left(\frac{L}{\eta }\right)^{3p}.$$
(15)
In KS, the number density of straining stagnation points decreases with increasing $`p`$  and  calculated the following scaling relation:

$$n_s\left(\frac{L}{\eta }\right)^{D_s},$$
(16)
where $`n_s`$ is the number density of straining stagnation points and $`D_s`$ is the fractal dimension of the spatial distribution of these points in the flow. In 2-D KS, $`D_s=3p`$ . Hence the number of straining stagnation points per unit area decreases with increasing $`p`$ in our KS but the mean square strain rate per straining stagnation point, i.e. $`(\frac{u}{x})^2/n_s`$, scales like $`E_0/(3p)L^2`$. This implies that, although the number density decreases with increasing $`p`$, but the mean strain rate per straining stagnation point becomes stronger, which is the reason behind the decrease of the parameters $`I_2`$ and $`W`$ with increasing $`p`$.