\documentclass[12pt]{article} \usepackage{e-jc,amsfonts,amssymb,amsmath,amsthm,epsfig,euscript} %\setlength{\textwidth}{6.3in} %\setlength{\textheight}{8.7in} %\setlength{\topmargin}{0pt} %\setlength{\headsep}{0pt} %\setlength{\headheight}{0pt} %\setlength{\oddsidemargin}{0pt} %\setlength{\evensidemargin}{0pt} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \def\mn{\makebox[1.1ex]{\rule[.58ex]{.71ex}{.15ex}}} \long\def\symbolfootnote[#1]#2{\begingroup \def\thefootnote{\fnsymbol{footnote}}\footnote[#1]{#2}\endgroup} % newcommands to be used in math mode %\newcommand{\coi}[1][\sigma]{\mathrm{coinv}(#1)} \newcommand{\coib}[1][\sigma]{\mathrm{coinv}_B(#1)} \newcommand{\com}[1][\sigma]{\mathrm{comaj}(#1)} \newcommand{\comb}[1][\sigma]{\mathrm{comaj}_B(#1)} %\DeclareMathOperator{\des}{\mathrm{des}} %\DeclareMathOperator{\maj}{\mathrm{maj}} \newcommand{\desb}[1][\sigma]{\mathrm{des}_B(#1)} %\newcommand{\epq}[1][t(x-y)]{\mathbf{e}_{p,q}^{#1}} \newcommand{\HF}{\xi} \newcommand{\HK}{\xi_B} %\newcommand{\inv}[1]{\mathrm{inv}(#1)} %\newcommand{\inv}[1]{\mathrm{inv}(#1)} \newcommand{\la}{\lambda} \newcommand{\La}{\Lambda} \newcommand{\ris}[1]{\mathrm{ris}(#1)} \newcommand{\wris}[1]{\mathrm{wris}(#1)} \newcommand{\sris}[1]{\mathrm{sris}(#1)} \newcommand{\wmaj}[1][\gamma]{\mathrm{wmaj}(#1)} \newcommand{\wdes}[1]{\mathrm{wdes}(#1)} \newcommand{\sdes}[1]{\mathrm{sdes}(#1)} \newcommand{\des}[1]{\mathrm{des}(#1)} \newcommand{\levmaj}[1][\gamma]{\mathrm{levmaj}(#1)} \newcommand{\lev}[1][\gamma]{\mathrm{lev}(#1)} \DeclareMathOperator{\parts}{parts} \newcommand{\majb}[1][\sigma]{\mathrm{maj}_B(#1)} \newcommand{\mmaj}[1][\sigma^1,\dots,\sigma^m]{\mathrm{commaj}(#1)} \newcommand{\mdes}[1][\sigma^1,\dots,\sigma^m]{\mathrm{comdes}(#1)} \newcommand{\nega}[1][\sigma]{\mathrm{neg}(#1)} \newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}} \newcommand{\ov}{\overline} \newcommand{\pos}[1][\sigma]{\mathrm{pos}(#1)} \newcommand{\qbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{q}} \newcommand{\pqbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{p,q}} \newcommand{\rbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{r}} %\newcommand{\ris}[1][\sigma]{\mathrm{ris}(#1)} %\newcommand{\risb}[1][\sigma]{\mathrm{ris}_B(#1)} \newcommand{\sg}{\sigma} \newcommand{\ep}{\epsilon} \newcommand{\ga}{\gamma} \newcommand{\Ta}{\Theta} \newcommand{\N}{\mathbb{N}} \newcommand{\Pos}{\mathbb{P}} \newcommand{\Ev}{\mathbb{E}} \newcommand{\Odd}{\mathbb{O}} \newcommand{\sP}{s\mathbb{P}} \newcommand{\UD}{U\mbox{-}D} \newcommand{\NDD}{ND\mbox{-}D} \newcommand{\UNU}{U\mbox{-}NU} \newcommand{\ud}{u\mbox{-}d} \newcommand{\mmp}{\mbox{mp}} \newcommand{\unu}{u\mbox{-}nu} \def\dd{{\textrm d}} %\def\qexp{{\mathbf{e}}_q} %\def\pqexp{{\mathbf{e}}_{p,q}} \newcommand{\sm}[2]{\sum_{#1 = #2}^{\infty}} \newcommand{\al}{\alpha} \newcommand{\cref}[1]{Corollary \ref{corollary:#1}} \newcommand{\cmch}[1][\sg^1,\dots,\sg^m]{\text{$\tau$-$\mathrm{commch}$}(#1)} \newcommand{\clap}[1][\sg^1,\dots,\sg^m]{\text{$\tau$-$\mathrm{comnlap}$}(#1)} \newcommand{\cvlap}[1][w,y]{\text{$v$-$\mathrm{comnlap}$}(#1)} %\newcommand{\des}[1]{\mathrm{des}(#1)} %\newcommand{\ep}[1]{\exp \left( #1 \right)} \newcommand{\qexp}[1]{\exp_{q} \left( #1 \right)} \newcommand{\pqexp}[1]{\exp_{q,p} \left( #1 \right)} \newcommand{\Epq}[1]{\mathrm{Exp}_{q} \left( #1 \right)} \newcommand{\eref}[1]{\eqref{equation:#1}} \newcommand{\FA}{f} \newcommand{\FAq}{f_q} \newcommand{\FAm}{f_m} \newcommand{\FB}{g} \newcommand{\FBb}{g_2} %\newcommand{\fig}[1]{\vspace{1ex} \begin{center} \input{#1.pstex_t} \end{center%} \vspace{1ex}} \newcommand{\Floor}[1][n/2]{\left \lfloor #1 \right \rfloor} \newcommand{\HA}{\xi} \newcommand{\HAq}{\xi_q} \newcommand{\HAm}{\xi_m} \newcommand{\HB}{\varphi} \newcommand{\HC}{\eta} \newcommand{\HCb}{\eta_2} \newcommand{\HL}{\vartheta} \newcommand{\im}{i} \newcommand{\inv}[1]{\mathrm{inv}(#1)} \newcommand{\coinv}[1]{\mathrm{coinv}(#1)} \newcommand{\lref}[1]{Lemma \ref{lemma:#1}} %\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}} \newcommand{\qbin}[3]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{#3}} \newcommand{\red}[1]{\mathrm{red}(#1)} \newcommand{\pred}[1]{\mathrm{pred}(#1)} %\newcommand{\sg}{\sigma} %\newcommand{\sm}[2]{\sum_{#1 = #2}^{\infty}} \newcommand{\sref}[1]{Section \ref{sub:#1}} \newcommand{\tmch}[1]{\text{$\tau$-$\mathrm{mch}$}(#1)} \newcommand{\Pmch}[1]{\text{$P$-$\mathrm{mch}$}(#1)} \newcommand{\umch}[1]{\text{$\Upsilon$-$\mathrm{mch}$}(#1)} \newcommand{\tumch}[1]{\text{$(\tau,u)$-$\mathrm{mch}$}(#1)} \newcommand{\tEumch}[1]{\text{$(\tau,Eu)$-$\mathrm{mch}$}(#1)} \newcommand{\ulap}[1]{\text{$u$-$\mathrm{nlap}$}(#1)} \newcommand{\Eulap}[1]{\text{$Eu$-$\mathrm{nlap}$}(#1)} \newcommand{\tlap}[1]{\text{$\tau$-$\mathrm{nlap}$}(#1)} \newcommand{\Plap}[1]{\text{$P$-$\mathrm{nlap}$}(#1)} \newcommand{\tEulap}[1]{\text{$(\tau,Eu)$-$\mathrm{nlap}$}(#1)} \newcommand{\Umch}[1]{\text{$\Upsilon$-$\mathrm{mch}$}(#1)} \newcommand{\Ulap}[1]{\text{$(\tau,\Upsilon)$-$\mathrm{nlap}$}(#1)} \newcommand{\tUmch}[1]{\text{$(\tau,\Upsilon)$-$\mathrm{mch}$}(#1)} \newcommand{\EUmch}[1]{E\text{$\Upsilon$-$\mathrm{mch}$}(#1)} \newcommand{\EUlap}[1]{E\text{$(\tau,\Upsilon)$-$\mathrm{nlap}$}(#1)} \newcommand{\EtUmch}[1]{E\text{$(\tau,\Upsilon)$-$\mathrm{mch}$}(#1)} \newcommand{\tUlap}[1]{\text{$\Upsilon$-$\mathrm{nlap}$}(#1)} \newcommand{\tref}[1]{Theorem \ref{theorem:#1}} \newcommand{\vartmch}[2]{\text{${#1}$-mch}(#2)} \newcommand{\vlap}[1]{\text{$v$-$\mathrm{nlap}$}(#1)} \newcommand{\vmch}[1]{\text{$v$-$\mathrm{mch}$}(#1)} \newcommand{\WE}{\upsilon} % newcommands to be used in regular mode \newcommand{\fig}[2]{\begin{figure}[ht] \centerline{\scalebox{.66}{\epsfig{file=#1.eps}}} \caption{#2} \label{fig:#1} \end{figure}} %\newcommand{\eref}[1]{(\ref{equation:#1})} %\newcommand{\sref}[1]{Section \ref{sub:#1}} %\newcommand{\tref}[1]{Theorem \ref{theorem:#1}} %\newcommand{\lref}[1]{Lemma \ref{lemma:#1}} %\newcommand{\fref}[1]{Figure \ref{figure:#1}} \title{Consecutive up-down patterns in up-down permutations} \author{ Jeffrey B. Remmel \\ \small Department of Mathematics\\[-0.8ex] \small University of California, San Diego\\[-0.8ex] \small La Jolla, CA 92093-0112. USA\\[-0.8ex] \small \texttt{jremmel@ucsd.edu} \and %ls } \date{\small Submitted: Date 1; Accepted: Date 2; Published: Date 3.\\ \small MR Subject Classifications: 05A15, 05E05} \begin{document} \maketitle \begin{abstract} \noindent In this paper, we study the distribution of the number of consecutive pattern matches of an up-down permutation $\tau$ in the set of up-down permutations. In particular, we study the distribution of the number of consecutive pattern matches of the five up-down permutations of length four, $1324$, $1423$, $2314$, $2413$, and $3412$, in the set of up-down permutations. We show that in all five cases, the generating function for the distribution of the number of consecutive pattern matches of $\tau$ in the set of up-down permutations can be expressed in terms of what we call the generalized maximum packing polynomials of $\tau$. We then provide some systematic methods to compute the generalized maximum packing polynomials for such $\tau$. \end{abstract} \section{Introduction} If $\sg = \sg_1 \ldots \sg_n$ is a permutation in the symmetric group $S_n$, then we let $$Des(\sg) = \{i: \sg_i > \sg_{i+1}\} \ \mbox{and} \ Ris(\sg) = \{i: \sg_i < \sg_{i+1}\}.$$ Let $\N = \{0,1, \ldots, \}$ denote the natural numbers, $\Pos =\{1, 2, \ldots \}$ denote the set of positive integers, $\Ev= \{0,2,4, \ldots\}$ denote the set of even numbers in $\N$, and $[n] = \{1,2, \ldots, n\}$ for $n \in \Pos$. We say that $\sg = \sg_1 \ldots \sg_n$ is an {\em up-down permutation} if either $n =1$ or $n > 1$ and $Des(\sg) = [n-1]\cap \Ev$. That is, we have $$\sg_1 < \sg_2 > \sg_3 < \sg_4 \ldots .$$ We let $\mathcal{A}_n$ denote the set of up-down permutations in $S_n$. Given a sequence $\sg = \sg_1 \ldots \sg_n$ of distinct integers, let $\red{\sg}$ be the permutation found by replacing the $i$th smallest integer that appears in $\sg$ by $i$. For example, if $\sg = 2754$, then $\red{\sg} = 1432$. Given a permutation $\tau=\tau_1 \ldots \tau_j\in S_j$ and a permutation $\sg = \sg_1 \ldots \sg_n \in S_n$, we say that $\tau$ {\em occurs} in $\sg$ if there are $1 \leq i_1 < \ldots < i_j \leq n$ such that $\red{\sg_{i_1} \ldots \sg_{i_j}} = \tau$ and we say that $\sg$ has a {\em $\tau$-match starting at position $i$} in $\sg$ if $\red{\sg_i \sg_{i+1} \ldots \sg_{i+j-1}} = \tau$. We say that $\sg$ {\em avoids} $\tau$ if there are no occurrences of $\tau$ in $\sg$. We let $\tmch{\sg}$ denote the number of $\tau$-matches in $\sg$. We let $A_{n,\tau}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tmch{\sg}}$. These definitions are easily extended to sets of permutations $\Upsilon \subseteq S_j$. That is, we say that $\Upsilon$ occurs in $\sg$ if there are $1 \leq i_1 < \ldots < i_j \leq n$ such that $\red{\sg_{i_1} \ldots \sg_{i_j}} \in \Upsilon$ and we say that $\sg$ has a $\Upsilon$-match starting at position $i$ in $\sg$ if $\red{\sg_i \sg_{i+1} \ldots \sg_{i+j-1}} \in \Upsilon$. We say that $\sg$ avoids $\Upsilon$ if there are no occurrences of $\Upsilon$ in $\sg$. We let $\umch{\sg}$ denote the number of $\Upsilon$-matches in $\sg$. We let $\mathcal{A}_{n,\Upsilon}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\umch{\sg}}$. There have been several papers that have studied the number of up-down permutations $\sg \in \mathcal{A}_n$ which avoid a given pattern. For example, Mansour \cite{mansour} and Deutsch and Reifegerste, see \cite{StCat}, Problem $h^7$ or \cite{hong}, showed that for any $\tau \in S_3$, the number of up-down permutations $\sg \in \mathcal{A}_{n}$ which avoid $\tau$ is always a Catalan number. For example, the number of up-down permutations $\sg \in \mathcal{A}_n$ that avoid $132$ ($231$) is $C_{\lfloor n/2 \rfloor}$. In \cite{lewis}, it was shown that the number of $\sg \in \mathcal{A}_{2n}$ which avoids 1234 or 2143 is $\frac{2(3n)!}{n!(n+1)!(n+2)!}$. There has been somewhat less work on the distribution of $\tau$-matches in up-down permutations. Carlitz \cite{carlitz1} found the generating function for the number of rises in the peaks of the up-down permutations where a rise in the peaks of an up-down permutation is just 213-match in $\sg$. The main goal of this paper is to study the generating functions \begin{equation}\label{gfA} A_{\tau}(t,x) = 1+ \sum_{n \geq 1} \frac{t^{2n}}{(2n)!} \sum_{\sg \in \mathcal{A}_{2n}} x^{\tmch{\sg}} \end{equation} and \begin{equation}\label{gfB} B_{\tau}(t,x) = \sum_{n \geq 1} \frac{t^{2n-1}}{(2n-1)!} \sum_{\sg \in \mathcal{A}_{2n-1}}x^{\tmch{\sg}} \end{equation} in the case where $\tau \in \mathcal{A}_4$. Note that there are 5 permutations in $\mathcal{A}_4$, namely, \begin{equation*} \tau^{(1)} = 1324, \tau^{(2)} = 2314, \tau^{(3)} = 2413, \tau^{(4)} = 1423, \ \mbox{and} \ \tau^{(5)} = 3412. \end{equation*} If $\sg \in \mathcal{A}_n$, then $\tau^{(i)}$-matches can only start at odd positions. If $\sg \in \mathcal{A}_{2n}$ and $\tau^{(i)}\mbox{-mch}(\sg) = n-1$, then we say that $\sg$ is a {\em maximum packing for $\tau^{(i)}$}. Thus if $\sg \in \mathcal{A}_{2n}$ is a maximum packing for $\tau^{(i)}$, then $\sg$ has $\tau^{(i)}$-matches starting at positions $1,3,\ldots,2n-3$. We let $\mathcal{MP}_{2n,\tau^{(i)}}$ denote the set of maximum packings for $\tau^{(i)}$ in $\mathcal{A}_{2n}$ and we let $\mmp_{2n,\tau^{(i)}} = |\mathcal{MP}_{2n,\tau^{(i)}}|$. We shall see that it follows from results of Harmse and Remmel \cite{HR} that \begin{eqnarray*} \mmp_{2n,\tau^{(1)}} &=& \mmp_{2n,\tau^{(3)}} =C_{n-1} \ \mbox{and} \\ \mmp_{2n,\tau^{(2)}} &=& \mmp_{2n,\tau^{(4)}} = \mmp_{2n\tau^{(5)}} = 1, \end{eqnarray*} where $C_n = \frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number. Our main theorem will show that for each $i \in [5]$, the generating functions $A_{\tau^{(i)}}(t,x)$ and $B_{\tau^{(i)}}(t,x)$ can be expressed in terms of what we call generalized maximum packings for $\tau^{(i)}$. That is, we say that $\sg \in S_{2n}$ is a {\em generalized maximum packing for $\tau^{(i)}$} if we can break $\sg$ into consecutive blocks $\sg = B_1 \ldots B_k$ such that \begin{enumerate} \item for all $1 \leq j \leq k$, $B_j$ is either an increasing sequence of length 2 or $\red{B_j}$ is maximum packing for $\tau^{(i)}$ of length $2s$ for some $s \geq 2$ and \item for all $1 \leq j \leq k-1$, the last element of $B_j$ is less than the first element of $B_{j+1}$. \end{enumerate} Note that if $\sg$ is a generalized maximum packing for $\tau^{(i)}$, there is only one possible block structure. That is, if $\sg = \sg_1 \ldots \sg_{2n} \in S_{2n}$ is a generalized maximum packing for $\tau^{(i)}$, our definitions force that $\sg_{2j-1} < \sg_{2j}$ for $i =1, \ldots, n$. Then it is easy to see that $\sg_{2j-1}\sg_{2j}$ and $\sg_{2j+1}\sg_{2j+2}$ are in the same block if and only if $\sg_{2j}> \sg_{2j+1}$. If $\sg$ is a generalized maximum packing for $\tau^{(i)}$ of length $2n$ with block structure $B_1 \ldots B_k$, then we define the weight $w(B_j)$ of block $B_j$ to be 1 if $B_j$ has length 2 and to be $(x-1)^s$ if $B_j$ has length $2s+2$ where $s \geq 1$. Then we define the weight $w(\sg)$ of $\sg$ to be $(-1)^{k-1}\prod_{j=1}^k w(B_j)$. For example, $$\sg = 1~2~3~5~4~7~6~9~8~10~11~12~13~14~15~17~16~18$$ is a generalized maximum packing for $\tau^{(1)} = 1324$ where $B_1 =1~2$, $B_2= 3~5~4~7~6~9~8~10$, $B_3 =11~12$, $B_4 = 13~14$ and $B_5 = 15~17~16~18$. Thus $w(B_1) = w(B_3) =w(B_4) =1$, $w(B_2) =(x-1)^3$ and $w(B_5) =(x-1)$ so that $w(\sg) = (-1)^4 (x-1)^4 = (x-1)^4$. Thus the weight of $\sg$ is just $(-1)^{k-1}(x-1)^{\tau^{(i)}\mbox{-mch}(\sg)}$ where $k$ is the number of blocks of $\sg$. We let $\mathcal{GMP}_{2n,\tau^{(i)}}$ denote the set of $\sg \in S_{2n}$ which are generalized maximum packings for $\tau^{(i)}$ and we let \begin{equation} GMP_{2n,\tau^{(i)}}(x) = \sum_{\sg \in \mathcal{GMP}_{2n,\tau^{(i)}}} w(\sg). \end{equation} We say that $\sg \in S_{2n+1}$ is a {\em generalized maximum packing for $\tau^{(i)}$} if we can break $\sg$ into consecutive blocks $\sg = B_1 \ldots B_k$ such that \begin{enumerate} \item for all $1 \leq j < k$, $B_j$ is either an increasing sequence of length 2 or $\red{B_j}$ is maximum packing of $\tau^{(i)}$ of length $2s$ for some $s \geq 2$, \item $B_k$ is a block of length $1$, and \item for all $1 \leq j \leq k-1$, the last element of $B_j$ is less than the first element of $B_{j+1}$. \end{enumerate} If $\sg$ is a generalized maximum packing for $\tau^{(i)}$ of length $2n+1$ with block structure $B_1 \ldots B_k$, then we define the weight $w(B_j)$ of block $B_j$ to be 1 if $B_i$ has length 1 or 2 and to be $(x-1)^s$ if $B_j$ has length $2s+2$ where $s \geq 1$. Then we define the weight $w(\sg)$ of $\sg$ to be $(-1)^{k-1}\prod_{i=1}^k w(B_i)= (-1)^{k-1}(x-1)^{\tau^{(i)}\mbox{-mch}(\sg)}$. For example, $$\sg = 1~2~3~5~4~7~6~9~8~10~11~12~13~14~15~17~16~18~19$$ is a generalized maximum packing for $\tau^{(1)} = 1324$ where $B_1 =1~2$, $B_2= 3~5~4~7~6~9~8~10$, $B_3 =11~12$, $B_4 = 13~14$ and $B_5 = 15~17~16~18$, and $B_6 =19$. Thus $w(B_1) = w(B_3) =w(B_4) =w(B_6)=1$, $w(B_2) =(x-1)^3$ and $w(B_5) =(x-1)$ so that $w(\sg) = (-1)^5 (x-1)^4 = -(x-1)^4$. We let $\mathcal{GMP}_{2n+1,\tau^{(i)}}$ denote the set of $\sg \in S_{2n+1}$ which are generalized maximum packings for $\tau^{(i)}$. We then let \begin{equation} GMP_{2n+1,\tau^{(i)}}(x) = \sum_{\sg \in \mathcal{GMP}_{2n+1,\tau^{(i)}}} w(\sg). \end{equation} We shall call $GMP_{n,\tau^{(i)}}(x)$ the generalized maximum packing polynomial for $\tau^{(i)}$ of length $n$. In general, it is much more difficult to compute $GMP_{2n,\tau^{(i)}}(x)$ and $GMP_{2n+1,\tau^{(i)}}(x)$ than to compute $\mmp_{2n,\tau^{(i)}}$ and $\mmp_{2n+1,\tau^{(i)}}$. Indeed, we do not have a closed expression for either $GMP_{2n,\tau^{(i)}}(x)$ or $GMP_{2n+1,\tau^{(i)}}(x)$ as a function of $n$ for any $i$. However, we will show that for $i \in \{1,2,4\}$, $GMP_{n,\tau^{(i)}}(x)$ can be computed via simple recursions. For example, we shall show that $GMP_{2,\tau^{(1)}}(x) =1$, $GMP_{4,\tau^{(1)}}(x) =x-2$, and, for $2n > 4$, \begin{multline}\label{t1rec} GMP_{2n,\tau^{(1)}}(x) = \\ C_{n-1}(x-1)^{n-1} -GMP_{2n-2,\tau^{(1)}}(x) - \sum_{k=2}^{n-1} C_{k-1}(x-1)^{k-1} GMP_{2n-2k,\tau^{(1)}}(x). \end{multline} Moreover, we shall show that $GMP_{1,\tau^{(1)}}(x) =1$ and $GMP_{2n+1,\tau^{(1)}}(x) = - GMP_{2n,\tau^{(1)}}(x)$ for $n \geq 1$. Our main theorem is the following. \begin{theorem}\label{thm:main} For $i=1, \ldots, 5$, \begin{equation}\label{eqA} A_{\tau^{(i)}}(t,x) = \frac{1}{1-\sum_{n\geq 1} GMP_{2n,\tau^{(i)}}(x) \frac{t^{2n}}{(2n)!}} \ \mbox{and} \end{equation} \begin{equation}\label{eqB} B_{\tau^{(i)}}(t,x) =\frac{\sum_{n \geq 1} GMP_{2n-1,\tau^{(i)}}(x) \frac{t^{2n-1}}{(2n-1)!}}{1-\sum_{n\geq 1} GMP_{2n,\tau^{(i)}}(x) \frac{t^{2n}}{(2n)!}}. \end{equation} \end{theorem} We shall prove Theorem \ref{thm:main} by applying the so-called homomorphism method which has been developed in a series of papers \cite{BeckRem,b,b2,HR,KNRR,MendesTh,MenRem1,Book,RRW,Wag}. In particular, we shall show that the generating functions in Theorem \ref{thm:main} arise by applying certain ring homomorphisms defined on the ring of symmetric functions $\Lambda$ in infinitely many variables to simple symmetric function identities. For example, let $h_n$ denote $n$th homogeneous symmetric function in $\Lambda$ and $e_n$ denote the $n$th elementary symmetric function in $\Lambda$. That is, $h_n$ and $e_n$ are defined by the generating functions \begin{equation*} H(t) = \sum_{n \geq 0} h_n t^n = \prod_i \frac{1}{1-x_it} \ \mbox{and} \ E(t) = \sum_{n \geq 0} e_n t^n = \prod_i (1+x_it). \end{equation*} Then we shall show that (\ref{eqA}) arises by applying a ring homomorphism $\Theta$ to the simple symmetric function identity that \begin{equation} H(t) = \frac{1}{E(-t)}. \end{equation} The basic idea of the homomorphism method is to show that \begin{equation}\label{key} (2n)!\theta(h_{2n}) = A_{2n,\tau^{(i)}}(x) = \sum_{\sg \in \mathcal{A}_{2n}} x^{\tau^{(i)}\mbox{-mch}(\sg)} \end{equation} for an appropriately chosen ring homomorphism $\theta$. Typically, one proves equations like (\ref{key}) by interpreting the left-hand side of (\ref{key}) in terms of a signed weighted sum of filled brick tabloids and then applying an appropriate sign-reversing weight-preserving involution to show that the combinatorial interpretation of $(2n)!\theta(h_{2n})$ reduces to the desired polynomial. The situation in this paper is a bit different from previous examples of the homomorphism method in that it requires two involutions to show that our combinatorial interpretation of $(2n)!\theta(h_{2n})$ reduces to the right-hand of (\ref{key}). Equation (\ref{eqB}) is proved in a similar manner except that we apply $\theta$ to a more complicated symmetric function identity. The outline of the paper is as follows. In section 2, we shall provide the necessary background in symmetric functions that is necessary for our proofs. In section 3, we shall prove Theorem \ref{thm:main}. In section 4, we shall show how to compute $\mmp_{n,\tau^{(i)}}$ for $i =1,2,3,4,5$. In section 5, we shall develop recursions for $GMP_{n,\tau^{(i)}}(x)$ for $i=1,2,4$. The simplest case is set of the recursions for $GMP_{n,\tau^{(1)}}(x)$ described above. In that case, we shall show that $GMP_{2n,\tau^{(1)}}(0) = (-1)^{n-1}C_n$ for $n \geq 1$ and $GMP_{2n,\tau^{(1)}}(x)|_x = (-1)^n \binom{2n}{n-2}$. Using these facts, we can compute the generating functions for the number of up-down permutations with no $\tau^{(1)}$-matches or with exactly one $\tau^{(1)}$-match. For example, we shall show that $$1 + \sum_{n \geq 1} \frac{t^{2n}}{(2n)!} N_{2n,\tau^{(1)}} = \frac{1}{1+ \sum_{n\geq 1} (-1)^n C_n \frac{t^{2n}}{(2n)!}}$$ where $N_{2n,\tau^{(1)}}$ is the number of $\sg \in \mathcal{A}_{2n}$ with no $\tau^{(1)}$-matches. Finally, in section 6, we shall study the distribution of double rise pairs and double descent pairs in up-down permutations. That is, if $\sg = \sg_1 \ldots \sg_n \in \mathcal{A}_n$ is an up-down permutation, then we say that a pair $(2i-1)(2i)$ is a {\em double rise pair} if both $\sg_{2i-1} < \sg_{2i+1}$ and $\sg_{2i} < \sg_{2i+2}$. Thus $(2i-1)(2i)$ is a double rise pair in $\sg$ if and only if there is a $1324$ match starting at position $2i-1$ in $\sg$. We say that a pair $(2i-1)(2i)$ is a {\em double descent pair} if both $\sg_{2i-1} > \sg_{2i+1}$ and $\sg_{2i} > \sg_{2i+2}$. Thus $(2i-1)(2i)$ is a double descent pair in $\sg$ if and only if there is a $D$-match starting at position $2i-1$ in $\sg$ where $D=\{2413,3412\}$. \section{Symmetric Functions} In this section we give the necessary background on symmetric functions needed for our proofs of the generating functions (\ref{eqA}) and (\ref{eqB}). Let $\Lambda$ denote the ring of symmetric functions over infinitely many variables $x_1, x_2, \ldots $ with coefficients in the field of complex numbers $\mathbb{C}$. Let $\la = (\la_1,\dots,\la_\ell)$ be an integer partition, that is, $\la$ is a finite sequence of weakly increasing nonnegative integers. Let $\ell(\la)$ denote the number of nonzero integers in $\la$. If the sum of these integers is $n$, we say that $\la$ is a partition of $n$ and write $\la \vdash n$. For any partition $\la = (\la_1,\dots,\la_\ell)$, let $e_\la = e_{\la_1} \cdots e_{\la_\ell}$ and $h_\la = h_{\la_1} \cdots h_{\la_\ell}$. The well-known fundamental theorem of symmetric functions says that $\{e_\la : \text{$\la$ is a partition}\}$ is a basis for $\La$ or, equivalently, that $\{e_0,e_1,\ldots \}$ is an algebraically independent set of generators for $\Lambda$. Since $\{e_0,e_1, \ldots \}$ is an algebraically independent set of generators for $\Lambda$, we can specify a ring homomorphism $\theta$ on $\Lambda$ by simply defining $\theta(e_n)$ for all $n \geq 0$. A {\em brick tabloid} of shape $(n)$ and type $\la =(\la_1,\ldots, \la_k)$ is a filling of a row of $n$ squares of cells with bricks of lengths $\la_1, \ldots, \la_k$ such that bricks do not overlap. For example, if $\lambda =(1^2,2^2)$, the six $\lambda$-brick tabloids of shape $(6)$ are pictured in Figure \ref{fig:brickt}. \fig{brickt}{The six brick tabloids of type $(1^2,2^2)$ and shape $(6)$.} Let $\mathcal{B}_{\la,n}$ denote the set of all $\la$-brick tabloids of shape $(n)$ and let $B_{\la,n} =|\mathcal{B}_{\la,n}|$. We shall write $B=(b_1, \ldots, b_k)$ if $B$ is brick tabloid of shape $n$ such that lengths of the bricks in $B$ are $b_1, \ldots, b_k$ as we read from left to right. E\u{g}ecio\u{g}lu and Remmel proved in \cite{ER} that \begin{equation}\label{omar} h_n = \sum_{\la \vdash n} (-1)^{n - \ell(\la)} B_{\la,n} e_\la = \sum_{\la \vdash n} (-1)^{n - \ell(\la)} \sum_{(b_1, \ldots, b_{\ell(\mu)}) \in \mathcal{B}_{\la,n}} \prod_{i=1}^{\ell(\mu)} e_{b_i} \end{equation} Next we define a class of symmetric functions $p_{n,\nu}$ which have a relationship with $e_\lambda$ that is analogous to the relationship between $h_n$ and $e_\lambda$. These functions were first introduced in \cite{LR} and \cite{MendesTh}. Let $\nu$ be a function which maps the set of nonnegative integers into a field $F$. Recursively define $p_{n,\nu} \in \La_n$ by setting $p_{0,\nu} = 1$ and \begin{equation}\label{pnnurec} p_{n,\nu} = (-1)^{n-1} \nu(n) e_n + \sum_{k=1}^{n-1}(-1)^{k-1}e_k p_{n-k,\nu} \ \mbox{for all $n \geq 1$.} \end{equation} By multiplying series, this means that \begin{equation*} \left(\sum_{n \geq 0}(-1)^n e_n t^n \right) \left(\sum_{n \geq 1} p_{n,\nu} t^n \right) = \sum_{n \geq 1} \left ( \sum_{k=0}^{n-1} p_{n-k,\nu} (-1)^k e_k \right ) t^n = \sum_{n \geq 1} (-1)^{n-1} \nu(n) e_n t^n, \end{equation*} where the last equality follows from the definition of $p_{n,\nu}$. Therefore, \begin{equation}\label{fund} \sum_{n \geq 1} p_{n,\nu}t^n = \frac{\sum_{n \geq 1} (-1)^{n-1} \nu(n) e_n t^n} {\sum_{n \geq 0} (-1)^n e_n t^n} \end{equation} or, equivalently, \begin{equation} \label{fund2} 1+ \sum_{n \geq 1} p_{n,\nu}t^n = \frac{1+ \sum_{n \geq 1} (-1)^{n}(e_n - \nu(n) e_n) t^n} {\sum_{n \geq 0} (-1)^n e_n t^n}. \end{equation} When taking $\nu(n) = 1$ for all $n \geq 1$, \eqref{fund2} becomes \begin{equation*} 1 + \sum_{n \geq 1} p_{n,1} t^n = 1 + \frac{\sum_{n \geq 1} (-1)^{n-1} e_n t^n} {\sum_{n \geq 0} (-1)^n e_n t^n} = \frac{1}{\sum_{n \geq 0} (-1)^n e_n t^n} = 1 + \sum_{n \geq 1} h_n t^n \end{equation*} which implies that $p_{n,1} = h_n$ for all $n$. Other special cases for $\nu$ give well-known generating functions. For example, if $\nu(n) = n$ for $n \geq 1$, then $p_{n,\nu}$ is the power symmetric function $\sum_{i} x_i^n$. By taking $\nu(n) = (-1)^k \chi(n \geq k+1)$ for some $k \geq 1$, $p_{n,(-1)^k\chi(n \geq k+1)}$ is the Schur function corresponding to the partition $(1^k,n)$. This definition of $p_{n,\nu}$ is desirable because of its expansion in terms of elementary symmetric functions. The coefficient of $e_\la$ in $p_{n,\nu}$ has a nice combinatorial interpretation similar to that of $h_n$. Suppose $T$ is a brick tabloid of shape $(n)$ and type $\la$ and that the final brick in $T$ has length $\ell$. Define the weight of a brick tabloid $w_{\nu}(T)$ to be $\nu(\ell)$ and let \begin{equation*} w_{\nu}(B_{\la,n}) = \sum_{T \in \mathcal{B}_{\la,n}} w_{\nu}(T). \end{equation*} It was proved in \cite{LR} and \cite{MendesTh} that \begin{equation}\label{pnuexp} p_{n,\nu} = \sum_{\la \vdash n}(-1)^{n-\ell(\la)} w_{\nu}(B_{\lambda,n}) e_\la = \sum_{\la \vdash n} (-1)^{n - \ell(\la)} \sum_{(b_1, \ldots, b_{\ell(\mu)}) \in \mathcal{B}_{\la,n}} \nu(b_{\ell(\mu)}) \prod_{i=1}^{\ell(\mu)} e_{b_i}.\end{equation} \section{The proof of Theorem \ref{thm:main}.} In this section, we shall prove Theorem \ref{thm:main}. We start out by proving (\ref{eqA}). Define a ring homomorphism $\theta$ from $\Lambda$ into $\mathbb{Q}(x)$ by setting $\theta(e_0) =1$, $\theta(e_{2n+1}) = 0$ for all $n \geq 0$, and \begin{equation}\label{theta} \theta(e_{2n}) = \frac{(-1)^{n-1}}{n!} GMP_{2n,\tau^{(i)}}(x) \ \mbox{for all $n \geq 1$.} \end{equation} Then we claim that $\theta(h_{2n-1}) =0$ and \begin{equation}\label{Ah0} (2n)!\theta(h_{2n}) = \sum_{\sg \in \mathcal{A}_{2n}} x^{\tau^{(i)}\mbox{-mch}(\sg)} \end{equation} for all $n \geq 1$. Note that by (\ref{omar}), $$\theta(h_{2n-1}) = \sum_{\mu \vdash 2n-1} (-1)^{2n-1 - \ell(\mu)} B_{\mu,2n-1} \theta(e_{\mu}). $$ Clearly if $\mu$ is partition of $2n-1$, then $\mu$ must have an odd part so that $\theta(e_\mu)=0$. Thus $\theta(h_{2n-1}) =0$ for all $n \geq 1$. Note also that \begin{equation}\label{Ah1} \theta(h_{2n}) = \sum_{\mu \vdash 2n} (-1)^{2n - \ell(\mu)} \sum_{(b_1, \ldots, b_{\ell(\mu)}) \in \mathcal{B}_{\mu,2n}} \prod_{i=1}^{\ell(\mu)} \theta(e_{b_i}) \end{equation} so that there is no loss if we restrict the sum on the right-hand side of (\ref{Ah1}) to partitions $\mu$ where every part of $\mu$ is even, i.e., to partitions of the form $2\la$ where $\la$ is a partition of $n$ and $2\la = (2\la_1, \ldots, 2\la_{\ell(\la)})$ if $\la = (\la_1, \ldots, \la_{\ell(\la)})$. Thus \begin{align} \label{Ah2} (2n)!\theta(h_{2n}) &= (2n)! \sum_{\la \vdash n} (-1)^{2n-\ell(\la)} \sum_{(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,n}} \prod_{j=1}^{\ell(\mu)} \theta(e_{2b_j}) \nonumber \\ &= (2n)! \sum_{\la \vdash n} (-1)^{2n-\ell(\la)} \sum_{(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,n}} \prod_{j=1}^{\ell(\mu)} \frac{(-1)^{2b_j -1}}{(2b_j)!} GMP_{2b_j,\tau^{(i)}}(x) \nonumber \\ &= \sum_{\la \vdash n} \sum_{T =(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,2n}} \binom{2n}{2b_1,\ldots,2b_{\ell(\la)}} \prod_{j =1}^{\ell(\la)} GMP_{2b_j,\tau^{(i)}}(x). \end{align} Next we want to give a combinatorial interpretation to the right-hand side of (\ref{Ah2}). We start with a brick tabloid $T= (2b_1, \ldots, 2b_{\ell(\la)})$ of type $2\la$. Then the binomial coefficient $\binom{2n}{2b_1,\ldots,2b_{\ell(\la)}}$ allows us to pick a set partition $\vec{U} = (U_1, \ldots, U_{\ell(\la)})$ of $\{1, \ldots, 2n\}$ where $|U_i| =2b_i$ for $i =1, \ldots, \ell(\la)$. Next we use the factor $\prod_{j =1}^{\ell(\la)} GMP_{2b_j,\tau^{(i)}}(x)$ to choose a sequence of permutations $\vec{\sg} = (\sg^{(1)}, \ldots, \sg^{(\ell(\la))})$ such that $\sg^{(j)} \in \mathcal{A}_{2\la_j}$ is a generalized maximum packing for $\tau^{(i)}$ for $j =1, \ldots, \ell(\la)$. Then for each $j$, we let $\alpha^{(j)}$ be the sequence that arises by replacing the $r$th largest element of $\sg^{(j)}$ by the $r$th largest element of $U_j$ and then placing these elements in the cells of brick $2b_j$ from left to right. For example, we have pictured this process for $\tau^{(1)} = 1324$ where the underlying brick tableau is $T=(2,8,6)$. We have also indicated the block structure in each brick by underlying those elements in a common block. The weight of such a triple $(T,\vec{U},\vec{\sg})$, $w(T,\vec{U},\vec{\sg})$, is $\prod_{j=1}^{\ell(\la)} w(\sg^{(j)})$. We can interpret $w(T,\vec{U},\vec{\sg})$ by placing a weight $1$ on top of each block of length $2$ that ends a brick and a weight of $-1$ on each block of length 2 which does not end a brick. For blocks of length $\geq 4$, we place a weight of $(x-1)$ at start of each $\tau^{(i)}$-match in the block. Finally, we replace the weight of the first $\tau^{(i)}$-match in a block by $-(x-1)$ if the block is not the last block in its brick. Thus the RHS of (\ref{Ah2}) can be interpreted as the sum of the weights of all triples $(T,\alpha,L)$ such that \begin{enumerate} \item $T= (d_1, \ldots, d_k)$ is brick tabloid of shape $(2n)$ where each brick $d_j$ has even length, \item $\alpha$ is a permutation of $S_{2n}$ such that in each brick $d_j$, the sequence of elements in brick $d_j$ reduces to a permutation in $\mathcal{GMP}_{d_j,\tau^{(i)}}$, and \item $L:\{1,\ldots, 2n\} \rightarrow \mathbb{Q}[x]$ assigns a label to each cell in $T$ where $L(j)$ denotes the label of $j$th cell of $T$, reading from left to right, and \begin{description} \item[(a)] $L(j) =1$ if $j$ is the second cell of a block of length 2 or $j$ does not start a $\tau^{(i)}$-match in a block of length $\geq 4$, \item[(b)] $L(j) =1$ if $j$ is the first cell of block of length 2 which ends a brick and $L(j) =-1$ if $j$ is the first cell of block of length 2 which does not end a brick, \item[(c)] $L(j) =(x-1)$ if $j$ is the first cell of block of length $\geq 4$ which ends a brick and $L(j) =-(x-1)$ if $j$ is the first cell of block of length $\geq 4$ which does not end a brick, and \item[(d)] $L(j) = (x-1)$ if $j$ is a cell which starts a $\tau^{(i)}$-match in a block of length $\geq 6$ which is not the first cell in its block. \end{description} \end{enumerate} We define the weight of $(T,\alpha,L)$, $w(T,\alpha,L)$, to be $\prod_{j=1}^{2n} L(j)$. For example, in Figure \ref{fig:Aexample1}, $T = (2,8,6)$, $\alpha = 1~3~4~5~7~10~9~12~11~13~2~8~6~14~15~16$, and $L$ is the labeling where all the cells which do not have explicit label in them are assumed to have label 1. \fig{Aexample1}{An elements of $\mathcal{T}_{16,\tau^{(1)}}$.} We let $\mathcal{T}_{2n,\tau^{(i)}}$ denote the set of all such triples constructed in this way. It then follows that \begin{equation}\label{Ah3} (2n)!\theta(h_{2n}) = \sum_{(T,\alpha,L) \in \mathcal{T}_{2n,\tau^{(i)}}} w(T,\alpha,L) \end{equation} Next we will define two involutions $I$ and $J$ which will show that RHS of (\ref{Ah3}) is equal to the RHS of (\ref{Ah0}). We define $I:\mathcal{T}_{2n,\tau^{(i)}} \rightarrow \mathcal{T}_{2n,\tau^{(i)}}$ as follows. Suppose that we are given a triple $(T,\alpha,L)$ where $T= (d_1, \ldots, d_k)$. Then read the bricks from left to right until you find the first brick $d_j$ such that either (i) the generalized maximum packing corresponding to the elements in $d_j$ consists of more than one block or (ii) the generalized maximum packing corresponding to the elements in $d_j$ consists of a single block and the last element of $d_j$ is less than the first element of the following brick $d_{j+1}$. In case (i), split $d_j$ into two bricks $d^*$ and $d^{**}$ where $d^*$ contains the cells of the first block in the generalized maximum packing corresponding to the elements in $d_j$ and $d^{**}$ contains the remaining cells of $d_j$. We keep all the labels the same except that we change the label on the first cell of $d^{*}$ from $-1$ to $1$ if the first block of $d_j$ is of length $2$ and from $-(x-1)$ to $(x-1)$ if the first block of $d_j$ has length $\geq 4$. In case (ii), we combine bricks $d_j$ and $d_{j+1}$ into a single brick $d$. Note that since the last element of $d_j$ is less than the first element of $d_{j+1}$, the elements in the new brick $d$ will still reduce to a generalized maximum packing for $\tau^{(i)}$. We keep all the labels the same except that we change the label on the first cell of $d_j$ from $1$ to $-1$ if $d_j$ is of length $2$ and from $(x-1)$ to $-(x-1)$ if $d_j$ has length $\geq 4$. In both cases, we do not change the underlying permutation $\alpha$. If neither case (i) nor case (ii) applies, then $I(T,\alpha,L) = (T,\alpha,L)$. For example, if $(T,\alpha, L)$ is the element of $\mathcal{T}_{16,\tau^{(1)}}$ pictured in Figure \ref{fig:Aexample1}, then we are in case (ii) since we can combine the first and second bricks so that $I(T,\alpha,L)$ is pictured in Figure \ref{fig:Aexample2}. \fig{Aexample2}{The image of $(T,\alpha,L)$ in Figure \ref{fig:Aexample1} under $I$.} It is easy to see that if $I(T,\alpha,L) = (T',\alpha,L') \neq (T,\alpha,L)$, then $I(T',\alpha,L') = (T,\alpha,L)$ and $w(T,\alpha,L) = - w(T',\alpha,L')$. Hence $I$ shows that \begin{eqnarray}\label{Ah4} (2n)!\theta(h_{2n}) &=& \sum_{(T,\alpha,L) \in \mathcal{T}_{2n,\tau^{(i)}}} w(T,\alpha,L) \nonumber \\ &=& \sum_{(T,\alpha,L) \in \mathcal{T}_{2n,\tau^{(i)}}, I(T,\alpha,L) = (T,\alpha,L)} w(T,\alpha,L). \end{eqnarray} Thus we must examine the fixed points of $I$. Clearly, if $(T,\alpha,L)$ is a fixed point of $I$, then the elements of each brick $d$ in $T$ must reduce to a generalized maximum packing of $\tau^{(i)}$ which consists of a single block. Second, we must not be able to combine any two bricks so that if $T=(d_1, \ldots, d_k)$, then the last element of $d_j$ is greater than the first element of $d_{j+1}$ for $j =1, \ldots, k-1$. But this means that the underlying permutation $\alpha$ is an up-down permutation. It follows that the fixed points $I$ consists of triples $(T,\alpha,L)$ such that \begin{description} \item[$(I)$] $\alpha$ is an up-down permutation of length $2n$, \item[$(II)$] $T=(d_1, \ldots, d_k)$ where each $d_j$ has even length and the elements of $d_j$ reduce to a generalized maximum packing of $\tau^{(i)}$ which consists of a single block, and \item[$(III)$] the label of $L(j)$ of the $j$th cell of $T$ is $(x-1)$ if $j$ is the start of $\tau^{(i)}$-match in $\alpha$ and is equal to $1$ otherwise. \end{description} Next we want to modify our interpretation of the right-hand side of (\ref{Ah4}) to consists of all triples $(T',\alpha,L')$ such that \begin{description} \item[$(I')$] $\alpha$ is an up-down permutation of length $2n$, \item[$(II')$] $T=(d_1, \ldots, d_k)$ where each $d_j$ has even length and the elements of $d_j$ reduce to a generalized maximum packing of $\tau^{(i)}$ which consists of a single block, and \item[$(III')$] the label of $L(j)$ of the $j$th cell of $T$ is either $x$ or $-1$ if $j$ is the start of $\tau^{(i)}$-match in $\alpha$ and is equal to $1$ otherwise. \end{description} We let $\mathcal{FI}_{2n,\tau^{(i)}}$ denote the set of triples $(T',\alpha,L')$ satisfying $(I')$-$(III')$ and for any $(T',\alpha,L') \in \mathcal{FI}_{2n,\tau^{(i)}}$, we define the weight of $(T',\alpha,L')$, $w(T',\alpha,L')$, to be $\prod_{j=1}^{2n} L'(j)$. For example, Figure \ref{fig:Aexample3} pictures an element of $\mathcal{FI}_{16,\tau^{(1)}}$ whose weight is $x$ where again the cells which do not have labels are assumed to have label 1. \fig{Aexample3}{An element of $\mathcal{FI}_{16,\tau^{(1)}}$.} It then follows that \begin{equation} \label{Ah5} (2n)!\theta(h_{2n}) = \sum_{(T',\alpha,L') \in \mathcal{FI}_{2n,\tau^{(i)}}} w(T',\alpha,L'). \end{equation} Next we define an involution $J: \mathcal{FI}_{2n,\tau^{(i)}} \rightarrow \mathcal{FI}_{2n,\tau^{(i)}}$. Given an element $(T,\alpha,L) \in \mathcal{FI}_{2n,\tau^{(i)}}$, scan the cells of $T =(d_1, \ldots, d_k)$ from left to right looking for the first brick $d_j$ such that either (A) $d_j$ has a $-1$ label on one of its cells or (B) the elements of $d_j$ and $d_{j+1}$ reduce a generalized maximum packing of $\tau^{(i)}$ which consists of a single block. In case (A), we break $d_j$ into 2 bricks $d^*$ and $d^{**}$ as follows. We know that that there $\tau^{(i)}$-matches starting at cells $1,3, \ldots ,d_j-3$ of $d_j$. Let $c$ be the left most cell of $d_j$ which has a $-1$ label. If $c$ is the first cell of $d_j$, then $d^*$ will consist of the first two cells of $d_j$ and $d^{**}$ will consist of the rest of the cells of $d_j$. If $c$ is not the first cell of $d_j$, then $c$ is the $(2s-1)$th cell of $d_j$ for some $s > 1$. Thus there are $\tau^{(i)}$-matches starting at cell $c-2$ and at cell $c$ of $d_j$ and cell $c-2$ is labeled with $x$. Then we let $d^*$ be the contain the cells of $d_j$ up to and including cell $c+2$ and $d^{**}$ contain the rest of the cells of $d_j$. In either case, we remove the $-1$ label from cell $c$ and replace it by $1$. In case (B), there must a $\tau^{(i)}$-match starting at the second to last cell of $d_j$ that includes the last two cells of $d_j$ and the first two cells of $d_{j+1}$. We then replace replace the bricks $d_j$ and $d_{j+1}$ by a single brick $d$ and replace the label of $1$ on the second to last cell of $d_j$ by $-1$. In either case, we do not change the underlying permutation $\alpha$. If neither case (A) or case (B) applies, then we let $J(T,\alpha,L) =(T,\alpha,L)$. For example, if we consider the $(T,\alpha,L)$ as pictured in Figure \ref{fig:Aexample3}, we cannot combine bricks $d_1$ and $d_2$ because $\alpha$ does not have a $\tau^{(1)}$-match starting cell 1 and we cannot combine bricks $d_2$ and $d_3$ because $\alpha$ does not have a $\tau^{(1)}$-match starting cell 3. Thus we are in case (B) where $d_j =d_3$ and $c =7$. Thus we split $d_3$ at two cells to the right of cell $c$ which means at cell 9. Thus $J(T,\alpha,L) = (T',\alpha,L')$ is pictured in Figure \ref{fig:Aexample4}. Note that it will automatically be the case that the first action that we can take for $(T',\alpha,L')$ is to combine the two bricks that made up the $d_3$ in $(T,\alpha,L)$. \fig{Aexample4}{$J(T,\alpha,L)$ for $(T,\alpha,L)$ of Figure \ref{fig:Aexample3}.} It is easy to see that if $J(T,\alpha,L) = (T',\alpha,L') \neq (T,\alpha,L)$, then $w((T,\alpha,L) = - w(T',\alpha,L')$ and $J(T',\alpha,L') = (T,\alpha,L)$. Thus it follows that \begin{equation} \label{Ah6} (2n)!\theta(h_{2n}) = \sum_{(T,\alpha,L) \in \mathcal{FI}_{2n,\tau^{(i)}}, J(T,\alpha,L) = (T,\alpha,L)} w(T,\alpha,L). \end{equation} Thus we must examine the fixed points of $J$. If $J(T,\alpha,L) = (T,\alpha,L)$, then clearly $(T,\alpha,L)$ can have no cells which have a $-1$ label. Thus in a brick $d$ of $T$ of length $\geq 4$, the start of every $\tau^{(i)}$-match contained in $d$ is labeled with an $x$. Moreover, there cannot be a $\tau^{(i)}$-match that involves cells in two different bricks since otherwise we could combine those two bricks since we would be guaranteed that elements of those two bricks would reduce to a generalized maximum packing for $\tau^{(i)}$ with a single block. Hence $w(T,\alpha,L) = x^{\tau^{(i)}\mbox{-mch}(\alpha)}$ Moreover if we are given an $\alpha \in \mathcal{A}_{2n}$, we can create a fixed point $(T,\alpha,L)$ of $J$ by defining the bricks $d_1, d_2, \ldots $ inductively. That is, we let $d_1$ be of length 2 if there is no $\tau^{(i)}$-match in $\alpha$ starting at 1 and $d_1$ be of length $2s$ if there are $\tau^{(i)}$-matches starting at positions $1,3, \ldots, 2s-3$ but not at $2s-1$ in $\alpha$. Then having defined bricks $d_1, \ldots, d_r$ where $d_r$ ends at cell $c = 2k < 2n$, we let $d_{r+1}$ be of length 2 if there is no $\tau^{(i)}$-match in $\alpha$ starting at $2k+1$ and $d_{r+1}$ be of length $2s$ if there are $\tau^{(i)}$-matches starting at positions $2k+1,2k+3, \ldots, 2k+2s-3$ but not at $2k+2s-1$ in $\alpha$. Hence \begin{equation*}\label{Ah7} (2n)!\theta(h_{2n}) = \sum_{\alpha \in \mathcal{A}_{2n}} x^{\tau^{(i)}\mbox{-mch}(\alpha)}. \end{equation*} It then follows that \begin{align*} \theta(\sum_{n \geq 0} h_n t^n) &= 1+ \sum_{n \geq 1} \frac{t^{2n}}{(2n)!} \sum_{\alpha \in \mathcal{A}_{2n}} x^{\tau^{(i)}\mbox{-mch}(\alpha)} \\ &= \frac{1}{1 + \sum_{n \geq 1}(-t)^n \theta(e_n)} \\ &= \frac{1}{1 - \sum_{n \geq 1} \frac{t^{2n}}{(2n)!}GMP_{2n,\tau^{(i)}}(x)} \end{align*} which is what we wanted to prove. To prove (\ref{eqB}), we need to define an appropriate weight function $\nu:\{1,2, \ldots \} \rightarrow \mathbb{Q}(x)$. That is, we let \begin{equation*}\label{Bp1} \nu(2n-1) =0 \ \mbox{and} \ \nu(2n) = (2n) \frac{GMP_{2n-1,\tau^{(i)}}(x)}{GMP_{2n,\tau^{(i)}}(x)} \ \mbox{for all $n \geq 1$.} \end{equation*} We have designed $\nu$ so that $ \nu(2n)\theta(e_{2n}) = \frac{(-1)^{2n-1}}{(2n-1)!}GMP_{2n-1,\tau^{(i)}}(x)$. Then we claim that for all $n \geq 0$, $\theta(p_{2n+1,\nu}) =0$ and \begin{equation}\label{Bp3} (2n+1)!\theta(p_{2n+2,\nu}) = \sum_{\sg \in \mathcal{A}_{2n+1}} x^{\tau^{(i)}\mbox{-mch}(\sg)}. \end{equation} Note that by (\ref{pnuexp}), $$\theta(p_{2n+1,\nu}) = \sum_{\mu \vdash 2n+1} (-1)^{2n+1 - \ell(\mu)} w_{\nu}(B_{\mu,2n+1}) \theta(e_{\mu}). $$ Clearly if $\mu$ is partition of $2n+1$, then $\mu$ must have an odd part so that $\theta(e_\mu)=0$. Thus $\theta(p_{2n+1,\nu}) =0$ for all $n \geq 0$. It also follows that when we want to compute $\theta(p_{2n+2,\nu})$, we can restrict ourselves to considering partitions of the form $2\la$ where $\la$ is a partition of $n+1$. Thus \begin{align} \label{Bp4} &(2n+1)!\theta(p_{2n+2,\nu}) = (2n+1)! \sum_{\la \vdash n+1} (-1)^{2n+2-\ell(\la)} \sum_{T =(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,2n+2}} \nu(2b_{\ell(\la)}) \theta(e_{2b_{\ell(\la)}}) \times \nonumber \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \prod_{j=1}^{\ell(\la)-1} \theta(e_{2b_j}) \nonumber \\ &= (2n+1)! \sum_{\la \vdash n+1} (-1)^{2n+2-\ell(\la)} \sum_{T =(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,2n+2}} \frac{(-1)^{2b_{\ell(\la)}-1}}{(2b_{\ell(\la)}-1)!} GPM_{2b_{\ell(\la)}-1,\tau^{(i)}} \times \nonumber \\ & \ \ \ \ \ \ \ \ \ \ \ \prod_{j=1}^{\ell(\la)-1} \frac{(-1)^{2b_j -1}}{(2b_j)!} GMP_{2b_j,\tau^{(i)}}(x) \nonumber \\ & = \sum_{\la \vdash n+1} \sum_{T =(2b_1, \ldots, 2b_{\ell(\la)}) \in \mathcal{B}_{2\la,2n+2}} \binom{2n+1}{2b_1,\ldots,2b_{\ell(\la)-1},2b_{\ell(\la)}-1} GPM_{2b_{\ell(\la)}-1,\tau^{(i)}} \times \\ & \ \ \ \ \ \ \ \ \ \ \ \prod_{j =1}^{\ell(\la)-1} GMP_{2b_j,\tau^{(i)}}(x). \nonumber \end{align} As before, we want to give a combinatorial interpretation to the right-hand side of (\ref{Bp4}). We start with a brick tabloid $T= (2b_1, \ldots, 2b_{\ell(\la)})$ of length $2n+2$ and type $2\la$. Then the binomial coefficient $\binom{2n+1}{2b_1,\ldots,2b_{\ell(\la)-1},2b_{\ell(\la)}-1}$ allows us to pick a set partition $\vec{U} = (U_1, \ldots, U_{\ell(\la)})$ of $\{1, \ldots, 2n\}$ where $|U_i| =2b_i$ for $i =1, \ldots, \ell(\la)-1$ and $|U_{\ell(\la)}|=2b_{\ell(\la)}-1$. Next we use the factor $GMP_{2b_{\ell(\la)} -1,\tau^{(i)}}(x) \prod_{j =1}^{\ell(\la)-1} GMP_{2b_j,\tau^{(i)}}(x)$ to choose a sequence of permutations $\vec{\sg} = (\sg^{(1)}, \ldots, \sg^{(\ell(\la))})$ such that $\sg^{(j)} \in \mathcal{A}_{2b_j}$ is a generalized maximum packing for $\tau^{(i)}$ for $j =1, \ldots, \ell(\la)-1$ and $\sg^{(\ell(\la))} \in \mathcal{A}_{2b_{\ell(\la)}-1}$ is a generalized maximum packing for $\tau^{(i)}$. Then for each $j$, we let $\alpha^{(j)}$ be the sequence that arises by replacing the $r$th largest element of $\sg^{(j)}$ by the $r$th largest element of $U_j$ and then placing these elements in the cells of brick $2b_j$ from left to right. This means that for the last brick $2b_{\ell(\la)}$, we will fill in all but the last cell which we leave blank. For example, we have pictured this process for $\tau^{(1)} = 1324$ where the underlying brick tableau $T=(2,8,6)$. We have also indicated the block structure in each brick by underlying those elements in a common block. The weight of such a triple $(T,\vec{U},\vec{\sg})$, $w(T,\vec{U},\vec{\sg})$, is $\prod_{j=1}^{\ell(\la)} w(\sg^{(j)})$. We can interpret $w(T,\vec{U},\vec{\sg})$ by placing a weight $1$ on top of each block of length 1 or $2$ that ends a brick and a weight of $-1$ on each block of length 2 which does not end a brick. For blocks of length $\geq 4$, we place a 2weight of $(x-1)$ at start of each $\tau^{(i)}$-match in the block. Finally, we replace the weight of the first $\tau^{(i)}$-match in the block by $-(x-1)$ if the block is not the last block in its brick. Thus the RHS of (\ref{Bp4}) can be interpreted as the sum of the weights of all triples $(T,\alpha,L)$ such that \begin{enumerate} \item $T= (d_1, \ldots, d_k)$ is brick tabloid of shape $(2n+2)$ where each brick $d_j$ has even length, \item $\alpha$ is a permutation of $S_{2n+1}$ such that in each brick $d_j$ with $j < k$, the elements in brick $d_j$ reduce to a permutation in $\mathcal{GMP}_{d_j,\tau^{(i)}}$ and the elements in brick $d_k$ fill the first $d_k-1$ cells of brick $d_k$ and reduce to a permutation in $\mathcal{GMP}_{d_k-1,\tau^{(i)}}$, and \item $L:\{1,\ldots, 2n+1\} \rightarrow \mathbb{Q}[x]$ assigns a label to each cell in $T$ where $L(j)$ denotes the label of $j$th cell of $T$, reading from left to right, and \begin{description} \item[(a)] $L(j) =1$ if $j$ is the second cell of a block of length 2 or $j$ does not start a $\tau^{(i)}$-match in a block of length $\geq 4$, \item[(b)] $L(j) =1$ if $j$ is the first cell of block of length 1 or 2 which ends a brick and $L(j) =-1$ if $j$ is the first cell of block of length 2 which does not end a brick, \item[(c)] $L(j) =(x-1)$ if $j$ is the first cell of block of length $\geq 4$ which ends a brick and $L(j) =-(x-1)$ if $j$ if the first cell of block of length $\geq 4$ which does not end a brick, and \item[(d)] $L(j) = (x-1)$ if $j$ is a cell which starts a $\tau^{(i)}$-match in a block of length $\geq 6$ which is not the first cell in its block, \end{description} \end{enumerate} where the weight of $(T,\alpha,L)$, $w(T,\alpha,L)$, equals $\prod_{j=1}^{2n+1} L(j)$. For example, in Figure \ref{fig:Bexample1}, $T = (2,8,6)$, $\alpha = 1~4~3~7~5~10~9~12~11~13~2~8~6~14~15$, and $L$ is the labeling where all the cells which do not have explicit label in them are assumed to have label 1. \fig{Bexample1}{An element of $\mathcal{T}_{15,\tau^{(1)}}$.} We let $\mathcal{T}_{2n+1,\tau^{(i)}}$ denote the set of all such triples constructed in this way. It then follows that \begin{equation}\label{Bp5} (2n+1)!\theta(p_{2n+2,\nu}) = \sum_{(T,\alpha,L) \in \mathcal{T}_{2n+1,\tau^{(i)}}} w(T,\alpha,L) \end{equation} Note that the only differences between the fillings of even length in the proof of (\ref{Ah0}) and our current fillings is that, in our current fillings, we have forced that the last brick ends in a block of length 1 and the last cell of that brick is blank. Next we will define two involutions $I$ and $J$ which will show that RHS of (\ref{Bp5}) is equal to the RHS of (\ref{Bp3}). In fact the definitions of $I$ and $J$ are essentially the same as before. We simply observe that the fact that the last block of the final brick is length 1 does not change things. We define $I:\mathcal{T}_{2n+1,\tau^{(i)}} \rightarrow \mathcal{T}_{2n+1,\tau^{(i)}}$ as follows. Given a triple $(T,\alpha,L)$, let $T= (d_1, \ldots, d_k)$. Then read the bricks from left to right until you find the first brick $d_j$ such that either (i) the generalized maximum packing corresponding to the elements in $d_j$ consists of more than one block or (ii) the generalized maximum packing corresponding to the elements in $d_j$ consists of a single block and the last element of $d_j$ is less than the first element of the following block $d_{j+1}$. In case (i), split $d_j$ into two bricks $d^*$ and $d^{**}$ where $d^*$ contains the cells of the first block of the generalized maximum packing corresponding to the elements in $d_j$ and $d^{**}$ contains the remaining cells of $d_j$. We keep all the labels the same except that we change the label on the first cell of $d^*$ from $-1$ to $1$ if the first block of $d_j$ is of length $2$ and from $-(x-1)$ to $(x-1)$ if the first block of $d_j$ has length $\geq 4$. In case (ii), we combine bricks $d_j$ and $d_{j+1}$ into a single brick $d$. Note that since the last element of $d_j$ is less than the first element of $d_{j+1}$, the elements in the new brick $d$ will still reduce to a generalized maximum packing of $\tau^{(i)}$. We keep all the labels the same except that we change the label on the first cell of $d_j$ from $1$ to $-1$ if $d_j$ is of length $2$ and from $(x-1)$ to $-(x-1)$ if $d_j$ has length $\geq 4$. In both cases, we do not change the underlying permutation $\alpha$. If neither case (i) or case (ii) applies, then $I(T,\alpha,L) = (T,\alpha,L)$. For example, if $(T,\alpha, L)$ is the element of $\mathcal{T}_{15,\tau^{(1)}}$ pictured in Figure \ref{fig:Bexample1}, then we are in case (i) since we cannot combine the first and second bricks or the second and third bricks. Thus we break that last brick into two bricks where the final brick of length 2 which has a single block of length 1. $I(T,\alpha,L)$ is pictured in Figure \ref{fig:Bexample2}. \fig{Bexample2}{The image of $(T,\alpha,L)$ in Figure \ref{fig:Bexample1} under $I$.} It is easy to see that if $I(T,\alpha,L) = (T',\alpha,L') \neq (T,\alpha,L)$, then $I(T',\alpha,L') = (T,\alpha,L)$ and $w(T,\alpha,L) = - w(T',\alpha,L')$. Hence $I$ shows that \begin{eqnarray}\label{Bpp} (2n-1)!\theta(p_{2n+2,\nu}) &=& \sum_{(T,\alpha,L) \in \mathcal{T}_{2n+1,\tau^{(i)}}} w(T,\alpha,L) \nonumber \\ &=& \sum_{(T,\alpha,L) \in \mathcal{T}_{2n+1,\tau^{(i)}}, I(T,\alpha,L) = (T,\alpha,L)} w(T,\alpha,L). \end{eqnarray} Again we must examine the fixed points of $I$. Clearly, if $(T,\alpha,L)$ is a fixed point of $I$, then the elements of each brick $d$ in $T$ must reduce to a generalized maximum packing of $\tau^{(i)}$ which consists of a single block. In particular, this means that the last brick of $T$ must be a length 2 and consist of a block with 1 element. Second, we must not be able to combine any two bricks so that if $T=(d_1, \ldots, d_k)$, then the last element of $d_j$ is greater than the first element of $d_{j+1}$ for $j =1, \ldots, k-1$. But this means that the underlying permutation $\alpha$ is an up-down permutation. It follows that the fixed points $I$ consists of triples $(T,\alpha,L)$ such that \begin{description} \item[(I)] $\alpha$ is an up-down permutation of length $2n+1$, \item[(II)] $T=(d_1, \ldots, d_k)$ where each $d_j$ with $j < k$ has even length and the elements of $d_j$ reduces to a generalized maximum packing of $\tau^{(i)}$ which consists of a single block, \item[(III)] $d_k$ is a brick of length 2 which consists of a single block of length 1, and \item[(IV)] the label of $L(j)$ of the $j$th cell of $T$ is $(x-1)$ if $j$ is the start of $\tau^{(i)}$-match in $\alpha$ and is equal to $1$ otherwise. \end{description} Now we can modify our interpretation of the right-hand side of (\ref{Bpp}) and define the involution $J$ exactly as before since the last element in the last brick never played a role in either the modification or the involution $J$. Thus $J$ will show that \begin{equation} \label{Bp6} (2n+1)!\theta(p_{2n+2,\nu}) = \sum_{\alpha \in \mathcal{A}_{2n+1}} x^{\tau^{(i)}\mbox{-mch}(\alpha)}. \end{equation} It then follows that \begin{align}\label{Bp7} \theta(\sum_{n \geq 1} p_{n,\nu} t^n) &= \sum_{n \geq 0} \frac{t^{2n+2}}{(2n+1)!} \sum_{\alpha \in \mathcal{A}_{2n+1}} x^{\tau^{(i)}\mbox{-mch}(\alpha)} \nonumber \\ &= \frac{\sum_{n \geq 1} (-1)^{n-1} \nu(n) \theta(e_n) t^n}{\sum_{n \geq 0} (-1)^n \theta(e_n) t^n} \nonumber \\ &= \frac{\sum_{n \geq 1} \frac{t^{2n}}{(2n-1)!}GMP_{2n-1,\tau^{(i)}}(x)}{1 - \sum_{n \geq 1} \frac{t^{2n}}{(2n)!}GMP_{2n,\tau^{(i)}}(x)}. \end{align} Dividing both sides of (\ref{Bp7}) by $t$ gives (\ref{eqB}) which is what we wanted to prove. \section{Computing $\mmp_{n,\tau^{(i)}}$.} In this section, we shall consider the problem of computing $\mmp_{\tau^{(i)},n}$ since we will need such computations to compute $GMP_{\tau^{(i)},n}$. The problem of computing $\mmp_{\tau^{(i)},2n}$ has been studied by Harmse and Remmel \cite{HR} in a different context. Harmse and Remmel studied maximum packings in column strict arrays. That is, let $\mathcal{F}_{n,k}$ denote the set of all fillings of a $k \times n$ rectangular array with the integers $1, \ldots, kn$ such that the elements increase from bottom to top in each column. We let $(i,j)$ denote the cell in the $i$th row from the bottom and the $j$th column from the left of the $k \times n$ rectangle and we let $F(i,j)$ denote the element in cell $(i,j)$ of $F\in\mathcal{F}_{n,k}$. If $F$ is any filling of a $k \times n$-rectangle with distinct positive integers such that elements in each column increase, reading from bottom to top, then we let $\red{F}$ denote the element of $\mathcal{F}_{n,k}$ which results from $F$ by replacing the $i$th smallest element of $F$ by $i$. For example, Figure \ref{fig:red} demonstrates a filling, $F$, with its corresponding reduced filling, $\red{F}$. \fig{red}{An example of $F\in\mathcal{F}_{3,4}$ and $\red{F}$.} If $F \in \mathcal{F}_{n,k}$ and $1 \leq c_1 < \cdots < c_j \leq n$, then we let $F[c_1,\ldots,c_j]$ be the filling of the $k \times j$ rectangle where the elements in column $a$ of $F[c_1,\ldots,c_j]$ equal the elements in column $c_a$ in $F$ for $a = 1, \ldots, j$. We can then extend the usual pattern matching definitions from permutations to elements of $\mathcal{F}_{n,k}$ as follows. \begin{definition}\label{def1} Let $P$ be an element of $\mathcal{F}_{j,k}$ and $F \in \mathcal{F}_{n,k}$ where $j \leq n$. Then we say \begin{enumerate} \item $P$ {\bf occurs} in $F$ if there are $1 \leq i_1 < i_2 < \cdots < i_j \leq n$ such that \\ $\red{F[i_1, \ldots, i_j]} = P$, \item $F$ {\bf avoids} $P$ if there is no occurrence of $P$ in $F$, and \item there is a {\bf $P$-match in $F$ starting at position $i$} if $\red{F[i,i+1, \ldots, i+j-1]} = P$. \end{enumerate} \end{definition} When $k=1$, then $\mathcal{F}_{n,1}=S_n$, where $S_n$ is the symmetric group, and our definitions reduce to the standard definitions that have appeared in the pattern matching literature. We let $\Pmch{F}$ denote the number of $P$-matches in $F$. For example, if we consider the fillings $P \in \mathcal{F}_{3,3}$ and $F,G \in \mathcal{F}_{6,3}$ shown in Figure \ref{fig:Pmatch}, then it is easy to see that there are no $P$-matches in $F$ but there is an occurrence of $P$ in $F$, since $\red{F[1,2,5]} =P$. Also, there are 2 $P$-matches in $G$ starting at positions 1 and 2, respectively, so $\Pmch{G} =2$. \fig{Pmatch}{Examples of $P$-matches and occurrences of $P$.} If $P \in \mathcal{F}_{2,k}$, then we define $MP_{n}^{P}$ to be the set of $F \in \mathcal{F}_{n,k}$ with $\Pmch{F} = n-1$, i.e. the set of $F \in \mathcal{F}_{n,k}$ with the property that there are $P$-matches in $F$ starting at positions $1,2, \ldots, n-1$. We let $\mmp_n^P = |MP_n^P|$ and, by convention, we define $\mmp_{1}^{P}=1$. For each $\tau^{(i)}$, let $P^{(i)}$ denote the element of $\mathcal{F}_{2,2}$ such that the first and third elements of $\tau^{(i)}$ are the first and second elements in row 1 of $P^{(i)}$, respectively, and the second and forth elements of $\tau^{(i)}$ are the first and second elements in row 2 of $P^{(i)}$, respectively. We have pictured $P^{(1)}, \ldots, P^{(5)}$ in Figure \ref{fig:correspond}. It is then easy to see that given maximum packing $F \in \mathcal{F}_{n,2}$ of $P^{(i)}$, one can construct an up-down permutation $\sg(F) \in \mathcal{A}_{2n}$ which is a maximum packing for $\tau^{(i)}$ by reading each column from bottom to top and the columns from right to left. Vice versa, given $\sg = \sg_1 \ldots, \sg_{2n} \in \mathcal{A}_{2n}$ which is a maximum packing for $\tau^{(i)}$, we can obtain an element $F(\sg) \in \mathcal{F}_{n,2}$ which is a maximum packing for $P^{(i)}$ by placing $\sg_1, \sg_3, \ldots, \sg_{2n-1}$ in the bottom row of $F(\sg)$, reading from left to right, and placing $\sg_2, \sg_4, \ldots, \sg_{2n}$ in the top row of $F(\sg)$, reading from left to right. An example of this correspondence is pictured at the top of Figure \ref{fig:correspond} for $\tau^{(1)} = 1324$ and $P^{(1)} = \begin{array}{|c|c|} \hline 3 & 4 \\ \hline 1 & 2 \\ \hline \end{array}$. \fig{correspond}{The correspondence between $\mathcal{MP}_{2n,\tau^{(i)}}$ and $\mathcal{MP}^{P^{(i)}}_n$.} It follows that for $i=1, \ldots, 5$, $\mmp_{2n,\tau^{(i)}} = \mmp_n^{P^{(i)}}$. Now Harmse and Remmel \cite{HR} proved that for $n \geq 2$, \begin{eqnarray*} \mmp_n^{P^{(1)}}&=& \mmp_n^{P^{(4)}}= C_{n-1} \ \mbox{and} \\ \mmp_n^{P^{(2)}}&=& \mmp_n^{P^{(3)}}= \mmp_n^{P^{(5)}}= 1. \end{eqnarray*} Thus we obtain the following theorem. \begin{theorem} For all $n \geq 2$, $\displaystyle \mmp_{2n,\tau^{(1)}}= \mmp_{2n,\tau^{(4)}}= C_{n-1}$ and \\ $\displaystyle \mmp_{2n,\tau^{(2)}} = \mmp_{2n,\tau^{(3)}}= \mmp_{2n,\tau^{(5)}}= 1$. \end{theorem} Our next goal is to prove the following. \begin{theorem} For all $n \geq 2$, $\displaystyle \mmp_{2n+1,\tau^{(1)}} = (2n)C_{n-1}$, $\displaystyle \mmp_{2n+1,\tau^{(2)}} = 2n$,\\ $\displaystyle \mmp_{2n+1,\tau^{(3)}}= C_{n-1} +C_n$, $\displaystyle \mmp_{2n+1,\tau^{(4)}} = n+1$ and $\displaystyle mmp_{2n+1,\tau^{(5)}}= 2$. \end{theorem} To compute $\mmp_{2n+1,\tau^{(i)}}$, we must exploit some of the techniques used by Harmse and Remmel \cite{HR} to compute $\mmp^{P}_n$ for $P \in \mathcal{F}_{2,k}$. To help us visualize the order relationships within $P^{(i)}$, we form a directed graph $G_{P^{(i)}}$ on the cells of the $2 \times 2$ rectangle by drawing a directed edge from the position of the number $j$ to the position of the number $j+1$ in $P$ for $j =1, \ldots, 3$. For example, in Figure \ref{fig:P1}, the graph $G_{P^{(1)}}$ is pictured immediately to the right $P^{(1)}$. Then $G_{P^{(i)}}$ determines the order relationships between all the cells in $P^{(i)}$ since $P^{(i)}(r,s) \alpha_{2n+1}$. We let $G^+_{n,P^{(i)}}$ denote this extended graph. For example, the graph $G^+_{6,P^{(1)}}$ is pictured in the third line of Figure \ref{fig:P1}. It follows that $\mmp_{2n+1,\tau^{(i)}}$ equals the number of linear extensions of $W_{G^+_{n,P^{(i)}}}$. Next we state a simple lemma about directed acyclic graphs with no multiple edges due to Harmse and Remmel \cite{HR} which will allow us to replace $G_{n,P^{(i)}}$ and $G^+_{n,P^{(i)}}$ by a simpler acyclic directed graphs which contains the same information about their associated posets $W_{G_{n,P^{(i)}}}$ and $W_{G^+_{n,P^{(i)}}}$. Given a directed acyclic graph $G = (V,E)$ with no multiple edges, let $Con(G)$ equal the set of all pairs $(i,j) \in V \times V$ such that there is a directed path in $G$ from vertex $i$ to vertex $j$. \begin{lemma} \label{lem:remove} Let $G = (V,E)$ be a directed acyclic graph with no multiple edges. Let $H$ be the subgraph of $G$ that results by removing all edges $e=(i,j) \in E$ such that there is a directed path from $i$ to $j$ in $G$ that does not involve $e$. Then $Con(G) = Con(H)$. \end{lemma} First consider the problem of computing $\mmp_{2n+1,P^{(1)}}$ for $n \geq 2$. In this case, let $a$ be the rightmost element in the top row of $G_{n,P^{(1)}}$. Since there is a directed path in $G_{n,P^{(1)}}$ from every element other than $a$ to $a$, it must be the case that $a$ is the last element in any linear extension of $W_{G_{n,P^{(1)}}}$ and, hence, in any $F \in \mathcal{MP}^{P^{(1)}}_n$, $F(a) = 2n$. Note that same thing happens in $G^+_{n,P^{(1)}}$. That is, there is a directed path in $G^+_{n,P^{(1)}}$ from every element other than $a$ to $a$. Thus it must be the case that $a$ is the last element in any linear extension of $W_{G^+_{n,P^{(1)}}}$ so that $a$ would be assigned the label $2n+1$ in any linear extension. But then it easy to see that $b$ can be assigned any element in $\{1, \ldots, 2n\}$. Thus once we pick the value assigned $b$, then the number of linear extensions of $G^+_{n,P^{(1)}}$ just reduces to the number of linear extensions of $G_{n,P^{(1)}}$ which is $C_{n-1}$. Thus $\mmp_{2n+1,\tau^{(1)}} = (2n)C_{n-1}$. \fig{P2}{The graphs $G_{n,P^{(2)}}$ and $G^+_{n,P^{(2)}}$.} In Figure \ref{fig:P2}, we have pictured the graphs of $G_{6,P^{(2)}}$ and $G^+_{6,P^{(2)}}$ on the left in the second and third lines, respectively. In both cases, one can use Lemma \ref{lem:remove} to show that we can remove all the vertical arrows in these graphs except the leftmost vertical arrow with out loosing any information about the number of linear extensions. Let $\overline{G}_{n,P^{(2)}}$ and $\overline{G}^+_{n,P^{(2)}}$ denote the resulting graphs obtained from $G_{n,P^{(2)}}$ and $G^+_{n,P^{(2)}}$, respectively. In this case, it is easy to see that in a linear extension of $G_{n,P^{(2)}}$, the rightmost top element $a$ must be the largest element $2n$ since there is a directed path in $G_{n,P^{(2)}}$ from every element other than $a$ to $a$. The same thing happens in $G^+_{n,P^{(2)}}$, namely $2n+1$ must be assigned to $a$ since there is a directed path in $G^+_{n,P^{(2)}}$ from every element other than $a$ to $a$. But then it easy to see that $b$ can be assigned to any element in $\{1, \ldots, 2n\}$. Thus once we pick a value that is assigned to $b$, then the number of linear extensions of $G^+_{n,P^{(2)}}$ just reduces to the number of linear extension of $G_{n,P^{(2)}}$ which is clearly just 1. Thus $\mmp_{2n+1,\tau^{(2)}} = 2n$. \fig{P3}{The graphs $G_{n,P^{(3)}}$ and $G^+_{n,P^{(3)}}$.} In Figure \ref{fig:P3}, we have pictured the graphs of $G_{6,P^{(3)}}$ and $G^+_{6,P^{(3)}}$ on the second line. Now consider the element $b$ in $G^+_{n,P^{(3)}}$. If we assign $b$ the value 1, then there is no restriction on the linear extensions of the remaining elements so that we get a total of $C_{n-1}$ linear extensions in that case since $\mmp_{n,P^{(3)}} =C_{n-1}$. However, if $b >1$, then it is easy to see that rightmost bottom element must be the first element in any linear extension since there is a directed path from that element to any other element which not equal to $b$. Thus the rightmost bottom element must be assigned to 1. It then follows that we can extend the graph $G^+_{n,P^{(3)}}$ to a graph $G^{++}_{n,P^{(3)}}$ by adding a new element $0$ and adding new directed edges connecting 0 to 1 and 1 to $b$. This process is pictured on line 4 of Figure \ref{fig:P3}. It is easy to see that the number of linear extensions of $G^+_{n,P^{(3)}}$ where $b > 1$ is just the number of linear extensions of $G^{++}_{n,P^{(3)}}$ which is the same as the number of linear extensions of $G_{n+1,P^{(3)}}$. Since the number of linear extensions of $G_{n+1,P^{(3)}}$ is $C_n$, it follows that $\mmp_{2n+1,\tau^{(3)}} = C_{n-1} + C_{n}$. \fig{P4}{The graphs $G_{n,P^{(4)}}$ and $G^+_{n,P^{(4)}}$.} In Figure \ref{fig:P4}, we have pictured the graphs of $G_{6,P^{(4)}}$ and $G^+_{6,P^{(4)}}$ on the left in the second and third lines, respectively. In both cases, one can use Lemma \ref{lem:remove} to show that we can remove all the vertical arrows in the graphs except the rightmost vertical arrow with out loosing any information about the number of linear extensions $W_{G_{6,P^{(4)}}}$ and $W_{G^+_{6,P^{(4)}}}$. Let $\overline{G}_{n,P^{(4)}}$ and $\overline{G}^+_{n,P^{(4)}}$ denote the resulting graphs obtained from $G_{n,P^{(2)}}$ and $G^+_{n,P^{(2)}}$, respectively. In this case, it is easy to see that in any linear extension of $W_{G_{n,P^{(4)}}}$, the rightmost top element $a$ of $G_{n,P^{(4)}}$ must be $(n+1)$st element in the linear extension of $W_{G_{6,P^{(4)}}}$ since there are $n$ elements $x$ for which there is a directed path in $\overline{G}_{n,P^{(4)}}$ from $x$ to $a$ and there are $n-1$ elements $y$ such that there is a directed path from $a$ to $y$ in $\overline{G}_{n,P^{(4)}}$. The same thing happens in $\overline{G}^+_{n,P^{(4)}}$, namely $a$ must be the $(n+2)$nd element in any linear extension of $W_{G^+_{6,P^{(4)}}}$ since there are $n+1$ elements $x$ for which there is a directed path in $\overline{G}^+_{n,P^{(4)}}$ from $x$ to $a$ and there are $n-1$ elements $y$ such that there is a directed path from $a$ to $y$ in $\overline{G}^+_{n,P^{(4)}}$. Hence we can assign $b$ to be any element from $1, \ldots ,n+1$. Once we pick a value for $b$, then the number of linear extensions of $\overline{G}^+_{n,P^{(4)}}$ just reduces to the number of linear extensions of $\overline{G}_{n,P^{(4)}}$ which is clearly just 1. Thus $\mmp_{2n+1,\tau^{(4)}} = n+1$. \fig{P5}{The graphs $G_{n,P^{(5)}}$ and $G^+_{n,P^{(5)}}$.} In Figure \ref{fig:P5}, we have pictured the graphs of $G_{6,P^{(5)}}$ and $G^+_{6,P^{(5)}}$ on the left in the second and third lines, respectively. In the case of $G^+_{n,P^{(5)}}$, it is easy to see that the rightmost top element $a$ must be the third element in the linear extension of $W_{G^+_{6,P^{(5)}}}$. Thus we have two linear extensions depending how we order the two elements connected to $a$. Hence $\mmp_{2n+1,P^{(5)}}=2$. \section{Computing $GMP_{n,\tau^{(i)}}(x)$.} In this section, we shall study the problem of computing $GMP_{n,\tau^{(i)}}(x)$ for $n \geq 1$ and $i=1, \ldots, 5$. First it is easy to see that for any $i$, \begin{eqnarray*} GMP_{1,\tau^{(i)}}(x) &=& GMP_{2,\tau^{(i)}}(x) = 1, \\ GMP_{3,\tau^{(i)}}(x) &=& -1, \ \mbox{and}\\ GMP_{4,\tau^{(i)}}(x) &=& x-2. \end{eqnarray*} That is, there is only one generalized maximum packing of length 1 which consists of block of length 1 and weight 1. Similarly, there is only one generalized maximum packing of length 2 which consists of block of length 2 and weight 1. There is only one generalized maximum packings of length 3, namely, $123$ where $12$ is block of length 2 and $3$ is block of length one. Thus $GMP_{3,\tau^{(i)}} = w(123) = -1$. There are two generalized maximum packings of length 4, namely, $1234$ which consists of two blocks of length 2 and has weight $-1$ and $\tau^{(i)}$ which consists of single block with weight $x-1$. Thus $GMP_{4,\tau^{(i)}} = x-2$. In general, we do not know how to find closed formulas for $GMP_{n,\tau^{(i)}}(x)$ as function of $n$, but there are several cases where there are simple recursions for computing $GMP_{n,\tau^{(i)}}(x)$. The easiest case is for $\tau^{(1)} = 1324$. \begin{theorem} For $n \geq 3$, \begin{multline}\label{tau1rec} GMP_{2n,\tau^{(1)}}(x) = \\ C_{n-1}(x-1)^{n-1} - GMP_{2n-2,\tau^{(1)}}(x) - \sum_{k=2}^{n-1} C_{k-1}(x-1)^{k-1}GMP_{2n-2k,\tau^{(i)}}(x) \end{multline} and, for $n \geq 2$, $\displaystyle GMP_{2n+1,\tau^{(1)}}(x) =-GMP_{2n,\tau^{(1)}}(x)$. \end{theorem} It then follows from (\ref{eqB}) that we have the following corollary. \begin{corollary} \begin{equation} B_{\tau^{(1)}}(t,x) =\frac{t-\sum_{n \geq 1} GMP_{2n,\tau^{(1)}}(x) \frac{t^{2n+1}}{(2n+1)!}}{1-\sum_{n\geq 1} GMP_{2n,\tau^{(1)}}(x) \frac{t^{2n}}{(2n)!}}. \end{equation} \end{corollary} \begin{proof} It is easy to see from the form of the graphs $G_{2n,P^{(1)}}$ that any maximum packing $\sg \in \mathcal{MP}_{2n,\tau^{(1)}}$ must start with 1 and end with $2n$. It follows that if $\sg = \sg_1 \ldots \sg_{2n} \in \mathcal{GMP}_{2n,\tau^{(1)}}$ with block structure $B_1\ldots B_k$, then for each $i < k$, the elements in $B_1 \ldots B_i$ is a rearrangement of the elements $\{1, \ldots, \sum_{j=1}^k |B_i|\}$. That is, for each $1 \leq i < k$, we know that the last element of $B_i$ which is the largest element in $B_i$ is less than the first element of $B_{i+1}$ which is the smallest element in $B_{i+1}$. Thus all the elements of $B_i$ are smaller than any element in $B_{i+1}$. Now suppose that $n \geq 3$ and $\sg = \sg_1 \ldots \sg_{2n} \in \mathcal{GMP}_{2n,\tau^{(1)}}$. There are three possibilities.\\ \ \\ {\bf Case 1.} $\sg$ consists of a single block. \\ In this case $\sg$ is a maximum packing of $\tau^{(1)}$ and $w(\sg) = (x-1)^{n-1}$. Since $\mmp_{2n,\tau^{(i)}} = C_{n-1}$, the contribution of the permutations in case 1 to $GMP_{2n,\tau^{(1)}}(x)$ is $C_{n-1}(x-1)^{n-1}$. \\ \ \\ {\bf Case 2.} $\sg$ has block structure $B_1 \ldots B_s$ where $s \geq 2$ and $B_1$ is of length 2. \\ In this case $B_1 =12$ and has weight $-1$ and $\red{B_2 \ldots B_s}$ is a generalized maximum packing for $\tau^{(1)}$ of length $2n-2$. Hence the contribution of the permutations in case 2 to $GMP_{2n,\tau^{(1)}}(x)$ is $-GMP_{2n-2,\tau^{(1)}}(x)$.\\ \ \\ {\bf Case 3.} $\sg$ has block structure $B_1 \ldots B_s$ where $s \geq 2$ and $B_1$ has length $>2$. \\ In this case, $B_1 =1\ldots 2k$ is a maximum packing for $\tau^{(1)}$ of length $2k$ for some $2 \leq k \leq n-1$ which has weight $-(x-1)^{k-1}$ and $\red{B_2 \ldots B_s}$ is a generalized maximum packing of length $2n-2k$. If $2 \leq k \leq n-1$, then there are $C_{k-1}$ choices for $B_1$. Hence the contribution of the permutations in case 2 to $GMP_{2n,\tau^{(1)}}(x)$ is $-\sum_{k=2}^{n-1} C_{k-1}(x-1)^{k-1} GMP_{2n-2k,\tau^{(1)}}(x)$.\\ \ \\ Thus for $n \geq 3$, (\ref{tau1rec}) holds. It is also easy to compute $GMP_{2n+1,\tau^{(1)}}(x)$. That is, since a generalized maximum packing $\sg \in \mathcal{A}_{2n+1}$ has block structure $B_1 \ldots B_k$ where $B_k$ has length 1 and $B_1 \ldots B_{k-1}$ reduces to a generalized maximum packing for $\tau^{(1)}$ of length $2n$, we know that the last element of $B_{k-1}$ is the largest element in $B_1 \ldots B_{k-1}$ and hence the element in $B_k$ must be $2n+1$. Thus in this case $GMP_{2n+1,\tau^{(1)}}(x) = - GMP_{2n,\tau^{(1)}}(x)$. \end{proof} Here is list of the first few values of $GMP_{2n,\tau^{(1)}}(x)$. \begin{eqnarray*} GMP_{2,\tau^{(1)}}(x) &=& 1 \\ GMP_{4,\tau^{(1)}}(x) &=& -2+x \\ GMP_{6,\tau^{(1)}}(x) &=& 5-6 x+2 x^2 \\ GMP_{8,\tau^{(1)}}(x) &=& -14+28 x-20 x^2+5 x^3 \\ GMP_{10,\tau^{(1)}}(x) &=& 42-120 x+135 x^2-70 x^3+14 x^4 \\ GMP_{12,\tau^{(1)}}(x) &=& -132+495 x-770 x^2+616 x^3-252 x^4+42 x^5 \\ GMP_{14,\tau^{(1)}}(x) &=& 429-2002 x+4004 x^2-4368 x^3+2730 x^4-924 x^5+132 x^6 \\ GMP_{16,\tau^{(1)}}(x) &=& -1430+8008 x-19656 x^2+27300 x^3-23100 x^4+\\ &&11880 x^5-3432 x^6+429 x^7 \end{eqnarray*} Plugging these values into the generating functions (\ref{eqA}) and (\ref{eqB}) and using Mathematica, we have computed the following table of values of $A_{n,\tau^{(1)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(1)}\mbox{-mch}(\sg)}$. \\ \ \\ \begin{tabular}{|l|l|} \hline $A_{1,\tau^{(1)}}$ & 1 \\ \hline $A_{2,\tau^{(1)}}$ & 1 \\ \hline $A_{3,\tau^{(1)}}$ & 2 \\ \hline $A_{4,\tau^{(1)}}$ & $4+x$ \\ \hline $A_{5,\tau^{(1)}}$ & $12+4 x$\\ \hline $A_{6,\tau^{(1)}}$ & $35+24x+2x^2$ \\ \hline $A_{7,\tau^{(1)}}$ & $142+118 x+12 x^2$ \\ \hline $A_{8,\tau^{(1)}}$ & $546+672 x+162 x^2+5 x^3$ \\ \hline $A_{9,\tau^{(1)}}$ & $2816+3968 x+1112 x^2+40 x^3$ \\ \hline $A_{10,\tau^{(1)}}$ & $13482+24660 x+11145 x^2+1220 x^3+14 x^4$ \\ \hline $A_{11,\tau^{(1)}}$ & $84764+170996 x+87200 x^2+10666 x^3+168 x^4$ \\ \hline \end{tabular}\\ \ \\ In this case, we can find explicit generating functions for the number of $\sg$ in $\mathcal{A}_n$ which have no $\tau^{(1)}$-matches. That is, we claim that $G_{2m,\tau^{(1)}}(0) = (-1)^{m-1}C_m$ for $m \geq 1$. This is clear for $m =1$ and $m=2$. Now if $n > 2$ and we assume that $G_{2m,\tau^{(1)}}(0) = (-1)^{m-1}C_m$ for $m < n$, then by (\ref{tau1rec}), we have \begin{align*} GMP_{2n,\tau^{(1)}}(0) &= C_{n-1}(-1)^{n-1} - GMP_{2n-2,\tau^{(i)}}(0) - \sum_{k=2}^{n-1} C_{k-1}(x-1)^{k-1}GMP_{2n-2k,\tau^{(i)}}(0)\\ &= C_{n-1}(-1)^{n-1} - (-1)^{n-2}C_{n-1} - \sum_{k=2}^{n-1} C_{k-1}(-1)^{k-1}(-1)^{n-k-1}C_{n-k}\\ &= (-1)^{n-1}(\sum_{k=1}^{n} C_{k-1}C_{n-k}) = (-1)^{n-1}C_n \end{align*} Thus if we let $N_{n,\tau^{(i)}} = A_{n,\tau^{(i)}}(0)$ be the number of $\sg \in \mathcal{A}_n$ with no $\tau^{(i)}$-matches, then by setting $x=0$ in (\ref{eqA}) and (\ref{eqB}) we obtain that \begin{equation}\label{Ntau1e} 1 + \sum_{n \geq 1} N_{2n,\tau^{(1)}} \frac{t^{2n}}{(2n)!} = \frac{1}{1 + \sum_{n \geq 1} (-1)^n C_n \frac{t^{2n}}{(2n)!}} \end{equation} and \begin{equation}\label{Ntau1o} \sum_{n \geq 0} N_{2n+1,\tau^{(1)}} \frac{t^{2n+1}}{(2n+1)!} = \frac{t+\sum_{n \geq 1} (-1)^n C_n\frac{t^{2n+1}}{(2n+1)!}}{1 + \sum_{n \geq 1} (-1)^n C_n \frac{t^{2n}}{(2n)!}}. \end{equation} We also claim that \begin{equation} GMP_{2n,\tau^{(1)}}(x)|_{x} = (-1)^n \binom{2n}{n-2} \ \mbox{for } n \geq 2. \end{equation} That is, $GMP_{4,\tau^{(1)}}(x)|_{x} =1$ so the formula holds for $n =2$. For $n > 2$, we have that $$GMP_{2n,\tau^{(1)}}(x) = C_{n-1}(x-1)^{n-1} - GMP_{2n2,\tau^{(1)}}(x) - \sum_{k=1}^{n-2} C_k (x-1)^k GMP_{2n-2k-2,\tau^{(1)}}(x).$$ Taking the coefficient of $x$ on both sides and using induction, we see that \begin{align*} GMP_{2n,\tau^{(1)}}(x)|_x = &\frac{1}{n}\binom{2n-2}{n-1}(n-1)(-1)^{n-2} - (-1)^{n-1}\binom{2n-2}{n-3} - \\ &\sum_{k=1}^{n-2} (C_k (x-1)^k|)_x (GMP_{2n-2k-2,\tau^{(1)}}(x))|_{x^0} - \\ &\sum_{k=1}^{n-2} (C_k (x-1)^k)|_{x^0} (GMP_{2n-2k-2,\tau^{(1)}}(x))|_{x}. \end{align*} Since $GMP_{2,\tau^{(1)}}(x)|_x =0$, we see by induction that \begin{align*} GMP_{2n,\tau^{(1)}}(x)|_x = &(-1)^n \binom{2n-2}{n-2} + (-1)^{n}\binom{2n-2}{n-3} - \\ &\sum_{k=1}^{n-2} \frac{1}{k+1}\binom{2k}{k}k(-1)^{k-1} (-1)^{n-k-2}\frac{1}{n-k}\binom{2n-2k-2}{n-k-1} - \\ &\sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k}(-1)^k (-1)^{n-k-1} \binom{2n-2k-2}{n-k-3}. \end{align*} Observe that $\binom{2n-1}{n-2} = \binom{2n-2}{n-2} + \binom{2n-2}{n-3}$ and $\frac{1}{k+1}\binom{2k}{k}k =\binom{2k}{k-1}$. Thus if we multiply both sides of our previous equation by $(-1)^n$ and use these observations, we see that \begin{align*} (-1)^n GMP_{2n,\tau^{(1)}}(x)|_x = &\binom{2n-1}{n-2} + \sum_{k=1}^{n-2} \frac{1}{n-k} \binom{2k}{k-1}\binom{2n-2k-2}{n-k-1} + \\ &\sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k}\binom{2n-2k-2}{n-k-3}\\ \end{align*} Replacing $k$ by $n-k-1$ in the first sum we see that \begin{align*} \sum_{k=1}^{n-2} \frac{1}{n-k} \binom{2k}{k-1}\binom{2n-2k-2}{n-k-1} &= \sum_{k=1}^{n-2} \frac{1}{k+1} \binom{2k}{k}\binom{2n-2k-2}{n-k-2} \\ &= \frac{1}{n-1}\binom{2n-4}{n-2}+\sum_{k=1}^{n-3} \frac{1}{k+1} \binom{2k}{k}\binom{2n-2k-2}{n-k-2}. \end{align*} Thus we are reduced to showing that \begin{align*} &\binom{2n}{n-2} = \binom{2n-1}{n-2} + \frac{1}{n-1}\binom{2n-4}{n-2} + \\ &\sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k} \left(\binom{2n-2k-2}{n-k-2} + \binom{2n-2k-2}{n-k-3}\right) \\ &= \binom{2n-1}{n-2} + \frac{1}{n-1}\binom{2n-4}{n-2} + \sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k} \binom{2n-2k-1}{n-k-2}. \end{align*} Thus to complete our induction, we need only show that \begin{equation*}\label{coefxtau1} \binom{2n-1}{n-3} = \frac{1}{n-1}\binom{2n-4}{n-2}+ \sum_{k=1}^{n-3} \frac{1}{k+1}\binom{2k}{k} \binom{2n-2k-1}{n-k-2} \end{equation*} which can be verified by using the FullSimplify command in Mathematica. We can now use the fact that $GMP_{2n,\tau^{(1)}}(x)|_x = (-1)^n \binom{2n}{n-2}$ for $n \geq 2$ to compute the generating function of the number of $\sg \in \mathcal{A}_{n}$ with exactly one $\tau^{(1)}$-match. That is, let \begin{eqnarray*} R(t) &=& \sum_{n \geq 1} (-1)^{n-1}C_n \frac{t^{2n}}{(2n)!}, \\ S(t) &=& \sum_{n \geq 2} (-1)^{n}\binom{2n}{n-2} \frac{t^{2n}}{(2n)!},\\ U(t) &=& \sum_{n \geq 1} (-1)^{n-1}C_n \frac{t^{2n+1}}{(2n+1)!}, \ \mbox{and} \\ V(t) &=& \sum_{n \geq 2} (-1)^{n}\binom{2n}{n-2} \frac{t^{2n+1}}{(2n+1)!}. \end{eqnarray*} Then we know that \begin{eqnarray*} A_{\tau^{(1)}}(t,x) &=& \frac{1}{1 - R(t) - xS(t) + O(x^2)} \ \mbox{and} \\ B_{\tau^{(1)}}(t,x) &=& \frac{t-U(t)-xV(t) +O(x^2)}{1 - R(t) - xS(t) + O(x^2)}. \end{eqnarray*} It follows that \begin{eqnarray} A_{\tau^{(1)}}(t,x)|_x &=&\left( 1+ \sum_{n\geq 1} (R(t) + xS(t))^n\right)|x = \sum_{n\geq 1} nS(t)(R(t))^{n-1} \nonumber \\ &=& S(t) \frac{d}{dt}\frac{1}{1-R(t)} = \frac{S(t)\frac{d}{dt}R(t)}{(1-R(t))^2}. \end{eqnarray} Similarly, one can compute that \begin{eqnarray} B_{\tau^{(1)}}(t,x)|_x &=& \frac{(t -U(t)) S(t)\frac{d}{dt}R(t)}{(1-R(t))^2} + \frac{V(t)}{1 -R(t)} \nonumber \\ &=& \frac{V(t)(1-R(t))+ (t -U(t))S(t)\frac{d}{dt}R(t)}{(1-R(t))^2}. \end{eqnarray} Next we consider $GMP_{n,\tau^{(2)}}(x)$. \begin{theorem} For $n \geq 3$, \begin{equation}\label{tau2rec} GMP_{2n,\tau^{(2)}}(x) = (x-1)^{n-1} - GMP_{2n-2,\tau^{(2)}}(x) - \sum_{j=2}^{n-1} \binom{2n-j-1}{j-1}GMP_{2n-2j,\tau^{(2)}}(x). \end{equation} and, for $n \geq 2$, $\displaystyle GMP_{2n+1,\tau^{(2)}}(x) = -GMP_{2n,\tau^{(2)}}(x)$. \end{theorem} Again it follows from (\ref{eqB}) that we have the following corollary. \begin{corollary} \begin{equation} B_{\tau^{(2)}}(t,x) =\frac{t-\sum_{n \geq 1} GMP_{2n,\tau^{(2)}}(x) \frac{t^{2n+1}}{(2n+1)!}}{1-\sum_{n\geq 1} GMP_{2n,\tau^{(2)}}(x) \frac{t^{2n}}{(2n)!}}. \end{equation} \end{corollary} \begin{proof} It is clear from the graph $G_{n,P^{(2)}}$ that in the unique maximum packing $\sg = \sg_1 \ldots \sg_{2n} \in \mathcal{A}_{2n}$ for $\tau^{(2)}$, $\sg_2 \sg_4 \ldots \sg_{2n} = (n+1)(n+2) \ldots (2n)$ and $\sg_1 \sg_3 \ldots \sg_{n} = n(n-1)(n-2) \ldots 1$. It follows that in a generalized maximum packing $\alpha \in S_{2n}$ with block structure $B_1 \ldots B_k$ that the last element of each block $B_i$ is the largest element in the block. Hence if $B_k$ is length two then, its two elements must be $(2n-1)$ and $(2n)$ since they must be larger than all the largest elements in each block $B_i$ for $i \neq k$. In that case $B_1 \ldots B_{k-1}$ is just a generalized maximum packing for $\tau^{(2)}$ of length $2n-2$ whose weight is $-w(\sg)$. If $B_k = \sg_{2n-2j+1} \ldots \sg_{2n}$ reduces to a maximum packing for $\tau^{(2)}$ of length $2j$ where $2 \leq j \leq n-1$, then it must be the case $\sg_{2n-2j+1}< \sg_{2n-2j+2} < \sg_{2n-2j+4} < \cdots < \sg_{2n}$ must be the $j+1$ largest elements from $\{1,\ldots, 2n\}$ since they will be larger than all the remaining elements of $B_k$ and larger than the largest element of $B_i$ for $i \neq k$. It follows that first element of block $B_k$ is $(2n-j)$. Our conditions for a generalized maximum packing for $\tau^{(2)}$ do not impose any relations between the remaining elements of $B_k$, namely $\sg_{2n-2j+3},\sg_{2n-2j+5}, \ldots , \sg_{2n-1}$, and the elements in blocks $B_1, \ldots, B_{k-1}$. Thus we have $\binom{2n-j-1}{j-1}$ ways to choose those elements. Once we have chosen those elements, then $B_1 \ldots B_{k-1}$ must reduce to a generalized maximum packing for $\tau^{(2)}$ of length $2n-2j$. Thus by classifying the elements of $\mathcal{GMP}_{2n,\tau^{(2)}}$ by the length of the last block, one can prove that (\ref{tau2rec}) holds. Again, it is easy to compute $GMP_{2n+1,\tau^{(2)}}(x)$. That is, since a generalized maximum packing $\sg \in \mathcal{A}_{2n+1}$ has block structure $B_1 \ldots B_k$ where $B_k$ has length 1 and $B_1 \ldots B_{k-1}$ reduces to a generalized maximum packing for $\tau^{(2)}$ of length $2n$, we know that the last element of $B_{k-1}$ is the largest element in $B_1 \ldots B_{k-1}$ and hence the element in $B_k$ must be $2n+1$. Thus in this case $GMP_{2n+1,\tau^{(2)}}(x) = - GMP_{2n,\tau^{(2)}}(x)$. \end{proof} Here is list of the first few values of $GMP_{2n,\tau^{(1)}}(x)$. \begin{eqnarray*} GMP_{2,\tau^{(2)}}(x) &=& 1 \\ GMP_{4,\tau^{(2)}}(x) &=& x-2 \\ GMP_{6,\tau^{(2)}}(x) &=& 6-6 x+x^2\\ GMP_{8,\tau^{(2)}}(x) &=& -23+36 x-15 x^2+x^3\\ GMP_{10,\tau^{(2)}}(x) &=& 106-229 x+160 x^2-37 x^3+x^4\\ GMP_{12,\tau^{(2)}}(x) &=& -567+1574 x-1566 x^2+650 x^3-93 x^4+x^5\\ GMP_{14,\tau^{(2)}}(x) &=& 3434-11706 x+15248 x^2-9310 x^3+2572 x^4- 238 x^5+x^6\\ GMP_{16,\tau^{(2)}}(x) &=& -23137+93831 x-151933 x^2+123814 x^3-52136 x^4+\\ &&10175 x^5-616 x^6+x^7 \end{eqnarray*} In this case the sequence $((-1)^{n-1}GMP_{2n,\tau^{(2)}}(0))_{n \geq 1}$ which starts out with \\ $1,2,6,23,106,567,23137, \ldots $ seems to be sequence A125273 in the Online Encyclopedia of Integer Sequences (OEIS). Unfortunately, there seems to be no exact formula for this sequence. The sequence $((-1)^{n}GMP_{2n,\tau^{(2)}}(x)|_x)_{n \geq 1}$ which starts out\\ $1,6,36,1574,11706,933831, \ldots $ does not appear in the OEIS. Plugging these values into the generating functions (\ref{eqA}) and (\ref{eqB}) and using Mathematica, we have computed the following table of values of $A_{n,\tau^{(2)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(2)}\mbox{-mch}(\sg)}$.\\ \ \\ \begin{tabular}{|l|l|} \hline $A_{1,\tau^{(2)}}$ & 1 \\ \hline $A_{2,\tau^{(2)}}$ & 1 \\ \hline $A_{3,\tau^{(2)}}$ & 2 \\ \hline $A_{4,\tau^{(2)}}$ & $4+x$ \\ \hline $A_{5,\tau^{(2)}}$ & $12+4 x$\\ \hline $A_{6,\tau^{(2)}}$ & $36+24x+x^2$ \\ \hline $A_{7,\tau^{(2)}}$ & $148+118 x+6 x^2$\\ \hline $A_{8,\tau^{(2)}}$ & $593+680 x+111 x^2+x^3$ \\ \hline $A_{9,\tau^{(2)}}$ & $3128+4032 x+768 x^2+8 x^3$ \\ \hline $A_{10,\tau^{(2)}}$ & $15676+25691 x+8680 x^2+473 x^3+x^4$ \\ \hline $A_{11,\tau^{(2)}}$ & $101094+180134 x+68326 x^2+4228 x^3+10 x^4$ \\ \hline \end{tabular}\\ \ \\ Next we consider $GMP_{2n,\tau^{(4)}}(x)$. \begin{theorem} For $n \geq 3$, \begin{equation}\label{tau4rec} GMP_{2n,\tau^{(4)}}(x) = (x-1)^{n-1} - GMP_{2n-2,\tau^{(4)}}(x) - \sum_{j=2}^{n-1} \binom{2n-j-1}{j-1}GMP_{2n-2j,\tau^{(4)}}(x) \end{equation} and, for $n \geq 2$, \begin{multline}\label{tau4reco} GMP_{2n+1,\tau^{(4)}}(x) = \\ -n(x-1)^{n-1} - GMP_{2n-1,\tau^{(4)}}(x) - \sum_{j=2}^{n-1} \binom{2n-j}{j-1}GMP_{2n+1-2j,\tau^{(4)}}(x). \end{multline} \end{theorem} \begin{proof} It is clear from the graph $G_{n,P^{(4)}}$ that in the unique maximum packing $\sg = \sg_1 \ldots \sg_{2n} \in \mathcal{A}_{2n}$ for $\tau^{(4)}$, $\sg_2 \sg_4 \ldots \sg_{2n} = (2n) (2n-1) \ldots (n+1)$ and $\sg_1 \sg_3 \ldots \sg_{2n-1} = 12 \ldots n$. It follows that in a generalized maximum packing $\alpha \in S_{2n}$ with block structure $B_1 \ldots B_k$ that the first element of each block $B_i$ is the smallest element in the block. Hence if $B_1$ is length two then, its two elements must be $1$ and $2$ since they must be smaller than all the smallest elements in each block $B_i$ for $i > 1$. In that case $B_2 \ldots B_{k}$ is just a generalized maximum packing for $\tau^{(4)}$ of length $2n-2$ whose weight is $-w(\sg)$. If $B_1 = \sg_{1} \ldots \sg_{2j}$ reduces to a maximum packing for $\tau^{(4)}$ of length $2j$ where $2 \leq j \leq n-1$, then it must be the case $\sg_{1}< \sg_{3} < \sg_{5} < \cdots < \sg_{2j-1} < \sg_{2j}$ must be the $j+1$ smallest elements from $\{1,\ldots, 2n\}$ since they will be smaller that all the remaining elements of $B_1$ and smaller than the smallest element of $B_i$ for $i >1$. It follows that the last element of block $B_1$ is $(j+1)$. Our definitions for a generalized maximum packing for $\tau^{(4)}$ do not impose any relations between the remaining elements of $B_1$, namely $\sg_{2},\sg_{4}, \ldots , \sg_{2j-2}$, and the elements in blocks $B_2, \ldots, B_{k}$. Thus we have $\binom{2n-j-1}{j-1}$ ways to choose those elements. Once we have chosen those elements, then $B_2 \ldots B_{k}$ must reduce to a generalized maximum packing for $\tau^{(4)}$ of length $2n-2j$. Thus by classifying the elements of $\mathcal{GMP}_{2n,\tau^{(4)}}$ by the length of the first block, we see that for $n \geq 3$, (\ref{tau4rec}) holds. This is the same recursion as (\ref{tau2rec}) and it implies that $A_{\tau^{(2)}}(t,x) = A_{\tau^{(4)}}(t,x)$. This is no surprise since even length up-down permutations are closed under reverse complement. That is, if $\sg = \sg_1 \ldots \sg_n \in S_n$, then the reverse of $\sg$, $\sg^r$, is defined to be $\sg^r = \sg_n \ldots \sg_1$ and the complement of $\sg$, $\sg^c$, is defined by $\sg^c = (n+1-\sg_1) \ldots (n+1-\sg_n)$. The reverse-complement of $\sg$ is $(\sg^r)^c$. It is easy to check that $\sg \in \mathcal{A}_{2n}$ if and only if $(\sg^r)^c \in \mathcal{A}_{2n}$ and that $(2314^r)^c = 1423$. Thus the map which send $\sg \in \mathcal{A}_{2n}$ to $(\sg^r)^c$ shows that $A_{\tau^{(2)}}(t,x) = A_{\tau^{(4)}}(t,x)$. It is not the case that $B_{\tau^{(2)}}(t,x) = B_{\tau^{(4)}}(t,x)$ since for $n \geq 2$, the number of maximum packings for $\tau^{(2)}$ of length $2n+1$ is $2n$ while the number of maximum packings for $\tau^{(4)}$ of length $2n+1$ is $(n+1)$. Nevertheless, we can still develop a recursion for $GMP_{2n+1,\tau^{(4)}}(x)$ for $n \geq 2$. That is, since any generalized maximum packing for $\tau^{(4)}$ of length $2n+1$ has block structure $B_1 \ldots B_k$ where $B_k$ has length 1 and $B_1 \ldots B_{k-1}$ reduces to a generalized maximum packing for $\tau^{(4)}$ of length $2n$, it will still be the case that the first element in each block is the smallest element. Hence if $B_1$ is length two then, its two elements must be $1$ and $2$ since they must be smaller than all the smallest elements in each block $B_i$. In that case $B_2 \ldots B_{k}$ is just a generalized maximum packing for $\tau^{(4)}$ of length $2n-1$ whose weight is $-w(\sg)$. If $B_1 = \sg_{1} \ldots \sg_{2j}$ reduces to a maximum packing for $\tau^{(4)}$ of length $2j$ where $2 \leq j \leq n-1$, then it will still be the case that $\sg_{1}< \sg_{3} < \sg_{5} < \cdots < \sg_{2j-1} < \sg_{2j}$ are the $j+1$ smallest elements from $\{1,\ldots, 2n\}$ and the last element of $B_1$ is $j+1$. If $j =n$, then it is easy to see that we have $n$ choices of $\sg_{2n+1}$ and once we choose $\sg_{2n+1}$, then the order of the rest of the elements are completely determined. Thus generalized maximum packings for $\tau^{(4)}$ which have two blocks $B_1B_2$ contribute a weight of $-n(x-1)^{n-1}$ to $GMP_{2n+1,\tau^{(4)}}$. If $2 \leq j \leq n-1$, then our definitions for a generalized maximum packing for $\tau^{(4)}$ do not impose any relations between the remaining elements of $B_1$, namely $\sg_{2},\sg_{4}, \ldots , \sg_{2j-2}$, and the elements in blocks $B_2, \ldots, B_{k}$. Thus we have $\binom{2n-j}{j-1}$ ways those choose those elements. Once we have chosen those elements, then $B_2 \ldots B_{k}$ must reduce to a generalized maximum packing for $\tau^{(4)}$ of length $2n+1-2j$. Thus by classifying the elements of $\mathcal{GMP}_{2n+1,\tau^{(4)}}$ by the length of the first block, we see that for $n \geq 2$ (\ref{tau4reco}) holds. \end{proof} Here is list of the first few values of $GMP_{2n+1,\tau^{(4)}}(x)$. \begin{eqnarray*} GMP_{1,\tau^{(4)}}(x) &=& 1 \\ GMP_{3,\tau^{(4)}}(x) &=& -1 \\ GMP_{5,\tau^{(4)}}(x) &=& 3-2 x \\ GMP_{7,\tau^{(4)}}(x) &=& -10+12 x-3 x^2\\ GMP_{9,\tau^{(4)}}(x) &=& 42-74 x+37 x^2-4 x^3\\ GMP_{11,\tau^{(4)}}(x) &=& -210+498 x-394 x^2+110 x^3-5 x^4\\ GMP_{13,\tau^{(4)}}(x) &=& 1199-3596 x+3946 x^2-1872 x^3+330 x^4-6 x^5\\ GMP_{15,\tau^{(4)}}(x) &=& -7670+27908 x-39356 x^2+26604 x^3-8476 x^4+996 x^5-7 x^6 \end{eqnarray*} In this case, the sequence $\{GMP_{2n+1,\tau^{(4)}}(0)\}_{n \geq 0}$ seems to be sequence A125274 in the OEIS. Unfortunately, there is no exact formulas for the elements in this sequence. Plugging these values into the generating functions (\ref{eqA}) and (\ref{eqB}) and using Mathematica, we have computed the following table of values of $A_{n,\tau^{(4)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(4)}\mbox{-mch}(\sg)}$.\\ \ \\ \begin{tabular}{|l|l|} \hline $A_{1,\tau^{(4)}}$ & 1 \\ \hline $A_{2,\tau^{(4)}}$ & 1 \\ \hline $A_{3,\tau^{(4)}}$ & 2 \\ \hline $A_{4,\tau^{(4)}}$ & $4+x$ \\ \hline $A_{5,\tau^{(4)}}$ & $13+3 x$\\ \hline $A_{6,\tau^{(4)}}$ & $36+24x+x^2$ \\ \hline $A_{7,\tau^{(4)}}$ & $165+103 x+4 x^2$\\ \hline $A_{8,\tau^{(4)}}$ & $593+680 x+111 x^2+x^3$ \\ \hline $A_{9,\tau^{(4)}}$ & $3507+3832 x+592 x^2+5 x^3$ \\ \hline $A_{10,\tau^{(4)}}$ & $15676+25691 x+8680 x^2+473 x^3+x^4$ \\ \hline $A_{11,\tau^{(4)}}$ & $113387+179369 x+58016 x^2+3014 x^3+6 x^4$\\ \hline \end{tabular}\\ \ \\ The key to our ability to develop recursions for $GMP_{n,\tau^{(i)}}(x)$ in the case where $i \in \{1,2,4\}$ is due to the fact that $\tau^{(1)}$, $\tau^{(2)}$, and $\tau^{(4)}$ either start with 1 or end with 4. This allowed us to develop recursions based on either length of the first block or the length of the last block in a generalized maximum packing. Neither $\tau^{(3)} = 2413$ nor $\tau^{(5)} = 3412$ start with 1 or end with 4 so that we have not been able to find any simple recursions for $GMP_{n,\tau^{(3)}}$ or $GMP_{n,\tau^{(5)}}$. J. Harmse \cite{Harmse} computed the following initial values of $GMP_{n,\tau^{(3)}}$ and $GMP_{n,\tau^{(5)}}$ by computing the number of linear extension of the posets associated with the various block structures of generalized maximal packings. Here is list of the first few values of $GMP_{2n,\tau^{(3)}}(x)$. \begin{eqnarray*} GMP_{1,\tau^{(3)}}(x) &=& 1 \\ GMP_{2,\tau^{(3)}}(x) &=& 1 \\ GMP_{3,\tau^{(3)}}(x) &=& -1 \\ GMP_{4,\tau^{(3)}}(x) &=& -2+x \\ GMP_{5,\tau^{(3)}}(x) &=& 3-2x \\ GMP_{6,\tau^{(3)}}(x) &=& 9-10 x+2 x^2 \\ GMP_{7,\tau^{(3)}}(x) &=& -18+24x-7x^2 \\ GMP_{8,\tau^{(3)}}(x) &=& -74+132 x-64 x^2+5 x^3 \\ GMP_{9,\tau^{(3)}}(x) &=& 190-376x+213x^2-26x^3\\ GMP_{10,\tau^{(3)}}(x) &=& 974-2394 x+1927 x^2-520 x^3+14 x^4 \\ GMP_{11,\tau^{(3)}}(x) &=&-3078+8180x-7287x^2+2282x^3-98x^4 \\ GMP_{12,\tau^{(3)}}(x) &=& -17688+54228 x-59393 x^2+26807 x^3-3997 x^4+42 x^5 \end{eqnarray*} Plugging these values into the generating functions (\ref{eqA}) and (\ref{eqB}) and using Mathematica, we have computed the following table of values of $A_{n,\tau^{(3)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(3)}\mbox{-mch}(\sg)}$. \\ \ \\ \begin{tabular}{|l|l|} \hline $A_{1,\tau^{(3)}}$ & 1 \\ \hline $A_{2,\tau^{(3)}}$ & 1 \\ \hline $A_{3,\tau^{(3)}}$ & 2 \\ \hline $A_{4,\tau^{(3)}}$ & $4+x$ \\ \hline $A_{5,\tau^{(3)}}$ & $13+3x$\\ \hline $A_{6,\tau^{(3)}}$ & $39+20x+2x^2$ \\ \hline $A_{7,\tau^{(3)}}$ & $178+87x+7x^2$ \\ \hline $A_{8,\tau^{(3)}}$ & $710+552 x+118 x^2+5 x^3$ \\ \hline $A_{9,\tau^{(3)}}$ & $4168+3146x+603x^2+19x^3$ \\ \hline $A_{10,\tau^{(3)}}$ & $29774+21666 x+5370 x^2+2697 x^3+14 x^4$ \\ \hline $A_{11,\tau^{(3)}}$ & $149030+152170x+27000x2+25536x^3+56x^4$ \\ \hline \end{tabular}\\ \ \\ \ \\ Here is list of the first few values of $GMP_{2n,\tau^{(5)}}(x)$. \begin{eqnarray*} GMP_{1,\tau^{(5)}}(x) &=& 1 \\ GMP_{2,\tau^{(5)}}(x) &=& 1 \\ GMP_{3,\tau^{(5)}}(x) &=& -1 \\ GMP_{4,\tau^{(5)}}(x) &=& -2+x \\ GMP_{5,\tau^{(5)}}(x) &=& 4-3x \\ GMP_{6,\tau^{(5)}}(x) &=& 14-14 x+ x^2 \\ GMP_{7,\tau^{(5)}}(x) &=& -39+44x-6x^2 \\ GMP_{8,\tau^{(5)}}(x) &=& -168+252 x-86 x^2+x^3 \\ GMP_{9,\tau^{(5)}}(x) &=& 594-1002+416x^2-7x^3\\ GMP_{10,\tau^{(5)}}(x) &=& 3352-6704 x+3782 x^2-430 x^3+ x^4 \\ GMP_{11,\tau^{(5)}}(x) &=& -13814+30264x-19404x^2=2962x^3-9x^4 \\ GMP_{12,\tau^{(5)}}(x) &=& -91038+224751 x-180196 x^2+48387 x^3-1906 x^4+x^5 \\ \end{eqnarray*} Plugging these values into the generating functions (\ref{eqA}) and (\ref{eqB}) and using Mathematica, we have computed the following table of values of $A_{n,\tau^{(5)}}(x) = \sum_{\sg \in \mathcal{A}_n} x^{\tau^{(5)}\mbox{-mch}(\sg)}$. \\ \ \\ \begin{tabular}{|l|l|} \hline $A_{1,\tau^{(5)}}$ & 1 \\ \hline $A_{2,\tau^{(5)}}$ & 1 \\ \hline $A_{3,\tau^{(5)}}$ & 2 \\ \hline $A_{4,\tau^{(5)}}$ & $4+x$ \\ \hline $A_{5,\tau^{(5)}}$ & $14+2x$\\ \hline $A_{6,\tau^{(5)}}$ & $44+16x+x^2$ \\ \hline $A_{7,\tau^{(5)}}$ & $214_56x+2x^2$ \\ \hline $A_{8,\tau^{(5)}}$ & $896+448 x+40 x^2+x^3$ \\ \hline $A_{9,\tau^{(5)}}$ & $5610+2190x+134x^2+2x^3$ \\ \hline $A_{10,\tau^{(5)}}$ & $29392+18496 x+ 2552x^2+80x^3+x^4$ \\ \hline $A_{11,\tau^{(5)}}$ & $224878+116776x+11880x^2+256x^3+2x^4$ \\ \hline \end{tabular}\\ \ \\ \section{Double rise pairs and double descent pairs.} Suppose that $\sg = \sg_1 \ldots \sg_{n} \in \mathcal{A}_{n}$. Then we say that $(2i-1)(2i)$ is a double rise (double descent) pair in $\sg$ if both $\sg_{2i-1}< \sg_{2i+1}$ and $\sg_{2i} < \sg_{2i+2}$ ($\sg_{2i-1}> \sg_{2i+1}$ and $\sg_{2i} > \sg_{2i+2}$). It is easy to see that $(2i-1)(2i)$ is a double rise pair if and only if $\red{\sg_{2i-1}\sg_{2i}\sg_{2i+1}\sg_{2i+2}}= 1324$ so that the number of double rise pairs in $\sg$ is just the number of $1324$-matches in $\sg$. Similarly, is $(2i-1)(2i)$ is a double descent pair if and only if $\red{\sg_{2i-1}\sg_{2i}\sg_{2i+1}\sg_{2i+2}} \in \{3412,2413\}$ so that if $D = \{3412,2413\}$, then the number of double descents pairs in $\sg$ is just the number of $D$-matches in $\sg$. In general, if $\Upsilon \subseteq \mathcal{A}_4$, we say that $\sg \in \mathcal{A}_{2n}$ is a maximum packing for $\Upsilon$ if $\umch{\sg} = n-1$. We say that $\sg \in S_{2n}$ is a {\em generalized maximum packing for $\Upsilon$} if we can break $\sg$ into consecutive blocks $\sg = B_1 \ldots B_k$ such that \begin{enumerate} \item for all $1 \leq j \leq k$, $B_j$ is either an increasing sequence of length 2 or $\red{B_j}$ is maximum packing for $\Upsilon$ of length $2s$ for some $s \geq 2$ and \item for all $1 \leq j \leq k-1$, the last element of $B_j$ is less than the first element of $B_{j+1}$. \end{enumerate} Similarly, we say that $\sg \in \mathcal{A}_{2n+1}$ is a maximum packing for $\Upsilon$ if $\umch{\sg} = n-1$. We say that $\sg \in S_{2n+1}$ is a {\em generalized maximum packing for $\Upsilon$} if we can break $\sg$ into consecutive blocks $\sg = B_1 \ldots B_k$ such that \begin{enumerate} \item for all $1 \leq j < k$, $B_j$ is either an increasing sequence of length 2 or $\red{B_j}$ is maximum packing for $\Upsilon$ of length $2s$ for some $s \geq 2$, \item $B_k$ is block of length 1, and \item for all $1 \leq j \leq k-1$, the last element of $B_j$ is less than the first element of $B_{j+1}$. \end{enumerate} Then we can define the generalized maximum packing polynomials $GMP_{2n,\Upsilon}(x)$ and $GMP_{2n+1,\Upsilon}(x)$ in the same manner that we defined $GMP_{2n,\tau^{(i)}}(x)$ and $GMP_{2n+1,\tau^{(i))}}(x)$. We then have the following theorem. \begin{theorem}\label{thm:mainu} Let $\Upsilon \subseteq \mathcal{A}_4$. Then \begin{eqnarray*}\label{eqAu} A_{\Upsilon}(t,x) &=& 1+ \sum_{n \geq 1} \frac{t^{2n}}{(2n)!} \sum_{\sg \in \mathcal{A}_{2n}} x^{\umch{\sg}}\\ &=&\frac{1}{1-\sum_{n\geq 1} GMP_{2n,\Upsilon}(x) \frac{t^{2n}}{(2n)!}} \end{eqnarray*} and \begin{eqnarray*}\label{eqBu} B_{\Upsilon}(t,x) &=& \sum_{n \geq 1} \frac{t^{2n-1}}{(2n-1)!} \sum_{\sg \in \mathcal{A}_{2n-1}} x^{\umch{\sg}}\\ &=&\frac{\sum_{n \geq 1} GMP_{2n-1,\Upsilon}(x) \frac{t^{2n-1}}{(2n-1)!}}{1-\sum_{n\geq 1} GMP_{2n,\Upsilon}(x) \frac{t^{2n}}{(2n)!}}. \end{eqnarray*} \end{theorem} That is, if $\Upsilon \subseteq \mathcal{A}_4$, the proof of Theorem \ref{thm:main} goes through without change if we replace maximum packings for $\tau^{(i)}$ with maximum packings for $\Upsilon$ and generalized maximum packings for $\tau^{(i)}$ by generalized maximum packings for $\Upsilon$ throughout the proof. Thus if we can compute $GMP_{n,D}(x)$, we would have the generating function for the distribution of double descents in $\mathcal{A}_n$. We can compute $\mmp_{2n,D}$ and $\mmp_{2n+1,D}$. That is, we have the following theorem. \begin{theorem} For all $n \geq 1$, $\displaystyle \mmp_{2n,D} = C_n \ \mbox{and} \ \mmp_{2n+1,D} = C_{n+1}$. \end{theorem} \begin{proof} It is easy to see that $\mmp_{2n,D}$ equals the number of $F \in \mathcal{F}_{2,n}$ such that for each $i