\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\usepackage[usenames]{color}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{amsmath,amssymb,amsthm,
	mathtools,booktabs,tikz,latexsym}

\usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref}

\usepackage{breakurl}

\usepackage{float}

\usepackage{psfig}
\usepackage{epsf}
\usepackage{graphics}


\usepackage[centertableaux]{ytableau}

\usetikzlibrary{arrows,positioning,shapes.geometric}
\usepackage[capitalize,noabbrev]{cleveref}


\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}


\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\definecolor{lightblue}{rgb}{0.8,0.8,1.0}
\definecolor{lightgreen}{rgb}{0.8,1.0,0.8}

\definecolor{pBlue}{RGB}{86,139,190}
\definecolor{pCyan}{RGB}{149,186,201}
\definecolor{pSand}{RGB}{184,166,121}
\definecolor{pAlgae}{RGB}{87,115,135}
\definecolor{pSkin}{RGB}{236,216,167}
\definecolor{pGray}{RGB}{156,175,156}
\definecolor{pPink}{RGB}{215,114,127}
\definecolor{pOrange}{RGB}{211,153,80}

\setcounter{MaxMatrixCols}{20}


\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\newcommand{\thsup}{\textnormal{th}}

\newcommand{\setN}{\mathbb{N}}
\newcommand{\avec}{\mathbf{a}}

\newcommand{\symS}{S}


\DeclareMathOperator{\length}{\ell}
\DeclareMathOperator{\rev}{rev}
\DeclareMathOperator{\flip}{flip}
\DeclareMathOperator{\revflip}{revflip}

\DeclareMathOperator{\rlrm}{rlrm}
\DeclareMathOperator{\inv}{inv}

\newcommand{\PAP}{\mathrm{P}}
\newcommand{\RRP}{\mathrm{MP}}
\newcommand{\rrp}{\mathrm{\mathfrak{mp}}}
\newcommand{\pap}{\mathrm{\mathfrak{p}}}

\newcommand{\SEF}{\mathcal{F}}  
\DeclareMathOperator{\sefToPerm}{\mathtt{sefToPerm}}


\tikzset{every picture/.append
	style={scale=1,
		baseline=(current bounding box.center),
		x=1em,
		y=1em,
		thinLine/.style={line width=0.7pt},
		thickLine/.style={line width=1.4pt,line join=round},
		snaking/.style={decorate,decoration={zigzag,segment length=1.0mm,amplitude=0.15mm}},
		fillGrey/.style={fill=black!30},
		entries/.style={xshift=-0.5em,yshift=-0.5em,font=\small},
		bgEntry/.style={xshift=-0.5em,yshift=-0.5em,font=\small,
			regular polygon,regular polygon sides=4,fill,inner sep=0pt,minimum size=1em
		},
		circled/.style={circle,draw,inner sep=0pt,minimum size=1em},
		mydot/.style={circle,fill=black,inner sep=0pt,minimum size=1mm}
	}
}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


	\begin{center}
	\vskip 1cm{\LARGE\bf Pattern-Avoidance and Fuss--Catalan\\ \vskip 0.3cm
		Numbers}\\
		\vskip 1cm
		\large
		\begin{minipage}{3.0in}
		\begin{center}
		Per Alexandersson\\
		Department of Mathematics\\ Stockholm University\\
		S-106 91 Stockholm \\  Sweden\\
		\href{mailto: per.w.alexandersson@gmail.com}{\tt per.w.alexandersson@gmail.com}\\
		\ \\
		Samuel Asefa Fufa\\
		Department of Mathematics \\ Addis Ababa University\\
		1176 Addis Ababa \\ Ethiopia\\
		\href{mailto: samuel.asefa@aau.edu.et}{\tt samuel.asefa@aau.edu.et}\\
		\end{center}
	\end{minipage} 
	\quad
	\begin{minipage}{3.0in}
	\begin{center}
		Frether Getachew Kebede\\
		Department of Mathematics \\ Addis Ababa University\\
		1176 Addis Ababa \\ Ethiopia\\
		\href{mailto: frigetach@gmail.com}{\tt frigetach@gmail.com}\\
		\ \\
		Dun Qiu\\
		Center for Combinatorics, LPMC\\ Nankai University\\
		Tianjin 300071 \\ P.\ R.\ China\\
		\href{mailto: qiudun@nankai.edu.cn}{\tt qiudun@nankai.edu.cn}\\
	\end{center}
		\end{minipage}
	\end{center}

\vskip .2in

\begin{abstract}
	We study a subset of permutations where entries are restricted to having the same 
	remainder as the index, modulo some integer $k \geq 2$.
	We show that by also imposing the classical 132- or 213-avoidance restriction on the permutations, 
	we recover the Fuss--Catalan numbers and some special cases of the Raney numbers.
	
	Surprisingly, an analogous statement also holds when we 
	impose the mod $k$ restriction on a Catalan family of subexcedant functions.
	
	Finally, we completely enumerate all combinations of mod-$k$-alternating 
	permutations that avoid two patterns of length 3. 
	This is analogous to the systematic study
	by Simion and Schmidt, of permutations avoiding two patterns of length 3.
\end{abstract}

\section{Introduction}
It is classically known that the number of permutations of length $n$
avoiding a permutation-pattern of length $3$ is counted by the Catalan number, $C_n$.
There is a plethora of other combinatorial objects that are counted by $C_n$;
see, e.g., \cite{StanleyCatalan}.
One classical Catalan family are the \textit{Dyck paths}---paths using
steps in $\{(1,0),(0,1)\}$, starting at $(0,0)$, ending at $(n,n)$,
and never going below the line $y=x$. This family can be generalized
to counting paths that never go below $y=kx$
and end at $(kn,n)$ for some fixed positive integer $k$. 
The number of such paths is the \textit{Fuss--Catalan number}:
\begin{equation*}
	C_n^{k+1} \coloneqq \frac{1}{(k+1)n+1} \binom{(k+1)n+1}{n} = \frac{1}{kn+1} \binom{(k+1)n}{n}.
\end{equation*}

In this paper, we find several \textit{Fuss}-generalizations 
of pattern-avoiding permutations by imposing additional 
restrictions on the entries in the permutations.

A parity-alternating permutation starting with an odd integer (PAP)
sends even integers to even integers and odd integers to odd. 
This set of permutations has been studied previously in
\cite{Tanimoto2010} when considering the ascent statistic and signed Eulerian numbers,
and later in \cite{KebedeRakotondrajao2021} where parity-alternating derangements
are enumerated.

We generalize the notion of parity-alternating permutations
to \textit{mod-$k$-alternating permutations}. Here, we require
that $\pi_i$ is congruent to $i$ (mod $k$), where $k \geq 1$ is a fixed integer.
This notion is not to be confused with the generalization in
\cite{Munagi2014}, where the size of blocks of entries with the
same parity are restricted (but not restricted to be $1$).

We enumerate the mod-$k$-alternating permutations under pattern-avoidance,
for each of the patterns in $\{132,213,231,312\}$.
Moreover, we also enumerate the mod-$k$-alternating
permutations that avoid two patterns of length $3$.
The number of mod-$k$-alternating permutations of length $n$
avoiding $\sigma$ is denoted $\rrp_\sigma(n,k)$.


We also consider subexcedant functions.
These are simply words of positive integers, $f_1,f_2,\ldots,f_n$,
such that $f_i \leq i$. There is a (specific) bijection between 
permutations of length $n$ and subexcedant functions of length $n$ 
(introduced in \cite{MantaciRakotondrajao2001}) so one can study 
subexcedant functions instead of permutations.
The mod-$k$-alternating restriction translates under this bijection to 
the exact same restriction on the subexcedant function.
In other words, $f_i \equiv i$ (mod $k$); see \cref{propsefRRPs}.


\subsection{Main results}

In \cref{secmodKPattern} we prove the following theorem.
In particular, this shows that $\rrp_\sigma(n,k)$ is a Raney 
number and that $\rrp_\sigma(km,k)$ is a Fuss--Catalan number.
\begin{theorem}[{\cref{cormainFussCatalan} below}]
	Let $\sigma \in \{132,213\}$ and $n,k \geq 1$.
	Let $m$ and $j$ be defined via $n=km+j$ with $0 \leq j < k$.
	Then
	\[
	\rrp_\sigma(n,k) =  \frac{j+1}{km+j+1} \binom{ (k+1)m + j }{km+j}.
	\]
	In particular
	\[
	\rrp_\sigma(km,k) = \frac{1}{(k+1)m+1} \binom{(k+1)m+1}{m}
	= \frac{1}{km+1} \binom{(k+1)m}{m}.
	\]
\end{theorem}

In \cref{secsubex}, we prove our second main result.
We let $\rrp_C(n,k)$ denote the set of mod-$k$-alternating
permutations whose subexcedant function satisfy the following two properties:
\begin{itemize}
	\item $f_i \equiv i$ (mod $k$),
	\item $1 \leq f_i \leq f_{i-1}+1$ for all $i \in \{2,3,\ldots,n\}$.
\end{itemize}
The first property is analogous to the mod-$k$-alternating property 
on permutations. Subexcedant functions that satisfy the second property
are enumerated by the Catalan numbers. The second condition is therefore
a natural analog to permutations avoiding a fixed-length-3 pattern.
We have the following result:

\begin{theorem}[{\cref{corsubexFuss} below}]
	Let $m$ and $j$ be defined via $n=km+j$ with $0 \leq j < k$.
	Then
	\[
	\rrp_C(n,k) =  \frac{j+1}{km+j+1} \binom{ (k+1)m + j }{km+j}
	\]
	and in particular
	\[
	\rrp_C(km,k) = \frac{1}{(k+1)m+1} \binom{(k+1)m+1}{m}
	= \frac{1}{km+1} \binom{(k+1)m}{m}.
	\]
\end{theorem}

We prove these two enumerative results by showing that the combinatorial objects satisfy certain recursions.
These recursions can then be used to produce a canonical bijection 
between $\rrp_{132}(n,k)$ and $\rrp_C(n,k)$, for example.
However, this bijection is not a restriction of any classical bijection 
that sends subexcedant functions to permutations.

Finally, in \cref{sec2patterns} we systematically enumerate 
all families of mod-$k$-alternating permutations 
avoiding two (different) patterns of length 3.


\section{Preliminaries}

Given a word $w = [w_1,\ldots,w_\ell]$ and an integer $n$, 
we let $n+w$ denote the word 
\[
 [w_1+n,w_2+n,\ldots,w_\ell+n].
\]
This convention is extended
to the expressions $w-n$ and $n-w$ in a natural manner.
If $\alpha = [\alpha_1,\ldots,\alpha_r]$ and $\beta = [\beta_1,\ldots,\beta_s]$
are words, then $[\alpha,\beta]$ denotes the concatenation
$
[\alpha_1,\ldots,\alpha_r, \beta_1,\ldots,\beta_s]
$.
We use several variants of this convention. 
We use the term \textit{subword} to denote a sequence 
of consecutive entries in a word.

The set $\{1,2,\ldots,n\}$ is denoted by $[n]$ 
(the context should make it clear that this is not
to be interpreted as the word of one letter).
The set of permutations of $[n]$ is denoted by $\symS_n$.
We use brackets for permutations in one-line notation and regular parenthesis to denote cycles.
We make use of four well-known involutions on $\symS_n$,
\textit{inverse}, \textit{reverse}, \textit{flip}, and \textit{revflip};
for $\pi = [\pi_1,\ldots,\pi_n] \in \symS_n$, we let
\[
\rev(\pi) \coloneqq [\pi_n,\pi_{n-1},\ldots,\pi_1], \;
\flip(\pi) \coloneqq n+1-\pi, \;
\text{ and } \;
\revflip(\pi) \coloneqq \flip(\rev(\pi)).
\]

For permutations $\pi, \omega \in \symS_n$, we think
of multiplication as a composition of functions so that
$(\pi \circ \omega)(k) = \pi(\omega(k))$ whenever $1 \leq k \leq n$.
Given $\pi$, we associate it with its permutation matrix;
\[
M_\pi \coloneqq \big( \delta_{i, \pi(j)} \big)_{1 \leq i, j \leq n}.
\]
The permutation matrix of the composition $\pi \circ \omega$ is $M_{\pi} M_{\sigma}$.
We follow the convention in \cite{Kitaev2011}
and illustrate permutation matrices by letting row indices start at the bottom,
as in \cref{figpermMatrix}. From now on, this is the picture we have in mind when
referring to permutation matrices.

