text:
# Generalised pattern avoidance

## 1. Introduction

In the last decade a wealth of articles has been written on the subject of pattern avoidance, also known as the study of “restricted permutations” and “permutations with forbidden subsequences”. Classically, a pattern is a permutation $`\sigma 𝒮_k`$, and a permutation $`\pi 𝒮_n`$ avoids $`\sigma `$ if there is no subsequence in $`\pi `$ whose letters are in the same relative order as the letters of $`\sigma `$. For example, $`\pi 𝒮_n`$ avoids $`132`$ if there is no $`1ijkn`$ such that $`\pi (i)\pi (k)\pi (j)`$. In  Knuth established that for all $`\sigma 𝒮_3`$, the number of permutations in $`𝒮_n`$ avoiding $`\sigma `$ equals the $`n`$th Catalan number, $`C_n=\frac{1}{1+n}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)`$. One may also consider permutations that are required to avoid several patterns. In  Simion and Schmidt gave a complete solution for permutations avoiding any set of patterns of length three. Even patterns of length greater than three have been considered. For instance, West showed in  that permutations avoiding both $`3142`$ and $`2413`$ are enumerated by the Shröder numbers, $`S_n=_{i=0}^n\left(\genfrac{}{}{0pt}{}{2ni}{i}\right)C_{ni}`$.

In  Babson and Steingrímsson introduced generalised permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. The motivation for Babson and Steingrímsson in introducing these patterns was the study of Mahonian statistics, and they showed that essentially all Mahonian permutation statistics in the literature can be written as linear combinations of such patterns. An example of a generalised pattern is $`(a\text{-}\text{-}cb)`$. An $`(a\text{-}\text{-}cb)`$-subword of a permutation $`\pi =a_1a_2\mathrm{}a_n`$ is a subword $`a_ia_ja_{j+1}`$, $`(i<j)`$, such that $`a_i<a_{j+1}<a_j`$. More generally, a pattern $`p`$ is a word over the alphabet $`a<b<c<d\mathrm{}`$ where two adjacent letters may or may not be separated by a dash. The absence of a dash between two adjacent letters in a $`p`$ indicates that the corresponding letters in a $`p`$-subword of a permutation must be adjacent. Also, the ordering of the letters in the $`p`$-subword must match the ordering of the letters in the pattern. This definition, as well as any other definition in the introduction, will be stated rigorously in Section 2. All classical patterns are generalised patterns where each pair of adjacent letters is separated by a dash. For example, the generalised pattern equivalent to $`132`$ is $`(a\text{-}\text{-}c\text{-}\text{-}b)`$.

We extend the notion of pattern avoidance by defining that a permutation avoids a (generalised) pattern $`p`$ if it does not contain any $`p`$-subwords. We show that this is a fruitful extension, by establishing connections to other well known combinatorial structures, not previously shown to be related to pattern avoidance. The main results are given below.

$$\begin{array}{ccc}P\hfill & |𝒮_n(P)|\hfill & Description\hfill \\ & & \\ a\text{-}\text{-}bc\hfill & B_n\hfill & \text{ Partitions of }[n]\hfill \\ a\text{-}\text{-}cb\hfill & B_n\hfill & \text{ Partitions of }[n]\hfill \\ b\text{-}\text{-}ac\hfill & C_n\hfill & \text{ Dyck paths of length }2n\hfill \\ a\text{-}\text{-}bc,ab\text{-}\text{-}c\hfill & B_n^{}\hfill & \text{ Non-overlapping partitions of }[n]\hfill \\ a\text{-}\text{-}bc,a\text{-}\text{-}cb\hfill & I_n\hfill & \text{ Involutions in }𝒮_n\hfill \\ a\text{-}\text{-}bc,ac\text{-}\text{-}b\hfill & M_n\hfill & \text{ Motzkin paths of length }n\hfill \end{array}$$

Here $`𝒮_n(P)=\{\pi 𝒮_n:\pi \text{ avoids }p\text{ for all }pP\}`$, and $`[n]=\{1,2,\mathrm{},n\}`$. When proving that $`|𝒮_n(a\text{-}\text{-}bc,ab\text{-}\text{-}c)|=B_n^{}`$ (the $`n`$th Bessel number), we first prove that there is a one-to-one correspondence between $`\{a\text{-}\text{-}bc,ab\text{-}\text{-}c\}`$-avoiding permutations and *monotone partitions*. A partition is monotone if its non-singleton blocks can be written in increasing order of their least element and increasing order of their greatest element, simultaneously. This new class of partitions is then shown to be in one-to-one correspondence with non-overlapping partitions.

## 2. Preliminaries

By an *alphabet* $`X`$ we mean a non-empty set. An element of $`X`$ is called a *letter*. A *word* over $`X`$ is a finite sequence of letters from $`X`$. We consider also the *empty word*, that is, the word with no letters; it is denoted by $`ϵ`$. Let $`x=x_1x_2\mathrm{}x_n`$ be a word over $`X`$. We call $`|x|:=n`$ the *length* of $`x`$. A *subword* of $`x`$ is a word $`v=x_{i_1}x_{i_2}\mathrm{}x_{i_k}`$, where $`1i_1<i_2<\mathrm{}<i_kn`$. A *segment* of $`x`$ is a word $`v=x_ix_{i+1}\mathrm{}x_{i+k}`$. If $`X`$ and $`Y`$ are two linearly ordered alphabets, then two words $`x=x_1x_2\mathrm{}x_n`$ and $`y=y_1y_2\mathrm{}y_n`$ over $`X`$ and $`Y`$, respectively, are said to be *order equivalent* if $`x_i<x_j`$ precisely when $`y_i<y_j`$.

Let $`X=A\{\text{-}\text{-}\}`$ where $`A`$ is a linearly ordered alphabet. For each word $`x`$ let $`\overline{x}`$ be the word obtained from $`x`$ by deleting all dashes in $`x`$. A word $`p`$ over $`X`$ is called a *pattern* if it contains no two consecutive dashes and $`\overline{p}`$ has no repeated letters. By slight abuse of terminology we refer to the *length of a pattern* $`p`$ as the length of $`\overline{p}`$. Two patterns $`p`$ and $`q`$ of equal length are said to be *dash equivalent* if the $`i`$th letter in $`p`$ is a dash precisely when the $`i`$th letter in $`q`$ is a dash. If $`p`$ and $`q`$ are dash and order equivalent, then $`p`$ and $`q`$ are *equivalent*. In what follows a pattern will usually be taken to be over the alphabet $`\{a,b,c,d,\mathrm{}\}\{\text{-}\text{-}\}`$ where $`\{a,b,c,d,\mathrm{}\}`$ is ordered so that $`a<b<c<d<\mathrm{}`$.

Let $`[n]:=\{1,2,\mathrm{},n\}`$ (so $`[0]=\mathrm{}`$). A *permutation* of $`[n]`$ is bijection from $`[n]`$ to $`[n]`$. Let $`𝒮_n`$ be the set of permutations of $`[n]`$. We shall usually think of a permutation $`\pi `$ as the word $`\pi (1)\pi (2)\mathrm{}\pi (n)`$ over the alphabet $`[n]`$. In particular, $`𝒮_0=\{ϵ\}`$, since there is only one bijection from $`\mathrm{}`$ to $`\mathrm{}`$, the empty map. We say that a subword $`\sigma `$ of $`\pi `$ is a $`p`$-*subword* if by replacing (possibly empty) segments of $`\pi `$ with dashes we can obtain a pattern $`q`$ equivalent to $`p`$ such that $`\overline{q}=\sigma `$. However, all patterns that we will consider will have a dash at the beginning and one at the end. For convenience, we therefore leave them out. For example, $`(a\text{-}\text{-}bc)`$ is a pattern, and the permutation $`491273865`$ contains three $`(a\text{-}\text{-}bc)`$-subwords, namely $`127`$, $`138`$, and $`238`$. A permutation is said to be *$`p`$-avoiding* if it does not contain any $`p`$-subwords. Define $`𝒮_n(p)`$ to be the set of $`p`$-avoiding permutations in $`𝒮_n`$ and, more generally, $`𝒮_n(A)=_{pA}𝒮_n(p)`$.

We may think of a pattern $`p`$ as a permutation statistic, that is, define $`p\pi `$ as the number of $`p`$-subwords in $`\pi `$, thus regarding $`p`$ as a function from $`𝒮_n`$ to $``$. For example, $`(a\text{-}\text{-}bc)\mathrm{\hspace{0.17em}491273865}=3`$. In particular, $`\pi `$ is $`p`$-avoiding if and only if $`p\pi =0`$. We say that two permutation statistics $`\mathrm{stat}`$ and $`\mathrm{stat}^{}`$ are *equidistributed* over $`A𝒮_n`$, if

$$\underset{\pi A}{}x^{\mathrm{stat}\pi }=\underset{\pi A}{}x^{\mathrm{stat}^{}\pi }.$$

In particular, this definition applies to patterns.

Let $`\pi =a_1a_2\mathrm{}a_n𝒮_n`$. An $`i`$ such that $`a_i>a_{i+1}`$ is called a *descent* in $`\pi `$. We denote by $`\mathrm{des}\pi `$ the number of descents in $`\pi `$. Observe that $`\mathrm{des}`$ can be defined as the pattern $`(ba)`$, that is, $`\mathrm{des}\pi =(ba)\pi `$. A *left-to-right minimum* of $`\pi `$ is an element $`a_i`$ such that $`a_i<a_j`$ for every $`j<i`$. The number of left-to-right minima is a permutation statistic. Analogously we also define *left-to-right maximum*, *right-to-left minimum*, and *right-to-left maximum*.

In this paper we will relate permutations avoiding a given set of patterns to other better known combinatorial structures. Here follows a brief description of these structures.

### Set partitions

A *partition* of a set $`S`$ is a family, $`\pi =\{A_1,A_2,\mathrm{},A_k\}`$, of pairwise disjoint non-empty subsets of $`S`$ such that $`S=_iA_i`$. We call $`A_i`$ a *block* of $`\pi `$. The total number of partitions of $`[n]`$ is called a *Bell number* and is denoted $`B_n`$. For reference, the first few Bell numbers are

$$1,1,2,5,15,52,203,877,4140,21147,115975,678570,4213597.$$

Let $`S(n,k)`$ be the number of partitions of $`[n]`$ into $`k`$ blocks; these numbers are called the *Stirling numbers of the second kind*.

### Non-overlapping partitions

Two blocks $`A`$ and $`B`$ of a partition $`\pi `$ *overlap* if

$$\mathrm{min}A<\mathrm{min}B<\mathrm{max}A<\mathrm{max}B.$$

A partition is *non-overlapping* if no pairs of blocks overlap. Thus

$$\pi =\{\{1,2,5,13\},\{3,8\},\{4,6,7\},\{9\},\{10,11,12\}\}$$

is non-overlapping. A pictorial representation of $`\pi `$ is

