% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.22}{23(4)}{2016}
% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsmath,amsthm, amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Preserving the number of cycles of length $k$\\in a growing
  uniform permutation}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

%\author{
%Philippe Duchon \qquad  Romaric Duvignau\\
%\small LaBRI \\[-0.8ex]
%\small Universit\'e de Bordeaux \\[-0.8ex]
%\small Talence, France\\
%\small\tt \{philippe.duchon,romaric.duvignau\}@labri.fr
%}

\author{Philippe Duchon\\
\small LaBRI \\[-0.8ex]
\small Universit\'e de Bordeaux\\[-0.8ex]
\small Talence, France\\
\small\tt philippe.duchon@labri.fr
\and
Romaric Duvignau\thanks{This work was done while the second author was affiliated with LaBRI, Universit\'e de Bordeaux.}\\
% Aix Marseille Universi CNRS, LIF UMR 7279, 13288, Marseille, France
\small LIF \\[-0.8ex]
\small Aix Marseille Universit\'e \\[-0.8ex]
\small Marseille, France\\
\small\tt romaric.duvignau@lif.univ-mrs.fr
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Mar 17, 2016}{Oct 26, 2016}{Nov 10, 2016}\\
\small Mathematics Subject Classifications: 05A05, 68Q87}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% our own packages
\usepackage[noend]{algpseudocode}
\usepackage{algorithm,dsfont}
\usepackage{color,xfrac,multicol}
\usepackage{tikz,subfig}
\usepackage{enumerate}

% shortcuts
\newcommand{\nat}{\mathbb{N}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\st}{\;|\;}
\newcommand{\pr}{\mathbb{P}}
\newcommand{\esp}{\mathbb{E}}
\newcommand{\ninf}{\lim\limits_{n \rightarrow \infty}}
\newcommand{\mif}{\quad \text{ if } \,}
\newcommand{\mother}{\quad \text{ otherwise} \,}
\newcommand{\mand}{\;\text{ and }\;}