\begin{figure}[!ht]
	\[
	M_\pi =
	\begin{pmatrix}
		0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
		0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
		0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
		0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
		0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
		0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
		0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
		1 & 0 & 0 & 0 & 0 & 0 & 0 & 0
	\end{pmatrix}
	\qquad
	\ytableausetup{boxsize=0.8em}
	\begin{ytableau}
		\none[8]& \, & \bullet & \, & \, & \, & \, & \, & \, \\
		\none[7]& \, & \, & \, & \, & \bullet & \, & \, & \, \\
		\none[6]&\, & \, & \, & \, & \, & \, & \bullet & \, \\
		\none[5]& \, & \, & \bullet & \, & \, & \, & \, & \, \\
		\none[4]& \, & \, & \, & \, & \, & \bullet & \, & \, \\
		\none[3]& \, & \, & \, & \bullet & \, & \, & \, & \, \\
		\none[2]& \, & \, & \, & \, & \, & \, & \, & \bullet \\
		\none[1]& \bullet & \, & \, & \, & \, & \, & \, & \, \\
		\none   & \none[1]&\none[2]&\none[3]&\none[4]&\none[5]&\none[6]&\none[7]&\none[8]
	\end{ytableau}
	\]
	\caption{
		The permutation matrix $M_\pi$ associated with $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$,
		where the bottom row is the first row.
		The rightmost figure is simply the graph of the function $i \mapsto \pi(i)$
		in Cartesian coordinates.
	}\label{figpermMatrix}
\end{figure}


\subsection{Permutation patterns}

A permutation $\pi \in \symS_n$ is said to contain the pattern $\sigma \in \symS_k$
if there is a subsequence of $\pi$ that is order-isomorphic to $\sigma$.
Otherwise, $\pi$ is said to avoid $\sigma$ and $\symS_{\sigma}(n)$ denotes
the set of $\sigma$-avoiding permutations over $[n]$. 
We simply write the pattern as a word.
For example, $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$ contains the pattern $231$
as the subsequence $3, 6, 2$ in $\pi$.
However, $[1, 7, 6, 4, 2, 3, 5, 8]$ avoids the pattern $231$.

\begin{figure}[!ht]
	\[
	M_\pi =
	\ytableausetup{boxsize=0.8em}
	\begin{ytableau}
		\, & \bullet & \, & \, & \, & \, & \, & \, \\
		\, & \, & \, & \, & \bullet & \, & \, & \, \\
		\, & \, & \, & \, & \, & \, & \ast & \, \\
		\, & \, & \bullet & \, & \, & \, & \, & \, \\
		\, & \, & \, & \, & \, & \bullet & \, & \, \\
		\, & \, & \, & \ast & \, & \, & \, & \, \\
		\, & \, & \, & \, & \, & \, & \, & \ast \\
		\bullet & \, & \, & \, & \, & \, & \, & \, \\
	\end{ytableau}
	\qquad
	M_\sigma =
	\begin{ytableau}
		\, & \ast & \, \\
		\ast & \, & \, \\
		\, & \, & \ast \\
	\end{ytableau}
	\]
	\caption{
		The permutation matrices associated with $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$
		and $\sigma = 231$. Here we see that $\pi$
		contains the pattern $\sigma$ (there are other instances of this pattern in $\pi$).
	}\label{figpermPatternContainment}
\end{figure}

A pattern of length $3$ is the first non-trivial case to consider 
and we use a one-line notation without the parentheses to represent such a pattern.
In \cref{fig132Avoiding}, we show the structure of $132$-avoiding permutations.
Any permutation of length $n$ avoiding the pattern $132$ must be of the form
\[
\pi = [\alpha_1, \ldots, \alpha_j, \; n, \; \beta_1,\ldots,\beta_{n-1-j}],
\]
where $\min(\alpha_1,\ldots,\alpha_j) > \max(\beta_1,\ldots,\beta_{n-1-j})$.

\begin{figure}[!ht]
	\centering
	\begin{tikzpicture}[scale=1.6]
		\draw[black,fill=pOrange] (0,2) rectangle (2,4);
		\draw[black,fill=pBlue] (2,4) rectangle (3,5);
		\draw[black,fill=pAlgae] (3,0) rectangle (5,2);
		\draw[black, dashed] (0,2) -- (5,2);
		\draw[black, dashed] (0,4) -- (5,4);
		\draw[black, dashed] (2,0) -- (2,5);
		\draw[black, dashed] (3,0) -- (3,5);
		\node at (2.5,4.5) {$n$};
	\end{tikzpicture}
	\caption{The structure of a permutation matrix that avoids the pattern $132$.
		The larger regions on the left and right are also $132$-avoiding
		which explains the ``Catalan structure''.
	}\label{fig132Avoiding}
\end{figure}
Permutations avoiding one pattern of length 3 have been studied extensively
and it is well-known (first proved by Knuth \cite{Knuth1997ArtOfProgramming,Knuth1998ArtOfProgramming})
that for all $n\geq 0$, we have
\[
|\symS_{123}(n)|=|\symS_{132}(n)|=|\symS_{213}(n)|=|\symS_{231}(n)|=|\symS_{312}(n)|=|\symS_{321}(n)| = \frac{1}{n+1}\binom{2n}{n}.
\]

For patterns $\sigma$ of length 3, the inverse map, the $\rev$ map, and the $\revflip$ map
are bijections between some of the sets $\symS_{\sigma}(n)$; see \cref{figlength3Bijections}.


\section{Fuss--Catalan numbers and Raney numbers}

The main result in this section is \cref{propgeneralFormula},
where we give a closed-form formula for
numbers $a_k(n)$ (defined in \eqref{eqakrecursion} below)
that generalize the Fuss--Catalan numbers. 
The recurrence defining the $a_k(n)$ shows up in several places in the later sections.


The \textit{Fuss--Catalan numbers}, $C_n^p$,
generalize the classical Catalan numbers. 
Note that for $p=2$ we recover the classical Catalan numbers; see \cref{tabfussCatalan}.
There is an extensive literature on Catalan numbers and we refer readers to Stanley's
large collection of Catalan objects and information~\cite{StanleyCatalan}.

If we set
\[
F_p(z) \coloneqq \sum_{n \geq 0} \frac{1}{pn+1} \binom{pn+1}{n} z^n,
\]
then Lambert \cite{Lambert1758, Lambert1770} proved that 
\[
F_p(z) = 1 + z(F_p(z))^p.
\]
A modern proof can be found in \cite[Eq.\ 7.68]{GrahamKnuthPatashnik1994}.
It follows that for all $\alpha \in \setN^{p}_{\geq 0}$, we have 
\begin{equation*}
	C_n^p = \sum_{\alpha} C_{\alpha_1}^p \cdot C_{\alpha_2}^p \cdot \cdots \cdot C_{\alpha_{p}}^p \qquad
	C_0^p = 1,
\end{equation*}
where the sum of the entries in $\alpha$ equals $n-1$. 
Note that this relation uniquely defines the sequence $(C_n^p)_{n\geq 0}$.


\begin{figure}[!ht]
	\centering
	\begin{tikzpicture}[xscale=4.8,yscale=4.5,baseline=40pt,
		circ/.style={circle,draw,inner sep=1pt, minimum width=4pt}
		]
		\node[circ] (132) at (0, 0) {$132$};
		\node[circ] (213) at (-1, 0) {$213$};
		\node[circ] (231) at (0, 1) {$231$};
		\node[circ] (312) at (-1, 1) {$312$};
		\node[circ] (321) at (1.5, 1) {$321$};
		\node[circ] (123) at (-2.5, 0) {$123$};
		\draw[black,thick,<->] (132)--(213) node[midway,below] {$\revflip$};
		\path (213) edge [loop below] node {inverse} (213);
		\path (132) edge [loop below] node {inverse} (132);
		\draw[black,thick,<->] (231)--(312) node[midway,above] {$\revflip$};
		\draw[black,thick,<->] (231)--(312) node[midway,below] {inverse};
		\draw[black,thin,dashed,<->] (231)--(132) node[midway,right] {$\rev$};
		\draw[black,thin,dashed,<->] (312)--(213) node[midway,left] {$\rev$};
		\path (123) edge [loop above] node {$\revflip$} (123);
		\path (321) edge [loop below] node {$\revflip$} (321);
	\end{tikzpicture}
	\caption{Bijections between sets of permutations that avoid a pattern of length $3$;
		see \cite{SimionSchmidt1985} for details.
		There are more well-known bijections but the ones shown above 
		also respect the parity-alternating property.
	}\label{figlength3Bijections}
\end{figure}


The Fuss--Catalan numbers can be modeled as the number of
non-crossing partitions of certain polygons
using $(p+1)$-gons; see \cite[p.\ 78]{BrakMahony2019x}.
Another interpretation using lattice paths was mentioned in the introduction.
\begin{table}[!ht]
	\centering
	\begin{tabular}{c|rrrrrrrr}
		 &1&2&3&4 &5&6&7&8 \\
		\hline
		$C_n^1$& 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
		$C_n^2$& 1 & 2 & 5 & 14 & 42 & 132 & 429 & 1430 \\
		$C_n^3$& 1 & 3 & 12 & 55 & 273 & 1428 & 7752 & 43263 \\
		$C_n^4$& 1 & 4 & 22 & 140 & 969 & 7084 & 53820 & 420732 \\
		$C_n^5$& 1 & 5 & 35 & 285 & 2530 & 23751 & 231880 & 2330445   \\
	\end{tabular}
	\caption{The values of $C_n^p$, with $n=1,2,\ldots,8$ and $p=1,2,\ldots,5$.}\label{tabfussCatalan}
\end{table}

The \textit{Raney numbers} (introduced in \cite{Raney1960}) may be defined as
\[
R_m(p,r) \coloneqq \frac{r}{mp+r} \binom{mp+r}{m}
\]
and are sometimes called the \textit{two-parameter Fuss--Catalan numbers}.
Note that $C_n^p = R_n(p,1)$, so the Raney numbers contain the Fuss--Catalan numbers as a sub-family.


\begin{proposition}\label{propgeneralFormula}
	Fix $k \in \setN$ and let the sequence $(a_k(n))_{n=0}^\infty$
	be defined by the recursion
	\begin{equation}\label{eqakrecursion}
		a_{k}(n+1) = \sum_{\substack{0\leq i \leq n \\ k \mid i}} a_{k}(i) a_{k}(n-i),\qquad a_k(0)\coloneqq 1.
	\end{equation}
	The closed-form expression for $a_k(n)$ is then given by
	\begin{equation}\label{eqclosedForm}
		a_{k}(km+j) = \frac{j+1}{km+j+1} \binom{ (k+1)m + j }{km+j}
	\end{equation}
	where we write $n=km+j$ with $0 \leq j < k$.
	In particular,
	\begin{equation}\label{corakGivesFussCat}
		a_k(km+j) = R_m(k+1,j+1)  \text{ and } a_k(km) = C^{k+1}_m
	\end{equation}
	so the $a_{k}(n)$ form a sub-family of the Raney numbers, which includes the Fuss--Catalan numbers.
\end{proposition}
\begin{proof}
	Let us first set
	\[
	A_k(t)    \coloneqq \sum_{m\geq 0} a_k(km) t^m \text{ and }
	B_{k,j}(t) \coloneqq \sum_{m\geq 0} a_k(km+j) t^m \text{ for } 0 \leq j \leq k.
	\]
	Our first goal is to obtain functional equations
	for the $B_{k,j}(t)$. We shall first prove that
	\begin{equation}\label{eqfunctionEquations}
		B_{k,j}(t) = (A_k(t))^{j+1}
		\qquad \text{ and } \qquad
		A_k(t) = 1 + t \cdot (A_k(t))^{k+1}.
	\end{equation}
	Let $j$ now be fixed with $1 \leq j \leq k$.
	The recursion in \eqref{eqakrecursion} can then be rewritten as
	\[
	\sum_{m\geq 0}  a_k(km+j)t^{m} = \sum_{m\geq 0} t^{m} \sum_{i} a_k(ki) \cdot a_k(km+j-1-ki)
	\]
	by first substituting $n \mapsto km+j-1$ and then multiplying by $t^{m}$ 
	on both sides followed by summing over $m$.