$$\pi =\begin{array}{c}\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \\ \text{1}\text{ }\text{ }\text{2}\text{ }\text{ }\text{3}\text{ }\text{ }\text{4}\text{ }\text{ }\text{5}\text{ }\text{ }\text{6}\text{ }\text{ }\text{7}\text{ }\text{ }\text{8}\text{ }\text{ }\text{9}\text{ }\text{ }\text{10}\text{ }\text{ }\text{11}\text{ }\text{ }\text{12}\text{ }\text{ }\text{13}\end{array}.$$

Let $`B_n^{}`$ be the number of non-overlapping partitions of $`[n]`$; this number is called the $`n`$th *Bessel number* \[4, p. 423\]. The first few Bessel numbers are

$$1,1,2,5,14,43,143,509,1922,7651,31965,139685,636712.$$

We denote by $`S^{}(n,k)`$ the number of non-overlapping partitions of $`[n]`$ into $`k`$ blocks.

### Involutions

An *involution* is a permutation which is its own inverse. We denote by $`I_n`$ the number of involutions in $`𝒮_n`$. The sequence $`\{I_n\}_0^{\mathrm{}}`$ starts with

$$1,1,2,4,10,26,76,232,764,2620,9496,35696,140152.$$

### Dyck paths

A *Dyck path* of length $`2n`$ is a lattice path from $`(0,0)`$ to $`(2n,0)`$ with steps $`(1,1)`$ and $`(1,1)`$ that never goes below the $`x`$-axis. Letting $`u`$ and $`d`$ represent the steps $`(1,1)`$ and $`(1,1)`$ respectively, we code such a path with a word over $`\{u,d\}`$. For example, the path

is coded by $`uuduuddd`$. The $`n`$th *Catalan number* $`C_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)`$ counts the number of Dyck paths of length $`2n`$. The sequence of Catalan numbers starts with

$$1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012.$$

### Motzkin paths

A *Motzkin path* of length $`n`$ is a lattice path from $`(0,0)`$ to $`(n,0)`$ with steps $`(1,0)`$, $`(1,1)`$, and $`(1,1)`$ that never goes below the $`x`$-axis. Letting $`\mathrm{}`$, $`u`$, and $`d`$ represent the steps $`(1,0)`$, $`(1,1)`$, and $`(1,1)`$ respectively, we code such a path with a word over $`\{\mathrm{},u,d\}`$. For example, the path

is coded by $`u\mathrm{}\mathrm{}ud\mathrm{}d\mathrm{}`$. The $`n`$th *Motzkin number* $`M_n`$ is the number of Motzkin paths of length $`n`$. The first few of the Motzkin numbers are

$$1,1,2,4,9,21,51,127,323,835,2188,5798,15511.$$

## 3. Three classes of patterns

Let $`\pi =a_1a_2\mathrm{}a_n𝒮_n`$. Define the *reverse* of $`\pi `$ as $`\pi ^r:=a_n\mathrm{}a_2a_1`$, and define the *complement* of $`\pi `$ by $`\pi ^c(i)=n+1\pi (i)`$, where $`i[n]`$.

###### Proposition 1.

With respect to being equidistributed, the twelve pattern statistics of length three with one dash fall into the following three classes.

* $`a\text{-}\text{-}bc`$, $`c\text{-}\text{-}ba`$, $`ab\text{-}\text{-}c`$, $`cb\text{-}\text{-}a`$.
* $`a\text{-}\text{-}cb`$, $`c\text{-}\text{-}ab`$, $`ba\text{-}\text{-}c`$, $`bc\text{-}\text{-}a`$.
* $`b\text{-}\text{-}ac`$, $`b\text{-}\text{-}ca`$, $`ac\text{-}\text{-}b`$, $`ca\text{-}\text{-}b`$.

###### Proof.

The bijections $`\pi \pi ^r`$, $`\pi \pi ^c`$, and $`\pi (\pi ^r)^c`$ give the equidistribution part of the result. Calculations show that these three distributions differ pairwise on $`𝒮_4`$. ∎

## 4. Permutations avoiding a pattern of class one or two

###### Proposition 2.

Partitions of $`[n]`$ are in one-to-one correspondence with $`(a\text{-}\text{-}bc)`$-avoiding permutations in $`𝒮_n`$. Hence $`|𝒮_n(a\text{-}\text{-}bc)|=B_n`$.

###### First proof.

Recall that the Bell numbers satisfy $`B_0=1`$, and

$$B_{n+1}=\underset{k=0}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{n}{k}\right)B_k.$$

We show that $`|𝒮_n(a\text{-}\text{-}bc)|`$ satisfy the same recursion. Clearly, $`𝒮_0(a\text{-}\text{-}bc)=\{ϵ\}`$. For $`n>0`$, let $`M=\{2,3,\mathrm{},n+1\}`$, and let $`S`$ be a $`k`$ element subset of $`M`$. For each $`(a\text{-}\text{-}bc)`$-avoiding permutation $`\sigma `$ of $`S`$ we construct a unique $`(a\text{-}\text{-}bc)`$-avoiding permutation $`\pi `$ of $`[n+1]`$. Let $`\tau `$ be the word obtained by writing the elements of $`MS`$ in decreasing order. Define $`\pi :=\sigma 1\tau `$.

Conversely, if $`\pi =\sigma 1\tau `$ is a given $`(a\text{-}\text{-}bc)`$-avoiding permutation of $`[n+1]`$, where $`|\sigma |=k`$, then the letters of $`\tau `$ are in decreasing order, and $`\sigma `$ is an $`(a\text{-}\text{-}bc)`$-avoiding permutation of the $`k`$ element set $`\{2,3,\mathrm{},n+1\}\{i:i\text{ is a letter in }\tau \}`$. ∎

###### Second proof.

Given a partition $`\pi `$ of $`[n]`$, we introduce a standard representation of $`\pi `$ by requiring that:

* Each block is written with its least element first, and the rest of the elements of that block are written in decreasing order.
* The blocks are written in decreasing order of their least element, and with dashes separating the blocks.

Define $`\widehat{\pi }`$ to be the permutation we obtain from $`\pi `$ by writing it in standard form and erasing the dashes. We now argue that $`\widehat{\pi }:=a_1a_2\mathrm{}a_n`$ avoids $`(a\text{-}\text{-}bc)`$. If $`a_i<a_{i+1}`$, then $`a_i`$ and $`a_{i+1}`$ are the first and the second element of some block. By the construction of $`\widehat{\pi }`$, $`a_i`$ is a left-to-right minimum, hence there is no $`j[i1]`$ such that $`a_j<a_i`$.

Conversely, $`\pi `$ can be recovered uniquely from $`\widehat{\pi }`$ by inserting a dash in $`\widehat{\pi }`$ preceding each left-to-right minimum, apart from the first letter in $`\widehat{\pi }`$. Thus $`\pi \widehat{\pi }`$ gives the desired bijection. ∎

###### Example 3.

As an illustration of the map defined in the above proof, let

$$\pi =\{\{1,3,5\},\{2,6,9\},\{4,7\},\{8\}\}.$$

Its standard form is $`8\text{-}\text{-}47\text{-}\text{-}296\text{-}\text{-}153`$. Thus $`\widehat{\pi }=847296153`$.

###### Porism 4.

Let $`L(\pi )`$ be the number of left-to-right minima of $`\pi `$. Then

$$\underset{\pi 𝒮_n(a\text{-}\text{-}bc)}{}x^{L(\pi )}=\underset{k0}{}S(n,k)x^k.$$

###### Proof.

This result follows readily from the second proof of Proposition 2. We here give a different proof, which is based on the fact that the Stirling numbers of the second kind satisfy

$$S(n,k)=S(n1,k1)+kS(n1,k).$$

Let $`T(n,k)`$ be the number of permutations in $`𝒮_n(a\text{-}\text{-}bc)`$ with $`k`$ left-to-right minima. We show that the $`T(n,k)`$ satisfy the same recursion as the $`S(n,k)`$.

Let $`\pi `$ be an $`(a\text{-}\text{-}bc)`$-avoiding permutation of $`[n1]`$. To insert $`n`$ in $`\pi `$, preserving $`(a\text{-}\text{-}bc)`$-avoidance, we can put $`n`$ in front of $`\pi `$ or we can insert $`n`$ immediately after each left-to-right minimum. Putting $`n`$ in front of $`\pi `$ creates a new left-to-right minimum, while inserting $`n`$ immediately after a left-to-right minimum does not. ∎

###### Proposition 5.

Partitions of $`[n]`$ are in one-to-one correspondence with $`(a\text{-}\text{-}cb)`$-avoiding permutations in $`𝒮_n`$. Hence $`|𝒮_n(a\text{-}\text{-}cb)|=B_n`$.

###### Proof.

Let $`\pi `$ be a partition of $`[n]`$. We introduce a standard representation of $`\pi `$ by requiring that:

* The elements of a block are written in increasing order.
* The blocks are written in decreasing order of their least element, and with dashes separating the blocks.

Notice that this standard representation is different from the one given in the second proof of Proposition 2. Define $`\widehat{\pi }`$ to be the permutation we obtain from $`\pi `$ by writing it in standard form and erasing the dashes. It easy to see that $`\widehat{\pi }`$ avoids $`(a\text{-}\text{-}cb)`$. Conversely, $`\pi `$ can be recovered uniquely from $`\widehat{\pi }`$ by inserting a dash in between each descent in $`\widehat{\pi }`$. ∎

###### Example 6.

As an illustration of the map defined in the above proof, let

$$\pi =\{\{1,3,5\},\{2,6,9\},\{4,7\},\{8\}\}.$$

Its standard form is $`8\text{-}\text{-}47\text{-}\text{-}269\text{-}\text{-}135`$. Thus $`\widehat{\pi }=847269135`$.

###### Porism 7.

$$\underset{\pi 𝒮_n(a\text{-}\text{-}cb)}{}x^{1+\mathrm{des}\pi }=\underset{k0}{}S(n,k)x^k.$$

###### Proof.

From the proof of Proposition 5 we see that $`\pi `$ has $`k+1`$ blocks precisely when $`\widehat{\pi }`$ has $`k`$ descents. ∎

###### Proposition 8.

Involutions in $`𝒮_n`$ are in one-to-one correspondence with permutations in $`𝒮_n`$ that avoid $`(a\text{-}\text{-}bc)`$ and $`(a\text{-}\text{-}cb)`$. Hence

$$|𝒮_n(a\text{-}\text{-}bc,a\text{-}\text{-}cb)|=I_n.$$

###### Proof.

We give a combinatorial proof using a bijection that is essentially identical to the one given in the second proof of Proposition 2.

Let $`\pi 𝒮_n`$ be an involution. Recall that $`\pi `$ is an involution if and only if each cycle of $`\pi `$ is of length one or two. We now introduce a standard form for writing $`\pi `$ in cycle notation by requiring that:

* Each cycle is written with its least element first.
* The cycles are written in decreasing order of their least element.

Define $`\widehat{\pi }`$ to be the permutation obtained from $`\pi `$ by writing it in standard form and erasing the parentheses separating the cycles.

