\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 the five up-down permutations of length four, 
$1324$, $2314$, $2413$, 
$1432$, and $3412$, in the set of up-down permutations. We show 
that for any such $\tau$, 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$. For example, 
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 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 [27, 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}$ that 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*}
In fact, the main ideas of this paper can be extended 
to study the distributions of $\tau$-matches in the set of up-down 
permutations where $\tau$ is a natural analogue of 
a minimal overlapping permutation 
as studied by Duane and Remmel \cite{DR}. This work appears in 
Duane's thesis \cite{Duane}. We have chosen to focus 
on the five up-down permutations of length four because the 
arguments are simpler and the formulas are more tractable than 
in the general case considered in Duane's thesis. However such 
an extension will be the subject of a forthcoming paper. 
 

Let $\tau \in \mathcal{A}_4$. If $\sg \in \mathcal{A}_n$ where $n \geq 4$, 
then $\tau$-matches can only start 
at odd positions. If $\sg \in \mathcal{A}_{2n}$ and $\tau\mbox{-mch}(\sg) = n-1$, 
then we say that $\sg$ is a {\em maximum packing for 
$\tau$}. Thus if $\sg \in \mathcal{A}_{2n}$ is a maximum packing 
for $\tau$, then $\sg$ has $\tau$-matches starting 
at positions $1,3,\ldots,2n-3$. We let $\mathcal{MP}_{2n,\tau}$ denote 
the set of maximum packings for $\tau$ in $\mathcal{A}_{2n}$ and we let 
$\mmp_{2n,\tau} = |\mathcal{MP}_{2n,\tau}|$.  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)}$. 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 
a 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 $(x-1)^s$ if $B_j$ has length $2s+2$ where 
$s \geq 0$. Thus if $B_i$ is a block of length 2, then $w(B_i) =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 a 
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 let $w(B_k) =1$ and, for $j <k$, 
we let $w(B_j)= (x-1)^s$ 
if $B_j$ has length $2s+2$. Then we let 
$w(\sg) = (-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 {\em 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{equation}\label{t1rec}
GMP_{2n,\tau^{(1)}}(x) = 
C_{n-1}(x-1)^{n-1} -\sum_{k=1}^{n-1} C_{k-1}(x-1)^{k-1} GMP_{2n-2k,\tau^{(1)}}(x).
\end{equation}
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 $\tau \in \mathcal{A}_4$, 
\begin{equation}\label{eqA}
A_{\tau}(t,x) = \frac{1}{1-\sum_{n\geq 1} GMP_{2n,\tau}(x) 
\frac{t^{2n}}{(2n)!}} \ \mbox{and}
\end{equation}
\begin{equation}\label{eqB}
B_{\tau}(t,x) =\frac{\sum_{n \geq 1} GMP_{2n-1,\tau}(x)
\frac{t^{2n-1}}{(2n-1)!}}{1-\sum_{n\geq 1} GMP_{2n,\tau}(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 the $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  
\begin{equation}
H(t) = \frac{1}{E(-t)}.
\end{equation}
For example, we shall 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 on symmetric functions that is required 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 the 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}$ where 
for any formal power series $f(x) = \sum_{n \geq 0} f_n x^n$, we 
write $f(x)|_{x^n}$ the coefficient of $x^n$ in $f$. 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
some field $F$. We let $\Lambda_n$ denote the space of homogeneous 
symmetric functions of degree $n$ so that 
$\Lambda = \oplus_{n \geq 0} \Lambda_n$.  

Let $\la = (\la_1,\dots,\la_\ell)$ be an integer partition, that is,
$\la$ is a finite sequence of weakly increasing non-negative
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)$ where 
$\lambda \vdash n$ 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 a brick tabloid of shape 
$n$ such that the 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 non-negative integers into the 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 $p_n = \sum_{i} x_i^n$. For any 
statement $A$, we let $\chi(A) =1$ if $A$ is true and $\chi(A) =0$ if 
$A$ is false. 
If $\nu(n) = (-1)^k \chi(n \geq k+1)$ for some $k \geq 1$, 
then $p_{n,\nu}$ is the Schur function $s_{(1^k,n-k)}$ corresponding to the partition $(1^k,n)$.

 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}. 
Fix $\tau  \in \mathcal{A}_4$. 

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)^{2n-1}}{(2n)!} GMP_{2n,\tau}(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\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 a 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}(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}(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}(x)$ to 
choose a sequence of permutations $\vec{\sg} = (\sg^{(1)}, \ldots, \sg^{(\ell(\la))})$ 
such that $\sg^{(j)} \in S_{2\la_j}$ is a generalized maximum packing for 
$\tau$ 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 
we place the elements of $\alpha^{(j)}$ in the cells of brick $2b_j$ from 
left to right. 
For example, we have illustrated this process in  Figure \ref{fig:Aexample1} 
for $\tau = \tau^{(1)} = 1324$ where the brick tabloid is  
$T=(2,8,6)$. We have also indicated the block structure 
in each brick by underlining those elements in a common block. 
The weight $w(T,\vec{U},\vec{\sg})$ of such a triple $(T,\vec{U},\vec{\sg})$ 
is $\prod_{j=1}^{\ell(\la)} w(\sg^{(j)})$.  
We can interpret 
 $w(T,\vec{U},\vec{\sg})$ as $\prod_{j=1}^{2n} L(j)$ 