\newcommand{\ins}{\hbox{insert}}
\newcommand{\rem}{\hbox{remove}}
% changed append -> connect
\newcommand{\app}{\hbox{connect}}
\newcommand{\spl}{\hbox{split}}
\newcommand{\cycle}{\hbox{cycle}}
\newcommand{\swap}{\hbox{swap}}
\newcommand{\spec}{\hbox{sc}}
% \newcommand{\shift}{\hbox{shift}}
% \newcommand{\pop}{\hbox{p-operator}}
% \newcommand{\shc}{\hbox{split-and-shift}}
% \newcommand{\hsh}{\hbox{hide-and-shift}}
\DeclareMathOperator\hsh{merge}
\DeclareMathOperator\pop{pop}
\DeclareMathOperator\shift{shift}
\DeclareMathOperator\shc{cut}
%\newcommand{\pop}{\hbox{pop}}
%\newcommand{\hsh}{\hbox{merge}}
%\newcommand{\shift}{\hbox{shift}}
%\newcommand{\shc}{\hbox{cut}}
\newcommand{\lsc}[1]{\lambda(#1)}
%$\lsc{\sigma}$
\newcommand{\len}{\mathcal{L}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  The goal of this work is to describe a uniform generation tree for
  permutations which preserves the number of $k$-cycles between any
  permutation (except for a \textit{small} unavoidable subset of optimal
  size) of the tree and its direct children. Moreover, the tree we 
  describe has the property that if the number of
  $k$-cycles does not change during any $k$ consecutive levels,
  then any further random descent will always yield
  permutations with that same number of $k$-cycles. This specific
  additional property yields interesting applications for exact
  sampling. We describe a new random generation algorithm for
  permutations with a fixed number of $k$-cycles in $n+\mathcal{O}(1)$
  expected calls to a random integer sampler. Another application is a
  combinatorial algorithm for exact sampling from the Poisson
  distribution with parameter $1/k$.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} random permutations; k-cycles in permutations; generation tree; random generation
\end{abstract}

\section{Introduction}

\subsection{Overview of results}

Throughout the paper, $k \geq 1$ is a predefined constant representing some fixed length of cycles in permutations. 

It is a well-known\footnote{see for example,~\cite{diaconis1994eigenvalues}
  and the references therein, or \cite{arratia1992cycle} for total
  variation distance bounds.} fact, that given an infinite vector
$(\sigma_n)_{n \geq 1}$ such that $\sigma_n$ is a permutation of $n$
elements chosen uniformly at random, $c_k(\sigma_n)$, the
number of cycles of length $k$ in $\sigma_n$, converges in
distribution to a random Poisson distributed variable $X_k$ with
expectation $1/k$, \textit{i.e.}, 
$$ \pr(c_k(\sigma_n) = \ell) \rightarrow \frac{e^{-1/k}}{k^\ell l!} \, , \quad\text{ as } n \rightarrow \infty.$$

It is a standard result of probability theory that convergence in
distribution can always be realized as almost sure convergence. In our
setting, this means one can construct a probability distribution $\mu$
on \emph{sequences} of permutations (whose $n$-th element $\sigma_n$
is always uniform among permutations of size $n$) such that, for
$\mu$-almost all sequences, $c_k(\sigma_n)$ converges to a Poisson
random variable with parameter $1/k$. Since we are dealing with
integer valued sequences, convergence is equivalent to the sequence
being ultimately constant. The main contribution of this paper is the
explicit combinatorial description of one such probability distribution.

Since permutations have the very particular property that the number
of permutations of each size is a multiple of the number of
permutations of the preceding size, a particular type of probability
distributions on size-indexed sequences of permutations is given by
so-called \emph{generation trees}: infinite trees with the unique
permutation of size $1$ as the root, where each permutation of size
$n$ has exactly $n+1$ children, each a permutation of size $n+1$, and
such that each permutation of size $n$ appears exactly once among the
nodes of level $n$. The corresponding probability distribution on
sequences corresponds to a \emph{random descent} in the tree, where,
at each step, one of the children is picked uniformly at random,
independently of the previous choices. Because each permutation
appears only once in the tree, the obtained sequences of permutations
are very particular; any permutation in the sequence uniquely
determines all previous permutations. Still, such sequences are
sufficient for our purpose, so that we solely concentrate on the
description of one such generation tree.

Our tree construction also exhibits a property that can be described
in standard probabilistic terminology. Not only do $\mu$-almost all
permutation sequences ultimately stabilize their number of $k$-cycles;
we explicitly describe a subclass of permutations (called non-special
permutations) such that $\mu$-almost all sequences contain such a
permutation, and that all permutations that follow a non-special
permutation (that is, its descendents in the tree) are also
non-special, and have the same number of $k$-cycles. In probabilistic
terms, the stabilization time $T$ for the number of $k$-cycles is not
a stopping time, but is upper bounded by a stopping time $T'$, which
is none other than the index of the first non-special permutation, and
for which we prove that $T\leq T'\leq T+k$ holds a.s.

One direct consequence is that $c_k(\sigma_{T'})$ is exactly Poisson
distributed with parameter $1/k$; this provides a ``purely discrete''
algorithm for sampling from this Poisson distribution by only using
integers and no floating point computations. It also allows for the
sampling from the distribution of the number of $k$-cycles in a
uniform permutation of size $n$, in constant expected time
(independently of $n$).

This paper is an extensive generalization of a previous work by the
authors~\cite{duchon2014new} where a similar construction is given for
the case $k=1$.

\subsection{Outline of the paper}

The paper is organized as follows. In the next section, we give some
notations and briefly discuss generation trees for permutations in
general. In Section~\ref{sec:tree} we describe our generation tree,
define a number of operations and prove their properties. The
proof of the main theorem is in Section~\ref{sec:proof}. In
Section~\ref{probabilistic}, we use the tree to describe new
algorithms for random generation and simulation of random variates.
We finish the paper with a conclusion outlining further possible
applications and directions for future research along the same vein.

\section{Uniform generation trees for permutations}

\subsection{Notations and definitions}

We use the notation $[a,b]$ for the set of integers $i$ such that $a
\leq i \leq b$ and $[n] = [1,n] = \{1, \dots, n\}$ for the set of the
first $n$ positive integers. We shall write $\mathcal{S}_V$ for the
set of all permutations over the set $V$ (bijections from $V$ to
itself). If $\sigma \in S_V$, we set $|\sigma| = |V|$ and call it the
\emph{size} of $\sigma$. The set $\mathcal{S}=\cup_n
\mathcal{S}_{[n]}$ is thus the set of all permutations on initial
segments of positive integers. When $V$ is not specified, the phrase
``permutation of size $n$'' refers to an element of
$\mathcal{S}_{[n]}$.

A \emph{cycle} in a permutation $\sigma \in S_V$ is a minimum nonempty
subset $V$ that is closed under the action of $\sigma$; we slightly
abuse this definition by considering the empty set to be a cycle (of
length $0$).

A cycle $C$ of length $k$, abbreviated as a $k$-cycle, is a cycle such
that $|C| = k$.  We shall denote by $\len_{\sigma}(j)$ the
length of the cycle containing $j$ in the permutation $\sigma$; we
further assume $\len_{\sigma}(j) = 0$ if $j$ is not an element of the
permutation $\sigma$.

A \emph{uniform generation tree} for permutations can be seen as the
description, for each nonnegative integer $n$, of a bijection $\phi_n$
from $\mathcal{S}_{[n]}\times [n+1]$ to $\mathcal{S}_{[n+1]}$. The
countable set $\mathcal{S}$ can thus be seen as the nodes of an
infinite rooted tree, with the unique permutation of size $1$ as the
root, and where each permutation $\sigma\in\mathcal{S}_{[n]}$ has
exactly $n+1$ children, obtained by applying $\phi_n$ to the pairs
$(\sigma,i)$ for $i\in [n+1]$. The $n!$ nodes at distance $n-1$ from the
root are then all permutations of $\mathcal{S}_{[n]}$. Such a
generation tree can also be seen as the description of a procedure for
the random generation of uniform permutations: from a random
permutation of size $n$ and an independent uniform integer in the
range $[n+1]$, $\phi_n$ gives us a uniform random permutation of size
$n+1$. Thus, starting from the root and repeating $n-1$ times the
simple procedure of moving to a uniformly chosen child of the current
node yields a uniform permutation of size $n$. We refer to this
procedure as a \emph{random descent} (possibly infinite) in the tree.

Consistently with the tree terminology, $\phi_n(\sigma,i)$ will be
called the \emph{$i$-th child of $\sigma$}, and $\sigma$ will be
called the \emph{parent} of each of its children. All permutations in
the subtree rooted at $\sigma$ are collectively called the
\emph{descendants} of $\sigma$.

\subsection{Some classical generation trees}
\label{sec:classic_gentree}

Many simple combinatorial descriptions of uniform generation
trees can be given. We briefly describe two of them.

\begin{itemize}
\item Last value insertion: from a permutation $\sigma\in
  \mathcal{S}_{[n-1]}$ and an integer $i\in[n]$, we obtain a new
  permutation $\sigma'\in\mathcal{S}_{[n]}$ as follows: set
  $\sigma'(n)=i$, and for $1\leq j\leq n-1$, $\sigma'(j)=\sigma(j)$ if
  $\sigma(j)<i$, and $\sigma'(j)=1+\sigma(j)$ if $\sigma(j)\geq i$. In
  other words, $i$ gives the value of $\sigma'(n)$, and all previous
  values at least  $i$ are shifted up by $1$.
\item Cycle insertion: this generation scheme is best described by its
  action on the cycles of the permutation. From a permutation
  $\sigma\in\mathcal{S}_{[n-1]}$ and an integer $i\in[n]$, we obtain a new
  permutation $\sigma''\in\mathcal{S}_{[n]}$ as follows: if $i=n$,
  simply set $\sigma''(n)=n$ and, for $1\leq j\leq n-1$,
  $\sigma''(j)=\sigma(j)$; otherwise, set $\sigma''(i)=n$,
  $\sigma''(n)=\sigma(i)$, and $\sigma''(j)=\sigma(j)$ for all other
  values of $j$. In other words, $n$ is inserted ``right after $i$''
  in its pre-existing cycle -- or is added as a new fixed point, if
  $i=n$.
\end{itemize}

Because last value insertion often shifts many values by $1$, it can
dramatically change the number of $k$-cycles -- that is, $c_k(\sigma)$
and $c_k(\phi_n(\sigma,i))$ can be very different. For instance, the
first child of the permutation $(1 2 \dots k)(k+1 \dots 2k)
\dots(n-k+1\dots n)$ formed entirely of $n/k$ cycles of length $k$ has
no $k$-cycles (it is cyclic for odd $k$, and, for even $k$,
it has $n/k$ $(k/2)$-cycles and one $(n/2+1)$-cycle).

On the other hand, the number of $k$-cycles can only change by $\pm 1$
under cycle insertion: it increases by $1$ if the selected element is
in a $(k-1)$-cycle (or if $n$ is added as a new fixed point for $k =
1$), and decreases by $1$ if $j$ was previously in a $k$-cycle. As one
descends in the tree according to the random choices of children, the
probability of changing the number of $k$-cycles becomes arbitrarily
small: it is exactly $2/n$ on the $n$-th step, as on average there is
$1$ element belonging to each cycle length.  One can easily prove,
though, that in an infinite random descent into the tree, this change
in the number of $k$-cycles will almost surely happen
infinitely often. The property holds for $k=1$: the last child of any
permutation always has one more fixed point; since the series $\sum_n
1/n$ is divergent, the second Borel-Cantelli lemma implies that almost
all infinite descents pass through infinitely many last children. The
property for general $k$ follows by induction on $k$: since the
expected number of $k$-cycles in permutations of size $n\geq 1$ is
exactly $1/k$ (thus finite), the fact that the number of $k$-cycles
almost surely increases infinitely often in a random descent implies
that it also decreases infinitely often; and, under cycle insertion,
the number of $k$-cycles decreases exactly when the number of
$(k+1)$-cycles increases.

The specific generation tree we describe in this paper has the
following properties:
\begin{enumerate}
\item\label{cond:stability} For each $n \geq 2$ not multiple of $k$, all permutations at
  level $n$ have the same number of $k$-cycles as their parent in the
  tree.
\item\label{cond:optimality} For each $n \geq 2$ such that $n=mk$, all but exactly
  $\frac{(mk)!}{k^m m!}2^{m-1}=o(n!)$ permutations in $\mathcal{S}_{[n]}$
  have the same number of $k$-cycles as their parent.
\item\label{cond:heredity} Whenever a permutation has the same number of $k$-cycles as its
  $k$-th ancestor in the tree, then all its children (and, by
  immediate induction, all its descendants) also have this property.
\item\label{cond:small_change} If a permutation $\sigma$ does not have the same number of
  $k$-cycles as its parent, then the difference is $\pm 1$.
\end{enumerate}

As a consequence, the evolution of the number of $k$-cycles in an
infinite random descent through the tree is quite different from the
``cycle insertion'' generation tree: with probability $1$, the descent
will, at some (random) level in the tree, reach a permutation whose
number of $k$-cycles is the same as its $k$-th antecedent; and, once
this happens, this number of $k$-cycles will remain constant for the
rest of the descent.

The first property above is only possible because of a specific
property on the distribution of $k$-cycles in random permutations,
which we have not been able to find in previous literature: if
$\lfloor n/k\rfloor = \lfloor n'/k\rfloor$, then for any integer
$\ell$, the proportion of permutations having exactly $\ell$
$k$-cycles is the same in $\mathcal{S}_{[n]}$ and in
$\mathcal{S}_{[n']}$. We give an elementary proof, using generating
functions, of this fact in the next section, and a bijective proof is
a byproduct of our tree construction.

The number of permutations having a different number of $k$-cycles
from their parent, as described in the second property above, is also
minimum possible, as we shall prove in the next section. Overall, this
means that our generation tree is optimal in this sense.

\section{The generation tree}\label{sec:tree}

The main objective of our generation tree is to preserve, as much as
possible, the number of $k$-cycles between any permutation $\sigma$
and its direct children in the tree. Our construction often
corresponds to the cycle insertion procedure as described in the
previous section.

Cycle insertion will change the number of $k$-cycles exactly when the
picked integer $i$ belongs to a $(k-1)$- or $k$-cycle, so a natural
idea when trying to design the generation tree is to use cycle
insertion in all other cases (thus obtaining only permutations in
which the maximum element is neither in a $k$- nor a $(k+1)$-cycle),
and somehow ``fix'' the remaining cases. 

In these two cases, we will deviate from the cycle insertion
construction. When $\len_{\sigma}(i) = k-1$, we will most often
produce a permutation $\sigma'$ with $\len_{\sigma'}(n) = k+1$ which
cannot be obtained otherwise.  When $\len_{\sigma}(i) = k$, we will
most often replace $i$ with $n$ in its cycle, then somehow insert $i$
somewhere else, taking care not to create or suppress any $k$-cycles. 

The situation is made a bit more complicated by the requirement for
the hereditary property (condition 3 in the previous section).

\subsection{Description of the tree}
\label{our-generation-tree}

We now give the global description of the tree, that is, describe, for any $\sigma\in\mathcal{S}_{[n]}$ and $i\in [n]$, how to
construct the $i$-th child $\sigma'$ of $\sigma$. The description uses
several operations and notations which will only be described later.

\begin{algorithm}[t]
\textsc{Generation-Tree}\vspace{0.1cm} \hrule \vspace{0.15cm}
The root of our tree is the unique permutation of size $1$. 

Let $n \geq 2$, $\sigma \in \mathcal{S}_{[n-1]}$, $i \in [n]$, $\tau = \ins(\sigma,i,n)$ and $(\ell,\zeta) \in [0..n-1] \times \mathcal{S}_{[n]}$ such that: 
$$(\ell,\zeta)  = \left\{
    \begin{array}{ll}
        (\len_{\sigma}(i), \tau) & \mif \len_{\sigma}(i)\not=k, \\
        (\len_{\sigma}(\gamma(\sigma)), \ins(\tau, \sigma^{-1}(\gamma(\sigma)), i)) & \mif \len_{\sigma}(i)=k \mand i < \gamma(\sigma), \\
        (0,\ins(\tau,i,i)) & \mif \len_{\sigma}(i)=k \mand i > \gamma(\sigma). \\
    \end{array}
\right.$$

In our generation tree, the $i$-th child $\sigma'$ of $\sigma$ is defined in the following fashion:
\begin{enumerate}[I.]
\item\label{rule1} If all other rules do not apply: $\sigma' = \zeta$.

\item\label{rule2} If $\ell = k-1$ and $\sigma$ is not special: $\sigma' = \pop(\zeta, i)$.

\item\label{rule3} If $\ell = 2k-1$, $\zeta$ is special and $k \nmid n$: $\sigma' = \shift^{-1}(\zeta)$.

\item\label{rule4} If $\ell = 2k-1$, $\zeta$ is special and $k \mid n$: $\sigma' = \shc(\zeta)$.

\item\label{rule5} If $\ell = 2k$, $\sigma$ is special, $i > \delta(\sigma)$ and $k \nmid n$:
\begin{enumerate}[(a)]
\item\label{rule5a} If $\len_{\sigma}(i) = 2k$: $\sigma' = \shift(\zeta)$.
\item\label{rule5b} If $\len_{\sigma}(i) = k$: $\sigma' = \ins(\zeta, \delta(\zeta,i), i)$.
\end{enumerate}

\item\label{rule6} If $\ell = k-1$ and $\sigma$ is special:
\begin{enumerate}[(a)]
\item\label{rule6a} If $\len_{\sigma}(i) = k-1$: $\sigma' = \zeta$.
\item\label{rule6b} If $\len_{\sigma}(i) = k$: $\sigma' = \hsh(\zeta,i)$.
\end{enumerate}
\end{enumerate}
\label{generation_tree_description}
\end{algorithm}

In the description of our generation tree, we use the
following notations:
\begin{itemize}
\item Some permutations will be called \emph{special}; their full
  definition is postponed to \S~\ref{special_permutations}. Special permutations have only
  cycles of lengths $k$ and $2k$, with the possible addition of a
  single \emph{special cycle}, denoted $\spec(\sigma)$, whose length is at most
  $k-1$. Non-special permutations have the important property of
  having only non-special permutations as their children, all of which
  have the same number of $k$-cycles as their parent.
\item $\len_{\sigma}(j)$ is the length of the cycle of $j$ in
  $\sigma$, with the convention $\len_{\sigma}(n) = 0$;
\item $\gamma(\sigma)$ is the largest element of $\sigma$ which is
  not in a $k$-cycle, with the convention $\gamma(\sigma) = 0$ if
  there is no such element;
\item when $\sigma$ is special, $\delta(\sigma)$ is the smallest
  element of the special cycle of $\sigma$: $\delta(\sigma) =
  \min(\spec(\sigma))$, with the convention $\delta(\sigma) = 0$ if
  $|\spec(\sigma)|= 0$. Moreover, we set $$\delta(\sigma,i)  = \left\{
    \begin{array}{ll}
        \delta(\sigma) & \mif |\spec(\sigma)| \not= 0, \\
        i & \mif |\spec(\sigma)|= 0.
    \end{array}
\right.$$
\end{itemize}

The notation $\tau=\ins(\sigma,a,b)$ corresponds to a variant of cycle
insertion: if $b$ is not an element of $\sigma$, then it is exactly
the result of inserting $b$ after $a$ in $\sigma$; if $b$ is an
element of $\sigma$, then one must first ``remove'' it from its cycle,
\textit{i.e.}, set $\tau(a)=b$, $\tau(b)=\sigma(a)$,
$\tau(\sigma^{-1}(b))=\sigma(b)$ unless $b=\sigma(b)$, and
$\tau(j)=\sigma(j)$ for all other $j$.

The tree description uses some additional operations $\pop$, $\shift$,
$\shc$ and $\hsh$, which will be defined later.

\begin{theorem} \label{generation_tree_theorem} The description
  \textsc{Generation-Tree} defines a uniform generation tree for
  permutations, satisfying the conditions \ref{cond:stability},
  \ref{cond:optimality}, \ref{cond:heredity} and
  \ref{cond:small_change} above.
\end{theorem}

The next subsection is devoted to some enumerative considerations.
The rest of the section contains the definitions of the missing
operators, and the proof of some of their properties.

\begin{figure}
\centering
\begin{tikzpicture}[scale=0.8, grow=right, level distance=45mm, child anchor=west]
\tikzstyle{level 1}=[sibling distance=71mm]
\tikzstyle{level 2}=[sibling distance=23.5mm]
\tikzstyle{level 3}=[sibling distance=5.5mm]
\tikzstyle{red} = [font=\bfseries]
\tikzstyle{blue} = [color=gray]
\node {\textbf{(1)}}child { node {\textbf{(12)}}child { node {\textbf{(1)(23)}}child { node {\textbf{(14)(23)}}{}}child { node {(1)(2)(34)}{}}child { node {(1)(24)(3)}{}}child { node {(1)(23)(4)}{}}}child { node {\textbf{(13)(2)}}child { node {\textbf{(1234)}}{}}child { node {\textbf{(13)(24)}}{}}child { node {(14)(2)(3)}{}}child { node {(13)(2)(4)}{}}}child { node {\textbf{(12)(3)}}child { node {\textbf{(1324)}}{}}child { node {\textbf{(1423)}}{}}child { node {\textbf{(12)(34)}}{}}child { node {(12)(3)(4)}{}}}}child { node {(1)(2)}child { node {(132)}child { node {(1432)}{}}child { node {(1)(243)}{}}child { node {(1342)}{}}child { node {(132)(4)}{}}}child { node {(123)}child { node {(143)(2)}{}}child { node {(1243)}{}}child { node {(1)(234)}{}}child { node {(123)(4)}{}}}child { node {(1)(2)(3)}child { node {(142)(3)}{}}child { node {(124)(3)}{}}child { node {(134)(2)}{}}child { node {(1)(2)(3)(4)}{}}}};
\end{tikzpicture}
\caption{Our generation tree for $k=2$ up to level $4$ with special permutations drawn in bold.}
\label{fig:generation_tree}
\end{figure}

\subsection{Optimum number of changing permutations}
\label{optimum-changing}

In any possible uniform generation tree for permutations, we will call
 a permutation \emph{changing} if it has a different number of $k$-cycles
from that of its parent. Because the distribution of parameter $c_k$
over $\mathcal{S}_{[n-1]}$ is different from the distribution of $c_k$ over $\mathcal{S}_{[n]}$ when $n$ is a multiple of $k$, any
generation tree will have at least some number of changing
permutations at those levels. We now make this quantitatively precise.

We start by proving the fact, mentioned in \S~\ref{sec:classic_gentree}, that the
distribution of the $c_k$ statistic over $\mathcal{S}_{[n]}$ only
changes when $n$ is a multiple of $k$.

Let $f_k(n,\ell)$ denote the number of permutations of size $n$ with
exactly $\ell$ $k$-cycles, and $q_k(n,\ell)=f_k(n,\ell)/n!$ their
proportion among permutations of size $n$. We will call such
permutations $(n,\ell)$-permutations.

\begin{proposition}\label{prop:dist_unchanged}
  For any $n\geq 2$ and $\ell$, we have
\begin{displaymath}
f_k(n,\ell) = \left\{ 
  \begin{array}{ll}
    n f_k(n-1,\ell) & \mif k \nmid n,\\
    n f_k(n-1,\ell) + (-1)^{m-\ell} \frac{(mk)!}{k^m \ell! (m-\ell)!} & \mif n=mk.
  \end{array}\right.
\end{displaymath}
\end{proposition}

\begin{proof}
  The statement is equivalent to a reformulation in terms of the
  $q_k$'s: $q_k(n,\ell)=q_k(n-1,\ell)$ if $n$ is not a multiple of
  $k$, and
  \begin{displaymath}
    q_k(n,\ell) - q_k(n-1,\ell) = (-1)^{m-\ell}\frac{\binom{m}{\ell}}{k^m m!},
  \end{displaymath}
if $n=km$.

  We start from the generating function for permutations according to
  size (exponential, counted by variable $x$) and number of $k$-cycles
  (ordinary, counted by variable $y$). From (\cite{wilfgf2},
  Thm. 4.7.2), this generating function is
  \begin{displaymath}
    G_k(x,y) = \sum_{n,\ell} q_k(n,\ell) x^n y^\ell = 
\frac{\exp(\frac{x^k(y-1)}{k})}{1-x}.
  \end{displaymath}
  Multiplying by $1-x$, we get a new generating function:
  \begin{displaymath}
    (1-x) G_k(x,y) = \sum_{n,\ell} \left(q_k(n,\ell) - q_k(n-1,\ell)\right) x^n y^\ell = \exp\left(\frac{x^k(y-1)}{k}\right).
  \end{displaymath}
  This new function is analytic in $y$ and $x^k$, so the
  coefficient of $x^n$ is zero unless $n$ is a multiple of $k$,
  proving the first case. The second case follows immediately from the
  Taylor expansion of the exponential function.  
\end{proof}

The first case of Proposition~\ref{prop:dist_unchanged} shows that it
is at least conceivable to look for a generation tree where every
permutation of size not multiple of $k$ has the same number of
$k$-cycles as its parent. For $n$ multiple of $k$, it gives us a lower
bound on the total number of changing permutations at level $n$ of any
uniform generation tree.


\begin{corollary} \label{optimum-changing-proposition} In any uniform
  generation tree, for any $m \geq 1$, at least $\frac{(mk)!}{k^m m!}
  2^{m-1}$ permutations of level $mk$ are changing permutations.
\end{corollary}

\begin{proof}
  If $n=km$ and $m - \ell$ is even, then by Proposition~\ref{prop:dist_unchanged}
  there are more $(n,\ell)$-permutations than children of
  $(n-1,\ell)$-permutations. Hence at least $f_k(n,\ell) - n
  f_k(n-1,\ell)$ among the $(n,\ell)$-permutations must
  have a parent with a different number of $k$-cycles. 
Summing over the possible $\ell$ gives the lower bound we are looking for: the number of changing permutations at level $n=mk$ must be at least
\begin{displaymath}
  \frac{(mk)!}{k^m m!} \sum_{\substack{\ell=0\\m-\ell\text{ even}}}^{m} \binom{m}{\ell} = \frac{(mk)!2^{m-1}}{k^m m!}.\qedhere
\end{displaymath}
\end{proof}

\subsection{Some special families of permutations}

Our construction is strongly dependent on a family of permutations that
we identify as \textit{special}. These permutations play a key role in
our generation tree and are exactly the permutations that have
descendants with a different number of $k$-cycles than themselves.

Special permutations are defined through a smaller family of
permutations which we call \textit{critical}.

A last family of permutations, \textit{quasi-special} permutations,
plays a minor role in the construction and are described at the end of
this section.

\subsubsection{Critical permutations}
\label{critical_permutations}

In Proposition~\ref{optimum-changing-proposition}, we gave an
\textit{a priori} lower bound on the number of \emph{changing}
permutations, valid for any possible uniform generation tree. We now
define a subset of permutations with the appropriate cardinality,
which will play this role in our tree.

  If $\sigma$ is a permutation over $V$ and $i \in V$,
  $\sigma^{[\ell]}(i)$ stands for the set $\{\sigma(i), \cdots,
  \sigma^{\ell}(i)\}$ of the $\ell$ first iterated images of $i$ under
  $\sigma$. More generally, we let $\sigma^{[a,b]}(i) = \{\sigma^j(i)
  \st a \leq j \leq b \}$ and in particular $\sigma^{[a,b]}(i) =
  \emptyset$ if $b < a$, and $\sigma^{[0,0]}(i) = \{\sigma^{0}(i)\} =
  \{i\}$.

\begin{definition}
  For any permutation $\sigma$ over some set $V$ of integers, let
  $C_1$, $\dots$, $C_m$ be the cycles of length other than $k$ in
  $\sigma$, ordered by their smallest element. Also, let $s_i = \min
  C_i$ be the minima of these cycles, with the convention that
  $s_{m+1} = |\sigma| + 1$.

All cycles of length $k$ in $\sigma$ are considered \textbf{critical}.

Among the other cycles, $C_i$ is also said to be \textbf{critical} if
$C_{i-1}$ is critical (for $i>1$), $|C_i| = 2k$, and
$$\sigma^k(s_i) = \min \sigma^{[k,2k-1]}(s_i)\cup \{s_{i+1}\}.$$
\end{definition}

\begin{definition}
A permutation $\sigma$ is \textbf{critical} if all its cycles are critical.
\end{definition}

Note that critical permutations have only $k$- and $(2k)$-cycles, with
extra conditions on the $(2k)$-cycles.

Permutations of size $mk$ made of $m$ $k$-cycles are easily
enumerated: there are exactly $(mk)!/(m!k^{m})$ of them. Note that
this is exactly the product of all integers not a multiple of $k$ up to
$2mk$.

It is easy to see that critical permutations of size $mk$ with $\ell$
$k$-cycles are in bijection with permutations of the same size with
exactly $m$ $k$-cycles, among which an even number $m-\ell$ are
selected. Indeed, merging the selected cycles pairwise into
$2k$-cycles (in order of their smallest elements), we obtain a
critical permutation (see \S~\ref{hide-and-shift} for the precise
definition of this bijection). Note that we can easily reverse the
procedure and identify which cycles have been chosen in the process.

Thus the number $C(mk,\ell)$ of critical permutations of size $mk$
with $\ell$ $k$-cycles (which implies that $m-\ell$ has to be even) is
given by
$$ C(mk,\ell) = \frac{(mk)!}{k^m m!} \binom{m}{\ell}.$$

Summing over values of $\ell$ with the appropriate parity, we get the
total number $C(mk)$ of critical permutations of size $mk$ as
$C(mk)=2^{m-1} C(mk,0)$. By definition, $C(n) = 0$ if $n$ is not a multiple of $k$.

These permutations will be exactly the changing permutations in our
generation tree. Note that their number matches the lower bound on the
number of such permutations given by
Proposition~\ref{optimum-changing-proposition}.

\subsubsection{Special permutations}
\label{special_permutations}

We now define the set of \textbf{special} permutations, which, in our
tree, will be exactly those permutations with at least one descendent
having a different number of $k$-cycles. In other words, special
permutations will be all ancestors of critical permutations.

\begin{definition}
  A permutation $\sigma$ is said to be \textbf{special} if it has at most one cycle of length strictly less than $k$ (called its \textit{special
    cycle}, and denoted $\spec(\sigma)$), and the elements not in this cycle form a critical permutation.
\end{definition}

Note that for $k=1$, critical and special permutations are the same.

Contrary to critical permutations, there are special
permutations of all sizes $n$. The length of the special cycle
must be $|\spec(\sigma)| = n \bmod k$. However, for
any $n$, all special permutations of size $n$ have numbers of
$k$-cycles of the same parity: 
for a critical permutation over the elements not in $\spec(\sigma)$ to exist, $\lfloor n/k \rfloor - \ell$ must be even. As for critical permutations, it is not very hard to count the number
of special permutations of a given size $n$.

In order to construct a special $(n,\ell)$-permutation $\sigma$ with
$\lfloor n/k \rfloor - \ell$ even, we can first build the cycle
$\spec(\sigma)$ of size $h = n \bmod k$: there are
$\tbinom{n}{h} (h-1)!$ possibilities for this cycle if $h > 0$, and
obviously $1$ possibility if $h=0$. The rest of the permutation is any
critical permutation with $\ell$ $k$-cycles over the remaining
elements.

Hence the number $S(n,\ell)$ of special permutations  of size $n=mk+h$
($0\leq h<k$) with $\ell$ $k$-cycles, is given by
$$S(n,\ell) = \left\{
\begin{array}{ll}
\frac{(mk)! \binom{m}{\ell}}{k^m m!} & \mif h=0,\\
\binom{mk+h}{h} (h-1)! \frac{(mk)! \binom{m}{\ell}}{k^m m!} & \mother.
\end{array}\right.$$

Summing over values of $\ell$ yields the total number $S(n)$ of
special permutations, which we write as a proposition for further reference:

\begin{proposition}\label{prop:countingspecials}
  For $n=mk+h$ with $0\leq h\leq k-1$, the total number $S(n)$ of
  special permutations of size $n$ is given by
\begin{displaymath}
S(n) = \left\{
\begin{array}{ll}
(h-1)! & \mif m=0,\\
\frac{1}{2} \left(\frac{2}{k}\right)^{m}\frac{(mk)!}{m!} & \mif h=0 \mand m\geq 1,\\
\frac{1}{2h} \left(\frac{2}{k}\right)^{m}\frac{(mk+h)!}{m!} & \mother.
\end{array}\right.
\end{displaymath}
\end{proposition}

Let us close this section by introducing an additional notation we shall
use on special permutations in the following sections.

\begin{definition}
  For any special permutation $\sigma$ of size $n$, we let
  $p_1(\sigma)$, $p_3(\sigma)$, $\dots$, $p_{2m-1}(\sigma)$ be the $m$
  minima of the $m$ $(2k)$-cycles of $\sigma$, and we let $p_{2j}(\sigma) =
  \sigma^k(p_{2j-1}(\sigma))$ for $j \in [m]$. The elements
  $p_j(\sigma)$ for $j \in [2m]$ are called the \textit{critical
    elements} of $\sigma$.
\end{definition}

\subsubsection{Quasi-special permutations}

We now define a third family of permutations which we need in order to describe
our uniform generation tree when $k \geq 2$.

\begin{definition}
For $k\geq 2$, a permutation $\sigma$ over $V$ is said to be \textbf{quasi-special} if:
\begin{enumerate}
\item it has one $(k-1)$-cycle $D_1$ and one $(k+1)$-cycle $D_2$;
\item the permutation $\tau$ formed by the elements of $\sigma$ belonging neither to $D_1$ nor to $D_2$ is \textit{critical};
\item $\gamma(\sigma)$ is in $D_2$ and $\min(D_1) < \sigma(\gamma(\sigma))$;
\item if $\tau$ has $(2k)$-cycles, its last critical element is
  smaller than $\min(D_1)$.
\end{enumerate}

For $k=1$, a permutation is quasi-special if and only if it is special.
\end{definition}

Note that no constraints are imposed on the elements of the cycle $D_2$
other than $\gamma(\sigma)$ and its image; in fact, these elements can
be anything between $1$ and $\gamma(\sigma)-1$.

We now compute the number of quasi-special permutations of a given
size $n=mk$, when $k\geq 2$. Starting from an $(mk,m)$-permutation
$\sigma$, select an even nonzero number $m-\ell$ of its cycles, write
$\gamma$ for the maximum element of the selected cycles, and identify,
among the selected cycles not containing $\gamma$, the one with the
largest minimum element; call this element $p$. We obtain a
quasi-special permutation by removing $\sigma(p)$ from its cycle, and
inserting it after $\gamma$, then merging the remaining selected
cycles pairwise in increasing order of their minima. This is
bijective; starting from the quasi-special permutation, one can easily
recover $\gamma$ (the maximum of the $(k+1)$-cycle), remove its image
and insert it after the minimum of the $(k-1)$-cycle, and split all
$(2k)$-cycles into $k$-cycles.

Hence, the number $Q(mk)$ of quasi-special permutations of size $mk$ is
given by
$$ Q(mk) = \frac{(mk)!}{k^m m!} \sum_{\substack{\ell = 2 \\ \ell \text{ even}}}^{m} \binom{m}{\ell} = \frac{(mk)!}{k^m m!} \left( 2^{m-1} - 1 \right).$$

By the same reasoning,
we obtain a formula for the number of quasi-special permutations of
size $n=mk$ with exactly $\ell$ $k$-cycles ($m-\ell<m$ even),
\begin{displaymath}
  Q(mk,\ell) = \frac{(mk)!}{k^m m!} \binom{m}{\ell}.
\end{displaymath}

\subsection{Some simple cycle manipulations}

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node (a) at (-3,0) {$a$};
\node (b) at (0,0) {$b$};

\path[->] (a) edge[bend left, red, dashed, thick] (b);
\path[->] (b) edge[bend left, blue, densely dotted, thick] (a);

\node (p1) at (1.5,0.33) {};	
\node (p2) at (4.5,0.33) {};	
\path[->] (p1) edge[thick, bend left] node[above] {$\spl$} (p2);

\node (pp1) at (1.5,-0.33) {};	
\node (pp2) at (4.5,-0.33) {};	
\path[->] (pp2) edge[thick, bend left] node[below] {$\app$} (pp1);

\node (ap) at (6,0) {$a$};
\path[->] (ap) edge[out=45,in=-45, red, dashed, thick, loop] (ap);

\node (bp) at (7.5,0) {$b$};
\path[->] (bp) edge[out=45,in=-45, blue, densely dotted, thick, loop] (bp);
\end{tikzpicture}
\end{center}
\caption{Illustration of $\spl$ and $\app$ procedures. Dashed and dotted lines represent (potentially empty) portions of a cycle, \textit{i.e.}, iterated images under $\sigma$ starting from the source of the edge until the target is met.}
\label{fig:split-append}
\end{figure}

As a preliminary to defining the operators on permutations that we
need in order to fully describe our generation tree, we now define
some simple transformations in terms of cycles.

We have already described the $\ins$ operation that we use to add an
element to a cycle.

We will have on occasion to \emph{remove} an element from a
permutation. This is a partial inverse to the $\ins$ operation. When
we mention the permutation $\sigma'$ obtained by removing an element
$b$ from its cycle in a permutation $\sigma\in \mathcal{S}_V$, we mean
that $\sigma'\in \mathcal{S}_{V\setminus\{b\}}$ is such that $\sigma =
\ins(\sigma', \sigma^{-1}(b), b)$. Equivalently, $\sigma' =
\hbox{remove}(\sigma,b)$ is defined as
follows:
\begin{itemize}\itemsep0em 
\item if $\sigma(b) \not= b$, $\sigma'(\sigma^{-1}(b)) = \sigma(b)$,
\item for all $j \in V \setminus \{\sigma^{-1}(b),b\}$, $\sigma'(j) = \sigma(j)$.
\end{itemize}

We still need two more operations on permutations that are defined in
terms of their cycles: \emph{splitting} a cycle into two cycles, and the
opposite operation of \emph{connecting} two different cycles. Both operations
correspond to the same composition with the transposition $\tau_{a,b}
= (a\; b)$, and the effect (splitting a cycle or connecting cycles)
depends only on whether $a$ and $b$ lie inside the same cycle in the
original permutation.

If $\sigma\in\mathcal{S}_V$ and $a,b$ are two elements of $V$,
then the permutation $\sigma' = \tau_{a,b} \circ
\sigma$ is defined as:
\begin{itemize}\itemsep0em
\item $\sigma'(\sigma^{-1}(b)) = a$, and $\sigma'(\sigma^{-1}(a)) = b$,
\item for all $i \in V \setminus \{\sigma^{-1}(a),\sigma^{-1}(b)\}$, $\sigma'(i) = \sigma(i)$.
\end{itemize}
If $a$ and $b$ are in the same cycle in $\sigma$, then the above
operation will result in splitting the cycle into two cycles, one
containing $a$ (and its iterated images under $\sigma$ up to
$\sigma^{-1}(b)$) and one containing $b$ (and its iterated images up
to $\sigma^{-1}(a)$); to make it clear, we shall use
$\spl(\sigma,a,b)$ to denote the obtained permutation, with the
convention that $\spl(\sigma,a,b) = \sigma$ if $a$ and $b$ are already
in different cycles. On the other hand, if $a$ and $b$ are in
different cycles in $\sigma$, this composition results in merging
the cycles of $a$ and $b$ into a single one; to make it clear, we will
use $\app(\sigma,a,b)$ in this case, and we set $\app(\sigma,a,b) =
\sigma$ when $a$ and $b$ are in the same cycle in $\sigma$.


\subsection{Insertion into $(k-1)$-cycles}

We now define an operator $\pop$ which is the key
ingredient of our generation tree. In our construction, it is used to
define the $i$-th child of a permutation $\sigma$ in most cases where
$i$ is in a $k$- or $(k-1)$-cycle of $\sigma$. By itself, it would be
a sufficient ingredient to define a generation tree with the
``preservation of $c_k$'' property (conditions 1 and 2 of our tree);
most of the added complexity is there because we want to
ensure the ``heredity'' property (condition 3). 

This operator can also be seen as providing a bijective proof of
Proposition~\ref{prop:dist_unchanged}, as we shall see.

\subsubsection{The $\pop$ operator}
\label{p-operator}

Let $\sigma\in \mathcal{S}_V$ be some permutation, and $i\in V$, such
that
\begin{itemize}\itemsep0em
\item $\sigma$ is not critical;
\item $\len_{\sigma}(i) = k$;
\item $\sigma(i)$ is the largest element of its cycle in $\sigma$, and
  $\sigma(i)>\gamma(\sigma)$.
\end{itemize} 

Under these conditions, we define $\sigma'= \pop(\sigma,i)\in
\mathcal{S}_V$ below. The important properties of $\pop$ are given by
the following proposition.

\begin{proposition} \label{pop-proposition} $\pop$ defines a bijection
  between, on the one hand, non-critical permutations $\sigma$ with a
  marked element $i$ such that $\sigma(i) > \gamma(\sigma)$,
  $\sigma(i)$ is the maximum of its cycle, and $\len_{\sigma}(i) = k$;
  and, on the other hand, permutations $\sigma'$ on the same set such
  that $\len_{\sigma'}(\gamma(\sigma')) = k+1$ and $\sigma'$ is not
  quasi-special. Moreover, whenever $\sigma'= \pop(\sigma,i)$, then $c_k(\sigma')=c_k(\sigma)-1$.
\end{proposition}

Note that the conditions on $\sigma'$ imply that it is not special:
if $k>1$, the existence of a $(k+1)$-cycle is sufficient; if $k=1$,
quasi-special and special permutations are the same.

To define $\pop$, we first need to define $p(\sigma)$ for non critical permutation
$\sigma$, and in some cases, we further define $p'(\sigma)$ and $p''(\sigma)$.

\begin{algorithm}[t]\label{pop-desc}
\textsc{$\pop$-operator}\vspace{0.1cm} \hrule \vspace{0.15cm}
Let $(\sigma,i) \in S_V \times V$ be such that $\sigma$ is not critical, $\len_{\sigma}(i) = k$, $\sigma(i)$ is the largest element of its cycle and $\sigma(i) > \gamma(\sigma)$. We set $\gamma = \sigma(i)$, $p = p(\sigma)$, $x=\sigma^{k-1}(p)$,
$y=\sigma^k(p)$, $\sigma_1 = \ins(\sigma, \gamma, x)$ and $\sigma_2 =
\ins(\sigma, \gamma, y)$.

The permutation $\sigma' = \pop(\sigma,i)$ is defined as follows:
\begin{enumerate}
\item \label{pop1}If $\len_\sigma(p)\not= k+1$, and condition $2$ does not apply:
\begin{enumerate}
\item \label{pop1a}If $\sigma(p) = p$: $\sigma' = \ins(\sigma, \gamma, p)$.
\item \label{pop1b}If $\sigma(p) \not= p$: $\sigma' = \ins(\sigma, \gamma, \sigma^{-1}(p))$.
\end{enumerate} 

\item \label{pop2}
\begin{enumerate}
\item \label{pop2a}If $\len_\sigma(p) = 2k+1$, $x = p'$ and $y = p''$: $\sigma' = \spl(\sigma_1, p, p'')$.
\item \label{pop2b}If $\len_\sigma(p) = 2k+1$ and $y = p'$: $\sigma' = \spl(\sigma_1, p, p')$.
\end{enumerate} 

\item \label{pop3}If $\len_\sigma(p)=k+1$:
\begin{enumerate}
\item \label{pop3a} If $x = p'$:
\begin{enumerate}
\item \label{pop3ai}If $y = p''$: $\sigma' = \ins(\sigma_1, p'', p'')$.
\item \label{pop3aii}If $y \not= p''$ and $\len_\sigma(p'') \not= k-1$: $\sigma' = \ins(\sigma_1, p'', y)$.
\item \label{pop3aiii}If $\len_\sigma(p'') = k-1$: $\sigma' = \app(\sigma_2, p, p'')$.
\end{enumerate}

\item \label{pop3b}If $y = p'$: $\sigma' = \ins(\sigma_1, p', p')$.
\item \label{pop3c}If $p' \not\in \{x,y\}$ and $\len_\sigma(p') \not= k-1$: $\sigma' = \ins(\sigma_1, p', y)$.
\item \label{pop3d}If $\len_\sigma(p') = k-1$: $\sigma' = \app(\sigma_2, p, p')$.

\end{enumerate}
\end{enumerate}
\end{algorithm}

\begin{definition}
  For any non-critical permutation $\sigma$, $p(\sigma)$ is the
  smallest element in a non-critical cycle. Furthermore, if $\len_\sigma(p(\sigma))>k$, we define $p'(\sigma)$
  as the smallest element in a non-critical cycle that is not in
  $\sigma^{[0..k-2]}(p(\sigma))$ (excluding $p(\sigma)$ in the case
  $k=1$), and $p''(\sigma)$ as the second smallest such element.
\end{definition}

Note that under the condition $\len_{\sigma}(p(\sigma)) > k$,
$p'(\sigma)$ and $p''(\sigma)$ are both well defined, since it is
assumed that the non critical cycle containing $p(\sigma)$ has at least $k+1$ elements
and we only exclude $k-1$ of them. In the case where $k=1$,
$p(\sigma)$ is still excluded, but the cycle not being critical
forbids it from being reduced to the $2$-cycle $(p(\sigma)\ p'(\sigma))$.

The definition of the operator is given in the description
\textsc{$\pop$-operator}.

All rules are presented in Figure~\ref{fig:pop}. Note that some rules
actually define $\sigma'$ in the same way, and are kept separated for
later convenience: \ref{pop1a} is identical to rule \ref{pop1b} in
that they define $\sigma'= \ins(\sigma,\gamma,\sigma^{-1}(p))$; rules
\ref{pop2a} and \ref{pop2b} both define $\sigma'= \spl(\sigma_1,p,y)$;
\ref{pop3ai} and \ref{pop3b} both define
$\sigma'=\ins(\sigma_1,y,y)$. Similarly, \ref{pop3aii} and \ref{pop3c}
correspond to the same action applied to $p''$ for the former, and
$p'$ for the latter; this is also true of \ref{pop3aiii} and \ref{pop3d}.


\begin{figure}
\begin{center}

%1.a
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-0.5-2,0.66) {\underline{\textbf{\ref{pop1a}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\path[->] (p) edge[loop] (p);

\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$p$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node at (15+2,0) {};
\end{tikzpicture}

%1.b
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-0.5-2,0.66) {\underline{\textbf{\ref{pop1b}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\node (a) at (4.5-1,0) {$a$};	
\node (k) at (3.5-1,-0.042)  {{\footnotesize $\not= k+1$}};	
\path[->] (p) edge[bend left, red, dashed, thick] (a);
\path[->] (a) edge[bend left] (p);


\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$a$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node (pp) at (11.75+1,0) {$p$};
\node (kp) at (12.25+1,0.55)  {{\footnotesize $\not= k-1$}};
\path[->] (pp) edge[out=45,in=-45, red, dashed, thick, loop] (pp);

\node at (15+2,0) {};
\end{tikzpicture}

%2.a
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-0.5-2,0.66) {\underline{\textbf{\ref{pop2a}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\node (x) at (4.75-1,0.66) {$p'$};
\node (y) at (5.5-1,0) {$p''$};

\node (kp) at (4.05-1,0.1) {{\footnotesize $2k+1$}};

\path[->] (p) edge[bend left, red, dashed, thick] (x);
\path[->] (x) edge[bend left] (y);
\path[->] (y) edge[bend left, blue, densely dotted, thick] (p);

\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$p'$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node (pp) at (11.75+1,0) {$p$};
\node (kp) at (12.25+1,0.55)  {{\footnotesize $k-1$}};
\path[->] (pp) edge[out=45,in=-45, red, dashed, thick, loop] (pp);

\node (ppp) at (13.25+1,0) {$p''$};
\node (kpp) at (13.85+1,0.66)  {{\footnotesize $k+1$}};
\path[->] (ppp) edge[out=45,in=-45, blue, densely dotted, thick, loop] (ppp);

\node at (15+2,0) {};
\end{tikzpicture}

%2.b
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-0.5-2,0.66) {\underline{\textbf{\ref{pop2b}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\node (x) at (4.75-1,0.66) {$x$};
\node (y) at (5.5-1,0) {$p'$};

\node (kp) at (4.05-1,0.1) {{\footnotesize $2k+1$}};

\path[->] (p) edge[bend left, red, dashed, thick] (x);
\path[->] (x) edge[bend left] (y);
\path[->] (y) edge[bend left, blue, densely dotted, thick] (p);

\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$x$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node (pp) at (11.75+1,0) {$p$};
\node (kp) at (12.25+1,0.55)  {{\footnotesize $k-1$}};
\path[->] (pp) edge[out=45,in=-45, red, dashed, thick, loop] (pp);

\node (ppp) at (13.25+1,0) {$p'$};
\node (kpp) at (13.85+1,0.66)  {{\footnotesize $k+1$}};
\path[->] (ppp) edge[out=45,in=-45, blue, densely dotted, thick, loop] (ppp);

\node at (15+2,0) {};
\end{tikzpicture}

%3.a.i
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-0.5-2,0.66) {\underline{\textbf{\ref{pop3ai}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\node (x) at (4-1,0.66) {$p'$};	
\node (y) at (4.5-1,0) {$p''$};	
\node (k) at (3.6-1,0.125)  {{\footnotesize $k+1$}};	
\path[->] (p) edge[bend left, red, dashed, thick] (x);
\path[->] (x) edge[bend left] (y);
\path[->] (y) edge[bend left] (p);


\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$p'$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node (pp) at (11.75+1,0) {$p$};
\node (kp) at (12.25+1,0.55)  {{\footnotesize $k-1$}};
\path[->] (pp) edge[out=45,in=-45, red, dashed, thick, loop] (pp);

\node (ppp) at (13.75+1,0) {$p''$};
\path[->] (ppp) edge[loop, looseness=3] (ppp);

\node at (15+2,0) {};
\end{tikzpicture}


%3.a.ii
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-0.5-2,0.66) {\underline{\textbf{\ref{pop3aii}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\node (x) at (4-1,0.66) {$p'$};	
\node (y) at (4.5-1,0) {$y$};	
\node (k) at (3.6-1,0.125)  {{\footnotesize $k+1$}};	
\path[->] (p) edge[bend left, red, dashed, thick] (x);
\path[->] (x) edge[bend left] (y);
\path[->] (y) edge[bend left] (p);

\node (p'') at (5.5-1,0) {$p''$};
\path[->] (p'') edge[out=45,in=-45, blue, densely dotted, thick, loop] (p'');
\node (k2) at (6.1-1,0.66)  {{\footnotesize $\not= k-1$}};

\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$p'$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node (pp) at (11.75+1,0) {$p$};
\node (kp) at (12.25+1,0.55)  {{\footnotesize $k-1$}};
\path[->] (pp) edge[out=45,in=-45, red, dashed, thick, loop] (pp);

\node (pp'') at (13.25+1,0) {$p''$};
\node (py) at (14.75+1,0) {$y$};
\path[->] (pp'') edge[bend left] (py);
\path[->] (py) edge[bend left, blue, densely dotted, thick] (pp'');
\node (kpp) at (14+1,0.5)  {{\footnotesize $\not= k+1$}};

\node at (15+2,0) {};
\end{tikzpicture}


%3.a.iii
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-0.5-2,0.66) {\underline{\textbf{\ref{pop3aiii}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\node (x) at (4-1,0.66) {$p'$};	
\node (y) at (4.5-1,0) {$y$};	
\node (k) at (3.6-1,0.125)  {{\footnotesize $k+1$}};	
\path[->] (p) edge[bend left, red, dashed, thick] (x);
\path[->] (x) edge[bend left] (y);
\path[->] (y) edge[bend left] (p);

\node (p'') at (5.5-1,0) {$p''$};
\path[->] (p'') edge[out=45,in=-45, blue, densely dotted, thick, loop] (p'');
\node (k2) at (6.1-1,0.66)  {{\footnotesize $k-1$}};	

\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$y$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node (pp) at (11.75+1,0) {$p$};
\node (ppp) at (14+1,0.66) {$p'$};
\node (pppp) at (14.75+1,0) {$p''$};

\node (kp) at (13.3+1,0.1) {{\footnotesize $2k-1$}};

\path[->] (pp) edge[bend left, red, dashed, thick] (ppp);
\path[->] (ppp) edge[bend left] (pppp);
\path[->] (pppp) edge[bend left, blue, densely dotted, thick] (pp);

\node at (15+2,0) {};
\end{tikzpicture}


%3.b
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-0.5-2,0.66) {\underline{\textbf{\ref{pop3b}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\node (x) at (4-1,0.66) {$x$};	
\node (y) at (4.5-1,0) {$p'$};	
\node (k) at (3.6-1,0.125)  {{\footnotesize $k+1$}};	
\path[->] (p) edge[bend left, red, dashed, thick] (x);
\path[->] (x) edge[bend left] (y);
\path[->] (y) edge[bend left] (p);


\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$x$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node (pp) at (11.75+1,0) {$p$};
\node (kp) at (12.25+1,0.55)  {{\footnotesize $k-1$}};
\path[->] (pp) edge[out=45,in=-45, red, dashed, thick, loop] (pp);

\node (ppp) at (13.75+1,0) {$p'$};
\path[->] (ppp) edge[loop, looseness=3] (ppp);

\node at (15+2,0) {};
\end{tikzpicture}

%3.c
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-0.5-2,0.66) {\underline{\textbf{\ref{pop3c}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\node (x) at (4-1,0.66) {$x$};	
\node (y) at (4.5-1,0) {$y$};	
\node (k) at (3.6-1,0.125)  {{\footnotesize $k+1$}};	
\path[->] (p) edge[bend left, red, dashed, thick] (x);
\path[->] (x) edge[bend left] (y);
\path[->] (y) edge[bend left] (p);

\node (p'') at (5.5-1,0) {$p'$};
\path[->] (p'') edge[out=45,in=-45, blue, densely dotted, thick, loop] (p'');
\node (k2) at (6.1-1,0.66)  {{\footnotesize $\not= k-1$}};

\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$x$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node (pp) at (11.75+1,0) {$p$};
\node (kp) at (12.25+1,0.55)  {{\footnotesize $k-1$}};
\path[->] (pp) edge[out=45,in=-45, red, dashed, thick, loop] (pp);

\node (pp'') at (13.25+1,0) {$p'$};
\node (py) at (14.75+1,0) {$y$};
\path[->] (pp'') edge[bend left] (py);
\path[->] (py) edge[bend left, blue, densely dotted, thick] (pp'');
\node (kpp) at (14+1,0.5)  {{\footnotesize $\not= k+1$}};

\node at (15+2,0) {};
\end{tikzpicture}

%3.d
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-2.5,0.66) {\underline{\textbf{\ref{pop3d}}}};

\node (i0) at (0-1,0) {$i$};
\node (g0) at (1.5-1,0) {$\gamma$};	
\node (k0) at (0.75-1,0)  {{\footnotesize $k$}};	
\path[->] (i0) edge[bend left] (g0);
\path[->] (g0) edge[bend left, dotted] (i0);

\node (p) at (2.5-1,0) {$p$};
\node (x) at (4-1,0.66) {$x$};	
\node (y) at (4.5-1,0) {$y$};	
\node (k) at (3.6-1,0.125)  {{\footnotesize $k+1$}};	
\path[->] (p) edge[bend left, red, dashed, thick] (x);
\path[->] (x) edge[bend left] (y);
\path[->] (y) edge[bend left] (p);

\node (p'') at (5.5-1,0) {$p'$};
\path[->] (p'') edge[out=45,in=-45, blue, densely dotted, thick, loop] (p'');
\node (k2) at (6.1-1,0.66)  {{\footnotesize $k-1$}};

\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (8.75+1,0) {$i$};
\node (g) at (9.75+1,0.66) {$\gamma$};	
\node (a) at (10.75+1,0) {$y$};	
\node (k) at (9.75+1,0.1)  {{\footnotesize $k+1$}};	
\path[->] (i) edge[bend left] (g);
\path[->] (g) edge[bend left] (a);
\path[->] (a) edge[bend left, dotted] (i);

\node (pp) at (11.75+1,0) {$p$};
\node (ppp) at (14+1,0.66) {$x$};
\node (pppp) at (14.75+1,0) {$p'$};

\node (kp) at (13.3+1,0.1) {{\footnotesize $2k-1$}};

\path[->] (pp) edge[bend left, red, dashed, thick] (ppp);
\path[->] (ppp) edge[bend left] (pppp);
\path[->] (pppp) edge[bend left, blue, densely dotted, thick] (pp);

\node at (15+2,0) {};
\end{tikzpicture}
\end{center}

\caption{Illustration of the different rules of the $\pop$ operator for $k \geq 2$. Plain lines indicate direct images under $\sigma$ or $\sigma'$, dashed and dotted lines indicate portions of cycles. Lengths of cycles are shown as integers inside or over cycles. All cycles are implicitly non critical and hence of length not $k$. Conditions are not shown (see text).}

\label{fig:pop}
\end{figure}

\begin{remark}
Let us consider how this operator works when $k = 1$. In this case,
the target set of the operator are non-special permutations $\sigma'$ where $\gamma(\sigma')$ is in a $2$-cycle. 

Moreover, we have $x = p$, $y = \sigma(p)$ and $i =
\gamma(\sigma)$. Hence some rules are never applied: rule~\ref{pop1a}
because $p$ cannot be a fixed point, rules~\ref{pop2a} and \ref{pop3a}
because $x$ cannot be $p'$, rule~\ref{pop3b} because $p$ cannot form a
$2$-cycle with $p'$, and rule~\ref{pop3d} because there are no
$0$-cycles. The three remaining rules (\ref{pop1b}, \ref{pop2b} and
\ref{pop3c}) are recalled in a simpler form with the description of
the tree for $k=1$ (in Section~\ref{k=1}) and depicted in Figure~\ref{fig:pop1}.
\end{remark}

The proof of Proposition~\ref{pop-proposition} is split in the four following lemmas.

\begin{lemma} \label{lemma:pop_onto_k=0}
For $k=1$, $\pop$ is onto.
\end{lemma}

\begin{figure}
\begin{center}

%1.b
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-2.25,0.66) {\underline{\textbf{\ref{pop1b}}}};

\node (g0) at (0,0) {$\gamma$};	
\path[->] (g0) edge[loop] (g0);

\node (p) at (1.5,0) {$p$};
\node (a) at (3.5,0) {$a$};	
\node (k) at (2.5,-0.042)  {{\footnotesize $\geq 3$}};	
\path[->] (p) edge[bend left, red, dashed, thick] (a);
\path[->] (a) edge[bend left] (p);


\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (9.75,0) {$\gamma$};
\node (a) at (11.75,0) {$a$};	
\node (k) at (10.75,0)  {{\footnotesize $2$}};	
\path[->] (i) edge[bend left] (a);
\path[->] (a) edge[bend left] (i);

\node (pp) at (12.75,0) {$p$};
\node (kp) at (13.25,0.55)  {{\footnotesize $\geq 2$}};
\path[->] (pp) edge[out=45,in=-45, red, dashed, thick, loop] (pp);

\node at (16,0) {};
\end{tikzpicture}


%2.b
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-2.25,0.66) {\underline{\textbf{\ref{pop2b}}}};

\node (g0) at (0,0) {$\gamma$};	
\path[->] (g0) edge[loop] (g0);

\node (p) at (1.5,0) {$p$};
\node (x) at (3,0.66) {$p'$};
\node (y) at (4.5,0) {$z$};

\node (kp) at (3,0.1) {{\footnotesize $3$}};

\path[->] (p) edge[bend left] (x);
\path[->] (x) edge[bend left] (y);
\path[->] (y) edge[bend left] (p);

\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (9.75,0) {$\gamma$};
\node (a) at (11.75,0) {$p$};	
\node (k) at (10.75,0)  {{\footnotesize $2$}};	
\path[->] (i) edge[bend left] (a);
\path[->] (a) edge[bend left] (i);

\node (ip) at (12.75,0) {$p'$};
\node (ap) at (14.75,0) {$z$};	
\node (kp) at (13.75,0)  {{\footnotesize $2$}};	
\path[->] (ip) edge[bend left] (ap);
\path[->] (ap) edge[bend left] (ip);

\node at (16,0) {};
\end{tikzpicture}

%3.c
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node[anchor=south west] (rule) [thick] at (-2.25,0.66) {\underline{\textbf{\ref{pop3c}}}};

\node (g0) at (0,0) {$\gamma$};	
\path[->] (g0) edge[loop] (g0);

\node (p) at (1.5,0) {$p$};
\node (y) at (3.5,0) {$y$};	
\node (k) at (2.5,0)  {{\footnotesize $2$}};	
\path[->] (p) edge[bend left] (y);
\path[->] (y) edge[bend left] (p);

\node (p0) at (4.5,0) {$p'$};
\node (k0) at (5,0.66)  {{\footnotesize $\geq 2$}};
\path[->] (p0) edge[out=45,in=-45, red, dashed, thick, loop] (pp);

\node (p1) at (7,0) {};	
\node (p2) at (8,0) {};	
\path[->] (p1) edge[ultra thick] (p2);

\node (i) at (9.75,0) {$\gamma$};
\node (a) at (11.75,0) {$p$};	
\node (k) at (10.75,0)  {{\footnotesize $2$}};	
\path[->] (i) edge[bend left] (a);
\path[->] (a) edge[bend left] (i);


\node (pp) at (12.75,0) {$p'$};
\node (ap) at (14.75,0) {$z$};	
\node (kp) at (13.75,-0.042)  {{\footnotesize $\geq 3$}};	

\path[->] (pp) edge[bend left] (ap);
\path[->] (ap) edge[bend left, red, dashed, thick] (pp);

\node at (16,0) {};
\end{tikzpicture}
\end{center}

\caption{Illustration of $\pop$'s rules for $k=1$.}
%Drawing conventions are the same as Figure~\ref{fig:pop}.
\label{fig:pop1}
\end{figure} 

\begin{proof}
  We construct a preimage $(\sigma,i)$ for any non-quasi-special
  permutation $\sigma'$ with $\len_{\sigma'}(\gamma(\sigma')) =
  2$. Let $p = p(\sigma')$, $p' = p'(\sigma')$ and $i = \gamma =
  \gamma(\sigma')$.

  We distinguish three cases, building in each case a permutation
  $\sigma$ where $i$ is a fixed point. In each case, the other fixed points
  of $\sigma$ are exactly those of $\sigma'$.
\begin{itemize}
\item[\ref{pop1b})] If $p \not= \sigma'(\gamma)$: $\sigma =
  \ins(\sigma', \sigma'^{-1}(p), \sigma'(\gamma))$. In this situation,
  $p$ is in a cycle of length at least $2$ in $\sigma'$, hence in a
  cycle of length at least $3$ in $\sigma$ (hence $p = p(\sigma)$) and
  $\sigma(p) \not= p'(\sigma)$. Hence rule~\ref{pop1b} applies to
  $(\sigma,i)$ (rule~\ref{pop2b} does not apply) and one easily checks
  that $\sigma' = \pop(\sigma,i)$.
\vspace{-1mm}
\item[\ref{pop2b})] If $p = \sigma'(\gamma)$ and
  $\len_{\sigma'}(p') = 2$: $\sigma = \ins(\sigma',
  \sigma'(p'), p)$. In this case, $p$ is inserted before
  $p'$ into a $2$-cycle, hence is in a $3$-cycle in $\sigma$.
  Consequently, $p(\sigma)=p$, and $p'(\sigma)=\sigma(p)$; thus
  rule~\ref{pop2b} applies to $(\sigma,i)$ and gives $\sigma'$.
\vspace{-1mm}
\item[\ref{pop3c})] If $p = \sigma'(\gamma)$ and $\len_{\sigma'}(p')
  \geq 3$: we let $\sigma_1 = \ins(\sigma', p, p)$ and we get the
  permutation $\sigma$ as $\sigma = \ins(\sigma_1, p, \sigma'(p'))$;
  that is, we extract $p$ and $\sigma'(p')$ from their cycles and
  construct a new $2$-cycle with them. We have $p$ in a $2$-cycle in
  $\sigma$, but $p'$ is in another cycle, thus we still have $p =
  p(\sigma)$ and $p' = p'(\sigma)$; rule~\ref{pop3c} applies on
  $(\sigma,i)$ and produces $\sigma'$.\qedhere
\end{itemize}
\end{proof}

\begin{lemma} \label{lemma:pop_onto_k>=2}
For $k\geq 2$, $\pop$ is onto.
\end{lemma}

\begin{proof}
  We construct a preimage $(\sigma,i)$ for any non-quasi-special
  permutation $\sigma'$ with $\len_{\sigma'}(\gamma(\sigma')) = k+1$.
  More precisely, for each possible $\sigma'$, we identify one of the
  ten rules of $\pop$ and describe a preimage $(\sigma,i)$ to which
  said rule applies, and yields $\sigma'$. In each case, $\sigma$ has
  exactly one more $k$-cycle than $\sigma'$.

  Let $\gamma=\gamma(\sigma')$, $i = \sigma'^{-1}(\gamma)$, $a =
  \sigma'(\gamma)$, $C$ the cycle of $\gamma$ (also containing $i$ and
  $a$). Let furthermore $\sigma''$ be the permutation obtained after
  removing the cycle $C$ from $\sigma'$ and adding the element $a$ as
  a fixed point, \textit{i.e.}, $\sigma''= \ins(\sigma|_{V \setminus
    C}, a, a)$. We note $\tilde{p} = p(\sigma'')$.

  In all the following cases (numbered by the corresponding rule of
  $\pop$ which yields $\sigma'$), it should be clear that the cycle
  containing $i$ (and $\gamma$) in $\sigma$ shall be of size $k$
  (hence critical), since the defined permutation $\sigma$ will always
  remove $a$ from its cycle (and leave other $k$-cycles untouched,
  resulting in $\sigma$ having exactly one more $k$-cycle than
  $\sigma'$). 
  
  Furthermore, all other cycles with a minimum less than
  $\tilde{p}$ shall not be modified in the construction of $\sigma$,
  hence these cycles shall remain critical in $\sigma$. Under these
  two conditions, we deduce directly that $\tilde{p} = p(\sigma)$
  if the cycle of $\tilde{p}$ is not critical in $\sigma$. In the
  following, we will not recall these two ``easy'' properties of
  $\sigma$.

Let us first deal with two specific cases.
\begin{enumerate}
\item[1.a)] If $a = \tilde{p}$, we let $\sigma = \ins(\sigma',
  \tilde{p}, \tilde{p})$.
\item[1.b)] If $\len_{\sigma'}(\tilde{p}) < k-1$, we let $\sigma =
  \ins(\sigma', \sigma'^{-1}(\tilde{p}), a)$.
\end{enumerate}

In these first two situations, $\tilde{p}$ is in a cycle of length
strictly less than $k$ in $\sigma$: in the first case, it is a fixed
point in $\sigma$ (and we assumed $k \geq 2$), and in the second case,
it is in a cycle of length $\len_{\sigma'}(\tilde{p}) + 1 < k$. Thus
$\tilde{p}$ is in a non critical cycle in $\sigma$, and therefore
$\tilde{p} = p(\sigma)$.

In the first case, rule number~\ref{pop1a} applies on $(\sigma,i)$ and
yields $\sigma'$. In the second case, rule~\ref{pop1b} is the only
applicable rule, and its application to $(\sigma,i)$
results in the permutation $\sigma'$.

We now move to the remaining cases. From now on, we assume $a \not=
\tilde{p}$ and $\len_{\sigma'}(\tilde{p}) \geq k-1$.

Let us further define two distinguished elements in $\sigma'$: $\tilde{p}'$ and $\tilde{p}''$.

We define $\tilde{p}'$ (resp. $\tilde{p}''$) as the smallest element
(resp. second smallest element) in a non-critical cycle in $\sigma''$
that does not belong to $\sigma'^{[0,k-2]}(\tilde{p})$. Since
$\sigma''$ contains a fixed point larger than $\tilde{p}$ (namely,
$a$), $\tilde{p}'$ is always well defined. Moreover, note that if
$\tilde{p}' = a$ and no element $\tilde{p}''$ can be found in
$\sigma''$ (that is, $\tilde{p}'$ is in the largest non critical
cycle in $\sigma''$), then the permutation $\sigma'$ is quasi-special
(and hence out of the scope of the lemma): indeed, in this situation,
$\gamma = \gamma(\sigma')$ is in a $(k+1)$-cycle, $\tilde{p}$ is the
minimum of a $(k-1)$-cycle, $\tilde{p}' = \sigma'(\gamma)$ is larger
than $\tilde{p}$, and all other cycles are critical in $\sigma''$. If
$\tilde{p}' \not= a$, at the very least, two elements larger than
$\tilde{p}$ are in non critical cycles in $\sigma''$. Overall,
$\tilde{p}'$ and $\tilde{p}''$ are always well-defined under our
current
assumptions.

In all remaining cases, we shall have $\sigma'^{[0,k-2]}(\tilde{p}) =
\sigma^{[0,k-2]}(\tilde{p})$, thus we get $\tilde{p}' = p'(\sigma)$
and $\tilde{p}'' = p''(\sigma)$ whenever $p'(\sigma)$ and
$p''(\sigma)$ are in non critical cycles of $\sigma$. 


We shall see in each rule that $p(\sigma) = \tilde{p}$, thus, for
elements larger than $\tilde{p}$ (which includes $\tilde{p}'$ and
$\tilde{p}''$), not being in critical cycles of $\sigma$ reduces to
not being in $k$-cycles; this is easily checked for the different
rules.

Let us now consider all cases where $\len_{\sigma'}(\tilde{p}) > k$.

\begin{enumerate}
\item[3.a.iii)] If $\len_{\sigma'}(\tilde{p}) = 2k-1$,
  $\sigma'^{k-1}(\tilde{p}) = \tilde{p}'$, and $\sigma'^{k}(\tilde{p})
  = \tilde{p}''$: we set $\sigma_1 =
  \spl(\sigma',\tilde{p},\tilde{p}'')$ and $\sigma = \ins(\sigma_1,
  \tilde{p}, a)$. In this situation, $\tilde{p}$ is in a $(k+1)$-cycle
  in $\sigma$, $\tilde{p}' = \sigma^{k-1}(p(\sigma))$ and
  $\len_{\sigma}(\tilde{p}'') = k-1$, thus rule~\ref{pop3aiii} applies
  to $(\sigma,i)$ and produces $\sigma'$.

\item[3.d)] If $\len_{\sigma'}(\tilde{p}) = 2k-1$ and
  $\sigma'^{k}(\tilde{p}) = \tilde{p}'$: $\sigma_1 = \spl(\sigma,
  \tilde{p}, \tilde{p}')$ and $\sigma = \ins(\sigma_1,
  \sigma_1^{-1}(\tilde{p}), a)$. In this case, $\tilde{p}$ is in a
  $(k+1)$-cycle and $\tilde{p}'$ in a $(k-1)$-cycle in $\sigma$. We
  have $\sigma' = \pop(\sigma,i)$ by rule~\ref{pop3d}.

\item[1.b)] In all remaining cases where $\len_{\sigma'}(\tilde{p}) >
  k$: we let $\sigma = \ins(\sigma', \sigma'^{-1}(\tilde{p}), a)$ and
  we get $\sigma'=\pop(\sigma,i)$ through rule \ref{pop1b}, by the
  following discussion.

  In this case, we increase the length of the cycle of $\tilde{p}$ by
  one, and since by hypothesis it was different from $k-1$, this
  cannot create a $k$-cycle. Moreover, we shall have
  $p(\sigma)=\tilde{p}$, as the only possibilities to create a
  critical cycle of length $2k$ are captured by the previous two
  cases. Indeed, since we insert $a$ in the second part of the
  $2k$-cycle, the first part should already satisfy the critical
  condition in order for the condition to hold for the full
  cycle. However, this implies either
  $\tilde{p}'=\sigma'^k(\tilde{p})$ or
  $\tilde{p}'=\sigma'^{k-1}(\tilde{p})$ and $\tilde{p}'' =
  \sigma'^k(\tilde{p})$; and both of these situations are already
  covered by the two previous cases. 

  Now let us check that rule~\ref{pop1b} is the rule that applies to
  $(\sigma,i)$, \textit{i.e.}, that rule~\ref{pop2} does not preempt
  it. By definition of $\tilde{p}$, it is not in a critical
  $2k$-cycle. Hence, if $\sigma'^k(\tilde{p}) = \tilde{p}'$ or
  $(\tilde{p}',\tilde{p}'')
  =(\sigma'^{k-1}(\tilde{p}),\sigma'^{k}(\tilde{p}))$, the cycle of
  $\tilde{p}$ must be of size other than $2k$. Increasing such a cycle
  cannot produce a $(2k+1)$-cycle and thus rule \ref{pop2} will never
  be used on $\sigma$.
\end{enumerate}

We are now left with the only remaining case:
$\len_{\sigma'}(\tilde{p}) = k-1$. In this part, we will often have to
insert two elements, one after the other, after the same element in $\sigma'$; we use
here the notation $\tau' = \ins(\tau, i, a, b)$ as a short form for $\tau' =
\ins(\ins(\tau, i, b), i, a)$.

The three next cases cover the case $a = \tilde{p}'$.

\begin{enumerate}
\item[3.a.i)] If $a = \tilde{p}'$ and $\len_{\sigma'}(\tilde{p}'') =
  1$: we set $\sigma = \ins(\sigma', \sigma'^{-1}(\tilde{p}),
  \tilde{p}', \tilde{p}'')$. In this case, rule~\ref{pop3ai} applies
  to $(\sigma,i)$ and yields $\sigma'$, since $\tilde{p}$ is in a
  $(k+1)$-cycle of $\sigma$ (hence $\tilde{p} = p(\sigma)$) whose last two 
  elements starting from $\tilde{p}$ are $p'(\sigma)$ and
  $p''(\sigma)$.

\item[3.a.ii)] If $a = \tilde{p}'$ and $\len_{\sigma'}(\tilde{p}'')
  \not\in \{1,k+1\}$: we set $\sigma = \ins(\sigma', \sigma'^{-1}(p),
  \tilde{p}', \sigma'(\tilde{p}''))$. We have then $\tilde{p}$ in a
  $(k+1)$-cycle in $\sigma$ (thus $\tilde{p} = p(\sigma)$) with
  $\sigma^{k-1}(p(\sigma)) = \tilde{p}' = p'(\sigma)$. The cycle of
  $\tilde{p}''$ is one shorter in $\sigma$ than in
  $\sigma'$; however, such a cycle cannot be of length $k$ (thus
  $p''(\sigma) = \tilde{p}''$) nor $k-1$. Hence, we have $\sigma' =
  \pop(\sigma,i)$ using rule~\ref{pop3aii}.

\item[2.a)] If $a = \tilde{p}'$ and $\len_{\sigma'}(\tilde{p}'') =
  k+1$: we set $\sigma_1 = \ins(\sigma', \sigma'^{-1}(\tilde{p}),
  \tilde{p}')$ and the permutation $\sigma = \app(\sigma_1, \tilde{p},
  \tilde{p}'')$. In this situation, $\tilde{p}$ is in $(2k+1)$-cycle
  of $\sigma$ whose elements in positions $k-1$ and $k$ (starting from
  $\tilde{p}$) are $p'(\sigma)$ and $p''(\sigma)$. Here 
  rule~\ref{pop2a} applies to $(\sigma,i)$ and gives $\sigma'$.

\end{enumerate}

Finally, the last three cases cover the remaining situations.

\begin{itemize}
\item[3.b)] If $\len_{\sigma'}(\tilde{p}') = 1$: we set $\sigma = \ins(\sigma',
  \sigma'^{-1}(\tilde{p}), a, \tilde{p}')$. We have $\tilde{p}$ in a
  $(k+1)$-cycle of $\sigma$ with $\tilde{p}'=\sigma^{-1}(\tilde{p})$, hence
  $\tilde{p} = p(\sigma)$ and $\tilde{p}'=p'(\sigma)$. In this
  situation, rule~\ref{pop3b} applies to $(\sigma,i)$ and produces
  $\sigma'$.

\item[3.c)] If $\len_{\sigma'}(\tilde{p}') \not\in \{1,k+1\}$: we set
  $\sigma = \ins(\sigma', \sigma'^{-1}(\tilde{p}), a,
  \sigma'(\tilde{p}'))$. In this case, $\len_{\sigma}(\tilde{p}) =
  k+1$ and $\len_{\sigma}(\tilde{p}') = \len_{\sigma'}(\tilde{p}') - 1
  \not\in \{k-1,k\}$. Hence we have $p(\sigma) = \tilde{p}$ and
  $p'(\sigma)=\tilde{p}'$, and rule~\ref{pop3c} applies to
  $(\sigma,i)$ and yields $\sigma'$.

\item[2.b)] If $a \not= \tilde{p}'$ and $\len_{\sigma'}(p') = k+1$: we
  set $\sigma_1 = \ins(\sigma', \sigma'^{-1}(\tilde{p}), a)$, and
   the permutation $\sigma = \app(\sigma_1, \tilde{p}, \tilde{p}')$. The cycle of
  $\tilde{p}$ in $\sigma$ is then of length $2k+1$, and
  $\sigma^{k}(\tilde{p}) = \tilde{p}'=p'(\sigma)$. Rule~\ref{pop2b} applies
  to $(\sigma,i)$ and yields $\sigma'$.\qedhere
\end{itemize}
\end{proof}

To prove that $\pop$ is one-to-one, we will need the following lemma, which
essentially states that $p(\sigma)$ can be recovered from $\sigma'$.

\begin{lemma}\label{lem:pseconde} Assume $k\geq 2$.
  Let $(\sigma,i)$ be such that $\sigma'=\pop(\sigma,i)$ is well
  defined, and let $\sigma''$ be obtained by removing the cycle containing 
  $i$ from $\sigma'$ and adding $a = \sigma'(\gamma(\sigma'))$ as a
  fixed point. Then $p(\sigma'') = p(\sigma)$.
\end{lemma}

\begin{proof}
  Let $p=p(\sigma)$ and, if they exist, $p'=p'(\sigma)$ and
  $p''=p''(\sigma)$; let also $\tilde{p} = p(\sigma'')$.

  Analysing the ten rules depicted by Figure~\ref{fig:pop},
  we observe that cycles of $\sigma$ other than those containing $i$,
  $p$, and possibly $p'$ and $p''$ all appear identically in
  $\sigma''$; furthermore, the elements of the cycle containing $i$
  are absent from $\sigma''$. Consequently, since $p=p(\sigma)$ is the
  smallest element not in a critical cycle, $p(\sigma'')$ is either
  equal to $p$ (if its cycle in $\sigma''$ is not critical) or larger
  than $p$ (if its cycle in $\sigma''$ is critical). To prove that we
  have $p=\tilde{p}$, we need to prove that the latter case is not
  possible.

  Note that the cycle of $p$ in $\sigma''$ cannot be of length $k$,
  and can be of length $2k$ only when rule~\ref{pop1b} is applied:
  rules~\ref{pop3aiii} and \ref{pop3d} place $p$ in a $(2k-1)$-cycle
  (and we have assumed $k\geq 2$); rule~\ref{pop1a} places it in a
  $(k+1)$-cycle, and all other rules except \ref{pop1b} place it in a
  $(k-1)$-cycle; and, since rule~\ref{pop1b} reduces by 1 the length
  of the cycle containing $p$ and only applies if this length is not
  $k+1$, the length in $\sigma''$ cannot be $k$. Overall, only
  rule~\ref{pop1b} could result in $p$ being in a critical cycle (of
  length $2k$) of $\sigma''$.

  Now, in rule~\ref{pop1b}, the cycle containing $p$ in $\sigma'$
  (hence in $\sigma''$ as well) is obtained by just removing
  $\sigma^{-1}(p)$. For this cycle to become critical in $\sigma''$,
  it would have to be of length $2k+1$ in $\sigma$, with the extra
  condition that $\sigma^{k}(p)$ be smaller than all elements in
  non-critical cycles of $\sigma$ except $\sigma^{[0,k-1]}(p)$; this
  condition reduces exactly to $y=p'$ or $x=p'$, $y=p''$, which are
  excluded from rule~\ref{pop1b}. Thus, even when rule~\ref{pop1b} is
  applied, the cycle containing $p$ is not critical, and we have
  $p=\tilde{p}$.
  \end{proof}

\begin{lemma} \label{lemma:pop_into}
$\pop$ is injective.
\end{lemma}

\begin{proof} 

  Let $(\sigma,i)$ be a pair on which $\pop$ is defined, and $\sigma'
  = \pop(\sigma,i)$. Set $p = p(\sigma)$, $p' = p'(\sigma)$,
  $p''=p''(\sigma)$ and $\gamma = \gamma(\sigma')$. It is clear that
  $\gamma = \sigma(i)$ for $k \geq 2$, and $\gamma=i$ for $k = 1$.

  The first part of our proof shows that no permutation $\sigma'$ can
  be obtained by applying two different rules, \textit{i.e.}, the
  images of the ten rules are pairwise disjoint. For each rule, we
  give a condition that can only be satisfied when applying this one
  rule, and leave it to the reader to check that it is indeed the
  case. Rule~\ref{pop1b} is the most complex, since we have to include
  the condition that rule~\ref{pop2} does not apply.

\begin{enumerate}
\item
\begin{enumerate}
\item $p = \sigma'(\gamma)$;
\item $p \not= \sigma'(\gamma)$ and $\len_{\sigma'}(p) \not= k-1$, and
  we are not in the situation (only posible if $k\geq 2$) where
  $\len_{\sigma'}(p) = 2k-1$ and ($\sigma'^{k}(p) = p'$ or
  $(\sigma'^{k-1}(p),\sigma'^{k}(p))\neq (p',p'')$); these exceptions
  are not produced by this rule as the cycle from which
  rule~\ref{pop1b} removes an element cannot be a critical one;
\end{enumerate} 

\item 
\begin{enumerate}
\item $\len_{\sigma'}(p) = k-1$, $\sigma'(\gamma) = p'$ and
  $\len_{\sigma'}(p'') = k+1$;
\item $\len_{\sigma'}(p) = k-1$, $\len_{\sigma'}(p') = k+1$ and
  $\sigma'(\gamma) \not= p'$, and for $k=1$, this condition should instead be: $p=\sigma'(\gamma)$ and $\len_{\sigma'}(p')=2$;
\end{enumerate} 

\item 
\begin{enumerate}
\item 
\begin{enumerate}
\item $\len_{\sigma'}(p) = k-1$, $\sigma'(\gamma) = p'$ and
  $\len_{\sigma'}(p'') = 1$;
\item $\len_{\sigma'}(p) = k-1$, $\sigma'(\gamma) = p'$, and
  $\len_{\sigma'}(p'') \not\in \{1,k+1\}$;
\item $\len_{\sigma'}(p) = 2k-1$, $\sigma'^{k-1}(p) = p'$ and
  $\sigma'^{k}(p) = p''$;
\end{enumerate}

\item $\len_{\sigma'}(p) = k-1$ and $\len_{\sigma'}(p') = 1$;
\item $\len_{\sigma'}(p) = k-1$ and $\len_{\sigma'}(p') \not\in
  \{1,k+1\}$, and for $k=1$, this condition should instead be:
  $p=\sigma'(\gamma)$ and $\len_{\sigma'}(p')\geq 3$;
\item $\len_{\sigma'}(p) = 2k-1$ and $\sigma'^{k}(p) = p'$.
\end{enumerate}
\end{enumerate}

  All that remains to do to prove the lemma is to prove that each rule
of $\pop$ is one-to-one. Suppose now, two distinct pairs $(\sigma_1,i_1)$ and
  $(\sigma_2,i_2)$ have the same image $\sigma'$ by the same rule of
  $\pop$. Necessarily, we must have
  $i_1=i_2=\sigma'^{-1}(\gamma)$, and by
  Lemma~\ref{lem:pseconde}, $p(\sigma_1)=p(\sigma_2)$.

  Analysing each rule, one may note that all cycles of length $2k$ in
  $\sigma_1$ and $\sigma_2$ with a minimum less than $p(\sigma_1)$ are
  critical and are present in $\sigma'$; these cycles must thus be
  identical in $\sigma_1$ and in $\sigma_2$. Similarly, the $k$-cycles
  of $\sigma$ (other than the one containing $i$) are also present in
  $\pop(\sigma,i)$, so that $\sigma_1$ and $\sigma_2$ have the same
  $k$-cycles.


  Finally, if the permutations $\sigma_1$ and $\sigma_2$ differ on the
  cycle of $p$ (or $p'$, or $p''$, depending on the rule), applying the
  same rule to both $\sigma_1$ and $\sigma_2$ results in different
  permutations; whereas if $\sigma_1$ and $\sigma_2$ differ in another
  place, the permutations obtained using the operator are again
  different as other cycles are not modified.

  Hence $\sigma_1 = \sigma_2$ and $\pop$ is indeed an injective function.
\end{proof}

Lemma~\ref{lemma:pop_onto_k=0}, \ref{lemma:pop_onto_k>=2}, and
\ref{lemma:pop_into} together prove Proposition~\ref{pop-proposition}.

\subsubsection{A bijection for permutations with no $k$-cycles }
\label{bijnokcycles}

Let $\mathcal{D}^k_{n}$ be the set of permutations of $[n]$ with no
$k$-cycles, and $\mathcal{Q}^k_{n}$ the set of quasi-special permutations
of $[n]$ with no $k$-cycles. Recall that we denote $f_k(n,0) =
|\mathcal{D}^k_{n}|$.

Using only the operator just defined, we can easily describe a
bijection $\chi_n$ from $\mathcal{D}^k_{n-1}\times [n]\setminus
\mathcal{SP}^k_{n-1}$ to $\mathcal{D}^k_{n}\setminus
\mathcal{Q}^k_{n}$, where the excluded set $\mathcal{SP}^{k}_{n-1}$ is
the set of pairs $(\sigma,i)$ in which $\sigma$ is special and
$\len_{\sigma}(i) = k-1$. Note that for $\mathcal{SP}^{k}_{n-1}$ to be
nonempty, $n$ must be a multiple of $k$ (the existence of a
$(k-1)$-cycle in a special permutation implies that the size is $-1
\bmod k$).

This bijection $\chi_n$ gives a combinatorial proof of the recurrence
relation for $f_k(n,0)$ given in Proposition~\ref{prop:dist_unchanged}
(which we already proved analytically, in the proof of
Proposition~\ref{optimum-changing-proposition}, for all numbers of
$k$-cycles).
 
This bijection can be seen as a generalization of a previous bijection
$\tau_n$ for derangements (permutations with no fixed points, that is, the case $k=1$) due to Rakotondrajao~\cite{fanja}. The
bijection $\tau_n$ is defined from $\mathcal{D}^1_{n-1} \times [n]
\setminus \{(\Delta^1_{n-1},n)\}$ to $\mathcal{D}^1_{n}$ for odd
$n$, and from $\mathcal{D}^1_{n-1} \times [n]$ to $\mathcal{D}^1_{n}
\setminus \Delta_{n}$ for even $n$, where $\Delta_n$ is the unique
critical derangement of size $n$, for $n$ even: it is the derangement
$(12)(34)\dots(n-1\, n)$.

The bijection of~\cite{fanja} gives a nice combinatorial proof of a
well-known recurrence over the number of derangements, $d_n =
|\mathcal{D}_n|$: $d_n = n d_{n-1} +
(-1)^n$. Proposition~\ref{prop:dist_unchanged} gives a generalization
of this recurrence for any $k \geq 1$; note that by taking $k=1$, we
recover the original recurrence over derangements $f_1(n,0) = n
f_1(n-1,0) + (-1)^{n}$.

Let $\sigma$ be a permutation of size $n-1$ with no $k$-cycles, and
$i\in[n]$, such that $\sigma$ is not special or $\len_{\sigma}(i)
\not= k-1$. We define $\sigma'=\chi_n(\sigma,i)$ as:
\begin{itemize}
\item if $\len_{\sigma}(i) \not= k-1$: $\sigma'=\ins(\sigma,i,n)$;
\item if $\len_{\sigma}(i) = k-1$: $\sigma'=\pop(\ins(\sigma,i,n),i)$.
\end{itemize}

\begin{theorem}
  $\chi_n$ is a bijection from $\mathcal{D}^k_{n-1}\times [n]\setminus
\mathcal{SP}^k_{n-1}$ to $\mathcal{D}^k_{n}\setminus
\mathcal{Q}^k_{n}$.
\end{theorem}

\begin{proof} 
  The first case describes a bijection between the pairs $(\sigma,i)$
  where $i$ is not in a $(k-1)$-cycle and permutations with no
  $k$-cycles where $n$ is not in a $(k+1)$-cycle; the second case is a
  bijection between the remaining pairs and permutations with no
  $k$-cycles where $n$ is in a $(k+1)$-cycle.
  \end{proof}

The link with the case $\ell=0$ of
Proposition~\ref{prop:dist_unchanged} is as follows. When $n$ is not a
multiple of $k$, both $\mathcal{SP}_{n-1}^{k}$ and
$\mathcal{Q}_{n}^{k}$ are empty, and $\chi_n$ constitutes a bijective
proof of the recurrence
\begin{displaymath}
  n f_{k}(n-1,0) = f_k(n,0).
\end{displaymath}
When $n = mk$, one of the two sets is empty, depending on the parity of $m$:
\begin{itemize}
\item For even $m$, $\mathcal{SP}_{n-1}^{k}=\emptyset$: special
  permutations of size $n-1$ with no $k$-cycles must consist of one
  $(k-1)$-cycle and a number of $(2k)$-cycles. In this case, $\chi_n$
  constitutes a bijective proof of the recurrence
  \begin{displaymath}
    n f_{k}(n-1,0) = f_k(n,0) - Q(n,0).
  \end{displaymath}
\item For odd $m$, $\mathcal{Q}_{n}^{k}=\emptyset$: quasi-special
  permutations of size $n$ with no $k$-cycles consist of one
  $(k-1)$-cycle, one $(k+1)$-cycle and a number of $(2k)$-cycles. In
  this case, since each special permutation of size $n-1$ has exactly
  one $(k-1)$-cycle, it appears in exactly $k-1$ pairs in
  $\mathcal{SP}_{n-1}^{k}$, and $\chi_n$ constitutes a bijective proof
  of the recurrence
  \begin{displaymath}
    n f_{k}(n-1,0) - (k-1) S(n-1,0) = f_k(n,0).
  \end{displaymath}
\end{itemize}

\subsection{Some other operators for (special) permutations}

We define here the three remaining operators that our tree construction
relies on. These are necessary to preserve the
\textit{special} subtree, that is, the property that all special
permutations are children of other special permutations in our
generation tree. They all use the largest element of a permutation
$\sigma$ which is not in a $k$-cycle, denoted $\gamma(\sigma)$.

\subsubsection{Decreasing the number of $k$-cycles: the $\hsh$ operator}
\label{hide-and-shift}

In our tree, this $\hsh$ operator serves to define special children
with one fewer $k$-cycles than their parent. Its direct effect on the
cycle type is that two $k$-cycles are replaced by a $(2k)$-cycle; some
care needs to be exercised to ensure that the result is a critical
permutation.

Precisely the operator $\hsh$ is defined over some \textit{acceptable}
pairs $(\sigma, i)$ such that $\sigma$ is a critical permutation over
$\mathcal{S}_{[n]}$, $n$ and $i$ are in two different $k$-cycles,
$\sigma(i)$ is the maximum of its cycle and $\sigma(i) >
\gamma(\sigma)$.

This operator splits each $(2k)$-cycle of $\sigma$ into two
$k$-cycles, one for each critical element of the cycle, then
reconstructs $\sigma'$ by including the cycles containing $n$ and $i$
in the new $(2k)$-cycles set, based on the simple bijection shortly
outlined \S~\ref{critical_permutations}.

Let us define properly this bijection first. For a permutation $\tau$
of size $mk$ constituted only of $k$-cycles, of which $\ell$ are marked
(with $m-\ell$ even), we call $\hbox{join}(\tau)$ the critical
permutation of size $mk$ obtained as follows:
\begin{itemize}\itemsep0em
\item we order the unmarked cycles $C_1$, $C_2$, $\dots$, $C_{m-\ell}$
  of $\tau$ in increasing order of their minimal elements;
\item we join these cycles pairwise by connecting $C_i$ to $C_{i-1}$ for even $i$, \textit{i.e.},
\begin{itemize}\itemsep0em
 \item $\tau_0 = \tau$,
 \item for $j\in [\frac{m-\ell}{2}]$, $\tau_j = \app(\tau_{j-1}, \min(C_{2j}), \min(C_{2j-1}))$,
 \item $\hbox{join}(\tau) = \tau_{(m-\ell)/2}$.
\end{itemize} 
\end{itemize}

Note that this operation defines a bijection from its input set to
critical permutations, as we can easily recover the permutation $\tau$
formed by $m$ cycles of length $k$ from any critical permutation
$\tau'$ of size $mk$ by splitting the $(2k)$-cycles of $\tau'$; the
marked cycles of $\tau$ are exactly the $k$-cycles of $\tau'$.

For $(\sigma,i)$ an acceptable pair for $\hsh$, we define the
permutation $\sigma' = \hsh(\sigma,i)$ as follows:
\begin{enumerate}
\item split the $(2k)$-cycles of $\sigma$ into $k$-cycles,
  \textit{i.e.}, $\sigma_1 = \hbox{join}^{-1}(\sigma)$; unmark the
  cycles of $n$ and $i$ to get $\sigma'_1$;
\item merge again the unmarked $k$-cycles of $\sigma_1'$
  into $(2k)$-cycles, \textit{i.e.}, $\sigma' =
  \hbox{join}(\sigma_1')$.
\end{enumerate}

\begin{proposition} \label{hide-and-shift-proposition} $\hsh$ defines
  a bijection between its acceptable pairs and critical permutations
  where $n$ is in a $(2k)$-cycle. The image has exactly two fewer
  $k$-cycles than the permutation in the pair.
\end{proposition}

\begin{proof} 
  The first step in $\hsh$ is a bijection between acceptable pairs and
  permutations with only $k$-cycles with an even number of unmarked
  cycles, with $n$ belonging to an unmarked cycle; here, $i$ can be
  recovered from the marked permuation by first recovering $\sigma(i)$
  as the maximum element among the unmarked cycles not containing $n$.

  The second step is reduced to $\hbox{join}$, and is also bijective
  from marked permutations with the cycle of $n$ unmarked, and
  critical permutations with $n$ in a $2k$-cycle.
  \end{proof}

\subsubsection{Special children: the $\shift$ operator}
\label{shift-operator}

We now define an operator $\shift$ that bijectively maps some
\textit{valid} non-special permutation $\tau$ to some special
permutation $\sigma'$ on the same set, which contains at least one
$(2k)$-cycle. The conditions on $\tau$ are as follows: 
\begin{itemize}
\item $\len_{\tau}(\gamma(\tau)) = 2k+1$;
\item $\sigma = \hbox{remove}(\tau, \gamma(\tau))$ is a special permutation
  whose special cycle (if it exists) has length other than $k-1$;
\item $i = \tau^{-1}(\gamma(\tau))> \delta(\sigma)$, where $\delta(\sigma)$ is the minimum element of the special cycle of $\sigma$ ($0$ if $|\sigma| = 0 \bmod k$).
\end{itemize}


The purpose of the $\shift$ operator in the construction of our
generation tree is to ensure the heredity condition: that special
permutations only appear as children of special permutations. When
trying to define the $i$-th child of a special permutation $\sigma$,
if $i$ happens to be in a cycle of length $k$ or $2k$ in $\sigma$,
using cycle insertion would result in a permutation that has a
$(k+1)$- or $(2k+1)$-cycle, thus a non special permutation; and in
other situations, cycle insertion may result in special permutations
being children of non special ones, which we want to avoid
completely. The $\shift$ operator is used to ``switch children'' in the
tree in order to maintain the hereditary property.

Informally, the way $\shift^{-1}$ acts is by ``shifting up'' the
sequence of critical elements of a special permutation (obtaining a
non special permutation as the result) in such a way that the
operation can be reversed. It is slightly more natural to define the reverse
operation (from non special to special permutation) as $\shift$, illustrated by Figure~\ref{fig:shift}.

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node (d) at (-2,0) {$\delta$};
\path[->] (d) edge [loop] (d);


\node (a1) at (0,0) {$i$};
\node (g) at (0.66,0.66) {$\gamma$};
\node (b1) at (2,0) {$p_{j+1}$};
\path[->] (a1) edge[bend left] (g);
\path[->] (g) edge[out=0, in=100, thick, blue, dashed] (b1);
\path[->] (b1) edge[out=-100, in=-80, thick, blue, dashed] (a1);

\path[->] (a1) edge [bend right, dotted] (d);
\path[->] (b1) edge [bend right, dotted] (a1);

\node (a2) at (4,0) {$p_{j+2}$};
\node (b2) at (6,0) {$p_{j+3}$};
\path[->] (a2) edge[out=80, in=100, thick, blue, dashed] (b2);
\path[->] (b2) edge[out=-100, in=-80, thick, blue, dashed] (a2);

\path[->] (a2) edge [bend right, dotted] (b1);
\path[->] (b2) edge [bend right, dotted] (a2);

\node (a3) at (8,0) {$p_{\ell-1}$};
\node (a) at (9,0.66) {$a$};
\node (b3) at (10,0) {$p_{\ell}$};
\path[->] (a3) edge[out=80, in=180, thick, blue, dashed] (a);
\path[->] (a) edge[out=0, in=100, thick, blue, dashed] (b3);
\path[->] (b3) edge[out=-100, in=-80, thick, blue, dashed] (a3);

\path[->] (a3) edge [bend right, dotted] (b2);
\path[->] (a) edge [bend left, dotted] (a3);


\path[->] (g) edge [bend left, dotted] (a);

\end{tikzpicture}
\end{center}
\caption{Illustration of the $\shift$ operator when $i$ is a critical element: $i = p_j$. Dotted arrows represent new positions of elements after the application of the operator.}
\label{fig:shift}
\end{figure} 

Let $\tau$ be some valid permutation in the sense described above. In
the following, let $\gamma = \gamma(\tau)$,
$\sigma=\hbox{remove}(\tau,\gamma)$, $i = \tau^{-1}(\gamma)$, $p_j =
p_j(\sigma)$ for $j \in [2m]$ (where $m$ is the number of
$(2k)$-cycles in the special permutation $\sigma$; \textit{i.e.}, the
$p_j$'s are the critical elements of $\sigma$), and $\delta =
\delta(\sigma)$ if $\sigma$ has a special cycle, $\delta = i$
otherwise (that is, if $|\sigma|$ is a multiple of $k$).

The permutation $\sigma' = \shift(\tau,i)$ is defined as follows:
\begin{itemize}
\item If $i$ is not a critical element of $\sigma$, then $\sigma' =
  \ins(\tau, \delta, i)$.
\item If $i = p_j$ for some $j \in [2m]$, then let $\ell$ be the
  smallest integer larger than $j$, such that $p_\ell >
  \min(\sigma^{[k-1]}(p_{\ell-1}))$ (if such an $\ell$ does not exist, we
  set $\ell = 2m+1$). Let
  $a=\min(\sigma^{[k-1]}(p_{\ell-1}))$, and let $\sigma'$ be the
  permutation obtained after these $\ell-j+2$ \textit{insertions}:
\begin{enumerate}
\item $\tau_{\ell-j} = \ins(\tau, a, \gamma)$ and $\tau_{\ell-j-1} = \ins(\tau_{\ell-j}, p_{\ell-1}, a)$;
\item for $h \in \{0, \dots, \ell-j-2\}$, $\tau_h = \ins(\tau_{h+1}, p_{j+h}, p_{j+h+1})$;
\item $\sigma' = \ins(\tau_0, \delta,i)$.
\end{enumerate}
\end{itemize}

In other words, each of the $p_h$ (for $j\leq h\leq \ell-2$) in $\tau$
is replaced by $p_{h+1}$ in the cycle structure of $\tau$,
$p_{\ell-1}$ is replaced by $a$, $a$ is replaced by $\gamma$, and
$i=p_j$ is inserted after $\delta$ (or as a new fixed point if
$\delta=i$, that is, if $\tau$ is of size $1 \bmod k$). Thus,
most cycle lengths are the same in $\sigma'$ and $\tau$; the only ones
that change are the $(2k+1)$-cycle that becomes a $(2k)$-cycle, and
the one cycle of length less than $k$ (the special cycle in $\sigma$)
that increases its size by one. The conditions on the choice of $\ell$
and $a$ ensure that, even though the critical elements of $\sigma$ are
replaced by larger values, $\sigma'$ is indeed a special permutation.

\begin{proposition} \label{shift-proposition} The $\shift$
  operator defines a bijection between its valid inputs $\tau$ and
  special permutations $\sigma'$ on the same set with the same number
  of $k$-cycles, where $\gamma(\sigma')$ is in a $(2k)$-cycle.
\end{proposition}

\begin{proof}
  We have already argued that $\sigma'$ is special. It has the same
  number of $k$-cycles as $\tau$; in fact, it has exactly the same
  $k$-cycles. In the definition, $\gamma$ is placed in a $(2k)$-cycle;
  and, since the elements in $k$-cycles are the same in $\tau$ and in
  $\sigma'$, we have $\gamma(\sigma') = \gamma$. Thus, $\shift(\tau)$
  is of the claimed type. Also, note that the validity conditions on
  $\tau$ (in particular, $i>\delta(\tau)$) ensures that
  $\delta(\sigma')= \delta$.

  To prove that $\shift$ is indeed bijective, we prove that for any
  permutation $\sigma'$ of the claimed type, there is only one
  possible preimage $\tau$, and leave it to the reader to check that
  applying $\shift$ to this $\tau$ does yield $\sigma'$.

  Starting from $\sigma'$, we already know that $\gamma$ can be
  identified as $\gamma(\sigma')$; $i$ can also be identified as
  $\sigma'(\delta(\sigma'))$. The shifted critical elements can then
  be identified (in $\sigma'$) as the critical elements larger than
  $i$, up to and including the critical element $p_j$ such that
  $\gamma \in \sigma'^{[k-1]}(p_j)$ (possibly none, if this $p_j$ is
  smaller than $i$). Then, $\tau$ can be recovered from $\sigma'$ by
  replacing each of these critical elements by the next (the smallest
  one is replaced by $i$, and the last replaces $\gamma$), then
  inserting $\gamma$ after $i$.
  \end{proof}

\subsubsection{Generating quasi-special permutations: the $\shc$ operator}
\label{split-and-shift}

Our last operator $\sigma' = \shc(\tau)$ defines a bijection between
critical permutations $\tau$ with \emph{at least} one $(2k)$-cycle,
and quasi-special permutations $\sigma'$ on the same set. Its direct
effect on the cycle type is that a $(2k)$-cycle is replaced by a
$(k-1)$-cycle and a $(k+1)$-cycle. 

Recall the conditions on a quasi-special permutation $\sigma'$: it has
one $(k+1)$-cycle, one $(k-1)$-cycle, and any number of $k$-cycles and
$(2k)$-cycles; when ignoring the two $(k\pm 1)$-cycles, it is special;
the minimum element $p$ in the $(k-1)$-cycle is larger than all
``critical'' elements; the maximum element $\gamma$ in the
$(k+1)$-cycle is larger than all elements not in $k$-cycles; and
finally, its image $p'=\sigma'(\gamma)$ is larger than $p$.

Now let us start from a critical permutation $\tau$ with at least one
$(2k)$-cycle.

Let us define how the permutation $\sigma'$ is obtained through this
operator. Let $m \geq 1$ be the number of $(2k)$-cycles in $\tau$,
$\gamma = \gamma(\tau)$ and let $p$ be the largest critical element
of $\tau$ such that $\gamma \not\in \tau^{[k-1]}(p)$, \textit{i.e.},
$$p  = \left\{
    \begin{array}{ll}
        p_{2m-1}(\tau) & \mif \gamma \in \tau^{[k-1]}(p_{2m}(\tau)), \\
        p_{2m}(\tau) & \mif \gamma \not\in \tau^{[k-1]}(p_{2m}(\tau)). 
    \end{array}
\right.$$

The permutation $\sigma'$ is obtained through the following process:

\begin{enumerate}
\item $\tau_1$, a permutation of $k$-cycles only with some cycles
  marked, is obtained by splitting all $(2k)$-cycles of $\tau$ at their
  critical elements, that is, $\tau_1 = \hbox{join}^{-1}(\tau)$;
\item mark two more cycles in $\tau_1$ to get $\tau_2$: those
  containing $\gamma$ and $p$ (these two cycles are distinct from the
  definition of $p$);
\item let $\tau_3 = \hbox{join}(\tau_2)$ and $p'= \tau(p)=\tau_3(p)$,
  and set $\sigma' = \hbox{insert}(\tau_3, \gamma, p')$.
\end{enumerate}

\begin{proposition} \label{split-and-shift-proposition}
  $\shc$ defines a bijection between critical
  permutations with at least one $(2k)$-cycle, and quasi-special
  permutations on the same set. Furthermore, the numbers of $k$-cycles
  of $\tau$ and $\shc(\tau)$ are the same.
\end{proposition}

\begin{proof}
  We start by checking that $\sigma'$ defined above is indeed a
  quasi-special permutation. Its cycle structure is appropriate:
  $\tau_3$ has only $k$- and $(2k)$-cycles, and the last insertion
  operation removes an element from one of the $k$-cycles to insert it
  into another one. The fact that, when these two $(k\pm 1)$-cycles
  are ignored, the rest is a critical permutation is guaranteed by the
  $\hbox{join}$ operation. The minimum element $p$ in the
  $(k-1)$-cycle is larger than the largest critical element of
  $\tau_3$. Obviously, the elements not in $k$-cycles are the same in
  $\tau$ and $\sigma'$, so that $\gamma(\sigma')$ is indeed $\gamma$,
  and is in the $(k+1)$-cycle of $\sigma'$ (and $\sigma'$ and $\tau$
  have the same number of $k$-cycles). Finally, $p$ is the minimum of
  its cycle, so that $p'>p$ is also guaranteed. These are exactly the
  conditions of a quasi-special permutation.

  We now check that any quasi-special permutation $\sigma'$ can have
  only one preimage $\tau$, and describe the inverse map; again, we
  leave it to the reader to check that this is indeed a preimage.
  
  Starting from some arbitrary quasi-special permutation $\sigma'$, we
  already know that $\gamma(\tau)$ must be $\gamma(\sigma')$, and can
  also recover $p$ as the minimum of the $(k-1)$-cycle, and $p'$ as
  $\sigma'(\gamma)$. Thus, we can also recover $\tau_3$ by inserting
  $p'$ after $\gamma$ ($\tau_3=\ins(\sigma',\gamma,p')$), then
  $\tau_2=\hbox{join}^{-1}(\tau_3)$, then unmark the cycles containing
  $\gamma$ and $p$ to recover $\tau_1$. Finally, $\tau$ is recovered
  as $\hbox{join}(\tau_1)$.
\end{proof}

\section{Proof of the main theorem}\label{sec:proof}

In this section, we prove the main result of the paper, namely, that
our definition, given in page~\pageref{generation_tree_description}, does define a
uniform generation tree with the desired properties. We first prove
the general case $k\geq 2$; the case $k=1$, together with the
somewhat simplified description of the tree, will be treated later.

\subsection{Proof for $k\geq 2$}

Before going to the proof of the theorem, we make some comments on the
definition, and derive some easy properties. 

First note that the conditions on the use of rules~\ref{rule2} to
\ref{rule6} are mutually exclusive, so that, by the fact that
rule~\ref{rule1} covers exactly the cases not covered by the others,
our description uses exactly one rule for each possible pair
$(\sigma,i)$ (we will check later that the rules are well defined,
\textit{i.e.}, that the operations are always used with proper
arguments).

The condition of
rule~\ref{rule1} was not made explicit in the description,
but it can be expressed easily. The rule is applied when one of the
following statements holds:
\begin{itemize}\itemsep0em
\item $\ell = 2k-1$ and $\zeta$ is not special,
\item $\ell = 2k$, and ($\sigma$ is not special or $i\leq \delta(\sigma)$ or $k \nmid n$),
\item $\ell \not\in \{k-1,2k-1,2k\}$.
\end{itemize}

Now note that in the definition, $\ell$ is always either $0$ or the
length of a cycle in $\sigma$. This makes it clear that
rule~\ref{rule1} is the only one which is applied both to special and
non-special permutations: rules \ref{rule2}, \ref{rule3}, and
\ref{rule4} are used only for non-special permutations (the latter two
imply that $\sigma$ contains a $2k-1$ cycle), and rules \ref{rule5}
and \ref{rule6} for special permutations. Another useful property that
always holds is $\ell+1=\len_{\zeta}(i)$, and $\zeta(i)\geq
\gamma(\zeta)$ (just check the three cases of the definition of
$(\ell,\zeta)$).

For the remainder of the proof, we note $\gamma = \gamma(\sigma)$ and
$\len(j)$ for $\len_\sigma(j)$. 

We now examine each individual rule and, for each one, we do three
things. We check that the permutation $\sigma'$ is well defined
(that is, the corresponding operator can be applied); we
determine whether $\sigma'$ is special; and  we determine the
number $j'$ of $k$-cycles of $\sigma'$, assuming its parent
permutation $\sigma$ has $j$ cycles of length $k$.
\begin{enumerate}[I.]
\item In this rule, either a fixed point is added, or the length of exactly
  one cycle containing $i$ or $\gamma$ increases by one:
\begin{itemize}\itemsep0em
\item if $\len(i) \not= k$, $\zeta$ corresponds to cycle insertion
  after $i$; since the cycle of $i$ cannot be of length $k-1$
  (captured by rules~\ref{rule2} and \ref{rule6}), $\sigma'$ has the
  same number of $k$-cycles as $\sigma$.
\item if $\len(i) = k$ and $i < \gamma$, $\zeta$ corresponds to the
  permutation where $i$ is replaced by $n$, then $i$ is inserted just before
  $\gamma$, thus increasing the length of $\gamma$'s cycle by one in
  $\sigma'$. Since $\len(\gamma) \not= k-1$ (captured again by
  rules~\ref{rule2} and \ref{rule6}), we get $j' = j$ again.
\item if $\len(i) = k$ and $i > \gamma$, $\zeta$ is the permutation
  obtained by replacing $i$ with $n$, then inserting $i$ as a fixed
  point, hence $j' = j$ in this case as well.
\end{itemize}
Moreover if $\sigma$ is
non special, $\sigma'$ is non special as well, because there
are only three ways for this cycle insertion to create a
special permutation, and each one is prevented in this
situation:
\begin{itemize}\itemsep0em
\item inserting into a cycle of length strictly less than $k-1$, but in this case $\sigma$ would have been special;
\item inserting into  a cycle of length $k-1$, but rule~\ref{rule1} does
  not apply in this case;
\item inserting into a cycle of length $2k-1$, but rules~\ref{rule3} and \ref{rule4} exactly capture this case when $\zeta$ is special.
\end{itemize}

If $\sigma$ is special, there is only one possibility for $\sigma'$ to
be special as well, that is, if we insert into the special cycle, and
it happens to be of length strictly less than $k-1$. This corresponds
to the case $\ell < k-1$ (note the case $\ell = k-1$ is captured by
rule~\ref{rule6}). In the only other possible situation where
rule~\ref{rule1} applies to a special permutation (that is, $\ell
= 2k$ but the condition of rule~\ref{rule5} fails), the permutation
$\sigma'$ obtained after rule~\ref{rule1} is not special since it
contains a cycle of length $2k+1$.

\item Since $\sigma$ is not special in this rule, $\zeta$, which is
  obtained from $\sigma$ by inserting some value into a $(k-1)$-cycle,
  is not critical. Second, the newly created $k$-cycle in $\zeta$
  contains $i$ (just check the two first cases of the definition of
  $\zeta$). Third, $\zeta(i)$ is either $n$ or $\gamma(\sigma)$; in
  both cases, $\zeta(i)$ is maximal in its cycle and larger than the
  maximum element of $\zeta$ not in a $k$-cycle. These three
  conditions show that $\pop(\zeta,i)$ is well defined. By the
  properties of $\pop$, $\sigma'$ is not special and $j'=j$.

\item Here $\zeta$ is special, $\gamma(\zeta)$ is either $n$ or
  $\gamma$, and $\gamma(\zeta)$ is in a $(2k)$-cycle of $\zeta$. Hence
  $\zeta$ lies in the image of $\shift$, so that $\sigma'$ is well
  defined and non special, and $j'=j$.

\item In this rule, $\zeta$ is critical and has a $(2k)$-cycle, hence
  the operator $\shc$ is defined on $\zeta$; $\sigma'$ is
  quasi-special (hence not special), and its number of $k$-cycles is
  the same as that of $\zeta$ (and of $\sigma$).

\item 
\begin{enumerate}[(a)]
\item Since $\sigma$ is special, $i > \delta(\sigma)$ and $n$ is not a
  multiple of $k$, so that the special cycle in $\sigma$, whose length
  is $n-1 \bmod k$, has length strictly less than $k-1$. In this case,
  $\zeta(i)=\gamma(\zeta)$ is in a $(2k+1)$-cycle of $\zeta$, and
  removing this value from $\zeta$ yields a special permutation (which
  may be $\sigma$, or another special permutation). Thus $\zeta$
  matches the criteria to apply the $\shift$ operator, and we get a
  special $\sigma'$ with $j'=j$.

\item In this situation, $\sigma'$ is obtained by replacing $i$ by $n$
  (keeping the same number of $k$-cycles) and placing it after
  $\delta(\sigma)$ thus making $\sigma'$ special as well by only
  increasing the length of the special cycle; again, we have $j'=j$.
\end{enumerate}

\item 
\begin{enumerate}[(a)]
\item This rule (identical to rule~\ref{rule1} but kept separate because it
  plays a specific role in our proof) inserts $n$ after $i$, thus
  creating a new $k$-cycle in $\sigma'$. Since other elements are left
  undisturbed, $\sigma'$ is a special permutation with no special
  cycle ($n$ is a multiple of $k$), and $j'=j+1$.

\item In this case, $n$ and $i$ are in different $k$-cycles in
  $\zeta$, $\zeta$ is critical (the $(k-1)$-cycle of $\gamma$ 
  has been replaced by a $k$-cycle), and
  $\zeta(i)$ is larger than any element of $\zeta$ outside
  $k$-cycles; hence $\hsh$ can be applied to $\zeta$. The operator
  produces a critical permutation $\sigma'$ with two $k$-cycles
  fewer than $\zeta$, thus one fewer than $\sigma$ ($j'=j-1$).
\end{enumerate}

\end{enumerate}

This case by case analysis shows that, provided our construction does
define a generation tree (which we shall prove next), the tree
does have all the claimed properties. We summarize them in the
following lemma:
 
\begin{lemma} \label{special_lemma}
The parent of each special permutation is special. The number of $k$-cycles of a permutation is different from that
  of its parent if and only if both are special, and the former is
  critical; the difference in the number of $k$-cycles is $\pm 1$,
  depending on whether rule~\ref{rule6a} or \ref{rule6b} is used to
  obtain the child from the parent.
\end{lemma}

We now turn to proving that our construction is indeed a generation
tree, that is, we have defined, for each $n$, a bijection
between $\mathcal{S}_{[n-1]}\times [n]$ and $\mathcal{S}_{[n]}$. Since
both sets obviously have the same cardinality, all we need to do is
prove that the transformation is one-to-one by exhibiting necessary
conditions on a preimage for each permutation.
 
Let $\sigma'$ be any permutation of size $n$, $\gamma =
\gamma(\sigma')$ and $\tau = \hbox{remove}(\sigma',\gamma)$ the
permutation of size $n-1$ where $\gamma$ has been removed from its
cycle.
 
If $\sigma'$ is special but not critical with $\len_{\sigma'}(\gamma)
= 2k$ and $\len_{\sigma'}(n) = k$: $\sigma'$ is the $i$-th child by
rule~\ref{rule5b} of $\sigma=\hbox{remove}(\ins(\sigma',
\sigma'^{-1}(n),i),n)$, with $i=\sigma'(\delta(\sigma'))$. In $\sigma$
the cycle of $i$ is of length $k$ ($n$ has been removed, $i$ added);
$\sigma$ is special with $|\spec(\sigma)| < k-1$ and
$i > \delta(\sigma)$, thus rule~\ref{rule5b} produces $\sigma'$.
 
We can now note that all other rules describe $\sigma'$ as the image
of $\zeta$ or $(\zeta,i)$ by a bijective transform ($\shift$,
$\shift^{-1}$, $\pop$, $\shc$, $\hsh$, and the identity
restricted to the application cases of rules~\ref{rule1} and
\ref{rule6a}). Thus, if we check that the images of these transforms
are pairwise disjoint, then we know that some $\zeta$ or pair
$(\zeta,i)$ can be recovered from $\sigma'$. In those cases where only
$\zeta$ is recovered this way, we also show how $i$ can be
independently recovered. Then, the proof is completed by checking that
knowing $\zeta$ and $i$ is enough to recover $\sigma$ (that is, the
mapping $(\sigma,i)\mapsto (\zeta,i)$ is injective).

The various images correspond to the following (pairwise incompatible)
descriptions:
 \begin{enumerate}[I.]
\item 
\begin{itemize}
\item $\gamma \not=0$ and $\len_{\sigma'}(\gamma) \not\in \{k+1, 2k, 2k+1\}$, or
\item $\sigma'$ is non-special, $\len_{\sigma'}(\gamma) = 2k$, or
\item $\len_{\sigma'}(\gamma) = 2k+1$ with either $k \mid n$, $\tau$ is non-special, or $\tau$ is special and $\sigma'^{-1}(\gamma) \leq \delta(\tau)$.
\end{itemize}

\item $\sigma'$ is non-special with $\len_{\sigma'}(\gamma) = k+1$, but $\sigma'$ is not quasi-special.

\item $\sigma'$ is a valid input of $\shift$ operator, \textit{i.e.}, $\len_{\sigma'}(\gamma) = 2k+1$, $k \nmid n$, $\tau$ is special and $\sigma'^{-1}(\gamma) > \delta(\tau)$.

\item $\sigma'$ is quasi-special.

\item 
\begin{enumerate}[(a)]
\item $\sigma'$ is special, $\len_{\sigma'}(n) = 2k$, $|\spec(\sigma')|\geq 1$.
\item $\sigma'$ is special, $\len_{\sigma'}(n) = k$, $|\spec(\sigma')|\geq 1$, and $\gamma\notin \spec(\sigma')$.
\end{enumerate}

\item 
\begin{enumerate}[(a)]
\item $\sigma'$ is special, $\len_{\sigma'}(n) = k$, $|\spec(\sigma')|=0$.
\item $\sigma'$ is special, $\len_{\sigma'}(n) = 2k$, $|\spec(\sigma')|=0$.
\end{enumerate}
\end{enumerate}

Let us give a few words of explanation as to why these rules cover all
possible cases. The case $\gamma=0$ is included in condition
\ref{rule5b} (it corresponds to $\sigma'$ having only
$k$-cycles). When $\gamma\neq 0$, we have a disjunction based on the
value of $\len_{\sigma'}(\gamma)$: value $k+1$ is covered exactly by
rules \ref{rule2} and \ref{rule4}; value $2k+1$, by rule \ref{rule3}
and the last case of rule \ref{rule1}; value $2k$ is covered by the
second case of rule \ref{rule1} and rules \ref{rule5} and \ref{rule6};
and all other values by the first case of rule \ref{rule1}.

Since these conditions cover all possibilities, each permutation
$\sigma'$ must fall in one condition, and we can deduce then a rule,
the permutation $\zeta$ and the value of $i = \sigma'^{-1}(\gamma)$
for all cases (except the case of rule~\ref{rule5b} which was
treated above).

Once $i$ and $\zeta$ are known, it is straightforward to reconstruct
the permutation $\sigma$ as $\sigma = \hbox{remove}(\hbox{insert}(\zeta, n, i),n)$.\qed

%\begin{flushright}
%$\square$
%\end{flushright}

\subsection{Generation tree for $k=1$}
\label{k=1} 

When $k$ is $1$ (that is, we are interested in the number of
\emph{fixed points} in permutations), the values $2k$ and $k+1$
coincide, and though the general description of the generation tree is
still valid, some of our arguments for the previous proof are not; and
at the same time, some of the rules in the general description never
apply. We now provide a more compact description of the same generation
tree in this case; the reader should check that what follows is indeed
equivalent, when $k=1$, to what we gave earlier.

\begin{algorithm}[t]
\textsc{Fixed-Point-Generation-Tree}\vspace{0.1cm} \hrule \vspace{0.15cm}

The root of the tree is $(1)$. Let $n \geq 2$, $\sigma \in
\mathcal{S}_{[n-1]}$, $i \in [n]$, $\gamma = \gamma(\sigma)$, $p =
p(\sigma)$, $p' = p'(\sigma)$ and
$\tau=\hbox{insert}(\sigma,n,n)$. The $i$-th child $\sigma'$ of
$\sigma$ is defined as follows:
\begin{enumerate}
\item\label{k1rule1} If $\sigma$ is special and $i = n$: $\sigma' = \tau$.

\item\label{k1rule2} If $\sigma$ is special and $\gamma < i < n$ : $\sigma' = \hbox{insert}(\sigma,i,n)$.

\item\label{k1rule3} If $i \leq \gamma$:
\begin{enumerate}
\item If $i = \sigma(i)$: $\sigma' = \hbox{insert}(\tau, \sigma^{-1}(\gamma), i)$.
\item If $i \not= \sigma(i)$: $\sigma' = \hbox{insert}(\sigma, i, n)$.
\end{enumerate}

\item\label{k1rule4} If $\sigma$ is non-special and $i > \gamma$ :
\begin{enumerate}
\item If $\len_{\sigma}(p) = 2$: $\tau' = \hbox{insert}(\tau, p', \sigma(p))$, and $\sigma' = \hbox{insert}(\tau', i, p)$.
\item If $\len_{\sigma}(p) = 3$ and $\sigma(p) = p'$: $\sigma' = \hbox{insert}(\tau', i, p)$.
\item Otherwise: $\sigma' = \hbox{insert}(\tau', i, \sigma^{-1}(p))$.
\end{enumerate} 
\end{enumerate}
\end{algorithm}

\begin{figure}[t]
\begin{center}

%1
\renewcommand{\thesubfigure}{1}
\subfloat[]{\label{fig:gentree-a}
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node (n) at (0,0) {$n$};	
\path[->] (n) edge[red, thick, loop] (n);
\end{tikzpicture}
}
%2
\hspace{0.5cm}
\renewcommand{\thesubfigure}{2}
\subfloat[]{\label{fig:gentree-b}
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node (i) at (0,0) {$i$};
\node (n) at (2,0) {$n$};	
\path[->] (i) edge[blue, dashed, loop] (i);
\path[->] (i) edge[red, thick, bend left] (n);
\path[->] (n) edge[red, thick, bend left] (i);
\end{tikzpicture}
}
%3.a)
\hspace{0.5cm}
\renewcommand{\thesubfigure}{3.a}
\subfloat[]{\label{fig:gentree-c}
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node (g) at (0,0) {$\sigma^{-1}(\gamma)$};
\node (i) at (1.5,0) {$i$};
\node (sg) at (3,0) {$\gamma$};	
%\path[->] (i) edge[blue, dashed, loop] (i);
\path[->] (g) edge[red, thick] (i);
\path[->] (i) edge[red, thick] (sg);
\path[->] (g) edge[blue, dashed, bend left] (sg);
\end{tikzpicture}
}
%3.b)
\hspace{0.5cm}
\renewcommand{\thesubfigure}{3.b}
\subfloat[]{\label{fig:gentree-d}
\begin{tikzpicture}[scale=0.8, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node (i) at (0,0) {$i$};
\node (n) at (1.5,0) {$n$};
\node (si) at (3,0) {$\sigma(i)$};	
\path[->] (i) edge[red, thick] (n);
\path[->] (n) edge[red, thick] (si);
\path[->] (i) edge[blue, dashed, bend left] (si);
\end{tikzpicture}
}
%4.a)
\renewcommand{\thesubfigure}{4.a}
\subfloat[]{\label{fig:gentree-e}
\hspace{0.1cm}
\begin{tikzpicture}[scale=0.7, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node (pp) at (0,0.6) {$p'$};
\node (sp) at (1.78,0) {$\sigma(p)$};
\node (spp) at (0,-0.6) {$\bullet$};	
\node (p) at (3.57,0) {$p$};
\node (i) at (5.35,0) {$i$};
\path[->] (pp) edge[red, thick, bend left] (sp);
\path[->] (pp) edge[blue, dashed, bend right] (spp);
\path[->] (sp) edge[red, thick, bend left] (spp);
\path[->] (sp) edge[blue, dashed, bend left]  (p);
\path[->] (p) edge[blue, dashed, bend left]  (sp);
\path[->] (p) edge[red, thick, bend left] (i);
\path[->] (i) edge[red, thick, bend left] (p);
\end{tikzpicture}
}
%4.b)
\hspace{0.5cm}
\renewcommand{\thesubfigure}{4.b}
\subfloat[]{\label{fig:gentree-f}
%\hspace{0.28cm}
\begin{tikzpicture}[scale=0.7, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node (pp) at (0,0.6) {$\bullet$};
\node (spp) at (0,-0.6) {$p'$};	
\node (p) at (2.175,0) {$p$};
\node (i) at (4.35,0) {$i$};
\path[->] (pp) edge[red, thick, bend left] (spp);
\path[->] (pp) edge[blue, dashed, bend left] (p);
\path[->] (p) edge[blue, dashed, bend left] (spp);
\path[->] (spp) edge[bend left] (pp);		
\path[->] (p) edge[red, thick, bend left] (i);
\path[->] (i) edge[red, thick, bend left] (p);
\end{tikzpicture}
}
%4.c)
\hspace{0.5cm}
\renewcommand{\thesubfigure}{4.c}
\subfloat[]{\label{fig:gentree-g}
%\hspace{0.2cm}
\begin{tikzpicture}[scale=0.7, every node/.style={transform shape}, every loop/.style={looseness=5}]
\node (p) at (0,0.6) {$\bullet$};
\node (spp) at (0,-0.6) {$p$};	
\node (sp) at (2.175,0) {$\sigma^{-1}(p)$};
\node (i) at (4.35,0) {$i$};
\path[->] (p) edge[red, thick, bend right] (spp);
\path[->] (p) edge[blue, dashed, bend left] (sp);
\path[->] (sp) edge[blue, dashed, bend left] (spp);		
\path[->] (sp) edge[red, thick, bend left] (i);
\path[->] (i) edge[red, thick, bend left] (sp);
\end{tikzpicture}
}
\end{center}
\caption{Illustration of our generation tree for $k=1$ and $\sigma \in \mathcal{S}_{[n-1]}$; dashed edges represent relations in $\sigma$, whereas thick edges represent relations in $\sigma'$, the $i$-th child of $\sigma$ in the tree. Only differences between $\sigma$ and $\sigma'$ are shown.}
\label{fig:gentree1}
\end{figure}

The authors gave in \cite{duchon2014new} a description of a generation tree
with similar properties to the one described here for $k=1$, but it
should be stressed that the tree is not the same. The tree described
here is almost identical to the one appearing in the second author's
Ph.D.  thesis~\cite{duvignau2015}, with slight changes introduced by
taking images in place of preimages in rules $(3.a)$ and $(4.c)$, and
reversing the $3$-cycle of $p$ in rule $(4.b)$.

For the rest of this section, we assume $k=1$. Recall that in this
case, ``special'', ``quasi-special'' and ``critical'' permutations are
the same.  Special permutations of size $n$ are made of an arbitrary
set of $\ell$ fixed points such that $n-\ell$ is even, and the rest of
the permutation forms the unique critical permutation over the
remaining elements, that is, the non-fixed points are paired into
$2$-cycles in increasing order. This makes it easier to see that there
are $2^{n-1}$ special permutations of size $n$; they are in bijection
with subsets of $[n]$ of even size.

Let us reconsider the pair $(\ell, \zeta)$ constructed as the
beginning of the general description. 

We get the following pair by setting $k=1$:
\begin{displaymath}
(\ell,\zeta)  = \left\{
    \begin{array}{ll}
        (\len_{\sigma}(i), \tau) & \mif i=n \text{ or } \sigma(i) \not= i,   \\
        (\len_{\sigma}(\gamma(\sigma)), \ins(\tau, \sigma^{-1}(\gamma(\sigma)), i)) & \mif \sigma(i)=i \mand i < \gamma(\sigma), \\
        (0,\ins(\tau,i,i)) & \mif \gamma(\sigma) < i < n, \\
    \end{array}
  \right.
\end{displaymath}
since $\len_{\sigma}(i)=1$ corresponds to $i$ being a fixed point;
note here $\ell = 0$ happens when $i > \gamma(\sigma)$ (including the
case $i=n$), otherwise we have $\ell \geq 2$.

Now reconsidering the rules of the general description:
rules~\ref{rule3},~\ref{rule4} and \ref{rule5} never apply since $1
\mid n$ and $\ell \not= 1$.

Rule \ref{rule2} applies when $\sigma$ is non-special and $\ell = 0$,
\textit{i.e.}, when $i > \gamma(\sigma)$. In the new description, this
is covered by rule \ref{k1rule4} which is just the description of $\pop$ for
$k=1$.

Rule \ref{rule6a} applies when $\sigma$ is special and
$\len_{\sigma}(i) = 0$, \textit{i.e.}, $i = n$. In this case, it
corresponds to the insertion of $n$ as a fixed point in $\sigma$. This
is covered by rule \ref{k1rule1} in the new description.

Rule \ref{rule6b} applies when $\sigma$ is special, $\gamma(\sigma) <
i < n$ (hence $i$ is a fixed point). In this case, $\hsh$ adds
a new $2$-cycle containing $i$ and $n$, as described in the new rule
\ref{k1rule2}.

The remaining original rule, rule number \ref{rule1}, corresponds to
the remaining cases, that is, $i \leq \gamma(\sigma)$. In this
case, there are two possibilities, either $i$ is not a fixed point in
$\sigma$ (and $n$ is inserted after $i$), or $i$ is a fixed point (and
it is inserted just before $\gamma(\sigma)$). This is covered by the
new rule \ref{k1rule3}.

The remaining constructions are illustrated in Figure~\ref{fig:gentree1}. It should be clear that this construction defines a uniform
generation tree, since from any permutation $\sigma'$ we can identify
which rule has been applied and easily reverse the operation:
\begin{itemize}\itemsep0em
\item rules \ref{k1rule1} and \ref{k1rule2} build special permutations
  with $n$ either as a fixed point or in a $2$-cycle, and
  $i=\sigma'^{-1}(n)$.
\item rule \ref{k1rule3} builds only permutations where
  $\gamma(\sigma')$ is in a $3$-cycle, and we have
  $i=\sigma'^{-1}(\gamma(\sigma'))$.
\item rule \ref{k1rule4} builds non-special permutations where
  $\gamma(\sigma')$ is in a $2$-cycle, and we have
  $i=\gamma(\sigma')$.
\end{itemize}

\section{Probabilistic consequences}
\label{probabilistic}

In this section, we describe a few applications of our tree
construction in a probabilistic setting.

\subsection{Stabilization time for the number of $k$-cycles}

Special permutations make up a vanishing proportion of all
permutations of a given size as size goes to infinity; thus, the
probability that a random descent reaches a changing permutation at a
given level goes to zero.  Thanks to the heredity property of our
generation tree, \emph{almost surely, the number of $k$-cycles in the
  permutations of a random descent is ultimately constant}. More
precisely, almost all descents will reach a non-special permutation,
and all permutations reached from then on will have the same number of
$k$-cycles.

Let $T'$ denote the size of the first non-special permutation in a
random descent; $T'$ is obviously a stopping time\footnote{with
  respect to the natural filtration defined by the sequence of
  permutations.}. If we define time $T$ as the stabilization time for
the number of $k$-cycles, that is, the first index $n$ such that
for all $m\geq n$ we have $c_k(\sigma_m)=c_k(\sigma_n)$, $T$ is not a
stopping time; for instance, in the generation tree for $k=2$ as shown
in Figure~\ref{fig:generation_tree}, all sequences containing the
permutation $(1)(2)$ have $T=1$ (and $T'=2$), but just looking at the
first permutation $(1)$ (which is a special permutation) does not let
one know the value of $T$. But, because each permutation of size a
multiple of $k$ either is non-special or has a different number of
$k$-cycles from its parent, $T'$ cannot be larger than $T+k$. 

For the applications we wish to describe in the rest of this section,
it is useful to compute the expected value of $T'$.

\begin{proposition}\label{prop:stoppingtime}
  Let $T'$ denote the size of the first non-special permutation in a
  random descent into our tree. Then $T'$ has finite expectation
  \begin{displaymath}
    \esp(T') = (1+H_{k-1}) \frac{e^{2/k}+1}{2},
  \end{displaymath}
  where $H_n=\sum_{i=1}^{n} 1/i$ denotes the $n$-th harmonic number.
\end{proposition}

\begin{proof}
  The expected time can be expressed as $\esp(T') = \sum_{n}
  \pr(T'\geq n)$, and the probability that $T'$ is at least $n$ is
  exactly the probability that the permutation reached at level $n-1$
  of the tree is special, \textit{i.e.}, $S(n-1)/(n-1)!$.
  
  Thus, we have
  \begin{align*}
\esp(T') &= \sum_{n\geq 0}  \frac{S(n)}{n!} \\
&= 1+ \sum_{h=1}^{k-1} \frac{S(h)}{h!} + \sum_{m=1}^\infty \left( \frac{S(mk)}{(mk)!} +  \sum_{h=1}^{k-1} \frac{S(mk+h)}{(mk+h)!} \right). 
\end{align*}

  Using the counting formulae of Proposition~\ref{prop:countingspecials}, we get
\begin{align*}
\esp(T') &= 1+ \sum_{h=1}^{k-1} \frac{(h-1)!}{h!} + \sum_{m=1}^\infty \left(\frac{1}{2} \frac{(2/k)^{m}}{m!} +  \sum_{h=1}^{k-1} \frac{1}{2h} \frac{(2/k)^{m}}{m!} \right) \\
&= 1+H_{k-1} + \frac{1+ H_{k-1}}{2} \sum_{m=1}^\infty \frac{(2/k)^m}{m!} \\
&= \left( 1+H_{k-1} \right) \frac{e^{2/k}+1}{2}.   \qedhere                                      
\end{align*}  
%\begin{align*}
%\esp(T') &= \sum_{n\geq 0} \frac{S(n)}{n!} = 1+ \sum_{h=1}^{k-1} \frac{S(h)}{h!} + \sum_{m=1}^\infty \left( \frac{S(mk)}{(mk)!} +  \sum_{h=1}^{k-1} \frac{S(mk+h)}{(mk+h)!} \right) \\
%&= 1+ \sum_{h=1}^{k-1} \frac{(h-1)!}{h!} + \sum_{m=1}^\infty \left(\frac{1}{2} \frac{(2/k)^{m}}{m!} +  \sum_{h=1}^{k-1} \frac{1}{2h} \frac{(2/k)^{m}}{m!} \right) \\
%&= 1+H_{k-1} + \frac{1+ H_{k-1}}{2} \sum_{m=1}^\infty \frac{(2/k)^m}{m!} = \left( 1+H_{k-1} \right) \frac{e^{2/k}+1}{2}. 
%\end{align*}
\end{proof}
%Hence we have indeed $\esp(T') = (1+H_{k-1}) \frac{e^{2/k}+1}{2}$.

\subsection{Uniform random generation of permutations with a fixed number
  of $k$-cycles}
 \label{randomk}

In this section, we show how our generation tree can be used for
random generation.

The fact that non-special permutations have the same number of
$k$-cycles as each of their children, and by induction as any of their
descendants, allows us to design algorithms that make use of this
property for sampling a uniform permutation conditioned on having a
prescribed number of $k$-cycles. The algorithm we get is efficient
both in time/space complexity and in \emph{randomness} complexity. The
randomness cost can be estimated by two different parameters, and we
analyze our sampling algorithm for both: the number of random
bits used by the algorithm (which we call the \emph{random bit}
complexity), and the number of calls to a unit-cost
$\texttt{Random}(m)$ primitive that returns a uniform number in $[m]$
(which we call the \emph{random integer} complexity; all calls to such
a \texttt{Random} primitive would be with parameters bounded by $n$).

In the discussion that follows, we consider both $k$ and $\ell$ to be
constants (the asymptotics is only for large $n$), though they may be
large constants.

A very basic rejection algorithm to sample uniformly a
$(n,\ell)$-permutation, that is a permutation of size $n$ with exactely $\ell$ $k$-cycles, is to generate uniform permutations of size
$n$, until one is obtained that has exactly $\ell$ cycles of length
$k$. Since the probability of success $f_k(n,\ell) / n!$ converges
(quickly, see~\cite{arratia1992cycle}) to $e^{-1/k}/(k^\ell \ell!)$ in
the large $n$ limit, this simple \emph{rejection method} needs to
generate, in expectation, $e^{1/k} k^\ell \ell!+O(1/n!)$ permutations
of size $n$. Thus its expected random integer complexity is $e^{1/k}
k^\ell \ell! n + O(1/(n-1)!)$ when using standard methods for
generating permutations, such as the Fisher-Yates shuffle, also known
as Knuth shuffle (see~\cite{fisher_yates, durstenfeld, knuth}).

If $\ell$ is large, this cost is impractical. There is an easy trick
to avoid this large multiplicative constant in front of $n$: we can
generate separately the $k$-cycles and the rest of the permutation. To
do so, we can sample $\ell k$ elements from $[n]$ by $\ell k$
successive calls to a uniform sampler, the $i$-th call using
$\texttt{Random}(n-i+1)$ in order to get one of the remaining elements
-- this can be done easily in $\mathcal{O}(1)$ per generation by just
swapping some elements in a table, in a Fisher-Yates fashion. At the
same time as selecting these elements, we can build $k$-cycles in the
same order as their selection: each $(\ell k, \ell)$-permutation of
the selected elements is equally likely this way. Then the second part
asks for a uniform $(n-\ell k, 0)$-permutation of the remaining
elements. In order to generate such a permutation of size $n-\ell k$,
a naive rejection algorithm in the same spirit as in the previous
paragraph needs in average $e^{1/k} (n-\ell k) + O(1/(n-\ell k-1)!)$ calls to
a random sampler. Hence this method yields an algorithm with random
integer complexity $e^{1/k} n + \ell k (1-e^{1/k})+ o(1)$.

For any value of $n$, $\ell$ and $k$ the above method is satisfactory
in a practical sense. However, we can improve the multiplicative
constant and obtain, thanks to our generation tree, a new random
generation algorithm with random integer cost $n + \mathcal{O}(1)$
calls to $\texttt{Random}()$. This algorithm is a rejection algorithm
heavily based on our generation tree.

Since $e^{1/k}$ is rather close to $1$ for values of $k$ larger than a
few units, the most interesting case in such a generation process
remains the uniform generation of derangements ($k=1$, $\ell=0$).

In the literature, \cite{conrado} proposes an equivalent of the
Fisher-Yates shuffle for derangements, resulting in a bounded time
algorithm with an expected random integer complexity of $2n +
o(n)$. In~\cite{arndt}, experimental studies are performed comparing
this method and the anticipated rejection method, resulting in
comparable results; an extension to permutations having only cycles of
length at least $m \geq 3$ is also
given. In~\cite{duchon2014new,duvignau2015}, a generator using
$n+\mathcal{O}(1)$ calls is given, matching the cost of an algorithm
sketched at the end of \cite{desar}, which is based on Lehmer encoding
and a specific bijection of permutations, and not directly on
derangements.

We propose the following natural algorithm
\textsc{UniformPerm0}(n,k) in order to sample uniformly a
permutation of size $n$ with \emph{no} $k$-cycles:
\begin{enumerate}
\item Perform a random descent in our generation tree until reaching a
  non-special permutation $\sigma$ or level $n$, whichever comes
  first.
\item If the reached permutation has no $k$-cycles, continue the descent until reaching level $n$ and return the permutation obtained at the end; otherwise, repeat Step 1.
\end{enumerate}

\begin{proposition}\label{prop:unifperm}
  \textsc{UniformPerm0}(n,k) returns a uniform permutation of size $n$
  that does not have any $k$-cycles; it has expected random integer complexity
  $n+\mathcal{O}(1)$.
\end{proposition}

\begin{proof} 
  The algorithm works as an anticipated rejection method: it is
  equivalent to performing a uniform sampling of a permutation of size
  $n$, and as soon as the generated permutation is known to have
  cycles of length $k$, the algorithm aborts and retries; otherwise it
  returns the sampled permutation. Thus the returned permutations are
  uniform $(n,0)$-permutations. The properties of the generation tree
  are used to make anticipated rejection efficient.

  Let $A=A_n$ be the random variable describing the number of calls to
  \texttt{Random()} used by the algorithm on input $n$; recall that
  $k$ is assumed to be a constant. We separate the cost into two
  contributions corresponding to the two phases of the algorithm, such
  that $A = C_1 + C_2$, where $C_1$ counts the calls to
  \texttt{Random()} made (including rejections) until a
  $(n,0)$-permutation is obtained that either is non-special, or has
  size $n$; and $C_2$ counts only calls made by step 2 of the
  algorithm.
  

  We have $\esp(C_1) = \esp(C)/\alpha$, where $C$ is the number of calls
  during one trial of the first phase, and $\alpha = q_k(n,0)$ the probability of
  success for each trial. 
  
  From the exponential generating function $G_k(x,0) =
  \exp(-x^k/k)/(1-x)$ counting the number of $(n,0)$-permutations (see
  proof of Proposition~\ref{prop:dist_unchanged}), we get $q_k(n,0)$
  as the coefficient of $x^n$ in $G_k(x,0)$:
$$q_k(n,0) = [x^n] \left( \sum_{j \geq 0} x^j \right) \left( \sum_{j \geq 0} \frac{(-1)^j x^{jk}}{k^j j!}\right) = \sum_{j = 0}^{\lfloor n/k \rfloor} \frac{(-1)^j}{k^j j!},$$ thus $$\alpha = \sum_{j=0}^{\lfloor
    n/k \rfloor} \frac{(-1)^j}{k^j j!} = e^{-1/k} - \sum_{j=\lfloor
    n/k \rfloor + 1}^{\infty} \frac{(-1)^j}{k^j j!}.$$ 
    
    The last term is an
  alternating series, so that the limit differs from $e^{-1/k}$ by at
  most the first term; independently of the parity of $\lfloor n/k
  \rfloor$, we get the valid bounds
 \begin{displaymath}
e^{-1/k} - \frac{1}{k^{1+\lfloor n/k\rfloor}(\lfloor n/k \rfloor+ 1)!} \;\leq\; \alpha \;\leq\; e^{-1/k} + \frac{1}{k^{1+\lfloor n/k\rfloor}(\lfloor n/k \rfloor+ 1)!},
\end{displaymath}
  so we have $1/\alpha = e^{1/k} + \mathcal{O}(1/(\lfloor n/k \rfloor+ 1)!)$.
%%% and $|1/\alpha - e^{1/k}| \leq 1$.

  We now compute an upper bound on $\esp(C)$. The number of calls to
  our random integer generator is exactly one less than the level at
  which the descent ends; that is, $\esp(C)=\esp(\min(n,T'))-1\leq
  \esp(T')-1$.

Finally, $C_2$ is at most $n-2$, since the smallest non-special
permutations are of size $2$. This carries over to $\esp(C_2) \leq
n-2$. By linearity of expectation, we obtain a bound on the expected
total number $\esp(A) = \esp(C_1) + \esp(C_2)$ of calls, \[\esp(A) \leq
n-2 + e^{1/k}\left( H_{k-1} + \frac{1+ H_{k-1}}{2} \left( e^{2/k}-1
  \right) \right)+ \mathcal{O}((n/k)!^{-1}).\qedhere\]
\end{proof}

To estimate the random bit complexity, we assume that the primitive
\texttt{Random(j)} is optimal in the sense described in
\cite{knuth_yao}. This implies that, for any $j>2$, the expected
random bit cost of the call \texttt{Random(j)} is at most
$2+\log_2(j)$. This is bounded above by $2+\log_2(n)$, since $j$ is
never larger than $n$. Multiplying by the previous bound for the
expected random integer complexity, we get an upper bound of
$n\log_2(n)+\mathcal{O}(n)$. This is asymptotically tight because the
expected number of random bits cannot be less than $\log_2(f_k(n,0))$,
which is also $n\log_2(n)+\mathcal{O}(n)$.

\begin{proposition}
  The expected random bit complexity of algorithm \textsc{UniformPerm0}(n,k) is
  $n\log_2(n)+\mathcal{O}(n)$.
\end{proposition}

Finally, from the discussion of the beginning of this section, we
deduce directly the following corollary:

\begin{corollary}
  It is possible to generate a uniform random permutation of size $n$
  with exactly $\ell$ $k$-cycles with expected random integer
  complexity $n+\mathcal{O}(1)$.
\end{corollary}

 \subsection{Sampling Poisson random variates}
 \label{poisson}

 A second consequence of our generation tree is a combinatorial
 algorithm to sample from the Poisson distribution with parameter
 $1/k$, that is, obtaining a random variate that takes each
 integer value $\ell\geq 0$ with probability $1 / (e^{1/k} k^\ell
 \ell!)$.

 Many sampling methods already exist for the Poisson distribution
 (see~\cite{Dev86} for most of them). These algorithms are efficient
 but use rational and irrational numbers. By contrast, our algorithm
 is purely combinatorial in nature and only uses small integer
 numbers.

\begin{algorithm}[!t]
\caption{\textsc{Poisson1}}
\label{poisson}
\begin{algorithmic}
\State $n \gets 1, \, g \gets 0, \, k \gets 1$
\Loop
	\State $i \gets \textbf{Random}(n+1)$
	\If{$i=n+1$} \State $k \gets k+1$
	\ElsIf{$i>g$} \State $k \gets k-1, \, g \gets n+1$
	\Else \State \Return $k$
	\EndIf
	\State $n \gets n+1$
\EndLoop
\end{algorithmic}
\end{algorithm}

Our algorithm \textsc{Poisson-$1/k$} is pretty simple once the
generation tree is known: perform a random descent in the generation
tree (by which we mean, start from the root, and at each level pick a
uniform random child of the current node), until a non-special
permutation is reached; then output its number of fixed points.

We have already computed the expected random integer complexity of
this algorithm in the proof of Proposition~\ref{prop:stoppingtime}, as
\begin{displaymath}
\esp(T'-1)= H_{k-1} \frac{e^{2/k}+1}{2} + \frac{e^{2/k}-1}{2}.
\end{displaymath}

As stated in the introduction, since we know that the limit
distribution of the number of $k$-cycles of uniform permutations of
size $n$ is the Poisson distribution with expectation $1/k$, we deduce
the correctness of the algorithm from the fact that it returns
precisely the limit of such a vector $(\sigma_n)_{n\geq 1}$ -- recall
that after reaching a non special permutation, further descents in the
tree yield permutations with the same number of $k$-cycles.

For the case $k = 1$, special permutations have a particularly simple
form, and the algorithm \textsc{Poisson1} is even simpler. It only
needs to keep track of $3$ integers representing the size of the
permutation, the largest non-fixed point and the current number of
fixed points.

From a Poisson distributed variable $X_1$ of expectation $1$, it is
easy to deduce another random variable $X_{1/k}$, which follows this time the Poisson distribution with mean $1/k$: $X_{1/k}$ is the number of heads
in $X_1$ biased coin flips with parameter $1/k$. For any $k$, the
number of times the \texttt{Random()} primitive has to be used in such
an algorithm is given by $1+(e^2-1)/2 = (e^2+1)/2 \approx 4.20$;
comparing this with the expected random integer complexity of
\textsc{Poisson-$1/k$} shows that the latter is more
efficient for $k\leq 32$.

We now turn to a short analysis of the random bit complexity of our
\textsc{Poisson1} algorithm.

\begin{proposition} The  \textsc{Poisson1} algorithm uses, in
  expectation, between $6.89$ and $6.9$ random bits, assuming the
  \texttt{Random} primitive is optimal in terms of random bits used.
\end{proposition}

\begin{proof}
  Let $B$ be the number of random bits used by the algorithm and $B_n$
  the number of random bits (if any) consumed at level $n$ of the
  tree, so that $C = \sum_{n=2}^{\infty} C_n$.

We have $\esp(B_n) = \frac{2^{n-2}}{(n-1)!} \esp(U_n)$, where $U_n$ is
the number of bits used by an optimal uniform sampler
$\texttt{Random}(n)$ in the sense of~\cite{knuth_yao}; the
$2^{n-2}/(n-1)!$ factor is simply the probability of reaching level
$n$ of the tree. The inequality $\log_2(n) \leq \esp(U_n) \leq
\log_2(n)+2$ is valid for all $n$, but using it blindly to bound the
complexity of our algorithm gives an upper bound of $9.59$,
significantly more bits than we want.

Instead, we compute exactly $D_m = \sum_{n=2}^{m}
\frac{2^{n-2}}{(n-1)!}  \esp(U_n)$ for some constant $m$. The lower
and upper bounds for $\esp(C)$ then become $D_m + \sum_{n\geq m}
\frac{2^{n-1}\log_2(n+1)}{n!}$ and $D_m+ \sum_{n\geq m}
\frac{2^{n-1}(2+\log_2(n+1))}{n!}$, respectively. For fixed $n$,
$\esp(U_n)$ can be simply obtained from the binary expansion of $1/n$,
as described in~\cite{knuth_yao}.

To obtain the estimates given in the proposition, we computed the
above bounds for $m=10$. Values of $\esp(U_n)$ for $n$ from $2$ to
$10$ are $1,8/3,2,18/5,11/3,$ $24/7,3,14/3,23/5$, yielding
$D_{10}=\frac{97771}{14175}\simeq 6.897$. This is a lower bound for
the expected random bit complexity.

For the upper bound, we need an upper bound for $$M=\sum_{n\geq
  10}\frac{2^{n-1}(2+\log_2(n+1))}{n!}.$$ 
  
  We only use the inequality $2+\log_2(n+1)\leq n$ (which is certainly valid for $n\geq 10$); we get
\begin{displaymath}
  M \leq \sum_{n\geq 9} \frac{2^n}{n!} = e^2 - \sum_{n=0}^8 \frac{2^n}{n!} = e^2 - \frac{2327}{315} \simeq 0.00175.
\end{displaymath}

Indeed, both the lower and upper bound are between $6.89$ and $6.9$.
\end{proof}

\begin{remark}
  In algorithm \textsc{Poisson1}, we can replace the call to the random
  sampler in the algorithm by an optimal ternary generator choosing
  the first option with probability $1/(n+1)$, the second one with
  probability $(n-g)/(n+1)$ and the third one with probability
  $g/(n+1)$. In such a situation, analogous bound computations as in
  the previous proof gives an expected bit complexity of $5.12$.
\end{remark}

Our Poisson algorithm is not an optimal algorithm regarding its bit consumption;
again applying the results in~\cite{knuth_yao}, an optimal algorithm
would use, in expectation, fewer than $2+E$ bits, where $E=1+e^{-1}\sum_{j\geq
  0} \log_2(j)/j!\simeq 1.89$ is the binary entropy of the Poisson
distribution; note, however, that such an algorithm would need the
binary expansions of all individual probabilities of the Poisson
distribution, $p_{j}=1/(j!e)$.

Once again, computing $\sum_{i = 0}^{B} i/2^i \sum_{j=0}^{A}
[p_j]_{i}$ for $[p_j]_{i}$ the $i$-th bit of the binary expansion of
probability $p_j$, and some constants $A$ and $B$, gives a lower bound
on the random bit complexity of an optimal algorithm for the Poisson
distribution. For $A=10$ and $B=32$, we get a lower bound of $3.66$,
indicating our combinatorial algorithm is within a factor $2$ of the
optimal cost.

\section{Concluding remarks}

We have described a new uniform generation tree for permutations, with
the property of preserving as much as possible the number of
$k$-cycles between a permutation and its parent. This generation tree
gives us a new and efficient algorithm for the uniform random
generation of permutations with exactly $\ell$ $k$-cycles,
as well as a new method for sampling from the Poisson distribution
with parameter $1/k$, both for any $k \geq 1$. Both algorithms use
only small integer numbers.

We believe other applications to random generation can be devised for
the generation tree, such as sampling permutations having some
predefined condition on their number of $k$-cycles: for example, an even
number. We expect our tree to make many rejection-based algorithms for
this kind of task particularly efficient. 

More generally, we are eager
to see if such a construction can be adapted to other families of
combinatorial objects, keeping in mind the potential gain for new
efficient generation algorithms for such objects. Indeed, the
generation process described in Section~\ref{randomk}
replaces a multiplicative constant by an additive constant, in the
expected cost of the algorithm. For combinatorial objects
representing an exponentially (in $k$) small part
of an easy to sample set, using an adaptation of our method may lead
to still generate those objects in time proportional to $n +
\mathcal{O}(1)$ instead of the exponential multiplicative cost induced
by a classic rejection algorithm.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection*{Acknowledgements}
%Thanks to Professor Querty for suggesting the proof of
%Lemma~\ref{lem:Technical}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{99}

\bibitem{arndt}
J\"org Arndt.
\newblock {\em Generating Random Permutations}.
\newblock PhD thesis, Australian National University, 2009.

\bibitem{arratia1992cycle}
Richard Arratia and Simon Tavare.
\newblock The cycle structure of random permutations.
\newblock {\em The Annals of Probability}, pages 1567--1591, 1992.

\bibitem{desar}
Jacques D\'esarm\'enien.
\newblock Une autre interpr\'etation du nombre de d\'erangements.
\newblock In {\em Actes 8e S\'em. Lothar. Combin.}, pages 11--16. IRMA,
  Strasbourg, 1984.

\bibitem{Dev86}
Luc Devroye.
\newblock {\em Non-Uniform Random Variate Generation}.
\newblock Springer Verlag, 1986.

\bibitem{diaconis1994eigenvalues}
Persi Diaconis and Mehrdad Shahshahani.
\newblock On the eigenvalues of random matrices.
\newblock {\em Journal of Applied Probability}, pages 49--62, 1994.

\bibitem{duchon2014new}
Philippe Duchon and Romaric Duvignau.
\newblock A new generation tree for permutations, preserving the number of
  fixed points.
\newblock In {\em 26th International Conference on Formal Power Series and
  Algebraic Combinatorics (FPSAC 2014)}, pages 679--690. DMTCS Proceedings,
  2014.

\bibitem{durstenfeld}
Richard Durstenfeld.
\newblock Algorithm 235: Random permutation.
\newblock {\em Commun. ACM}, 7(7):420, July 1964.

\bibitem{duvignau2015}
Romaric Duvignau.
\newblock {\em Maintenance et simulation de graphes al{\'e}atoires dynamiques (Maintenance and simulation of dynamic random graphs)}.
\newblock PhD thesis, University of Bordeaux, 2015.

\bibitem{fisher_yates}
R.~A. Fisher and F.~Yates.
\newblock {\em {Statistical Tables for Biological, Agricultural and Medical
  Research}}.
\newblock Edinburgh: Oliver and Boyd, 1938.

\bibitem{knuth}
Donald~E. Knuth.
\newblock {\em The Art of Computer Programming, Volume 2 (3rd Ed.):
  Seminumerical Algorithms}.
\newblock Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1997.

\bibitem{knuth_yao}
Donald~E Knuth and Andrew~C Yao.
\newblock The complexity of nonuniform random number generation.
\newblock In {\em Proceedings of Symposium on Algorithms and Complexity}, pages
  357--428. Academic Press, New York, 1976.

\bibitem{conrado}
Conrado Mart\'{\i}nez, Alois Panholzer, and Helmut Prodinger.
\newblock Generating random derangements.
\newblock In {\em I. Munro, R. Sedgewick, W. Szpankowski, and D. Wagner,
  editors, Proc. of the 10th ACM-SIAM Workshop on Algorithm Engineering and
  Experiments (ALENEX) and the 5th ACM-SIAM Workshop on Analytic Algorithmics
  and Combinatorics (ANALCO)}, pages 234--240. SIAM, 2008.

\bibitem{fanja}
Fanja Rakotondrajao.
\newblock k-fixed-points-permutations.
\newblock In {\em INTEGERS: Electronic Journal of Combinatorial Number Theory},
  volume~7, 2007.
\newblock A36.

\bibitem{wilfgf2}
Herbert~S Wilf.
\newblock {\em generatingfunctionology}.
\newblock Elsevier, 2013.

\end{thebibliography}

\end{document}