%
	We then have 
	\begin{align*}
		B_{k,j}(t) = \sum_{m\geq 0} \sum_{i} a_k(ki) t^i \cdot  a_k(km-ki+j-1) t^{m-i}
		= A_k(t) \cdot B_{k,j-1}(t).
	\end{align*}
	A simple inductive argument over $j$ concludes the proof
	and the first set of relations in \eqref{eqfunctionEquations} is established.
	On one hand, we now have 
	$ B_{k,k}(t) = (A_k(t))^{k+1}$.
	On the other hand, the definition of the $B_{k,j}$
	tells us that $1 + t B_{k,k}(t) = A_k(t)$. So 
	\[
	A_k(t) = 1 + t (A_k(t))^{k+1}
	\]
	which is the second relation in \eqref{eqfunctionEquations}.
	
	Recall that Lagrange inversion (see \cite[Thm.\ 5.1.1]{Wilf1994}) 
	states that if $x(t)$ satisfies the functional 
	equation $x(t) = t \cdot \phi( x(t) )$ with $\phi(0) \neq 0$, then 
	\begin{equation}\label{eqlagrangeInversion}
		f(x(t)) \bigg \vert_{t^n}  = \frac{1}{n}  f'(x) \phi(x)^n \bigg \vert_{x^{n-1}}.
	\end{equation}
	The recursion for $A_k(t)$ we had before is precisely of the form $x(t) = t \cdot \phi( x(t) )$
	when $x(t) = A_k(t)-1$, $f(x)=1+x$ and $\phi(x)=(1+x)^{k+1}$.
	Hence, Lagrange inversion gives
	\[
	A_k(t) \bigg \vert_{t^m} = \frac{1}{m}  (1+x)^{(k+1)m} \bigg \vert_{x^{m-1}},
	\]
	which gives the $j=0$ case of \eqref{eqclosedForm}.
	
	If we instead choose $f(x)=(1+x)^{j+1}$ but keep $x(t) = A_k(t)-1$ and $\phi(x)=(1+x)^{k+1}$
	in \eqref{eqlagrangeInversion}, then
	\[
	B_{k,j}(t) \bigg \vert_{t^m} =
	(A_{k}(t))^{j+1} \bigg \vert_{t^m} =\frac{j+1}{m} (1+x)^{(k+1)m+j} \bigg \vert_{x^{m-1}}=\frac{j+1}{m}\binom{(k+1)m+j}{m-1}.
	\]
	This proves the remaining cases in \eqref{eqclosedForm}.
\end{proof}

\begin{lemma}\label{lemanotherrecur}
	For a fixed $r$ in $\{0,1,\ldots,k-1\}$ and $m\geq 1$, we have 
	\begin{equation}\label{eqanotherrecur}
		a_k(km)=\sum_{j=0}^{m-1} a_k(kj+r)a_k(k(m-j)-r-1)
	\end{equation}
	where $a_k(n)$ is the sequence in \cref{propgeneralFormula}.
\end{lemma}
\begin{proof}
	In the notation of \cref{propgeneralFormula} it is straightforward to prove that 
	\[
	A_k(t)=1+tB_{k,r}(t)B_{k,k-1-r}(t)
	\]
	by using \eqref{eqfunctionEquations}. 
	Comparing coefficients now gives the desired formula.
\end{proof}



\section{Mod-\texorpdfstring{$k$}{k}-alternating permutations and pattern avoidance}\label{secmodKPattern}


\subsection{Mod-\texorpdfstring{$k$}{k}-alternating permutations}

Let $\PAP(n)$ denote the set of parity alternating permutations (PAP)
starting with an odd entry and let $\pap(n)$ be the cardinality of $\PAP(n)$.
Moreover, we let $\PAP_\sigma(n)$ be the set of PAPs avoiding the permutation pattern $\sigma$.
We also let $\PAP_{\sigma,\tau}(n)$ be the set of PAPs avoiding patterns $\sigma$ and $\tau$.

Similarly, $\PAP^*(n)$ denotes the set of parity-alternating permutations starting with
an \textit{even} entry; $\PAP^*_\sigma(n)$ and $\PAP^*_{\sigma,\tau}(n)$ are defined analogously.

The following lemma is straightforward to verify.
\begin{lemma}\label{lemrevBij}
	For $m \geq 0$, the maps
	\begin{align*}
		&\rev: \PAP_{132}(2m)  \to \PAP^*_{231}(2m) \\
		&\rev: \PAP_{231}(2m)  \to \PAP^*_{132}(2m) \\
		&\rev: \PAP_{132}(2m+1)  \to \PAP_{231}(2m+1) \\
		&\rev: \PAP_{231}(2m+1)  \to \PAP_{132}(2m+1)
	\end{align*}
	are bijections. 
\end{lemma}
For instance, $34561278$ is mapped to $87216543$, and $5234167$ 
is mapped to $7614325$ under the reverse map. 
Note that $34561278$ and $5234167$ are $132$-avoiding 
and $87216543$ and $7614325$ are $231$-avoiding.

\begin{definition}
	Given $k\geq 2$, a \textit{mod-$k$-alternating permutation} of size $n$
	is a permutation $\pi \in \symS_n$ such that
	\[
	\pi(i)\equiv i \,\,(\text{mod } k) \qquad \text{ for all $i=1,2,\ldots,n$}.
	\]
	Let $\RRP(n,k)$ be the set of such mod-$k$-alternating permutations 
	and we set 
	\[
	\RRP_\sigma(n,k)\coloneqq\RRP(n,k)\cap\symS_\sigma(n).
	\]
	Note that it can be easily seen that $\RRP(n,k)$ is closed under compositions and
	taking inverses, so that it is a subgroup of $\symS_n$.
	
	For $k=2$ we recover the classical parity-alternating permutations starting with an odd integer.
	Note that
	\begin{align*}
		\rrp(n,k)\coloneqq|\RRP(n,k)| = \Bigl(\Big\lceil\frac{n}{k}\Big\rceil!\Bigr)^j\Bigl(\Big\lfloor\frac{n}{k}\Big\rfloor!\Bigr)^{k-j}
	\end{align*}
	where $j$ is the remainder when $n$ is divided by $k$. 
	We set $\rrp_\sigma(n,k)\coloneqq|\RRP_\sigma(n,k)|$. 
\end{definition}

\begin{example}
	For example, $\RRP(7,3)$ has $(3!)^1 \cdot (2!)^2 = 24$ elements:
	\begin{equation*}
		\begin{matrix}
			[1,2,3,4,5,6,7] & [1,2,6,4,5,3,7] & [1,5,3,4,2,6,7] & [1,5,6,4,2,3,7] & [1,2,3,7,5,6,4]\\
			[1,2,6,7,5,3,4] &  [1,5,3,7,2,6,4] & [1,5,6,7,2,3,4] & [4,2,3,1,5,6,7] & [4,2,6,1,5,3,7]\\ 
			[4,5,3,1,2,6,7] & [4,5,6,1,2,3,7] & [4,2,3,7,5,6,1] & [4,2,6,7,5,3,1] & [4,5,3,7,2,6,1]\\ 
			[4,5,6,7,2,3,1] & [7,2,3,1,5,6,4] & [7,2,6,1,5,3,4] & [7,5,3,1,2,6,4] & [7,5,6,1,2,3,4]\\
			[7,2,3,4,5,6,1]& [7,2,6,4,5,3,1] & [7,5,3,4,2,6,1] & [7,5,6,4,2,3,1]. & \\
		\end{matrix}
	\end{equation*}
\end{example}


We shall also introduce some notation for mod-$k$-alternating permutations
starting with the remainder $r$ mod $k$.
\begin{definition}
	Let $\RRP(n,k,r)$ denote the set of permutations of length $n$
	that satisfy
	\begin{equation}\label{eqmodKwithRemainder}
		\pi(i) \equiv (r+i-1)\,\,(\text{mod } k) \qquad\text{ for all $1 \leq i \leq n$}.
	\end{equation}
	Moreover, we set $\RRP_\sigma(n,k,r) \coloneqq \RRP(n,k,r) \cap \symS_\sigma(n)$, $\rrp(n,k,r)\coloneqq |\RRP(n,k,r)|$, and $\rrp_\sigma(n,k,r)\coloneqq |\RRP_\sigma(n,k,r)|$.
\end{definition}

\begin{lemma}\label{lemnonEmptyCases}
	We have $\rrp(n,k,r)=0$ unless $r=1$ or $n=mk$ for some integer $m$.
\end{lemma}
\begin{proof}
	Suppose $2 \leq r \leq k$ and $\pi \in \RRP(n,k,r)$.
	By \eqref{eqmodKwithRemainder}, the number of positions in $\pi$
	where the entry has a remainder $r$ always exceeds the number of entries with a remainder $r-1$,
	unless $n$ is a multiple of $k$. 
	This is due to the fact that the first position has a remainder $r$,
	so that the remainders must form the pattern
	\[
	[r,r+1,r+2,\ldots,0,1,\ldots,r-1,r,\ldots].
	\]	
	Now, the number of entries with index equal to $r$ mod $k$
	is never larger than the number of entries with index equal to $r-1$ mod $k$.
	This is because the entries are from $[n]$.
	Since these two counts must agree for $\pi$, the statement follows.
\end{proof}

\begin{lemma}
	The cardinality of $\RRP(nk,k,r)$ is $(n!)^k$.
\end{lemma}
\begin{proof}
	This is straightforward.
\end{proof}


\begin{lemma}\label{lemmodkAltRevFlip}
	We have $\rrp_{\sigma}(n,k) = \rrp_{\revflip(\sigma)}(n,k)$.
	Moreover,
	\begin{equation}\label{eqrevflipRelation}
		\rrp_{\sigma}(n,k,r) = \rrp_{\revflip(\sigma)}(n,k,2-r).
	\end{equation}
	In particular, $\rrp_{132}(n,k)$ and $\rrp_{213}(n,k)$
	have the same cardinality.
\end{lemma}
\begin{proof}
	Note that it is enough to prove \eqref{eqrevflipRelation},
	and that it suffices to show 
	that 
	\[
	\revflip : \RRP_{\sigma}(n,k,r) \to \RRP_{\revflip(\sigma)}(n,k, 2-r )
	\]
	is a bijection.
	
	For $\pi \in \RRP_{\sigma}(n,k,r)$,
	we have that the last element in $\pi$ has remainder $r-1+n$ mod $k$.
	Hence, the first element of $\revflip(\pi)$ has remainder $n+1-(r-1+n) = 2-r$ mod $k$.
	The remaining properties are now straightforward to verify;
	that is, 
	\[
	\revflip(\pi) \in \RRP_{\revflip(\sigma)}(n,k, 2-r ).
	\]
\end{proof}


\begin{lemma}\label{lemmodkInverse}
	We have $\rrp_{\sigma}(n,k)= \rrp_{\sigma^{-1}}(n,k)$.
\end{lemma}
\begin{proof}
	We have $\pi \in \symS_\sigma(n) \iff \pi^{-1} \in \symS_{\sigma^{-1}}(n)$
	(this is classical; see \cite[Lem.\ 1]{SimionSchmidt1985})
	so $\pi \in \RRP_{\sigma}(n,k)$ holds if and only if $\pi^{-1} \in \RRP_{\sigma^{-1}}(n,k)$.
\end{proof}


\begin{proposition}\label{proponlyIdentityStronger}
	For $k\geq 3$ and $n \geq 1$ we have 
	\begin{equation}\label{eqonlyIdentityStronger}
		\rrp_{312}(n,k,r) =
		\begin{cases}
			1, & \text{ if } r=1;\\
			2^{n/k-1}, & \text{ if } r=2 \text{ and } k \mid n;\\
			0, & \text{ otherwise.}
		\end{cases}
	\end{equation}
	Note that by \cref{lemmodkAltRevFlip}, a corresponding statement holds for the pattern $231$.
\end{proposition}
\begin{proof}
	We shall prove the stronger statement that $\RRP_{312}(n,k,1)$ consists of only the identity permutation.
	
	We proceed by induction over $n$ and assume
	that the statement in \eqref{eqonlyIdentityStronger} is true
	for permutations of length less than $n$; the base cases $n=1$ and $n=2$ 
	are straightforward to verify.
	Note that since $k \geq 3$, $r=0$ and $r=2$ are different cases.
	
	Suppose that $\pi \in \RRP_{312}(n,k,r)$ is of the form
	\begin{equation}\label{eq312form}
		\pi = [\alpha,1,\beta]
	\end{equation}
	for some $n\geq 3$.

\medskip
	
\noindent\textbf{Case $r=1$.} 
	If $\alpha$ is the empty sequence, then $[\beta-1] \in \RRP_{312}(n-1,k,1)$ 
	which must be the identity permutation by induction.
	Hence, we can assume that the length, say $s$, of $\alpha$ is 
	greater than $0$ and we must therefore have $n \geq k+1$.
	
	Since $\pi$ avoids $312$, we have $\max(\alpha)<\min(\beta)$. 
	In particular, $\alpha$ is constructed from 
	\[
	\{2,3,\ldots, s+1\}.
	\]
	So $[\alpha,1]\in \RRP_{312}(s+1,k,1)$. 
	
	On the other hand, $\beta$ consists of numbers in $\{s+2,\ldots,n\}$ 
	and 
	\[
	\beta-(s+1)\in \RRP_{312}(n-(s+1),k,1).
	\]
	Thus, $\beta-(s+1)$ is an identity permutation by the induction hypothesis. 
	However, $[\alpha-1]$ is an element in $\RRP_{312}(s,k,0)$, but this 
	set is empty (by induction hypothesis). Hence, the case $r=1$ is done.