where $L:\{1,\ldots, 2n\} \rightarrow \mathbb{Q}[x]$ is a labeling 
of the cells of $T$ which is defined as follows. 
First we define a labeling $\bar{L}:\{1,\ldots, 2n\} \rightarrow \mathbb{Q}[x]$
where $\bar{L}(j) =1$ if cell $j$ does not start a $\tau$-match that is 
contained in its brick and 
$\bar{L}(j) =x-1$ if cell $j$ starts a $\tau$-match that is contained 
in its brick. Then we define $L(j) = - \bar{L}(j)$ if 
$j$ is the first cell of its block and that block is not 
the last block in its brick and $L(j) = \bar{L}(j)$ otherwise. 
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 a 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}$,  and 
\item $L:\{1,\ldots, 2n\} \rightarrow \mathbb{Q}[x]$ is the labeling 
of the cells of $T$ described above. 
\end{enumerate}
 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 an 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}$ 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}} w(T,\alpha,L). 
\end{equation}

Next we will define two involutions $I$ and $J$ which 
will show that right-hand side 
 of (\ref{Ah3}) is equal to the right-hand side of (\ref{Ah0}). 
We define  $I:\mathcal{T}_{2n,\tau} \rightarrow 
\mathcal{T}_{2n,\tau}$ 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$. 
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}} w(T,\alpha,L) 
\nonumber \\
&=& \sum_{\stackrel{(T,\alpha,L) \in \mathcal{T}_{2n,\tau}}{ 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$ 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 of $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$ 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$-match in $\alpha$ that lies 
in its brick and is 
equal to $1$ otherwise.  
\end{description}

Next we want to modify our interpretation of the 
right-hand side of (\ref{Ah4}) to consist 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$ 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$-match in $\alpha$ that 
lies in its brick and is 
equal to $1$ otherwise.  
\end{description}
We let $\mathcal{FI}_{2n,\tau}$ denote the set of triples 
$(T',\alpha,L')$ satisfying $(I')$--$(III')$. Then for any 
$(T',\alpha,L') \in \mathcal{FI}_{2n,\tau}$, we define 
the weight  $w(T',\alpha,L')$ of $(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}} w(T',\alpha,L').
\end{equation}

Next we define an involution $J: \mathcal{FI}_{2n,\tau} \rightarrow 
\mathcal{FI}_{2n,\tau}$. Given an element 
$(T,\alpha,L) \in \mathcal{FI}_{2n,\tau}$, scan the 
cells of $T =(d_1, \ldots, d_k)$ from left to right looking for the first 
cell $c$ such that either (A) the label of $c$ is $-1$  or  
(B) $c$ is the second to last element of a brick $d_j$ such that 
the elements of bricks $d_j$ and $d_{j+1}$ reduce to a generalized 
maximum packing of $\tau$ which consists of a single block. Note 
that in case (B), $c$ must have label 1 since it does not 
start match of $\tau$ in $\alpha$ that lies in its brick. 
In case (A), if $c$ is in brick $d_j$, then break 
$d_j$ into two bricks $d^*$ and $d^{**}$ where $d^*$ contain the cells 
of $d_j$ up to and including cell $c+1$ and $d^{**}$ contains the 
rest of the cells of $d_j$. We then replace  
the $-1$ label on cell $c$ by $1$. In case (B), 
we replace the bricks 
$d_j$ and $d_{j+1}$ by a single brick $d$ and replace 
the label of $1$ on $c$ by $-1$. In either case, we do not 
change the underlying permutation $\alpha$. 
 If neither case (A) nor case (B) applies, then we let 
$J(T,\alpha,L) =(T,\alpha,L)$.  For example, if we 
consider the triple $(T,\alpha,L)$ 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 cells 8 and 9 so that $J(T,\alpha,L) = (T',\alpha,L')$ is 
the filling 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_{\stackrel{(T,\alpha,L) \in \mathcal{FI}_{2n,\tau}}{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$-match contained in $d$ is labeled with an $x$. 
Moreover, we claim that there cannot be a $\tau$-match that involves  
cells in two different bricks $d_j$ and $d_{j+1}$. That is, the 
only way a $\tau$-match could span cells in both $d_j$ and 
$d_{j+1}$ is if that $\tau$ match started in cell $c$ which 
is the second to last 
cell of $d_j$.  But this would imply that the elements of 
$d_j$ and $d_{j+1}$ would reduce to a generalized maximum packing for 
$\tau$ with a single block and, hence, case (B) of our involution 
would apply to $c$. Hence if $(T,\alpha,L)$ is a fixed point of 
$J$, then $w(T,\alpha,L) = x^{\tau\mbox{-mch}(\alpha)}$.

For any $\alpha \in \mathcal{A}_{2n}$, there is a 
unique fixed point  $(T,\alpha,L)$ of $J$ whose underlying permutation 
is $\alpha$.  That is, we must define the bricks 
$d_1, d_2, \ldots $ inductively as follows.
We  let $d_1$ be of  length 2 if there is no $\tau$-match in $\alpha$ starting 
at 1 and $d_1$ be of length $2s$ if there are 
 $\tau$-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$-match in $\alpha$ starting 
at $2k+1$ and $d_{r+1}$ be of length $2s$ if there are 
 $\tau$-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\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\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}(x)} 
\end{align*}
which is what we wanted to prove. 




To prove (\ref{eqB}), we will use the same ring homomorphism 
$\theta$ with weight function $\nu:\mathbb{P} \rightarrow \mathbb{Q}(x)$ 
where 
\begin{equation*}\label{Bp1}
\nu(2n-1) =0 \  \mbox{and} \ \nu(2n) = \frac{2n  GMP_{2n-1,\tau}(x)}{GMP_{2n,\tau}(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}(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\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 a 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}) \nonumber \\
&= (2n+1)! \sum_{\la \vdash n+1} (-1)^{2n+2-\ell(\la)}
\sum_{(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,2n+2}}
\nu(2b_{\ell(\la)}) \theta(e_{2b_{\ell(\la)}}) \prod_{j=1}^{\ell(\la)-1} \theta(e_{2b_j}) \nonumber \\
&= (2n+1)! \sum_{\la \vdash n+1} (-1)^{2n+2-\ell(\la)}
\sum_{(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}(x) \times \nonumber \\
& \ \ \ \  \ \ \ \ \ \ \  \prod_{j=1}^{\ell(\la)-1} \frac{(-1)^{2b_j -1}}{(2b_j)!} 
GMP_{2b_j,\tau}(x) \nonumber \\
& =  \sum_{\la \vdash n+1} \sum_{(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}(x) \times \\
& \ \ \ \  \ \ \ \ \ \ \ \prod_{j =1}^{\ell(\la)-1} GMP_{2b_j,\tau}(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+1\}$ 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}(x) \prod_{j =1}^{\ell(\la)-1} GMP_{2b_j,\tau}(x)$ to 
choose a sequence of permutations $\vec{\sg} = (\sg^{(1)}, \ldots, \sg^{(\ell(\la))})$ 
such that $\sg^{(j)} \in S_{2b_j}$ is a generalized maximum packing for 
$\tau$ for $j =1, \ldots, \ell(\la)-1$ and 
$\sg^{(\ell(\la))} \in S_{2b_{\ell(\la)}-1}$ is a generalized maximum packing for $\tau$. 
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 
we place the elements of $\alpha^{(j)}$ 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 illustrated this process in Figure \ref{fig:Bexample1}  
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 $w(T,\vec{U},\vec{\sg})$ 
of such a triple $(T,\vec{U},\vec{\sg})$   is 
$\prod_{j=1}^{\ell(\la)} w(\sg^{(j)})$. Again 
we can interpret $w(T,\vec{U},\vec{\sg})$ to be 
$\prod_{j=1}^{2n+1} L(j)$ where 
$L:\{1,\ldots, 2n\} \rightarrow \mathbb{Q}[x]$ is a labeling 
of the cells of $T$. To define $L$, we label the blank 
cell with 1 and then we label the remaining cells exactly as we 
did before. 
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 a 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}$ 
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}$,  and 
\item $L:\{1,\ldots, 2n\} \rightarrow \mathbb{Q}[x]$ is the 
labeling of the cells of $T$ described above. 
\end{enumerate}  
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 an 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}$ 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}} w(T,\alpha,L).
\end{equation}



