%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2018}
\articlenumber{66}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc


\usepackage{float, subcaption, tikz}
\usetikzlibrary{decorations.pathreplacing,calc}
%
\tikzstyle{b}=[thick,decorate, decoration={brace,amplitude=5pt,mirror}, xshift=0.4pt,yshift=-0.4pt]
\tikzstyle{l}=[midway,yshift=-0.5cm]

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}{[theorem]Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}


\newcommand{\todo}[1]{\vspace{2 mm}\par\noindent
   \marginpar[\flushright\textsc{ToDo}]{\textsc{ToDo}}\framebox{\begin{minipage}[c]{\textwidth}
   \tt #1 \end{minipage}}\vspace{2 mm}\par}

\renewcommand{\S}{\mathcal{S}}
\newcommand{\U}{\mathcal{U}}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\Des}{Des}
\newcommand{\Inv}{\mathcal{I}}
\newcommand{\Dinv}{\mathcal{D}}
\newcommand{\inv}{i}

\newcommand{\x}{\boldsymbol{x}}

%% define your title in the usual way
\title{On the number of $\lambda$-unimodal involutions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Archer, Gay, Germany, King, Lauderdale, Lupo, Rossi]{Kassie Archer\thanks{\href{mailto:karcher@uttyler.edu}{karcher@uttyler.edu}}\addressmark{1}, Angela M. Gay\addressmark{1}, Virginia Germany\addressmark{1}, C. Marin King\addressmark{1},  \\
Lindsey-Kay
Lauderdale\thanks{\href{mailto:llauderdale@uttyler.edu}{llauderdale@uttyler.edu}}\addressmark{1},
Thomas Lupo\addressmark{1},  \and Francesca L. Rossi\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Texas at Tyler, Tyler, TX 75799}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{For a given composition $\lambda$ of the positive integer $n$, a $\lambda$-unimodal permutation is a permutation comprised of contiguous unimodal segments whose lengths are determined by $\lambda$. In this extended abstract, the authors present a generating function for the number of $\lambda$-unimodal involutions and address its relationship to the Gelfand character of the symmetric group.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{involutions, enumeration, $\lambda$-unimodal permutations, descents}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{66-Archer-Gay-Germany-King-Lauderdale-Lupo-Rossi.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

A permutation is \textit{unimodal} provided its one-line notation is increasing, then decreasing.  Given any composition $\lambda$ of the positive integer $n$, we say that a permutation is $\lambda$\textit{-unimodal} if it is comprised of contiguous unimodal segments whose lengths are determined by the composition $\lambda$.  These $\lambda$-unimodal permutations are the topic of research by numerous authors, although they are not often studied as purely combinatorial objects, and first appeared in the study of characters of the symmetric group; see for example \cite{APR08, AR2015,A2015,ER2014,R1998,R1997}.  %The cycle structure of $\lambda$-unimodal permutations also has applications to dynamical systems and card shuffling.
In \cite{A2016}, the first author of this extended abstract investigated $\lambda$-unimodal cycles and their application to a specific character of the symmetric group.
Here, we investigate $\lambda$-unimodal involutions, i.e., those $\lambda$-unimodal permutations that are their own (algebraic) inverse. 

In  \cite{APR08, AR2015}, it is shown that these involutions have a direct relationship to the so-called Gelfand character, $\chi^G$. This character is associated to the representation of $\S_n$ obtained by taking the multiplicity-free direct sum of the irreducible representations of $\S_n$. For example, see \cite{APR08}. %More here?
Specifically, if $\Inv^\lambda$ denotes the set of $\lambda$-unimodal involutions and $\des_\lambda(\pi)$ denotes the number of $\lambda$-descents of a permutation $\pi$ (defined in Section \ref{sec:background}), then 
\begin{equation}\label{eq:char}
\chi_\lambda^G = \sum_{\pi\in\Inv^\lambda}(-1)^{\des_\lambda(\pi)}.
\end{equation}

%It is well-known that if $\U_n$ is the set of unimodal permutations on $\{1,2,\ldots,n\}$, then $|\U_n|=2^{n-1}$.   %PUT THIS FACT IN THE BACKGROUND

In this extended abstract, we enumerate $\lambda$-unimodal involutions
via a recursive generating function. This can be further refined to a
generating function for $\lambda$-unimodal involutions with a given
number of $\lambda$-descents, which in turn gives a generating function
for the Gelfand character (see Theorem \ref{main theorem 2}). This gives
us a new way of computing the Gelfand character (other than the
Murnaghan--Nakayama rule; see \cite{M-1937, N1940, B2004, R1997} for more).
%CITE THE M-N RULE stuff and ROICHMAN and insert B2004 Burnstein
 Because of space restrictions, most of the details of the proof regarding the computation of these involutions by $\lambda$-descents are omitted. However, this gives us an approach to address an open question in \cite{R2014}, in which Roichman comments on the desirability of combinatorial proofs to the given character formulas, such as Equation~\eqref{eq:char}. 

%From the combinatorial perspective, there is a long history of studying involutions of permutations with a certain one-line structure. In the study of pattern-avoiding permutations, several results have been obtained regarding the enumeration of pattern-avoiding involutions; see \cite{BHPV, DRS,SS1985} among others.
%This fits into the larger question of enumerating permutations that have certain one-line structure (including pattern-avoiding permutations or $\lambda$-unimodal permutations) by their cycle type. This question is quite challenging in general since the dual nature of a permutation as a word in its one-line notation and as a bijection in its cycle notation is usually not easily reconciled. Though involutions are generally well-studied in this context, few other results are known. These include the complete enumeration of unimodal permutations by cycle type \cite{G2001,T2001}. A few other results regarding cycle type of pattern-avoiding permutations are known as well \cite{AE2014, AL2016, AL2017, DFH2013, ElizaldePhd}. In \cite{A2016}, $\lambda$-unimodal cycles are enumerated. 

%The question of enumerating permutations that have a certain one-line structure by their cycle type turns out to be more than just an interesting exercise. Cycles in particular have been studied and are known to have applications to dynamical systems \cite{AE2014, WR1987} and card-shuffling \cite{DFH2013}. The set of $\lambda$-unimodal permutations is closely related to those permutations realized as the periodic patterns of the alternating signed shift map \cite{AE2014, AL2016} and to so-called shelf-shuffled permutations \cite{DFH2013}. In addition, as stated previously, there is a close relationship between the cycle structure of $\lambda$-unimodal permutations and characters of the symmetric group. In fact, taking a sum similar to Equation~\eqref{eq:char} over $\lambda$-unimodal permutations in any conjugacy class or union of conjugacy classes gives rise to some character of the symmetric group. For these reasons, the authors are quite interested in further studying the cycle structure of these permutations. 

%Weiss and Rogers \cite{WR1987} were the first to enumerate unimodal cycles using iterated maps. More generally, Gannon \cite{G2001} and Thibon \cite{T2001} independently enumerated unimodal permutations by cycle type, and the first author of this extended abstract and Elizalde \cite{AE2014} used unimodal permutations to characterize the permutations that are realized by the $n$-periodic orbits of the tent map.  In the context of card-shuffling, Diaconis, Fulman and Holmes \cite{DFH2013} studied certain $\lambda$-unimodal permutations obtained by a new type of card-shuffling machine that use shelf-shuffling.  The first and fourth authors of this extended abstract have studied these permutations in a different context in \cite{AL2016}, and established a bijection between unimodal permutations of length $n-1$ and so called almost-increasing cyclic permutations of length $n$ in \cite{AL2017}.


\section{Background and Notation}\label{sec:background}

Let $\S_n$ be the set of permutations on $[n] = \{1,2,\ldots,n\}$, and write $\pi \in \S_n$ in its one-line notation as $\pi=\pi_1\pi_2\ldots\pi_n=\pi(1)\pi(2)\ldots \pi(n)$.  A permutation $\pi \in \S_n$ is \textit{unimodal} if there exists $i \in [n]$ such that 
	\[\pi_1<\pi_2<\cdots<\pi_{i-1}<\pi_i>\pi_{i+1}>\cdots>\pi_{n-1}>\pi_n;\]
that is, $\pi$ is increasing then decreasing.  A \textit{composition} of the integer $n$, denoted $\lambda \vDash n$,  is a sequence of positive integers $\lambda=(\lambda_1,\lambda_2, \ldots, \lambda_k)$ such that $\sum \lambda_i=n$.  Given a composition $\lambda=(\lambda_1,\lambda_2, \ldots, \lambda_k)$ of $n$, we say that $\pi \in \S_n$ is $\lambda$\textit{-unimodal} provided $\pi$ is composed of $k$ contiguous segments, where the $i$-th segment is unimodal of length $\lambda_i$.  For example, the permutation $\pi = 129654873 \in \S_9$ is $(5,4)$-unimodal because the first five entries $12965$ and the last four entries $4873$ both form unimodal segments of $\pi$; the pictorial representation of this permutation can be seen in Figure~\ref{fig:EXAMPLES}(a).  The permutation $\pi \in \S_n$ has a \textit{descent} at position $i$ if $\pi_i>\pi_{i+1}$. The \textit{descent set} of $\pi$, denoted $\Des(\pi)$, is the set of descents and the \textit{descent number} of $\pi$, denoted $\des(\pi)$, is the number of descents of $\pi$.  If $\lambda=(\lambda_1,\lambda_2, \ldots, \lambda_k) \vDash n$, we say that $i$ is a $\lambda$\textit{-descent} of $\pi$ if $i$ is a descent that occurs within a segment of length $\lambda_i$ for some $i \in [n]$. In other words, we define the set of $\lambda$-descents of $\pi$, denoted $\Des_\lambda(\pi)$, to be the set $$\Des_\lambda(\pi)=\Des(\pi)\setminus\{\lambda_1, \lambda_1+\lambda_2, \ldots, \lambda_1+\lambda_2+\cdots+\lambda_{k-1}\}.$$ We let $\des_\lambda(\pi)$ denote the number of $\lambda$-descents of $\pi$.  For example, for the permutation $\pi = 129654873 \in \S_9$, we have $\des(\pi)=5$ and $\des_\lambda(\pi)=4$, where $\lambda=(5,4)$.  Finally, $\pi \in \S_n$ is an \textit{involution} if it is comprised of only transpositions and fixed points.  Equivalently, every involution is it own inverse and in its pictorial representation, every involution is symmetric about the diagonal.  The $(4,3,2)$-unimodal involution $\pi=476183259 \in \S_9$ is depicted in Figure~\ref{fig:EXAMPLES}(b).
Finally, let $S^\lambda$ denote the set of $\lambda$-unimodal permutations and let $\Inv^\lambda$ denote the set of $\lambda$-unimodal involutions. For example, $129654873\in S^{(5,4)}$ and $129654873 \in \Inv^{(5,4)}$; also $476183259 \in \Inv^{(4,3,2)}$.

  	\begin{figure}[H]
	\centering
		\begin{tabular}{ccc}
			\subcaptionbox{$(5,4)$-unimodal permutation $\pi = 129654873 \in \S_9$}{
			\begin{tikzpicture}[scale=.5]
				\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
				\tikzset{myx/.pic = {\draw 
				      (-2.5mm,-2.5mm) -- (2.5mm,2.5mm)
				      (-2.5mm,2.5mm) -- (2.5mm,-2.5mm);}}

				\draw[gray] (0,0) grid (9,9);
				\draw[thick] (5,0) -- (5,9);
				\foreach \x/\y in {1/1,2/2,3/9,4/6,5/5,6/4,7/8,8/7,9/3}
				\myx[(\x-.5,\y-.5)];
				
			\end{tikzpicture}} & \hspace{1cm} &

			\subcaptionbox{$(4,3,2)$-unimodal involution $\pi=476183259 \in \S_9$}{
			\begin{tikzpicture}[scale=.5]
				\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
				\tikzset{myx/.pic = {\draw 
 				     (-2.5mm,-2.5mm) -- (2.5mm,2.5mm)
 				     (-2.5mm,2.5mm) -- (2.5mm,-2.5mm);}}

				\draw[gray] (0,0) grid (9,9);
				\foreach \x/\y in {1/4,2/7,3/6,4/1,5/8,6/3,7/2,8/5,9/9}
				\myx[(\x-.5,\y-.5)];
				\draw[-, dashed] (0,0) -- (9,9);
				\draw[thick] (4,0) -- (4,9) (7,0) -- (7,9);
			\end{tikzpicture}}
		
		\end{tabular}
		\caption{ Pictorial representations of $\lambda$-unimodal permutations.}
		\label{fig:EXAMPLES}
	\end{figure} 
	

We conclude this section with two enumerations of the set of $\lambda$-unimodal permutations that do not appear anywhere in the literature, in part because these permutations are not yet well-studied. 
%\begin{prop}
If $\lambda=(\lambda_1,\lambda_2, \ldots, \lambda_k) \vDash n$, then the number of $\lambda$-unimodal permutations in $\S_n$ is 
	\[{n \choose \lambda_1,\lambda_2,\ldots,\lambda_k}\prod_{i=1}^k 2^{\lambda_i-1} ={n \choose \lambda_1,\lambda_2,\ldots,\lambda_k}2^{n-k},\]
	where ${n \choose \lambda_1,\lambda_2,\ldots,\lambda_k}$ denotes the multinomial coefficient.
The number of $\lambda$-unimodal permutations in $\S_n$ with $m$ $\lambda$-descents is
		\[{n \choose \lambda_1,\lambda_2,\ldots,\lambda_k}\sum_{\mathbf d \in \Omega_{\lambda}^m} \prod_{i=1}^k {\lambda_i-1 \choose d_i}={n \choose \lambda_1,\lambda_2,\ldots,\lambda_k}{n-k \choose m},\]
where $\Omega_{\lambda}^m = \{(d_1,d_2,\ldots,d_k): \sum d_i=m \text{ and } 0 \leq d_i \leq \lambda_i-1\}.$
The proofs of these equations follow quickly from the fact that there are exactly $2^{n-1}$ unimodal permutations in $\S_n$ and exactly ${{n-1}\choose{m}}$ unimodal permutations in $\S_n$ with $m$ descents. 
%\end{prop}


\section{Main Theorem}\label{sec3}

In this section, let $\Lambda_k$ be the set of integer compositions into $k$ positive integer parts and let $\lambda=(\lambda_1, \lambda_2, \ldots, \lambda_k)\in \Lambda_k$. Let $\x$ denote the set of indeterminates $\{x_1, x_2, \ldots, x_k\}$. For a generating function $F$ on variables $\x \setminus\{x_{i_1}, x_{i_2}, \ldots, x_{i_j}\}$, we write $F(\x; \hat{x}_{i_1}, \hat{x}_{i_2}, \ldots, \hat{x}_{i_j})$. For example, if $k=3$, then $\x=\{x_1, x_2,x_3\}$ and $F(\x; \hat{x}_2)$ is a function on variables $x_1$ and $x_3$ only. Let $x^\lambda$ denote the monomial $x^\lambda=x_1^{\lambda_1}x_2^{\lambda_2}\cdots x_k^{\lambda_k}$. 

We first define three generating functions as follows. Recall that $\Inv^\lambda$ is the set of $\lambda$-unimodal involutions. Let $\Inv^\lambda_j$ be the set of $\lambda$-unimodal involutions, where either $\pi_1\leq \lambda_1+\cdots + \lambda_j$ and the first segment is decreasing or where $\pi_1>\lambda_1+\cdots + \lambda_j$. Finally, let $\Dinv_i^\lambda$  be the set of $\lambda$-unimodal involutions, where $\pi_1\leq\lambda_1+\cdots + \lambda_i$ and the first segment is decreasing.
We define the generating functions $L^k(\x), L_j^k(\x),$ and $D_i^k(\x)$ as follows:
$$L^k(\x) = \sum_{\lambda \in \Lambda_k}|\Inv^\lambda| x^\lambda, \, \, \, \, \, \, \, \, L_j^k(\x) = \sum_{\lambda \in \Lambda_k}|\Inv^\lambda_j| x^\lambda, \quad \text{ and } \quad D_i^k(\x) = \sum_{\lambda \in \Lambda_k}|\Dinv^{\lambda}_i| x^\lambda.$$ 
We find recursive formulas for these generating functions below.

\begin{theorem}\label{main theorem}
We have $L^0(\x)=1$, $L^1(\x) = \dfrac{x_1}{(1-x_1)^2}$ and for $k \geq 2$,
\begin{align*}
L^k(\x) = & \, \frac{1}{1-x_1}\bigg[x_1^2L^k_1(\x) + (x_1+x_1^2)L^{k-1}(\x;\hat{x}_1) \\
& +\sum_{i=2}^k x_1x_i [2L^{k-1}(\x; \hat{x}_1)+L^{k-1}_{i-1}(\x; \hat{x}_i) + L^{k-2}(\x; \hat{x}_1, \hat{x}_i) + L_i^k(\x) +L_{i-1}^k(\x)] \bigg];
\end{align*}
if $k \geq 1$, then $L_k^k(\x) = D_k^k(\x)$ and for $1\leq j<k$,
\begin{align*}
L_j^k(\x) = & \, \frac{1}{1-x_1x_{j+1}}\bigg[D_j^k(\x) + \sum_{i=j+2}^k x_1x_{i} L_{i-1}^k(\x) \\ 
& + \sum_{i=j+1}^kx_1x_i[2L^{k-1}(\x; \hat{x}_1) + L_{i-1}^{k-1}(\x; \hat{x}_i)+L^{k-2}(\x; \hat{x}_1, \hat{x}_i) + L_i^k(\x)] \bigg];
\end{align*}
and if $k\geq 1$, then $D_1^k(\x) = \dfrac{x_1}{1-x_1}L^{k-1}(\x;\hat{x}_1)$ and for $1\leq i <k$, we have
\begin{align*}
D_i^k(\x) \hspace{-2pt}= \hspace{-2pt} \frac{1}{1-x_1x_i}\bigg[D_{i-1}^k(\x)+x_1x_i[D_{i-1}^k(\x) +D_{i-1}^{k-1}(\x; \hat{x}_i)+L^{k-2}(\x; \hat{x}_1, \hat{x}_i) + 2L^{k-1}(\x; \hat{x}_1)]\bigg].
\end{align*}
\end{theorem}


%\todo{explain proof technique (where does the 1 go) for each of these. Start with base cases and then $L^k$. Draw the six possible pictures for when the 1 is not in the first segment. Show the four(?) cases for when 1 is in the first segment. }

 In the extended abstract, we provide proof sketches due to the space limitations. To prove Theorem~\ref{main theorem}, we start with a few lemmas to establish the base cases and recurrences. For $\pi \in S_n$ with $\pi=\pi_1\pi_2\ldots\pi_n$ and $\sigma_m \in \S_m$ with $\sigma=\sigma_1\sigma_2\ldots\sigma_m$, we let $\pi \oplus \sigma \in \S_{n+m}$ denote the permutation
	\[\pi \oplus \sigma = \pi_1\pi_2\ldots\pi_n(\sigma_1+n)(\sigma_2+n)\ldots(\sigma_m+n).\]
For example, if $\pi=312 \in \S_3$ and $\sigma=635421\in \S_6$, then $\pi \oplus \sigma=312968754 \in \S_9$.

%Also, for $\sigma \in S_{n-1}$ with $\sigma=\sigma_1\sigma_2\ldots\sigma_{n-1}$, let $1\oplus\sigma \in \S_n$ denote the permutation $1(\sigma_1+1)(\sigma_2+1) \ldots (\sigma_{n-1}+1)$.  For example, if $\sigma=47618325 \in \S_8$, then $1\oplus \sigma=158729436\in \S_9$. Similarly, for $\sigma \in S_{n-2}$ with $\sigma=\sigma_1\sigma_2\ldots\sigma_{n-2}$, let $21\oplus\sigma \in \S_n$ denote the permutation $21(\sigma_1+2)(\sigma_2+2) \ldots (\sigma_{n-1}+2)$. For example, if $\sigma=47618325 \in \S_8$, then $21\oplus \sigma=216983(10)547 \in \S_{10}$.

\begin{lemma}
If $n\geq 1$, then there are $n$ unimodal involutions in $\S_n$. Consequently, the generating function $L^1(x) =\displaystyle \sum_{\pi\in\Inv^{(n)}}\hspace{-5pt} x^n$ is given by $$L^1(x) = \frac{x}{(1-x)^2}.$$
\end{lemma}

\begin{proof}[Proof Sketch]
Clearly there is only one unimodal permutation of length 1 and it is an involution. We proceed by induction. For any $\pi\in \Inv^{(n)}$ with $n\geq 2$, either $\pi_1=1$ or $\pi_n=1$. Notice that if $\pi_1=1$, then $\pi\in \Inv^{(n)}$ if and only if $\pi=1\oplus \sigma$ with $\sigma \in \Inv^{(n-1)}$. If $\pi_n=1$ then necessarily $\pi_1=n$, and thus $\pi$ is the decreasing permutation which is indeed an involution. Therefore, $|\Inv^{(n)}|=|\Inv^{(n-1)}|+1$, which in turn implies that $|\Inv^{(n)}|=n$, and thus the result follows.
\end{proof}

Clearly, the number of unimodal involutions in $\S_n$ that are strictly decreasing is 1 for each $n$ and thus $D_1^1(\x)=\dfrac{x_1}{1-x_1}$. By the definition of $L_k^k(\x),$ it is clear that we must have $L_k^k(\x) = D_k^k(\x)$ for all $k\geq 1$.

\begin{lemma}
For any $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k)\vDash n$, the number of $\lambda$-unimodal involutions for which the first $\lambda_1$ elements are decreasing and $\pi_1\leq \lambda_1$ is equal to the number of $\lambda'$-unimodal involutions, where $\lambda'=(\lambda_2, \ldots, \lambda_k)\vDash n-\lambda_1$. Consequently, the generating function for these permutations is given by $$D_1^k(\x) = \dfrac{x_1}{1-x_1}L^{k-1}(\x;\hat{x}_1).$$
\end{lemma}

\begin{proof}[Proof Sketch]
If the first $\lambda_1$ elements of a $\lambda$-unimodal involution $\pi$ form a decreasing sequence and $\pi_1\leq \lambda_1$, then $\pi_i=\lambda_1-i+1$ for all $i \in [\lambda_1]$.  For any $\sigma \in \Inv^{\lambda'}$, we can obtain a $\lambda$-unimodal involution with the necessary property by taking $\pi = \delta_{\lambda_1} \oplus \sigma$, where $\delta_{\lambda_1}$ is the decreasing permutation of length $\lambda_1$. The result now follows. 
\end{proof}

With the base cases of Theorem~\ref{main theorem} established, we can now prove the recurrences given in Theorem~\ref{main theorem}. For convenience, we establish the following notation.  If $\lambda=(\lambda_1, \lambda_2, \ldots, \lambda_k) \vDash n$, then let $\bar{\lambda} = (\lambda_1-1, \lambda_2, \ldots, \lambda_k)$; when $\lambda_1 =1$, we implicitly assume that $\bar{\lambda} = (\lambda_2, \lambda_3, \ldots, \lambda_k)$.  Also, let $\bar{\lambda}^1=(\lambda_1-2, \lambda_2, \ldots, \lambda_k)$, and for $i \in \{2,3,\ldots,k\}$, we let $\bar{\lambda}^i = (\lambda_1-1, \lambda_2, \ldots, \lambda_{i-1}, \lambda_{i}-1, \lambda_{i+1},\ldots, \lambda_k)$, where again if $\lambda_1=1$ or if $\lambda_i=1$, we omit these terms from $\bar{\lambda}^i$ altogether. For example, if $\lambda=(4,3,1,2)$, then $\bar{\lambda}=(3,3,1,2)$, $\bar{\lambda}^1 = (2,3,1,2)$, $\bar{\lambda}^2 = (3,2,1,2)$, and $\bar{\lambda}^3=(3,3,2)$. 
Finally, let $$s_\lambda^i = \lambda_1+\lambda_2+\cdots+\lambda_i.$$ For example, if $\lambda=(4,2,6,1)$, then $s_\lambda^1=4$, $s_\lambda^2=6$, $s_\lambda^3=12$, and $s_\lambda^4=13$. 


\begin{lemma}\label{lem:Lk}
For $k\geq 2$, the generating function $L^k(\x)$ satisfies the recurrence
\begin{align*}
L^k(\x) = & \, \frac{1}{1-x_1}\bigg[x_1^2L^k_1(\x) +(x_1+x_1^2)L^{k-1}(\x;\hat{x}_1) \\
& +\sum_{i=2}^k x_1x_i [2L^{k-1}(\x; \hat{x}_1)+L^{k-1}_{i-1}(\x; \hat{x}_i) + L^{k-2}(\x; \hat{x}_1, \hat{x}_i) + L_i^k(\x) +L_{i-1}^k(\x)] \bigg].
\end{align*}
\end{lemma}

\begin{proof}[Proof Sketch]
We will establish the following equivalent formula: 
\begin{align*}
L^k(\x) = & \,x_1L^k(\x) +x_1^2L^k_1(\x)+ (x_1+x_1^2)L^{k-1}(\x;\hat{x}_1)  \\
& +\sum_{i=2}^k x_1x_i [2L^{k-1}(\x; \hat{x}_1)+L^{k-1}_{i-1}(\x; \hat{x}_i) + L^{k-2}(\x; \hat{x}_1, \hat{x}_i) + L_i^k(\x) +L_{i-1}^k(\x)].
\end{align*}
Suppose that $\pi \in \Inv^\lambda$, and consider where $1$ is in the permutation $\pi$. Notice that since $\pi$ is $\lambda$-unimodal, 1 must occur at the beginning or end of a unimodal segment. That is, if $\pi_j=1$, then $j \in \{\lambda_i : i\in [n]\} \cup\{\lambda_{i}+1 : i\in [n-1]\} \cup \{1\}$.  Two cases follow.


	\begin{figure}[H]
	\centering
	\resizebox{.98\textwidth}{!}{
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}
				\fill[red!10!white] (1,1) rectangle (9,9);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,0) grid (1,1);
				\draw[thick] (1,0) -- (1,9);
				\foreach \x/\y in {1/1}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (1,0) node[l] {$\lambda_1$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}
				\draw[gray, fill=red!10!white] (1,1) rectangle (9,9);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,0) grid (1,1);
				\draw[thick] (4,0) -- (4,9);
%				\draw[red] (1,1) -- (9,1);
%				\draw[red] (1,1) -- (1,9);
				\foreach \x/\y in {1/1}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (4,0) node[l] {$\lambda_1$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}
				\draw[gray, fill=red!10!white] (2,2) rectangle (9,9);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) grid (2,2);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[thick] (2,0) -- (2,9);
