\documentclass[12pt]{article}
\usepackage{e-jc,amsfonts,amssymb,amsmath,amsthm,epsfig,euscript}

%\setlength{\textwidth}{6.3in}
%\setlength{\textheight}{8.7in}
%\setlength{\topmargin}{0pt}
%\setlength{\headsep}{0pt}
%\setlength{\headheight}{0pt}
%\setlength{\oddsidemargin}{0pt}
%\setlength{\evensidemargin}{0pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}

\def\mn{\makebox[1.1ex]{\rule[.58ex]{.71ex}{.15ex}}}

\long\def\symbolfootnote[#1]#2{\begingroup
\def\thefootnote{\fnsymbol{footnote}}\footnote[#1]{#2}\endgroup}

% newcommands to be used in math mode

%\newcommand{\coi}[1][\sigma]{\mathrm{coinv}(#1)}
\newcommand{\coib}[1][\sigma]{\mathrm{coinv}_B(#1)}
\newcommand{\com}[1][\sigma]{\mathrm{comaj}(#1)}
\newcommand{\comb}[1][\sigma]{\mathrm{comaj}_B(#1)}
%\DeclareMathOperator{\des}{\mathrm{des}}
%\DeclareMathOperator{\maj}{\mathrm{maj}}
\newcommand{\desb}[1][\sigma]{\mathrm{des}_B(#1)}
%\newcommand{\epq}[1][t(x-y)]{\mathbf{e}_{p,q}^{#1}}
\newcommand{\HF}{\xi}
\newcommand{\HK}{\xi_B}
%\newcommand{\inv}[1]{\mathrm{inv}(#1)}
%\newcommand{\inv}[1]{\mathrm{inv}(#1)}
\newcommand{\la}{\lambda}
\newcommand{\La}{\Lambda}
\newcommand{\ris}[1]{\mathrm{ris}(#1)}
\newcommand{\wris}[1]{\mathrm{wris}(#1)}
\newcommand{\sris}[1]{\mathrm{sris}(#1)}
\newcommand{\wmaj}[1][\gamma]{\mathrm{wmaj}(#1)}
\newcommand{\wdes}[1]{\mathrm{wdes}(#1)}
\newcommand{\sdes}[1]{\mathrm{sdes}(#1)}
\newcommand{\des}[1]{\mathrm{des}(#1)}
\newcommand{\levmaj}[1][\gamma]{\mathrm{levmaj}(#1)}
\newcommand{\lev}[1][\gamma]{\mathrm{lev}(#1)}
\DeclareMathOperator{\parts}{parts}
\newcommand{\majb}[1][\sigma]{\mathrm{maj}_B(#1)}
\newcommand{\mmaj}[1][\sigma^1,\dots,\sigma^m]{\mathrm{commaj}(#1)}
\newcommand{\mdes}[1][\sigma^1,\dots,\sigma^m]{\mathrm{comdes}(#1)}
\newcommand{\nega}[1][\sigma]{\mathrm{neg}(#1)}
\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}}
\newcommand{\ov}{\overline}
\newcommand{\pos}[1][\sigma]{\mathrm{pos}(#1)}
\newcommand{\qbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{q}}
\newcommand{\pqbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{p,q}}
\newcommand{\rbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{r}}
%\newcommand{\ris}[1][\sigma]{\mathrm{ris}(#1)}
%\newcommand{\risb}[1][\sigma]{\mathrm{ris}_B(#1)}
\newcommand{\sg}{\sigma}
\newcommand{\ep}{\epsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ta}{\Theta}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Pos}{\mathbb{P}}
\newcommand{\Ev}{\mathbb{E}}
\newcommand{\Odd}{\mathbb{O}}
\newcommand{\sP}{s\mathbb{P}}
\newcommand{\UD}{U\mbox{-}D}
\newcommand{\NDD}{ND\mbox{-}D}
\newcommand{\UNU}{U\mbox{-}NU}
\newcommand{\ud}{u\mbox{-}d}
\newcommand{\mmp}{\mbox{mp}}
\newcommand{\unu}{u\mbox{-}nu}
\def\dd{{\textrm d}}
%\def\qexp{{\mathbf{e}}_q}
%\def\pqexp{{\mathbf{e}}_{p,q}}
\newcommand{\sm}[2]{\sum_{#1 = #2}^{\infty}}

\newcommand{\al}{\alpha}
\newcommand{\cref}[1]{Corollary \ref{corollary:#1}}
\newcommand{\cmch}[1][\sg^1,\dots,\sg^m]{\text{$\tau$-$\mathrm{commch}$}(#1)}
\newcommand{\clap}[1][\sg^1,\dots,\sg^m]{\text{$\tau$-$\mathrm{comnlap}$}(#1)}
\newcommand{\cvlap}[1][w,y]{\text{$v$-$\mathrm{comnlap}$}(#1)}
%\newcommand{\des}[1]{\mathrm{des}(#1)}
%\newcommand{\ep}[1]{\exp \left( #1 \right)}
\newcommand{\qexp}[1]{\exp_{q} \left( #1 \right)}
\newcommand{\pqexp}[1]{\exp_{q,p} \left( #1 \right)}
\newcommand{\Epq}[1]{\mathrm{Exp}_{q} \left( #1 \right)}
\newcommand{\eref}[1]{\eqref{equation:#1}}
\newcommand{\FA}{f}
\newcommand{\FAq}{f_q}
\newcommand{\FAm}{f_m}
\newcommand{\FB}{g}
\newcommand{\FBb}{g_2}
%\newcommand{\fig}[1]{\vspace{1ex} \begin{center} \input{#1.pstex_t} \end{center%} \vspace{1ex}}
\newcommand{\Floor}[1][n/2]{\left \lfloor #1 \right \rfloor}
\newcommand{\HA}{\xi}
\newcommand{\HAq}{\xi_q}
\newcommand{\HAm}{\xi_m}
\newcommand{\HB}{\varphi}
\newcommand{\HC}{\eta}
\newcommand{\HCb}{\eta_2}
\newcommand{\HL}{\vartheta}
\newcommand{\im}{i}
\newcommand{\inv}[1]{\mathrm{inv}(#1)}
\newcommand{\coinv}[1]{\mathrm{coinv}(#1)}
\newcommand{\lref}[1]{Lemma \ref{lemma:#1}}
%\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}}
\newcommand{\qbin}[3]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{#3}}
\newcommand{\red}[1]{\mathrm{red}(#1)}
\newcommand{\pred}[1]{\mathrm{pred}(#1)}
%\newcommand{\sg}{\sigma}
%\newcommand{\sm}[2]{\sum_{#1 = #2}^{\infty}}
\newcommand{\sref}[1]{Section \ref{sub:#1}}
\newcommand{\tmch}[1]{\text{$\tau$-$\mathrm{mch}$}(#1)}
\newcommand{\Pmch}[1]{\text{$P$-$\mathrm{mch}$}(#1)}
\newcommand{\umch}[1]{\text{$\Upsilon$-$\mathrm{mch}$}(#1)}
\newcommand{\tumch}[1]{\text{$(\tau,u)$-$\mathrm{mch}$}(#1)}
\newcommand{\tEumch}[1]{\text{$(\tau,Eu)$-$\mathrm{mch}$}(#1)}
\newcommand{\ulap}[1]{\text{$u$-$\mathrm{nlap}$}(#1)}
\newcommand{\Eulap}[1]{\text{$Eu$-$\mathrm{nlap}$}(#1)}
\newcommand{\tlap}[1]{\text{$\tau$-$\mathrm{nlap}$}(#1)}
\newcommand{\Plap}[1]{\text{$P$-$\mathrm{nlap}$}(#1)}
\newcommand{\tEulap}[1]{\text{$(\tau,Eu)$-$\mathrm{nlap}$}(#1)}




\newcommand{\Umch}[1]{\text{$\Upsilon$-$\mathrm{mch}$}(#1)}
\newcommand{\Ulap}[1]{\text{$(\tau,\Upsilon)$-$\mathrm{nlap}$}(#1)}
\newcommand{\tUmch}[1]{\text{$(\tau,\Upsilon)$-$\mathrm{mch}$}(#1)}
\newcommand{\EUmch}[1]{E\text{$\Upsilon$-$\mathrm{mch}$}(#1)}
\newcommand{\EUlap}[1]{E\text{$(\tau,\Upsilon)$-$\mathrm{nlap}$}(#1)}
\newcommand{\EtUmch}[1]{E\text{$(\tau,\Upsilon)$-$\mathrm{mch}$}(#1)}


\newcommand{\tUlap}[1]{\text{$\Upsilon$-$\mathrm{nlap}$}(#1)}
\newcommand{\tref}[1]{Theorem \ref{theorem:#1}}
\newcommand{\vartmch}[2]{\text{${#1}$-mch}(#2)}
\newcommand{\vlap}[1]{\text{$v$-$\mathrm{nlap}$}(#1)}
\newcommand{\vmch}[1]{\text{$v$-$\mathrm{mch}$}(#1)}
\newcommand{\WE}{\upsilon}


% newcommands to be used in regular mode


\newcommand{\fig}[2]{\begin{figure}[ht]
\centerline{\scalebox{.66}{\epsfig{file=#1.eps}}}
\caption{#2}
\label{fig:#1}
\end{figure}}
%\newcommand{\eref}[1]{(\ref{equation:#1})}
%\newcommand{\sref}[1]{Section \ref{sub:#1}}
%\newcommand{\tref}[1]{Theorem \ref{theorem:#1}}
%\newcommand{\lref}[1]{Lemma \ref{lemma:#1}}
%\newcommand{\fref}[1]{Figure \ref{figure:#1}}


\title{Consecutive up-down patterns in up-down permutations}

\author{
Jeffrey B. Remmel \\
\small Department of Mathematics\\[-0.8ex]
\small University of California, San Diego\\[-0.8ex]
\small La Jolla, CA 92093-0112. USA\\[-0.8ex]
\small \texttt{jremmel@ucsd.edu}
\and
%ls
}

\date{\small Submitted: Date 1;  Accepted: Date 2;
 Published: Date 3.\\
\small MR Subject Classifications: 05A15, 05E05}

\begin{document}
\maketitle
 



\begin{abstract}
\noindent In this paper, we study the distribution of the number 
of consecutive pattern matches of an up-down permutation  
$\tau$ in the set of up-down permutations. In particular, 
we study the distribution of the number of 
consecutive pattern matches of the five up-down permutations of length four, 
$1324$, $1423$, $2314$, 
$2413$, and $3412$, in the set of up-down permutations. We show 
that in all five cases, the generating function for the distribution of the 
number of consecutive pattern matches of $\tau$ in the set 
of up-down permutations can be expressed in terms 
of what we call the generalized maximum packing polynomials of $\tau$. 
We then provide some systematic 
methods to compute the generalized maximum packing polynomials 
for such $\tau$.  



\end{abstract}


\section{Introduction}

If $\sg = \sg_1 \ldots \sg_n$ is a permutation in the symmetric 
group $S_n$, then we let 
$$Des(\sg) = \{i: \sg_i > \sg_{i+1}\} \  \mbox{and} \ Ris(\sg)  = \{i: \sg_i < \sg_{i+1}\}.$$ Let 
$\N  = \{0,1, \ldots, \}$ denote the natural numbers, $\Pos =\{1, 2, \ldots \}$ denote the set of positive integers,  
$\Ev= \{0,2,4, \ldots\}$ denote the set of even numbers in $\N$,  and 
$[n] = \{1,2, \ldots, n\}$ for $n \in \Pos$. We say that 
$\sg = \sg_1 \ldots \sg_n$ is an {\em up-down permutation} if either 
$n =1$ or $n > 1$ and 
$Des(\sg) = [n-1]\cap \Ev$.  That is, we have 
$$\sg_1 < \sg_2 > \sg_3 < \sg_4 \ldots .$$
We let $\mathcal{A}_n$ denote the set of up-down permutations in 
$S_n$.  


Given a sequence $\sg = \sg_1 \ldots \sg_n$ of distinct integers,
let $\red{\sg}$ be the permutation found by replacing the
$i$th smallest integer that appears in $\sg$ by $i$.  For
example, if $\sg = 2754$, then $\red{\sg} = 1432$.  Given a
permutation $\tau=\tau_1 \ldots \tau_j\in S_j$ and a permutation 
$\sg = \sg_1 \ldots \sg_n \in S_n$, we say that $\tau$ {\em occurs} in 
$\sg$ if there are $1 \leq i_1 < \ldots < i_j \leq n$ such 
that $\red{\sg_{i_1} \ldots \sg_{i_j}} = \tau$ and 
we say that $\sg$ has a {\em $\tau$-match starting at position $i$} in $\sg$ 
if $\red{\sg_i \sg_{i+1} \ldots \sg_{i+j-1}} = \tau$.  We say 
that $\sg$ {\em avoids} $\tau$ if there are no occurrences of $\tau$ in $\sg$.
 We let $\tmch{\sg}$ denote the number of $\tau$-matches in $\sg$. 
We let $A_{n,\tau}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tmch{\sg}}$. 

These definitions are easily extended to sets of permutations 
$\Upsilon \subseteq S_j$. That is, we say that $\Upsilon$ occurs in 
$\sg$ if there are $1 \leq i_1 < \ldots < i_j \leq n$ such 
that $\red{\sg_{i_1} \ldots \sg_{i_j}} \in \Upsilon$ and 
we say that $\sg$ has a $\Upsilon$-match starting at position $i$ in $\sg$ 
if $\red{\sg_i \sg_{i+1} \ldots \sg_{i+j-1}} \in \Upsilon$.  We say 
that $\sg$ avoids $\Upsilon$ if there are no occurrences of $\Upsilon$ in 
$\sg$. We let $\umch{\sg}$ denote the number of $\Upsilon$-matches in $\sg$. 
We let $\mathcal{A}_{n,\Upsilon}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\umch{\sg}}$. 


There have been several papers that have studied the number of up-down  
permutations $\sg \in \mathcal{A}_n$ which avoid a given pattern. For example, 
Mansour \cite{mansour} and Deutsch and Reifegerste, see \cite{StCat}, Problem $h^7$ or \cite{hong}, showed that for any $\tau \in S_3$, 
the number of up-down permutations $\sg \in \mathcal{A}_{n}$ which avoid $\tau$ is always a Catalan number. For example,  the number of up-down 
permutations $\sg \in \mathcal{A}_n$ that avoid $132$ ($231$) is 
$C_{\lfloor n/2 \rfloor}$. In 
\cite{lewis}, it was shown that 
the number of $\sg \in \mathcal{A}_{2n}$ which avoids 1234 or 2143 is 
$\frac{2(3n)!}{n!(n+1)!(n+2)!}$.  There has been 
somewhat less work on the distribution of $\tau$-matches 
in up-down permutations. Carlitz \cite{carlitz1} found the generating 
function for the number of rises in the peaks of the up-down permutations 
where a rise in the peaks of an up-down permutation  
is just 213-match in $\sg$.  


The main goal of this paper is to study the generating functions 
\begin{equation}\label{gfA}
A_{\tau}(t,x) =  1+ \sum_{n \geq 1} \frac{t^{2n}}{(2n)!} 
\sum_{\sg \in \mathcal{A}_{2n}} x^{\tmch{\sg}}
\end{equation}
and 
\begin{equation}\label{gfB}
B_{\tau}(t,x) = \sum_{n \geq 1} \frac{t^{2n-1}}{(2n-1)!} 
\sum_{\sg \in \mathcal{A}_{2n-1}}x^{\tmch{\sg}}
\end{equation}
in the case where $\tau \in \mathcal{A}_4$.  Note that there are 
5 permutations in $\mathcal{A}_4$, namely,
\begin{equation*}
\tau^{(1)} =  1324, \tau^{(2)} = 2314, \tau^{(3)} = 2413, \tau^{(4)} =  1423,  \ \mbox{and} \ \tau^{(5)} = 3412.
\end{equation*}
If $\sg \in \mathcal{A}_n$, then $\tau^{(i)}$-matches can only start 
at odd positions. If $\sg \in \mathcal{A}_{2n}$ and $\tau^{(i)}\mbox{-mch}(\sg) = n-1$, 
then we say that $\sg$ is a {\em maximum packing for 
$\tau^{(i)}$}. Thus if $\sg \in \mathcal{A}_{2n}$ is a maximum packing 
for $\tau^{(i)}$, then $\sg$ has $\tau^{(i)}$-matches starting 
at positions $1,3,\ldots,2n-3$. We let $\mathcal{MP}_{2n,\tau^{(i)}}$ denote 
the set of maximum packings for $\tau^{(i)}$ in $\mathcal{A}_{2n}$ and we let 
$\mmp_{2n,\tau^{(i)}} = |\mathcal{MP}_{2n,\tau^{(i)}}|$.  We shall see that it  follows from 
results of Harmse and Remmel \cite{HR} that 
\begin{eqnarray*}
\mmp_{2n,\tau^{(1)}} &=& \mmp_{2n,\tau^{(3)}} =C_{n-1}  \ \mbox{and} \\
\mmp_{2n,\tau^{(2)}} &=&  \mmp_{2n,\tau^{(4)}} = \mmp_{2n\tau^{(5)}} = 1,
\end{eqnarray*}
where $C_n = \frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number. 




Our main theorem will show that for each $i \in [5]$, 
the  generating functions $A_{\tau^{(i)}}(t,x)$ and $B_{\tau^{(i)}}(t,x)$ 
can be expressed in terms of what we call generalized maximum packings for 
$\tau^{(i)}$. That is, we say that $\sg \in S_{2n}$ is a 
{\em generalized maximum packing 
for $\tau^{(i)}$} if we can break $\sg$ into consecutive blocks  
$\sg = B_1 \ldots B_k$ such that 
\begin{enumerate}
\item for all $1 \leq j \leq k$, 
$B_j$ is either an increasing sequence of length 2 or $\red{B_j}$ is 
maximum packing for $\tau^{(i)}$ of length $2s$ for some $s \geq 2$ and 
\item for all $1 \leq j \leq k-1$, the last element of 
$B_j$ is less than the first element of $B_{j+1}$. 
\end{enumerate}
Note that if $\sg$ is a generalized maximum packing for $\tau^{(i)}$, there 
is only one possible block structure.  That is, if $\sg = \sg_1 \ldots \sg_{2n} \in S_{2n}$ is a generalized maximum packing for $\tau^{(i)}$, our 
definitions force that $\sg_{2j-1} < \sg_{2j}$ for $i =1, \ldots, 
n$.  Then it is easy to see that $\sg_{2j-1}\sg_{2j}$ and 
$\sg_{2j+1}\sg_{2j+2}$ are in the same block if and only 
if $\sg_{2j}> \sg_{2j+1}$. 

If $\sg$ is a generalized 
maximum packing for $\tau^{(i)}$ of length $2n$ 
with block structure $B_1 \ldots B_k$, 
then we define the weight $w(B_j)$ of block $B_j$   to be 1 if 
$B_j$ has length 2 and to be $(x-1)^s$ if $B_j$ has length $2s+2$ where 
$s \geq 1$. Then we define the weight $w(\sg)$ of $\sg$    to 
be $(-1)^{k-1}\prod_{j=1}^k w(B_j)$. For example, 
$$\sg = 1~2~3~5~4~7~6~9~8~10~11~12~13~14~15~17~16~18$$
is a generalized maximum packing for $\tau^{(1)} = 1324$ where 
$B_1 =1~2$, $B_2= 3~5~4~7~6~9~8~10$, $B_3 =11~12$, $B_4 = 13~14$ and 
$B_5 = 15~17~16~18$.  Thus $w(B_1) = w(B_3) =w(B_4) =1$, 
$w(B_2) =(x-1)^3$ and $w(B_5) =(x-1)$ so that $w(\sg) = 
(-1)^4 (x-1)^4 = (x-1)^4$. Thus the weight of $\sg$ is just 
$(-1)^{k-1}(x-1)^{\tau^{(i)}\mbox{-mch}(\sg)}$ where $k$ is 
the number of blocks of $\sg$. 
We let $\mathcal{GMP}_{2n,\tau^{(i)}}$ denote 
the set of $\sg \in S_{2n}$  which are generalized maximum packings 
for $\tau^{(i)}$ and we let 
\begin{equation}
GMP_{2n,\tau^{(i)}}(x) = \sum_{\sg \in \mathcal{GMP}_{2n,\tau^{(i)}}} w(\sg).
\end{equation}


We say that $\sg \in S_{2n+1}$ is a {\em generalized maximum packing 
for $\tau^{(i)}$} if we can break $\sg$ into consecutive blocks 
$\sg = B_1 \ldots B_k$ such that 
\begin{enumerate}
\item for all $1 \leq j < k$, 
$B_j$ is either an increasing sequence of length 2 or $\red{B_j}$ is 
maximum packing of $\tau^{(i)}$ of length $2s$ for some $s \geq 2$,
\item $B_k$ is a block of length $1$, 
and 
\item for all $1 \leq j \leq k-1$, the last element of 
$B_j$ is less than the first element of $B_{j+1}$. 
\end{enumerate}
If $\sg$ is a generalized 
maximum packing for $\tau^{(i)}$ of length $2n+1$ 
with block structure $B_1 \ldots B_k$, 
then we define the weight $w(B_j)$ of block $B_j$   to be 1 if 
$B_i$ has length 1 or 2 and to be $(x-1)^s$ if $B_j$ has length $2s+2$ where 
$s \geq 1$. Then we define the weight $w(\sg)$ of $\sg$    to 
be $(-1)^{k-1}\prod_{i=1}^k w(B_i)= 
(-1)^{k-1}(x-1)^{\tau^{(i)}\mbox{-mch}(\sg)}$. For example, 
$$\sg = 1~2~3~5~4~7~6~9~8~10~11~12~13~14~15~17~16~18~19$$
is a generalized maximum packing for $\tau^{(1)} = 1324$ where 
$B_1 =1~2$, $B_2= 3~5~4~7~6~9~8~10$, $B_3 =11~12$, $B_4 = 13~14$ and 
$B_5 = 15~17~16~18$, and $B_6 =19$.  Thus $w(B_1) = w(B_3) =w(B_4) =w(B_6)=1$, 
$w(B_2) =(x-1)^3$ and $w(B_5) =(x-1)$ so that $w(\sg) = 
(-1)^5 (x-1)^4 = -(x-1)^4$. 
We let $\mathcal{GMP}_{2n+1,\tau^{(i)}}$ denote 
the set of $\sg \in S_{2n+1}$  which are generalized maximum packings 
for $\tau^{(i)}$. We then let 
\begin{equation}
GMP_{2n+1,\tau^{(i)}}(x) = 
\sum_{\sg \in \mathcal{GMP}_{2n+1,\tau^{(i)}}} w(\sg).
\end{equation}
We shall call $GMP_{n,\tau^{(i)}}(x)$ the generalized 
maximum packing polynomial 
for $\tau^{(i)}$ of length $n$. 

In general, it is much more difficult to compute 
$GMP_{2n,\tau^{(i)}}(x)$ and $GMP_{2n+1,\tau^{(i)}}(x)$ than to 
compute $\mmp_{2n,\tau^{(i)}}$ and $\mmp_{2n+1,\tau^{(i)}}$.  
Indeed, we do not have a closed expression for either 
$GMP_{2n,\tau^{(i)}}(x)$ or $GMP_{2n+1,\tau^{(i)}}(x)$
as a  function of $n$ for 
any $i$.  However, we will show that for $i \in \{1,2,4\}$, 
$GMP_{n,\tau^{(i)}}(x)$ can be computed via simple recursions.  
For example, we shall 
show that $GMP_{2,\tau^{(1)}}(x) =1$, $GMP_{4,\tau^{(1)}}(x) =x-2$, and, 
for $2n > 4$,
\begin{multline}\label{t1rec}
GMP_{2n,\tau^{(1)}}(x) = \\
C_{n-1}(x-1)^{n-1} -GMP_{2n-2,\tau^{(1)}}(x) - 
\sum_{k=2}^{n-1} C_{k-1}(x-1)^{k-1} GMP_{2n-2k,\tau^{(1)}}(x).
\end{multline}
Moreover, we shall show that  $GMP_{1,\tau^{(1)}}(x) =1$ and 
$GMP_{2n+1,\tau^{(1)}}(x) = - GMP_{2n,\tau^{(1)}}(x)$ for $n \geq 1$. 


Our main theorem is the following. 
\begin{theorem}\label{thm:main}
For $i=1, \ldots, 5$, 
\begin{equation}\label{eqA}
A_{\tau^{(i)}}(t,x) = \frac{1}{1-\sum_{n\geq 1} GMP_{2n,\tau^{(i)}}(x) 
\frac{t^{2n}}{(2n)!}} \ \mbox{and}
\end{equation}
\begin{equation}\label{eqB}
B_{\tau^{(i)}}(t,x) =\frac{\sum_{n \geq 1} GMP_{2n-1,\tau^{(i)}}(x)
\frac{t^{2n-1}}{(2n-1)!}}{1-\sum_{n\geq 1} GMP_{2n,\tau^{(i)}}(x) 
\frac{t^{2n}}{(2n)!}}.
\end{equation}
\end{theorem}


We shall prove Theorem \ref{thm:main} by applying the so-called 
homomorphism method which has been developed in a series of papers 
\cite{BeckRem,b,b2,HR,KNRR,MendesTh,MenRem1,Book,RRW,Wag}. 
In particular, 
we shall show that the generating functions in Theorem \ref{thm:main} 
arise by 
applying certain ring homomorphisms defined on the ring  
of symmetric functions $\Lambda$ in infinitely many variables  
to simple symmetric function identities.  For example, 
let $h_n$ denote $n$th homogeneous symmetric function in $\Lambda$ 
and $e_n$ denote the $n$th elementary symmetric function in 
$\Lambda$. That is, $h_n$ and $e_n$ are defined by 
the generating functions  
\begin{equation*}
H(t) = \sum_{n \geq 0} h_n t^n = \prod_i \frac{1}{1-x_it} \ \mbox{and} \ 
E(t) = \sum_{n \geq 0} e_n t^n = \prod_i (1+x_it). 
\end{equation*}
Then we shall show  that (\ref{eqA}) arises by applying 
a ring homomorphism $\Theta$ to the simple symmetric 
function identity that 
\begin{equation}
H(t) = \frac{1}{E(-t)}.
\end{equation}
The basic idea of the homomorphism method  is 
to show that 
\begin{equation}\label{key} 
(2n)!\theta(h_{2n}) = A_{2n,\tau^{(i)}}(x) = 
\sum_{\sg \in \mathcal{A}_{2n}} x^{\tau^{(i)}\mbox{-mch}(\sg)}
\end{equation}
for an appropriately chosen ring homomorphism $\theta$. Typically,
one proves equations like 
(\ref{key}) by interpreting the left-hand side of (\ref{key}) in 
terms of a signed weighted sum of filled brick tabloids and then applying 
an appropriate sign-reversing weight-preserving involution to 
show that the combinatorial interpretation of $(2n)!\theta(h_{2n})$ 
reduces to the desired polynomial.  The situation 
in this paper is a bit different from previous examples of the homomorphism 
method in that it requires two involutions 
to show that our  combinatorial interpretation of $(2n)!\theta(h_{2n})$ 
reduces to the right-hand of (\ref{key}). Equation (\ref{eqB}) is 
proved in a similar manner except that we apply $\theta$ to a more 
complicated symmetric function identity. 




The outline of the paper is as follows. In section 2, we shall provide 
the necessary background in symmetric functions that is necessary for 
our proofs. In section 3, we shall prove Theorem \ref{thm:main}.
In section 4, we shall show how to compute $\mmp_{n,\tau^{(i)}}$ for 
$i =1,2,3,4,5$. In section 5, we shall develop 
recursions for $GMP_{n,\tau^{(i)}}(x)$ for $i=1,2,4$. The simplest 
case is set of the recursions for $GMP_{n,\tau^{(1)}}(x)$ described above. 
In that case, we shall 
show that $GMP_{2n,\tau^{(1)}}(0) = (-1)^{n-1}C_n$ for $n \geq 1$ 
and $GMP_{2n,\tau^{(1)}}(x)|_x = (-1)^n \binom{2n}{n-2}$. Using 
these facts, we can compute the generating functions 
for the number of up-down permutations with no $\tau^{(1)}$-matches 
or with exactly one $\tau^{(1)}$-match. For example, we 
shall show that
$$1 + \sum_{n \geq 1} \frac{t^{2n}}{(2n)!} N_{2n,\tau^{(1)}} = 
\frac{1}{1+ \sum_{n\geq 1} (-1)^n C_n \frac{t^{2n}}{(2n)!}}$$
where $N_{2n,\tau^{(1)}}$ is the number of 
$\sg \in \mathcal{A}_{2n}$ with no $\tau^{(1)}$-matches. 
Finally, in section 6, we shall study the distribution of 
double rise pairs and double descent pairs in up-down permutations. 
That is, 
if $\sg = \sg_1 \ldots \sg_n \in \mathcal{A}_n$ is an up-down 
permutation, then  we say that a pair $(2i-1)(2i)$ is a {\em double 
rise pair} if both $\sg_{2i-1} < \sg_{2i+1}$ and $\sg_{2i} < \sg_{2i+2}$. 
Thus $(2i-1)(2i)$ is a double rise pair in $\sg$ if and only if 
there is a $1324$ match starting at position $2i-1$ in $\sg$. 
We say that a pair $(2i-1)(2i)$ is a {\em double 
descent pair} if both $\sg_{2i-1} > \sg_{2i+1}$ and $\sg_{2i} > \sg_{2i+2}$. 
Thus $(2i-1)(2i)$ is a double descent pair in $\sg$ if and only if 
there is a $D$-match starting at position $2i-1$ in $\sg$ where $D=\{2413,3412\}$.


\section{Symmetric Functions}


In this section we give the necessary background on symmetric
functions needed for our proofs of the generating functions (\ref{eqA}) 
and (\ref{eqB}).

Let $\Lambda$ denote the ring of symmetric functions
over infinitely many variables $x_1, x_2, \ldots $ with coefficients in
the field of complex numbers $\mathbb{C}$.

Let $\la = (\la_1,\dots,\la_\ell)$ be an integer partition, that is,
$\la$ is a finite sequence of weakly increasing nonnegative
integers.  Let $\ell(\la)$ denote the number of nonzero integers in
$\la$. If the sum of these integers is $n$, we say that $\la$ is a
partition of $n$ and write $\la \vdash n$.  For any partition $\la =
(\la_1,\dots,\la_\ell)$, let $e_\la = e_{\la_1} \cdots
e_{\la_\ell}$ and $h_\la = h_{\la_1} \cdots
h_{\la_\ell}$. The well-known fundamental theorem of symmetric
functions says that $\{e_\la : \text{$\la$ is a partition}\}$ is a
basis for $\La$ or, equivalently, that 
$\{e_0,e_1,\ldots \}$ is an algebraically
independent set of generators for $\Lambda$.
  Since $\{e_0,e_1, \ldots \}$ is an 
algebraically independent
set of generators for $\Lambda$, we can specify a ring homomorphism
$\theta$ on $\Lambda$ by simply defining $\theta(e_n)$ for all
$n \geq 0$.


A {\em
brick tabloid} of shape $(n)$ and type $\la =(\la_1,\ldots, \la_k)$ is a
filling of a row of $n$ squares of cells with bricks of lengths
$\la_1, \ldots, \la_k$ such that bricks do not overlap.
For example, if $\lambda =(1^2,2^2)$, the six $\lambda$-brick 
tabloids of shape $(6)$ are pictured in Figure 
\ref{fig:brickt}.



\fig{brickt}{The six brick tabloids of type $(1^2,2^2)$ and shape $(6)$.}

Let $\mathcal{B}_{\la,n}$ denote the set of all $\la$-brick tabloids of shape $(n)$ and let
$B_{\la,n} =|\mathcal{B}_{\la,n}|$.  We shall write 
$B=(b_1, \ldots, b_k)$ if $B$ is brick tabloid of shape 
$n$ such that lengths of the bricks in $B$ are $b_1, \ldots, 
b_k$ as we read from left to right. 
E\u{g}ecio\u{g}lu and Remmel proved in
\cite{ER} that
\begin{equation}\label{omar}
h_n = \sum_{\la \vdash n} (-1)^{n - \ell(\la)} B_{\la,n} e_\la 
= \sum_{\la \vdash n} (-1)^{n - \ell(\la)} 
\sum_{(b_1, \ldots, b_{\ell(\mu)}) \in \mathcal{B}_{\la,n}} 
\prod_{i=1}^{\ell(\mu)} e_{b_i}
\end{equation}

Next we define a class of symmetric functions $p_{n,\nu}$ which have a relationship with $e_\lambda$ that is analogous to the relationship between $h_n$ and $e_\lambda$. These functions were first introduced in \cite{LR} and 
\cite{MendesTh}. Let $\nu$ be a function which maps the set of nonnegative integers into a field $F$. Recursively define $p_{n,\nu} \in \La_n$ by setting $p_{0,\nu} = 1$ and 
\begin{equation}\label{pnnurec}
p_{n,\nu} = (-1)^{n-1} \nu(n) e_n + \sum_{k=1}^{n-1}(-1)^{k-1}e_k p_{n-k,\nu}
\ \mbox{for all $n \geq 1$.}
\end{equation}
 By multiplying series, this means that
\begin{equation*}
\left(\sum_{n \geq 0}(-1)^n e_n t^n \right) \left(\sum_{n \geq 1}
p_{n,\nu} t^n \right)
= \sum_{n \geq 1} \left ( \sum_{k=0}^{n-1} p_{n-k,\nu} (-1)^k e_k
\right ) t^n
= \sum_{n \geq 1} (-1)^{n-1} \nu(n) e_n t^n,
\end{equation*}
where the last equality follows from the definition of $p_{n,\nu}$.
Therefore,
\begin{equation}\label{fund}
\sum_{n \geq 1} p_{n,\nu}t^n
= \frac{\sum_{n \geq 1} (-1)^{n-1} \nu(n) e_n t^n}
{\sum_{n \geq 0} (-1)^n e_n t^n}
\end{equation}
or, equivalently,
\begin{equation}
\label{fund2}
1+ \sum_{n \geq 1} p_{n,\nu}t^n
= \frac{1+ \sum_{n \geq 1} (-1)^{n}(e_n - \nu(n) e_n) t^n}
{\sum_{n \geq 0} (-1)^n e_n t^n}.
\end{equation}
When taking $\nu(n) = 1$ for all $n \geq 1$, \eqref{fund2} becomes
\begin{equation*}
1 + \sum_{n \geq 1} p_{n,1} t^n
= 1 + \frac{\sum_{n \geq 1} (-1)^{n-1} e_n t^n}
{\sum_{n \geq 0} (-1)^n e_n t^n}
= \frac{1}{\sum_{n \geq 0} (-1)^n e_n t^n}
= 1 + \sum_{n \geq 1} h_n t^n
\end{equation*}
which implies that $p_{n,1} = h_n$ for all $n$.  Other special cases for $\nu$ give well-known generating functions. For example, if $\nu(n) = n$ for $n \geq 1$, then $p_{n,\nu}$ is the power symmetric function $\sum_{i} x_i^n$. By taking $\nu(n) = (-1)^k \chi(n \geq k+1)$ for some $k \geq 1$, $p_{n,(-1)^k\chi(n \geq k+1)}$ is the Schur function corresponding to the partition $(1^k,n)$.

This definition of $p_{n,\nu}$ is desirable because of its expansion in terms
of elementary symmetric functions. The coefficient of $e_\la$ in $p_{n,\nu}$
has a nice combinatorial interpretation similar to that of $h_n$. Suppose $T$ is a brick tabloid of shape $(n)$ and type
$\la$ and that the final brick in $T$ has length $\ell$. Define the weight
of a brick tabloid $w_{\nu}(T)$ to be $\nu(\ell)$ and let
\begin{equation*}
w_{\nu}(B_{\la,n}) = \sum_{T \in \mathcal{B}_{\la,n}} w_{\nu}(T).
\end{equation*}
It was proved in \cite{LR} and 
\cite{MendesTh} that 
\begin{equation}\label{pnuexp}
p_{n,\nu} = \sum_{\la \vdash n}(-1)^{n-\ell(\la)} w_{\nu}(B_{\lambda,n}) e_\la 
= \sum_{\la \vdash n} (-1)^{n - \ell(\la)} 
\sum_{(b_1, \ldots, b_{\ell(\mu)}) \in \mathcal{B}_{\la,n}} \nu(b_{\ell(\mu)})
\prod_{i=1}^{\ell(\mu)} e_{b_i}.\end{equation}







\section{The proof of Theorem \ref{thm:main}.}


In this section, we shall prove Theorem \ref{thm:main}.

We start out by proving (\ref{eqA}). Define a ring homomorphism $\theta$ from $\Lambda$ into 
$\mathbb{Q}(x)$ by setting $\theta(e_0) =1$, $\theta(e_{2n+1}) = 0$ 
for all $n \geq 0$, and 
\begin{equation}\label{theta}
\theta(e_{2n}) = \frac{(-1)^{n-1}}{n!} GMP_{2n,\tau^{(i)}}(x) \ 
\mbox{for all $n \geq 1$.}
\end{equation}
Then we claim that $\theta(h_{2n-1}) =0$ and 
\begin{equation}\label{Ah0}
(2n)!\theta(h_{2n}) = \sum_{\sg \in \mathcal{A}_{2n}} x^{\tau^{(i)}\mbox{-mch}(\sg)} 
\end{equation}
for all $n \geq 1$. 
Note that by (\ref{omar}), 
$$\theta(h_{2n-1}) = \sum_{\mu \vdash 2n-1} 
(-1)^{2n-1 - \ell(\mu)} B_{\mu,2n-1} \theta(e_{\mu}).
$$
Clearly if $\mu$ is partition of $2n-1$, then $\mu$ must 
have an odd part so that $\theta(e_\mu)=0$. Thus 
$\theta(h_{2n-1}) =0$ for all $n \geq 1$. Note also that 
\begin{equation}\label{Ah1}
\theta(h_{2n}) = 
\sum_{\mu \vdash 2n} 
(-1)^{2n - \ell(\mu)} \sum_{(b_1, \ldots, b_{\ell(\mu)}) \in 
\mathcal{B}_{\mu,2n}} \prod_{i=1}^{\ell(\mu)} \theta(e_{b_i})
\end{equation}
so that there is no loss if we restrict the sum on 
the right-hand side of (\ref{Ah1}) to partitions 
$\mu$ where every part of $\mu$ is even, i.e., 
to partitions of the form $2\la$ where $\la$ is a partition 
of $n$ and $2\la = (2\la_1, \ldots, 2\la_{\ell(\la)})$ if 
$\la = (\la_1, \ldots, \la_{\ell(\la)})$. 
Thus 
\begin{align} \label{Ah2}
(2n)!\theta(h_{2n}) 
&= (2n)! \sum_{\la \vdash n} (-1)^{2n-\ell(\la)} 
\sum_{(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,n}} 
\prod_{j=1}^{\ell(\mu)} \theta(e_{2b_j}) \nonumber \\
&= (2n)! \sum_{\la \vdash n} (-1)^{2n-\ell(\la)} 
\sum_{(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,n}} 
\prod_{j=1}^{\ell(\mu)}  
\frac{(-1)^{2b_j -1}}{(2b_j)!} 
GMP_{2b_j,\tau^{(i)}}(x) \nonumber \\
&= \sum_{\la \vdash n} 
\sum_{T =(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,2n}} 
\binom{2n}{2b_1,\ldots,2b_{\ell(\la)}} 
\prod_{j =1}^{\ell(\la)} GMP_{2b_j,\tau^{(i)}}(x).
\end{align}

Next we want to give a combinatorial interpretation to 
the right-hand side of (\ref{Ah2}). We start with a brick tabloid 
$T= (2b_1, \ldots, 2b_{\ell(\la)})$ of type $2\la$.  Then 
the binomial coefficient $\binom{2n}{2b_1,\ldots,2b_{\ell(\la)}}$ 
allows us to pick a set partition $\vec{U} = (U_1, \ldots, U_{\ell(\la)})$ of 
$\{1, \ldots, 2n\}$ where $|U_i| =2b_i$ for $i =1, \ldots, \ell(\la)$.  
Next we use the factor 
$\prod_{j =1}^{\ell(\la)} GMP_{2b_j,\tau^{(i)}}(x)$ to 
choose a sequence of permutations $\vec{\sg} = (\sg^{(1)}, \ldots, \sg^{(\ell(\la))})$ 
such that $\sg^{(j)} \in \mathcal{A}_{2\la_j}$ is a generalized maximum packing for 
$\tau^{(i)}$ for $j =1, \ldots, \ell(\la)$. 
Then for each $j$, we let $\alpha^{(j)}$ be the sequence 
that arises by replacing the $r$th largest element of 
$\sg^{(j)}$ by the $r$th largest element of $U_j$ and then 
placing these elements in the cells of brick $2b_j$ from 
left to right. 
For example, we have pictured this process  
for $\tau^{(1)} = 1324$ where the underlying brick tableau is  
$T=(2,8,6)$. We have also indicated the block structure 
in each brick by underlying those elements in a common block. 
The weight of such a triple $(T,\vec{U},\vec{\sg})$,   $w(T,\vec{U},\vec{\sg})$, is 
$\prod_{j=1}^{\ell(\la)} w(\sg^{(j)})$.  We can interpret 
 $w(T,\vec{U},\vec{\sg})$ by placing a weight $1$ on top of each 
block of length $2$ that ends  a brick and a weight of $-1$ on 
each block of length 2 which does not end a brick.  For blocks 
of length $\geq 4$, we place a weight of $(x-1)$ at start of 
each $\tau^{(i)}$-match in the block. Finally,  
we replace the weight of the first $\tau^{(i)}$-match in a block 
by $-(x-1)$ if the block is not the last block in its brick. 
Thus the RHS of (\ref{Ah2}) can be interpreted as the sum of the 
weights of all 
triples $(T,\alpha,L)$ such that  
\begin{enumerate}
\item $T= (d_1, \ldots, d_k)$ is brick tabloid of shape $(2n)$ where 
each brick $d_j$ has even length, 
\item $\alpha$ is a permutation of $S_{2n}$ such that 
in each brick $d_j$, the sequence of elements in brick $d_j$ reduces 
to a permutation in $\mathcal{GMP}_{d_j,\tau^{(i)}}$,  and 
\item $L:\{1,\ldots, 2n\} \rightarrow \mathbb{Q}[x]$ assigns 
a label to each cell in $T$ where $L(j)$ denotes the label  of 
$j$th cell of $T$, reading from left to right, and 
\begin{description}
\item[(a)] $L(j) =1$ if $j$ is the second cell of a block of 
length 2 or $j$ does not start a $\tau^{(i)}$-match in a block 
of length $\geq 4$, 
\item[(b)] $L(j) =1$ if $j$ is the first cell of block of 
length 2 which ends a brick and $L(j) =-1$ if $j$ 
is the first cell of block of 
length 2 which does not end a brick,
\item[(c)] $L(j) =(x-1)$ if $j$ is the first cell of block of 
length $\geq 4$  which ends a brick and $L(j) =-(x-1)$ if $j$ is the first cell of block of 
length $\geq 4$ which does not end a brick, and 
\item[(d)] $L(j) = (x-1)$ if $j$ is a cell which starts a 
$\tau^{(i)}$-match in a block of length $\geq 6$ which is not 
the first cell in its block. 
\end{description}
\end{enumerate}
We define the weight of  
$(T,\alpha,L)$, $w(T,\alpha,L)$,  to be  $\prod_{j=1}^{2n} L(j)$. 
For example, in Figure \ref{fig:Aexample1}, $T = (2,8,6)$, 
$\alpha = 1~3~4~5~7~10~9~12~11~13~2~8~6~14~15~16$, and $L$ is the labeling 
where all the cells 
which do not have explicit label in them are assumed to have label 1. 


\fig{Aexample1}{An elements of $\mathcal{T}_{16,\tau^{(1)}}$.}

We let $\mathcal{T}_{2n,\tau^{(i)}}$ denote the set of 
all such triples constructed in this way.  It then follows 
that 
\begin{equation}\label{Ah3}
(2n)!\theta(h_{2n}) = 
\sum_{(T,\alpha,L) \in \mathcal{T}_{2n,\tau^{(i)}}} w(T,\alpha,L)
\end{equation}

Next we will define two involutions $I$ and $J$ which 
will show that RHS of (\ref{Ah3}) is equal to the RHS of (\ref{Ah0}). 
We define  $I:\mathcal{T}_{2n,\tau^{(i)}} \rightarrow 
\mathcal{T}_{2n,\tau^{(i)}}$ as follows. 
Suppose that we are given  a triple $(T,\alpha,L)$ 
where $T= (d_1, \ldots, d_k)$. Then 
read the bricks from left 
to right until you find the first brick $d_j$ such that either 
(i) the generalized maximum packing corresponding to 
the elements in 
$d_j$ consists of more than one block or (ii) 
the generalized maximum packing corresponding to 
the elements in $d_j$ consists of a 
single block and the last element of $d_j$ is less than the 
first element of the following brick $d_{j+1}$. In case (i), 
split $d_j$ into two bricks $d^*$ and $d^{**}$ where 
$d^*$ contains the cells of the first block in the generalized maximum packing corresponding to the elements in $d_j$ and $d^{**}$ contains 
the remaining cells of $d_j$. We keep all the 
labels the same except that we change the label on the first 
cell of $d^{*}$ from $-1$ to $1$ if the first block of $d_j$ is of length  
$2$ and from $-(x-1)$ to $(x-1)$ if the first block of $d_j$ has 
length $\geq 4$.  In case (ii), we combine bricks $d_j$ and $d_{j+1}$ into 
a single brick $d$. Note that since the last element 
of $d_j$ is less than the first element of $d_{j+1}$, the elements 
in the new brick $d$ will still reduce to a 
generalized maximum packing for 
$\tau^{(i)}$. 
We keep all the 
labels the same except that we change the label on the first 
cell of $d_j$ from $1$ to $-1$ if  $d_j$ is of length  
$2$ and from $(x-1)$ to $-(x-1)$ if $d_j$ has 
length $\geq 4$.  In both cases, we do not change the underlying 
permutation $\alpha$.
If neither case (i) nor case (ii) applies, 
then $I(T,\alpha,L) = (T,\alpha,L)$.  
For example, if $(T,\alpha, L)$ is the element of 
$\mathcal{T}_{16,\tau^{(1)}}$ pictured in Figure \ref{fig:Aexample1}, 
then we are in case (ii) since we can combine the first and second 
bricks so that $I(T,\alpha,L)$ is pictured in Figure \ref{fig:Aexample2}. 

\fig{Aexample2}{The image of $(T,\alpha,L)$ in Figure \ref{fig:Aexample1} under $I$.}



It is easy to 
see that if $I(T,\alpha,L) = (T',\alpha,L') \neq (T,\alpha,L)$, then 
$I(T',\alpha,L') = (T,\alpha,L)$ and $w(T,\alpha,L) = - w(T',\alpha,L')$. 
Hence $I$ shows that 
\begin{eqnarray}\label{Ah4}
(2n)!\theta(h_{2n}) &=& 
\sum_{(T,\alpha,L) \in \mathcal{T}_{2n,\tau^{(i)}}} w(T,\alpha,L) 
\nonumber \\
&=& \sum_{(T,\alpha,L) \in \mathcal{T}_{2n,\tau^{(i)}}, I(T,\alpha,L) = 
(T,\alpha,L)} w(T,\alpha,L).
\end{eqnarray}
Thus we must examine the fixed points of $I$. Clearly, 
if $(T,\alpha,L)$ is a fixed point of $I$, then the elements 
of each brick $d$ in $T$ must reduce to a generalized maximum 
packing of $\tau^{(i)}$ which consists of a single block. 
Second, we must not be able to combine any two bricks so 
that if $T=(d_1, \ldots, d_k)$, then the last element of 
$d_j$ is greater than the first element of $d_{j+1}$ for 
$j =1, \ldots, k-1$.  But this means that the underlying permutation 
$\alpha$ is an up-down permutation. It follows that the fixed 
points $I$ consists of triples $(T,\alpha,L)$ such that 
\begin{description}
\item[$(I)$] $\alpha$ is an up-down permutation of length $2n$, 
\item[$(II)$] $T=(d_1, \ldots, d_k)$ where each $d_j$ has even length and 
the elements of $d_j$ reduce to a generalized maximum packing 
of $\tau^{(i)}$ which consists of a single block, and 
\item[$(III)$] the label of $L(j)$ of the $j$th cell of $T$ is 
$(x-1)$ if $j$ is the start of $\tau^{(i)}$-match in $\alpha$ and is 
equal to $1$ otherwise.  
\end{description}

Next we want to modify our interpretation of the 
right-hand side of (\ref{Ah4}) to consists of all triples  
$(T',\alpha,L')$ such that 
\begin{description}
\item[$(I')$] $\alpha$ is an up-down permutation of length $2n$, 
\item[$(II')$] $T=(d_1, \ldots, d_k)$ where each $d_j$ has even length and 
the elements of $d_j$ reduce to a generalized maximum packing 
of $\tau^{(i)}$ which consists of a single block, and 
\item[$(III')$] the label of $L(j)$ of the $j$th cell of $T$ is either 
$x$ or $-1$ if $j$ is the start of $\tau^{(i)}$-match in $\alpha$ and is 
equal to $1$ otherwise.  
\end{description}
We let $\mathcal{FI}_{2n,\tau^{(i)}}$ denote the set of triples 
$(T',\alpha,L')$ satisfying $(I')$-$(III')$ and for any 
$(T',\alpha,L') \in \mathcal{FI}_{2n,\tau^{(i)}}$, we define 
the weight of $(T',\alpha,L')$, $w(T',\alpha,L')$, to 
be $\prod_{j=1}^{2n} L'(j)$. 
For example, Figure \ref{fig:Aexample3} pictures an element 
of $\mathcal{FI}_{16,\tau^{(1)}}$ whose weight is $x$ where again 
the cells which do not have labels are assumed to have label 1. 


\fig{Aexample3}{An element of $\mathcal{FI}_{16,\tau^{(1)}}$.}



It then follows that 
\begin{equation} \label{Ah5}
(2n)!\theta(h_{2n}) = 
\sum_{(T',\alpha,L') \in \mathcal{FI}_{2n,\tau^{(i)}}} w(T',\alpha,L').
\end{equation}

Next we define an involution $J: \mathcal{FI}_{2n,\tau^{(i)}} \rightarrow 
\mathcal{FI}_{2n,\tau^{(i)}}$. Given an element 
$(T,\alpha,L) \in \mathcal{FI}_{2n,\tau^{(i)}}$, scan the 
cells of $T =(d_1, \ldots, d_k)$ from left to right looking for the first brick  $d_j$ such that either (A) $d_j$ has a $-1$ label on one of its cells 
or (B) the elements of $d_j$ and $d_{j+1}$ reduce a generalized 
maximum packing of $\tau^{(i)}$ which consists of a single block. 
In case (A), we break $d_j$ into 2 bricks $d^*$ and $d^{**}$ as follows. 
We know that that there $\tau^{(i)}$-matches starting at cells 
$1,3, \ldots ,d_j-3$ of $d_j$. Let 
$c$ be the  left most cell of $d_j$ which has a $-1$ label.
If $c$ is the first cell of $d_j$, then  
$d^*$ will consist of the first two cells of $d_j$ and $d^{**}$ will 
consist of the rest of the cells of $d_j$. 
If $c$ is not the first cell of $d_j$, then $c$ is the $(2s-1)$th cell of $d_j$ for some $s > 1$. 
Thus there are $\tau^{(i)}$-matches starting at cell $c-2$ and at cell $c$ 
of $d_j$ and cell $c-2$ is labeled with $x$.  Then we let $d^*$ be the contain the cells 
of $d_j$ up to and including cell $c+2$ and $d^{**}$ contain the 
rest of the cells of $d_j$. In either case, we remove 
the $-1$ label from cell $c$ and replace it by $1$. In case (B), 
there must a $\tau^{(i)}$-match starting at the second to last cell 
of $d_j$ that includes the last two cells of $d_j$ and the first 
two cells of $d_{j+1}$.  We then replace replace the bricks 
$d_j$ and $d_{j+1}$ by a single brick $d$ and replace 
the label of $1$ on the 
second to last cell of $d_j$ by $-1$. In either case, we do not 
change the underlying permutation $\alpha$. 
If neither case (A) or case (B) applies, then we let 
$J(T,\alpha,L) =(T,\alpha,L)$.  For example, if we 
consider the $(T,\alpha,L)$ as pictured in Figure 
\ref{fig:Aexample3}, we cannot combine bricks $d_1$ and $d_2$ because 
$\alpha$ does not have a $\tau^{(1)}$-match starting cell 1 and 
we cannot combine bricks $d_2$ and $d_3$ because 
$\alpha$ does not have a $\tau^{(1)}$-match starting cell 3. Thus we are 
in case (B) where $d_j =d_3$ and $c =7$. Thus we split 
$d_3$ at two cells to the right of cell $c$ which means at cell 9. 
Thus $J(T,\alpha,L) = (T',\alpha,L')$ is pictured in 
Figure \ref{fig:Aexample4}. 
Note that it will automatically be the case that the first action 
that we can take for $(T',\alpha,L')$ is to combine the 
two bricks that made up the $d_3$ in $(T,\alpha,L)$. 


\fig{Aexample4}{$J(T,\alpha,L)$ for $(T,\alpha,L)$ of Figure \ref{fig:Aexample3}.}


It is easy to see that 
if $J(T,\alpha,L) = (T',\alpha,L') \neq (T,\alpha,L)$, then 
$w((T,\alpha,L) = - w(T',\alpha,L')$ and  
$J(T',\alpha,L') = (T,\alpha,L)$. Thus it follows that 

\begin{equation} \label{Ah6}
(2n)!\theta(h_{2n}) = 
\sum_{(T,\alpha,L) \in \mathcal{FI}_{2n,\tau^{(i)}},
J(T,\alpha,L) = (T,\alpha,L)} w(T,\alpha,L).
\end{equation}
 
Thus we must examine the fixed points of $J$. If 
$J(T,\alpha,L) = (T,\alpha,L)$, then clearly $(T,\alpha,L)$ can have no 
cells which have a $-1$ label.  Thus in a brick $d$ of $T$ of length $\geq 4$, 
the start of every $\tau^{(i)}$-match contained in $d$ is labeled with an $x$. 
Moreover, there cannot be a $\tau^{(i)}$-match that involves  
cells in two different bricks since otherwise we could combine those 
two bricks since we would be guaranteed that elements of 
those two bricks would reduce to a generalized maximum packing for 
$\tau^{(i)}$ with 
a single block. Hence $w(T,\alpha,L) = x^{\tau^{(i)}\mbox{-mch}(\alpha)}$ 
Moreover if we are given an $\alpha \in \mathcal{A}_{2n}$, we can create a 
fixed point  $(T,\alpha,L)$ of $J$ by defining the bricks 
$d_1, d_2, \ldots $ inductively. 
That is, we let $d_1$ be of  length 2 if there is no $\tau^{(i)}$-match in $\alpha$ starting 
at 1 and $d_1$ be of length $2s$ if there are 
 $\tau^{(i)}$-matches starting at positions $1,3, \ldots, 2s-3$ but not at 
$2s-1$ in $\alpha$. Then having defined bricks $d_1, \ldots, d_r$ 
where $d_r$ ends at cell $c = 2k < 2n$, we let $d_{r+1}$ be of  length 2 if there is no $\tau^{(i)}$-match in $\alpha$ starting 
at $2k+1$ and $d_{r+1}$ be of length $2s$ if there are 
 $\tau^{(i)}$-matches starting at positions $2k+1,2k+3, \ldots, 2k+2s-3$ but not at 
$2k+2s-1$ in $\alpha$. 
Hence 
\begin{equation*}\label{Ah7}
(2n)!\theta(h_{2n}) =  \sum_{\alpha \in \mathcal{A}_{2n}} x^{\tau^{(i)}\mbox{-mch}(\alpha)}.
\end{equation*}

It then follows that 
\begin{align*}
\theta(\sum_{n \geq 0} h_n t^n) &= 1+ \sum_{n \geq 1} \frac{t^{2n}}{(2n)!} 
\sum_{\alpha \in \mathcal{A}_{2n}} x^{\tau^{(i)}\mbox{-mch}(\alpha)} \\
&= \frac{1}{1 + \sum_{n \geq 1}(-t)^n \theta(e_n)} \\
&= \frac{1}{1 - \sum_{n \geq 1} \frac{t^{2n}}{(2n)!}GMP_{2n,\tau^{(i)}}(x)} 
\end{align*}
which is what we wanted to prove. 




To prove (\ref{eqB}), we need to define an appropriate weight 
function $\nu:\{1,2, \ldots \} \rightarrow \mathbb{Q}(x)$. That is, 
we let 
\begin{equation*}\label{Bp1}
\nu(2n-1) =0 \  \mbox{and} \ \nu(2n) = (2n) \frac{GMP_{2n-1,\tau^{(i)}}(x)}{GMP_{2n,\tau^{(i)}}(x)} 
\ \mbox{for all $n \geq 1$.}
\end{equation*}
 We have designed $\nu$ so that $
\nu(2n)\theta(e_{2n}) = \frac{(-1)^{2n-1}}{(2n-1)!}GMP_{2n-1,\tau^{(i)}}(x)$.
Then we claim that for all $n \geq 0$, $\theta(p_{2n+1,\nu}) =0$  and 
\begin{equation}\label{Bp3}
(2n+1)!\theta(p_{2n+2,\nu}) = \sum_{\sg \in \mathcal{A}_{2n+1}} 
x^{\tau^{(i)}\mbox{-mch}(\sg)}.
\end{equation} 
Note that by (\ref{pnuexp}), 
$$\theta(p_{2n+1,\nu}) = \sum_{\mu \vdash 2n+1} 
(-1)^{2n+1 - \ell(\mu)} w_{\nu}(B_{\mu,2n+1}) \theta(e_{\mu}).
$$
Clearly if $\mu$ is partition of $2n+1$, then $\mu$ must 
have an odd part so that $\theta(e_\mu)=0$. Thus 
$\theta(p_{2n+1,\nu}) =0$ for all $n \geq 0$.  It also 
follows that when we want to compute 
$\theta(p_{2n+2,\nu})$, we can restrict ourselves to considering 
partitions 
 of the form $2\la$ where $\la$ is a partition 
of $n+1$.  Thus 
\begin{align} \label{Bp4}
&(2n+1)!\theta(p_{2n+2,\nu}) = (2n+1)! \sum_{\la \vdash n+1} (-1)^{2n+2-\ell(\la)}
\sum_{T =(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,2n+2}}
\nu(2b_{\ell(\la)}) \theta(e_{2b_{\ell(\la)}}) \times \nonumber \\
& \ \ \ \  \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \prod_{j=1}^{\ell(\la)-1} \theta(e_{2b_j}) \nonumber \\
&= (2n+1)! \sum_{\la \vdash n+1} (-1)^{2n+2-\ell(\la)}
\sum_{T =(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,2n+2}} 
\frac{(-1)^{2b_{\ell(\la)}-1}}{(2b_{\ell(\la)}-1)!} 
GPM_{2b_{\ell(\la)}-1,\tau^{(i)}} \times \nonumber \\
& \ \ \ \  \ \ \ \ \ \ \  \prod_{j=1}^{\ell(\la)-1} \frac{(-1)^{2b_j -1}}{(2b_j)!} 
GMP_{2b_j,\tau^{(i)}}(x) \nonumber \\
& =  \sum_{\la \vdash n+1} \sum_{T =(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,2n+2}} \binom{2n+1}{2b_1,\ldots,2b_{\ell(\la)-1},2b_{\ell(\la)}-1} 
GPM_{2b_{\ell(\la)}-1,\tau^{(i)}} \times \\
& \ \ \ \  \ \ \ \ \ \ \ \prod_{j =1}^{\ell(\la)-1} GMP_{2b_j,\tau^{(i)}}(x). \nonumber
\end{align}

As before,  we want to give a combinatorial interpretation to 
the right-hand side of (\ref{Bp4}). We start with a brick tabloid 
$T= (2b_1, \ldots, 2b_{\ell(\la)})$ of length $2n+2$ and type $2\la$.  Then 
the binomial coefficient 
$\binom{2n+1}{2b_1,\ldots,2b_{\ell(\la)-1},2b_{\ell(\la)}-1}$ 
allows us to pick a set partition $\vec{U} = (U_1, \ldots, U_{\ell(\la)})$ of 
$\{1, \ldots, 2n\}$ where $|U_i| =2b_i$ for $i =1, \ldots, \ell(\la)-1$ 
and $|U_{\ell(\la)}|=2b_{\ell(\la)}-1$.   
Next we use the factor 
$GMP_{2b_{\ell(\la)} -1,\tau^{(i)}}(x) \prod_{j =1}^{\ell(\la)-1} GMP_{2b_j,\tau^{(i)}}(x)$ to 
choose a sequence of permutations $\vec{\sg} = (\sg^{(1)}, \ldots, \sg^{(\ell(\la))})$ 
such that $\sg^{(j)} \in \mathcal{A}_{2b_j}$ is a generalized maximum packing for 
$\tau^{(i)}$ for $j =1, \ldots, \ell(\la)-1$ and 
$\sg^{(\ell(\la))} \in \mathcal{A}_{2b_{\ell(\la)}-1}$ is a generalized maximum packing for $\tau^{(i)}$. 
Then for each $j$, we let $\alpha^{(j)}$ be the sequence 
that arises by replacing the $r$th largest element of 
$\sg^{(j)}$ by the $r$th largest element of $U_j$ and then 
placing these elements in the cells of brick $2b_j$ from 
left to right. This means that for the last brick 
$2b_{\ell(\la)}$, we will fill in all but the last cell which we leave 
blank. 
For example, we have pictured this process  
for $\tau^{(1)} = 1324$ where the underlying brick tableau 
$T=(2,8,6)$. We have also indicated the block structure 
in each brick by underlying those elements in a common block. 
The weight of such a triple $(T,\vec{U},\vec{\sg})$,   $w(T,\vec{U},\vec{\sg})$, is 
$\prod_{j=1}^{\ell(\la)} w(\sg^{(j)})$.  We can interpret 
 $w(T,\vec{U},\vec{\sg})$ by placing a weight $1$ on top of each 
block of length 1 or $2$ that ends  a brick and a weight of $-1$ on 
each block of length 2 which does not end a brick.  For blocks 
of length $\geq 4$, we place a 2weight of $(x-1)$ at start of 
each $\tau^{(i)}$-match in the block. Finally, 
we replace the weight of the first $\tau^{(i)}$-match in the 
block by $-(x-1)$ if the block is not the last block in its brick. 
Thus the RHS of (\ref{Bp4}) can be interpreted as the sum of the 
weights of all 
triples $(T,\alpha,L)$ such that  
\begin{enumerate}
\item $T= (d_1, \ldots, d_k)$ is brick tabloid of shape $(2n+2)$ where 
each brick $d_j$ has even length, 
\item $\alpha$ is a permutation of $S_{2n+1}$ such that 
in each brick $d_j$ with $j < k$, 
the elements in brick $d_j$ reduce  
to a permutation in $\mathcal{GMP}_{d_j,\tau^{(i)}}$ 
and the elements in brick $d_k$ fill the first 
$d_k-1$ cells of brick $d_k$ and reduce to a permutation in 
$\mathcal{GMP}_{d_k-1,\tau^{(i)}}$,  and 
\item $L:\{1,\ldots, 2n+1\} \rightarrow \mathbb{Q}[x]$ assigns 
a label to each cell in $T$ where $L(j)$ denotes the label  of 
$j$th cell of $T$, reading from left to right, and 
\begin{description}
\item[(a)] $L(j) =1$ if $j$ is the second cell of a block of 
length 2 or $j$ does not start a $\tau^{(i)}$-match in a block 
of length $\geq 4$, 
\item[(b)] $L(j) =1$ if $j$ is the first cell of block of 
length 1 or 2 which ends a brick and $L(j) =-1$ if $j$ is the first cell of block of 
length 2 which does not end a brick,
\item[(c)] $L(j) =(x-1)$ if $j$ is the first cell of block of 
length $\geq 4$  which ends a brick and $L(j) =-(x-1)$ if $j$ if the first cell of block of 
length $\geq 4$ which does not end a brick, and 
\item[(d)] $L(j) = (x-1)$ if $j$ is a cell which starts a 
$\tau^{(i)}$-match in a block of length $\geq 6$ which is not 
the first cell in its block, 
\end{description}
\end{enumerate}
where  the weight of  
$(T,\alpha,L)$, $w(T,\alpha,L)$, equals $\prod_{j=1}^{2n+1} L(j)$. 
For example, in Figure \ref{fig:Bexample1}, $T = (2,8,6)$, 
$\alpha = 1~4~3~7~5~10~9~12~11~13~2~8~6~14~15$, and $L$ is the labeling 
where all the cells 
which do not have explicit label in them are assumed to have label 1. 


\fig{Bexample1}{An element of $\mathcal{T}_{15,\tau^{(1)}}$.}

We let $\mathcal{T}_{2n+1,\tau^{(i)}}$ denote the set of 
all such triples constructed in this way.  It then follows 
that 
\begin{equation}\label{Bp5}
(2n+1)!\theta(p_{2n+2,\nu}) = 
\sum_{(T,\alpha,L) \in \mathcal{T}_{2n+1,\tau^{(i)}}} w(T,\alpha,L)
\end{equation}



Note that the only differences between the fillings of even 
length in the proof of (\ref{Ah0}) and our current fillings 
is that, in our current fillings, we have forced that the 
last brick  ends in  a block of length 1 and the last cell of 
that brick is blank. 

Next we will define two involutions $I$ and $J$ which 
will show that RHS of (\ref{Bp5}) is equal to the RHS of (\ref{Bp3}). 
In fact the definitions of $I$ and $J$ are essentially the 
same as before.  We simply observe that 
the fact that the last block of the final brick is length 1 does 
not change things. 
We define  $I:\mathcal{T}_{2n+1,\tau^{(i)}} \rightarrow 
\mathcal{T}_{2n+1,\tau^{(i)}}$ as follows. 
Given a triple $(T,\alpha,L)$, let $T= (d_1, \ldots, d_k)$. Then 
read the bricks from left 
to right until you find the first brick $d_j$ such that either 
(i) the generalized maximum packing corresponding to the 
elements in $d_j$ consists of more than one block or (ii) 
the generalized maximum packing corresponding to the 
elements in $d_j$ consists of a 
single block and the last element of $d_j$ is less than the 
first element of the following block $d_{j+1}$. In case (i), 
split $d_j$ into two bricks $d^*$ and $d^{**}$ where 
$d^*$ contains the cells of the first block of the generalized maximum packing corresponding to the 
elements in $d_j$ and $d^{**}$ contains 
the remaining cells of $d_j$. We keep all the 
labels the same except that we change the label on the first 
cell of $d^*$ from $-1$ to $1$ if the first block of $d_j$ is of length 
$2$ and from $-(x-1)$ to $(x-1)$ if the first block of $d_j$ has 
length $\geq 4$.  In case (ii), we combine bricks $d_j$ and $d_{j+1}$ into 
a single brick $d$. Note that since the last element 
of $d_j$ is less than the first element of $d_{j+1}$, the elements 
in the new brick $d$ will still reduce to a  generalized maximum packing 
of $\tau^{(i)}$. 
We keep all the 
labels the same except that we change the label on the first 
cell of $d_j$ from $1$ to $-1$ if  $d_j$ is of length 
$2$ and from $(x-1)$ to $-(x-1)$ if $d_j$ has 
length $\geq 4$.  In both cases, we do not change the underlying 
permutation $\alpha$.
If neither case (i) or case (ii) applies, 
then $I(T,\alpha,L) = (T,\alpha,L)$.  
For example, if $(T,\alpha, L)$ is the element of 
$\mathcal{T}_{15,\tau^{(1)}}$ pictured in Figure \ref{fig:Bexample1}, 
then we are in case (i) since we cannot combine the first and second 
bricks or the second and third bricks. Thus we break 
that last brick into two bricks where the final 
brick of length 2 which has a single block of length 1.  
$I(T,\alpha,L)$ is pictured in Figure \ref{fig:Bexample2}. 

\fig{Bexample2}{The image of $(T,\alpha,L)$ in Figure \ref{fig:Bexample1} under $I$.}

It is easy to 
see that if $I(T,\alpha,L) = (T',\alpha,L') \neq (T,\alpha,L)$, then 
$I(T',\alpha,L') = (T,\alpha,L)$ and $w(T,\alpha,L) = - w(T',\alpha,L')$. 
Hence $I$ shows that 
\begin{eqnarray}\label{Bpp}
(2n-1)!\theta(p_{2n+2,\nu}) &=& 
\sum_{(T,\alpha,L) \in \mathcal{T}_{2n+1,\tau^{(i)}}} w(T,\alpha,L) 
\nonumber \\
&=& \sum_{(T,\alpha,L) \in \mathcal{T}_{2n+1,\tau^{(i)}}, I(T,\alpha,L) = 
(T,\alpha,L)} w(T,\alpha,L).
\end{eqnarray}



Again we must examine the fixed points of $I$. Clearly, 
if $(T,\alpha,L)$ is a fixed point of $I$, then the elements 
of each brick $d$ in $T$ must reduce to a generalized maximum 
packing of $\tau^{(i)}$ which consists of a single block. In 
particular, this means that the last brick of $T$ must 
be a length 2 and consist of a block with 1 element. 
Second, we must not be able to combine any two bricks so 
that if $T=(d_1, \ldots, d_k)$, then the last element of 
$d_j$ is greater than the first element of $d_{j+1}$ for 
$j =1, \ldots, k-1$.  But this means that the underlying permutation 
$\alpha$ is an up-down permutation. It follows that the fixed 
points $I$ consists of triples $(T,\alpha,L)$ such that 
\begin{description}
\item[(I)] $\alpha$ is an up-down permutation of length $2n+1$, 
\item[(II)] $T=(d_1, \ldots, d_k)$ where each $d_j$ with $j < k$ 
has even length and 
the elements of $d_j$ reduces to a generalized maximum packing 
of $\tau^{(i)}$ which consists of a single block, 
\item[(III)] $d_k$ is a brick of length 2 which consists of a single block of length 1, and  
\item[(IV)] the label of $L(j)$ of the $j$th cell of $T$ is 
$(x-1)$ if $j$ is the start of $\tau^{(i)}$-match in $\alpha$ and is 
equal to $1$ otherwise.  
\end{description}



Now we can modify our interpretation of the 
right-hand side of (\ref{Bpp}) and define the involution $J$ exactly 
as before since the last element in the last brick never played 
a role in either the modification or the involution $J$. 
Thus $J$ will show that  

\begin{equation} \label{Bp6}
(2n+1)!\theta(p_{2n+2,\nu})  = \sum_{\alpha \in \mathcal{A}_{2n+1}} x^{\tau^{(i)}\mbox{-mch}(\alpha)}.
\end{equation}


It then follows that 
\begin{align}\label{Bp7}
\theta(\sum_{n \geq 1} p_{n,\nu} t^n) &= \sum_{n \geq 0} \frac{t^{2n+2}}{(2n+1)!} \sum_{\alpha \in \mathcal{A}_{2n+1}} x^{\tau^{(i)}\mbox{-mch}(\alpha)} \nonumber \\
&= \frac{\sum_{n \geq 1} (-1)^{n-1} \nu(n) \theta(e_n) t^n}{\sum_{n \geq 0} (-1)^n \theta(e_n) t^n} \nonumber \\
&= \frac{\sum_{n \geq 1} \frac{t^{2n}}{(2n-1)!}GMP_{2n-1,\tau^{(i)}}(x)}{1 - \sum_{n \geq 1} \frac{t^{2n}}{(2n)!}GMP_{2n,\tau^{(i)}}(x)}.
\end{align}


Dividing  both sides of (\ref{Bp7}) by $t$ gives (\ref{eqB})  
which is what we wanted to prove. 



\section{Computing $\mmp_{n,\tau^{(i)}}$.}

In this section, we shall consider the problem 
of computing $\mmp_{\tau^{(i)},n}$ since we will 
need such computations to compute $GMP_{\tau^{(i)},n}$.  


The problem of computing  $\mmp_{\tau^{(i)},2n}$ has been studied 
by Harmse and Remmel \cite{HR} in a different context. Harmse 
and Remmel studied maximum packings in column strict arrays. 
That is, let 
 $\mathcal{F}_{n,k}$ denote the set of all fillings 
of a $k \times n$ rectangular array with the integers $1, \ldots, 
kn$ such that the elements increase from bottom to top 
in each column. We let $(i,j)$ denote the cell in the 
$i$th row from the bottom and the $j$th column from the left of the $k \times n$ rectangle 
and we let $F(i,j)$ denote the element in cell $(i,j)$ of 
$F\in\mathcal{F}_{n,k}$. 



If $F$ is any filling of a $k \times n$-rectangle with distinct positive 
integers such that elements in each column increase, 
reading from bottom to top, then 
we let $\red{F}$ denote the element of 
$\mathcal{F}_{n,k}$ which results from $F$ by replacing 
the $i$th smallest element of $F$ by $i$. For example, Figure \ref{fig:red} demonstrates 
a filling, $F$, with its corresponding reduced filling, $\red{F}$.


\fig{red}{An example of $F\in\mathcal{F}_{3,4}$ and $\red{F}$.}

If $F \in \mathcal{F}_{n,k}$ and $1 \leq c_1 < \cdots < c_j \leq n$, then 
we let $F[c_1,\ldots,c_j]$ be the filling of the $k \times j$ rectangle 
where the elements in column $a$ of $F[c_1,\ldots,c_j]$ equal the elements 
in column $c_a$ in $F$ for $a = 1, \ldots, j$.   We can 
then extend the usual pattern matching definitions from permutations 
to elements of  $\mathcal{F}_{n,k}$ as follows. 
\begin{definition}\label{def1} Let $P$ be an element of 
$\mathcal{F}_{j,k}$ and $F \in \mathcal{F}_{n,k}$ where $j \leq n$. 
Then we say
\begin{enumerate}
\item  $P$ {\bf occurs} in $F$ if there are
$1 \leq i_1 < i_2 < \cdots < i_j \leq n$ such that \\
$\red{F[i_1, \ldots, i_j]} = P$,

\item $F$ {\bf avoids} 
$P$ if there is no occurrence of $P$ in $F$, and   

\item there is a {\bf $P$-match  in $F$ starting at
position $i$} if $\red{F[i,i+1, \ldots, i+j-1]} = P$.
\end{enumerate}
\end{definition}
When $k=1$, then $\mathcal{F}_{n,1}=S_n$, where $S_n$ is the symmetric 
group, and our definitions reduce to the standard definitions that 
have appeared in the pattern matching literature. 



We let $\Pmch{F}$ denote the 
number of $P$-matches in $F$.  For example, if we consider the fillings $P \in \mathcal{F}_{3,3}$ and 
$F,G \in \mathcal{F}_{6,3}$ shown in Figure \ref{fig:Pmatch}, 
then it is easy to see that there are no $P$-matches in $F$ 
but there is an occurrence of $P$ in $F$, since 
$\red{F[1,2,5]} =P$. Also, there are 2 $P$-matches in $G$ starting at 
positions 1 and 2, respectively, so $\Pmch{G} =2$.  


\fig{Pmatch}{Examples of $P$-matches and occurrences of $P$.} 


If $P \in \mathcal{F}_{2,k}$, then 
we define $MP_{n}^{P}$ to be the set of 
$F \in \mathcal{F}_{n,k}$ with $\Pmch{F} = n-1$, i.e. the set of 
$F \in \mathcal{F}_{n,k}$ with the property that 
there are
$P$-matches in $F$ starting at positions $1,2, \ldots, n-1$.  
We let $\mmp_n^P = |MP_n^P|$ and, by convention, we define $\mmp_{1}^{P}=1$.


For each $\tau^{(i)}$, let $P^{(i)}$ denote the element of 
$\mathcal{F}_{2,2}$ 
such that the first and third elements of $\tau^{(i)}$ are  
the first and second elements in row 1 of $P^{(i)}$, respectively, and 
the second and forth elements of $\tau^{(i)}$ are 
the first and second elements in row 2 of $P^{(i)}$, respectively. 
We have pictured $P^{(1)}, \ldots, P^{(5)}$ in Figure 
\ref{fig:correspond}.  It is then easy to see that given 
maximum packing $F \in  \mathcal{F}_{n,2}$ of $P^{(i)}$, 
one can construct an up-down permutation $\sg(F) \in \mathcal{A}_{2n}$ 
which is a 
maximum packing for $\tau^{(i)}$ by reading 
each column from bottom to top and the columns from right to left. 
Vice versa, given $\sg = \sg_1 \ldots, \sg_{2n} \in \mathcal{A}_{2n}$ which 
is a maximum packing for $\tau^{(i)}$, we can obtain an 
element $F(\sg) \in  \mathcal{F}_{n,2}$ which is a maximum 
packing for  $P^{(i)}$ by placing $\sg_1, \sg_3, \ldots, \sg_{2n-1}$ in 
the bottom row of $F(\sg)$, reading from left to right, and 
placing $\sg_2, \sg_4, \ldots, \sg_{2n}$ in 
the top row of $F(\sg)$, reading from left to right. An example  
of this correspondence is pictured at the top of 
Figure \ref{fig:correspond} for $\tau^{(1)} = 1324$ and $P^{(1)} = \begin{array}{|c|c|}
 \hline 3 & 4 \\
 \hline 1 & 2 \\
 \hline
 \end{array}$.


\fig{correspond}{The correspondence between 
$\mathcal{MP}_{2n,\tau^{(i)}}$ and $\mathcal{MP}^{P^{(i)}}_n$.}




It follows that for $i=1, \ldots, 5$, $\mmp_{2n,\tau^{(i)}} = 
\mmp_n^{P^{(i)}}$. Now Harmse and Remmel \cite{HR} proved that for 
$n \geq 2$, 
\begin{eqnarray*}
\mmp_n^{P^{(1)}}&=& \mmp_n^{P^{(4)}}= C_{n-1} \ \mbox{and} \\
\mmp_n^{P^{(2)}}&=& \mmp_n^{P^{(3)}}= \mmp_n^{P^{(5)}}= 1.
\end{eqnarray*}
Thus we obtain the following theorem. 
\begin{theorem} For all $n \geq 2$, 
$\displaystyle \mmp_{2n,\tau^{(1)}}= \mmp_{2n,\tau^{(4)}}= C_{n-1}$ and \\ 
$\displaystyle 
\mmp_{2n,\tau^{(2)}} = \mmp_{2n,\tau^{(3)}}= \mmp_{2n,\tau^{(5)}}= 1$.
\end{theorem}

Our next goal is to prove the following. 

\begin{theorem} For all $n \geq 2$, $\displaystyle 
\mmp_{2n+1,\tau^{(1)}} = (2n)C_{n-1}$, $\displaystyle \mmp_{2n+1,\tau^{(2)}} =  2n$,\\
$\displaystyle \mmp_{2n+1,\tau^{(3)}}= C_{n-1} +C_n$, $\displaystyle  \mmp_{2n+1,\tau^{(4)}} = n+1$ and $\displaystyle mmp_{2n+1,\tau^{(5)}}=  2$.
\end{theorem}


To compute $\mmp_{2n+1,\tau^{(i)}}$, we must exploit 
some of the techniques used by Harmse and Remmel 
\cite{HR} to compute $\mmp^{P}_n$ for $P \in \mathcal{F}_{2,k}$. 
To help us visualize the order relationships 
within $P^{(i)}$, we form a directed graph $G_{P^{(i)}}$ on the cells of the
$2 \times 2$ rectangle by drawing a directed edge 
from the position of the number $j$ to the position 
of the number $j+1$ in $P$ for $j =1, \ldots, 3$.  For example, in 
Figure \ref{fig:P1}, the graph $G_{P^{(1)}}$ is pictured 
immediately to the right $P^{(1)}$. 
Then $G_{P^{(i)}}$ determines the order relationships between all the cells in $P^{(i)}$
since $P^{(i)}(r,s)<P^{(i)}(u,v)$ if there is a directed 
path from cell $(r,s)$ to cell $(u,v)$ in $G_{P^{(i)}}$. 
Now suppose that $F \in \mathcal{MP}_n^{P^{(i)}}$ where $n \geq 3$. Because  
there is a $P^{(i)}$-match starting in column $j$ for each 
$1 \leq j < n$, we can superimpose 
$G_{P^{(i)}}$ on the cells in columns $j$ and $j+1$ to determine the order 
relations between the elements in those two columns. If we do 
this for every pair of columns, $j$ and $j+1$ for $j =1, \ldots, n-1$, 
we end up with a directed graph on the cells of 
the $2 \times n$ rectangle which we will call $G_{n,P^{(i)}}$. 
For example, in Figure \ref{fig:P1},
$G_{6,P^{(1)}}$ is pictured  in the second row.  It is then 
easy to see that if $F \in \mathcal{MP}_n^{P^{(i)}}$ and there is a directed 
path from cell $(r,s)$ to cell $(u,v)$ in $G_{n,P^{(i)}}$, then 
it must be the case that $F(r,s) < F(u,v)$. 
Note that $G_{n,P^{(i)}}$ will always be a directed acyclic 
graph with no  multiple edges.  


\fig{P1}{The graphs $G_{n,P^{(1)}}$ and $G^+_{n,P^{(1)}}$.}


Harmse and Remmel \cite{HR} proved that 
the problem of computing $\mmp_n^{P^{(i)}}$ for any 
$P^{(i)} \in \mathcal{F}_{2,2}$ of shape $2^2$ can be reduced to finding 
the number of linear extensions of a certain poset associated 
with $P^{(i)}$. 
That is, the graph $G_{n,P^{(i)}}$ induces a poset 
$\mathcal{W}_{n, P^{(i)}} = (\{(i,j): 1 \leq i \leq 2\ \& \ 1 \leq j \leq n\}, <_W)$ 
on the cells of the 
$2 \times n$ rectangle by defining $(i,j) <_W (s,t)$ if 
and only if there is a directed 
path from $(i,j)$ to $(s,t)$ in $G_{n,P^{(i)}}$. 
Harmse and Remmel proved that there 
is a 1:1 correspondence between the elements of $\mathcal{MP}_n^{}$ 
and the linear extensions of $\mathcal{W}_{n,P^{(i)}}$. That is, 
if $F \in \mathcal{MP}_n^{P^{(i)}}$, then it is easy to see 
that $(a_1,b_1), \ldots, (a_{2n},b_{2n})$ where $F(a_i,b_i)= i$ is 
a linear extension of $\mathcal{W}_{P,n}$. Vice versa, if 
$(a_1,b_1), \ldots, (a_{2n},b_{2n})$ is a linear extension of 
$\mathcal{W}_{P,n}$, then one can define 
$F$ so that $F(a_i,b_i)=i$ and it will automatically be the case 
that $F \in \mathcal{MP}_n^{P^{(i)}}$. 


We can define a similar poset for maximum packings of 
$\tau^{(i)}$ of length $2n+1$.  Note that in a 
maximum packing $F \in \mathcal{MP}_n^{P^{(i)}}$, 
the element $a$ in the top right-hand corner 
of $F$ corresponds to the last element of $\sg(F)$ so that, 
to account for the last element in a permutation 
$\alpha = \alpha_1 \ldots \alpha_{2n+1} \in \mathcal{A}_{2n+1}$ which 
has $\tau^{(i)}$-matches  starting at positions $1,3, \ldots 2n-3$, 
we must add an extra element $b$ to graph 
$G_{n,P^{(i)}}$ with a directed arrow from $b$ to $a$ since we know that $\alpha_{2n} > \alpha_{2n+1}$. We let $G^+_{n,P^{(i)}}$ denote this extended graph. 
For example, the graph $G^+_{6,P^{(1)}}$ is pictured in the 
third line of Figure \ref{fig:P1}. It follows 
that $\mmp_{2n+1,\tau^{(i)}}$ equals the number of 
linear extensions of  $W_{G^+_{n,P^{(i)}}}$.





Next we state a  simple lemma  about directed acyclic graphs with no  multiple 
edges due to Harmse and Remmel \cite{HR} which will allow  
us to replace $G_{n,P^{(i)}}$ and  $G^+_{n,P^{(i)}}$
by a simpler acyclic directed graphs 
which contains the same information about their associated posets 
$W_{G_{n,P^{(i)}}}$ and  $W_{G^+_{n,P^{(i)}}}$.  Given  a directed acyclic graph $G = (V,E)$ 
with no multiple edges, let $Con(G)$ equal the set 
of all pairs $(i,j) \in V \times V$ such that there is a directed 
path in $G$ from vertex $i$ to vertex $j$. 

\begin{lemma} \label{lem:remove}
Let $G = (V,E)$ be a directed acyclic graph 
with no multiple edges. Let $H$ be the subgraph of $G$ that 
results by removing all edges $e=(i,j) \in E$ such that 
there is a directed path from $i$ to $j$ in $G$ that does not 
involve $e$. Then $Con(G) = Con(H)$. 
\end{lemma}


First consider the problem of computing 
$\mmp_{2n+1,P^{(1)}}$ for $n \geq 2$.  In this case, let 
$a$ be the rightmost element in the top row of $G_{n,P^{(1)}}$.
Since there is a directed path in $G_{n,P^{(1)}}$ 
from every element  other than $a$ to $a$, it must be the case 
that $a$ is the last element in any linear extension 
of $W_{G_{n,P^{(1)}}}$ and, hence, in any $F \in 
\mathcal{MP}^{P^{(1)}}_n$, $F(a) = 2n$. 
Note that same thing happens in $G^+_{n,P^{(1)}}$. That is, 
there is a directed path in $G^+_{n,P^{(1)}}$ 
from every element  other than $a$ to $a$. 
Thus it must be the case 
that $a$ is the last element in any linear extension 
of $W_{G^+_{n,P^{(1)}}}$ so that $a$ would be assigned 
the label $2n+1$ in any linear extension.  
But then it easy to see 
that $b$ can be assigned any element in $\{1, \ldots, 2n\}$. Thus once 
we pick the value assigned $b$, then the number of linear extensions 
of $G^+_{n,P^{(1)}}$ just reduces to the number of 
linear extensions of $G_{n,P^{(1)}}$ which is $C_{n-1}$. Thus 
$\mmp_{2n+1,\tau^{(1)}} = (2n)C_{n-1}$. 


\fig{P2}{The graphs $G_{n,P^{(2)}}$ and $G^+_{n,P^{(2)}}$.}


In Figure \ref{fig:P2}, we have pictured the graphs of 
$G_{6,P^{(2)}}$ and $G^+_{6,P^{(2)}}$ on the left in the second and 
third lines, respectively.  In both cases, one can use Lemma \ref{lem:remove} 
to show that we can remove all the vertical arrows in these graphs 
except the leftmost vertical arrow with out loosing any information 
about the number of linear extensions. Let 
$\overline{G}_{n,P^{(2)}}$ and $\overline{G}^+_{n,P^{(2)}}$ denote 
the resulting graphs obtained from $G_{n,P^{(2)}}$ and $G^+_{n,P^{(2)}}$, respectively. In this case, 
it is easy to see that in a linear extension 
of $G_{n,P^{(2)}}$, the rightmost top element $a$ must be the largest 
element $2n$ since there is a directed path in $G_{n,P^{(2)}}$ 
from every element other than $a$ to $a$.  The same 
thing happens in $G^+_{n,P^{(2)}}$, namely $2n+1$ must be assigned to $a$ 
since there is a directed path in $G^+_{n,P^{(2)}}$ 
from every element other than $a$ to $a$. But then it easy to see 
that $b$ can be assigned to any element in $\{1, \ldots, 2n\}$. Thus once 
we pick a value that is assigned to  $b$, then the number of linear extensions 
of $G^+_{n,P^{(2)}}$ just reduces to the number of 
linear extension of $G_{n,P^{(2)}}$ which is clearly just 1. Thus 
$\mmp_{2n+1,\tau^{(2)}} = 2n$. 

\fig{P3}{The graphs $G_{n,P^{(3)}}$ and $G^+_{n,P^{(3)}}$.}


In Figure \ref{fig:P3}, we have pictured the graphs of 
$G_{6,P^{(3)}}$ and $G^+_{6,P^{(3)}}$ on the second line. 
Now consider the element $b$ in $G^+_{n,P^{(3)}}$. If we 
assign $b$ the value 1, then there is no restriction  
on the linear extensions of the remaining elements 
so that we get a total of $C_{n-1}$ linear extensions 
in that case since $\mmp_{n,P^{(3)}} =C_{n-1}$. 
However, if $b >1$, then it is easy to see that rightmost 
bottom element must be the first element in any linear extension 
since there is a directed path from that element to any other 
element which not equal to $b$. Thus the rightmost bottom element 
must be assigned to 1. It then follows that we can extend the 
graph $G^+_{n,P^{(3)}}$ to a graph $G^{++}_{n,P^{(3)}}$ by adding 
a new element $0$ and adding new directed 
edges connecting 0 to 1 and 1 to $b$. This process is pictured 
on line 4 of Figure \ref{fig:P3}.  It is easy to see 
that the number of linear extensions of $G^+_{n,P^{(3)}}$ where $b > 1$ 
is just the number of linear extensions of $G^{++}_{n,P^{(3)}}$ which 
is the same as the number of linear extensions of $G_{n+1,P^{(3)}}$.
Since  the number of linear extensions of $G_{n+1,P^{(3)}}$  
is $C_n$, it follows that $\mmp_{2n+1,\tau^{(3)}} = C_{n-1} + C_{n}$. 



\fig{P4}{The graphs $G_{n,P^{(4)}}$ and $G^+_{n,P^{(4)}}$.}

In Figure \ref{fig:P4}, we have pictured the graphs of 
$G_{6,P^{(4)}}$ and $G^+_{6,P^{(4)}}$ on the left in the second and 
third lines, respectively.  In both cases, one can use Lemma \ref{lem:remove} 
to show that we can remove all the vertical arrows in the graphs 
except the rightmost vertical arrow with out loosing any information 
about the number of linear extensions $W_{G_{6,P^{(4)}}}$ and $W_{G^+_{6,P^{(4)}}}$. Let 
$\overline{G}_{n,P^{(4)}}$ and $\overline{G}^+_{n,P^{(4)}}$ denote 
the resulting graphs obtained from $G_{n,P^{(2)}}$ and $G^+_{n,P^{(2)}}$, 
respectively. In this case, 
it is easy to see that in any linear extension 
of $W_{G_{n,P^{(4)}}}$, the rightmost top element $a$ of  $G_{n,P^{(4)}}$
must be $(n+1)$st element in the linear extension of $W_{G_{6,P^{(4)}}}$
since 
there are $n$ elements $x$ for which there is a  directed path in 
$\overline{G}_{n,P^{(4)}}$ 
from $x$ to $a$ and there are $n-1$ elements $y$ such that there 
is a directed path from $a$ to $y$ in $\overline{G}_{n,P^{(4)}}$.
The same 
thing happens in $\overline{G}^+_{n,P^{(4)}}$, namely $a$ must be 
the $(n+2)$nd element in any linear extension of $W_{G^+_{6,P^{(4)}}}$
since 
there are $n+1$ elements $x$ for which there is a  directed path in 
$\overline{G}^+_{n,P^{(4)}}$ 
from $x$ to $a$ and there are $n-1$ elements $y$ such that there 
is a directed path from $a$ to $y$ in $\overline{G}^+_{n,P^{(4)}}$.
Hence we can assign $b$ to be any element from $1, \ldots ,n+1$. 
Once 
we pick a value for $b$, then the number of linear extensions 
of $\overline{G}^+_{n,P^{(4)}}$ just reduces to the number of 
linear extensions of $\overline{G}_{n,P^{(4)}}$ which is clearly just 1. Thus 
$\mmp_{2n+1,\tau^{(4)}} = n+1$. 


\fig{P5}{The graphs $G_{n,P^{(5)}}$ and $G^+_{n,P^{(5)}}$.}


In Figure \ref{fig:P5}, we have pictured the graphs of 
$G_{6,P^{(5)}}$ and $G^+_{6,P^{(5)}}$ on the left in the second and 
third lines, respectively.
In the case of  $G^+_{n,P^{(5)}}$, it is easy to see that 
the rightmost top element $a$ must be the third element in 
the linear extension of $W_{G^+_{6,P^{(5)}}}$.  
Thus we have two linear extensions  
depending how we order the two elements connected to $a$. 
Hence $\mmp_{2n+1,P^{(5)}}=2$. 

\section{Computing $GMP_{n,\tau^{(i)}}(x)$.}

In this section, we shall study the problem of computing  
$GMP_{n,\tau^{(i)}}(x)$ for $n \geq 1$ and $i=1, \ldots, 5$. 
First it is easy to see that for any $i$, 
\begin{eqnarray*}
GMP_{1,\tau^{(i)}}(x) &=&  GMP_{2,\tau^{(i)}}(x) =  1, \\ 
GMP_{3,\tau^{(i)}}(x) &=& -1, \ \mbox{and}\\
GMP_{4,\tau^{(i)}}(x) &=& x-2.
\end{eqnarray*}
That is, there is only one generalized maximum packing of 
length 1 which consists of block of length 1 and weight 1. Similarly, 
there is only one generalized maximum packing of 
length 2 which consists of block of length 2 and weight 1. 
There is only one generalized maximum packings of length 3, namely, 
$123$ where $12$ is block of length 2 and $3$ is block of length one. 
 Thus $GMP_{3,\tau^{(i)}} = w(123) = -1$. 
There are two generalized maximum packings of length 4, namely, 
$1234$ which consists of two blocks of length 2 and has weight $-1$ and 
$\tau^{(i)}$ which consists of single block with weight $x-1$. 
Thus $GMP_{4,\tau^{(i)}} = x-2$.  

In general, we do not know how to find closed formulas 
for $GMP_{n,\tau^{(i)}}(x)$ as  function of $n$,  
but there are several cases where there are simple recursions 
for computing $GMP_{n,\tau^{(i)}}(x)$.  

The easiest case is for $\tau^{(1)} = 1324$. 
\begin{theorem} For $n \geq 3$, 
\begin{multline}\label{tau1rec}
GMP_{2n,\tau^{(1)}}(x) = \\
C_{n-1}(x-1)^{n-1} - GMP_{2n-2,\tau^{(1)}}(x) -
 \sum_{k=2}^{n-1} C_{k-1}(x-1)^{k-1}GMP_{2n-2k,\tau^{(i)}}(x) 
\end{multline}
and, for $n \geq 2$, $\displaystyle GMP_{2n+1,\tau^{(1)}}(x) =-GMP_{2n,\tau^{(1)}}(x)$.
\end{theorem}
It then follows from (\ref{eqB}) that we have the following corollary. 
\begin{corollary}
\begin{equation}
B_{\tau^{(1)}}(t,x) =\frac{t-\sum_{n \geq 1} GMP_{2n,\tau^{(1)}}(x)
\frac{t^{2n+1}}{(2n+1)!}}{1-\sum_{n\geq 1} GMP_{2n,\tau^{(1)}}(x) 
\frac{t^{2n}}{(2n)!}}.
\end{equation}
\end{corollary}

\begin{proof} 
It is easy 
to see from the form of the graphs $G_{2n,P^{(1)}}$ that any 
maximum packing $\sg \in \mathcal{MP}_{2n,\tau^{(1)}}$ must start 
with 1 and end with $2n$.  It follows that if 
$\sg = \sg_1 \ldots \sg_{2n}  \in \mathcal{GMP}_{2n,\tau^{(1)}}$ 
with block structure $B_1\ldots B_k$, then for each $i < k$, 
the elements in $B_1 \ldots B_i$ is a rearrangement of 
the elements $\{1, \ldots, \sum_{j=1}^k |B_i|\}$. That is, 
for each $1 \leq i < k$, we know that the last element   
of $B_i$ which is the largest element in $B_i$ is less than 
the first element of $B_{i+1}$ which is the smallest element 
in $B_{i+1}$. Thus all the elements of $B_i$ are smaller than 
any element in $B_{i+1}$. 

Now suppose that $n \geq 3$ and 
$\sg = \sg_1 \ldots \sg_{2n}  \in \mathcal{GMP}_{2n,\tau^{(1)}}$.
There are three possibilities.\\
\ \\
{\bf Case 1.}  $\sg$ consists of a single block.  \\
In this case $\sg$ is a maximum packing of $\tau^{(1)}$ and 
$w(\sg) = (x-1)^{n-1}$.  Since $\mmp_{2n,\tau^{(i)}} = C_{n-1}$, 
the contribution of the permutations in case 1 to 
$GMP_{2n,\tau^{(1)}}(x)$ is $C_{n-1}(x-1)^{n-1}$. \\
\ \\
{\bf Case 2.}  $\sg$ has block structure $B_1 \ldots B_s$ where 
$s \geq 2$ and $B_1$ is of length 2.  \\
In this case $B_1 =12$ and has weight $-1$ and 
$\red{B_2 \ldots B_s}$ is a generalized maximum packing for $\tau^{(1)}$ of 
length $2n-2$. Hence the contribution of the permutations in case 2 to 
$GMP_{2n,\tau^{(1)}}(x)$ is $-GMP_{2n-2,\tau^{(1)}}(x)$.\\
\ \\ 
{\bf Case 3.}  $\sg$ has block structure $B_1 \ldots B_s$ where 
$s \geq 2$ and $B_1$ has length $>2$.  \\
In this case, $B_1 =1\ldots 2k$ is a maximum packing 
for $\tau^{(1)}$ of length $2k$ for some $2 \leq k \leq n-1$ 
which has weight $-(x-1)^{k-1}$ and 
$\red{B_2 \ldots B_s}$ is a generalized maximum packing of 
length $2n-2k$. If $2 \leq k \leq n-1$, then there are $C_{k-1}$ choices 
for $B_1$. Hence the contribution of the permutations in case 2 to 
$GMP_{2n,\tau^{(1)}}(x)$ is $-\sum_{k=2}^{n-1} C_{k-1}(x-1)^{k-1}
GMP_{2n-2k,\tau^{(1)}}(x)$.\\
\ \\ 
Thus for $n \geq 3$, (\ref{tau1rec}) holds. 


It is also easy to compute 
$GMP_{2n+1,\tau^{(1)}}(x)$. That is, since 
a generalized maximum packing $\sg \in \mathcal{A}_{2n+1}$ has block 
structure $B_1 \ldots B_k$ where $B_k$ has length 1 and 
$B_1 \ldots B_{k-1}$ reduces to a generalized maximum packing 
for $\tau^{(1)}$ of length $2n$, we know that the last 
element of $B_{k-1}$ is the largest element in $B_1 \ldots B_{k-1}$ 
and hence the element in $B_k$ must be $2n+1$. Thus in this 
case $GMP_{2n+1,\tau^{(1)}}(x) = - GMP_{2n,\tau^{(1)}}(x)$.
\end{proof}



Here is list of the first few values of $GMP_{2n,\tau^{(1)}}(x)$. 
\begin{eqnarray*}
GMP_{2,\tau^{(1)}}(x) &=& 1 \\
GMP_{4,\tau^{(1)}}(x) &=& -2+x \\
GMP_{6,\tau^{(1)}}(x) &=& 5-6 x+2 x^2 \\
GMP_{8,\tau^{(1)}}(x) &=& -14+28 x-20 x^2+5 x^3 \\
GMP_{10,\tau^{(1)}}(x) &=& 42-120 x+135 x^2-70 x^3+14 x^4 \\
GMP_{12,\tau^{(1)}}(x) &=& -132+495 x-770 x^2+616 x^3-252 x^4+42 x^5 \\
GMP_{14,\tau^{(1)}}(x) &=& 429-2002 x+4004 x^2-4368 x^3+2730 x^4-924 x^5+132 x^6 \\
GMP_{16,\tau^{(1)}}(x) &=& -1430+8008 x-19656 x^2+27300 x^3-23100 x^4+\\
&&11880 x^5-3432 x^6+429 x^7 
\end{eqnarray*}


Plugging these values into the generating functions 
(\ref{eqA}) and (\ref{eqB}) and using Mathematica, we 
have computed the following table of values of 
$A_{n,\tau^{(1)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(1)}\mbox{-mch}(\sg)}$. \\
\ \\
\begin{tabular}{|l|l|}
\hline
$A_{1,\tau^{(1)}}$ & 1 \\
\hline
$A_{2,\tau^{(1)}}$ & 1 \\
\hline
$A_{3,\tau^{(1)}}$ & 2 \\
\hline
$A_{4,\tau^{(1)}}$ & $4+x$ \\
\hline
$A_{5,\tau^{(1)}}$ & $12+4 x$\\
\hline
$A_{6,\tau^{(1)}}$ & $35+24x+2x^2$ \\
\hline
$A_{7,\tau^{(1)}}$ & $142+118 x+12 x^2$ \\
\hline
$A_{8,\tau^{(1)}}$ & $546+672 x+162 x^2+5 x^3$ \\
\hline
$A_{9,\tau^{(1)}}$ & $2816+3968 x+1112 x^2+40 x^3$ \\
\hline
$A_{10,\tau^{(1)}}$ & $13482+24660 x+11145 x^2+1220 x^3+14 x^4$ \\
\hline
$A_{11,\tau^{(1)}}$ & $84764+170996 x+87200 x^2+10666 x^3+168 x^4$ \\
\hline
\end{tabular}\\
\ \\


In this case, we can find explicit generating functions 
for the number of $\sg$ in $\mathcal{A}_n$ which have no $\tau^{(1)}$-matches. 
That is, we claim that 
$G_{2m,\tau^{(1)}}(0) = (-1)^{m-1}C_m$ for $m \geq 1$.  This is clear for 
$m =1$ and $m=2$.  Now if $n > 2$ and 
we assume that $G_{2m,\tau^{(1)}}(0) = (-1)^{m-1}C_m$ for $m < n$, 
then by (\ref{tau1rec}), we have 

\begin{align*}
GMP_{2n,\tau^{(1)}}(0)  
&= C_{n-1}(-1)^{n-1} - GMP_{2n-2,\tau^{(i)}}(0) -
 \sum_{k=2}^{n-1} C_{k-1}(x-1)^{k-1}GMP_{2n-2k,\tau^{(i)}}(0)\\
&= C_{n-1}(-1)^{n-1} - (-1)^{n-2}C_{n-1} -
 \sum_{k=2}^{n-1} C_{k-1}(-1)^{k-1}(-1)^{n-k-1}C_{n-k}\\
&= (-1)^{n-1}(\sum_{k=1}^{n} C_{k-1}C_{n-k}) = (-1)^{n-1}C_n
\end{align*}

Thus if we let $N_{n,\tau^{(i)}} = A_{n,\tau^{(i)}}(0)$ be the 
number of $\sg \in \mathcal{A}_n$ with no $\tau^{(i)}$-matches, 
then by setting 
$x=0$ in (\ref{eqA}) and (\ref{eqB}) we obtain that 
\begin{equation}\label{Ntau1e}
1 + \sum_{n \geq 1} N_{2n,\tau^{(1)}} \frac{t^{2n}}{(2n)!} = 
\frac{1}{1 + \sum_{n \geq 1} (-1)^n C_n \frac{t^{2n}}{(2n)!}}
\end{equation}
and
\begin{equation}\label{Ntau1o}
\sum_{n \geq 0} N_{2n+1,\tau^{(1)}} \frac{t^{2n+1}}{(2n+1)!} = 
\frac{t+\sum_{n \geq 1} (-1)^n C_n\frac{t^{2n+1}}{(2n+1)!}}{1 + \sum_{n \geq 1} (-1)^n C_n \frac{t^{2n}}{(2n)!}}.
\end{equation}



We also claim that 
\begin{equation}
GMP_{2n,\tau^{(1)}}(x)|_{x} = (-1)^n \binom{2n}{n-2} \ \mbox{for } n \geq 2. 
\end{equation}
That is, $GMP_{4,\tau^{(1)}}(x)|_{x} =1$ so the formula holds 
for $n =2$. For $n > 2$, we have 
that 
$$GMP_{2n,\tau^{(1)}}(x) = C_{n-1}(x-1)^{n-1} - GMP_{2n2,\tau^{(1)}}(x) 
- \sum_{k=1}^{n-2} C_k (x-1)^k GMP_{2n-2k-2,\tau^{(1)}}(x).$$
Taking the coefficient of $x$ on both sides and using induction, we 
see that 
\begin{align*}
GMP_{2n,\tau^{(1)}}(x)|_x = &\frac{1}{n}\binom{2n-2}{n-1}(n-1)(-1)^{n-2} - (-1)^{n-1}\binom{2n-2}{n-3} - \\
&\sum_{k=1}^{n-2} (C_k (x-1)^k|)_x (GMP_{2n-2k-2,\tau^{(1)}}(x))|_{x^0} - \\
&\sum_{k=1}^{n-2} (C_k (x-1)^k)|_{x^0} (GMP_{2n-2k-2,\tau^{(1)}}(x))|_{x}.
\end{align*}
Since $GMP_{2,\tau^{(1)}}(x)|_x =0$, we see by induction that 
\begin{align*}
GMP_{2n,\tau^{(1)}}(x)|_x = &(-1)^n \binom{2n-2}{n-2} + (-1)^{n}\binom{2n-2}{n-3} - \\
&\sum_{k=1}^{n-2}  \frac{1}{k+1}\binom{2k}{k}k(-1)^{k-1}  
(-1)^{n-k-2}\frac{1}{n-k}\binom{2n-2k-2}{n-k-1} - \\
&\sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k}(-1)^k (-1)^{n-k-1} \binom{2n-2k-2}{n-k-3}.
\end{align*}
Observe that $\binom{2n-1}{n-2} = \binom{2n-2}{n-2} + \binom{2n-2}{n-3}$ and   
$\frac{1}{k+1}\binom{2k}{k}k =\binom{2k}{k-1}$. 
Thus if we multiply both sides of our previous equation by 
$(-1)^n$ and use these observations, we see that  
\begin{align*}
(-1)^n GMP_{2n,\tau^{(1)}}(x)|_x = &\binom{2n-1}{n-2} + 
\sum_{k=1}^{n-2}  \frac{1}{n-k} \binom{2k}{k-1}\binom{2n-2k-2}{n-k-1} + \\  
&\sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k}\binom{2n-2k-2}{n-k-3}\\
\end{align*}
Replacing $k$ by $n-k-1$ in the first sum we see that 
\begin{align*}
\sum_{k=1}^{n-2}  \frac{1}{n-k} \binom{2k}{k-1}\binom{2n-2k-2}{n-k-1} 
&= \sum_{k=1}^{n-2}  \frac{1}{k+1} \binom{2k}{k}\binom{2n-2k-2}{n-k-2} \\
&= \frac{1}{n-1}\binom{2n-4}{n-2}+\sum_{k=1}^{n-3}  \frac{1}{k+1} \binom{2k}{k}\binom{2n-2k-2}{n-k-2}.
\end{align*}
Thus we are reduced to showing that 
\begin{align*}
&\binom{2n}{n-2} = \binom{2n-1}{n-2} + \frac{1}{n-1}\binom{2n-4}{n-2} + \\ 
&\sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k} \left(\binom{2n-2k-2}{n-k-2} +
\binom{2n-2k-2}{n-k-3}\right) \\
&= \binom{2n-1}{n-2}  + \frac{1}{n-1}\binom{2n-4}{n-2} +  
\sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k} \binom{2n-2k-1}{n-k-2}.
\end{align*}
Thus to complete our induction, we need only  show that 
\begin{equation*}\label{coefxtau1}
\binom{2n-1}{n-3} = \frac{1}{n-1}\binom{2n-4}{n-2}+ 
\sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k} \binom{2n-2k-1}{n-k-2}
\end{equation*}
which can be verified by using the FullSimplify command in 
Mathematica. 









We can now use the fact that $GMP_{2n,\tau^{(1)}}(x)|_x = (-1)^n 
\binom{2n}{n-2}$ for $n \geq 2$ to compute the generating 
function of the number of $\sg \in \mathcal{A}_{n}$ with exactly one 
$\tau^{(1)}$-match. That is, let 
\begin{eqnarray*}
R(t) &=& \sum_{n \geq 1} (-1)^{n-1}C_n \frac{t^{2n}}{(2n)!}, \\
S(t) &=& \sum_{n \geq 2} (-1)^{n}\binom{2n}{n-2} \frac{t^{2n}}{(2n)!},\\
U(t) &=& \sum_{n \geq 1} (-1)^{n-1}C_n \frac{t^{2n+1}}{(2n+1)!}, 
\ \mbox{and} \\
V(t) &=& \sum_{n \geq 2} (-1)^{n}\binom{2n}{n-2} \frac{t^{2n+1}}{(2n+1)!}.
\end{eqnarray*}
Then we know that 
\begin{eqnarray*}
A_{\tau^{(1)}}(t,x) &=& \frac{1}{1 - R(t) - xS(t) + O(x^2)} \ \mbox{and} \\
B_{\tau^{(1)}}(t,x) &=& \frac{t-U(t)-xV(t) +O(x^2)}{1 - R(t) - xS(t) + O(x^2)}.
\end{eqnarray*}
It follows that 
\begin{eqnarray}
A_{\tau^{(1)}}(t,x)|_x &=&\left( 1+ \sum_{n\geq 1} (R(t) + xS(t))^n\right)|x 
= \sum_{n\geq 1} nS(t)(R(t))^{n-1} \nonumber \\
&=& S(t) \frac{d}{dt}\frac{1}{1-R(t)} = \frac{S(t)\frac{d}{dt}R(t)}{(1-R(t))^2}.
\end{eqnarray}
Similarly, one can compute that 
\begin{eqnarray}
B_{\tau^{(1)}}(t,x)|_x &=& \frac{(t -U(t)) S(t)\frac{d}{dt}R(t)}{(1-R(t))^2}
+ \frac{V(t)}{1 -R(t)} \nonumber \\
&=& \frac{V(t)(1-R(t))+ (t -U(t))S(t)\frac{d}{dt}R(t)}{(1-R(t))^2}.
\end{eqnarray}


Next we consider $GMP_{n,\tau^{(2)}}(x)$. 
\begin{theorem} For $n \geq 3$, 
\begin{equation}\label{tau2rec}
GMP_{2n,\tau^{(2)}}(x) = (x-1)^{n-1} - GMP_{2n-2,\tau^{(2)}}(x) -
\sum_{j=2}^{n-1} \binom{2n-j-1}{j-1}GMP_{2n-2j,\tau^{(2)}}(x).
\end{equation}
and, for $n \geq 2$,  $\displaystyle GMP_{2n+1,\tau^{(2)}}(x) =  -GMP_{2n,\tau^{(2)}}(x)$.
\end{theorem}
Again it follows from (\ref{eqB}) that we have the following corollary. 
\begin{corollary}  
\begin{equation}
B_{\tau^{(2)}}(t,x) =\frac{t-\sum_{n \geq 1} GMP_{2n,\tau^{(2)}}(x)
\frac{t^{2n+1}}{(2n+1)!}}{1-\sum_{n\geq 1} GMP_{2n,\tau^{(2)}}(x) 
\frac{t^{2n}}{(2n)!}}.
\end{equation}
\end{corollary}
\begin{proof}
It is clear from 
the graph $G_{n,P^{(2)}}$ that in the unique maximum 
packing $\sg = \sg_1 \ldots \sg_{2n} \in \mathcal{A}_{2n}$ for $\tau^{(2)}$,   
$\sg_2 \sg_4 \ldots \sg_{2n} = (n+1)(n+2) \ldots (2n)$ and 
$\sg_1 \sg_3 \ldots \sg_{n} = n(n-1)(n-2) \ldots 1$.
It follows that in a generalized maximum packing 
$\alpha \in S_{2n}$ with block structure $B_1 \ldots B_k$ that 
the last element of each block $B_i$ is the largest element 
in the block. Hence if $B_k$ is length two 
then, its two elements must be $(2n-1)$ and $(2n)$ since they 
must be larger than all the largest elements in each block $B_i$ 
for $i \neq k$.  
In that case $B_1 \ldots B_{k-1}$ is just a generalized 
maximum packing for $\tau^{(2)}$ of length $2n-2$ whose 
weight is $-w(\sg)$. 


If $B_k = \sg_{2n-2j+1} \ldots \sg_{2n}$ reduces to a maximum packing for $\tau^{(2)}$ of 
length $2j$ where $2 \leq j \leq n-1$, then it must be the case 
$\sg_{2n-2j+1}< \sg_{2n-2j+2} < \sg_{2n-2j+4} < \cdots < \sg_{2n}$ 
must be the $j+1$ largest elements from $\{1,\ldots, 2n\}$ since 
they will be larger than all the remaining elements of $B_k$ and larger 
than the largest element of $B_i$ for $i \neq k$. It follows 
that first element of block $B_k$ is $(2n-j)$. Our conditions for 
a generalized maximum packing for $\tau^{(2)}$ do not impose any 
relations between the remaining elements of $B_k$, 
namely $\sg_{2n-2j+3},\sg_{2n-2j+5}, \ldots , \sg_{2n-1}$, and the elements 
in blocks $B_1, \ldots, B_{k-1}$.  Thus we have 
$\binom{2n-j-1}{j-1}$ ways to choose those elements. Once we have 
chosen those elements, then $B_1 \ldots B_{k-1}$ must reduce 
to a generalized maximum packing for $\tau^{(2)}$ of length 
$2n-2j$. Thus by classifying the 
elements of $\mathcal{GMP}_{2n,\tau^{(2)}}$ by the length of the last 
block, one can prove that  (\ref{tau2rec}) holds. 

Again, it is easy to compute 
$GMP_{2n+1,\tau^{(2)}}(x)$. That is, since 
a generalized maximum packing $\sg \in \mathcal{A}_{2n+1}$ has block 
structure $B_1 \ldots B_k$ where $B_k$ has length 1 and 
$B_1 \ldots B_{k-1}$ reduces to a generalized maximum packing 
for $\tau^{(2)}$ of length $2n$, we know that the last 
element of $B_{k-1}$ is the largest element in $B_1 \ldots B_{k-1}$ 
and hence the element in $B_k$ must be $2n+1$. Thus in this 
case $GMP_{2n+1,\tau^{(2)}}(x) = - GMP_{2n,\tau^{(2)}}(x)$.
\end{proof}



Here is list of the first few values of $GMP_{2n,\tau^{(1)}}(x)$. 
\begin{eqnarray*}
GMP_{2,\tau^{(2)}}(x) &=& 1 \\
GMP_{4,\tau^{(2)}}(x) &=& x-2 \\
GMP_{6,\tau^{(2)}}(x) &=&  6-6 x+x^2\\
GMP_{8,\tau^{(2)}}(x) &=&  -23+36 x-15 x^2+x^3\\
GMP_{10,\tau^{(2)}}(x) &=&  106-229 x+160 x^2-37 x^3+x^4\\
GMP_{12,\tau^{(2)}}(x) &=&  -567+1574 x-1566 x^2+650 x^3-93 x^4+x^5\\
GMP_{14,\tau^{(2)}}(x) &=& 3434-11706 x+15248 x^2-9310 x^3+2572 x^4-
238 x^5+x^6\\
GMP_{16,\tau^{(2)}}(x) &=& -23137+93831 x-151933 x^2+123814 x^3-52136 x^4+\\
&&10175 x^5-616 x^6+x^7
\end{eqnarray*}

In this case the sequence $((-1)^{n-1}GMP_{2n,\tau^{(2)}}(0))_{n \geq 1}$ 
which 
starts out with \\
$1,2,6,23,106,567,23137, \ldots $ seems to 
be sequence A125273 in the Online Encyclopedia of Integer 
Sequences (OEIS). Unfortunately, there seems 
to be no exact formula for this sequence. 
The sequence $((-1)^{n}GMP_{2n,\tau^{(2)}}(x)|_x)_{n \geq 1}$ which 
starts out\\
 $1,6,36,1574,11706,933831, \ldots $ does 
not appear in the OEIS. 


Plugging these values into the generating functions 
(\ref{eqA}) and (\ref{eqB}) and using Mathematica, we 
have computed the following table of values of 
$A_{n,\tau^{(2)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(2)}\mbox{-mch}(\sg)}$.\\
\ \\ 
\begin{tabular}{|l|l|}
\hline
$A_{1,\tau^{(2)}}$ & 1 \\
\hline
$A_{2,\tau^{(2)}}$ & 1 \\
\hline
$A_{3,\tau^{(2)}}$ & 2 \\
\hline
$A_{4,\tau^{(2)}}$ & $4+x$ \\
\hline
$A_{5,\tau^{(2)}}$ & $12+4 x$\\
\hline
$A_{6,\tau^{(2)}}$ & $36+24x+x^2$ \\
\hline
$A_{7,\tau^{(2)}}$ & $148+118 x+6 x^2$\\
\hline
$A_{8,\tau^{(2)}}$ & $593+680 x+111 x^2+x^3$ \\
\hline
$A_{9,\tau^{(2)}}$ & $3128+4032 x+768 x^2+8 x^3$ \\
\hline
$A_{10,\tau^{(2)}}$ &  $15676+25691 x+8680 x^2+473 x^3+x^4$ \\
\hline
$A_{11,\tau^{(2)}}$ & $101094+180134 x+68326 x^2+4228 x^3+10 x^4$ \\
\hline
\end{tabular}\\
\ \\




Next we consider $GMP_{2n,\tau^{(4)}}(x)$. 
\begin{theorem} For $n \geq 3$, 
\begin{equation}\label{tau4rec}
GMP_{2n,\tau^{(4)}}(x) = (x-1)^{n-1} - GMP_{2n-2,\tau^{(4)}}(x) -
\sum_{j=2}^{n-1} \binom{2n-j-1}{j-1}GMP_{2n-2j,\tau^{(4)}}(x) 
\end{equation}
and, for $n \geq 2$, 
\begin{multline}\label{tau4reco}
GMP_{2n+1,\tau^{(4)}}(x) = \\
-n(x-1)^{n-1} - GMP_{2n-1,\tau^{(4)}}(x) -
\sum_{j=2}^{n-1} \binom{2n-j}{j-1}GMP_{2n+1-2j,\tau^{(4)}}(x).
\end{multline}
\end{theorem} 
\begin{proof} 
It is clear from 
the graph $G_{n,P^{(4)}}$ that in the unique maximum 
packing $\sg = \sg_1 \ldots \sg_{2n} \in \mathcal{A}_{2n}$ for $\tau^{(4)}$, 
$\sg_2 \sg_4 \ldots \sg_{2n} = (2n) (2n-1) \ldots (n+1)$ and 
$\sg_1 \sg_3 \ldots \sg_{2n-1} = 12 \ldots n$.
It follows that in a generalized maximum packing 
$\alpha \in S_{2n}$ with block structure $B_1 \ldots B_k$ that 
the first element of each block $B_i$ is the smallest element 
in the block. Hence if $B_1$ is length two 
then, its two elements must be $1$ and $2$ since they 
must be smaller than all the smallest elements in each block $B_i$ 
for $i > 1$. 
In that case $B_2 \ldots B_{k}$ is just a generalized 
maximum packing for $\tau^{(4)}$ of length $2n-2$ whose 
weight is $-w(\sg)$. 


If $B_1 = \sg_{1} \ldots \sg_{2j}$ reduces to a maximum packing for 
$\tau^{(4)}$ of 
length $2j$ where $2 \leq j \leq n-1$, then it must be the case 
$\sg_{1}< \sg_{3} < \sg_{5} < \cdots < \sg_{2j-1} < \sg_{2j}$ 
must be the $j+1$ smallest elements from $\{1,\ldots, 2n\}$ since 
they will be smaller that all the remaining elements of $B_1$ and smaller 
than the smallest element of $B_i$ for $i >1$. It follows 
that the last element of block $B_1$ is $(j+1)$. Our definitions for 
a generalized maximum packing for $\tau^{(4)}$ do not impose any 
relations between the remaining elements of $B_1$, 
namely $\sg_{2},\sg_{4}, \ldots , \sg_{2j-2}$, and the elements 
in blocks $B_2, \ldots, B_{k}$.  Thus we have 
$\binom{2n-j-1}{j-1}$ ways to  choose those elements. Once we have 
chosen those elements, then $B_2 \ldots B_{k}$ must reduce 
to a generalized maximum packing for $\tau^{(4)}$ of length 
$2n-2j$. Thus by classifying the 
elements of $\mathcal{GMP}_{2n,\tau^{(4)}}$ by the length of the first
block, we see that for $n \geq 3$, (\ref{tau4rec}) holds. 

This is the same recursion as (\ref{tau2rec}) and it 
implies that $A_{\tau^{(2)}}(t,x) = A_{\tau^{(4)}}(t,x)$. 
This is no surprise since even length up-down permutations 
are closed under reverse complement.  That is, 
if $\sg = \sg_1 \ldots \sg_n \in S_n$, then 
the reverse of $\sg$, $\sg^r$, is defined to be 
$\sg^r = \sg_n \ldots \sg_1$ and the 
complement of $\sg$, $\sg^c$, is defined by $\sg^c = (n+1-\sg_1) \ldots (n+1-\sg_n)$.  The reverse-complement of $\sg$ is $(\sg^r)^c$.  It 
is easy to check that $\sg \in \mathcal{A}_{2n}$ if and only if $(\sg^r)^c \in \mathcal{A}_{2n}$ 
and that $(2314^r)^c = 1423$.  Thus the map which send 
$\sg \in \mathcal{A}_{2n}$ to $(\sg^r)^c$ shows that 
$A_{\tau^{(2)}}(t,x) = A_{\tau^{(4)}}(t,x)$.

It is not the case that $B_{\tau^{(2)}}(t,x) = B_{\tau^{(4)}}(t,x)$ 
since for $n \geq 2$, 
the number of maximum packings for $\tau^{(2)}$ of length $2n+1$ is 
$2n$ while 
the number of maximum packings for $\tau^{(4)}$ of length $2n+1$ is $(n+1)$.
Nevertheless, we can still develop a recursion for 
$GMP_{2n+1,\tau^{(4)}}(x)$ for $n \geq 2$. That is, since 
any generalized maximum packing for $\tau^{(4)}$ of length 
$2n+1$ has block structure $B_1 \ldots B_k$ where $B_k$ has 
length 1 and $B_1 \ldots B_{k-1}$ reduces to a generalized maximum packing for $\tau^{(4)}$ of length 
$2n$, it will still be the case that the first element in 
each block is the smallest element. 

Hence if $B_1$ is length two 
then, its two elements must be $1$ and $2$ since they 
must be smaller than all the smallest elements in each block $B_i$. 
In that case $B_2 \ldots B_{k}$ is just a generalized 
maximum packing for $\tau^{(4)}$ of length $2n-1$ whose 
weight is $-w(\sg)$. 

If $B_1 = \sg_{1} \ldots \sg_{2j}$ reduces to a maximum packing for 
$\tau^{(4)}$ of 
length $2j$ where $2 \leq j \leq n-1$, then it will still 
be the case that 
$\sg_{1}< \sg_{3} < \sg_{5} < \cdots < \sg_{2j-1} < \sg_{2j}$ 
are the $j+1$ smallest elements from $\{1,\ldots, 2n\}$ and the 
last element of $B_1$ is $j+1$. If $j =n$, then 
it is easy to see that we have $n$ choices of $\sg_{2n+1}$ and 
once we choose $\sg_{2n+1}$, then the order of the rest of 
the elements are completely determined.  Thus generalized 
maximum packings for $\tau^{(4)}$ which have two blocks 
$B_1B_2$ contribute a weight of $-n(x-1)^{n-1}$ to 
$GMP_{2n+1,\tau^{(4)}}$. 
If $2 \leq j \leq n-1$, then 
our definitions for   
a generalized maximum packing for $\tau^{(4)}$ do not impose any 
relations between the remaining elements of $B_1$, 
namely $\sg_{2},\sg_{4}, \ldots , \sg_{2j-2}$, and the elements 
in blocks $B_2, \ldots, B_{k}$.  Thus we have 
$\binom{2n-j}{j-1}$ ways those choose those elements. Once we have 
chosen those elements, then $B_2 \ldots B_{k}$ must reduce 
to a generalized maximum packing for $\tau^{(4)}$ of length 
$2n+1-2j$. Thus by classifying the 
elements of $\mathcal{GMP}_{2n+1,\tau^{(4)}}$ by the length of the first
block, we see that for $n \geq 2$ (\ref{tau4reco}) holds.
\end{proof}


Here is list of the first few values of $GMP_{2n+1,\tau^{(4)}}(x)$. 
\begin{eqnarray*}
GMP_{1,\tau^{(4)}}(x) &=& 1 \\
GMP_{3,\tau^{(4)}}(x) &=& -1 \\
GMP_{5,\tau^{(4)}}(x) &=& 3-2 x \\
GMP_{7,\tau^{(4)}}(x) &=&  -10+12 x-3 x^2\\
GMP_{9,\tau^{(4)}}(x) &=&  42-74 x+37 x^2-4 x^3\\
GMP_{11,\tau^{(4)}}(x) &=&  -210+498 x-394 x^2+110 x^3-5 x^4\\
GMP_{13,\tau^{(4)}}(x) &=& 1199-3596 x+3946 x^2-1872 x^3+330 x^4-6 x^5\\
GMP_{15,\tau^{(4)}}(x) &=&  -7670+27908 x-39356 x^2+26604 x^3-8476 x^4+996 x^5-7 x^6
\end{eqnarray*}

In this case, the sequence $\{GMP_{2n+1,\tau^{(4)}}(0)\}_{n \geq 0}$
seems to be sequence A125274 in the OEIS. Unfortunately, 
there is no exact formulas for the elements in this sequence. 



Plugging these values into the generating functions 
(\ref{eqA}) and (\ref{eqB}) and using Mathematica, we 
have computed the following table of values of 
$A_{n,\tau^{(4)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(4)}\mbox{-mch}(\sg)}$.\\ 
\ \\
\begin{tabular}{|l|l|}
\hline
$A_{1,\tau^{(4)}}$ & 1 \\
\hline
$A_{2,\tau^{(4)}}$ & 1 \\
\hline
$A_{3,\tau^{(4)}}$ & 2 \\
\hline
$A_{4,\tau^{(4)}}$ & $4+x$ \\
\hline
$A_{5,\tau^{(4)}}$ & $13+3 x$\\
\hline
$A_{6,\tau^{(4)}}$ & $36+24x+x^2$ \\
\hline
$A_{7,\tau^{(4)}}$ & $165+103 x+4 x^2$\\
\hline
$A_{8,\tau^{(4)}}$ & $593+680 x+111 x^2+x^3$ \\
\hline
$A_{9,\tau^{(4)}}$ & $3507+3832 x+592 x^2+5 x^3$ \\
\hline
$A_{10,\tau^{(4)}}$ &  $15676+25691 x+8680 x^2+473 x^3+x^4$ \\
\hline
$A_{11,\tau^{(4)}}$ &  $113387+179369 x+58016 x^2+3014 x^3+6 x^4$\\
\hline
\end{tabular}\\
\ \\

The key to our ability to develop recursions for $GMP_{n,\tau^{(i)}}(x)$ in 
the case where $i \in \{1,2,4\}$ is due to the fact that  
$\tau^{(1)}$, $\tau^{(2)}$, and $\tau^{(4)}$ either start with 1 or 
end with 4. This allowed us to develop recursions based on either 
length of the first block or the length of the last block in a 
generalized maximum packing. 
Neither $\tau^{(3)} = 2413$ nor $\tau^{(5)} = 3412$ 
start with 1 or end with 4 so that we have not been 
able to find any simple recursions for $GMP_{n,\tau^{(3)}}$ or 
$GMP_{n,\tau^{(5)}}$.  


J. Harmse \cite{Harmse} computed the following initial values 
of $GMP_{n,\tau^{(3)}}$ and $GMP_{n,\tau^{(5)}}$ by computing 
the number of linear extension of the posets associated 
with the various block structures of generalized maximal 
packings. 



Here is list of the first few values of $GMP_{2n,\tau^{(3)}}(x)$. 
\begin{eqnarray*}
GMP_{1,\tau^{(3)}}(x) &=& 1 \\
GMP_{2,\tau^{(3)}}(x) &=& 1 \\
GMP_{3,\tau^{(3)}}(x) &=& -1 \\
GMP_{4,\tau^{(3)}}(x) &=& -2+x \\
GMP_{5,\tau^{(3)}}(x) &=& 3-2x \\
GMP_{6,\tau^{(3)}}(x) &=& 9-10 x+2 x^2 \\
GMP_{7,\tau^{(3)}}(x) &=& -18+24x-7x^2 \\
GMP_{8,\tau^{(3)}}(x) &=& -74+132 x-64 x^2+5 x^3 \\
GMP_{9,\tau^{(3)}}(x) &=&  190-376x+213x^2-26x^3\\
GMP_{10,\tau^{(3)}}(x) &=& 974-2394 x+1927 x^2-520 x^3+14 x^4 \\
GMP_{11,\tau^{(3)}}(x) &=&-3078+8180x-7287x^2+2282x^3-98x^4  \\
GMP_{12,\tau^{(3)}}(x) &=& -17688+54228 x-59393 x^2+26807 x^3-3997 x^4+42 x^5 
\end{eqnarray*}


Plugging these values into the generating functions 
(\ref{eqA}) and (\ref{eqB}) and using Mathematica, we 
have computed the following table of values of 
$A_{n,\tau^{(3)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(3)}\mbox{-mch}(\sg)}$. \\
\ \\
\begin{tabular}{|l|l|}
\hline
$A_{1,\tau^{(3)}}$ & 1 \\
\hline
$A_{2,\tau^{(3)}}$ & 1 \\
\hline
$A_{3,\tau^{(3)}}$ & 2 \\
\hline
$A_{4,\tau^{(3)}}$ & $4+x$ \\
\hline
$A_{5,\tau^{(3)}}$ & $13+3x$\\
\hline
$A_{6,\tau^{(3)}}$ & $39+20x+2x^2$ \\
\hline
$A_{7,\tau^{(3)}}$ & $178+87x+7x^2$ \\
\hline
$A_{8,\tau^{(3)}}$ & $710+552 x+118 x^2+5 x^3$ \\
\hline
$A_{9,\tau^{(3)}}$ & $4168+3146x+603x^2+19x^3$ \\
\hline
$A_{10,\tau^{(3)}}$ & $29774+21666 x+5370 x^2+2697 x^3+14 x^4$ \\
\hline
$A_{11,\tau^{(3)}}$ & $149030+152170x+27000x2+25536x^3+56x^4$ \\
\hline
\end{tabular}\\
\ \\
\ \\
Here is list of the first few values of $GMP_{2n,\tau^{(5)}}(x)$. 
\begin{eqnarray*}
GMP_{1,\tau^{(5)}}(x) &=& 1 \\
GMP_{2,\tau^{(5)}}(x) &=& 1 \\
GMP_{3,\tau^{(5)}}(x) &=& -1 \\
GMP_{4,\tau^{(5)}}(x) &=& -2+x \\
GMP_{5,\tau^{(5)}}(x) &=& 4-3x \\
GMP_{6,\tau^{(5)}}(x) &=& 14-14 x+ x^2 \\
GMP_{7,\tau^{(5)}}(x) &=& -39+44x-6x^2 \\
GMP_{8,\tau^{(5)}}(x) &=& -168+252 x-86 x^2+x^3 \\
GMP_{9,\tau^{(5)}}(x) &=&  594-1002+416x^2-7x^3\\
GMP_{10,\tau^{(5)}}(x) &=& 3352-6704 x+3782 x^2-430 x^3+ x^4 \\
GMP_{11,\tau^{(5)}}(x) &=& -13814+30264x-19404x^2=2962x^3-9x^4 \\
GMP_{12,\tau^{(5)}}(x) &=& -91038+224751 x-180196 x^2+48387 x^3-1906 x^4+x^5 \\
\end{eqnarray*}


Plugging these values into the generating functions 
(\ref{eqA}) and (\ref{eqB}) and using Mathematica, we 
have computed the following table of values of 
$A_{n,\tau^{(5)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(5)}\mbox{-mch}(\sg)}$. \\
\ \\
\begin{tabular}{|l|l|}
\hline
$A_{1,\tau^{(5)}}$ & 1 \\
\hline
$A_{2,\tau^{(5)}}$ & 1 \\
\hline
$A_{3,\tau^{(5)}}$ & 2 \\
\hline
$A_{4,\tau^{(5)}}$ & $4+x$ \\
\hline
$A_{5,\tau^{(5)}}$ & $14+2x$\\
\hline
$A_{6,\tau^{(5)}}$ & $44+16x+x^2$ \\
\hline
$A_{7,\tau^{(5)}}$ & $214_56x+2x^2$ \\
\hline
$A_{8,\tau^{(5)}}$ & $896+448 x+40 x^2+x^3$ \\
\hline
$A_{9,\tau^{(5)}}$ & $5610+2190x+134x^2+2x^3$ \\
\hline
$A_{10,\tau^{(5)}}$ & $29392+18496 x+ 2552x^2+80x^3+x^4$ \\
\hline
$A_{11,\tau^{(5)}}$ & $224878+116776x+11880x^2+256x^3+2x^4$ \\
\hline
\end{tabular}\\
\ \\


\section{Double rise pairs and double descent pairs.}


Suppose that $\sg = \sg_1 \ldots \sg_{n} \in \mathcal{A}_{n}$. 
Then we say that $(2i-1)(2i)$ is 
a double rise (double descent) pair in $\sg$ if 
both $\sg_{2i-1}< \sg_{2i+1}$ and $\sg_{2i} < \sg_{2i+2}$ ($\sg_{2i-1}> \sg_{2i+1}$ and $\sg_{2i} > \sg_{2i+2}$). 
It is easy to see that $(2i-1)(2i)$ is 
a double rise pair 
if and only if $\red{\sg_{2i-1}\sg_{2i}\sg_{2i+1}\sg_{2i+2}}=
1324$ so that the number of double rise pairs in $\sg$ is just 
the number of $1324$-matches in $\sg$. Similarly, is $(2i-1)(2i)$ is 
a double descent pair 
if and only if $\red{\sg_{2i-1}\sg_{2i}\sg_{2i+1}\sg_{2i+2}}
\in \{3412,2413\}$ so that if $D = \{3412,2413\}$, then 
the number of double descents pairs in $\sg$ is just 
the number of $D$-matches in $\sg$. 


In general, if $\Upsilon \subseteq \mathcal{A}_4$, we say that 
$\sg \in \mathcal{A}_{2n}$ is  a maximum packing for $\Upsilon$ if 
$\umch{\sg} = n-1$.  We say that $\sg \in S_{2n}$ is a {\em generalized maximum packing 
for $\Upsilon$} if we can break $\sg$ into consecutive blocks  
$\sg = B_1 \ldots B_k$ such that 
\begin{enumerate}
\item for all $1 \leq j \leq k$, 
$B_j$ is either an increasing sequence of length 2 or $\red{B_j}$ is 
maximum packing for $\Upsilon$ of length $2s$ for some $s \geq 2$ and 
\item for all $1 \leq j \leq k-1$, the last element of 
$B_j$ is less than the first element of $B_{j+1}$. 
\end{enumerate}
Similarly, we say that 
$\sg \in \mathcal{A}_{2n+1}$ is  a maximum packing for $\Upsilon$ if 
$\umch{\sg} = n-1$.  We say that $\sg \in S_{2n+1}$ is a {\em generalized maximum packing 
for $\Upsilon$} if we can break $\sg$ into consecutive blocks  
$\sg = B_1 \ldots B_k$ such that 
\begin{enumerate}
\item for all $1 \leq j < k$, 
$B_j$ is either an increasing sequence of length 2 or $\red{B_j}$ is 
maximum packing for $\Upsilon$ of length $2s$ for some $s \geq 2$,
\item $B_k$ is block of length 1, 
 and 
\item for all $1 \leq j \leq k-1$, the last element of 
$B_j$ is less than the first element of $B_{j+1}$. 
\end{enumerate}
Then we can define the generalized maximum packing polynomials
$GMP_{2n,\Upsilon}(x)$ and $GMP_{2n+1,\Upsilon}(x)$ in the 
same manner
 that we defined $GMP_{2n,\tau^{(i)}}(x)$ and $GMP_{2n+1,\tau^{(i))}}(x)$.


We then have the following theorem. 
\begin{theorem}\label{thm:mainu}
Let $\Upsilon \subseteq \mathcal{A}_4$. Then 
\begin{eqnarray*}\label{eqAu}
A_{\Upsilon}(t,x) &=& 1+ \sum_{n \geq 1} \frac{t^{2n}}{(2n)!} \sum_{\sg \in \mathcal{A}_{2n}} x^{\umch{\sg}}\\
&=&\frac{1}{1-\sum_{n\geq 1} GMP_{2n,\Upsilon}(x) \frac{t^{2n}}{(2n)!}} 
\end{eqnarray*}
and
\begin{eqnarray*}\label{eqBu}
B_{\Upsilon}(t,x) &=& \sum_{n \geq 1} \frac{t^{2n-1}}{(2n-1)!} \sum_{\sg \in \mathcal{A}_{2n-1}} x^{\umch{\sg}}\\
&=&\frac{\sum_{n \geq 1} GMP_{2n-1,\Upsilon}(x)
\frac{t^{2n-1}}{(2n-1)!}}{1-\sum_{n\geq 1} GMP_{2n,\Upsilon}(x) 
\frac{t^{2n}}{(2n)!}}.
\end{eqnarray*}
\end{theorem}
That is, if $\Upsilon \subseteq \mathcal{A}_4$, 
the proof of Theorem \ref{thm:main} goes through without 
change if we replace maximum packings for $\tau^{(i)}$ with 
maximum packings for $\Upsilon$ and generalized maximum 
packings for $\tau^{(i)}$ by generalized maximum packings 
for $\Upsilon$ throughout the proof. 

Thus if we can compute $GMP_{n,D}(x)$, we would have the generating 
function for the distribution of double descents in $\mathcal{A}_n$. 
We can compute $\mmp_{2n,D}$ and $\mmp_{2n+1,D}$. That is, we 
have the following theorem. 
\begin{theorem} For all $n \geq 1$, $\displaystyle 
\mmp_{2n,D} =  C_n \ \mbox{and} \ 
\mmp_{2n+1,D} = C_{n+1}$.
\end{theorem}
\begin{proof}
It is easy to see that 
$\mmp_{2n,D}$ equals the number of $F \in \mathcal{F}_{2,n}$ such 
that for each $i <n$, there is either a $P^{(2)}$-match or a 
$P^{(5)}$-match starting in column $i$.  Let 
the reverse of $F$ equal $F^r$ where the first row of 
$F^r$ is $F(1,n), F(1,n-1) \ldots, F(1,1)$ reading from left to right 
and the second row of $F^r$ is 
$F(2,n), F(2,n-1) \ldots, F(2,1)$ reading from left to right.
For example, 
$$(P^{(3)})^r  = P^{(1)} = \begin{array}{|c|c|}
 \hline 3 & 4 \\
 \hline 1 & 2 \\
 \hline
 \end{array} \ \mbox{and} \ (P^{(5)})^r   = \begin{array}{|c|c|}
 \hline 2 & 4 \\
 \hline 1 & 3 \\
 \hline
 \end{array}.$$
It is easy to see that  $F \in \mathcal{F}_{2,n}$ has the property  
that for each $i <n$, there is either a $P^{(2)}$-match or a 
$P^{(5)}$-match  starting at column $i$ if and only if 
$F^r \in \mathcal{F}_{2,n}$ 
has the property  
that for each $i <n$, there is either a $(P^{(2)})^r$-match or a 
$(P^{(5)})^r$-match starting at column $i$. 
But note that   $(P^{(3)})^r$ and $(P^{(5)})^r$ are the two 
standard tableaux of shape (2,2). Thus $F^r$  
has the property  
that for each $i <n$, there is either a $(P^{(2)})^r$-match or a 
$(P^{(5)})^r$-match starting at column $i$ if and only if 
$F^r$ is standard tableau of shape $(n,n)$. But it follows 
from the Frame-Robinson-Thrall hook formula \cite{FRT} for the number of 
standard tableaux of a given shape $\lambda$  that the 
number of standard tableaux of shape $(n,n)$ is the Catalan number $C_n$. 
Thus $\mmp_{2n,u} = C_n$.

It follows that there is a graph $G_D$ associated with $D$ which 
consists of the graph pictured on the right in the first line 
of Figure \ref{fig:U}. Then we can construct graphs 
$G_{D,n}$ and $G^+_{D,n}$ using $G_D$ in the same way 
that we constructed graphs $G_{n,P^{(i)}}$ and $G^+_{n,P^{(i)}}$ 
from $G_{P^{(i)}}$. For example, the graphs 
$G_{D,6}$ and $G^+_{D,6}$ are pictured on line 2 of Figure \ref{fig:U}. 
Then $\mmp_{2n,D}$ is the number of linear extensions of the poset 
determined by $G_{n,D}$ and $\mmp_{2n+1,D}$ is the number of 
linear extensions of the poset determined by $G^+_{n,D}$. 

\fig{U}{The graphs $G_{n,D}$ and $G^+_{n,D}$.}


We claim 
that the number of linear extensions of the poset determined by $G^+_{n,D}$
is just $C_{n+1}$.
Note that in $G_{n,D}$, the element in bottom right-hand corner 
must be the first element in any linear extension of the poset 
determined by $G_{n,D}$.  Now create a new graph $G^{++}_{n,D}$
by adding a new element 0 and new directed edges 
connecting 0 to the element in the bottom 
right hand corner of $G^+_{n,D}$ 
and 0 to $b$  to form a graph $G^{++}_{n,D}$.  It is 
easy to see that  the number of linear extensions of the poset determined by $G^+_{n,D}$ is equal to the number of linear extensions of the poset determined by $G^{++}_{n,D}$. However the number of linear extensions of the poset determined by $G^{++}_{n,D}$ is just the number of linear extensions of 
the poset determined by $G_{n+1,D}$ which is $C_{n+1}$. 
\end{proof}


Unfortunately elements of $\mathcal{MP}_{2n,D}$ do not end in 1 or 
$2n$ so that there does not seem to be any way to develop simple 
recursions for $GMP_{2n,D}(x)$ or $GMP_{2n+1,D}(x)$.  
Nevertheless, J. Harmse \cite{Harmse} computed the following  initial values.  
of $GMP_{n,D}(x)$
\begin{eqnarray*}
GMP_{1,D}(x) &=& 1\\
GMP_{2,D}(x) &=& 1\\
GMP_{3,D}(x) &=& -1\\
GMP_{4,D}(x) &=& 2x-3\\
GMP_{5,D}(x) &=& 6-5x\\
GMP_{6,D}(x) &=& 24-28x+5x^2\\
GMP_{7,D}(x) &=& -64+84x-21x^2\\
GMP_{8,D}(x) &=& -369+648x-294x^2+14x^3\\
GMP_{9,D}(x) &=& 1288-2439x+1236x^2-84x^3\\
GMP_{10,D}(x) &=& 8970-20792 x+15189 x^2-3408 x^3+42 x^4\\
GMP_{11,D}(x) &=&  -31121+73723 x-54978 x^2+12705 x^3-330 x^4\\
GMP_{12,D}(x) &=& -323736+933223 x-937838 x^2+369138 x^3-40920 x^4+132 x^5\\
\end{eqnarray*}


Plugging these values into the generating functions 
(\ref{eqAu}) and (\ref{eqBu}) and using Mathematica, we 
have computed the following table of values of 
$A_{n,D}(x) = \sum_{\sg \in \mathcal{A}_n} x^{D\mbox{-mch}(\sg)}$. \\
\ \\
\begin{tabular}{|l|l|}
\hline
$A_{1,D}$ & 1 \\
\hline
$A_{2,D}$ & 1 \\
\hline
$A_{3,D}$ & 2 \\
\hline
$A_{4,D}$ & $3+2x$ \\
\hline
$A_{5,D}$ & $11+5 x$\\
\hline
$A_{6,D}$ & $24+32 x+5 x^2$ \\
\hline
f$A_{7,D}$ & $125+133 x+14 x^2$ \\
\hline
$A_{8,D}$ & $345+760 x+266 x^2+14 x^3$ \\
\hline
$A_{9,D}$ & $1341+4359 x+1194 x^2+42 x^3$ \\
\hline
$A_{10,D}$ & $7890+24928 x+15609 x^2+2052 x^3+42 x^4$ \\
\hline
$A_{11,D}$ & $17752+162570 x+115401 x^2+2937 x^3+132 x^4$ \\
\hline
\end{tabular}\\
\ \\


Adrian Duane,  in his 
Ph.D. thesis \cite{Duane}, 
showed that the techniques that we have developed in this paper can be 
extended to find generating functions for the distribution of the 
number of $\tau$-matches in $\mathcal{A}_n$ where $\tau \in \mathcal{A}_{2j}$ 
is an up-down minimal overlapping 
permutation. Here $\tau \in \mathcal{A}_{2j}$ is said to be an 
 up-down  minimal overlapping permutation  if the smallest $i$ such that there exists a $\sg \in \mathcal{A}_{2i}$ such 
that $\tmch{\sg}=2$ is $4j-2$.  
 Also the techniques that we have developed in this paper can be 
generalized to find to generating functions for the distribution of 
the number of 
consecutive matches in generalized $k$-Euler permutations. That is, 
let $E^{(k)}_n = \{ \sg \in S_n: Des(\sg)  = 
\{kj: j \geq 1\} \cap [n-1]\}$. In particular, we can generalize the results 
of this paper to study the distribution of $\tau$-matches 
in $E^{(k)}_n$ where $\tau \in E^{(k)}_{2k}$.  




\begin{thebibliography}{20}


\bibitem{BeckRem} 
D.A. Beck and J.B. Remmel, Permutation enumeration of the 
symmetric group and the combinatorics of symmetric functions, 
J. of Combinatorial Theory(A) {\bf 72}, (1995), 1-49. 


\bibitem{br}
D. Beck, J. Remmel, and T. Whitehead, The combinatorics of
transition matrices between the bases of the symmetric functions and
the $B_n$ analogues, Discrete Math. \textbf{153}
(1996), 3--27.


\bibitem{b} F. Brenti, Permutation enumeration, symmetric
functions, and unimodality, Pacific J. Math. \textbf{157}
(1993), 1--28.

\bibitem{b2} F. Brenti, A class of $q$-symmetric functions arising from
plethysm, J. Combinatorial Theory (A), \textbf{91} (2000), 137--170.


\bibitem{carlitz1} L. Carlitz, Enumeration of up-down permutations by 
the number of rises, Pacific J. Math., {\bf 45} (1973), 49-59.

\bibitem{carlitz2} L. Carlitz and R. Scoville, Enumeration 
of up-down permutations by upper records, Monatsh. Math., {\bf 79} (1975), 
3-12. 

\bibitem{Duane} A. S. Duane, Pattern matching statistics in 
the permutations $S_n$ and the alternating permutations $A_n$ for minimally overlapping patterns, Ph.D. Thesis, University of California, San Diego, (2013). 



\bibitem{ER} \"O. E\~gecio\~glu and J. Remmel, Brick tabloids and connection matrices between bases of symmetric functions, Discrete Applied Math.
{\bf 34} (1991), 107--120.


\bibitem{FRT} J.S. Frame, G. De B. Robinson, and R.M. Thrall, 
The hook graphs of the symmetric group, Canad. J. Math., (1954), 316-324.




\bibitem{GJ} I.P. Goulden and D.M. Jackson, \emph{Combinatorial Enumeration},
A Wiley-Interscience Series in Discrete Mathematics, John Wiley \& Sons Inc,
New York, (1983).

\bibitem{Harmse} J. Harmse, private communication (2012).


\bibitem{HR} J. Harmse and J.B. Remmel, Patterns in column strict fillings 
of rectangular arrays, Pure Math. and Applications, {\bf 22} (2011), 131-171.



\bibitem{hong} G. Hong, Catalan numbers in pattern-avoiding permutations, 
MIT Undergraduate J. Mathematics, {\bf 10} (2008), 53-68.






\bibitem{KNRR} S. Kitaev, A. Niedermaier, J.B. Remmel, and A. Riehl,
Generalized pattern matching conditions for $C_k \wr S_n$, ISRN Combinatorics, 
{\bf 2013}, Article ID634823 (2013), 21. pgs. 


\bibitem{L} T.M. Langley, Alternative transition matrices for Brenti's q-symmetric functions and a class of $q,t$-symmetric functions on the hyperoctahedral group, Proceedings of the 2002 Conference on Formal Power Series and Algebraic Combinatorics, Melbourne Australia.


\bibitem{LR} T.M. Langley and J.B. Remmel,
Enumeration of $m$-tuples of permuations and a new class of
power bases for the space of symmetric functions, Advances in App.
Math. {\bf 36} (2006), 30--66.

\bibitem{lewis} J.B. Lewis, Pattern avoidance in alternating permutations 
and tableaux, Discrete Math. and Theoretical Comp. Sci, proc. {\bf AN} 
(2010), 259-270.



\bibitem{mansour} T. Mansour,  Restricted 132-alternating permutations and Chebyshev polynomials, Annals of Combinatorics, {\bf 7} (2003), 201-227.

\bibitem{mansour2} T. Mansour and A. Robertson, Refined restricted 
permutations avoiding subsets of patterns of length 3, Annals of Combinatorics, {\bf 7} (2002), 407-418.



\bibitem{MendesTh} A. Mendes, Building generating functions brick by brick, 
Ph.D. thesis, University of California, San Diego, (2004). 



\bibitem{MenRem1} A. Mendes and J.B. Remmel, Permutations and words counted
by consecutive patterns, Advances Appl.
Math., {\bf 37}(4), (2006), 443-480.

\bibitem{MenRem2}
A. Mendes and J. Remmel, Generating functions for statistics
on $C\sb k\wr S\sb n$, S\'em. Lothar. Comb. \textbf{54A}: Article 
  B54At, (2005/07).


\bibitem{Book} A. Mendes and J.B. Remmel, Generating Functions from
Symmetric Functions, preprint.

\bibitem{MRR} A. Mendes, J.B. Remmel, and A. Riehl, Permutations with $k$-regular descent patterns, \emph{Permutation Patterns}, (S. Linton, N. Ru\u{s}kuc, V. 
Vatter, eds.), London. Math. Soc. Lecture Notes 376, (2010), 259-286.


\bibitem{RRW}  D. Ram, J.B. Remmel, and T. Whitehead, Combinatorics of the $q$-basis of symmetric functions, J. Comb. Th. Series A,
\textbf{76}(2) (1996), 231--271.



\bibitem{Wag} J. D. Wagner, The permutation enumeration of
wreath products and cyclic and symmetric groups, Advances in Appl.
Math., {\bf 30} (2003), 343--368.

\bibitem{StCat} R.P. Stanley, Catalan addendum to Enumerative Combinatorics,
Available online at www-math.mit.edu/~rstan/ec/catadd.pdf, (2009). 

\end{thebibliography}







\end{document}