Note that the only difference between the fillings of even 
length in the proof of (\ref{Ah0}) and our current fillings 
is that, in our current fillings, the last brick ends in 
a blank cell and the block structure of the reduction 
of the sequence of elements  
in the last brick must end in a block of size 1. 
This means that 
we can define the two involutions $I$ and $J$ exactly as 
before since  the fact that the last block of the final brick is length 1 does 
not change things. Using the same reasoning as in our proof of (\ref{Ah0}), 
it is easy to check that our involutions $I$ and $J$ show that  
\begin{equation} \label{Bp6}
(2n+1)!\theta(p_{2n+2,\nu})  = \sum_{\alpha \in \mathcal{A}_{2n+1}} x^{\tau\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\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}(x)}{1 - \sum_{n \geq 1} \frac{t^{2n}}{(2n)!}GMP_{2n,\tau}(x)}.
\end{align}


Dividing the second and the last elements in the 
string of equalities in (\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$.   If 
$P \in \mathcal{F}_{j,k}$ and $F \in \mathcal{F}_{n,k}$ where $j \leq n$,  
then  we say there is a {\em $P$-match  in $F$ starting at
position $i$} if $\red{F[i,i+1, \ldots, i+j-1]} = P$.
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$ 
and  there are 2 $P$-matches in $G$ starting at 
positions 1 and 2 so $\Pmch{F} =0$ and  $\Pmch{G} =2$.  


\fig{Pmatch}{Computing the number of $P$-matches for elements 
in  $\mathcal{F}_{6,3}$.} 


If $P \in \mathcal{F}_{2,k}$, then 
we define $\mathcal{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 = |\mathcal{MP}_n^P|$ and, by convention, we define $\mmp_{1}^{P}=1$.


Given an $F \in  \mathcal{F}_{n,2}$, we let 
$\sg(F)$ be the permutation 
$$\sg(F) =F(1,1)F(2,1)F(1,2)F(2,2) \ldots F(1,n)F(2,n).$$ 
We then let $P^{(i)}$ denote the element of 
$\mathcal{F}_{2,2}$ such that $\sg(P^{(i)}) = \tau^{(i)}$. 
For example, $P^{(1)}, \ldots, P^{(5)}$ are pictured 
in Figure \ref{fig:correspond}. 
It is then easy to see that for any 
maximum packing $F \in  \mathcal{F}_{n,2}$ of $P^{(i)}$, 
$\sg(F)$ is an up-down permutation in $\mathcal{A}_{2n}$ which is a maximum 
packing for $\tau^{(i)}$.  
Vice versa, if $\sg = \sg_1 \ldots \sg_{2n}$ is a 
maximum packing of $\tau^{(i)}$, then  the $2 \times n$ array 
$F_{\sg}$ where $F_\sg(1,i) = \sg_{2i-1}$ and $F_\sg(2,i) = \sg_{2i}$ 
is a maximum packing for $P^{(i)}$. 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$, $ \mmp_n^{P^{(1)}} = \mmp_n^{P^{(3)}}= C_{n-1}$ and 
 $\mmp_n^{P^{(2)}} = \mmp_n^{P^{(4)}}= \mmp_n^{P^{(5)}}= 1$. 
Thus we obtain the following theorem. 
\begin{theorem} For all $n \geq 2$, 
{\rm $\displaystyle \mmp_{2n,\tau^{(1)}}= \mmp_{2n,\tau^{(3)}}= C_{n-1}$} and \\ {\rm $\displaystyle 
\mmp_{2n,\tau^{(2)}} = \mmp_{2n,\tau^{(4)}}= \mmp_{2n,\tau^{(5)}}= 1$}.
\end{theorem}

Our next goal is to prove the following. 

\begin{theorem} For all $n \geq 2$, {\rm $\displaystyle 
\mmp_{2n+1,\tau^{(1)}} = 2n C_{n-1}$, $\displaystyle \mmp_{2n+1,\tau^{(2)}} =  2n$},\\
{\rm $\displaystyle \mmp_{2n+1,\tau^{(3)}}= C_{n-1} +C_n$, $\displaystyle  \mmp_{2n+1,\tau^{(4)}} = n+1$} and {\rm $\displaystyle \mmp_{2n+1,\tau^{(5)}}=  2$}.
\end{theorem}
\begin{proof}
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,2, 3$.  For example, in 
Figure \ref{fig:P1}, the graph $G_{P^{(1)}}$ is pictured 
immediately to the right of $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}_{G_{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}_{G_{n,P^{(i)}}}$. Vice versa, if 
$(a_1,b_1), \ldots, (a_{2n},b_{2n})$ is a linear extension of 
$\mathcal{W}_{G_{n,P^{(i)}}}$, 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  $\mathcal{W}_{G^+_{n,P^{(i)}}}$.



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 $\mathcal{W}_{G_{n,P^{(1)}}}$ and, hence, in any $F \in 
\mathcal{MP}^{P^{(1)}}_n$, $F(a) = 2n$. 
Note that the 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 $\mathcal{W}_{G^+_{n,P^{(1)}}}$ so that $a$ would be assigned 
the label $2n+1$ in any linear extension.  
But then it is easy to see 
that $b$ can be assigned any element in $\{1, \ldots, 2n\}$. Thus once 
we pick the value assigned to $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)}}$ in the 
second line.   In this case, 
it is easy to see that there is a unique linear extension 
of $\mathcal{W}_{G_{n,P^{(2)}}}$ 
and 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 is 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 extensions of $G_{n,P^{(2)}}$ which is 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)}}$ in 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 the 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 is 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)}}$ in the second line.   
In this case, 
it is easy to see that there is a unique  linear extension 
of $\mathcal{W}_{G_{n,P^{(4)}}}$ and 
the rightmost top element $a$ of  $G_{n,P^{(4)}}$
must be the $(n+1)$st element in the linear extension of $\mathcal{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)}}$.
Similarly, $a$ must be 
the $(n+2)$nd element in any linear extension of 
$\mathcal{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 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)}}$ in the second line. 
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 
any linear extension of $\mathcal{W}_{G^+_{6,P^{(5)}}}$.  
Thus we have two linear extensions  
depending upon how we order the two elements that have a 
directed edge into $a$. 
Hence $\mmp_{2n+1,P^{(5)}}=2$. \end{proof}