%				\draw[red] (2,2) -- (9,2);
%				\draw[red] (2,2) -- (2,9);
				\foreach \x/\y in {1/2, 2/1}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (2,0) node[l] {$\lambda_1$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (3,3);
				\fill[red!10!white] (1,4) rectangle (3,9);
				\fill[red!10!white] (4,4) rectangle (9,9);
				\fill[red!10!white] (4,1) rectangle (9,3);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,3) rectangle (9,4);
				\draw[gray] (3,0) rectangle (4,9);
				\draw[gray] (0,3) grid (1,4);
				\draw[gray] (3,0) grid (4,1);
				\draw[thick] (4,0) -- (4,9);
%				\draw[red] (1,9) -- (1,4)--(3,4)--(3,9);
%				\draw[red] (9,1) -- (4,1)--(4,3)--(9,3);
%				\draw[red] (1,1) -- (1,3)--(3,3)--(3,1)--(1,1);
%				\draw[red] (4,4) -- (4,9);
%				\draw[red] (4,4) -- (9,4);
				\foreach \x/\y in {4/1, 1/4}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (4,0) node[l] {$\lambda_1$};
		\end{tikzpicture}}
		\caption{This figure illustrates the case in proof of Lemma \ref{lem:Lk} when 1 lies in the first segment (i.e. when $\pi_1=1$ or $\pi_{\lambda_1}=1$). In the left-most picture, the $\times$ in the bottom left corner together with the shaded portion contribute $x_1L^{k-1}(\x; \hat{x}_1)$. In the second picture, we get $x_1L^k(\x)$; in the third picture, we get $x_1^2L^{k-1}(\x; \hat{x}_1)$; in the fourth picture we get $x_1^2L^k_1(\x)$. }
		\label{fig:Lk first segment}
	\end{figure}	