\medskip
	
	\noindent \textbf{Case $r \neq 1$.}
	By \cref{lemnonEmptyCases}, we can assume $k \mid n$ and $\alpha-1\in \RRP_{312}(s,k,r-1)$. 
	But this set is empty unless $r=2$ or $r=3$ and $k \mid s$. 
	The latter is impossible, since the form in \eqref{eq312form} 
	tells us $r+s\equiv 1$ (mod $k$), which implies that $k\nmid s$. 
	For the first case ($r=2$) there is only one possibility for
	$\alpha$, namely $[2,3,\ldots,s+1]$ by induction. 
	
	We also know that $[\beta-s-1] \in \RRP_{312}(n{-}s{-}1,k,2)$.
	Moreover, we also need that $k \mid (n{-}s{-}1)$ and there 
	are (by induction) $2^{(n{-}s{-}1)/k-1}$ options for $\beta$.
	Accounting for all possible values of $n{-}s{-}1$ in $\{0,k,2k,\ldots,n-k\}$,
	we have $1+1+2+4+\dotsb+2^{(n/k-1)-1} = 2^{n/k-1}$ ways to obtain $\pi$. \qedhere
\end{proof}


The following proposition is analogous to \cref{proponlyIdentityStronger}.
\begin{proposition}\label{prop213kgeq3}
	Let $k \geq 1$.
	With $a_k(n)$ defined as in \cref{propgeneralFormula}, we have
	\begin{equation}\label{eq213kgeq3}
		\rrp_{213}(n,k,r) =
		\begin{cases}
			a_k(n), & \text{ if } r=1 \text{ or } k \mid n; \\
			0, & \text{ otherwise.}
		\end{cases}
	\end{equation}
	By \cref{lemmodkAltRevFlip}, a similar statement holds for the pattern $132$.
\end{proposition}
\begin{proof}
	If $k=1$, then $r=1$ and $\rrp_{213}(n,1)$ is the Catalan number. 
	From now on assume that $k\geq 2$.
	
	For the case $r=1$, let us consider $ \pi \in \RRP_{213}(n+1,k)$. 
	It must be of the form
	\[
	\pi = [\alpha_1,\ldots,\alpha_{j},1,\beta_1,\ldots,\beta_{n-j}]
	\]
	where we must have $\alpha_t > \beta_s$ for all relevant $t,s$;
	see \cref{fig213RRPFig}.
	
	\begin{figure}[!ht]
		\centering
		\begin{tikzpicture}[scale=1.1]
			\draw[black,fill=pPink] (5,0) rectangle (6,1);
			\draw[black,fill=pBlue] (6,1) rectangle (9,4);
			\draw[black,fill=pOrange] (0,4) rectangle (5,9);
			
			\draw[black, dashed] (6,0) -- (6,9);
			\draw[black, dashed] (5,0) -- (5,9);
			\draw[black, dashed] (0,4) -- (9,4);
			\draw[black, dashed] (0,1) -- (9,1);
			
			\node at (5.5,0.5) {$1$};
			\node at (7.5,2.5) {$\beta$};
			\node at (2.5,6.5) {$\alpha$};
		\end{tikzpicture}
		\caption{The structure of a $213$-avoiding permutation.}\label{fig213RRPFig}
	\end{figure}
	Since $1$ can only appear at some position $km+1$ for some $m \in \setN$,
	we must have that $k\mid j$. 
	Hence, setting
	\begin{align*}
		\alpha' & \coloneqq [\alpha_1 - (n-j+1),\alpha_2 - (n-j+1), \ldots,\alpha_j - (n-j+1)] \\
		\beta' & \coloneqq [\beta_1-1, \beta_2-1, \ldots,\beta_{n-j}-1]
	\end{align*}
	we have that $\alpha' \in \RRP_{213}(j,k)$ 
	if $k\mid n{+}1$ and $\alpha' \in \RRP_{213}(j,k,r'{\neq} 1)$ otherwise. 
	In both cases, $\alpha'$ exists since $k\mid j$ and followed by inductive argument. 
	In addition, we have 
	\[
	\beta' \in \RRP_{213}(n-j,k).
	\]
	Thus we have a bijective proof of the recursion in \eqref{eqakrecursion}.

	The ``otherwise'' case follows from \cref{lemnonEmptyCases}.
	Hence, only the case $k \mid n$, $r \neq 1$ needs to be proved.
	Note that it suffices to show that $\rrp_{213}(km,k,r) = a_k(km)$.
	
	It is straightforward to verify that \eqref{eq213kgeq3} holds whenever $n \leq 2$.
	Now suppose $\pi$ is in $\RRP_{213}(n,k,r)$ for some $r \in \{2,3,\ldots,k\}$ and $n \geq 3$ with $n=km$.
	Then $\pi$ is of the form
	\[
	[\alpha_1, 1, \alpha_{2}]
	\]
	where $\min(\alpha_1)>\max(\alpha_2)$ as seen in \cref{fig213RRPFig}.
	Let $\alpha_1$ have length $s$, so that $\alpha_2$ has length $n-1-s$.
	Note that we must have $k \mid s+r-1$ in order for the first entry in $\alpha_1$
	to have remainder $r$ mod $k$.
	We then have 
	\[
	(\alpha_2-1) \in \RRP_{213}(n-1-s,k,1) \text{ and }
	(\alpha_1-(n-s)) \in \RRP_{213}(s,k,1).
	\]
	Conversely, given permutations $\tau_1 \in \RRP_{213}(s,k,1)$
	and $\tau_2\in \RRP_{213}(n-1-s,k,1)$ for some $s$ satisfying $k \mid s+r-1$,
	we can construct a unique $\pi \in \RRP_{213}(n,k,r)$ by reversing
	the process above. 
	Hence, when $k\mid n$ we have 
	\begin{equation*}
		\rrp_{213}(n,k,r) = 
		\sum_{\substack{s=1 \\ k \mid s+r-1}}^{n-1} \rrp_{213}(s,k,1) \cdot \rrp_{213}(n-s-1,k,1).
	\end{equation*}
	Now, setting $n=km$, $s=kj+r'$ (note that $s$ can be expressed in this way for the fixed $r' = k-r+1$),
	and using that $a_k(i) = \rrp_{213}(i,k,1)$, we get
	\begin{equation*}
		\rrp_{213}(km,k,r) = \sum_{j=0}^{m-1} a_k(kj+r') \cdot a_k(km-(kj+r')-1).
	\end{equation*}
	By \eqref{eqanotherrecur} in \cref{lemanotherrecur} we may now 
	conclude that $\rrp_{213}(km,k,r) = a_k(km)$.\qedhere
	
\end{proof}

We can now give two new combinatorial interpretations of the
Fuss--Catalan numbers.
\begin{corollary}\label{cormainFussCatalan}
	Let $\sigma \in \{132,213\}$ and $n,k \geq 1$.
	Let $m$ and $j$ be defined via $n=km+j$ with $0 \leq j < k$.
	Then
	\[
	\rrp_\sigma(n,k) =  \frac{j+1}{km+j+1} \binom{ (k+1)m + j }{km+j}
	\]
	and in particular
	\[
	\rrp_\sigma(km,k) = \frac{1}{(k+1)m+1} \binom{(k+1)m+1}{m}
	= \frac{1}{km+1} \binom{(k+1)m}{m}.
	\]
\end{corollary}
\begin{proof}
This follows from \cref{propgeneralFormula} and \cref{corakGivesFussCat}.
\end{proof}


\subsection{PAPs avoiding one of 132, 213, 231, and 312}

The case $k=2$ is rather different from $k \geq 3$
as indicated by \cref{proponlyIdentityStronger}.
In this subsection, we treat the $k=2$ case for
the patterns in $\{132,213,231,312\}$.

\begin{lemma}\label{lem132Structure}
	Let $\pi \in \PAP_{132}(n)$ with $n \geq 2$.
	Then either $n$ appears after $n-1$ in $\pi$
	or $n$ is odd and appears at position $1$.
\end{lemma}
\begin{proof}
	The case $n=2$ is easy so suppose $n \geq 3$ and $\pi(1)\neq n$.
	Then the numbers to the left of $n$ must be greater than the
	numbers from the right of $n$ in $\pi$
	(since we must avoid the pattern $132$; see \cref{fig132Avoiding}).
	In particular, $n-1$ must appear before $n$ and we are done.
\end{proof}


\begin{proposition}\label{prop132-231}
	For $m\geq 0$, set
	\begin{align*}
		a_m \coloneqq \pap_{132}(2m), \quad b_m \coloneqq \pap_{132}(2m+1), \\
		a'_m \coloneqq \pap_{231}(2m), \quad b'_m \coloneqq \pap_{231}(2m+1).
	\end{align*}
	We then have $a_m = a'_m$ and $b_m = b'_m$ for all $m$.
\end{proposition}
\begin{proof}
We already know that $b_m=b'_m$ since $\rev: \PAP_{132}(2m+1)\to \PAP_{231}(2m+1)$
is a bijection.

\textbf{Claim:}
	We have
	\begin{equation}
		a_{m} = \sum_{\substack{i+j+k=m-1 \\ i,j,k \geq 0}} a_i a'_j a_k, \text{ and }
		a'_{m} = \sum_{\substack{i+j+k=m-1 \\ i,j,k \geq 0}} a'_i a_j a'_k.
		\label{eq132RecursionMod}
	\end{equation}
	First set $n\coloneqq 2m$ and suppose $\pi \in \PAP_{132}(2m)$.
	By \cref{lem132Structure}, we know that it must be of the form
	\[
	[\underbrace{\alpha_1, \alpha_2, \ldots, \alpha_{2i}}_\alpha, \; n-1, \;
	\underbrace{\beta_{1},\ldots, \beta_{2j}}_\beta, \; n, \;
	\underbrace{\gamma_{1},\ldots,\gamma_{2k}}_\gamma].
	\]
	Moreover, since the permutation is $132$-avoiding (see \cref{fig132Avoiding}), it must be of the form
	\begin{figure}[!ht]
		\centering
		\begin{tikzpicture}[scale=1.6]
			\draw[black,fill=pOrange] (7,0) rectangle (11,4);
			\draw[black,fill=pBlue] (4,4) rectangle (6,6);
			\draw[black,fill=pAlgae] (0,6) rectangle (3,9);
			\draw[black,fill=pSkin] (3,9) rectangle (4,10);
			\draw[black,fill=pPink] (6,10) rectangle (7,11);
			
			\draw[black, dashed] (3,0) -- (3,11);
			\draw[black, dashed] (4,0) -- (4,11);
			\draw[black, dashed] (6,0) -- (6,11);
			\draw[black, dashed] (7,0) -- (7,11);
			
			\draw[black, dashed] (0,4) -- (11,4);
			\draw[black, dashed] (0,6) -- (11,6);
			\draw[black, dashed] (0,9) -- (11,9);
			\draw[black, dashed] (0,10) -- (11,10);
			\node at (6.5,10.5) {$n$};
			\node at (3.5,9.5) {$\scriptstyle{n-1}$};
			\node at (9,2) {$\gamma$};
			\node at (5,5) {$\beta$};
			\node at (1.5,7.5) {$\alpha$};
		\end{tikzpicture}
	\caption{The structure of a $132$-avoiding PAP with even length.}\label{eq132RecursionFig}
\end{figure}

	Now, the permutation matrices $\alpha$ and $\gamma$ can be interpreted
	as smaller permutations in some $\PAP_{132}(2i)$ and $\PAP_{132}(2k)$, respectively.
	Moreover, the permutation $\beta$ can be seen as an element in $\PAP^*_{132}(2j)$.
	By the reversal bijection, we have that $\beta$ corresponds to
	some element in $\PAP_{231}(2j)$ whose cardinality is $a'_j$.
	Hence, we can conclude the first formula in \eqref{eq132RecursionMod}.
	
	Using a similar argument (just reverse everything)
	we can show the second recursive identity.
	An inductive argument over $m$ now allows us to
	conclude that $a_m = a'_m$ for all $m \geq 0$.
\end{proof}

\begin{corollary}
	For any $\sigma \in \{132,213,231,312\}$, we have 
	\begin{equation*}
		\pap_{\sigma}(2m) = \frac{1}{2m+1}\binom{3m}{m}\quad\text{and}\quad
		\pap_{\sigma}(2m+1) = \frac{1}{2m+1}\binom{3m+1}{m+1}.
	\end{equation*}
\end{corollary}
\begin{proof}
	The formulas follow from \cref{cormainFussCatalan} for $\sigma=132$. 
	By \cref{prop132-231}, the statement holds
	for the pattern $231$. 
	By applying the $\revflip$ map we obtain the same 
	counts for the other two patterns.