\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$, $GMP_{1,\tau^{(i)}}(x) =  GMP_{2,\tau^{(i)}}(x) =  1$, $GMP_{3,\tau^{(i)}}(x)=   -1$, and  
$GMP_{4,\tau^{(i)}}(x)=   x-2$. 
That is, there is only one generalized maximum packing of 
length 1 which consists of a block of length 1 and weight 1. Similarly, 
there is only one generalized maximum packing of 
length 2 which consists of a block of length 2 and weight 1. 
There is only one generalized maximum packing of length 3, namely, 
$123$ where $12$ is a block of length 2 and $3$ is a 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 a 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 for $i \in \{1,2,4\}$ there are simple recursions 
for computing $GMP_{n,\tau^{(i)}}(x)$.  
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 will allow us to develop recursions based on either 
the 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 and we have not been 
able to find any simple recursions for $GMP_{n,\tau^{(3)}}$ or 
$GMP_{n,\tau^{(5)}}$.  


The easiest case is for $\tau^{(1)} = 1324$ where we have the 
following theorem. 
\begin{theorem} For $n \geq 3$, 
\begin{equation}\label{tau1rec}
GMP_{2n,\tau^{(1)}}(x) = 
C_{n-1}(x-1)^{n-1} -
 \sum_{k=1}^{n-1} C_{k-1}(x-1)^{k-1}GMP_{2n-2k,\tau^{(1)}}(x) 
\end{equation}
and, for $n \geq 2$, $\displaystyle GMP_{2n+1,\tau^{(1)}}(x) =-GMP_{2n,\tau^{(1)}}(x)$.
\end{theorem}
\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$.  By the definition 
of a generalized maximum packing whose block structure is $B_1 \ldots B_k$, 
the last element of $B_i$ must be smaller than the first element 
of $B_{i+1}$ for all $i < k$. Thus all the elements of $B_i$ are smaller than 
any element in $B_{i+1}$ for all $i<k$. 