Observe that $`\widehat{\pi }`$ avoids $`(a\text{-}\text{-}bc)`$: Assume that $`a_i<a_{i+1}`$, that is $`(a_ia_{i+1})`$ is a cycle in $`\pi `$, then $`a_i`$ is a left-to-right minimum in $`\pi `$. This is guaranteed by the construction of $`\widehat{\pi }`$. Thus there is no $`j<i`$ such that $`a_j<a_i`$.

The permutation $`\widehat{\pi }`$ also avoids $`(a\text{-}\text{-}cb)`$: Assume that $`a_i>a_{i+1}`$, then $`a_{i+1}`$ must be the smallest element of some cycle. Then $`a_i`$ is a left-to-right minimum in $`\pi `$.

Conversely, if $`\widehat{\pi }:=a_1\mathrm{}a_n`$ is an $`\{a\text{-}\text{-}bc,a\text{-}\text{-}cb\}`$-avoiding permutation then the involution $`\pi `$ is given by: $`(a_ia_{i+1})`$ is a cycle in $`\pi `$ if and only if $`a_i<a_{i+1}`$. ∎

###### Example 9.

The involution $`\pi =826543719`$ written in standard form is

$$(9)(7)(\mathrm{4\hspace{0.17em}5})(\mathrm{3\hspace{0.17em}6})(2)(\mathrm{1\hspace{0.17em}8}),$$

and hence $`\widehat{\pi }=974536218`$.

###### Porism 10.

$$𝒮_n(a\text{-}\text{-}bc,a\text{-}\text{-}cb)=𝒮_n(a\text{-}\text{-}bc,acb)=𝒮_n(abc,a\text{-}\text{-}cb)=𝒮_n(abc,acb).$$

###### Proof.

Kitaev  observed that the dashes in the patterns $`(a\text{-}\text{-}bc)`$ and $`(a\text{-}\text{-}cb)`$ are immaterial for the proof of Proposition 8. The result may, however, also be proved directly. For an example of such a proof see the proof of Lemma 21. ∎

###### Porism 11.

The number of permutations in $`𝒮_{n+k}(a\text{-}\text{-}bc,a\text{-}\text{-}cb)`$ with $`n1`$ descents equals the number of involutions in $`𝒮_{n+k}`$ with $`nk`$ fixed points.

###### Proof.

Under the bijection $`\pi \widehat{\pi }`$ in the proof of Proposition 8, a cycle of length two in $`\pi `$ corresponds to an occurrence of $`(ab)`$ in $`\widehat{\pi }`$. Hence, if $`\pi `$ has $`n2k`$ fixed points, then $`\widehat{\pi }`$ has $`nk1`$ descents. Substituting $`n+k`$ for $`n`$ we get the desired result. ∎

To take the analysis of descents in $`\{a\text{-}\text{-}bc,a\text{-}\text{-}cb\}`$-avoiding permutations further, we introduce the polynomial

$$A_n(x)=\underset{\pi 𝒮_n(a\text{-}\text{-}bc,a\text{-}\text{-}cb)}{}x^{1+\mathrm{des}\pi },$$

and call it the $`n`$th *Eulerian polynomial for $`\{a\text{-}\text{-}bc,a\text{-}\text{-}cb\}`$-avoiding permutations*. Direct enumeration shows that the sequence $`\{A_n(x)\}`$ starts with

$$\begin{array}{ccccccccccccccccc}\hfill A_0(x)& =& 1\hfill & & & & & & & & & & & & & & \\ \hfill A_1(x)& =& & +& x\hfill & & & & & & & & & & & & \\ \hfill A_2(x)& =& & & x\hfill & +& x^2\hfill & & & & & & & & & & \\ \hfill A_3(x)& =& & & & & 3x^2\hfill & +& x^3\hfill & & & & & & & & \\ \hfill A_4(x)& =& & & & & 3x^2\hfill & +& 6x^3\hfill & +& x^4\hfill & & & & & & \\ \hfill A_5(x)& =& & & & & & & 15x^3\hfill & +& 10x^4\hfill & +& x^5\hfill & & & & \\ \hfill A_6(x)& =& & & & & & & 15x^3\hfill & +& 45x^4\hfill & +& 15x^5\hfill & +& x^6\hfill & & \\ \hfill A_7(x)& =& & & & & & & & & 105x^4\hfill & +& 105x^5\hfill & +& 21x^6\hfill & +& x^7.\hfill \end{array}$$

We will relate these polynomials to the so called Bessel polynomials. The $`n`$th *Bessel polynomial* $`y_n(x)`$ is defined by

$$y_n(x)=\underset{k=0}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{n+k}{k}\right)\left(\genfrac{}{}{0pt}{}{n}{k}\right)\frac{k!}{2^k}x^k.$$
(1)
The first six of the Bessel polynomials are

$$\begin{array}{ccccccccccccccc}\hfill y_0(x)& =& 1\hfill & & & & & & & & & & & & \\ \hfill y_1(x)& =& 1\hfill & +& x\hfill & & & & & & & & & & \\ \hfill y_2(x)& =& 1\hfill & +& 3x\hfill & +& 3x^2\hfill & & & & & & & & \\ \hfill y_3(x)& =& 1\hfill & +& 6x\hfill & +& 15x^2\hfill & +& 15x^3\hfill & & & & & & \\ \hfill y_4(x)& =& 1\hfill & +& 10x\hfill & +& 45x^2\hfill & +& 105x^3\hfill & +& 105x^4\hfill & & & & \\ \hfill y_5(x)& =& 1\hfill & +& 15x\hfill & +& 105x^2\hfill & +& 420x^3\hfill & +& 945x^4\hfill & +& 945x^5.\hfill & & \end{array}$$

These polynomials satisfy the second order differential equation

$$x^2\frac{d^2y}{dx^2}+2(x+1)\frac{dy}{dx}=n(n+1)y.$$

Moreover, the Bessel polynomials satisfy the recurrence relation

$$y_{n+1}(x)=(2n+1)xy_n(x)+y_{n1}(x).$$
(2)
###### Proposition 12.

Let $`y_n(x)`$ be the $`n`$th Bessel polynomial, and let $`A_n(x)`$ be the $`n`$th Eulerian polynomial for $`\{a\text{-}\text{-}bc,a\text{-}\text{-}cb\}`$-avoiding permutations. Then

* $`_ny_n(x)(xt)^n`$ generates $`\{A_n(t)\}`$, that is

$$\underset{n0}{}A_n(t)x^n=\underset{n0}{}y_n(x)(xt)^n.$$
* $`A_0(x)=1`$, $`A_1(x)=x`$, and for $`n2`$, we have

$$A_{n+2}(x)=x(1+x+2x\frac{d}{dx})A_n(x).$$
* $`A_n(x)`$ is explicitly given by

$$A_n(x)=\underset{k=0}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{n}{k}\right)\left(\genfrac{}{}{0pt}{}{nk}{k}\right)\frac{k!}{2^k}x^{nk}.$$

###### Proof.

Let $`I_n^k`$ denote the number of involutions in $`𝒮_n`$ with $`k`$ fixed points. Then Porism 11 is equivalently stated as

$$A_n(x)=\underset{k0}{}I_n^{2kn}x^k.$$
(3)
In  Dulucq and Favreau showed that the Bessel polynomials are given by

$$y_n(x)=\underset{k0}{}I_{n+k}^{nk}x^k.$$
(4)
To prove (i), multiply Equation (4) by $`(xt)^n`$ and sum over $`n`$.

$`{\displaystyle \underset{n0}{}}y_n(x)(xt)^n`$ $`={\displaystyle \underset{n0}{}}{\displaystyle \underset{k0}{}}I_{n+k}^{nk}t^nx^{n+k}`$
$`={\displaystyle \underset{k0}{}}{\displaystyle \underset{n0}{}}I_k^{2nk}t^nx^k`$ By substituting $`nk`$ for $`k`$.
$`={\displaystyle \underset{k0}{}}A_k(t)x^k`$ By Equation (3).
We now multiply Equation (2) by $`(xt)^n`$ and sum over $`n`$. Tedious but straightforward calculations then yield (ii) from (i). Finally, we obtain (iii) from Equation (1) by identifying coefficients in (i). ∎

###### Definition 13.

Let $`\pi `$ be an arbitrary partition whose non-singleton blocks $`\{A_1,\mathrm{},A_k\}`$ are ordered so that for all $`i[k1]`$, $`\mathrm{min}A_i>\mathrm{min}A_{i+1}`$. If $`\mathrm{max}A_i>\mathrm{max}A_{i+1}`$ for all $`i[k1]`$, then we call $`\pi `$ a *monotone partition*. The set of monotone partitions of $`[n]`$ is denoted by $`_n`$.

###### Example 14.

The partition

$$\pi =\begin{array}{c}\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{1}\text{ }\text{ }\text{2}\text{ }\text{ }\text{3}\text{ }\text{ }\text{4}\text{ }\text{ }\text{5}\text{ }\text{ }\text{6}\text{ }\text{ }\text{7}\text{ }\text{ }\text{8}\text{ }\text{ }\text{9}\text{ }\text{ }\text{10}\text{ }\text{ }\text{11}\text{ }\text{ }\text{12}\text{ }\text{ }\text{13}\end{array}$$

is monotone.

###### Proposition 15.

Monotone partitions of $`[n]`$ are in one-to-one correspondence with permutations in $`𝒮_n`$ that avoid $`(a\text{-}\text{-}bc)`$ and $`(ab\text{-}\text{-}c)`$. Hence

$$|𝒮_n(a\text{-}\text{-}bc,ab\text{-}\text{-}c)|=|_n|.$$

###### Proof.

Given $`\pi `$ in $`_n`$, let $`A_1\text{-}\text{-}A_2\text{-}\text{-}\mathrm{}\text{-}\text{-}A_k`$ be the result of writing $`\pi `$ in the standard form given in the second proof of Proposition 2, and let $`\widehat{\pi }=A_1A_2\mathrm{}A_k`$. By the construction of $`\widehat{\pi }`$ the fist letter in each $`A_i`$ is a left-to-right minimum. Furthermore, since $`\pi `$ is monotone the second letter in each non-singleton $`A_i`$ is a right-to-left maximum. Therefore, if $`xy`$ is an $`(ab)`$-subword of $`\widehat{\pi }`$, then $`x`$ is left-to-right minimum and $`y`$ is a right-to-left maximum. Thus $`\widehat{\pi }`$ avoids both $`(a\text{-}\text{-}bc)`$ and $`(ab\text{-}\text{-}c)`$.

Conversely, given $`\widehat{\pi }`$ in $`𝒮_n(a\text{-}\text{-}bc,ab\text{-}\text{-}c)`$, let $`A_1\text{-}\text{-}A_2\text{-}\text{-}\mathrm{}\text{-}\text{-}A_k`$ be the result of inserting a dash in $`\widehat{\pi }`$ preceding each left-to-right minimum, apart from the first letter in $`\widehat{\pi }`$. Since $`\widehat{\pi }`$ is $`(ab\text{-}\text{-}c)`$-avoiding, the second letter in each non-singleton $`A_i`$ is a right-to-left maximum. The second letter in $`A_i`$ is the maximal element of $`A_i`$ when $`A_i`$ is viewed as a set. Thus $`\pi =\{A_1,A_2,\mathrm{},A_k\}`$ is monotone. ∎