First, assume that $1$ lies in the first segment (of length $\lambda_1$) and consider the following four possible subcases, pictured in Figure~\ref{fig:Lk first segment}. If $\lambda_1=1$, then we have $\pi_1=1$ and $\pi = 1\oplus \sigma$, where $\sigma$ is a $\bar{\lambda}$-unimodal involution. This contributes $x_1L^{k-1}(\x; \hat{x}_1)$ to the sum. If $\lambda_1>1$ and $\pi_1=1$, then $\pi=1\oplus \sigma$, where $\sigma$ is a $\bar\lambda$-unimodal involution, which contributes $x_1L^k(\x)$ to the sum. If $\lambda_1=2$ and $\pi_2=1$, then we necessarily have that $\pi_1=2$ since $\pi$ is an involution. Hence we must have $\pi = 21\oplus \sigma$, where $\sigma$ is a $\bar\lambda^1$-unimodal involution. This contributes $x_1^2L^{k-1}(\x; \hat{x}_1)$ to the sum. Finally, if $\lambda_1>2$ and $\pi_{\lambda_1} = 1$, then we must have $\pi_1 = \lambda_1$ and in turn $\pi = \lambda_1\alpha1\beta$, where the permutation $\sigma=\alpha\beta$ is order-isomorphic to a $\bar{\lambda}^1$-unimodal involution with the added condition that $\sigma_1>\bar{\lambda}^1_1$ or $\sigma_1\leq \bar{\lambda}^1_1$ and $\sigma_1\ldots\sigma_{\bar{\lambda}^1_1}$ is decreasing. This contributes $x_1^2L^k_1(\x)$ to the sum.



	\begin{figure}[!h]
	\centering
	\resizebox{.9\textwidth}{!}{%
	\begin{tabular}{@{}l@{}}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (5,5);
				\fill[red!10!white] (1,6) rectangle (5,9);
				\fill[red!10!white] (6,6) rectangle (9,9);
				\fill[red!10!white] (6,1) rectangle (9,5);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,5) rectangle (9,6);
				\draw[gray] (5,0) rectangle (6,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (1,0) -- (1,9);
				\draw[thick] (5,0) -- (5,9);
				\draw[thick] (6,0) -- (6,9);
%				\draw[red] (1,1) -- (5,1)--(5,5)--(1,5)--(1,1);
%				\draw[red] (9,6)--(6,6) -- (6,9);
%				\draw[red] (1,9)--(1,6)--(5,6)--(5,9);
%				\draw[red] (9,1)--(6,1)--(6,5)--(9,5);
				\foreach \x/\y in {6/1, 1/6}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (1,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (5,0) -- (6,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (5,5);
				\fill[red!10!white] (1,6) rectangle (5,9);
				\fill[red!10!white] (6,6) rectangle (9,9);
				\fill[red!10!white] (6,1) rectangle (9,5);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,5) rectangle (9,6);
				\draw[gray] (5,0) rectangle (6,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (3,0) -- (3,9);
				\draw[thick] (5,0) -- (5,9);
				\draw[thick] (6,0) -- (6,9);
%				\draw[red] (1,1) -- (5,1)--(5,5)--(1,5)--(1,1);
%				\draw[red] (9,6)--(6,6) -- (6,9);
%				\draw[red] (1,9)--(1,6)--(5,6)--(5,9);
%				\draw[red] (9,1)--(6,1)--(6,5)--(9,5);
				\foreach \x/\y in {6/1, 1/6}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (3,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (5,0) -- (6,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (4,4);
				\fill[red!10!white] (1,5) rectangle (4,9);
				\fill[red!10!white] (5,5) rectangle (9,9);
				\fill[red!10!white] (5,1) rectangle (9,4);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,4) rectangle (9,5);
				\draw[gray] (4,0) rectangle (5,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (1,0) -- (1,9);
				\draw[thick] (4,0) -- (4,9);
				\draw[thick] (7,0) -- (7,9);
%				\draw[red] (1,1) -- (4,1)--(4,4)--(1,4)--(1,1);
%				\draw[red] (9,5)--(5,5) -- (5,9);
%				\draw[red] (1,9)--(1,5)--(4,5)--(4,9);
%				\draw[red] (9,1)--(5,1)--(5,4)--(9,4);
				\foreach \x/\y in {5/1, 1/5}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (1,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (4,0) -- (7,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}
		\\
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (6,6);
				\fill[red!10!white] (1,7) rectangle (6,9);
				\fill[red!10!white] (7,7) rectangle (9,9);
				\fill[red!10!white] (7,1) rectangle (9,6);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,6) rectangle (9,7);
				\draw[gray] (6,0) rectangle (7,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (1,0) -- (1,9);
				\draw[thick] (4,0) -- (4,9);
				\draw[thick] (7,0) -- (7,9);
%				\draw[red] (1,1) -- (6,1)--(6,6)--(1,6)--(1,1);
%				\draw[red] (9,7)--(7,7) -- (7,9);
%				\draw[red] (1,9)--(1,7)--(6,7)--(6,9);
%				\draw[red] (9,1)--(7,1)--(7,6)--(9,6);
				\foreach \x/\y in {7/1, 1/7}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (1,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (4,0) -- (7,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (4,4);
				\fill[red!10!white] (1,5) rectangle (4,9);
				\fill[red!10!white] (5,5) rectangle (9,9);
				\fill[red!10!white] (5,1) rectangle (9,4);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,4) rectangle (9,5);
				\draw[gray] (4,0) rectangle (5,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (3,0) -- (3,9);
				\draw[thick] (4,0) -- (4,9);
				\draw[thick] (7,0) -- (7,9);
%				\draw[red] (1,1) -- (4,1)--(4,4)--(1,4)--(1,1);
%				\draw[red] (9,5)--(5,5) -- (5,9);
%				\draw[red] (1,9)--(1,5)--(4,5)--(4,9);
%				\draw[red] (9,1)--(5,1)--(5,4)--(9,4);
				\foreach \x/\y in {5/1, 1/5}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (3,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (4,0) -- (7,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (6,6);
				\fill[red!10!white] (1,7) rectangle (6,9);
				\fill[red!10!white] (7,7) rectangle (9,9);
				\fill[red!10!white] (7,1) rectangle (9,6);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,6) rectangle (9,7);
				\draw[gray] (6,0) rectangle (7,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (3,0) -- (3,9);
				\draw[thick] (4,0) -- (4,9);
				\draw[thick] (7,0) -- (7,9);
				\foreach \x/\y in {7/1, 1/7}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (3,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (4,0) -- (7,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}
		 \end{tabular}%
		 }
		\caption{This figure illustrates the case in the proof of Lemma \ref{lem:Lk} when $1$ lies in the $i$-th segment with $i>1$. From left-to-right along each row starting at the top left picture, these figures illustrate the following terms of the recurrence: $x_1x_i L^{k-2}(\x; \hat{x}_1, \hat{x}_i)$, $x_1x_iL^{k-1}_{i-1}(\x; \hat{x}_i) $, $x_1x_iL^{k-1}(\x; \hat{x}_1)$, $x_1x_iL^{k-1}(\x; \hat{x}_1)$, $x_1x_iL_{i-1}^k(\x)$, and $x_1x_iL_i^k(\x).$}
		\label{fig: Lk other segments}
	\end{figure}	

Now assume that $1$ lies in the $i$-th segment with $i>1$, and consider the six subcases pictured in Figure~\ref{fig: Lk other segments}. If $\lambda_1 =\lambda_i=1$ and $\pi({s_{\lambda}^i})=1$, then we must have 
$\pi = s_\lambda^i\alpha1\beta$, where the permutation $\sigma=\alpha\beta$ is order-isomorphic to a $\bar{\lambda}^i$-unimodal involution. This contributes $x_1x_i L^{k-2}(\x; \hat{x}_1, \hat{x}_i)$ to the sum for each $i>1$. If $\lambda_1>1$ and $\lambda_i=1$ (and thus $\pi({s_\lambda^i}) = 1$), then we must have that $\pi = s_\lambda^i\alpha1\beta$, where the permutation $\sigma=\alpha\beta$ is order-isomorphic to a $\bar{\lambda}^i$-unimodal involution with the added condition that $\sigma_1>s_{\bar{\lambda}^i}^{i-1}$ or $\sigma_1\leq s_{\bar{\lambda}^i}^{i-1}$ and $\sigma_1\ldots\sigma_{\bar{\lambda}^i_1}$ is decreasing. Thus, this contributes $x_1x_i L^{k-1}_{i-1}(\x; \hat{x}_i)$ to the sum for each $i>1$. If $\lambda_1=1$ and $\lambda_i>1$, then either $\pi(s_\lambda^i) =1$ or $\pi(s_\lambda^{i-1}+1) = 1$. In the former case, we have that $\pi = s_\lambda^i\alpha1\beta$, where the permutation $\sigma=\alpha\beta$ is order-isomorphic to a $\bar{\lambda}^i$-unimodal involution and in the latter case, we must have that $\pi = (s_\lambda^{i-1}+1)\alpha1\beta$, where the permutation $\sigma=\alpha\beta$ is order-isomorphic to a $\bar{\lambda}^i$-unimodal involution. Together, these contribute $2x_1x_iL^{k-1}(\x; \hat{x}_1)$ to the sum for each $i>1$. Finally, we have the subcase when $\lambda_1>1$ and $\lambda_i>1$. In this instance, we must have either  $\pi(s_\lambda^{i-1}+1) = 1$ or $\pi(s_\lambda^i) =1$.   If $\pi(s_\lambda^{i-1}+1) = 1$, then $\pi = (s_\lambda^{i-1}+1)\alpha1\beta$, where the permutation $\sigma=\alpha\beta$ is order-isomorphic to a $\bar{\lambda}^i$-unimodal involution with the added condition that $\sigma_1>s_{\bar{\lambda}^i}^{i-1}$ or $\sigma_1\leq s_{\bar{\lambda}^i}^{i-1}$ and $\sigma_1\ldots\sigma_{\bar{\lambda}^i_1}$ is decreasing.  If $\pi(s_\lambda^i) =1$, then $\pi = s_\lambda^i\alpha1\beta$, where the permutation $\sigma=\alpha\beta$ is order-isomorphic to a $\bar{\lambda}^i$-unimodal involution with the added condition that $\sigma_1>s_{\bar{\lambda}^i}^{i}$ or $\sigma_1\leq s_{\bar{\lambda}^i}^{i}$ and $\sigma_1\ldots\sigma_{\bar{\lambda}^i_1}$ is decreasing. Together, these contribute $x_1x_i[L_{i-1}^k(\x)  + L_{i}^k(\x)]$ to the sum for each $i>1$.
\end{proof}


	

\begin{lemma}
For $1\leq j\leq k$, the generating function $L^k_j(\x)$ satisfies the recurrence
\begin{align*}
L_j^k(\x) = & \, \frac{1}{1-x_1x_{j+1}}\bigg[D_j^k(\x) + \sum_{i=j+2}^k x_1x_{i} L_{i-1}^k(\x) \\ 
& + \sum_{i=j+1}^kx_1x_i[L_i^k(\x) + 2L^{k-1}(\x; \hat{x}_1) + L_{i-1}^{k-1}(\x; \hat{x}_i)+L^{k-2}(\x; \hat{x}_1, \hat{x}_i)] \bigg].
\end{align*}

\end{lemma}
\begin{proof}[Proof Sketch]
We will establish the equivalent formula: 
\begin{align*}
L_j^k(\x) = & \, D_j^k(\x) + \sum_{i=j+1}^k x_1x_{i}[ L_{i-1}^k(\x)+L_i^k(\x) + 2L^{k-1}(\x; \hat{x}_1) + L_{i-1}^{k-1}(\x; \hat{x}_i)+L^{k-2}(\x; \hat{x}_1, \hat{x}_i)].
\end{align*}
The proof is similar to the one for Lemma \ref{lem:Lk}, so we omit some of the details; the associated figures are also very similar to those in Figure \ref{fig: Lk other segments}.
%The associated figures can be found in Figure~\ref{fig:Ljk}.
 Let $\pi\in\Inv^\lambda$, where $\pi_1\leq s_\lambda^j$ and $\pi_1\ldots\pi_{\lambda_1}$ is decreasing or $\pi_1>s_\lambda^j$. In the first case, we get exactly those permutations enumerated using the generating function $D_j^k(\x)$. Otherwise, we must have that $\pi_1>s_\lambda^j$, which implies that if $\pi_k=1$, then $k>s_\lambda^j$. Thus for any $i\geq j+1$, we can add $i$ either to the beginning or end of the $i$-th unimodal segment. Again, there are six cases. The case when $\lambda_1=\lambda_i=1$ contributes $x_1x_iL^{k-2}(\x; \hat{x}_1, \hat{x}_i)$ to the sum for each $i\geq j+1$. In the case where $\lambda_1=1$ and $\lambda_i>1$, we can either have $\pi(s_\lambda^i)=1$ or $\pi(s_\lambda^{i-1}+1)=1$. This contributes $2x_1x_iL^{k-1}(\x; \hat{x}_1)$ to the sum for each $i\geq j+1$. The case when $\lambda_1>1$ and $\lambda_i=1$ contributes $x_1x_iL_{i-1}^{k-1}(\x; \hat{x}_i)$ for each $i\geq j+1$. In the case when $\lambda_1>1$ and $\lambda_i>1$, we can either have $\pi(s_\lambda^i)=1$ or $\pi(s_\lambda^{i-1}+1)=1$. This contributes $x_1x_{i}[ L_{i-1}^k(\x)+L_i^k(\x)]$ to the sum for each $i\geq j+1$. 
\end{proof}

\begin{lemma}\label{lem:Dki}
For $1<i\leq k$, the generating function $D_i^k(\x)$ satisfies the recurrence
$$
D_i^k(\x) = \frac{1}{1-x_1x_i}\bigg[D_{i-1}^k(\x)+x_1x_i[D_{i-1}^k(\x) +D_{i-1}^{k-1}(\x; \hat{x}_i)+L^{k-2}(\x; \hat{x}_1, \hat{x}_i) + 2L^{k-1}(\x; \hat{x}_1)]\bigg].
$$
\end{lemma}
\begin{proof}[Proof Sketch]
We will establish the equivalent formula: 
$$
D_i^k(\x) =  D_{i-1}^k(\x)+x_1x_i[D_i^k(\x) +D_{i-1}^k(\x) +D_{i-1}^{k-1}(\x; \hat{x}_i)+L^{k-2}(\x; \hat{x}_1, \hat{x}_i) + 2L^{k-1}(\x; \hat{x}_1)].
$$
Again, because of similarities to the proof of Lemma~\ref{lem:Lk}, we omit most of the details.  
The associated figures can be found in Figure~\ref{fig:Dki}.
	\begin{figure}[!h]
	\centering
	\resizebox{.9\textwidth}{!}{%
	\begin{tabular}{@{}l@{}}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (5,5);
				\fill[red!10!white] (1,6) rectangle (5,9);
				\fill[red!10!white] (6,6) rectangle (9,9);
				\fill[red!10!white] (6,1) rectangle (9,5);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,5) rectangle (9,6);
				\draw[gray] (5,0) rectangle (6,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (1,0) -- (1,9);
				\draw[thick] (5,0) -- (5,9);
				\draw[thick] (6,0) -- (6,9);
%				\draw[red] (1,1) -- (5,1)--(5,5)--(1,5)--(1,1);
%				\draw[red] (9,6)--(6,6) -- (6,9);
%				\draw[red] (1,9)--(1,6)--(5,6)--(5,9);
%				\draw[red] (9,1)--(6,1)--(6,5)--(9,5);
				\foreach \x/\y in {6/1, 1/6}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (1,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (5,0) -- (6,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (4,4);
				\fill[red!10!white] (1,5) rectangle (4,9);
				\fill[red!10!white] (5,5) rectangle (9,9);
				\fill[red!10!white] (5,1) rectangle (9,4);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,4) rectangle (9,5);
				\draw[gray] (4,0) rectangle (5,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (1,0) -- (1,9);
				\draw[thick] (4,0) -- (4,9);
				\draw[thick] (7,0) -- (7,9);
%				\draw[red] (1,1) -- (4,1)--(4,4)--(1,4)--(1,1);
%				\draw[red] (9,5)--(5,5) -- (5,9);
%				\draw[red] (1,9)--(1,5)--(4,5)--(4,9);
%				\draw[red] (9,1)--(5,1)--(5,4)--(9,4);
				\foreach \x/\y in {5/1, 1/5}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (1,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (4,0) -- (7,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (6,6);
				\fill[red!10!white] (1,7) rectangle (6,9);
				\fill[red!10!white] (7,7) rectangle (9,9);
				\fill[red!10!white] (7,1) rectangle (9,6);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,6) rectangle (9,7);
				\draw[gray] (6,0) rectangle (7,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (1,0) -- (1,9);
				\draw[thick] (4,0) -- (4,9);
				\draw[thick] (7,0) -- (7,9);
%				\draw[red] (1,1) -- (6,1)--(6,6)--(1,6)--(1,1);
%				\draw[red] (9,7)--(7,7) -- (7,9);
%				\draw[red] (1,9)--(1,7)--(6,7)--(6,9);
%				\draw[red] (9,1)--(7,1)--(7,6)--(9,6);
				\foreach \x/\y in {7/1, 1/7}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (1,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (4,0) -- (7,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}
		\\
				\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (5,5);
				\fill[red!10!white] (3,6) rectangle (5,9);
				\fill[red!10!white] (6,6) rectangle (9,9);
				\fill[red!10!white] (6,1) rectangle (9,5);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,5) rectangle (9,6);
				\draw[gray] (5,0) rectangle (6,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (3,0) -- (3,9);
				\draw[thick] (5,0) -- (5,9);
				\draw[thick] (6,0) -- (6,9);
%				\draw[red] (1,1) -- (5,1)--(5,5)--(1,5)--(1,1);
%				\draw[red] (9,6)--(6,6) -- (6,9);
%				\draw[red] (1,9)--(1,6)--(5,6)--(5,9);
%				\draw[red] (9,1)--(6,1)--(6,5)--(9,5);
				\foreach \x/\y in {6/1, 1/6}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (3,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (5,0) -- (6,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (4,4);
				\fill[red!10!white] (3,5) rectangle (4,9);
				\fill[red!10!white] (5,5) rectangle (9,9);
				\fill[red!10!white] (5,1) rectangle (9,4);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,4) rectangle (9,5);
				\draw[gray] (4,0) rectangle (5,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (3,0) -- (3,9);
				\draw[thick] (4,0) -- (4,9);
				\draw[thick] (7,0) -- (7,9);
%				\draw[red] (1,1) -- (4,1)--(4,4)--(1,4)--(1,1);
%				\draw[red] (9,5)--(5,5) -- (5,9);
%				\draw[red] (1,9)--(1,5)--(4,5)--(4,9);
%				\draw[red] (9,1)--(5,1)--(5,4)--(9,4);
				\foreach \x/\y in {5/1, 1/5}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (3,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (4,0) -- (7,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}\hspace{12pt}
		\begin{tikzpicture}[scale=.7]
			\newcommand\myx[1][(0,0)]{\pic at #1 {myx};}
			\tikzset{myx/.pic = {\draw 
			      (-2mm,-2mm) -- (2mm,2mm)
			      (-2mm,2mm) -- (2mm,-2mm);}}

				\fill[red!10!white] (1,1) rectangle (6,6);
				\fill[red!10!white] (3,7) rectangle (6,9);
				\fill[red!10!white] (7,7) rectangle (9,9);
				\fill[red!10!white] (7,1) rectangle (9,6);
				\draw[gray] (0,0) rectangle (9,9);
				\draw[gray] (0,0) rectangle (1,9);
				\draw[gray] (0,0) rectangle (9,1);
				\draw[gray] (0,6) rectangle (9,7);
				\draw[gray] (6,0) rectangle (7,9);
				%\draw[gray] (0,0) grid (1,1);
				\draw[thick] (3,0) -- (3,9);
				\draw[thick] (4,0) -- (4,9);
				\draw[thick] (7,0) -- (7,9);
				\foreach \x/\y in {7/1, 1/7}
				\myx[(\x-.5,\y-.5)];
				\draw[b] (0,0) -- (3,0) node[l] {\footnotesize $\lambda_1$};
				\draw[b] (4,0) -- (7,0) node[l] {\footnotesize $\lambda_i$};
		\end{tikzpicture}
		 \end{tabular}%
		 }
		\caption{This figure illustrates Lemma \ref{lem:Dki} when  $s_\lambda^{i-1}<\pi_1\leq s_\lambda^i$. From left-to-right along each row starting at the top left picture, these figures illustrate the following terms of the recurrence: $x_1x_iL^{k-2}(\x; \hat{x}_1, \hat{x}_i)$, $x_1x_iL^{k-1}(\x; \hat{x}_1)$, $x_1x_iL^{k-1}(\x; \hat{x}_1)$, $x_1x_iD_{i-1}^{k-1}(\x; \hat{x}_i)$, $x_1x_iD_{i-1}^k(\x)$, and $x_1x_iD_i^k(\x)$.}
		\label{fig:Dki}
	\end{figure}
		
	

%\todo{maybe we don't need figures here either? although I guess we need to fill space}
 Let $\pi\in\Inv^\lambda$, where $\pi_1\leq s_\lambda^i$ and $\pi_1\ldots\pi_{\lambda_1}$ is decreasing. In the case when $\pi_1\leq s_\lambda^{i-1}$, we have exactly those permutations enumerated by $D_{i-1}^k$. If $s_\lambda^{i-1}<\pi_1\leq s_\lambda^i$, then we must have that $\pi_1=s_\lambda^i$ or $\pi_1 =s_\lambda^{i-1}+1$. The case when $\lambda_1=\lambda_i=1$ contributes $x_1x_iL^{k-2}(\x; \hat{x}_1, \hat{x}_i)$ to the sum. The case when $\lambda_1=1$ and $\lambda_i>1$ contributes $2x_1x_iL^{k-1}(\x; \hat{x}_1)$ to the sum. The case when $\lambda_1>1$ and $\lambda_i=1$ contributes $x_1x_iD_{i-1}^{k-1}(\x; \hat{x}_i)$ to the sum. Finally, the case when $\lambda_1>1$ and $\lambda_i>1$ contributes $x_1x_i[D_i^k(\x) +D_{i-1}^k(\x)]$ to the sum. 
\end{proof}

\vspace{-10pt}

\section{The Gelfand character}

Let $G^k(\x)$ be defined to be as follows: 
$$G^k(\x) = \sum_\lambda \chi_\lambda^G x^\lambda,$$ where $\chi^G$ is the Gelfand character mentioned in the introduction, $\lambda$ is a partition of length $k$, and $\chi_\lambda^G$ is the value the character takes on the conjugacy class given by  $\lambda$. Then $G^k(\x)$ can be computed recursively from itself and two other series, $G_j^k$ and $H_i^k$, both defined in the next theorem.  

\begin{theorem}\label{main theorem 2}
We have $G^0(\x)=1$, $G^1(\x) = \dfrac{x_1}{1-x_1^2}$ and for $k \geq 2$,
\begin{align*}
G^k(\x) = & \, \frac{1}{1-x_1}\bigg[(x_1-x_1^2)G^{k-1}(\x;\hat{x}_1) -x_1^2(G^k_1(\x) -2H_1^k(\x)) +\sum_{i=2}^k x_1x_i [G^{k-2}(\x; \hat{x}_1, \hat{x}_i) \\
& +G_{i-1}^{k-1}(\x; \hat{x}_i)-2H_{i-1}^{k-1}(\x;\hat{x}_i)-G_i^k(\x)+2H_i^k(\x) +G_{i-1}^k(\x) -2H_{i-1}^k(\x)] \bigg];
\end{align*}
if $k \geq 1$, then $G_k^k(\x,t) = H_k^k(\x,t)$ and for $1\leq j<k$,
\begin{align*}
G_j^k(\x) = & \, \frac{1}{1-x_1x_{j+1}}\bigg[H_j^k(\x) + \sum_{i=j+2}^k x_1x_{i}G_{i-1}^k(\x)  + \sum_{i=j+1}^k x_1x_i [G^{k-2}(\x; \hat{x}_1, \hat{x}_i) \\
& +G_{i-1}^{k-1}(\x; \hat{x}_i)-2H_{i-1}^{k-1}(\x;\hat{x}_i)-G_i^k(\x)+2H_i^k(\x) -2H_{i-1}^k(\x)] \bigg];
\end{align*}
and if $k\geq 1$, then $H_1^k(\x) = \dfrac{x_1}{1+x_1}G^{k-1}(\x;\hat{x}_1)$ and for $1\leq i <k$, we have
\begin{align*}
H_i^k(\x) = & \, \frac{1}{1-x_1x_i}\bigg[H_{i-1}^k(\x)+x_1x_i[G^{k-2}(\x; \hat{x}_1, \hat{x}_i)-H_{i-1}^k(\x) -H_{i-1}^{k-1}(\x; \hat{x}_i)]\bigg].
\end{align*}
\end{theorem}

\begin{proof}[Proof Sketch]
The results of Section \ref{sec3} can quickly be extended to include $\lambda$-descents. Let $\Inv^\lambda(d)$ be the set of permutations $\pi\in\Inv^\lambda$ such that $\des_\lambda(\pi) = d$. Similarly, let $\Inv_j^\lambda(d)$ be the set of permutations $\pi\in\Inv_j^\lambda$ such that $\des_\lambda(\pi) = d$, and let $\mathcal{D}_i^\lambda(d)$ be the set of permutations $\pi\in\mathcal{D}_i^\lambda$ such that $\des_\lambda(\pi) = d$. Let
$$
L^k(\x,t) = \sum_{\lambda \in \Lambda_k}\sum_{d\geq0}|\Inv^\lambda(d)| x^\lambda t^{d}, \quad \quad \,  L_j^k(\x,t) = \sum_{\lambda \in \Lambda_k}\sum_{d\geq0}|\Inv_j^\lambda(d)| x^\lambda t^{d}, $$
$$
\text{ and } \quad D_i^k(\x,t) =\sum_{\lambda \in \Lambda_k}\sum_{d\geq0} |\mathcal{D}_i^\lambda(d)| x^\lambda t^{d}.
$$
We can keep track of descents by paying attention to where we add new elements. For example, consider Figure \ref{fig:Lk first segment}. In the first three cases, no descents would be added. However, in the last case, we would get an extra two descents if the first segment (of length $\lambda_1$) were decreasing (one descent in position 1 and one descent in position $\lambda_1-1$). Now consider Figure \ref{fig: Lk other segments}. Cases 1 and 3 add no descents; cases 2, 3, and 4 add one descent; and case 6 adds two descents. This gives us the formula:
\begin{align*}
L^k(\x,t) = & \, \frac{1}{1-x_1}\bigg[(x_1+x_1^2t)L^{k-1}(\x,t;\hat{x}_1) +x_1^2t(L^k_1(\x,t) +(t-1)D_1^k(\x,t)) \\
& +\sum_{i=2}^k x_1x_i [(t+1)L^{k-1}(\x,t; \hat{x}_1)+ L_{i-1}^{k-1}(\x,t; \hat{x}_i)+L_{i-1}^k(\x,t) +(t-1)D_{i-1}^k(\x,t) \\
& +(t-1)D_{i-1}^{k-1}(\x,t;\hat{x}_i)+ L^{k-2}(\x,t; \hat{x}_1, \hat{x}_i) + t(L_i^k(\x,t)+(t-1)D_i^k(\x,t))] \bigg];
\end{align*}
the formulas for $ L_j^k(\x,t)$ and $D_i^k(\x,t)$ are computed in a similar fashion. Notice that by Equation~\eqref{eq:char}, $$L^k(\x,-1) = \sum_\lambda \chi_\lambda^G x^\lambda= G^k(\x).$$ Thus, we can obtain the generating functions listed in the theorem. 
\end{proof}

%\section{Discussion}
%
%These results of Section \ref{sec3} can quickly be extended to include $\lambda$-descents. Let $\Inv^\lambda(d)$ be the set of permutations $\pi\in\Inv^\lambda$ such that $\des_\lambda(\pi) = d$. Similarly, let $\Inv_j^\lambda(d)$ be the set of permutations $\pi\in\Inv_j^\lambda$ such that $\des_\lambda(\pi) = d$, and let $\mathcal{D}_i^\lambda(d)$ be the set of permutations $\pi\in\mathcal{D}_i^\lambda$ such that $\des_\lambda(\pi) = d$. Let
%$$
%L^k(\x,t) = \sum_{\lambda \in \Lambda_k}\sum_{d\geq0}|\Inv^\lambda(d)| x^\lambda t^{d}, \quad \quad \,  L_j^k(\x,t) = \sum_{\lambda \in \Lambda_k}\sum_{d\geq0}|\Inv_j^\lambda(d)| x^\lambda t^{d}, $$
%$$
%\text{ and } \quad D_i^k(\x,t) =\sum_{\lambda \in \Lambda_k}\sum_{d\geq0} |\mathcal{D}_i^\lambda(d)| x^\lambda t^{d}.
%$$
%Then the following theorem holds. 
%\begin{theorem}\label{main theorem 2}
%We have $L^0(\x,t)=1$, $L^1(\x,t) = \dfrac{x_1}{(1-x_1)(1-x_1t)}$ and for $k \geq 2$,
%\begin{align*}
%L^k(\x,t) = & \, \frac{1}{1-x_1}\bigg[(x_1+x_1^2t)L^{k-1}(\x,t;\hat{x}_1) +x_1^2t(L^k_1(\x,t) +(t-1)D_1^k(\x,t)) \\
%& +\sum_{i=2}^k x_1x_i [(t+1)L^{k-1}(\x,t; \hat{x}_1)+ t(L_{i-1}^{k-1}(\x,t; \hat{x}_i)+(t-1)D_{i-1}^{k-1}(\x,t;\hat{x}_i)) \\
%&+ L^{k-2}(\x,t; \hat{x}_1, \hat{x}_i) + t(L_i^k(\x,t)+(t-1)D_i^k(\x,t)) +L_{i-1}^k(\x,t) +(t-1)D_{i-1}^k(\x,t)] \bigg];
%\end{align*}
%if $k \geq 1$, then $L_k^k(\x,t) = D_k^k(\x,t)$ and for $1\leq j<k$,
%\begin{align*}
%L_j^k(\x,t) = & \, \frac{1}{1-x_1x_{j+1}}\bigg[D_j^k(\x,t) + \sum_{i=j+2}^k x_1x_{i} L_{i-1}^k(\x,t) \\ 
%& + \sum_{i=j+1}^k x_1x_i [(t+1)L^{k-1}(\x,t; \hat{x}_1)+ t(L_{i-1}^{k-1}(\x,t; \hat{x}_i)+(t-1)D_{i-1}^{k-1}(\x,t;\hat{x}_i)) \\
%&+ L^{k-2}(\x,t; \hat{x}_1, \hat{x}_i) + t(L_i^k(\x,t)+(t-1)D_i^k(\x,t)) +L_{i-1}^k(\x,t) +(t-1)D_{i-1}^k(\x,t)] \bigg];
%\end{align*}
%and if $k\geq 1$, then $D_1^k(\x,t) = \dfrac{x_1}{1-x_1t}L^{k-1}(\x,t;\hat{x}_1)$ and for $1\leq i <k$, we have
%\begin{align*}
%D_i^k(\x,t) = & \, \frac{1}{1-x_1x_it^2}\bigg[D_{i-1}^k(\x,t)\\ 
%& +x_1x_i[tD_{i-1}^k(\x,t) +tD_{i-1}^{k-1}(\x,t; \hat{x}_i)+L^{k-2}(\x,t; \hat{x}_1, \hat{x}_i) + (t+1)L^{k-1}(\x,t; \hat{x}_1)]\bigg].
%\end{align*}
%\end{theorem}


Below are the first few terms of $G^k(\x)$ for $k\in \{1,2,3\}$ as computed from the formulas in Theorem \ref{main theorem 2}. 
\begin{align*}
G^1(x)   =& \, \,  x+x^3+x^5+x^7+ x^9 + x^{11} +x^{13} + x^{15}+ x^{17} + x^{19} +x^{21}+ x^{23} + x^{25} +\cdots \\
G^2(x,y) =& \, \,  2xy + xy^3 +2x^2y^2+ x^3y  + xy^5  + 4x^3y^3 +  x^5y  + xy^7 + x^3y^5+4x^4y^4   +\cdots \\
G^3(x,y,z) =& \, \,  4xyz + 2xyz^3 + 2xy^2z^2 +2x^2yz^2 + 2x^2y^2z + 2x^3yz   + 2xy^3z  + 4z^3yz^3+ \cdots \\
\end{align*}
Notice that for each $k\geq1$, $G^k(\x)$ is symmetric in its $k$ variables. This must happen since Equation~\eqref{eq:char} holds for any ordering of the composition $\lambda$. Therefore, if we would like to compute $\chi^G_{(1,1,3)}$, we can take either the coefficient of $xyz^3$, $xy^3z$, or $x^3yz$ in $G^k(\x)$ as our answer. In each case, we find that $\chi^G_{(1,1,3)}=2$.

%GIVE EXAMPLE OF L


%Notice that by Equation~\eqref{eq:char}, $$L^k(\x,-1) = \sum_\lambda \chi_\lambda^G x^\lambda,$$ where $\chi^G$ is the Gelfand character mentioned in the introduction and $\lambda$ is a partition of length $k$. This provides us with a way of computing the generating function for the Gelfand character.

%Though we omit it in the extended abstract, the authors will use these methods to find a combinatorial proof of (\ref{eq:char}). 

\section{Discussion}

It remains to determine the computational complexity for computing the Gelfand character using this method and to compare it with known methods (as in \cite{M-1937, N1940, R1997}). %One thing that appears different about this computation is that the Gelfand character is computed on the $k$th iteration for all $n$ so that $\lambda$ has $k$ parts. 

In addition, several other characters can be realized by studying certain properties of $\lambda$-unimodal permutations. In particular, if a set $B(n)\subseteq \mathcal{S}_n$ is a so-called \textit{fine set} (see for example, \cite{AR2015}), then $$\chi_\lambda=\sum_{\pi \in B(n)\cap \mathcal{L}^\lambda} (-1)^{\des_\lambda(\pi)}$$ where $\chi$ is a character of some representation of $\mathcal{S}_n$ and $\mathcal{L}^\lambda$ is the set of $\lambda$-unimodal permutations. Fine sets include conjugacy classes and their unions, Knuth classes, Coxeter length, and more \cite{AR2015}. It should be possible to employ techniques similar to the ones found in \cite{A2016} and here to find combinatorial proofs for the formulas of these characters. 

%\todo{reference back to Roichman's paper. For these, its the Gelfand character. Say there's not room in the extended abstract.}

\acknowledgements{The authors would like to thank the University of Texas at Tyler's Office of Sponsored Research and Center for Excellence in Teaching and Learning for their support in conducting this research. The awards from these offices supported the research conducted for this paper by two faculty members, Kassie Archer and L.-K. Lauderdale, together with undergraduate students Marin King, Thomas Lupo, and Francesca Rossi and graduate students Angela Gay and Virginia Germany.}


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