Now suppose that $n \geq 3$ and 
$\sg = \sg_1 \ldots \sg_{2n}  \in \mathcal{GMP}_{2n,\tau^{(1)}}$.
There are two 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$.\\
If $B_1$ is of length 2, then $B_1 =12$ and has weight $-1 = -C_0$ and 
$\red{B_2 \ldots B_s}$ is a generalized maximum packing for $\tau^{(1)}$ of 
length $2n-2$.  If $B_1$ has length 
$2k$ where $k \geq 2$, then $B_1 =1\ldots 2k$ is a maximum packing 
for $\tau^{(1)}$ of length $2k$  
which has weight $-(x-1)^{k-1}$ and 
$\red{B_2 \ldots B_s}$ is a generalized maximum packing of 
length $2n-2k$. 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=1}^{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 the list of the first few values of $GMP_{2n,\tau^{(1)}}(x)$. 
\begin{align*}
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{align*}


Plugging these values into the generating functions 
(\ref{eqA}) and (\ref{eqB}), 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{align*}
A_{1,\tau^{(1)}} &= 1 \\
A_{2,\tau^{(1)}} &= 1 \\
A_{3,\tau^{(1)}} &= 2 \\
A_{4,\tau^{(1)}} & =4+x  \\
A_{5,\tau^{(1)}} &= 12+4 x \\
A_{6,\tau^{(1)}} & = 35+24x+2x^2 \\
A_{7,\tau^{(1)}} & = 142+118 x+12 x^2 \\
A_{8,\tau^{(1)}} &= 546+672 x+162 x^2+5 x^3 \\
A_{9,\tau^{(1)}} &= 2816+3968 x+1112 x^2+40 x^3  \\
A_{10,\tau^{(1)}} &= 13482+24660 x+11145 x^2+1220 x^3+14 x^4  \\
A_{11,\tau^{(1)}} & = 84764+170996 x+87200 x^2+10666 x^3+168 x^4   
\end{align*} 


In this case, one can explicitly calculate the values 
of $GMP_{n,\tau^{(1)}}(x)|_{x^0} = GMP_{n,\tau^{(1)}}(0)$ and 
$GMP_{n,\tau^{(1)}}(x)|_x$.  One can obviously get recursions 
for $GMP_{n,\tau^{(1)}}(x)|_{x^k}$ for $k \geq 2$ but we could 
not find nice explicit formulas for such coefficients. For example, 
the sequence of absolute values of the coefficients of 
$GMP_{n,\tau^{(1)}}(x)|_{x^2}$ does not appear in 
the On-Line Encyclopedia of Integer Sequences (OEIS). 

\begin{theorem}\label{thm:specialvalues}
\begin{enumerate}
\item For all $m \geq 1$, $G_{2m,\tau^{(1)}}(0) = (-1)^{m-1}C_m$ and \\
$G_{2m+1,\tau^{(1)}}(0) = (-1)^{m}C_m$.

\item For all $m \geq 2$, $G_{2m,\tau^{(1)}}(x)|_{x} = 
(-1)^{m}\binom{2m}{m-2}$ and 
$G_{2m+1,\tau^{(1)}}(x)|_{x} = (-1)^{m+1}\binom{2m}{m-2}$.

\end{enumerate}
\end{theorem}
\begin{proof}
For (1), our formula obviously holds 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} -
 \sum_{k=1}^{n-1} C_{k-1}(-1)^{k-1}GMP_{2n-2k,\tau^{(i)}}(0)\\
&= C_{n-1}(-1)^{n-1} - \sum_{k=1}^{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*}

For (2), $GMP_{4,\tau^{(1)}}(x)|_{x} =1$ so our  formula holds 
for $n =2$. For $n > 2$, we have 
that 
\begin{align*}
GMP_{2n,\tau^{(1)}}(x)|_x = \ &
C_{n-1}(x-1)^{n-1}|_x - \sum_{k=1}^{n-1} (C_k (x-1)^k|)|_x (GMP_{2n-2k-2,\tau^{(1)}}(x))|_{x^0} - \\
&\sum_{k=1}^{n-1} (C_k (x-1)^k)|_{x^0} (GMP_{2n-2k-2,\tau^{(1)}}(x))|_{x}.
\end{align*}
Using induction and some simplifications with binomial coefficients, one 
can show that this is equivalent to the following identity: 
\begin{align}\label{keyeq}
(-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}\nonumber
\end{align}
One can then verify that the right-hand side of (\ref{keyeq}) is 
equal to $\binom{2n}{n-2}$ by induction using a series of 
routine manipulations and some simple identities for binomial coefficients. 
\end{proof}


Let $N_{n,\tau^{(1)}}$ denote the number of permutations 
$\sg \in \mathcal{A}_n$ such that $\tau^{(1)}\mbox{-mch}(\sg) =0$ 
and  $U_{n,\tau^{(1)}}$ denote the number of permutations 
$\sg \in \mathcal{A}_n$ such that $\tau^{(1)}\mbox{-mch}(\sg) =1$. 
Our previous theorem allows us to compute explicit generating 
functions for   $N_{n,\tau^{(1)}}$ and  $U_{n,\tau^{(1)}}$. 