\end{proof}


\section{Mod-\texorpdfstring{$k$}{k}-alternating subexcedant functions}\label{secsubex}

Subexcedant functions and their close connection with permutations
was initially studied in \cite{MantaciRakotondrajao2001}. 
We refer to \cite{AlexanderssonGetachew2021x} and \cite{BeyeneMantaci2021x}
as examples of applications of these objects.

\begin{definition}\label{subex}
	A \textit{subexcedant function} $f$ on $[n]$ is a map $f : [n] \longrightarrow [n]$
	such that
	\begin{equation*}
		1\leq f(i)\leq i \text{ for all } 1\leq i\leq n.
	\end{equation*}
	We denote the set of all
	subexcedant functions on $[n]$ by $\SEF_n$.
\end{definition}
One can easily see that $\mathcal{F}_n$ has cardinality $n!$. 
The bijection $\sefToPerm: \SEF_n \longrightarrow \symS_n$ is defined as a product 
\begin{equation}\label{eqsefToPerm}
	\sefToPerm(f) \coloneqq (n\,\,f(n))  \cdots (2\,\,f(2)) (1\,\,f(1))
\end{equation}
of cycles of maximum length 2. 
This bijection is the one described in \cite{MantaciRakotondrajao2001}.

The inverse map is defined as follows:
\begin{equation}\label{eqpermToSefRecursion}
	\sefToPerm^{-1}(\sigma)_j \coloneqq
	\begin{cases}
		\sigma(n), & \text{ if } j=n; \\
		\sefToPerm^{-1}( \; (n\,\,\sigma(n) ) \circ\sigma \;  )_j, & \text{ otherwise}
	\end{cases}
\end{equation}
where $\sigma \in \symS_n$ and $j \in [n]$.


\begin{proposition}\label{propsefRRPs}
	Suppose $\pi \in \symS_n$ and $f_\pi$ is the corresponding element in $\SEF_n$.
	Then $\pi$ is in $\RRP(n,k)$ if and only if $f_\pi(i) \equiv i$ (mod $k$).
\end{proposition}
\begin{proof}
	First, suppose that $f_\pi(i) \equiv i$ (mod $k$) for some $\pi\in\symS_n$.
	In the product \eqref{eqsefToPerm}, we see that $f_\pi$ has $k$ disjoint cycle products, then
	the first product contains integers that are congruent to $1$ (mod $k$), the second product contains
	integers that are congruent to $2$ (mod $k$), and so on, with the 
	last product containing integers that are congruent to $k$ (mod $k$).
	Hence $\pi \in \RRP(n,k)$.
	
	On the other hand, suppose now that $\pi \in \RRP(n,k)$ and consider $f_\pi = \sefToPerm^{-1}(\pi)$.
	In the recursion in \eqref{eqpermToSefRecursion},
	we always interchange integers at positions $i$ and $j$, where 
	\[
		j\equiv i \;(\text{mod } k).
	\]
	So (via an inductive argument) we must have 
	that $f_\pi(i) \equiv i$ (mod $k$) for all $i$.
\end{proof}

\begin{example}
	The subexcedant function $12341634$ corresponds to the permutation
	\[
	 [5,2,7,8,1,6,3,4]
	 \]
	 in $\RRP(8,4)$.
\end{example}
\begin{definition}
	A word $w = (w_1,\ldots,w_n) \in \setN^n$ is a \textit{Catalan word} if
	\[
	w_1 =1 \text{ and } 1\leq w_i \leq w_{i-1}+1 \text{ whenever $2 \leq i\leq n$}.
	\]
	A permutation $\pi$ in $\PAP(n)$ is called a \textit{Catalan PAP} if $f_\pi$ is a Catalan word.
	Let $\PAP_C(n)$ be the set of Catalan PAPs and let $\pap_C(n)$ be its cardinality.
	We define $\RRP_C(n,k)$ in the same manner and set $\rrp_C(n,k)\coloneqq |\RRP_C(n,k)|$.
\end{definition}
There are $\frac{1}{n+1}\binom{2n}{n}$ Catalan words of length $n$
and we shall see below that Catalan words are 
essentially the same as the well-known \textit{area sequences}.

\begin{definition}
	A sequence $(a_1,\ldots,a_n)$ is an \textit{area sequence} if
	\[
	a_1 =0 \text{ and } 0\leq a_i \leq a_{i-1}+1 \text{ whenever $2 \leq i\leq n$}.
	\]
\end{definition}
Area sequences are in bijection with Catalan words. The array $(a_1,\ldots,a_n)$
is an area sequence if and only if $(a_1+1,a_2+1,\ldots,a_n+1)$
is a Catalan word. The notion of area sequences plays an 
important role in \textit{diagonal harmonics}; see \cite{qtCatalanBook}.