What is left for us to show is that there is a one-to-one correspondence between monotone partitions and non-overlapping partitions. The proof we give is strongly influenced by the work of Flajolet .

###### Proposition 16.

Monotone partitions of $`[n]`$ are in one-to-one correspondence with non-overlapping partitions of $`[n]`$. Hence $`|_n|=B_n^{}`$.

###### Proof.

If $`k`$ is the minimal element of a non-singleton block, then call $`k`$ the *first* element of that block. Similarly, If $`k`$ is the maximal element of a non-singleton block, then call $`k`$ the *last* element of that block. An element of a non-singleton that is not a first or last element is called an *intermediate* element. Let us introduce an ordering of the blocks of a partition. A block $`A`$ is smaller than a block $`B`$ if $`\mathrm{min}A<\mathrm{min}B`$.

We define a map $`\mathrm{\Phi }`$ that to each non-overlapping partition $`\pi `$ of $`[n]`$ gives a unique monotone partition $`\mathrm{\Phi }(\pi )`$ of $`[n]`$. Let the integer $`k`$ range from $`1`$ to $`n`$.

* If $`k`$ is the first element of a block of $`\pi `$, then open a new block in $`\mathrm{\Phi }(\pi )`$ by letting $`k`$ be its first element. (A block $`B`$ is open if $`\mathrm{max}B<k`$.)
* If $`k`$ is the last element of a block of $`\pi `$, then close the smallest open block of $`\mathrm{\Phi }(\pi )`$ by letting $`k`$ be its last element.
* If $`k`$ is an intermediate element of some block $`B`$ of $`\pi `$, and $`B`$ is the $`i`$:th largest open block of $`\pi `$, then let $`k`$ belong to the $`i`$th largest open block of $`\mathrm{\Phi }(\pi )`$.
* If $`\{k\}`$ is a singleton block of $`\pi `$, then let $`\{k\}`$ be a singleton block of $`\mathrm{\Phi }(\pi )`$.

Observe that $`\mathrm{\Phi }(\pi )`$ is monotone. Indeed, it is only in (b) that we close a block of $`\mathrm{\Phi }(\pi )`$, and we always close the smallest open block of $`\mathrm{\Phi }(\pi )`$.

Conversely, we give a map $`\mathrm{\Psi }`$ that to each monotone partition $`\pi `$ be a of $`[n]`$ gives a unique non-overlapping partition $`\mathrm{\Psi }(\pi )`$ of $`[n]`$. Define $`\mathrm{\Psi }`$ the same way as $`\mathrm{\Phi }`$ is defined, except for case (c), where we instead of closing the smallest open block close the largest open block.

It is easy to see that $`\mathrm{\Phi }`$ and $`\mathrm{\Psi }`$ are each others inverses and hence they are bijections. ∎

###### Corollary 17.

The NOPs (non-overlapping partitions) of $`[n]`$ are in one-to-one correspondence with permutations in $`𝒮_n`$ that avoid $`(a\text{-}\text{-}bc)`$ and $`(ab\text{-}\text{-}c)`$. Hence

$$|𝒮_n(a\text{-}\text{-}bc,ab\text{-}\text{-}c)|=B_n^{}.$$

###### Proof.

Follows immediately from Proposition 15 together with Proposition 16. ∎

###### Example 18.

By the proof of Proposition 16, the non-overlapping partition

$`\pi `$ $`=\begin{array}{c}\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \\ \text{1}\text{ }\text{ }\text{2}\text{ }\text{ }\text{3}\text{ }\text{ }\text{4}\text{ }\text{ }\text{5}\text{ }\text{ }\text{6}\text{ }\text{ }\text{7}\text{ }\text{ }\text{8}\text{ }\text{ }\text{9}\text{ }\text{ }\text{10}\text{ }\text{ }\text{11}\text{ }\text{ }\text{12}\text{ }\text{ }\text{13}\end{array}`$
corresponds to the monotone partition
$`\mathrm{\Phi }(\pi )`$ $`=\begin{array}{c}\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\\ \text{1}\text{ }\text{ }\text{2}\text{ }\text{ }\text{3}\text{ }\text{ }\text{4}\text{ }\text{ }\text{5}\text{ }\text{ }\text{6}\text{ }\text{ }\text{7}\text{ }\text{ }\text{8}\text{ }\text{ }\text{9}\text{ }\text{ }\text{10}\text{ }\text{ }\text{11}\text{ }\text{ }\text{12}\text{ }\text{ }\text{13}\end{array}`$
that according to the proof of Proposition 15 corresponds to the $`\{a\text{-}\text{-}bc,ab\text{-}\text{-}c\}`$-avoiding permutation
$`\widehat{\mathrm{\Phi }(\pi )}`$ $`=\mathrm{\hspace{0.17em}10\hspace{0.33em}13\hspace{0.33em}11\hspace{0.33em}9\hspace{0.33em}4\hspace{0.33em}12\hspace{0.33em}6\hspace{0.33em}3\hspace{0.33em}8\hspace{0.33em}1\hspace{0.33em}7\hspace{0.33em}5\hspace{0.33em}2}.`$
###### Porism 19.

Let $`L(\pi )`$ be the number of left-to-right minima of $`\pi `$. Then

$$\underset{\pi 𝒮_n(a\text{-}\text{-}bc,ab\text{-}\text{-}c)}{}x^{L(\pi )}=\underset{k0}{}S^{}(n,k)x^k.$$

###### Proof.

Under the bijection $`\pi \widehat{\pi }`$ in the proof of Proposition 15, the number of blocks in $`\pi `$ determines the number of left-to-right minima of $`\widehat{\pi }`$, and vice versa. The number of blocks is not changed by the bijection $`\mathrm{\Phi }_1\mathrm{\Psi }_2`$ in the proof of Proposition 16. ∎

## 5. Permutations avoiding a pattern of class three

In  Knuth observed that there is a one-to-one correspondence between $`(b\text{-}\text{-}a\text{-}\text{-}c)`$-avoiding permutations and Dyck paths. For completeness and future reference we give this result as a lemma, and prove it using one of the least known bijections. First we need a definition. For each word $`x=x_1x_2\mathrm{}x_n`$ without repeated letters, we define the *projection* of $`x`$ onto $`S_n`$, which we denote $`\mathrm{proj}(x)`$, by

$$\mathrm{proj}(x)=a_1a_2\mathrm{}a_n,\text{ where }a_i=|\{j[n]:x_ix_j\}|.$$

Equivalently, $`\mathrm{proj}(x)`$ is the permutation in $`𝒮_n`$ which is order equivalent to $`x`$. For example, $`\mathrm{proj}(265)=132`$.

###### Lemma 20.

$`|𝒮_n(b\text{-}\text{-}a\text{-}\text{-}c)|=C_n.`$

###### Proof.

Let $`\pi =a_1a_2\mathrm{}a_n`$ be a permutation of $`[n]`$ such that $`a_k=1`$. Then $`\pi `$ is $`(b\text{-}\text{-}a\text{-}\text{-}c)`$-avoiding if and only if $`\pi =\sigma 1\tau `$, where $`\sigma :=a_1\mathrm{}a_{k1}`$ is a $`(b\text{-}\text{-}a\text{-}\text{-}c)`$-avoiding permutation of $`\{n,n1,\mathrm{},nk+1\}`$, and $`\tau :=a_{k+1}\mathrm{}a_n`$ is a $`(b\text{-}\text{-}a\text{-}\text{-}c)`$-avoiding permutation of $`\{2,3,\mathrm{},k\}`$.

We define recursively a mapping $`\mathrm{\Phi }`$ from $`𝒮_n(b\text{-}\text{-}a\text{-}\text{-}c)`$ onto the set of Dyck paths of length $`2n`$. If $`\pi `$ is the empty word, then so is the Dyck path determined by $`\pi `$, that is, $`\mathrm{\Phi }(ϵ)=ϵ`$. If $`\pi ϵ`$, then we can use the factorisation $`\pi =\sigma 1\tau `$ from above, and define $`\mathrm{\Phi }(\pi )=u(\mathrm{\Phi }\mathrm{proj})(\sigma )d(\mathrm{\Phi }\mathrm{proj})(\tau )`$. It is easy to see that $`\mathrm{\Phi }`$ may be inverted, and hence is a bijection. ∎

###### Lemma 21.

A permutation avoids $`(b\text{-}\text{-}ac)`$ if and only if it avoids $`(b\text{-}\text{-}a\text{-}\text{-}c)`$.

###### Proof.

The sufficiency part of the proposition is trivial. The necessity part is not difficult either. Assume that $`\pi `$ contains a $`(b\text{-}\text{-}a\text{-}\text{-}c)`$-subword. Then there exist

$$A,B,C,n_1,n_2,\mathrm{},n_r[n],\text{ where }A<B<C,$$

such that $`BAC`$ is a subword of $`\pi `$, and $`An_1\mathrm{}n_rC`$ is a segment of $`\pi `$. If $`n_1>B`$, then $`BAn_1`$ form a $`(b\text{-}\text{-}ac)`$-subword in $`\pi `$. Assume that $`n_1<B`$. Indeed, to avoid forming a $`(b\text{-}\text{-}ac)`$-subword we will have to assume that $`n_i<B`$ for all $`i[r]`$, but then $`Bn_rC`$ is a $`(b\text{-}\text{-}ac)`$-subword. Accordingly we conclude that there exists at least one $`(b\text{-}\text{-}ac)`$-subword in $`\pi `$. ∎

###### Proposition 22.

Dyck paths of length $`2n`$ are in one-to-one correspondence with $`(b\text{-}\text{-}ac)`$-avoiding permutations in $`𝒮_n`$. Hence

$$|𝒮_n(b\text{-}\text{-}ac)|=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right).$$

###### Proof.

Follows immediately from Lemma 20 and Lemma 21. ∎

###### Proposition 23.

Let $`L(\pi )`$ be the number of left-to-right minima of $`\pi `$. Then

$$\underset{\pi 𝒮_n(b\text{-}\text{-}ac)}{}x^{L(\pi )}=\underset{k0}{}\frac{k}{2nk}\left(\genfrac{}{}{0pt}{}{2nk}{n}\right)x^k.$$

###### Proof.

A *return step* in a Dyck path $`\delta `$ is a $`d`$ such that $`\delta =\alpha u\beta d\gamma `$, for some Dyck paths $`\alpha `$, $`\beta `$, and $`\gamma `$. A useful observation is that every non-empty Dyck path $`\delta `$ can be uniquely decomposed as $`\delta =u\alpha d\beta `$, where $`\alpha `$ and $`\beta `$ are Dyck paths. This is the so-called *first return decomposition* of $`\delta `$. Let $`R(\delta )`$ denote the number of return steps in $`\delta `$.