\begin{theorem} Let $R(t) =  
\sum_{n \geq 1} (-1)^{n-1}C_n \frac{t^{2n}}{(2n)!}$ and 
$S(t) = \sum_{n \geq 2} (-1)^{n}\binom{2n}{n-2} \frac{t^{2n}}{(2n)!}$. 
Then 
\begin{align}\label{Ntau1e}
&1 + \sum_{n \geq 1} N_{2n,\tau^{(1)}} \frac{t^{2n}}{(2n)!} =  
\frac{1}{1-R(t)}, \\ 
&\sum_{n \geq 0} N_{2n+1,\tau^{(1)}} \frac{t^{2n+1}}{(2n+1)!} =
\frac{t- \int_0^t R(z)dz}{1-R(t)},\\
&1 + \sum_{n \geq 1} U_{2n,\tau^{(1)}} \frac{t^{2n}}{(2n)!} =  
\frac{S(t)}{(1-R(t))^2},\ \mbox{and}\\
&\sum_{n \geq 0} N_{2n+1,\tau^{(1)}} \frac{t^{2n+1}}{(2n+1)!} = 
\frac{(1-R(t))(\int_0^t S(z)dz)+S(t)(t - \int_0^t R(z)dz)}{(1-R(t))^2}. 
\end{align}
\end{theorem}
\begin{proof}
By Theorem \ref{thm:specialvalues}, 
\begin{equation}
\sum_{n \geq 1} GMP_{2n,\tau^{(1)}}(x) \frac{t^{2n}}{(2n)!}
= R(t) + x S(t) + O(x^2)
\end{equation}
and 
\begin{align*}
\sum_{n \geq 1} GMP_{2n-1,\tau^{(1)}}(x) \frac{t^{2n-1}}{(2n-1)!}& = 
t + \sum_{n \geq 2}  GMP_{2n-1,\tau^{(1)}}(x) \frac{t^{2n-1}}{(2n-1)!} \\
&= t- \sum_{n \geq 2}  GMP_{2n-2,\tau^{(1)}}(x) \frac{t^{2n-1}}{(2n-1)!}\\
&= t - \int_0^t R(z) + x S(z) +O(x^2) dz.
\end{align*}
Plugging these expressions into Theorem \ref{thm:main}, 
we see that 
\begin{equation}\label{A11}
A_{\tau^{(1)}}(t,x) = \frac{1}{1-R(t) -x S(t) +O(x^2)}
\end{equation}
and 
\begin{equation}\label{B11} 
B_{\tau^{(1)}}(t,x) = \frac{t -\int_0^t R(z)dz - x \int_0^t S(z) dz +O(x^2)}{1-R(t) -x S(t) +O(x^2)}.
\end{equation}
Equations (\ref{Ntau1e}) and (31) follow by putting 
$x =0$ in (\ref{A11}) and (\ref{B11}), respectively. 

To prove (32) and (33), note 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 \\
&=& \frac{S(t)}{(1-R(t))^2}.
\end{eqnarray}
Similarly, one can compute that 
\begin{eqnarray}
B_{\tau^{(1)}}(t,x)|_x &=& \frac{(t -\int_0^t R(z)dz) S(t)}{(1-R(t))^2}
+ \frac{\int_0^t S(z)dz}{1 -R(t)} \nonumber \\
&=& \frac{(1-R(t))(\int_0^t S(z)dz)+S(t)(t - \int_0^t R(z)dz)}{(1-R(t))^2}.
\end{eqnarray}
\end{proof}

Unfortunately, we have not been able to prove similar results 
for $\tau^{(i)}$ where $i \geq 2$ because in these cases,  
we have not been able to find explicit formulas for 
$GMP_{n,\tau^{(i)}}(0)$ or  $GMP_{n,\tau^{(i)}}(x)|_x$. 








Next we consider recursions for $GMP_{n,\tau^{(2)}}(x)$. 
\begin{theorem} For $n \geq 3$, 
\begin{equation}\label{tau2rec}
GMP_{2n,\tau^{(2)}}(x) = (x-1)^{n-1} -
\sum_{j=1}^{n-1} \binom{2n-j-1}{j-1}(x-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}
\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$,  
the last element of each block $B_i$ is the largest element 
in the block. 


If $\sg$ is a maximum packing for $\tau^{(2)}$ with 
block structure $B_1 \ldots B_k$, we shall simply write 
$\sg = B_1 \ldots B_k$. 
Our recursion follows by classifying the generalized 
packings  $\sg = B_1 B_2 \ldots B_k$ for $\tau^{(2)}$ by the size 
of the last block $B_k$. 
If $k=1$, then $\sg$ is unique and $w(\sg) = (x-1)^{n-1}$. Thus 
suppose that $k \geq 2$. 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$ 
and $w(\sg) = -w(B_1 \ldots B_{k-1})$. Thus such permutations 
contribute $-GMP_{2n-2,\tau^{(2)}}(x)$ to $GMP_{2n,\tau^{(2)}}(x)$.
If $B_k$ has length $2j$ where $j \geq 2$, then 
$B_k = \sg_{2n-2j+1} \ldots \sg_{2n}$ reduces to a maximum packing for 
$\tau^{(2)}$ of 
length $2j$ and $w(\sg) = -(x-1)^{j-1}w(B_1 \ldots B_{k-1})$. 
Then we know that  
$\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 such permutations 
contribute $-\binom{2n-j-1}{j-1}(x-1)^{j-1}GMP_{2n-2j,\tau^{(2)}}(x)$ to $GMP_{2n,\tau^{(2)}}(x)$.
Hence (\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 the list of the first few values of $GMP_{2n,\tau^{(1)}}(x)$. 
\begin{align*}
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{align*}

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 $ is sequence A125273 in the 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}), 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{align*}
A_{1,\tau^{(2)}} & = 1 \\
A_{2,\tau^{(2)}} &= 1 \\
A_{3,\tau^{(2)}} &= 2 \\
A_{4,\tau^{(2)}} & = 4+x \\
A_{5,\tau^{(2)}} &= 12+4 x \\
A_{6,\tau^{(2)}} & = 36+24x+x^2 \\
A_{7,\tau^{(2)}} &= 148+118 x+6 x^2\\
A_{8,\tau^{(2)}} &= 593+680 x+111 x^2+x^3 \\
A_{9,\tau^{(2)}} &= 3128+4032 x+768 x^2+8 x^3 \\
A_{10,\tau^{(2)}}&= 15676+25691 x+8680 x^2+473 x^3+x^4\\
A_{11,\tau^{(2)}}&=101094+180134 x+68326 x^2+4228 x^3+10 x^4 \\
\end{align*}