There is a well-known bijection between Dyck paths and area sequences.
We illustrate this bijection in the following example.
\begin{example}\label{exdyckPath}
	The Dyck path $P=\texttt{nnennneneeneee}$ has the area sequence 
	
	$\avec = (0,1,1,2,3,3,2)$.
	\[
		P=
		\begin{tikzpicture}
			\begin{scope}
				\fill[lightgray](0,1)--(0,2)--(1,2)--(1,5)--(2,5)--(2,6)--(4,6)--(4,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--cycle;
				\draw[step=1em,gray](0,0) grid (7,7);
				\draw[thickLine](0,0)--(0,2)--(1,2)--(1,5)--(2,5)--(2,6)--(4,6)--(4,7)--(7,7);
				
				
				\draw
				(0,0)node[mydot]{}
				(7,7)node[mydot]{};
				\draw
				(1,1)node[entries]{$1$}
				(2,2)node[entries]{$2$}
				(3,3)node[entries]{$3$}
				(4,4)node[entries]{$4$}
				(5,5)node[entries]{$5$}
				(6,6)node[entries]{$6$}
				(7,7)node[entries]{$7$};
			\end{scope}
		\end{tikzpicture}
	\]
	The number of shaded boxes in row $i$ (from the bottom) is given by $a_i$
	and this provides the bijection between area sequences and Dyck paths.
\end{example}

We denote the set of all Dyck paths of size $n$ such that the number of
boxes in each row above the path is a multiple of $k$ by $L^k_{n}$;
see \cref{exspecialDyckPaths}.

\begin{corollary}
	The set $\RRP_C(n,k)$ has the same cardinality as $L^k_{n}$.
\end{corollary}
\begin{proof}
	Let $\pi\in \RRP_C(n,k)$. 
	By \cref{propsefRRPs}, the corresponding subexcedant function
	$f_\pi=w_1w_2\cdots w_n$ is a Catalan word with 
	the property $i-w_i=\alpha_i k$ for all $i\in [n]$, where  $\alpha_i\in \setN$. 
	Hence, $\avec = (w_1-1,w_2-1,\ldots,w_n-1)$ is an 
	area sequence for some Dyck path.
	Now, the number of boxes in the $i^\thsup$ row above the Dyck path is given by
	\begin{equation*}
		(i-1) - (w_i-1)=\alpha_i k,
	\end{equation*}
	since the $i^\thsup$ row has $i-1$ boxes 
	above the diagonal in the $n\times n$ grid.
\end{proof}

\begin{example}\label{exspecialDyckPaths}
	Here are the 9 Dyck paths corresponding to the entries in $\RRP_C(7,3)$.
	\[
	\begin{tikzpicture}[scale=0.9]
		\fill[lightgray](0,0)--(0,1)--(0,2)--(0,3)--(1,3)--(2,3)--(3,3)--(3,4)--(3,5)--(3,6)--(4,6)--(5,6)--(6,6)--(6,7)--(7,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--(0,1);
		\draw[step=1em,gray](0,0) grid (7,7);
		\draw[thickLine](0,0)--(0,1)--(0,2)--(0,3)--(1,3)--(2,3)--(3,3)--(3,4)--(3,5)--(3,6)--(4,6)--(5,6)--(6,6)--(6,7)--(7,7);
		\draw (0,0)node[mydot]{}
		(7,7)node[mydot]{};
		\draw
		(1,1) node[entries]{$1$}
		(2,2) node[entries]{$2$}
		(3,3) node[entries]{$3$}
		(4,4) node[entries]{$4$}
		(5,5) node[entries]{$5$}
		(6,6) node[entries]{$6$}
		(7,7) node[entries]{$7$}
		;
	\end{tikzpicture}
	\begin{tikzpicture}[scale=0.9]
		\fill[lightgray](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(1,4)--(2,4)--(3,4)--(3,5)--(3,6)--(4,6)--(5,6)--(6,6)--(6,7)--(7,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--(0,1);
		\draw[step=1em,gray](0,0) grid (7,7);
		\draw[thickLine](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(1,4)--(2,4)--(3,4)--(3,5)--(3,6)--(4,6)--(5,6)--(6,6)--(6,7)--(7,7);
		\draw (0,0)node[mydot]{}
		(7,7)node[mydot]{};
		\draw
		(1,1) node[entries]{$1$}
		(2,2) node[entries]{$2$}
		(3,3) node[entries]{$3$}
		(4,4) node[entries]{$4$}
		(5,5) node[entries]{$5$}
		(6,6) node[entries]{$6$}
		(7,7) node[entries]{$7$}
		;
	\end{tikzpicture}
	\begin{tikzpicture}[scale=0.9]
		\fill[lightgray](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(1,5)--(2,5)--(3,5)--(3,6)--(4,6)--(5,6)--(6,6)--(6,7)--(7,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--(0,1);
		\draw[step=1em,gray](0,0) grid (7,7);
		\draw[thickLine](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(1,5)--(2,5)--(3,5)--(3,6)--(4,6)--(5,6)--(6,6)--(6,7)--(7,7);
		\draw (0,0)node[mydot]{}
		(7,7)node[mydot]{};
		\draw
		(1,1) node[entries]{$1$}
		(2,2) node[entries]{$2$}
		(3,3) node[entries]{$3$}
		(4,4) node[entries]{$4$}
		(5,5) node[entries]{$5$}
		(6,6) node[entries]{$6$}
		(7,7) node[entries]{$7$}
		;
	\end{tikzpicture}
	\begin{tikzpicture}[scale=0.9]
		\fill[lightgray](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(0,6)--(1,6)--(2,6)--(3,6)--(4,6)--(5,6)--(6,6)--(6,7)--(7,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--(0,1);
		\draw[step=1em,gray](0,0) grid (7,7);
		\draw[thickLine](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(0,6)--(1,6)--(2,6)--(3,6)--(4,6)--(5,6)--(6,6)--(6,7)--(7,7);
		\draw (0,0)node[mydot]{}
		(7,7)node[mydot]{};
		\draw
		(1,1) node[entries]{$1$}
		(2,2) node[entries]{$2$}
		(3,3) node[entries]{$3$}
		(4,4) node[entries]{$4$}
		(5,5) node[entries]{$5$}
		(6,6) node[entries]{$6$}
		(7,7) node[entries]{$7$}
		;
	\end{tikzpicture}
	\begin{tikzpicture}[scale=0.9]
		\fill[lightgray](0,0)--(0,1)--(0,2)--(0,3)--(1,3)--(2,3)--(3,3)--(3,4)--(3,5)--(3,6)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--(0,1);
		\draw[step=1em,gray](0,0) grid (7,7);
		\draw[thickLine](0,0)--(0,1)--(0,2)--(0,3)--(1,3)--(2,3)--(3,3)--(3,4)--(3,5)--(3,6)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7);
		\draw (0,0)node[mydot]{}
		(7,7)node[mydot]{};
		\draw
		(1,1) node[entries]{$1$}
		(2,2) node[entries]{$2$}
		(3,3) node[entries]{$3$}
		(4,4) node[entries]{$4$}
		(5,5) node[entries]{$5$}
		(6,6) node[entries]{$6$}
		(7,7) node[entries]{$7$}
		;
	\end{tikzpicture}
	\]
	\[
	\begin{tikzpicture}[scale=0.9]
		\fill[lightgray](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(1,4)--(2,4)--(3,4)--(3,5)--(3,6)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--(0,1);
		\draw[step=1em,gray](0,0) grid (7,7);
		\draw[thickLine](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(1,4)--(2,4)--(3,4)--(3,5)--(3,6)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7);
		\draw (0,0)node[mydot]{}
		(7,7)node[mydot]{};
		\draw
		(1,1) node[entries]{$1$}
		(2,2) node[entries]{$2$}
		(3,3) node[entries]{$3$}
		(4,4) node[entries]{$4$}
		(5,5) node[entries]{$5$}
		(6,6) node[entries]{$6$}
		(7,7) node[entries]{$7$}
		;
	\end{tikzpicture}
	\begin{tikzpicture}[scale=0.9]
		\fill[lightgray](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(1,5)--(2,5)--(3,5)--(3,6)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--(0,1);
		\draw[step=1em,gray](0,0) grid (7,7);
		\draw[thickLine](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(1,5)--(2,5)--(3,5)--(3,6)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7);
		\draw (0,0)node[mydot]{}
		(7,7)node[mydot]{};
		\draw
		(1,1) node[entries]{$1$}
		(2,2) node[entries]{$2$}
		(3,3) node[entries]{$3$}
		(4,4) node[entries]{$4$}
		(5,5) node[entries]{$5$}
		(6,6) node[entries]{$6$}
		(7,7) node[entries]{$7$}
		;
	\end{tikzpicture}
	\begin{tikzpicture}[scale=0.9]
		\fill[lightgray](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(0,6)--(1,6)--(2,6)--(3,6)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--(0,1);
		\draw[step=1em,gray](0,0) grid (7,7);
		\draw[thickLine](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(0,6)--(1,6)--(2,6)--(3,6)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7);
		\draw (0,0)node[mydot]{}
		(7,7)node[mydot]{};
		\draw
		(1,1) node[entries]{$1$}
		(2,2) node[entries]{$2$}
		(3,3) node[entries]{$3$}
		(4,4) node[entries]{$4$}
		(5,5) node[entries]{$5$}
		(6,6) node[entries]{$6$}
		(7,7) node[entries]{$7$}
		;
	\end{tikzpicture}
	\begin{tikzpicture}[scale=0.9]
		\fill[lightgray](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(0,6)--(0,7)--(1,7)--(2,7)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7)--(6,7)--(6,6)--(5,6)--(5,5)--(4,5)--(4,4)--(3,4)--(3,3)--(2,3)--(2,2)--(1,2)--(1,1)--(0,1);
		\draw[step=1em,gray](0,0) grid (7,7);
		\draw[thickLine](0,0)--(0,1)--(0,2)--(0,3)--(0,4)--(0,5)--(0,6)--(0,7)--(1,7)--(2,7)--(3,7)--(4,7)--(5,7)--(6,7)--(7,7);
		\draw (0,0)node[mydot]{}
		(7,7)node[mydot]{};
		\draw
		(1,1) node[entries]{$1$}
		(2,2) node[entries]{$2$}
		(3,3) node[entries]{$3$}
		(4,4) node[entries]{$4$}
		(5,5) node[entries]{$5$}
		(6,6) node[entries]{$6$}
		(7,7) node[entries]{$7$}
		;
	\end{tikzpicture}
	\]
\end{example}

\begin{theorem}
	Let $r_{k}(n) \coloneqq \rrp_C(n,k)$. Then
	\begin{equation*}
		r_{k}(n+1) = \sum_{\substack{0\leq j \leq n \\ k \mid j}} r_{k}(j) r_{k}(n-j),\qquad r_k(0)\coloneqq 1.
	\end{equation*}
\end{theorem}
\begin{proof}
	Let $\pi$ be in $\RRP_C(n+1,k)$. Consider the last 1 in $f_\pi$. Then we have
	\begin{align*}
		f_\pi=\gamma_j,1,\gamma_{n-j},
	\end{align*}
	where $\gamma_j$ is the subword having length $j$. 
	Clearly, $j$ is a multiple of $k$ and $0\leq j\leq n$. 
	Finally $\gamma_j\in\RRP_C(j,k)$ and $\gamma_{n-j}{-}1\in\RRP_C(n-j,k)$, 
	since $\gamma_{n-j}$ starts with 2.
\end{proof}

In the same manner as the proof of \cref{cormainFussCatalan}, 
we have the following corollary.
\begin{corollary}\label{corsubexFuss}
	Let $m$ and $j$ be defined via $n=km+j$ with $0 \leq j < k$.
	Then
	\[
	\rrp_C(n,k) =  \frac{j+1}{km+j+1} \binom{ (k+1)m + j }{km+j}
	\]
	and in particular,
	\[
	\rrp_C(km,k) = \frac{1}{(k+1)m+1} \binom{(k+1)m+1}{m}
	= \frac{1}{km+1} \binom{(k+1)m}{m}.
	\]
\end{corollary}

The fact that our Dyck paths are counted by Raney numbers is not new;
this is a classical interpretation of Raney numbers. 
We decided to include this interpretation mainly for context and to illustrate the 
surprising fact that a Catalan family with mod-$k$-restrictions again gives 
Raney numbers, just as for mod-$k$-alternating permutations and pattern-avoidance.


\section{Mod-\texorpdfstring{$k$}{k}-alternating permutations avoiding two patterns}\label{sec2patterns}

The systematic study of permutations avoiding two patterns of length $3$
was completed by Simion and Schmidt \cite{SimionSchmidt1985}.
In this section, we do the same for parity-alternating permutations 
and mod-$k$-alternating permutations.

Due to \cref{proponlyIdentityStronger},
the situation for $k \geq 3$ is, in general, simpler than the $k=2$ case.
In \cref{tab2patterns}, we present an overview of our results in 
the $k=2$ case. We consider the sequence
$(\pap_{\sigma,\tau}(n))_{n\geq 1}$ and separate it into the cases $n=2m$ and $n=2m+1$.
Closed-form formulas for the 
sequences $(\pap_{\sigma,\tau}(2m))_{m\geq 1}$ and $(\pap_{\sigma,\tau}(2m+1))_{m\geq 0}$,
where 
\[
\sigma,\tau \in \{123,132,213,231,312,321\},
\]
are shown in the table.

The bold letters refer to cases that are treated below.
Note that \cref{lemmodkAltRevFlip,lemmodkInverse} can easily be generalized 
to sets of permutations avoiding two or more patterns. 
For example, $\pap_{\sigma,\tau}(n,k) = \pap_{\revflip(\sigma),\revflip(\tau)}(n,k)$.
Cases marked with the same letter indicate situations that 
give the same enumeration after applying these lemmas.
We emphasize that the formulas are only valid for permutations of length at least $1$.
\begin{table}[!ht]
	\centering
	\begin{tabular}{l|llllll}
		& \textbf{123} & \textbf{132} & \textbf{213} & \textbf{231} & \textbf{312} & \textbf{321}\\
		\hline
		\textbf{123} &* &   &  & \\
		\textbf{132} & \textbf{A}; $2^{m-1}$, 1 & *  &  & \\
		\textbf{213} & \textbf{A}; $2^{m-1}$, 1 &  \textbf{D}; $2^{m-1}$, $F_{2m+1}$ & * & \\
		\textbf{231} & \textbf{B}; $m$, $\binom{m}{2}{+}1$ &  \textbf{E}; $2^{m-1}$, $2^{m}$ & \textbf{E}; $2^{m-1}$, $2^{m}$ & *  &\\
		\textbf{312} & \textbf{B}; $m$, $\binom{m}{2}{+}1$ &  \textbf{E}; $2^{m-1}$, $2^{m}$ & \textbf{E}; $2^{m-1}$, $2^{m}$ & \textbf{F}; $F_{n}$ & * & \\
		\textbf{321} & \textbf{C}; 0 &   \textbf{G}; $\binom{m}{2}{+}1$ &  \textbf{G};  $\binom{m}{2}{+}1$ & \textbf{I}; 1  & \textbf{I}; 1 & *\\
	\end{tabular}
	\vspace{.5cm}
	\caption{Pair of formulas in an entry represent the cases $n=2m$ and $n=2m+1$, respectively.
		A single formula covers to both cases.
		The Fibonacci numbers are denoted by $F_n$, with $F_1=F_2=1$.}\label{tab2patterns}
\end{table}

\begin{remark}
	There are no permutations of length 5 or more that avoid $123$ and $321$. 
	On the other hand, we only get the identity permutation that avoids $231$ and $321$ 
	due to \cref{proponlyIdentityStronger} or (in the case $k=2$) a simple argument.
\end{remark}
Only the cases A, D, and G are interesting for $k \geq 3$.
Otherwise at least one pattern is covered by \cref{proponlyIdentityStronger}
and then the number of mod-$k$-alternating
permutations over $[n]$ that avoid the two patterns is 1, for all $n$.
The general formula for $\rrp_{\sigma,\tau}(n,k)$ in cases A, D, and G
is given in the corresponding subsection.

\subsection{Case A, (132, 123)}
\begin{lemma}\label{lem123-132general}
	Any permutation in $\symS_{132,123}(n)$ starts with at least $n-1$.
\end{lemma}
\begin{proof}
	Suppose $\pi\in\symS_{132,123}(n)$ and $\pi(1)<n-1$. 
	Then $\pi$ contains either the $123$ pattern $\pi(1)\;n{-1}\;n$
	or the $132$ pattern $\pi(1)\;n\;n{-1}$. 
	Hence, $\pi(1)\geq n-1$.
\end{proof}

\begin{proposition}
	For $n$ odd, the set $\PAP_{132,123}(n)$ consists 
	only of the permutation $[n,n-1,\ldots,1]$.
	When $n=2m$, we have $\pap_{132,123}(2m) = 2^{m-1}$.
\end{proposition}
\begin{proof}
	Suppose $\pi \in \PAP_{132,123}(n)$ for odd $n$. 
	From \cref{lem123-132general}, $\pi$ starts with $n$ and then the 
	rest of the permutation must follow the same rule. 
	Hence, $\pi$ is the unique permutation $[n,n-1,\ldots,1]$.
	
	For the second claim, suppose that
	\[
	\pi = [ \alpha, 2m, \beta ] \in \PAP_{132,123}(2m).
	\]
	Then it is easy to verify that the permutations 
	\begin{equation}\label{eqcaseAperms}
		[2m+1, 2m+2, \alpha, 2m, \beta ] \text{ and }
		[2m+1, 2m,   \alpha, 2m+2, \beta ] 
	\end{equation}
	are elements in $\PAP_{132,123}(2m+2)$.
	
	Now, for any $\pi' \in \PAP_{132,123}(2m+2)$, 
	by \cref{lem123-132general} we have that $2m+1$ is in the very first position. 
	In a similar manner, we must have that $\pi'(2) \in \{ 2m, 2m+2\}$.
	We have now shown that all elements in $\PAP_{132,123}(2m+2)$
	are in one of the forms described in \eqref{eqcaseAperms}.
	By an inductive argument it follows that $\pap_{132,123}(2m) = 2^{m-1}$.
\end{proof}

\begin{proposition}
	Let $k\geq 3$ and write $n = km+l$, where $0 \leq l < k$.
	We then have 
	\[
	\rrp_{132,123}(km+l,k)=
	\begin{cases}
		1, & \text{ if } (k,l)\in\{(3,1),(3,2),(4,2)\}; \\
		0, & \text{ otherwise.}
	\end{cases}
	\]
\end{proposition}
\begin{proof}
	Suppose $\pi\in \RRP_{132,123}(n,k)$ and consider the position of $1$ in $\pi$. 
	Since $\pi$ avoids both $132$ and $123$, we must have that $1$ 
	is in the last or penultimate position.
	Consequently, $l \in \{1,2\}$ 
	and we shall treat these two cases separately.

	\medskip
		
	\noindent \textbf{Case $l=1$.}
	Since $k \geq 3$, we see that $2$ must appear to the left of $1$ with at least one entry in between.
	Moreover, since $\pi$ must avoid both $132$ and $123$, there cannot be 
	more than one entry between $2$ and $1$, which implies that $k=3$.
	The same reasoning as above shows that $3$ must be placed between $2$ and $1$,
	so $\pi$ ends with $231$.
	We may now treat the first $n-3$ entries in $\pi$ as an element in $\RRP_{132,123}(n-3,k)$.
	By induction, we can then conclude that $\pi$ is the unique permutation
	\[
	\pi=[3m{+}1, \,\,\, 3m{-}1,3m,3m{-}2, \,\, \ldots, \,\,8,9,7, \,\, 5,6,4, \,\,2,3,1],
	\]
	where the largest entry is first and the remaining entries appear in blocks of $3$.

	\medskip\noindent
	\textbf{Case $l=2$.} It is straightforward to show that 
	we must have $2$ at the last position of $\pi$ in order 
	to avoid the two patterns.
	Now, a similar argument as above shows that 
	\[
	\pi = [ \ldots, 3,1,2] \text{ or } \pi = [ \ldots, 3,j,1,2]
	\]
	where $4 \leq j \leq n$. The first option gives $k=3$
	while the second option forces $k=4$ and $j=4$.
	
	In case $k=3$, we have that $\pi$ ends with $3,1,2$
	and an inductive argument then gives
	\[
	\pi = [3m{+}1, 3m{+}2, \,\,\, 3m,3m{-}2,3m{-}1, \,\, \ldots, \,\,  9,7,8, \,\,  6,4,5, \,\,3,1,2].
	\]
	Similarly, the case $k=4$ gives 
	\[
	\pi = [4m{+}1, 4m{+}2, \,\,\, 4m{-}1,4m,4m{-}3,4m{-}2, \,\, \ldots, \,\,  7,8,5,6, \,\,3,4,1,2].
	\]
\end{proof}



\subsection{Case B, (231, 123)}

For $n$ odd, we have $\pap_{321,132}(n)=\pap_{231,123}(n)$
because the reversal map (\cref{lemrevBij}) gives a bijection between the sets.
The latter set is enumerated further down in Case G.

The case of even $n$ is covered by the following lemma.
\begin{lemma}
	Suppose $\pi \in \PAP_{231,123}(2m)$.
	Then
	\[
	\pi = [k, k-1, k-2,\ldots,1,2m,2m-1,\ldots,k+1]
	\]
	for some odd $k$. 
	Consequently, $\pap_{231,123}(2m) = m$.
\end{lemma}
\begin{proof}
	Because $\pi$ is $231$-avoiding, all entries to the right of $2m$ must be larger than
	all entries to its left. Moreover, it is then straightforward to show that
	both these intervals must be decreasing in order for $\pi$ to avoid the pattern $123$.
	There are exactly $m$ choices of the first entry in $\pi$---any odd number in $[2m]$.
	The lemma follows from these observations.
\end{proof}


\subsection{Case D, (213, 132)}

\begin{proposition}
	For $k \geq 1$ and $0 \leq l <k$, we have 
	\[
	\rrp_{213,132}(km+l,k) =
	\begin{cases}
		2^{m-1}, & \text{ if } l=0; \\
		F_{2m+1}, & \text{ otherwise.}
	\end{cases}
	\]
\end{proposition}
\begin{proof}
	For $k=1$, this reduces to proving that $\symS_{213,132}(m)=2^{m-1}$.
	This has been done already by Simion and Schmidt \cite{SimionSchmidt1985}. 
	We treat the case $k\geq 2$ in the remaining part of the proof.

	\medskip\noindent
	\textbf{Case $l \geq 1$}. 
	From the recursive formula $F_{2m+1}=F_{2m}+F_{2m-1}$ of the Fibonacci numbers,
	we can easily deduce the following recursive formula 
	involving only the odd indexed Fibonacci numbers:
	\begin{align}\label{eqoddFibonacci}
		F_{2m+1}=2F_{2(m-1)+1}+F_{2(m-2)+1}+F_{2(m-3)+1}+\dotsb + F_{3}+F_1.
	\end{align}
	Our goal is to show the same recursive structure for elements in $\RRP_{213,132}(km+l,k)$.
	
	Suppose $\pi \in \RRP_{213,132}(km+l,k)$. 
	We claim that $\pi$ can be obtained in one of the following three ways,
	corresponding to the factor $2$ in $2F_{2(m-1)+1}$ 
	and the remaining terms in \eqref{eqoddFibonacci}, respectively.
	\begin{enumerate}
		\item[(1a)] From $\pi' \in \RRP_{213,132}(k(m-1)+l,k)$
		by inserting the consecutive integers
		\[
		k(m{-}1){+}l{+}1,\,\,k(m{-}1){+}l{+}2,\ldots, km{+}l{-}1, \,\,km{+}l
		\]
		(in this order) immediately after the largest entry in $\pi'$.
		
		\item[(1b)] 
		From $\pi' \in \RRP_{213,132}(k(m-1)+l,k)$ by inserting
		the two sequences of consecutive integers
		\[
		k(m{-}1){+}l{+}i,\,\,k(m{-}1){+}l{+}i{+}1,\ldots, km{+}l,
		\]
		and then
		\[
		k(m{-}1){+}l{+}1,\ldots, k(m{-}1){+}l{+}i{-}1,
		\]
		(in this order) for some $1<i\leq k$ such 
		that $k(m{-}1){+}l{+}i\equiv 1$ (mod $k$), in the beginning of $\pi'$.
		In fact, we have $i=k-l+1$.
		
		\item[(2)] From $\pi''\in\RRP_{213,132}(k s +l,k)$ for any $1\leq s< m-1$ by inserting
		the two sequences of consecutive integers
		\[
		k(m{-}1){+}l{+}i,\,\,k(m{-}1){+}l{+}i{+}1,\ldots, km{+}l,
		\]
		and then
		\[
		ks{+}l{+}1,\,\,ks{+}l{+}2,\ldots, k(m{-}1){+}l{+}i{-}1
		\]
		in the beginning of $\pi''$, where $i$ satisfies the same condition as in the previous case.
	\end{enumerate}
	It is straightforward to verify that the three cases 
	are mutually exclusive, and are indeed elements of $\RRP_{213,132}(km+l,k)$.
	We must show that every element in $\RRP_{213,132}(km+l,k)$ 
	belongs to one of these cases.
	
	Consider the largest element, $km+l$, in $\pi$. 
	All elements to its left must appear in increasing order. 
	Moreover, there cannot be any gaps as that 
	would produce a $132$-pattern. 
	There are two cases to consider. 
	The first one is if $km+l$ occurs after $k(m-1)+l$ and there are 
	exactly $k-1$ elements, all are greater than $k(m-1)+l$, between them in increasing order. 
	This implies that $\pi$ belongs to case (1a) above.
	Otherwise, the entries to the left of $km+l$
	form the interval
	\[
	\underbrace{k(m{-}1){+}l{+}i,\,\,k(m{-}1){+}l{+}i{+}1,\ldots, km{+}l-1}_{k-i},km{+}l
	\]
	for a unique $i \in [k]$. 
	The largest entry in $\pi$ (to the right of $km+l$)
	is $k(m{-}1){+}l{+}i-1$, so 
	the entries between $km+l$ and $k(m{-}1){+}l{+}i-1$ must form 
	an increasing sequence of consecutive integers. The first one being 
	of the form $ks+l+1$ for some $s \in [m-1]$.
	This puts $\pi$ in either case (1b) (for $s=m-1$) or case (2).
	
	This shows that we have the recursion 
	\begin{align*}
		\rrp_{213,132}(km+l,k) &= 2 \, \rrp_{213,132}(k(m-1)+l,k)+\rrp_{213,132}(k(m-2)+l,k)\\
		&+\dotsb +\rrp_{213,132}(k+l,k)+\rrp_{213,132}(l,k).
	\end{align*}
	Thus, (after checking initial conditions) we have that
	$(\rrp_{213,132}(km+l,k))_{m=0}^\infty$ satisfies 
	the same recursion as in \eqref{eqoddFibonacci}. 
	Therefore, $\rrp_{213,132}(km+l,k)=F_{2m+1}$.
	
\medskip\noindent	
	\textbf{Case $l=0$}. 
	Suppose that $\pi\in\RRP_{213,132}(k(m+1),k)$. 
	
	By a similar argument as above, $\pi$ either starts with
	\[
	km{+}1,\,\,km{+}2,\ldots, k(m{+}1){-}1,\,\, k(m{+}1)
	\]
	or $km$ is followed by this sequence of integers.
	Thus, we can obtain $\pi$ from $\pi'\in \RRP_{213,132}(km,k)$ by
	inserting
	\[
	km{+}1,\,\,km{+}2,\ldots, k(m{+}1){-}1,\,\, k(m{+}1)
	\]
	either immediately after $km$, or at the beginning of $\pi'$. 
	Hence,
	\begin{align*}
		\rrp_{213,132}(k(m+1),k)=2\,\rrp_{213,132}(km,k).
	\end{align*}
	We also have the initial condition $\rrp_{213,132}(k,k)=1$ (the identity permutation)
	so it follows that $\rrp_{213,132}(km,k)=2^{m-1}$.
\end{proof}

\begin{corollary}
	We have 
	\[
	\pap_{213,132}(2m) =2^{m-1}\qquad \text{ and }\qquad \pap_{213,132}(2m+1)=F_{2m+1}.
	\]
\end{corollary}


\subsection{Case E, (231, 132)}
\begin{proposition}
	We have 
	\[
	\pap_{231,132}(2m)= 2^{m-1}\quad\text{ and }\quad
	\pap_{231,132}(2m+1)=2^m.
	\]
\end{proposition}
\begin{proof}
	If $\pi \in \symS_{231,132}(n)$, it is clear that $n$ must be either in the
	very beginning or at the very end of $\pi$. 
	Thus, $\pi\in\PAP_{231,132}(2m+1)$ is obtained from $\pi'\in \PAP_{231,132}(2m-1)$ 
	by inserting $2m,2m{+}1$ at the end of $\pi'$ or by inserting $2m{+}1,2m$ 
	at the beginning of $\pi'$. 
	Moreover, every $\pi\in\PAP_{231,132}(2m)$ can be obtained from some 
	$\pi'\in \PAP_{231,132}(2m-1)$ by inserting $2m$ at the end of $\pi'$.  
	Hence,
	\[
	\pap_{231,132}(2m+1)=2\, \pap_{231,132}(2m-1)\quad\text{ and }\quad \pap_{231,132}(2m)=\pap_{231,132}(2m-1),
	\]
	where $\pap_{231,132}(1)=1$ and $\pap_{231,132}(2)=1$. 
	The statement then follows by a simple inductive argument.
\end{proof}




\subsection{Case F, (312, 231)}

For $k \geq 3$, the set $\RRP_{312,231}(n,k)$ contains 
only the identity permutation due to \cref{proponlyIdentityStronger}.

For $k=2$, we have the following proposition.
\begin{proposition}
	We have $\pap_{312,231}(n) = F_n$, the $n^\thsup$ Fibonacci number.
\end{proposition}
\begin{proof}
	It is easy to verify that this holds for $n \leq 3$
	so suppose that $\pi\in \PAP_{312,231}(n)$ for some $n \geq 4$.
	
	If $\pi(n)\neq n$, then $n-1$ must appear on the right of 
	$n$; otherwise $n-1,\,\,n,\,\,\pi(n)$ forms a $231$-pattern
	so $n$ is immediately followed by $n-1$ in order to avoid $312$. 
	
	Similarly, $n-2$ cannot be anywhere left of $n$,
	since then $n-2,\,\,n,\,\,\pi(n)$ would form a $231$-pattern.
	
	Now, if there was some element between $n-1$ and $n-2$,
	then there would be a $312$-pattern in $\pi$. 
	Hence, $n,n-1,n-2$ must be a subword of $\pi$.
	
	It follows that any $\pi\in \PAP_{312,231}(n)$ can be constructed either
	from some $\pi' \in \PAP_{312,231}(n-1)$, by appending $n$
	at the very end, or by inserting $n,n-1$ immediately before $n-2$
	in some $\pi'' \in \PAP_{312,231}(n-2)$.
	Thus, we have the classical Fibonacci recursion and the statement follows.
\end{proof}
Observe that for odd $n$ we may apply \cref{lemrevBij}
and then see that $\pap_{312,231}(n) = \pap_{132,213}(n)$,
where the latter is $F_n$ according to Case D.


\subsection{Case G, (321, 132)}


\begin{lemma}\label{lemcons}
	Let $\pi \in \RRP_{321,132}(km+l,k)$, where $0\leq l<k$ and $k \geq 2$. 
	Then for any $j \in [m]$, the entries
	\[
	k(j{-}1){+}1,\,\, k(j{-}1){+}2,\,\, \ldots,\,\, kj{-}1,\,\, kj
	\]
	form a subword of $\pi$. 
	Moreover, the last $l$ numbers in $[km+l]$ 
	must appear in increasing order at the very end of $\pi$.
\end{lemma}
\begin{proof}
	Suppose $k(j-1)+i$ is on the left of $k(j-1)+i-1$ for some $1<i\leq k$. 
	Then $\pi(1), \,k(j{-}1){+}i,\, k(j{-}1){+}i{-}1$ form either a
	$132$- or a $321$-pattern, depending on the
	value of $\pi(1)$ (we know $\pi(1)\neq k(j-1)+i$ since $\pi(1) \equiv 1$ (mod $k$)). 
	Therefore,
	\[
	k(j{-}1){+}1,\,\, k(j{-}1){+}2,\,\, \ldots,\,\, kj{-}1,\,\, kj
	\]
	appear in this order.
	
	Now suppose that $k(j-1)+i-1$ and $k(j-1)+i$ are not adjacent for some $1<i\leq k$.
	Then there are at least $k$ entries between them since $\pi$ 
	is a mod-$k$-alternating permutation. 
	Each such entry must be
	less than $k(j-1)+i-1$, otherwise we have a $132$-pattern.
	Now consider the position of $1$ in $\pi$ and let $t$ be the 
	number succeeding $k(j-1)+i-1$. If $1$ appears to the left of $k(j-1)+i-1$, then
	$1,\ldots,\,\,k(j{-}1){+}i{-}1,\,\,t$ form a $132$-pattern. 
	If $1$ is on the right, it can not be immediately after $k(j-1)+i-1$
	since $i>1$. Thus, $t\neq 1$ and $k(j{-}1){+}i{-}1,\,\,t,\ldots,\,\,1$ form a
	$321$-pattern.
	
	Now, it remains to show the last statement in the lemma.
	For $l=0$, there is nothing more to prove. 
	If $l>0$ we can argue in the same manner as above, that $km+1,km+2,\ldots,km+l$
	must form a subword of $\pi$. Since all other entries are partitioned into
	blocks of length $k$, we must have that the $l$ largest entries
	appear at the very end. Otherwise, the entry immediately after $km+l$
	would have the wrong remainder mod $k$.
\end{proof}

\begin{proposition}
	For any $k \geq 1$, $m \geq 0$, and $0\leq l<k$, we have 
	\[
	\rrp_{321,132}(km+l,k)=\binom{m}{2}+1.
	\]
\end{proposition}
\begin{proof}
	Let $\pi \in \RRP_{321,132}(km+l,k)$. By the second statement in \cref{lemcons},
	we can simply disregard the last $l$ entries and conclude that 
	$\rrp_{321,132}(km+l,k) = \rrp_{321,132}(km,k)$.
	By the first property in \cref{lemcons}, we note that there is a simple bijection
	from $\RRP_{321,132}(km,k)$ to $\symS_{321,132}(m)$.
	We simply keep only the first entry in each block of $k$ letters and standardize the result.
	Thus, $\rrp_{321,132}(km+l,k)=|\symS_{321,132}(m)|$.
	Finally, it has already been shown that $|\symS_{321,132}(m)| = \binom{m}{2}+1$; 
	see \cite[Prop.\ 11]{SimionSchmidt1985}.
\end{proof}

\begin{corollary}
	We have 
	\[
	\pap_{321,132}(2m)=\pap_{321,132}(2m+1)=\binom{m}{2}+1.
	\]
\end{corollary}


\section{Remarks}

The attentive reader has most likely noticed that 
we have said nothing about parity--alternating permutations
avoiding the single pattern 123, or the single pattern 321.

The sequence with the number of 123-avoiding PAPs of size $n$
starts as
\[
1, 1, 1, 3, 3, 10, 11, 37, 44, 146, 185, 603, 808, 2576,\ldots.
\]
Similarly, for $321$-avoiding PAPs, we get 
\[
1, 1, 1, 2, 3, 6, 11, 22, 44, 89, 185, 382, 808, 1702, \ldots.
\]
Recall from \cref{lemrevBij} that the reversal map 
is a bijection between the sets 
$\PAP_{321}(2m+1)$ and $\PAP_{123}(2m+1)$,
so $\pap_{321}(2m+1)=\pap_{123}(2m+1)$ for all $m\geq 0$.

We have not managed to produce recursive formulas 
for these sequences. The numbers above were obtained by 
brute-force enumeration---we construct the odd and even parts separately
and then check if the merged permutation is 123- (or 321)-avoiding.

However, we have managed to find a property of $321$-avoiding PAPs which may 
be exploited to produce a recursive formula. 
This property is proved in \cref{prop321AvoPAPs} but we need a definition first in order to state it.

\begin{definition}
	A \textit{left-to-right maximum} of $\pi\in\symS_n$ is an integer $i\in[n]$ such that $i>j$ 
	for all $j\in[n]$ to the left of $i$ in the one-line notation of $\pi$.
	We call the integers that are not left-to-right maxima \textit{hole values}.
\end{definition}

\begin{proposition}\label{prop321AvoPAPs}
	Let $\pi\in\PAP_{321}(n)$ be non-identity. Then
	\begin{enumerate}
		\item there exists a pair of hole values in $\pi$ that are consecutive and
		\item the highest such pair of numbers either stands in 
		adjacent positions or has an even length sequence of 
		consecutive left-to-right-maxima between the numbers.
	\end{enumerate}
\end{proposition}
\begin{proof}
	Let $i\in[1,n-1]$ be the highest position with no excedance 
	in $\pi\in\PAP_{321}(n)$ till $i$. 
	Then $\pi_j=j$, for all $j=1,2,\ldots, i{-}1$ and $\pi_{i+1}>i{+}1$ 
	since $\pi_i>i$ and $\pi$ is a $321$-avoiding PAP. 
	Thus, $i$ and $i+1$ are hole values, which show the existence.
	
	Now consider the highest such pair of consecutive hole values in $\pi$, 
	say $h$ and $h+1$. The integer $h+1$ is always to the right of $h$. 
	Otherwise, $\pi_h, h{+}1, h$ forms a $321$ pattern. If $h$ and $h+1$ are 
	adjacent, then we are done. 
	Otherwise, there is an even number (at least two) of 
	positions between $h$ and $h+1$ since $\pi$ is a PAP. 
	Moreover, the numbers between $h$ and $h+1$ are left-to-right maxima 
	since $\pi$ is $321$-avoiding. If the numbers in between are consecutive, 
	then we are done. Otherwise, we have a pair of consecutive hole values 
	which are greater than $h$ and $h+1$. 
	This is a contradiction since $h$ and $h+1$ are the highest.
\end{proof}




\section{Acknowledgments}

Thanks to Ran Pan \cite{Ran2015} for proposing the problem about pattern avoidance of 
parity-alternating permutations.

We appreciate the hospitality we get from the
Department of Mathematics, Stockholm University. 
We especially acknowledge the useful discussions 
with J\"orgen Backelin and Joel Persson. The second and 
third authors are grateful for the 
financial support extended by the cooperation 
agreement between the International Science Program (ISP) 
at Uppsala University and Addis Ababa University.
We are also grateful for the financial support provided by the Wennergren foundation. 
Dun Qiu is supported by the National Natural Science Foundation of China (NSFC) grants, 12001037, 12171034, and 12271023.

The On-line Encyclopedia of Integer Sequences (OEIS)
has been a valuable tool in this research project. 

We are thankful for the valuable suggestions from the anonymous referee,
in particular for simplifying the proof of \cref{propgeneralFormula}.


\begin{thebibliography}{99}
	
	\bibitem{AlexanderssonGetachew2021x}
	Per Alexandersson and Frether Getachew
	\newblock An involution on derangements, arxiv preprint arXiv:2105.08455, 2021.
	Available at
	\newblock \url {http://arxiv.org/abs/2105.08455}.
	
	\bibitem{BeyeneMantaci2021x}
	Fufa Beyene and Roberto Mantaci.
	\newblock Flattened partitions and subxceedant functions, arxiv preprint 	arXiv:2101.07081, 2021. Available at
	\newblock \url {http://arxiv.org/abs/2101.07081}.
	
	\bibitem{BrakMahony2019x}
	R. Brak and N. Mahony.
	\newblock Fibonacci, {M}otzkin, {S}chroder, {F}uss-{C}atalan and other
	combinatorial structures: Universal and embedded bijections, arxiv preprint arXiv:1909.09296, 2019. Available at 
	\newblock \url {http://arxiv.org/abs/1909.09296}.

	\bibitem{GrahamKnuthPatashnik1994}
	Ronald Graham, Donald Knuth, and Oren Patashnik.
	\newblock {\em Concrete Mathematics: {A} Foundation for Computer Science}.
	\newblock Addison-Wesley, second edition, 1994.
	
	\bibitem{qtCatalanBook}
	James Haglund.
	\newblock {\em The $q,t$-{C}atalan Numbers and the Space of Diagonal Harmonics
		({U}niversity lecture series)}.
	\newblock {\em Amer.\ Math.\ Soc.}, 2007. Available at
	\newblock \url{https://www.math.upenn.edu/~jhaglund/books/qtcat.pdf}.
	
	\bibitem{KebedeRakotondrajao2021}
	Frether Getachew Kebede and Fanja Rakotondrajao.
	\newblock Parity alternating permutations starting with an odd integer.
	\newblock {\em Enumer. Comb. Appl.} \textbf{1} (2021), 
	 Paper No.\ S2R16.
	\newblock \url{https://doi.org/10.54550/eca2021v1s2r16}.

	\bibitem{Kitaev2011}
	Sergey Kitaev.
	\newblock {\em Patterns in Permutations and Words}.
	\newblock Springer, 2011.
	
	
	\bibitem{Knuth1997ArtOfProgramming}
	Donald E. Knuth.
	\newblock {\em The Art of Computer Programming, Volume 1: Fundamental
		Algorithms}.
	\newblock Addison Wesley Longman Publishing Co., Inc., 	third edition, 1997.
	
	\bibitem{Knuth1998ArtOfProgramming}
	Donald E. Knuth.
	\newblock {\em The Art of Computer Programming, Volume 3: Sorting and
		Searching}.
	\newblock Addison Wesley Longman Publishing Co., Inc., 	second edition, 1998.
	
	
	\bibitem{Lambert1758}
	J. H. Lambert.
	\newblock Observationes vari{\ae} in mathesin puram.
	\newblock {\em Acta Helvetica Physico-Mathematico-Anatomico-Botanico-Medica, Basileae}
	\textbf{3} (1758), 128--168. Available at
	\newblock \url{https://www.biodiversitylibrary.org/bibliography/9661}.
	
	\bibitem{Lambert1770}
	J. H. Lambert.
	\newblock Observations analytiques.
	\newblock {\em Nouveaux M\'emoires de l'Acad\'emie royale des {S}ciences et
		{B}elles-{L}ettres de {B}erlin} (1770), 225--244.
	
	\bibitem{MantaciRakotondrajao2001}
	Roberto Mantaci and Fanja Rakotondrajao.
	\newblock A permutations representation that knows what ``{E}ulerian'' means.
	\newblock {\em {Discrete Math. Theoret.\ Comput.\ Sci.}} \textbf{4} (2001), 101--108. Available at
	\newblock \url{https://dmtcs.episciences.org/271}.
	
	\bibitem{Munagi2014}
	Augustine Munagi.
	\newblock Parity-alternating permutations and successions.
	\newblock {\em Cent.\ Eur.\ J. Math.} \textbf{2} (2014), 1390--1402.
	\newblock \url{https://doi.org/10.2478/s11533-014-0421-2}.
	
	\bibitem{Ran2015}	Ran Pan.
	\newblock Problem 10, Project P, 2015.
	\newblock \url{https://mathweb.ucsd.edu/~projectp/problems/p10.html}.
	
	\bibitem{Raney1960}	George N. Raney.
	\newblock Functional composition patterns and power series reversion.
	\newblock{\em Trans.\ Amer.\ Math.\ Soc.} \textbf{94} (1960), 441--451. \url{https://doi.org/10.1090/s0002-9947-1960-0114765-9}.

	\bibitem{SimionSchmidt1985}
	Rodica Simion and Frank W. Schmidt.
	\newblock Restricted permutations.
	\newblock {\em European J. Combin.} \textbf{6} (1985), 383--406. 

	\bibitem{OEIS}
	Neil J. A. Sloane.
	\newblock The {O}n-{L}ine {E}ncyclopedia of {I}nteger {S}equences, 2019. Available at
	\newblock \url{https://oeis.org}.
	
	
	\bibitem{StanleyCatalan}
	Richard P. Stanley.
	\newblock {\em Catalan Numbers}.
	\newblock { Cambridge University Press}, 2015.
	
	\bibitem{Tanimoto2010}
	Shinji Tanimoto.
	\newblock Combinatorics of the group of parity alternating permutations,
	\newblock {\em Adv.\ Appl.\ Math.} \textbf{44} (2010), 225--230.
	
	\bibitem{Wilf1994}
	Herbert S. Wilf,
	\newblock {\em generatingfunctionology}.
	\newblock {Elsevier}, 1994. Available at
	\newblock \url {https://www2.math.upenn.edu/~wilf/gfologyLinked2.pdf}.
	
\end{thebibliography}

\bigskip 
\hrule 
\bigskip 

\noindent {\it 2020 Mathematics Subject Classification:} Primary 05A05; Secondary 05A15, 05A19.

\noindent \emph{Keywords:} mod-$k$-alternating permutation, Fuss--Catalan number, Raney number.

\bigskip
\hrule
\bigskip

\noindent 
(Concerned with sequences 
\seqnum{A000027},
\seqnum{A000045},
\seqnum{A000079},
\seqnum{A000124},
\seqnum{A047749},
\seqnum{A079508},
\seqnum{A335109},
\seqnum{A354208},
\seqnum{A355089}, and
\seqnum{A355262}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  May 24 2022;
revised versions received  January 23 2023; January 24 2023; February 25 2023;
April 6 2023.
Published in {\it Journal of Integer Sequences}, April 7 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in 
	
\end{document}

                                                                                