In  Deutsch showed that the distribution of $`R`$ over all Dyck paths of length $`2n`$ is the distribution we claim that $`L`$ has over $`𝒮_n(b\text{-}\text{-}ac)`$.

Let $`\gamma `$ be a Dyck path of length $`2n`$, and let $`\gamma =u\alpha d\beta `$ be its first return decomposition. Then $`R(\gamma )=1+R(\beta )`$. Let $`\pi 𝒮_n(b\text{-}\text{-}ac)`$, and let $`\pi =\sigma 1\tau `$ be the decomposition given in the proof of Lemma 20. Then $`L(\pi )=1+L(\sigma )`$. The result now follows by induction. ∎

In addition, it is easy to deduce that left-to-right minima, left-to-right maxima, right-to-left minima, and right-to-left maxima all share the same distribution over $`𝒮_n(b\text{-}\text{-}ac)`$.

###### Proposition 24.

Motzkin paths of length $`n`$ are in one-to-one correspondence with permutations in $`𝒮_n`$ that avoid $`(a\text{-}\text{-}bc)`$ and $`(ac\text{-}\text{-}b)`$. Hence

$$|𝒮_n(a\text{-}\text{-}bc,ac\text{-}\text{-}b)|=M_n.$$

###### Proof.

We mimic the proof of Lemma 20. Let $`\pi 𝒮_n(a\text{-}\text{-}bc,ac\text{-}\text{-}b)`$. Since $`\pi `$ avoids $`(ac\text{-}\text{-}b)`$ it also avoids $`(a\text{-}\text{-}c\text{-}\text{-}b)`$ by Lemma 21 via $`\pi (\pi ^c)^r`$. Thus we may write $`\pi =\sigma n\tau `$, where $`\pi (k)=n`$, $`\tau `$ is an $`\{a\text{-}\text{-}bc,ac\text{-}\text{-}b\}`$-avoiding permutation of $`\{n1,n2,\mathrm{},nk+1\}`$, and $`\tau `$ is an $`\{a\text{-}\text{-}bc,ac\text{-}\text{-}b\}`$-avoiding permutation of $`[nk]`$. If $`\sigma ϵ`$ then $`\sigma =\sigma ^{}r`$ where $`r=nk+1`$, or else an $`(a\text{-}\text{-}bc)`$-subword would be formed with $`n`$ as the ’$`c`$’ in $`(a\text{-}\text{-}bc)`$. Define a map $`\mathrm{\Phi }`$ from $`𝒮_n(a\text{-}\text{-}bc,ac\text{-}\text{-}b)`$ to the set of Motzkin paths by $`\mathrm{\Phi }(ϵ)=ϵ`$ and