Next we consider recursions for $GMP_{2n,\tau^{(4)}}(x)$. 
\begin{theorem} For $n \geq 3$, 
\begin{equation}\label{tau4rec}
GMP_{2n,\tau^{(4)}}(x) = (x-1)^{n-1} -
\sum_{j=1}^{n-1} \binom{2n-j-1}{j-1}GMP_{2n-2j,\tau^{(4)}}(x) 
\end{equation}
and, for $n \geq 2$, 
\begin{equation}\label{tau4reco}
GMP_{2n+1,\tau^{(4)}}(x) =
-n(x-1)^{n-1} - \sum_{j=1}^{n-1} \binom{2n-j}{j-1}GMP_{2n+1-2j,\tau^{(4)}}(x).
\end{equation}
\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$, 
the first element of each block $B_i$ is the smallest element 
in the block. 


If $\sg$ is a maximum packing for $\tau^{(4)}$ with block structure 
$B_1 \ldots B_k$, we shall simply write $\sg =B_1 \ldots B_k$. 
We will classify the generalized maximum packings 
$\sg = B_1 \ldots B_k$ of $\tau^{(4)}$ of length $2n$ by 
the size of the first block $B_1$.  If $k=1$, then 
$\sg$ is unique and $w(\sg) = (x-1)^{n-1}$. 
Next consider the case where $k \geq 2$. 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$ 
and $w(\sg) = - w(B_2 \ldots B_k)$. Thus such permutations 
contribute $-GMP_{2n-2,\tau^{(4)}}(x)$  to $GMP_{2n,\tau^{(4)}}(x)$. 
If $B_1$ is of size $2j$ where $j \geq 2$, then 
$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$ and 
$w(\sg) = -(x-1)^{j-1}w(B_2 \ldots B_k)$. 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 than 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 such permutations contribute 
$-\binom{2n-j-1}{j-1}(x-1)^{j-1}GMP_{2n-2j,\tau^{(4)}}(x)$ to 
$GMP_{2n,\tau^{(4)}}(x)$. 
Hence (\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 sends  
$\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. 

Again, we will classify the generalized maximum packings 
$\sg = B_1 \ldots B_k$ of $\tau^{(4)}$ of length $2n+1$ by 
the size of the first block $B_1$.  If $k=2$, then $B_1$ 
has length $2n$ and $B_2$ has length 1. One can see 
by the graph of $G_{n,P^{(4)}}$ and the fact 
that $\sg_{2n} < \sg_{2n+1}$ that $\sg_{2n} =n+1$. Then 
we have $n$ choices for $\sg_{2n+1}$ and after 
we pick $\sg_{2n+1}$, $\sg_1 \ldots \sg_{2n}$ must reduce 
to a maximum packing of $\tau^{(4)}$.  Since 
there is only one maximum packing of length $2n$ for 
$\tau^{(4)}$, we have exactly $n$ such permutations 
and the weight of each such permutation is $-(x-1)^{n-1}$. 
Thus such permutations contribute 
$-n(x-1)^{n-1}$ to $GMP_{2n+1,\tau^{(4)}}(x)$. 
Next consider the case where $k \geq 3$. 
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-1$ 
and $w(\sg) = - w(B_2 \ldots B_k)$. Thus such permutations 
contribute $-GMP_{2n-1,\tau^{(4)}}(x)$  to $GMP_{2n+1,\tau^{(4)}}(x)$. 
If $B_1$ is of size $2j$ where $j \geq 2$, then 
$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$ and 
$w(\sg) = -(x-1)^{j-1}w(B_2 \ldots B_k)$. 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 than 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+1-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+1-2j$. Thus such permutations contribute 
$-\binom{2n-j}{j-1}(x-1)^{j-1}GMP_{2n+1-2j,\tau^{(4)}}(x)$ to 
$GMP_{2n,\tau^{(4)}}(x)$. Hence (\ref{tau4reco}) holds.
\end{proof}


Here is the list of the first few values of $GMP_{2n+1,\tau^{(4)}}(x)$. 
\begin{align*}
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{align*}

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



Plugging these values into the generating functions 
(\ref{eqA}) and (\ref{eqB}), 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{align*} 
A_{1,\tau^{(4)}} & = 1 \\
A_{2,\tau^{(4)}} & = 1 \\
A_{3,\tau^{(4)}} & = 2 \\
A_{4,\tau^{(4)}} & = 4+x \\
A_{5,\tau^{(4)}} &= 13+3 x\\
A_{6,\tau^{(4)}} & = 36+24x+x^2 \\
A_{7,\tau^{(4)}} &= 165+103 x+4 x^2\\
A_{8,\tau^{(4)}} &= 593+680 x+111 x^2+x^3  \\
A_{9,\tau^{(4)}} & = 3507+3832 x+592 x^2+5 x^3 \\
A_{10,\tau^{(4)}} & = 15676+25691 x+8680 x^2+473 x^3+x^4 \\
A_{11,\tau^{(4)}} & = 113387+179369 x+58016 x^2+3014 x^3+6 x^4\\
\end{align*}



As we mentioned in the introduction to this section, we 
have not be able to find simple recursions for $GMP_{n,\tau^{(3)}}(x)$ 
or $GMP_{n,\tau^{(5)}}(x)$.  However, 
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 extensions of the posets associated 
with the various block structures of generalized maximal 
packings. 



Here is the list of the first few values of $GMP_{2n,\tau^{(3)}}(x)$. 
\begin{align*}
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{align*}


Plugging these values into the generating functions 
(\ref{eqA}) and (\ref{eqB}), 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{align*} 
A_{1,\tau^{(3)}} & = 1 \\
A_{2,\tau^{(3)}} & = 1 \\
A_{3,\tau^{(3)}} & = 2 \\
A_{4,\tau^{(3)}} & = 4+x \\
A_{5,\tau^{(3)}} & = 13+3x \\
A_{6,\tau^{(3)}} &= 39+20x+2x^2  \\
A_{7,\tau^{(3)}} & = 178+87x+7x^2 \\
A_{8,\tau^{(3)}} & = 710+552 x+118 x^2+5 x^3  \\
A_{9,\tau^{(3)}} & = 4168+3146x+603x^2+19x^3 \\
A_{10,\tau^{(3)}} & = 29774+21666 x+5370 x^2+2697 x^3+14 x^4  \\
A_{11,\tau^{(3)}} & = 149030+152170x+27000x2+25536x^3+56x^4  \\
\end{align*}


Here is the list of the first few values of $GMP_{2n,\tau^{(5)}}(x)$. 
\begin{align*}
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{align*}


Plugging these values into the generating functions 
(\ref{eqA}) and (\ref{eqB}), 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{align*}
A_{1,\tau^{(5)}} &= 1 \\
A_{2,\tau^{(5)}} & = 1 \\
A_{3,\tau^{(5)}} & = 2 \\
A_{4,\tau^{(5)}} & = 4+x  \\
A_{5,\tau^{(5)}} & = 14+2x\\
A_{6,\tau^{(5)}} & = 44+16x+x^2 \\
A_{7,\tau^{(5)}} & = 214-56x+2x^2 \\
A_{8,\tau^{(5)}} & = 896+448 x+40 x^2+x^3  \\
A_{9,\tau^{(5)}} & = 5610+2190x+134x^2+2x^3  \\
A_{10,\tau^{(5)}} & = 29392+18496 x+ 2552x^2+80x^3+x^4 \\
A_{11,\tau^{(5)}} & = 224878+116776x+11880x^2+256x^3+2x^4 \\
\end{align*}


\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, $(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 descent 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 a 
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 a  
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)$.


If $\Upsilon \subseteq \mathcal{A}_4$, 
the proof of Theorem \ref{thm:main} goes through without 
change if we replace maximum packings for $\tau$ with 
maximum packings for $\Upsilon$ and generalized maximum 
packings for $\tau$ by generalized maximum packings 
for $\Upsilon$ throughout the proof. Thus we 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}


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 $F^r$ be the reverse 
of $F$. That is, the first row of 
$F^r$ is $F(1,n), F(1,n-1) \ldots, F(1,1)$  
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 a 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,D} = C_n$.