$$\mathrm{\Phi }(\pi )=\{\begin{array}{cc}\mathrm{}(\mathrm{\Phi }\mathrm{proj})(\sigma )\hfill & \text{ if }\pi =n\sigma ,\hfill \\ u(\mathrm{\Phi }\mathrm{proj})(\sigma )d\mathrm{\Phi }(\tau )\hfill & \text{ if }\pi =\sigma rn\tau \text{ and }r=nk+1.\hfill \end{array}$$

Its routine to find the inverse of $`\mathrm{\Phi }`$. ∎

###### Example 25.

Let us find the Motzkin path associated to the $`\{a\text{-}\text{-}bc,ac\text{-}\text{-}b\}`$-avoiding permutation $`76453281`$.

$`\mathrm{\Phi }(76453\mathrm{𝟐𝟖}1)`$ $`=`$ $`u\mathrm{\Phi }(\mathrm{𝟓}4231)d\mathrm{\Phi }(\mathrm{𝟏})`$
$`=`$ $`u\mathrm{}\mathrm{\Phi }(\mathrm{𝟒}231)d\mathrm{}`$
$`=`$ $`u\mathrm{}\mathrm{}\mathrm{\Phi }(\mathrm{𝟐𝟑}1)d\mathrm{}`$
$`=`$ $`u\mathrm{}\mathrm{}ud\mathrm{\Phi }(\mathrm{𝟏})d\mathrm{}`$
$`=`$ $`u\mathrm{}\mathrm{}ud\mathrm{}d\mathrm{}`$
## Acknowledgement

I am greatly indebted to my advisor Einar Steingrímsson, who put his trust in me and gave me the opportunity to study mathematics on a postgraduate level. This work has benefited from his knowledge, enthusiasm and generosity.


format: text

text:
# First Neutrino Observations from the Sudbury Neutrino Observatory

## 1 INTRODUCTION

This paper presents the first neutrino observations from the Sudbury Neutrino Observatory  (SNO), a 1000 tonne heavy-water-based Cerenkov detector situated 2 km underground in INCO’s Creighton mine near Sudbury, Ontario, Canada. The SNO detector has been filled with water since May, 1999. After a commissioning period, the detector parameters were fixed at the start of November 1999 and neutrino data acquisition and associated calibrations have been taking place almost continuously since then. In this initial phase of the project, the detector is filled with pure heavy water. Neutrinos from 8B decay in the sun are observed from Cerenkov processes following these reactions:
1. The Charged Current (CC) reaction, specific to electron neutrinos:

$$d+\nu _ep+p+e^{}$$

This reaction has a Q value of -1.4 MeV and the electron energy is strongly correlated with the neutrino energy, providing very good sensitivity to spectral distortions.
2. Neutral Current (NC) reaction, equally sensitive to all non-sterile neutrino types:

$$\nu _x+dn+p+\nu _x$$

This reaction has a threshold of 2.2 MeV and is observed through the detection of neutrons by three different techniques in separate phases of the experiment.
3. Elastic Scattering (ES) reaction:

$$\nu _x+e^{}e^{}+\nu _x$$

This reaction has a substantially lower cross section than the other two and is predominantly sensitive to electron neutrinos; they have about six times greater cross-section than $`\mu `$ or $`\tau `$ neutrinos.

The reaction:

$$\overline{\nu }_e+dn+n+e^+$$
(1)
also provides a unique signature for anti-electron neutrinos from various possible sources.
The SNO experimental plan calls for three phases of about one year each wherein different techniques will be employed for the detection of neutrons from the NC reaction. During the first phase, with pure heavy water, neutrons are observed through the Cerenkov light produced when neutrons are captured in deuterium, producing 6.25 MeV gammas. In this phase, the capture probability for such neutrons is about 25% and the Cerenkov light is relatively close to the threshold of about 5 MeV electron energy, imposed by radioactivity in the detector. (Figure 1). For the second phase, about 2.5 tonnes of NaCl will be added to the heavy water and neutron detection will be enhanced through capture on Cl, with about 8.6 MeV gamma energy release and about 83% capture efficiency. (See Figure 1). For the third phase, the salt is removed and an array of 3He- filled proportional counters will be installed to provide direct detection of neutrons with a capture efficiency of about 45%.

## 2 PHYSICS OBJECTIVES

The main physics goals for the Observatory are observations of:
\- Solar Neutrinos
\- Atmospheric Neutrinos
\- Supernova Neutrinos
\- Cosmic Ray Muons
\- Anti-electron neutrinos from various processes including transformations of solar neutrinos or relic supernova neutrinos.

For Solar Neutrinos, the combination of three detection reactions provides several sensitive ways to seek evidence for neutrino flavor change without relying on calculations of initial fluxes from solar models. The ratio of neutrino fluxes above a threshold, as observed by the CC and NC reactions provides a very sensitive way to observe transformations to active neutrinos.

The ratio of CC/NC can be observed during all three phases of operation. The sensitivity to the NC reaction is limited during the first phase, but there will be excellent sensitivity with different systematic uncertainties during the other two phases. The ratio of fluxes detected by the CC and ES reaction has a smaller dependence on flavor change to active species through the sensitivity to $`\mu `$ and $`\tau `$ neutrinos in the ES cross section. Events from the CC and ES reactions can be distinguished through the very different directional response. The ES reaction is strongly peaked away from the Sun, whereas the CC reaction has a form of approximately $`11/3`$ cos$`\theta _{sun}`$, with about a factor of two difference in rate between forward and backward directions relative to the Sun. The angular resolution of the detector is better than 25 degrees. The NC rate may be determined during the pure D2O phase partly through a distinctive variation as a function of radius. However, the definition of the number of events observed with this reaction is clearly enhanced by the addition of salt (see Figure 1), and will be determined independently of the Cerenkov signals when the 3He-filled proportional counters are installed. The observed spectrum for the CC reaction is a very sensitive indicator of distortions caused by the MSW effect because the energy of outgoing electrons is strongly correlated with the incoming neutrino energy and the detector energy resolution is better than 20% for the range of interest. With the relatively high statistical accuracy indicated by Figure 1, the SNO detector will also provide sensitive measurements of the solar neutrino flux as a function of zenith angle to search for MSW regeneration in the Earth. Correlations between flux, energy spectrum, zenith angle and time of year will also be studied. With the variety of reactions to be studied, the SNO detector can explore oscillations via the MSW effect or vacuum oscillation processes over the full range of parameters consistent with previous experiments. It could provide clear evidence for electron neutrino flavor change, including transformations to either active or sterile types.

## 3 DETECTOR PERFORMANCE

The SNO detector consists of 1000 tonnes of pure D2O contained within an acrylic vessel (12 m diameter, 5 cm thick), viewed by 9438 PMT’s mounted on a geodesic structure 18 m in diameter, all contained within a polyurethane-coated barrel-shaped cavity (22m diameter by 34 m high). The cavity volume outside the acrylic vessel (AV) is filled with purified H2O. There are 91 PMT’s looking outward from the geodesic structure, viewing the outer H2O volume.
The SNO detector has been full of water since May, 1999. During the period until November, 1999, detailed commissioning tests and calibrations were performed. There has been no substantial problem from electrical breakdown of high voltage connectors submerged in light water since nitrogen was added to the degassed water. During the period before November, a variety of adjustments were made to improve the light sensitivity by about 25% and to reduce the trigger threshold to about 2 MeV. Four additional PMT’s were installed in the neck of the acrylic vessel to provide a clear indication of instrumental light emitted in this region, probably from static discharges of insulating materials. 222Rn gas in the air above the heavy water was reduced to acceptable levels by flushing with boil-off gas from liquid nitrogen.
As of November, 1999, the desired detector specifications had been met, the detector parameters were frozen and production data accumulation was started, interspersed with a variety of calibration measurements. The detector performance has been very good, with more than 98.5% of all channels operational; a total event rate of less than 5 Hz above a threshold of about 20 hit PMT’s; PMT individual noise rates of less than 500 Hz for a threshold of about 0.3 photoelectrons, providing fewer than 2 noise hits per event.

## 4 CALIBRATION

Detector calibration is being carried out with a variety of techniques and sources. Electronic calibrations of pedestals, slopes and timing are performed regularly with pulsers. The 600,000 electronic constants are very stable. Optical properties of the detector have been studied using a diffusing ball, (Laserball) receiving light from a pulsed laser system providing wavelengths between 337 and 700 nm with variable intensity at repetition rates from near 0 to 45 Hz. This source and other calibration sources are moved within the D2O volume using a manipulator system capable of positioning them to better than 5 cm. Positions in the H2O volume between the D2O and the PMT’s are also accessible along vertical paths from above. A nearly mono-energetic 16N gamma ray source has also been deployed.

Figure 2 shows a spectrum from the 16N source compared with a Monte Carlo simulation, using optical parameters extracted from a preliminary analysis of the laserball data. A single constant corresponding to the average quantum efficiency of the PMT’s has been adjusted to match the centroid of these spectra. A further comparison of centroids for over 20 other locations throughout the D2O volume showed less than 2% difference between the data and the simulation at any point. An acrylic- encapsulated 242Cf fission neutron source has also been deployed to study the neutron response of the detector.
Other sources being prepared include a 19.8 MeV gamma source produced by the (p,t) reaction, a triggered source for the 232Th and 238U chains producing 2.6 and 2.4 MeV gammas and a source of 8Li, emitting betas up to 13 MeV. The short-lived 16N and 8Li activities are produced by a pulsed neutron generator located near the SNO detector and are transported via capillary tubing to decay chambers within the detector volume.

## 5 OBSERVATIONS TO DATE

In addition to Cerenkov light produced by neutrinos and radioactivity, there can be other sources of ”instrumental light” arising from parts of the detector. For example, it is well known that PMT’s can occasionally emit light, perhaps through internal electrical discharges. Light from these sources has very different characteristics from the typical patterns observed for Cerenkov light at solar neutrino energies. The light from a flashing PMT shows an early trigger for the flashing PMT, followed by light observed across the detector, at least 70 ns later. For SNO, six or more electronic channels surrounding the flashing PMT typically show pickup signals, distinguishing the events further from Cerenkov events.
Figure 3 shows the raw spectrum of events (solid line) observed with the detector for a fraction of the data obtained since the start of data taking in November, 1999. The events are plotted against NHIT, the number of PMT’s contained in a 400 ns second window surrounding the detector trigger (more than about 20 PMT’s hit within a 100 ns window). NHIT is approximately proportional to the electron energy for a Cerenkov event, with about 9 NHIT corresponding to 1 MeV. Only a fraction of the data have been shown as the remainder are being saved for a comparison after the cuts have been fully defined.

The dashed line shows the residual data after cuts have been imposed to remove events that show characteristics matching the Flashing PMT’s. The dotted line shows the residual data after further cuts are imposed to remove another class of events associated with bursts of light from the neck region of the detector. These events may arise from static discharges of insulating materials. Four additional PMT’s were installed in this region in September, 1999. They clearly observe these events and are very insensitive to light generated in the detector itself, as determined from the calibration sources. The dot and dash line shows the residual events after the imposition of further cuts which eliminate events that show characteristics of pickup in the electronic systems.

Two separate groups within the SNO Collaboration developed a series of cuts to eliminate these instrumental light sources and their results for the residual spectrum were virtually identical, lending confidence in the robustness with which these events can be distinguished from neutrinos. To ensure that these cuts do not remove a significant number of neutrino events, the fraction of signal loss was tested with the 16N source. The results are shown in Figure 4, indicating very low loss of signal in the region tested.

Following these cuts, algorithms based on timing and spatial information were used to reconstruct the position and direction of the events. Figure 5 shows the resulting spectrum for a large fiducial volume.

Superimposed on the data is the simulated spectrum for the CC reaction in Figure 1, scaled to the data. As the calibrations are not yet complete, the SNO collaboration has chosen not to quote a number for the flux of electron neutrinos measured by the CC reaction on deuterium. However, it should be apparent from the figure that the spectrum is well defined so that an accurate measurement will be obtained when further calibrations have been completed.

Figure 6 shows events as a function of the direction to the sun for a lower energy threshold and a larger fiducial volume. Even with somewhat more radioactive background included by these parameter choices, the peak at cos$`\theta _{sun}=1`$ from the ES reaction is apparent.

Figure 7 shows the distribution of events as a function of (radius/600cm)3, for a high-energy threshold. The radius of the AV is 600 cm, so the heavy water volume corresponds to values less than 1. It is apparent that there is a clear excess of events in this region, indicating the substantial contribution from the CC reaction on deuterium.

Figure 8 shows the distribution of events with a high energy threshold for a region in the light water outside the AV. Events have been selected to remove inward-coming gamma rays. The peak from ES events is apparent with a relatively small background.

## 6 RADIOACTIVE BACKGROUNDS

Radioactive backgrounds that contribute to the Cerenkov light in the detector arise from the decay chains of 238U and 232Th impurities in the water and other detector materials. At low energies, the dominant contributions come from impurities in the water. These contributions can be measured through the radioassay of the light and heavy water. They can also be measured independently through observation of the low energy region of the Cerenkov spectrum for events reconstructing in the water regions. Sensitive techniques have been developed for radioassay of 224Ra, 226Ra and 222Rn in the water. The measurements for Ra are performed by extracting the Ra on beads coated with manganese oxide or on ultrafiltration membranes coated with hydrous titanium oxide. After sampling hundreds of tonnes of water, these materials are measured for radioactive decay of the Ra with techniques sensitive to tens of atoms. (see reference for more details) The 222Rn is measured by degassing 50 or more tonnes of water and collecting the Rn gas with liquid nitrogen-cooled traps. The collected gas is then counted with ZnS coated scintillation cells (Lucas cells) to observe the alpha decays. These techniques have been employed to make very sensitive measurements of the water, as shown in Figures 9 and 10.

The Cerenkov light generated by the Th and U radioactivity can be observed at low energies as illustrated in figure 1 and observed in figures 3 and 5. As the decay products and sequence are different for the two chains it is also possible to use pattern recognition to obtain a statistical separation of the contributions from the two chains. Future calibrations will include the use of proportional counters containing Th and U chain sources to provide triggered events to calibrate the detector response in this region. However, the data to date, with large calibration uncertainties, do agree with the radioassay measurements. The light water in the SNO detector is designed to attenuate higher energy gamma rays (fission and alpha-induced) from radioactivity in the cavity walls and the PMT support structure. High-energy events reconstructed in the light water volume outside the AV are found to be predominantly inward going and the numbers decrease rapidly as a function of radius. Using calibration data from the 16N source positioned near the PMT’s, extrapolations of the number of high energy gammas interacting within the D2O volume indicate that fewer than a few percent of the events above NHIT = 60 in Figure 5 arise from external high energy gammas. In addition to the contributions to Cerenkov light, the presence of Th and U chain elements can produce a background for the NC reaction through the photodisintegration of deuterium by 2.6 MeV gammas from the Th chain and 2.4 MeV gammas from the U chain. The horizontal lines in Figure 10 individually represent contributions to the neutron background in the detector from photodisintegration equivalent to 5% of the signal expected for the NC reaction for the neutrino flux of BP98. As is apparent from the figure, these goals have been met for the U chain and are met within a factor of two for the Th chain.

## 7 CONCLUSIONS

Based on energy, direction and location information, the data in the regions of interest in Figures 5 to 8 appear to be dominated by 8B solar neutrino events observed with the CC and ES reactions, with very little background. This implies that measurements during the pure heavy water phase will provide an accurate measurement of the electron neutrino flux via the CC reaction after completion of further calibrations. The measurements of radioactivity imply that the NC measurements can be made with only a small uncertainty from the radioactive background.

## 8 Acknowledgments

This research has been financially supported in Canada by the Natural Sciences and Engineering Research Council, Industry Canada, National Research Council of Canada, Northern Ontario Heritage Fund Corporation and the Province of Ontario, in the United States by the Department of Energy, and in the United Kingdom by the Science and Engineering Research Council and the Particle Physics and Astronomy Research Council. Further support was provided by INCO, Atomic Energy of Canada Limited (AECL), Agra-Monenco, Canatom, Canadian Microelectronics Corporation and Northern Telecom. The heavy water has been loaned by AECL with the cooperation of Ontario Hydro. The provision of INCO of an underground site is greatly appreciated.

aThe SNO Collaboration includes: M. G. Boulay, E. Bonvin, M. Chen, F. A. Duncan, E. D. Earle, H. C. Evans, G.T. Ewan, R. J. Ford, A. L. Hallin, P. J. Harvey, J. D. Hepburn, C. Jillings, H. W. Lee, J. R. Leslie, H. B. Mak, A. B. McDonald, W. McLatchie, B. A. Moffat, B.C. Robertson, P. Skensved, B. Sur, Queen’s University, Kingston, Ontario K7L 3N6, Canada.; I. Blevis, F. Dalnoki-Veress, W. Davidson, J. Farine, D.R. Grant, C. K. Hargrove, I. Levine, K. McFarlane, T. Noble, V.M. Novikov, M. O’Neill, M. Shatkay, C. Shewchuk, D. Sinclair, Carleton University, Ottawa, Ontario K1S 5B6, Canada.; T. Andersen, M.C. Chon, P. Jagam, J. Law, I.T. Lawson, R. W. Ollerhead, J. J. Simpson, N. Tagg, J.X. Wang, University of Guelph, Guelph, Ontario N1G 2W1, Canada.; J. Bigu, J.H.M. Cowan, E. D. Hallman, R. U. Haq, J. Hewett, J.G. Hykawy, G. Jonkmans, A. Roberge, E. Saettler, M.H. Schwendener, H. Seifert, R. Tafirout, C. J. Virtue, Laurentian University, Sudbury, Ontario P3E 2C6, Canada.; S. Gil, J. Heise, R. Helmer, R.J. Komar, T. Kutter, C.W. Nally, H.S. Ng, R. Schubank,,Y. Tserkovnyak, C.E. Waltham, University of British Columbia, Vancouver, BC V6T 1Z1, Canada.; E. W. Beier, D. F. Cowen, E. D. Frank, W. Frati, P.T. Keener, J. R. Klein, C. Kyba, D. S. McDonald, M.S.Neubauer, F. M. Newcomer, V. Rusu, R. Van Berg, R. G. Van de Water, P. Wittich, University of Pennsylvania, Philadelphia, PA 19104, USA.; T. J. Bowles, S. J. Brice, M. Dragowsky, M. M. Fowler, A. Goldschmidt, A. Hamer, A. Hime, K. Kirch, J. B. Wilhelmy, J. M. Wouters, Los Alamos National Laboratory, Los Alamos, NM 87545, USA.; Y. D. Chan, X. Chen, M.C.P. Isaac, K. T. Lesko, A.D. Marino, E.B. Norman, C.E. Okada, A.W. P. Poon, A. R. Smith, A. Schuelke, R. G. Stokstad, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA.; Q. R. Ahmad, M. C. Browne, T.V. Bullard, P. J. Doe, C. A. Duba, S. R. Elliott, R. Fardon, J.V. Germani, A. A. Hamian, K. M. Heeger, R. Meijer Drees, J. Orrell, R. G. H. Robertson, K. Schaffer, M. W. E. Smith, T. D. Steiger, J. F. Wilkerson, University of Washington, Seattle, WA 98195, USA.; J. C. Barton, S.Biller, R. Black, R. Boardman, M. Bowler, J. Cameron, B. Cleveland, G. Doucas, Ferraris, H. Fergami, K.Frame, H. Heron, C. Howard, N. A. Jelley, A. B. Knox, M. Lay,W. Locke, J. Lyon, N. McCaulay, S. Majerus, G. MacGregor, M. Moorhead, M. Omori, N. W. Tanner, R. Taplin, M. Thorman, P. T. Trent, D. L.Wark, N. West, University of Oxford, Oxford OX1 3NP, United Kingdom.; J. Boger, R. L Hahn, J.K. Rowley, M. Yeh Brookhaven National Laboratory, Upton, NY 11973-5000, USA.; R.G. Allen, G. Buhler, H.H. Chen (Deceased), University of California, Irvine, CA 92717, USA.


text:
# REFERENCES

Comment on ”High Field Quasiparticle Tunneling in Bi2Sr2CaCu2O8+δ : Negative Magnetoresistance in the Superconducting State”

High magnetic field studies of the cuprate superconductors have revealed a non-Fermi liquid origin of the normal state resistivity , a negative normal state c-axis magnetoresistance , and a non-BCS shape of the upper critical field $`H_{c2}(T)`$ .

However, recently Morozov $`et`$ $`al`$ claimed  that Ref.  ’fell into the trap’ of attributing the negative c-axis magnetoresistance above the maximum of $`\rho _c(B)`$ to the normal state. These authors argued that magnetoresistance in Bi2Sr2CaCu2O8+δ is ’controlled by the quasiparticle tunnelling in the superconducting state’. In this Comment we challenge their arguments.

The authors of Ref. claim that while $`\rho _c`$ is a measure of the interplane tunnelling, only the in-plane data could represent a true normal state and be used in the determination of $`H_{c2}`$. Their main argument comes from the apparently different field dependences of $`\rho _c`$ and $`\rho _{ab}`$ as shown in their Fig.2. However, $`{}_{}{}^{}\rho _{ab}^{}(B)^{}`$ was measured by means of contacts situated on the same face of the crystal . Therefore this curve does not represent the in-plane resistivity because neither current redistribution (as considered in ) nor crystal imperfections were accounted for. We have applied the routine procedure for resistive $`H_{c2}`$ evaluation  from the in- and out-of-plane data obtained on the same samples in . The very similar values of $`H_{c2}(T)`$ obtained from $`\rho _{ab}`$ $`and`$ $`\rho _c`$ (solid and dashed lines in the Figure) are evident. This result contradicts the argument by Morozov $`et`$ $`al`$. As to Ref. of , different properties of the crystals used for $`\rho _c`$ and $`\rho _{ab}`$ measurements (i.e. 10-15K difference in $`T_{c0}`$ as seen from Fig.3,4 of that reference), makes corresponding comparison meaningless.

Another finding of Ref.  is a non-linear c-axis I(V), attributed by the authors to a suppression of the Josephson coupling. However, a comparative analysis of the data from their Fig.2 and the inset to Fig.1 favours the Joule heating origin of the effect giving a selfconsistent estimate of an excessive heating of about 2K near the maximum of the 35K-curve in Fig.3. Moreover, although the pulse system used by them delivers 10-20 times smaller rates, $`dB/dt`$, than conventional systems, the huge size, $`S`$, of the crystal  essentially overwhelmes this advantage since the eddy current heating is proportional to $`(dB/dt)^2S^2`$. Noticeable heating with eddy currents in the crystal with a 60 times smaller $`S`$ than in Ref.  was observed  below 30-40 K. That suggests significant heating effects in the low-temperature data of Ref. . Indeed, clear signatures of this heating are evident from the comparison of their data for 50K and 55K in Fig.1 and 2 . An independent test of the field dependence of the quasiparticle conductivity, shown in Fig.4 , suffers from the same problem. The scale of I(V) curves in the inset to Fig.4, allows us to estimate the Joule heating as $`30\mu W`$. Hence, heat in excess of 1000 W/cm2 was conducted through the active $`2\mu m^2`$ area of the mesa depicted in Fig.4. Accounting for the poor out-of-plane thermal conductivity of BSCCO-2212, this may entail significant heating of the active area of the structure thus rising the question of the physical meaning of the measured quantities.

Finally, a linear negative longitudinal magnetoresistance has been measured by us  both below and $`above`$ the $`zero`$ field critical temperature, $`T_{c0}`$. Therefore, in contrast to , we consider the effect to be an intrinsic $`normal`$ state property. Our view is also supported by a noticeable difference in the absolute value of the normalised magnetoresistance slope obtained on crystals with similar $`T_{c0}`$.

V.N. Zavaritsky, Kapitza Institute for Physical problems, Moscow, Russia.

M. Springford, H.H. Wills Physics Laboratory, University of Bristol, Bristol, United Kingdom.

A.S. Alexandrov, Department of Physics, Loughborough University, Loughborough, United Kingdom.


text:
# Issues and methods for CMB anisotropy data reduction

## 1  Introduction

The importance of measuring anisotropies of the Cosmic Microwave Background (CMB) to constrain cosmological models is now well established. It has been demonstrated that the properties of these anisotropies depend drastically on the seeds for structure formation as well as on cosmological parameters describing the matter content, the geometry, and the evolution of our Universe .

The complexity of CMB data taking into account imperfections in the observations, however, has led the CMB community into developing sophisticated data reduction methods. In this review paper, I discuss the principal issues about CMB data analysis, centering the discussion on map-making, as other aspects related to $`C_{\mathrm{}}`$ estimation and its interpretation are discussed by other authors in these proceedings.

## 2  Modelling the data for its reduction

Data reduction methods involve:

* writing down an accurate model of the problem (including prior knowledge);
* deciding optimisation criteria;
* finding the optimal solution given the model and the optimisation criteria;
* implementing the solution numerically.

The last two aspects have been discussed extensively in the litterature in the context of CMB anisotropy measurements . Less emphasis has been put on the first two aspects so far, although they are certainly as important as the last two.

modelling

For most CMB experiments, the problem is modelled as trying to measure CMB temperature fluctuations $`T_p`$ of the sky in a number of sky pixels, indexed here by $`p`$, having measurements in the form of a series of samples $`m_t`$ (in the context of map-making, for instance, samples can typically be indexed by time). The simplest way of expressing the measurements $`m_t`$ as a function of the unknown $`T_p`$ is:

$$m_t=A_{tp}T_p+n_t$$
(1)
here, $`T_p`$ and $`m_t`$ are one-dimensional vectors indexed by pixel numbers and by time. $`A_{tp}`$ is a pointing matrix telling how much of pixel $`p`$ is seen at time $`t`$. $`n_t`$ is the noise. Summation over repeated indices is assumed.

If we have several timelines corresponding to several detectors, the measurement can be modelled as one single data vector by appending all data streams one after the other. Similarly, when the sky emission, represented by temperature $`T_p=_cT_p^c`$ is a superposition of emissions due to various astrophysical processes, the system can be written in the form of equation 1 with $`p`$ indexing both pixel and component (instead of pixel only). If there are $`N_c`$ components (galactic dust, CMB, Sunyaev Zel’dovich emission,…), the linear system becomes simply $`N_c`$ times as large (with $`N_c`$ times more unkowns). Formulation 1 is thus quite general (up to the constraint that the model is linear).

It is often assumed that the pointing matrix is perfectly well known, that the noise is Gaussian (and stationnary) and that its autocorrelation $`N=nn^t`$ (the so-called noise covariance matrix) is known ($`n^t`$ is the transpose of vector $`\stackrel{}{n}`$).

Optimisation criteria

The “Optimisation” of the processing requires an optimisation criterium. For the construction of a pixellised map one wants typically to minimise the quadratic sum of the errors in all pixels:

$$\chi ^2=\underset{p}{}(\stackrel{~}{T}_pT_p)^2$$
(2)
where $`\stackrel{~}{T}_p`$ denotes the estimator of the true pixel temperature $`T_p`$. If the distributions for $`n`$ and $`T`$ are Gaussian and their autocorrelations $`N`$ and $`S`$ are known, minimising the $`\chi ^2`$ of equation 2 leads to the Wiener solution:

$$\stackrel{~}{T}=[S^1+A^tN^1A]^1A^tN^1m$$
(3)
Alternatively, assuming no prior knowledge on the sky signal, one may decide to minimize a standard $`\chi ^2`$ on the measurements:

$$\chi ^2=(mA\stackrel{~}{T})^tN^1(mA\stackrel{~}{T})$$
(4)
in which case the solution is the COBE method, i.e.:

$$\stackrel{~}{T}=[A^tN^1A]^1A^tN^1m$$
(5)
The Wiener method is the optimal linear method when all processes are Gaussian and when their spectra are known. Non-linear methods relying on Maximum Entropy, using Neural Networks, or linear methods using wavelets may perform better in a variety of cases .

Both the Wiener and the COBE methods rely on a particular prior knowledge about the signal and the noise: the knowledge of their autocovariance. The availability of such prior information is far from being obvious, as stressed by Ferreira and Jaffe , even if it does not need to be perfect.

The results of the data reduction depend to some extent on the reliability of this knowledge. If we assume that the noise is white (uncorrelated), for instance, the COBE method reduces to simple averaging of measurements in pixels:

$$\stackrel{~}{T}=[A^tA]^1A^tm$$
(6)
If the assumption is erroneous (i.e. the noise is not white), this map-making method is very far from being optimal .

More generally, the results of the data reduction depend on the accuracy of the model. In the future, methods taking into account explicitely the confidence one has in the model should be implemented. This is the object of current research. I believe it will help finding the best solution, as well as quantifying the errors, making results more robust.

Optimal solution

Once the problem is properly modelled, finding the optimal mathematical solution to data reduction is generally not the most difficult task for the applications we are interested in. The assesment of errors in the case of non gaussian processes, however, is not simple. So far, linear methods with the assumption of Gaussianity have performed satisfactorily.

Implementation

The numerical implementation of even the simplest data reduction scheme is quite a formidable problem in the context of present and future CMB missions, as emphasised by Bond et al. . Iterative methods to solve large systems can be employed in some cases , but implementing the optimal solution for a large and complex system as for the upcoming Planck mission is a hard task.

## 3  Main issues for data reduction and interpretation

We now review and discuss specific examples which constitute some of the major issues about CMB observation and data analysis:

1. astrophysical foregrounds
2. noise and slow drifts (the so-called 1/f noise)
3. imperfections of instrument properties and of their knowledge

Astrophysical components

CMB anisotropy experiments observe the sky at frequencies ranging from few GHz to few hundreds of GHz, at centimeter to millimeter wavelengths. The observed emission is not only due to CMB anisotropies, as other astrophysical processes also emit in this frequency range . The major known contributors are three galactic processes (thermal galactic dust emission, bremsstrahlung emission of free electrons – the so-called free-free emission, synchrotron emission) and extragalactic sources (IR and radio galaxies, and hot ionised gaz through the SZ effect, principally in clusters of galaxies). In data processing, one needs to separate the contribution of different sources. This aspect will be discussed in section 4.

Noise and slow drifts

The presence of slow drifts in the data streams is a well known problem to CMB anisotropy measurements. Long-term instabilities is a particularity of the sensitive detector technology used for CMB mapping. Such instabilities originate in a combination of detector 1/f noise, thermal instabilities, amplifier gain instabilities, fluctuations of atmospheric emission (especially for ground-based experiments). For radio detectors with HEMT amplifiers, the main source of slow drifts is 1/f noise. For bolometers, it is more often thermal fluctuations of the detector environment that causes trouble. For instance, a 3% emissive telescope mirror which temperature fluctuates by 0.1 K generates 3 mK fluctuations in detected signals, which is mainly in the form of random low-frequency drifts. Removing the effects of such slow drifts is known as “destriping”, and will be discussed in section 5.

Imperfections of a real instrument

Departures from ideality in the instruments must be taken into account. This is especially the case for sensitive experiments as Planck, for which it is targetted to measure the fluctuation power spectrum down to one per cent accuracies per single $`\mathrm{}`$ value.

One critical aspect for Planck is the problem of straylight, which is the unwanted radiation received by the instrument detectors. Straylight can be divided into two broad categories. The first one is straylight originating in the sidelobe pickup of astrophysical radiation outside the line of sight defined by the detectors main beams. This problem of “sidelobe straylight” is well known to telecommunication engineers as well as radio-astronomers. The second, more specific to CMB anisotropies (especially at high frequency) is that of straylight internal to the instrument, i.e. emission of parts of the instrument picked up by the detector. The emission due to fluctuations of the temperature of optical elements, discussed in section 4, is an example of this “internal straylight”. These two aspects of straylight are illustrated in figure 1.

The estimation of straylight effects for a mission as Planck will be discussed in section 6.

## 4  Separation of astrophysical components

The safest way to avoid contamination of CMB anisotropy observations by foregrounds is to make observations in the cleanest regions of the sky, where the contribution of the CMB to the sky emission dominates by a large amount, so that other components can be neglected. There are a few such regions in the sky, at high galactic latitudes, so this has been possible sofar for experiments with little sky coverage. Ultimately, it will become necessary to increase sky coverage even for small scale experiments, and try to remove foregrounds from the measurements, even if they do not impact much the ability of MAP and Planck to measure the CMB power spectrum . For astrophysicists anyway, foregrounds are interesting in themselves, as they carry information about the properties of interstellar medium or about the distribution of astrophysical sources of radiation (and hence of matter) in our Universe.

The separation of astrophysical components is possible essentially because the components have distinct emission spectra as a function of radiation wavelength. This is illustrated in figure 2. If the number of components and their respective spectra were perfectly well known, and if measurements were noiseless, then multifrequency observations (with at least as many observations as there are components) would allow in principle the recovery of the emission of each of the component at each point. Equation 1 still holds, but now $`t`$ indexes both time and detector number, and $`p`$ indexes both time and astrophysical component. The linear system can be large: the total number of measurements (i.e. the size of vector $`m_t`$) is $`N_{\mathrm{detectors}}\times N_{\mathrm{samples}}`$, and the size of vector $`T_p`$ (the unknown) is $`N_{\mathrm{processes}}\times N_{\mathrm{pixels}}`$. For Planck, the number of detectors is of the order of 100, the number of samples is of the order of a billion per timeline, the number of pixels of the sky is about one to 10 million, and the number of astrophysical processes is at least five or six (3 or 4 galactic components, CMB, and SZ - not mentioning complications arising for polarisation measurements).

This large system can not be handled by a brute force method. It can be simplified in some cases, if the noise is uncorrelated for instance. Assuming we dispose of clean maps of the sky at various frequencies, we can write:

$$m_\nu (\stackrel{}{x})=A_{\nu c}T_c(\stackrel{}{x})+n_\nu (\stackrel{}{x})$$
(7)
where now $`\nu `$ indexes frequencies of observation, and $`c`$ indexes astrophysical components. $`A_{\nu c}`$ is the mixing matrix, $`m_\nu (\stackrel{}{x})`$ the value of the map at frequency $`\nu `$ in direction $`(\stackrel{}{x})`$, and $`T_c(\stackrel{}{x})`$ the emission of component $`c`$. $`n_\nu `$ is the noise in measurement $`m_\nu `$.

Equation 7 can be inverted by any of the standard methods as the COBE or the Wiener one mentioned in section 1. This can be done in real space (pixel by pixel), or in Fourier space (mode by mode), or on other basis of functions (wavelet by wavelet…), depending on the shape and the coverage of the maps, the geometry of the observations, and the correlation properties of the noise and the components.

For details about linear methods, we refer the reader to the papers by Tegmark  and Bouchet and Gispert , and for nonlinear methods to papers by Hobson et al.  and Baccigalupi et al. . The Wiener method of Bouchet and Gispert has been extended recently to the separation of polarised components by Bouchet, Prunet and Sethi .

The trickiest part is getting the right model of the data : assuming the right number of components, knowing their spectra (matrix $`A_{\nu c}`$) and knowing the properties of the noise. This is especially true as recent measurements seem to indicate the presence of microwave dust emission from rotating grains in addition to the usual thermal emission, for instance, which complicate even more the determination of the spectrum of the (always sub-dominant, or nearly so) free-free emission. Variations of the number of relevant components and of their statistical and spectral properties as a function of the region of the sky observed complicate the separation of components on full-sky maps. Clearly, although some efforts have been made recently in this direction, the separation of components by a Wiener method on full sky maps is in contradiction with the known properties of foregrounds (localised, position-dependent).

Future methods, probably, will have to take explicitely into account the effect of uncertainties in the model, including in the error estimates the impact of unknown errors in matrix $`A`$.

## 5  Subtraction of slow drifts

Slow drifts are one of the lost fundamental problems we have to face for CMB anisotropy measurements. In most cases, this problem can be handled satisfactorily independently of the separation of astrophysical components. This decomposition of the problem of data reduction into subtasks with little loss in performance permits to handle very large data sets, as discussed by Bond and collaborators .

In the simplest model, slow drifts are simply due to $`1/f`$ noise. The total noise (including this low-frequency component) is stationnary, its spectrum is known, and the optimal reprojection of the data, taking into account the correlation of the noise, can be obtained in the COBE way, as discussed by Tegmark . If the spectrum is not known, then one can estimate it from the data as in the method of Ferreira and Jaffe . However, this last method relies on the assumption that the spectrum of the noise is somewhat smooth, as it is binned in ranges of frequencies. This is not necessarily the case (actually it is not the case in most of the examples I know) so the impact of this uncertainty in the model should be evaluated - and, if possible, taken into account for finding the best solution and errors.

Another method for slow drifts removal, which does not rely on prior knowledge of the noise spectrum, consists in modelling slow drifts as a function of a relatively small number of parameters $`A_i`$, to be fitted as unknowns of the model. Formally, we write:

$$m_t=A_{tp}T_p+f(A_i)+n_t$$
(8)
where $`f(A_i)`$ is a function slowly varying with time, parametred by coefficients $`A_i`$, modelling the effect of the slow drifts, and $`n_t`$ can now be assumed to be white. These coefficients, for instance, can be coefficient of the Fourier expansion of the timeline (or fractions of it) as in , or coefficients of splines used to fit the slow drifts. The system is then solved for $`T_p`$ and $`A_i`$ by minimising the $`\chi ^2`$:

$$\chi ^2=[m_tA_{tp}T_p+f(A_i)][m_tA_{tp}T_p+f(A_i)]^t$$
(9)
An adaptation of this method in the context of the measurement of CMB polarisation has been implemented on simulated data by Revenu and collaborators .

In this method which seems to “fit the noise out”, the fact that the noise is essentially low-frequency comes in to allow the low frequency drifts to be modelled as a function of a small number of parameters, so that the total number of unknown is significantly smaller than the number of measurements. From Shannon sampling theorem, this is possible, for instance, if the knee frequency above which slow drifts become negligible is significantly smaller than the sampling frequency of the data. The slow drifts, then, can be “sampled” at a rate significantly slower than the sampling of the timeline, allowing for the number of parameters to be much less than the number of data points.

The method, clearly, requires a lot of redundancy in the data, as discussed in . These redundancies should also be spread out along the timeline so that they allow sampling the slow drifts (using parameters $`A_i`$) at a sufficient rate.

## 6 The straylight problem

One of the most serious problem for most CMB anisotropy experiments, and especially for sensitive ones, is the problem of straylight. Minimising the total amount of unwanted radiation admitted into the detectors is a permanent instrumentalist’s nightmare. The correction of straylight effects in the data processing is a complicated problem, and is the object of active research. The first step is the estimation of the properties and levels of these effects for a mission such as Planck.

A model for the Planck antenna pattern has been computed at ESTEC by P. de Maagt and collaborators. Figure 3 displays a single cut of the $`4\pi `$ antenna pattern (in the plane of symmetry of the satellite).

In terms of integrated emission as seen from solar neighborhood, the strongest sources of radiation in the submillimeter sky, relevant for the problem of straylight, are the Sun, the planets and the Moon, the galactic plane emission, and the CMB dipole.

The properties of the sidelobe pickup depend on the scan strategy. For Planck, the satellite is rotated around a spin axis offset by 85 degrees from the optical axis, so that the main beam corresponding to a given detector scans the sky along great circles about 85 degrees in diameter. The orientation of the spin axis is re-adjusted every hour or so to follow the apparent motion of the Sun in the sky, keeping the spin-axis roughly anti-solar. For details on the Planck scanning, see .

Using the Planck 100 GHz antenna pattern of P. de Maagt and a model of the sky featuring galactic emission scaled from the DIRBE 240$`\mu `$m map and 408 MHz maps , we get estimated straylight signals due to the pickup of galactic emission in sidelobes for Planck. The result is displayed in figure 4. Although the total peak-to-peak straylight signal remains within reasonable limits (less than 2 $`\mu `$K), its large-scale properties could generate spurious non-gaussianity at low $`\mathrm{}`$, detectable by sensitive non-gaussianity tests. It is therefore a potential worry.

## 7 Conclusions

In this paper, I have reviewed the main issues and methods concerning the reduction of CMB data. I have emphasised on the importance of proper modelling for finding an optimal solution to this problem. The main issues for CMB data reduction are foregrounds (astrophysical or others), slow drifts of various origins in the timelines, and instrumental imperfections as the problem of straylight pickup in the detectors. Understanding the issues and the instrumental problems is important, as the optimisation of the reduction requires optimising the data model at least as much as optimising the numerical methods for solving the problem.

Standard linear methods for handling astrophysical foregrounds and slow drifts are now well established. These methods could still be improved by taking into account explicitely the uncertainty in the measurement model (lack of knowledge of the exact number of “sources” for component separation, imprecision in the knowledge of foreground spectra and statistical properties, imprecision in the knowledge of detector pointings).

Acknowledgements

Thanks to Jean-Christophe Hamilton and Alexandre Amblard for their critical reading of the original manuscript.