The graph $G_D$ associated with $D$ is 
pictured on the right in the first line 
of Figure \ref{fig:U}. Then we can construct the graphs 
$G_{D,n}$ and $G^+_{D,n}$ using $G_D$ in the same way 
that we constructed the 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 the 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{align*}
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{align*}


Plugging these values into the generating functions 
(\ref{eqAu}) and (\ref{eqBu}), 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{align*}
A_{1,D} & = 1 \\
A_{2,D} & = 1 \\
A_{3,D} & = 2 \\
A_{4,D} & = 3+2x  \\
A_{5,D} & = 11+5 x\\
A_{6,D} & = 24+32 x+5 x^2 \\
A_{7,D} & = 125+133 x+14 x^2 \\
A_{8,D} & = 345+760 x+266 x^2+14 x^3 \\
A_{9,D} & = 1341+4359 x+1194 x^2+42 x^3 \\
A_{10,D}& = 7890+24928 x+15609 x^2+2052 x^3+42 x^4 \\
A_{11,D}& = 17752+162570 x+115401 x^2+2937 x^3+132 x^4 
\end{align*} 


A. 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 the 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}$.
\footnote{We wish to thank the anonomous referee for many suggested 
improvements in the presentation of this paper}



\begin{thebibliography}{20}


\bibitem{BeckRem} 
D. Beck and J. 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{DR} A.S. Duane and J.B. Remmel, 
Minimal overlapping patterns in colored 
permutations, Electronic J. Combinatorics, {\bf 18(2)} (2011), P25, 34 pgs.
 




\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., {\bf 6} (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, DMTCS Proceedings, 22nd International Conference 
on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 
(2010), 391--402.



\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 6} (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/$\backsim$rstan/ec/catadd.pdf, (2013). 

\end{thebibliography}







\end{document}
