\documentclass[11pt]{amsart}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{amsfonts,amsmath,amssymb}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem*{note}{Remark}
\newtheorem{require}[theorem]{Requirement}
\newtheorem{example}[theorem]{Example}

\usepackage{url}
\usepackage{color}
%\newcommand{\blue}[1]{{\leavevmode#1}}

%\newcommand{\qed}{\mbox{$\Diamond$}\vspace{\baselineskip}}
\def\sym{\operatorname{sym}}
%\newcommand{\sym}{\hbox{sym}}
%\newenvironment{proof}{\noindent{\bf Proof:}}{\qed}
\newcommand{\Var}{\operatorname{\mathbb{V}}}
\newcommand{\E}{\operatorname{\mathbb{E}}}
\def\ds{\displaystyle}
%\usepackage{lineno}
%\linenumbers*[1]
\def\bi{\bigskip\noindent}
\def\si{\smallskip\noindent}
\def\pr{\text{P}}
\def\ex{\text{E}}
\def\la{\lambda}
\def\eps{\varepsilon}
\def\wh{\widehat}
\def\cal{\mathcal}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\Pr{\operatorname{\mathbb{P}}}

\date{}


\begin{document}

%\begin{frontmatter}
\title[Product of cycles]{On the cycle structure of the product of random maximal cycles}

\author{Mikl\'os B\'ona}
\address{Department of Mathematics, University of Florida, $358$ Little Hall, PO Box $118105$,
Gainesville, FL, $32611-8105$ (USA)}
\email{bona@ufl.edu}
\author{Boris Pittel}
\address{Department of Mathematics, The Ohio State University, $231$ West $18$-th Avenue, Columbus, Ohio $43210-1175$ (USA)}
\email{bgp@math.ohio-state.edu}

\keywords
{cycles, permutations, product, distribution, Fourier transform}


\subjclass[2010] {05A05, 05A15, 05A16, 05D40, 05E10}

\begin{abstract} The subject of this paper is the cycle structure of the random permutation $\sigma$ of $[N]$, which is the product of $k$ independent random cycles of maximal length $N$.  We use the character-based Fourier transform to study the counts of cycles of $\sigma$ by length and also the distribution of the elements of the subset $[\ell]$ among the cycles of $\sigma$. 
 \end{abstract}

\maketitle

\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 80 \rms (2019), Article~B80b\hfill}
\def\thepage{}

\section{Introduction}
Enumeration of  permutations of a set $[N]=\{1,2,\dots,N\}$ according to the numbers of cycles of various lengths has a long and glorious history. The plentiful results are not infrequently cast in the
probabilistic light, if the assumption is made that a permutation is chosen {\em uniformly at random }
among all $N!$ permutations. The techniques vary widely, from bijective methods to
multivariate generating functions to functional limit theorems, allowing to find solutions, exact or
asymptotic, of rather delicate, enumerative-probabilistic, problems. More recently there has been
a growing interest in the probabilities regarding distribution of the elements of a subset $S\subseteq [N]$ 
among the cycles of the random permutation. For instance, we can determine the probability that each of the entries in $S$ will be in  a different cycle, or that all entries of $S$ will  be in the same cycle, or that each cycle of $p$ 
will contain at least one entry of $S$. See \cite{Lovasz} for results of this kind. 

The classic, and more recent,  problems become much more difficult if, instead of a uniformly random permutation, we consider a random permutation which is a {\em product} of  random {\em maximal} cycles. That is, our sample space is now that of all ordered $k$-tuples $(p_1,p_2,\dots ,p_k)$, where all $p_i$ are maximal cycles of length $N$. One can investigate the random permutation
$\sigma:=p_1\cdots p_k$ under the assumption that $p_1,\dots,p_k$ are  maximal cycles,
chosen uniformly at random, and independently of each other, from all $(N-1)!$ such cycles. The problem to determine 
the probability that the permutation $\sigma$ has prescribed counts of cycles of all lengths is equivalent to a special case of
the problem to count all factorizations of $\sigma$ belonging to a given conjugacy class into the {product} of $k$ permutations each belonging to its own conjugacy class. There is a long, glorious history of research in this
classic area, starting with Hurwitz \cite{Hur} {who was motivated by deep connections between factorizations and topological equivalence classes of functions on associated Riemann surfaces; see \cite{LandoZvonkin} for the history 
of the subject, and a relatively recent paper by Poulalhon and Schaeffer \cite{PouSch}}.  Still when counting 
the products $\sigma$ that do not fill a single conjugacy class, or few such classes, that usage of the existing results on factorization is quite problematic.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL MIKL\'OS B\'ONA AND BORIS PITTEL}{\SMALL PRODUCT OF CYCLES}

 \subsection{Motivation and recent results}
Among the sources of our inspiration are Zagier's classic formula for the distribution of the number of cycles in $\sigma$ for $k=2$ (see \cite{Zagier}), and the more recent results by Stanley  \cite{Stanley2} and by Bernardi et al.\ \cite{Bernardi}, again for $k=2$.  For the  problem in \cite{Zagier}, the admissible products of cycles form a union of too many conjugacy classes for invoking the factorization results. 
In \cite{Bernardi},  a formula is proved for the probability that 
$\sigma$, the product of two maximal cycles, separates the {\em given disjoint} subsets of $[N]$, i.e., no two 
of those subsets are represented in the same cycle of $\sigma$. For this problem the {labels of elements in $[N]$ are at the core
of counting, and the set of admissible products is a union of {\it subsets of\/} conjugacy classes. }
%and In particular,
%the probability that $\sigma$ separates the entries $1,\dots,\ell$ is equal to $1/\ell!$ if $N-\ell$ is odd. In other words, in this aspect, the product of two independent maximal cycles behaves as the uniformly random permutation!

 Beside their intrinsic interest, solutions of the mentioned problems  may lead to surprising applications. 
In \cite{bona-flynn}, B\'ona and Flynn used a result of Stanley \cite{Stanley2} concerning the special case $S=\{1,2\}$ and $k=2$
to prove an exact formula for the average number of block interchanges needed to sort a permutation, a problem motivated
by genome sorting. Equally interesting are the methods that can be used, as they come from a wide array of areas in mathematics, such as character theory, multivariate Gaussian integration,  bijective combinatorics and the summation techniques for hypergeometric sums.

\subsection{Overview: methods and results} 

In $1986$ Harer and Zagier \cite{HarerZagier} discovered a remarkable formula for the bivariate generating 
function of the number of cycles in the product of a maximal cycle and {a random, fixed-point
free, involution of $[2n]$}, thus solving a difficult problem of enumerating the chord diagrams by the
genus of an associated surface. The proof was based on evaluation of {multidimensional} 
Gaussian integrals. Soon after, Jackson \cite{Jackson}, and later Zagier \cite{Zagier}, found
alternative proofs that used characters of the symmetric group $S_{2n}$. Recently, the second
author found a different, character-based proof in \cite{Pittel}. Its core {consists of computing }and {\it marginally}
inverting the Fourier transform of the underlying probability measure on $S_{2n}$. In the present paper, we use the techniques in \cite{Pittel}, see also an earlier paper by Chmutov
and Pittel \cite{Chmutov}, to investigate the product of $k$ maximal cycles in $S_N$. In order to make the discussion reasonably self-contained, we will introduce the necessary definitions and facts from \cite{Pittel} in Section~\ref{Prelim}. 

We begin Section~\ref{cycles} with Lemma~\ref{cycledist} that  states an explicit formula for the probability distribution of the
number of cycles in $\sigma$, the product of $k$ random, independent, maximal
cycles in $S_N$. Not surprisingly, the distribution is expressed through the Stirling numbers of
first kind.  {The formulas for the probability that $\sigma$ is
the identity permutation and for the probability that  $\sigma$ is a maximal cycle obtained by Stanley in \cite{Stanley} 
are the special cases of the identity in this lemma.}  Our analysis also delivers a well-known formula found by Zagier  for the case $k=2$. See
Corollary~\ref{zagier} for this special case; see the Appendix by Zagier in \cite{LandoZvonkin} for the original result of Zagier. 
In Corollary~\ref{zagier3}, we also obtain a bivariate generating function for the distribution of the number of cycles for the product of three cycles. We conclude this section with a relatively
compact integral formula for the probability that the product of two cycles belongs to a given
conjugacy class.

Then, in Section~\ref{A},  we turn to the following general question.  Let $p_A(N,$\linebreak $\ell;k)$ be 
the probability that the number of elements of $[\ell]=\{1,2,\dots ,\ell\}$ in each cycle of $\sigma $ comes from the
set $A\subseteq \mathbb Z_{\ge 0}$. What can we say about $p_A(N,\ell;k)$? 

To this end, for a general $A$, we first enumerate the admissible permutations by the cycle counts and then evaluate
the sum of character values over all admissible permutations for irreducible representations
labeled by one-hook Young diagrams.  Then we consider the special case when $A= \mathbb Z_{>0}$, i.e., when each cycle of $\sigma $ contains at least one
element of $[\ell]$. Using the inverse Fourier transform, we find an alternating sum expression for this probability with 
$N-\ell+1$ binomial-type summands. This result is proved in Theorem~\ref{formulaforA1}. For $k=2$,  this sum reduces to two
notably simpler  expressions, that can be  efficiently computed for moderate $\ell$ and moderate $N-\ell$
respectively.

Next we investigate the case of $A=\{0,\ell\}$, that is, when all elements of $\ell$ are in the same cycle of $\sigma$. 
This computation is longer than its counterpart in the previous case, and it leads to a general formula for $p_A(N,\ell;k)$, given in Theorem~\ref{formulaforA2}, that is
analogous to that for $A=\mathbb Z_{>0}$. Again, if $k=2$, then the formula shrinks to a pair of computationally efficient sums for moderate $\ell$ and moderate $N-\ell$ respectively.
For $\ell=2$ and $\ell=3$, we recover the results obtained by Stanley \cite{Stanley2}. 

Having experimented with {\sl Maple}, we feel confident  that the residual  sums for $k=2$ in either of the two cases do not have a more compact presentation.

After this, in Section~\ref{separate}, we turn to our most {technical} problem. We consider disjoint subsets ${\cal S}_1,{\cal S}_2,\dots ,{\cal S_t}$ of $[N]$ such
that $|{\cal S}_j|=\ell _j$;  define $\ell=\sum_j \ell_j$. Let $p(N,\vec\ell;k)$ denote the probability that no cycle of $\sigma$
contains elements from more than one
${\cal S}_j$, a property to which we refer by saying that $\sigma$ {\em separates} the sets 
${\cal S}_1,{\cal S}_2,\dots, {\cal S}_t$.
Bernardi et al.\ \cite{Bernardi} found a striking formula for $p(N,\vec\ell;2)$ that involved an alternating sum of $\ell-t+1$ terms. Remarkably, the  factor $\prod_j\ell_j!$ aside, the rest of the formula depends on
$\ell$ and $t$ only. In Lemma~\ref{generalk}, we show that the separation probability continues to have this
latter property  for all $k\ge 2$, and find an alternating sum formula with $N-\ell+t+1$ terms for this probability, which is computationally efficient if  $t$ and $N-\ell$ are both bounded as $N$ grows. Then, for $k=2$, we are able to simplify this formula to one that is close in appearance, but is significantly different from
 the formula in \cite{Bernardi}. This formula is given in Theorem~\ref{k=2separate}, and it  still contains a sum of $\ell-t+1$ summands, but the signs are no longer alternating.  

Finally, in Section~\ref{isolated}, we consider the following question. Let us say that the elements of $[\ell]$ are blocked in a permutation 
$s$ of $[N]$ if no two elements of $[\ell]$ are neighbors, {\em and} each element of $[\ell]$ has a neighbor from 
$[N] \setminus [\ell]$. Then, for a general $k\ge 2$,  we find a {\em two-term} formula for the probability that $\sigma$ blocks the elements of $[\ell]$.
This formula is proved in Theorem~\ref{twotermformula}.

While on occasion our proofs deliver the already known results, 
we hope that the employed techniques can be used
for a broader variety of problems on cyclic structure of the products of random permutations. 

In conclusion we should mention the recent paper \cite{FerRat} by F\'eray and Rattan. 
Among other results, it was proved in \cite{FerRat} that the number of ways to write a given permutation $\sigma$ as the product 
of an $n$-cycle and a permutation $[(n-a)-\text{cycle}]\cup \rho$, depends only on the product of {signs} of $\sigma$
and $\rho$ and the first $(a-1)$ multiplicities of cycle lengths in $\sigma$, thus generalizing a theorem by Boccara
\cite{Boc}. F\'eray and Rattan also found a recurrence equation for separation probabilities for the product of $n$-cycle and
$(n-a)$ cycle. Their methods differ significantly from ours.

\section{Preliminaries}\label{Prelim}
A key observation is that the set of all maximal cycles forms a {\em conjugacy class} in the symmetric group $S_N$, a class with particularly simple character values. We mention that permutations generated by a given conjugacy class were studied
for instance by Diaconis and Shahshahani  \cite{DiaconisShahshahani}, and, from a more algebraic point of view, 
by Larsen and Shalev \cite{larsen}. Some of that work resulted in asymptotic formulas.  However,  the research in the present paper  is in the line of work of proving {\em exact} formulas in combinatorial enumeration, like the mentioned results in \cite{Bernardi,Sta1,Stanley,Stanley2}.

Let us start with the Fourier inversion formula for a general probability measure $P$ on $S_N$:\begin{equation}\label{geninv}
P(s)=\frac{1}{N!}\sum_{\la\vdash N}f^{\la}\,\text{tr}\bigl(\rho^{\la}(s^{-1})\hat P(\rho^{\la})\bigr),\quad s\in S_N.
\end{equation}
(See  Diaconis and Shahshahani \cite{DiaconisShahshahani} and Diaconis \cite{Diaconis} for a lucid
discussion and applications of the Fourier transform for asymptotic analysis of the random walks 
on the symmetric group $S_N$ and other simple groups.)  Here $\la$ is a generic partition of the integer $N$, $\rho^{\la}$ is the irreducible representation of $S_N$
associated with $\la$, $f^{\la}=\text{dim}(\rho^{\la})$, and $\hat P(\rho^{\la})$ is the $f^{\la}\times f^{\la}$ matrix-valued Fourier transform of $P(\cdot)$ evaluated at $\rho^{\la}$, 
$
\hat P(\rho^{\la})=\sum_{s\in S_N} \rho^{\la}(s) P(s).
$
Let us evaluate the right-hand side of \eqref{geninv} for $P=P_{\sigma}$, the probability 
measure on $S_N$
induced by 
$\sigma=\prod_{j=1}^k \sigma_j$, where $\sigma_j$ is uniform on a conjugacy 
class $C_j$.  Let $P_{\sigma_j}$ be the probability measure on $S_N$ induced  by $\sigma_j$, i.e., $P_{\sigma_j}$ is
uniform on $C_j$. As the $\sigma_j$ are independent, we have $P_{\sigma}(s)=\sum_{s_1,\dots, s_k}\prod_jP_{\sigma_j}(s_j)$, ($s_1\cdots s_k=s$), that is, $P_{\sigma}$ is the convolution of $P_{\sigma_1},\dots,P_{\sigma_k}$. So, by multiplicativity
of the Fourier transform for convolutions, 
$
\hat{P}_{\sigma}(\rho^{\la}) = \prod_j \hat {P}_{\sigma_j}(\rho^{\la}).
$
Since each $P_{\sigma_j}$ is supported by the single conjugacy class $C_j$, we have
$\hat P_{\sigma_j}(\rho^{\la})=\tfrac{\chi^{\la}(C_j)}{f^{\la}}\,I_{f^{\la}}$, where $I_{f^{\la}}$ is  the
$f^{\la}\times f^{\la}$ identity matrix, see \cite{Diaconis}. So
\[
\hat{P}_{\sigma}(\rho^{\la}) = \prod_{j=1}^k\hat {P}_{\sigma_j}(\rho^{\la})=
(f^{\la})^{-k}\prod_{j=1}^k\chi^{\la}(C_j)\,I_{f^{\la}},
\]
and  \eqref{geninv} becomes
\begin{equation}\label{3chi}
\begin{aligned}
P_{\sigma}(s)&=\frac{1}{N!}\sum_{\la}(f^{\la})^{-k+1}\,\left(\prod_{j=1}^k\chi^{\la}(C_j)\right)\,\text{tr}
\bigl(\rho^{\la}(s^{-1})I_{f^{\la}}\bigr)\\
&=\frac{1}{N!}\sum_{\la}(f^{\la})^{-k+1}\chi^{\la}(s)\prod_{j=1}^k\chi^{\la}(C_j);
\end{aligned}
\end{equation}
see Stanley \cite[Exercise~7.67]{Stanley}.

\begin{note} 
For the special case $s=\text{id}$, the identity \eqref{3chi} becomes
\[
\pr_{\sigma}(\text{id})=\frac{1}{N!}\sum_{\la}(f^{\la})^{-k+2}\prod_{j=1}^k\chi^{\la}(C_j).
\]
Since the left-hand side is just ${\cal N}(C_1,\dots,C_k)$, the number of ways to write the identity
permutation as the product of elements of $C_1,\dots,C_k$, divided by $\prod_{j=1}^k |C_j|$,
we obtain the well-known $S_N$-version of Frobenius'  identity 
\begin{equation}\label{Frob}
{\cal N}(C_1,\dots,C_k)=\frac{\prod_{j=1}^k|C_j|}{N!}\sum_{\la}(f^{\la})^{-k+2}\prod_{j=1}^k\chi^{\la}(C_j).
\end{equation}
\end{note}

We will use \eqref{3chi} for $C_j\equiv \cal C_N$, where $\cal C_N$ is the conjugacy class of all
maximal cycles.  By the Murnaghan--Nakayama rule (see \cite[Lemma~4.10.2]{Sagan} or
\cite[Section~7.17, Equation~(7.75)]{Stanley}), $\chi^{\la}(\cal C_N)=0$  unless the
diagram $\la$ is a single hook $\la^*$, with one row of length $\la_1$ and one column of height $\la^{1}$, so $\la_1+\la^1=N+1$.  In that case 
\begin{equation}\label{chiN}
\chi^{\la}({\cal C}_N)=(-1)^{\la^1-1}. 
\end{equation}
As for $f^{\la^*}$, the number of Standard Young Tableaux of shape $\la^*$, by applying the hook length formula (or simply selecting the entries that go in the first column),
 we obtain
\begin{equation}\label{fla*=}
f^{\la^*}=\frac{N!}{N\prod_{r=1}^{\la_1-1} r\,\prod_{s=1}^{\la^1-1}s}=\binom{N-1}{\la_1-1}.
\end{equation}
The equations \eqref{3chi}, \eqref{chiN} and \eqref{fla*=} imply 
\begin{equation*}%\label{Psigma(s)}
P_{\sigma}(s)=\frac{1}{N!}\sum_{\la^*}(-1)^{k(\la^1-1)}\binom{N-1}{\la_1-1}^{-k+1}\chi^{\la^*}(s),
\end{equation*}
or more generally: for $\mathcal A\subseteq S_N$,
\begin{equation}\label{Psigma(s)}
\begin{aligned}
P_{\sigma}(\mathcal A)&=\frac{1}{N!}\sum_{\la^*}(-1)^{k(\la^1-1)}\binom{N-1}{\la_1-1}^{-k+1}\chi^{\la^*}(\mathcal A),\\
\chi^{\la^*}(\mathcal A)&:=\sum_{s\in \mathcal A}\chi^{\la^*}(s).
\end{aligned}
\end{equation}
By the Murnaghan--Nakayama rule, given a hook diagram $\la^*$, the value of  $\chi^{\la^*}(s)$ depends on $s$ only through $\vec{\nu}=\vec{\nu}(s):=\{\nu_r\}_{r\ge 1}$, where $\nu_r=\nu_r(s)$ is the total number of $r$-long cycles in the permutation $s$. It was proved in \cite{Pittel} that 
\begin{equation}\label{chila*(nu)}
\chi^{\la^*}(s)=(-1)^{\la^1+\nu}\,[\xi^{\la_1}]\, \frac{\xi}{1-\xi}\prod_{r\ge 1}(1-\xi^r)^{\nu_r},
\end{equation}
$\nu(s):=\sum_r\nu_r(s)$ being the total number of cycles of $s$. From \eqref{chila*(nu)} it follows that 
\begin{equation}\label{sumchila*,nu}
\begin{aligned}
\sum_{s:\, \vec{\nu}(s)=\vec\nu}\chi^{\la^*}(s)&=(-1)^{N}N! \,{\cal A}(N,\nu,\la_1),\\
{\cal A}(N,\nu,\la_1)&:=\binom{N-1}{N-\la_1}\sum_{\ell\ge 1}(-1)^{\ell}\,{\frac{c(\ell,\nu)}{\ell!}}
\binom{N-\la_1}{N-\ell},
\end{aligned}
\end{equation}
where {$c(\ell,\nu)$ is the total number of permutations
of $[\ell]=\{1,2,\dots ,\ell\}$ with $\nu$ cycles;} see the proof of Theorem~2.1 and Equation~(2.20) in \cite{Pittel}. 
The formulas \eqref{3chi}, {\eqref{Psigma(s)}--\eqref{sumchila*,nu}} are the basis of the proofs 
of a series of exact formulas in the rest of the paper.

\begin{remark}
Some asymptotic approximations for the product of maximal cycles can be obtained directly via the total variation distance bound {based on the Fourier inversion formula \eqref{geninv}.  This powerful approach} was pioneered by Diaconis and Shahshahani (see \cite{DiaconisShahshahani}, \cite{Diaconis}). Observe that 
the conjugacy class $C_N$ belongs to the alternating group $A_N$ for $N$ odd, and to $A_N^c=S_{N}
\setminus A_N$ for $N$ even. So for $N$ odd,  the product of $k$ cycles is in $A_N$ for every $k$.
 For $N$ even, the product of $k$ cycles is in $A_N$ if and only if $k$ even. A minor modification of the
 argument in \cite{Chmutov} 
 yields that in each case the total variation distance
 between the distribution of product of $k$ independent, uniformly random, $N$-cycles and the
uniform distribution on the corresponding range ($A_N$ or $A_N^c$, depending on parities of
 $N$ and $k$) decays as $N^{-k/2}$ for $n\to\infty$. The interested reader may wish to compare this general error estimate with the particular remainder term estimates arising from our exact results and the known/folklore results for 
a uniformly random permutation from $A_N$ or $A_N^c$.
\end{remark}
  
\section{Distribution of the number of cycles in $\sigma$}\label{cycles}  To stress dependence 
of $\sigma$ on $k$, in this section we will write $\sigma^{(k)}$ instead of $\sigma$. {Let $\nu(\sigma)$ denote the number of cycles in a permutation $\sigma$. We start with the following general
formula.} 

\begin{lemma} \label{cycledist} The identity 
\begin{equation}\label{P(nu(sigma)=nu)}
\begin{aligned}
\pr(\nu(\sigma^{(k)})=\nu)&=(-1)^N\sum_{\la_1=1}^N(-1)^{k(N-\la_1)}\binom{N-1}{N-\la_1}^{-k+2}\\
&\kern3cm
\times\sum_{\ell\ge 1}(-1)^{\ell}\,{ \frac{c(\ell,\nu)}{\ell!}}
\binom{N-\la_1}{N-\ell}
\end{aligned}
\end{equation}
holds. 
\end{lemma}

\begin{proof}
Combination of
\eqref{sumchila*,nu}, \eqref{Psigma(s)}, and $\la^1+\la_1=N+1$ proves \eqref{P(nu(sigma)=nu)}. 
\end{proof}


\begin{corollary} \label{sigma-id} For $k\ge 2$, the identity 
\begin{equation}\label{Pr(id)=}
\begin{aligned}
\pr(\sigma^{(k)}=\text{\em id})&=\pr(\nu(\sigma)=N)
=\frac{1}{N!}\sum_{r=0}^{N-1}(-1)^{kr}\binom{N-1}{r}^{-k+2},
\end{aligned}
\end{equation}
holds.
\end{corollary}

\begin{proof}
Use Formula \eqref{P(nu(sigma)=nu)} and the fact that ${c(\ell,\nu)}=0$ for $\ell<\nu$.
\end{proof}

Note that Formula \eqref{Pr(id)=} appears as Equation~(7.181) in \cite{Stanley}.  In the special case
of $k=2$  Corollary~\ref{sigma-id} yields 
 \begin{equation}\label{P(sigma2isid)}
 \pr(\sigma^{(2)}=\text{id})=\tfrac{1}{(N-1)!}. 
 \end{equation}
 This is an obvious result, since the inverse of a uniformly random cycle is again a uniformly
 random cycle.
 
The special case of $k=3$ is not so obvious. However, combining \eqref{Pr(id)=} and  the identity 
\begin{equation}\label{Sury}
\sum_{r=a}^n \frac{(-1)^r}{\binom{n}{r}}=\frac{n+1}{n+2}\left[\frac{(-1)^a}{\binom{n+1}{a}}+(-1)^n\right]
\end{equation}
(see \cite{Sury}, \cite[Equation~(7.211)]{Stanley}, \cite {SWZ}), we have  a non-obvious answer
\begin{equation}\label{P(siigma3=id)}
\pr(\sigma^{(3)}=\text{id})=\frac{1+(-1)^{N-1}}{(N-1)!\,(N+1)},
\end{equation}
see \cite[Exercise~7.67~(d)]{Stanley}.

The remarkable identity \eqref{Sury}  followed from the elementary 
formula for a special case of the beta integral:
\begin{equation}\label{recbin=}
\binom{n}{r}^{-1}=(n+1)\int_0^1t^r(1-t)^{n-r}\,dt.
\end{equation}

Note that for  even $N$,  Equation~\eqref{P(siigma3=id)} returns zero probability, and that is how it should be, since the product of three
even cycles is an odd permutation, and therefore, cannot be the identity. Furthermore, since
$\sigma^{(k)}=\sigma^{(k-1)}\sigma_k$, the product  $\sigma^{(k)}$ is the identity if and only if $\sigma^{(k-1)}=
(\sigma_{k})^{-1}$, which is a maximal cycle. As $(\sigma_{k})^{-1}$ is uniform on the set of all
$(N-1)!$ maximal cycles,  {\it and\/} independent of $\sigma^{(k-1)}$, we see then that
\begin{equation}\label{P(cycle)=P(id)}
\pr(\sigma^{(k-1)}\text{ is a cycle})=(N-1)!\,\pr(\sigma^{(k)}=\text{id}).
\end{equation}

In the special case of $k=2$, we rediscover a result that has been proved several times, with different methods. 
\begin{corollary} \label{cycleproducts}
We have
\begin{equation}\label{P(sigma2=cycle)}
\pr(\sigma^{(2)}\text{ \em is a cycle})=\frac{1+(-1)^{N-1}}{N+1}.
\end{equation}
\end{corollary}

\begin{proof} This is immediate from 
  Equations \eqref{P(siigma3=id)} and \eqref{P(cycle)=P(id)}.
\end{proof}

For even $N$, the statement of Corollary~\ref{cycleproducts} is obvious, since the product of two maximal cycles is an even permutation, and, hence, it cannot be an $N$-cycle for even $N$.  For odd $N$, the result  is 
equivalent to a well-known, but not at all obvious, fact that there are $\tfrac{2(N-1)!}{N+1}$ ways to
factor a given maximal cycle into a product of two maximal cycles; see for instance
\cite{cangelmi} and the references therein.  In general, Equations \eqref{Pr(id)=} and \eqref{P(cycle)=P(id)} imply 
the following. 

\begin{corollary}
For all positive integers $k$, we have
\begin{equation}\label{P(cycle)gen}
\pr(\sigma^{(k)}\text{ \em is a cycle})=\frac{1}{N}\sum_{r=0}^{N-1}(-1)^{(k+1)r}\binom{N-1}{r}^{-k+1}.
\end{equation}
\end{corollary}

Further, it follows from \eqref{P(nu(sigma)=nu)} that, for every real number $x$, we have
\begin{align}
\ex\bigl[x^{\nu({\sigma^{(k)}})}\bigr]&=(-1)^N\sum_{\la_1=1}^N(-1)^{k(N-\la_1)}\binom{N-1}{N-\la_1}^{-k+2}\notag\\
&\kern2cm
\times\sum_{\ell\ge 1}\frac{(-1)^{\ell}}{\ell!}
\binom{N-\la_1}{N-\ell}\sum_{\nu\ge 1}x^{\nu}c(\ell,\nu)\notag\\
&=(-1)^N\sum_{\la_1=1}^N(-1)^{k(N-\la_1)}\binom{N-1}{N-\la_1}^{-k+2}\sum_{\ell\ge 1}\binom{N-\la_1}{N-\ell}\binom{-x}{\ell}\notag\\
&=(-1)^N\sum_{\la_1=1}^N(-1)^{k(N-\la_1)}\binom{N-1}{N-\la_1}^{-k+2}\binom{N-\la_1-x}{N}\notag\\
&=(-1)^N\sum_{r=0}^{N-1}(-1)^{kr}\binom{N-1}{r}^{-k+2}\binom{r-x}{N}.\label{k,Exnu(sigma)}
\end{align}
For a positive integer $x$, the non-zero contributions to the sum come from $r<\min\{N,x\}$. So,
for instance,
\begin{align*}
\ex\bigl[2^{\nu(\sigma^{(k)})}\bigr]&=N+1+\frac{(-1)^k}{(N-1)^{k-2}},\quad N>1,\\
\ex\bigl[3^{\nu(\sigma^{(k)})}\bigr]&=2(N+2)_2-\frac{N+1}{(N-1)^{k-2}}+\binom{N-1}{2}^{-k+2},
\quad N>2,
\end{align*}
where we use the notation $(a)_b=a(a-1)\cdots (a-b+1)$, for integers $a\geq b\geq 0$. 


For $k=2$ and $x>N$,  Equation \eqref{k,Exnu(sigma)} implies 
the following corollary.

\begin{corollary} \label{zagier} We have
\begin{align}
\ex\bigl[x^{\nu(\sigma^{(2)})}\bigr]&=(-1)^N\sum_{\la_1=1}^N\binom{N-\la_1-x}{N}\notag\\
&=\sum_{\la_1=1}^N\binom{\la_1+x-1}{N}
=\sum_{j=N}^{N+x-1}\binom{j}{N}-\sum_{j=N}^{x-1}\binom{j}{N}\notag\\
&=\binom{N+x}{N+1}-\binom{x}{N+1}=\binom{N+x}{N+1}+(-1)^N\binom{N-x}{N+1}.
\label{2,Exnu(sigma)} 
\end{align} 
\end{corollary}
Of course, the identity \eqref{2,Exnu(sigma)} holds for all $x$. It is equivalent to Zagier's result, (see  the Appendix by Zagier in \cite{LandoZvonkin}), stating 
that 
\[
\pr(\nu(\sigma^{(2)})=\nu)=(1+(-1)^{N-\nu})\,[x^{\nu}]\binom{N+x}{N+1}.
\]

For $k=3$, we can prove the following (weighted) analogue of Corollary~\ref{zagier}. 

%the combination of \eqref{k,Exnu(sigma)} and the identity \eqref{recbin=} allows us to show that

\begin{corollary} \label{zagier3} We have
 \begin{equation}\label{k=3,H-Z}
\sum_{N\ge 1}\frac{y^N}{N}\ex\bigl[x^{\nu(\sigma^{(3)}(N))}\bigr]=
\int_0^1\frac{(1-y(1-t))^{-x} -(1-y(1-t))^x}{1-yt(1-t)}\,dt;
\end{equation}
here $\sigma^{(3)}(N)$ is the product of $3$ random cycles of length $N$, and $|x|\le1$, $|y|<1$.
\end{corollary}

Note that the right-hand side of \eqref{k=3,H-Z} is an odd function of $x$. This should be expected, 
since--regardless of the parity of 
$N$--the number of cycles in $\sigma^{(3)}(N)$ is odd. In particular, using
\[
(1-y(1-t))^{-x} -(1-y(1-t))^x=2\sum_{r\text{ odd}}\frac{\log^r (1-y(1-t))^{-1}}{r!}\,x^r,
\]
we obtain
\begin{equation}\label{fun}
\sum_{N\ge 1}\frac{y^N}{N}\pr(\sigma^{(3)}(N)\text{ has }r\text{ cycles})=\frac{2}{r!}\int_0^1\frac{\log^r\bigl(1-y(1-t)\bigr)^{-1}}{1-yt(1-t)}\,dt.
\end{equation}
Here is a probabilistic interpretation of this identity. For $y\in (0,1)$, introduce an integer-valued random variable $\mathcal N$ such
that 
\[
\pr(\mathcal N=N)= \frac{y^N}{N} \log(1-y)^{-1},\quad N\ge 1,
\]
i.e., $\mathcal N$ has the logarithmic distribution with parameter $y$. So we (A) choose the random length $\mathcal N$ of the permutations, (B) conditioned on $\mathcal N$, generate, in order, three independent uniform cycles of length $\mathcal N$,
and (C) compute their product $\sigma^{(3)}(\mathcal N)$. Then  identity \eqref{fun} means that, for $r$ odd,
\[
\pr(\sigma^{(3)}(\mathcal N)\text{ has }r\text{ cycles})=\frac{2}{r!\log (1-y)^{-1}}\int_0^1\frac{\log^r\bigl(1-y(1-t)\bigr)^{-1}}{1-yt(1-t)}\,dt.
\]

%\begin{multline*}
%\sum_{N\ge 1}\frac{y^N}{N}\pr(\sigma^{(3)}(N)\text{ is a cycle})=2\int_0^1\frac{\log\bigl(1-y(1-t)\bigr)^{-1}}{1-yt(1-t)}\,dt\\
%=2\sum_{j>0}\frac{1}{j}\int_0^1\frac{\bigl(y(1-t)\bigr)^j}{1-yt(1-t)}\,dt=2\sum_{j>0,h\ge 0}
%\frac{y^{j+h}}{j}\int_0^1(1-t)^{j+h}t^h\,dt\\
%=2\sum_{j>0,h\ge 0}\frac{y^{j+h}}{j}(j+2h+1)^{-1}\binom{j+2h}{h}^{-1}.
%\end{multline*}
%So
%\begin{equation}\label{p(sigma^3=cycle}
%\pr(\sigma^{(3)}(N)\text{ is a cycle})=2N\sum_{h<N}(N-h)^{-1}(N+h+1)^{-1}\binom{N+h}{h}^{-1};
%\end{equation}
%compare with the equation \eqref{P(cycle)gen} for $k=3$.

\begin{proof}[Proof of Corollary~\ref{zagier3}]  Since both sides of  \eqref{k=3,H-Z} are analytic for $|y|<1$, it
suffices to prove the identity for $|y|\le 1/3$. From \eqref{k,Exnu(sigma)}, \eqref{recbin=} and
\[
(-1)^N \binom{r-x}{N}= [z^N] (1-z)^{r-x},
\]
we obtain 
\begin{multline*}
N^{-1}\ex\bigl[x^{\nu(\sigma^{(3)}(N))}\bigr]=[z^N] \sum_{r=0}^{N-1}(1-z)^{r-x}\int_0^1(1-t)^{N-1-r}t^r\,dt\\
=[z^N] (1-z)^{-x}\int_0^1(1-t)^{N-1}\sum_{r=0}^{N-1}\left(-\frac{(1-z)t}{1-t}\right)^r\,dt\\
=[z^N] (1-z)^{-x}\int_0^1\frac{(1-t)^N+(-1)^{N+1}\bigl((1-z)t\bigr)^N}{1-tz}\,dt.
\end{multline*}
Next
\[
y^N(1-t)^N [z^N] \,\frac{(1-z)^{-x}}{1-tz}=[z^N]\,\frac{\bigl(1-(1-t)yz\bigr)^{-x}}{1-t(1-t)yz};
\]
so
\begin{align}
\int_0^1\sum_{N\ge 1}y^N(1-t)^N [z^N] \,\frac{(1-z)^{-x}}{1-tz}\,dt&=\int_0^1\sum_{N\ge 1}[z^N]\,\frac{\bigl(1-(1-t)yz\bigr)^{-x}}{1-t(1-t)yz}\,dt\notag\\
&=\int_0^1\frac{\bigl(1-(1-t)y\bigr)^{-x}}{1-t(1-t)y}\,dt  -1.\label{first}
\end{align}
Further, by the Cauchy integral  formula,
\begin{multline*}
y^N[z^N]\frac{(1-z)^{-x}}{1-tz}\bigl((1-z)t\bigr)^N=\frac{1}{2\pi i}\oint_{|z|=2/3}
\frac{(1-z)^{-x}}{z^{N+1}(1-tz)}\bigl(y(1-z)t\bigr)^N\,dz\\
=\frac{1}{2\pi i}\oint_{|z|=2/3}
\frac{(1-z)^{-x}}{z(1-tz)}\left(\frac{y(1-z)t}{z}\right)^N\,dz .
\end{multline*}
On the circle $|z|=2/3$, we have $\bigl|\tfrac{y(1-z)t}{z}\bigr|\le 5|y|/2\le 5/6$; so summing
over $N\ge 1$, 
\begin{align*}
\sum_{N\ge 1} (-1)^{N+1}y^N[z^N]&\frac{(1-z)^{-x}}{1-tz}\bigl((1-z)t\bigr)^N\\
&=\frac{1}{2\pi i}\oint_{|z|=2/3}\frac{(1-z)^{-x}}{z(1-tz)}\frac{\tfrac{y(1-z)t}{z}}{1+\tfrac{y(1-z)t}{z}}\,dz\\
&=\frac{1}{2\pi i}\oint_{|z|=2/3}\frac{(1-z)^{-x}}{z(1-tz)}\cdot\frac{y(1-z)t}{z+y(1-z)t}\,dz.
\end{align*}
For $t>0$, in the circle $|z|\leq 2/3$ the integrand has two poles, both simple, at $z=0$ and 
$z=-\tfrac{yt}{1-yt}$, with respective residues equal to $1$ and $-\tfrac{(1-yt)^x}{1-yt(1-t)}$.
Thus
\[
\sum_{N\ge 1} (-1)^{N+1}y^N[z^N]\frac{(1-z)^{-x}}{1-tz}\bigl((1-z)t\bigr)^N=1-\frac{(1-yt)^x}
{1-yt(1-t)}.
\]
Integrating for $t\in [0,1]$ and adding to \eqref{first}, we obtain
\[
\sum_{N\ge 1}\frac{y^N}{N}\ex\bigl[x^{\nu(\sigma^{(3)}(N))}\bigr]=\int_0^1\frac{(1-y(1-t))^{-x} -(1-yt)^x}{1-yt(1-t)}\,dt,
\]
which is equivalent to \eqref{k=3,H-Z}, as $t(1-t)$ is symmetric with respect to $t=1/2$. As a partial check, the  integral on the right-hand side equals $\log (1-y)^{-1}$ if $x=1$.
\end{proof}

Our final result in this section is a relatively compact integral formula for $P_n(\boldsymbol\nu)$,
the probability that $\sigma^{(2)}$ has $\nu_{\ell}$ cycles of length $\ell$, where $1\le \ell\le n$, for
 {\it arbitrary} $\boldsymbol\nu$, i.e., satisfying the only constraint $\sum_{\ell} \ell\nu_{\ell}=N$.
Since $\sigma^{(2)}$ is even, $P_n(\boldsymbol\nu)=0$ if $\sum_{\ell\text{ even}}\nu_{\ell}$ is odd.

\begin{theorem}\label{gensig2} We have
\[
P_n(\boldsymbol\nu)=\frac{N}{\prod_{\ell} \ell^{\nu_{\ell}}\nu_{\ell}!}\int_0^1\prod_{\ell\ge 1}
\bigl[t^{\ell}+(-1)^{\ell+1}(1-t)^{\ell}\bigr]^{\nu_{\ell}}\,dt .
\] 
\end{theorem}
%
\begin{proof} First, the number of permutations $s$ with cycle structure $\boldsymbol\nu$ is equal to 
$N!/\prod_{\ell} \ell^{\nu_{\ell}}\nu_{\ell}!$. Furthermore, for every such permutation $s$, Formula
 \eqref{chila*(nu)} implies that  $\la^1+\la_1=N+1$ and $\nu=\sum_{\ell}\nu_{\ell}$. Setting $r=N-\la_1$, and choosing a positive $\rho$, we obtain
\[
\chi^{\la^*}(s)=(-1)^{N+r}\frac{1}{2\pi i}\oint\limits_{|\xi|=\rho}\frac{1}{\xi^{r+1}(1-\xi)}\prod_{\ell\ge 1}
(\xi^{\ell}-1)^{\nu_{\ell}}\,d\xi.
\]
Here the circular contour is traversed counter-clockwise, and $\rho$ is arbitrary, as the integrand is
singular at $\xi=0$ only. Substituting $\xi = 1/\eta$, we have
\[
\chi^{\la^*}(s)=(-1)^{N+r}\frac{1}{2\pi i}\oint\limits_{|\eta|=1/\rho}\frac{1}{\eta^{N-r}(\eta-1)}
\prod_{\ell\ge 1}(1-\eta^{\ell})^{\nu_{\ell}}\,d\eta,
\]
with the contour traversed counter-clockwise again. 
Substituting this formula in Equation~\eqref{Psigma(s)}, 
and using \eqref{recbin=}, we have 
\begin{align*}
P&_{\sigma^{(2)}}(s)=\frac{(-1)^N}{N!}\sum_{r=0}^{N-1}\binom{N-1}{r}^{-1}\chi^{\la^*}(s)\\
&\, =\frac{(-1)^NN}{N!}\sum_{r=0}^{N-1}\chi^{\la^*}(s)\int\limits_0^1t^r(1-t)^{N-1-r}\,dt\\
&\, =\frac{(-1)^N}{(N-1)!}\,\frac{1}{2\pi i}\oint\limits_{|\eta|=1/\rho}\!\!\left(\int\limits_0^1(1-t)^{N-1}\sum_{r=0}^{N-1}
\left(\!-\frac{t\eta}{1-t}\right)^r\,dt\!\right)\frac{\prod_{\ell}(1-\eta^{\ell})^{\nu_{\ell}}}{\eta^N(\eta-1)}\,d\eta\\
&\, =\frac{(-1)^N}{(N-1)!}\int\limits_0^1\left(\frac{1}{2\pi i}\oint\limits_{|\eta|=1/\rho}
\frac{(1-t)^N-(-t\eta)^N}{1-t+t\eta}\cdot\frac{\prod_{\ell}(1-\eta^{\ell})^{\nu_{\ell}}}{\eta^N(\eta-1)}\,d\eta\right)\,dt .
%=\frac{1}{(N-1)!}\,\frac{1}{2\pi i}\oint\limits_{|\eta|=1/\rho}\left(\int_0^1
%\frac{(1-t)^N-(-t\eta)^N}{1-t+t\eta}\,dt\right)\frac{\prod_s(1-\eta^s)^{\nu_s}}{\eta^N(\eta-1)}\,d\eta\\
%=\frac{1}{(N-1)!}\,[\eta^{N-1}].
\end{align*}
Pick $\eps\in (0,1)$ and consider $t\le 1-\eps$. Choose $\rho>(1-\eps)/\eps$. For this $\rho$,
the internal integrand has two  singular points, $\eta=0$ and $\eta=-(1-t)/t$,  respectively within and outside of the integration contour. Crucially, 
\[
\frac{-(-t\eta)^N}{1-t+t\eta}\cdot\frac{\prod_{\ell}(1-\eta^{\ell})^{\nu_{\ell}}}{\eta^N(\eta-1)}
=\frac{-(-t)^N}{1-t+t\eta}\cdot\frac{\prod_{\ell}(1-\eta^{\ell})^{\nu_{\ell}}}{\eta-1}
\]
has no singularity at $\eta=0$, and for $t>0$, we have
\[
\frac{(1-t)^N}{1-t+t\eta}\cdot\frac{\prod_{\ell}(1-\eta^{\ell})^{\nu_{\ell}}}{\eta^N(\eta-1)}=O(|\eta|^{-2}),
\quad |\eta|\to\infty,
\]
as $\sum_{\ell}\ell\nu_{\ell}=N$. So, by the residue theorem,
the internal integral equals 
\begin{align*}
\frac{1}{2\pi i}\oint\limits_{|\eta|=1/\rho}
\frac{(1-t)^N}{1-t+t\eta}&{}\cdot\frac{\prod_{\ell}(1-\eta^{\ell})^{\nu_{\ell}}}{\eta^N(\eta-1)}\,d\eta\\
&=-t^{-1}\left.(1-t)^N\cdot\frac{\prod_{\ell}(1-\eta^{\ell})^{\nu_{\ell}}}{\eta^N(\eta-1)}\right|_{\eta=-\tfrac{1-t}{t}}\\
&=(-1)^N\prod_{\ell\ge 1}\bigl[t^{\ell}+(-1)^{\ell+1}(1-t)^{\ell}\bigr]^{\nu_{\ell}},
\end{align*}
for all $0< t\le 1-\eps$. Letting $\eps\to 0$, we obtain
\[
P_{\sigma^{(2)}}(s)=\frac{1}{(N-1)!}\int\limits_0^1\prod_{\ell\ge 1}\bigl[t^{\ell}+(-1)^{\ell+1}(1-t)^{\ell}\bigr]^{\nu_{\ell}}\,dt.
\]
Multiplying the result by $N!/\prod_{\ell}\ell^{\,\nu_{\ell}}\nu_{\ell}!$ we complete the proof.
\end{proof}
%In a private communication G\'abor Hetyei raised an interesting question concerning the order
%of the subgroup generated by the product of two random cycles, and more specifically
%the chances that the order is even/odd. One should hardly expect a relatively compact,
%non-asymptotic, formula for this probability. Contemplating G\'abor Hetyei's problem, we found an
%appealing formula for the probability that the product $\sigma^{(2)}$ is a fixed-point free involution, or more generally that all cycles of $\sigma^{(2)}$ are of the same length $r\ge 2$. We need only to consider $N\equiv 0\,(\text{mod }r)$.
\begin{corollary}\label{P(N,r)=}  Let $P_{N,r}$ denote the probability that all cycles of $\sigma^{(2)}$ are of the same length $r\ge 2$, i.e., $N\equiv 0\ (\text{mod }r)$ and $\nu_r=N/r$. (So $P_{N,r}=0$ if $r$ is
even and $N\not\equiv 0\ (\text{\em mod }2r)$.) Then
\begin{equation}\label{P(N,r)}
\begin{aligned}
P_{N,r}&=\frac{N}{r^{N/r}(N/r)!}\int_0^1\bigl[t^r+(-1)^{r+1}(1-t)^r\bigr]^{N/r}\,dt\\
&=\frac{N}{(N+1)r^{N/r}(N/r)!}\underset{j\equiv 0\ (\text{\em mod }r)}{\sum_{0\le j\le N}}
\!\!\!\!(-1)^{j(r+1)/r}\frac{\binom{N/r}{j/r}}{\binom{N}{j}}.\\
\end{aligned}
\end{equation}
In particular,
\begin{gather}\label{P(N,2),P(N,3)}
P_{N,2}=\frac{\bigl(1+(-1)^{N/2}\bigr)N/2}{2^{N/2}(N/2+1)!},\quad P_{N,3}
=\frac{N}{(N/3)!\,(12)^{N/3}}\sum_{j=0}^{N/3}
\binom{N/3}{j}\frac{3^j}{2j+1},\\
\label{P(N,4)}
P_{N,4}=\frac{\bigl(1+(-1)^{N/4}\bigr)N/2}{8^{N/4} (N/4)!}\sum_{j=0}^{N/4}\binom{N/4}{j}\frac{1}{N/4+2j+1}.
\end{gather}
\end{corollary}
%\noindent The derivation of \eqref{P(N,2),P(N,3)}-\eqref{P(N,4)} seems to indicate that the identity in the second line
%in \eqref{P(N,r)} is the preferred expression for the probability $P_{N,r}$ when $r>4$.

\begin{proof} 
%First of all, the number of permutations $s$ with $N/r$ cycles of length $r$ each is
%$N!/[r^{N/r} (N/r)!]$. So, using  \eqref{Psigma(s)}, \eqref{chila*(nu)}, and $\la^1+\la_1=N+1$, we obtain 
%\begin{align*}
%P_{N,r}&=\frac{(-1)^{N}}{r^{N/r}(N/r)!}\sum_{\la_1=1}^N\frac{(-1)^{\la_1-1}}{\binom{N-1}{\la_1-1}}
%[\xi^{\la_1-1}] (1-\xi)^{-1}(\xi^r-1)^{N/r}\\
%&=\frac{(-1)^{N}}{r^{N/r}(N/r)!}\sum_{\la_1=1}^N\frac{(-1)^{\la_1-1}}{\binom{N-1}{\la_1-1}}\sum_{j\le \la_1-1}
%\binom{N/r}{j/r}(-1)^{(N-j)/r}\\
%&=\frac{(-1)^{N}}{r^{N/r}(N/r)!}\sum_j\binom{N/r}{j/r}(-1)^{(N-j)/r}\sum_{\la_1=j+1}^N\frac{(-1)^{\la_1-1}}{\binom{N-1}{\la_1-1}}.
%\end{align*}
%The inner-most sum is zero for $j=N$.  Using the identity \eqref{Sury} for $j<N$, and
%$\sum_t (-1)^t \binom{a}{t}=0$ for $a>0$,  we arrive at the first line identity in  \eqref{P(n,r)}. 
%If $\tfrac{N(r-1)}{r}\not\equiv 0\,(\text{mod }2)$, then the $j$-term and the $(N-j)$-th term in this sum cancel each other out for every $j$ in question, whence $P_{N,r}=0$. If $\tfrac{N(r-1)}{r}\equiv 0\,(\text{mod }2)$, then the identity can be rewritten as follows:
The second identity in \eqref{P(N,r)} follows  from the
%from Theorem \ref{gensig2} via
 binomial
formula for the integrand $\bigl[t^r+(-1)^{r+1}(1-t)^{r}\bigr]^{N/r}$, and summation of the resulting beta integrals.
%\begin{align*}
%P_{N,r}&=\frac{N}{(N+1)r^{N/r}(N/r)!}\sum_{k=0}^{N/r}\left[(-1)^{r+1}\right]^k
%\frac{\binom{N/r}{k}}{\binom{N}{rk}}\\
%&=\frac{N}{r^{N/r}(N/r)!}\sum_{k=0}^{N/r}\binom{N/r}{k}\left[(-1)^{r+1}\right]^k
%\int_0^1 (t^r)^k \bigl((1-t)^r\bigr)^{N/r-k}\,dt\\
%&=\frac{N}{r^{N/r}(N/r)!}\int_0^1\bigl[(1-t)^r+(-1)^{r+1}t^r\bigr]^{N/r}\,dt.
%\end{align*}
Furthermore, denoting $u=2t-1$, we have
\[
\bigl[t^r+(-1)^{r+1}(1-t)^r\bigr]^{N/r}=\begin{cases}
u^{N/2},&r=2,\\
\left(\frac{3u^2+1}{4}\right)^{N/3},&r=3,\\
\left(\frac{u^3+u}{2}\right)^{N/4},&r=4.
\end{cases}
\]
Switching to $u=2t-1$ in the integral in \eqref{P(N,r)}, using the binomial formula and integrating, we obtain 
 Formulas \eqref{P(N,2),P(N,3)}--\eqref{P(N,4)}. Using the same device for $r>4$ would have necessitated the
multinomial formula, leading to multi-fold sums, progressively more complex than the formula in the second line of \eqref{P(N,r)}.
\end{proof}
\begin{corollary}\label{inv} For all positive integers $N$, we have
\[
\pr(\sigma^{(2)}\text{ \em is an involution})=N\!\!\!
\underset{\nu_2\text{ \em even}}{\sum_{\nu_1+2\nu_2=N}}\frac{1}{\nu_1!\,2^{\nu_2}(\nu_2+1)!}.
\]
\end{corollary}
The identities equivalent to \eqref{P(N,2),P(N,3)}  were proved in \cite{doignon} by using the sum-type formulas for the total number of ways to represent
a maximal cycle as a product of a maximal cycle and a permutation from a given conjugacy
class, see \cite{Gou}, \cite{Sta1}, \cite{GouSch}.  The sequence $(N-1)!\, P_{N,2}$ is listed by
Sloane as A035319, and known as the counts of certain rooted maps, see \cite{walsh}. The sequence 
$(N-1)!\,P_{N,3}$ is listed in Sloane as A178217. 
%{\color{blue} Miklos, is $(N-1)! P_{N,4}$ also listed in Sloane?}

\section{Probability that  the occupancy numbers  of the cycles of $\sigma$ by the
elements of $[\ell]$ belong to a given set}\label{A}

In the section title and elsewhere below $\sigma$ is $\sigma^{(k)}$, the product of $k$
random maximal cycles.  Let $A\subseteq \mathbb Z_{\ge 0}$ be given. Recall that $p_A(N,\ell;k)$ is the probability that the number
of elements of $[\ell]$ in each cycle of $\sigma$ belongs
to the set $A$. {Let $\mathcal A$ denote the set of all permutations $s$ with this property, so that $p_A(N,\ell;k)=P_{\sigma}(s\in \mathcal A)$.}

The examples include: (1) $A_1=\mathbb Z_{>0}$; each cycle must contain at least
one element of $[\ell]$; (2) $A_2=\{0,\ell\}$; one of the cycles of $\sigma$ contains the whole
set $[\ell]$; (3) $A_3=\{0,1\}$; each element of $[\ell]$ belongs to a distinct cycle of $\sigma$.

The problem of finding an explicit formula for  $p_A(N,\ell;k)$ was solved by Stanley \cite{Stanley2} in the special 
cases of $k=2$, $\ell=2$ and $A=\{0,2\}$ or $A=\{0,1\}$. 
Recently, Bernardi et al.\ \cite{Bernardi} solved the case $k=2$, $A=A_3$ for $\ell \ge 2$.
In fact they solved a general problem of separation probability for $t$ disjoint sets ${\cal S}_1,\dots, {\cal S}_{t}$. We will present an alternative solution for this problem.

To evaluate  $p_A(N,\ell;k)$, consider first $Q_A(\vec{\nu},\ell)$, the total number of permutations $s$ of $[N]$, with 
$\vec{\nu}(s)=\{\nu_r(s)\}=\{\nu_r\}=\vec{\nu}$, such that the number of
elements of $[\ell]$ in every cycle is an element of $A$. The reason we need $Q_A(\vec{\nu},\ell)$ is that the key formula \eqref{chila*(nu)}
expresses $\chi^{\la*}(s)$ through the cycle counts $\nu_r(s)$, $r\ge 1$.



{\begin{theorem}\label{QA}
For all $\ell\geq 2$, we have
\begin{equation}\label{QA=} 
Q_A(\vec{\nu},\ell) =
(N-\ell)!\,\ell!\,\, [w^{\ell}]\prod_r\frac{1}{\nu_r!}\left(\frac{\sum_{a\in A}\binom{r}{a}w^a}{r}\right)^{\nu_r}.
\end{equation}
\end{theorem}


\begin{proof} To evaluate $Q_A(\vec{\nu},\ell)$, it suffices to evaluate its counterpart $\mathcal Q_A(\vec{\nu},\ell)$
that corresponds to the case when cycles of the same length are ordered, because
\[
Q_A(\vec{\nu},\ell)=\frac{\mathcal Q_A(\vec{\nu},\ell)}{\prod_r \nu_r!}.
\]
Introduce the integers $a_{r,j}\ge 0$, $b_{r,j}\ge 0$ that
stand for the generic numbers of elements from $[\ell]$ and $[N]\setminus [\ell]$ in the $j$-th cycle of length $r$, $(j\in [\nu_r])$. Let  $\mathbf a$ (respectively $\mathbf b$) denote the sequence of the numbers $a_{r,j}$ (respectively $b_{r,j}$), in increasing
order of the indices $r$, and (for each $r$)  in increasing order of the indices $j$.  For $\mathbf a$, $\mathbf b$ to be admissible we must have
\begin{align}
a_{r,j}&{}+b_{r,j}=r,\label{a+b=r}\\
 &a_{r,j}\in A, \label{ainA}\\
\sum_{r,j}a_{r,j}&=\ell,\quad \sum_{r,j}b_{r,j}=N-\ell.\label{sumarj=ell,sumbrj=N-ell}
\end{align}
Given $\mathbf a$ and $\mathbf b$, the number of ways to partition $[\ell]$ into the subsets of cardinality $a_{r,j}$ and to
partition $[N]\setminus [\ell]$ into the subsets of cardinality $b_{r,j}$ is
\[
\frac{\ell!}{\prod_{r,j} a_{r,j}!}\cdot \frac{(N-\ell)!}{\prod_{r,j} b_{r,j}!}.
\]
(Here the subsets form two ordered sequences, each in increasing order of $r$, and (given $r$) in increasing order of $j\in [\nu_r]$.) Given two such set partitions of $[\ell]$ and $N\setminus [\ell]$, the number of ways to form a cycle from the $(r,j)$-th
set belonging to the first partition and the $(r,j)$-th set belonging to the second partition is $(a_{r,j}+b_{r,j}-1)!=(r-1)!$.
Therefore
\begin{equation}\label{p(nu,ell)}
\begin{aligned}
\mathcal Q_A(\vec{\nu},\ell)&=(N-\ell)!\,\ell!
\underset{\eqref{a+b=r}, \eqref{ainA},\eqref{sumarj=ell,sumbrj=N-ell}}
{\sum_{\mathbf a,\,\mathbf b\text{ meet }}}
\prod_r((r-1)!)^{\nu_r}\prod_{j\in [\nu_r]}\frac{1}{a_{r,j}!\,b_{r,j}!}\\
&=(N-\ell)!\,\ell!\,[w^{\ell}]\prod_r\frac{1}{r^{\nu_r}}\,\prod_{j\in[\nu_r]} \sum_{a_{r,j}\in A}
\binom{r}{a_{r,j}} w^{a_{r,j}}\\
%&=(N-\ell)!\,\ell!\,[w^{\ell}]\prod_r\frac{1}{r^{\nu^r}\nu_r!}\,\left(\sum_{a\in A}\binom{r}{a}w^a\right)^{\nu_r}\\
%&=(N-\ell)!\,\ell!\,[w^{\ell}]\prod_r\frac{1}{r^{\nu_r}\nu_r!}\bigl[(1+w)^r-1\bigr]^{\nu_r}\\
&=(N-\ell)!\,\ell!\,\, [w^{\ell}]\prod_r\left(\frac{\sum_{a\in A}\binom{r}{a}w^a}{r}\right)^{\nu_r}.
\kern3.5cm\qedhere
\end{aligned}
\end{equation}
\end{proof}

Let $\mathcal A(\vec\nu):=\{s\in \mathcal A: \vec\nu(s)=\vec\nu\}$. Then, using \eqref{chila*(nu)}, $\nu=\sum_r\nu_r$ and \eqref{QA=}, we conclude that
\begin{multline*}
\chi^{\la^*}(\mathcal A(\vec\nu))=(-1)^{\la^1+\nu} Q_A(\vec\nu,\ell)\cdot [\xi^{\la_1}]\frac{\xi}{1-\xi}\prod_{r\ge 1} (1-\xi^r)^{\nu_r}\\
=(-1)^{\la^1}(N-\ell)!\,\ell!
\cdot 
[\xi^{\la_1}w^{\ell}]\,\,\frac{\xi}{1-\xi}\,\prod_r\frac{1}{\nu_r!}\left(-\frac{(1-\xi^r)\bigl(\sum_{a\in A}\binom{r}{a}w^a\bigr)}{r}\right)^{\nu_r}.
\end{multline*}
%\begin{multline*}
%\sum_{s\in \mathcal A:\,\vec{\nu}(s)=\vec{\nu}}\chi^{\la^*}(s)=(-1)^{\la^1}(N-\ell)!\,\ell!\\
%\times 
%[\xi^{\la_1}w^{\ell}]\,\,\frac{\xi}{1-\xi}\,\prod_r\frac{1}{\nu_r!}\left(-\frac{(1-\xi^r)\bigl(\sum_{a\in A}\binom{r}{a}w^a\bigr)}{r}\right)^{\nu_r}.
%\end{multline*}
%Call a permutation $s$ of $[N]$ admissible if the numbers of elements from $[\ell]$ 
% in each cycle of $s$ meet the constraint \eqref{ainA}. 
This identity implies
 \begin{multline}\label{sumcharadmsss1}
\chi^{\la^*}(\mathcal A)=(-1)^{\la^1}(N-\ell)!\,\ell!\\
\times 
[\xi^{\la_1}w^{\ell}]\,\,\frac{\xi}{1-\xi}\,
\underset{1\nu_1+2\nu_2+\cdots =N}{\sum_{\vec\nu:}}\prod_r\frac{1}{\nu_r!}\left(-\frac{(1-\xi^r)\bigl(\sum_{a\in A}\binom{r}{a}w^a\bigr)}{r}\right)^{\nu_r}.
\end{multline}
}The expression in the second line of  \eqref{sumcharadmsss1} equals
\begin{align}
[\xi^{\la_1}w^{\ell}x^N]& \frac{\xi}{1-\xi}\,\sum_{\vec\nu\,\ge \mathbf 0}\prod_r\frac{(x^r)^{\nu_r}}{\nu_r!}\left(-\frac{(1-\xi^r)\bigl(\sum_{a\in A}\binom{r}{a}w^a\bigr)}{r}\right)^{\nu_r}\notag\\
&=[\xi^{\la_1}w^{\ell}x^N] \frac{\xi}{1-\xi}\,\prod_r\sum_{\nu_r\ge 0}\frac{1}{\nu_r!}
\left(-\frac{x^r(1-\xi^r)\bigl(\sum_{a\in A}\binom{r}{a}w^a\bigr)}{r}\right)^{\nu_r}\notag\\
&=[\xi^{\la_1}w^{\ell}x^N] \frac{\xi}{1-\xi}\,\prod_r\exp\left(-\frac{x^r(1-\xi^r)\bigl(\sum_{a\in A}\binom{r}{a}w^a\bigr)}{r}\right)\notag\\
&=[\xi^{\la_1}w^{\ell}x^N] \frac{\xi}{1-\xi}\,\exp\left(-\sum_{r\ge 1}\frac{x^r(1-\xi^r)\bigl(\sum_{a\in A}\binom{r}{a}w^a\bigr)}{r}\right).\label{xila1wellxN}
%\\
%=[\xi^{\la_1}w^{\ell}x^N] \frac{\xi}{1-\xi}\,\frac{\bigl(1-x(1+w)\bigr)(1-\xi x)}{\bigl(1-\xi x(1+w)\bigr)(1-x)};
\end{align}
%for the last equality we used 
%\[
%\frac{x^r(1-\xi^r)\bigl((1+w)^r-1\bigr)}{r}=\bigl[x(1+w)\bigr]^r -\bigl[x\xi (1+w)\bigr]^r +(x\xi)^r -x^r,
%\]
%and the expansion $\sum_r z^r/r =-\log(1-z)$, ($|z|<1$). 
\subsection{Probability that each cycle of $\sigma$ contains at least one element of $[\ell]$}\label{A=A_1} In this case $A=A_1=\mathbb Z_{>0}$. Therefore 
\[
\sum_{a\in A}\binom{r}{a}w^a=(1+w)^r-1.
\]

In this section, we prove the following result and discuss some of its special cases. 
\begin{theorem}\label{formulaforA1}
For all positive integers $\ell$ and $k$, we have
\begin{equation} \label{equationforA1} 
p_{A_1}(N,\ell;k) = \binom{N}{\ell}^{-1}\sum_{\la_1=\ell}^N(-1)^{(k-1)(N-\la_1)}
\binom{N-1}{N-\la_1}^{-k+1}\binom{\la_1-1}{\ell-1}. \end{equation}
\end{theorem}

\begin{proof} Using \eqref{sumcharadmsss1}, \eqref{xila1wellxN} and $\sum_{j\ge 1} z^j/j=-\log(1-z)$,
$|z|<1$, we obtain 
\begin{equation}\label{sumadmisss}
\begin{aligned}
{ \chi^{\la^*}(\mathcal A)}&=(-1)^{\la^1}(N-\ell)!\,\ell!\\
&\kern1cm
\times [\xi^{\la_1}w^{\ell}x^N]\,\,\frac{\xi}{1-\xi}\,\frac{\bigl(1-x(1+w)\bigr)(1-\xi x)}{\bigl(1-\xi x(1+w)\bigr)(1-x)}.
\end{aligned}
\end{equation}
Let us simplify this formula. Write
\begin{align*}
[w^{\ell}]\frac{1-x(1+w)}{1-\xi x(1+w)}&=\frac{\xi-1}{\xi}[w^{\ell}] \frac{1}{1-\xi x(1+w)}\\
&=\frac{1-\xi}{\xi^2x}\,[w^{\ell}]\left(w-\frac{1-\xi x}{\xi x}\right)^{-1}\\
&=\frac{1-\xi}{\xi^2 x}\binom{-1}{\ell}(-1)^{-1-\ell}\left(\frac{1-\xi x}{\xi x}\right)^{-1-\ell}\\
&=-\frac{1-\xi}{\xi^2 x}\left(\frac{\xi x}{1-\xi x}\right)^{1+\ell}.
\end{align*}
Therefore 
\begin{align*}
[\xi^{\la_1}w^{\ell}x^N]\,\,\frac{\xi}{1-\xi}\,&\frac{\bigl(1-x(1+w)\bigr)(1-\xi x)}{\bigl(1-\xi x(1+w)\bigr)(1-x)}
=  -[\xi^{\la_1}x^N]\,(1-x)^{-1}\left(\frac{\xi x}{1-\xi x}\right)^{\ell}\\
 &\kern2cm
=  -[x^N]\, x^{\la_1}(1-x)^{-1}\cdot [y^{\la_1}]\left(\frac{y}{1-y}\right)^{\ell} \\
&\kern2cm
=  -[y^{\la_1-k}](1-y)^{-\ell}= -\binom{\la_1-1}{\la_1-\ell},
\end{align*}
where  $\binom{a}{b}=0$ for $b<0$. So \eqref{sumadmisss} becomes
\begin{equation}\label{sumaddexpl}
{ \chi^{\la^*}(\mathcal A)}=(-1)^{\la^1-1}(N-\ell)!\,\ell!\binom{\la_1-1}{\la_1-\ell}.
\end{equation}
Combining \eqref{sumaddexpl} and \eqref{Psigma(s)} we conclude that 
\begin{equation}\label{Pr(keverywhere)}
\begin{aligned}
p_{A_1}(N,\ell;k)
&=\frac{1}{N!}\sum_{\la^*}(-1)^{k(\la^1-1)}\binom{N-1}{\la_1-1}^{-k+1}{\! \chi^{\la^*}(\mathcal A)}\\
&=\binom{N}{\ell}^{-1}\sum_{\la_1=\ell}^N(-1)^{(k-1)(N-\la_1)}\binom{N-1}{N-\la_1}^{-k+1}\binom{\la_1-1}{\ell-1},
\end{aligned}
\end{equation}
\si
which was to be proved. 
\end{proof}

Note that as $N\to\infty$,  the dominant contribution to the right-hand side in \eqref{Pr(keverywhere)} comes from 
{$\la_1=N$, so that $p_{A_1}(N,\ell;k)=\ell/N +O(N^{-2\ell+1})$; the formula
is useful for $\ell>1$.  (Of course, $p_{A_1}(N,1;k)=P(\sigma^{(k)}\text{ is a cycle})$, see \eqref{P(cycle)gen}.)} We remark that $\ell/N$ is the exact probability that every cycle of the uniformly
random permutation of $[N]$ contains at least one element of $[\ell]$; see
\cite[Section~3, Exercise~6]{Lovasz}.

\begin{theorem} For all positive integers $\ell$, we have
\begin{equation}\label{p1Nell=expl}
\begin{aligned}
p_{A_1}(N,\ell;2)&=(-1)^{N-1}N\binom{N}{\ell}^{-1}\\
&\kern1.5cm
\times\biggl[\frac{(-1)^{\ell-1}}{(N+\ell)\binom{N+\ell-1}{\ell-1}}
+\sum_{j=0}^{\ell-1}\frac{(-1)^{N+\ell-j}\binom{N}{j}}{N+\ell-j}\biggr]\\
&=(-1)^{N+\ell}N\binom{N}{\ell}^{-1}\sum_{i=0}^{N-\ell}(-1)^i\binom{N}{i}\frac{1}{i+\ell}.
\end{aligned}
\end{equation}
%\begin{equation} \label{A1k2} 
%p_{A_1}(N,\ell;2)=(-1)^{N+\ell}N\binom{N}{\ell}^{-1}\sum_{i=0}^{N-\ell}(-1)^i\binom{N}{i}\frac{1}{i+\ell}
%\end{equation}
\end{theorem}

\begin{note} The first (respectively second) identity is computationally efficient when $\ell$ (respectively $N-\ell$) is moderately valued.
\end{note}

\begin{proof} {For the proof we need a certain binomial identity.} Introduce
\begin{equation}\label{Snabdef}
S_{n,a,b}=\sum_{r=a+b}^n (-1)^r\frac{\binom{r-a}{b}}{\binom{n}{r}}.
\end{equation}
This function is relevant since \eqref{Pr(keverywhere)} is equivalent to
\begin{equation}\label{PA1=SN-1}
p_{A_1}(N,\ell;2)=
(-1)^{N-1}\binom{N}{\ell}^{-1}S_{N-1,0,\ell-1}.
\end{equation}
As we mentioned earlier,
\begin{equation}\label{SWZ}
S_{n,0,0}=(1+(-1)^n)\,\frac{n+1}{n+2},
\end{equation}
(see \cite{Sury}, \cite{Stanley}, \cite{SWZ}), and the key element of the proofs was  identity \eqref{recbin=}.

In fact,  in \cite{Sury} the equation \eqref{recbin=} was used to derive a sum-type formula, still with $n+1$ terms, for 
\[
\sum_{r=0}^n (-1)^r\frac{x^r}{\binom{n}{r}},
\]
that yielded \eqref{SWZ} via setting $x=1$. We also use \eqref{recbin=} but avoid an intermediate 
sum with $n+1$ terms, and instead differentiate the resulting integral with respect to the 
parameter $x$. Here are the details. For $a+b\le n$, define 
\[
\cal S_{n,a,b}(x):=\sum_{r=a+b}^n(-1)^r\frac{x^{r-a}}{\binom{n}{r}}.
\]
Observe that 
$S_{n,a,b}=\tfrac{1}{b!}\left.\frac{d^b \cal S_{n,a,b}(x)}{d x^b}\right|_{x=1}$.
Now
\begin{equation}\label{cals(nax)=}
\begin{aligned}
\cal S_{n,a,b}&(x)=(n+1)\int_0^1\left(\sum_{r=a+b}^n (-1)^r x^{r-a} t^r(1-t)^{n-r}\right) dt\\
&=(n+1)(-1)^{a+b}\int_0^1t^{a+b}(1-t)^{n-a-b}x^b\sum_{r=a+b}^n \left(-\frac{xt}{1-t}\right)^{r-a-b}\, dt\\
&=(n+1)(-1)^{a+b}\int_0^1\frac{x^b+(-1)^{n-a-b}x^{n-a+1}\left(\tfrac{t}{1-t}\right)^{n-a-b+1}}{1+\tfrac{xt}{1-t}}\\
&\times t^{a+b}(1-t)^{n-a-b}\,dt.
\end{aligned}
\end{equation}
To compute $(d^b/d x^{b})\cal S_{n,a,b}(x)$ at $x=1$, we differentiate $b$ times the right-hand side of \eqref{cals(nax)=}
with respect to $x$  by carrying the operation inside the integral and then setting
$x=1$. So
\begin{multline}\label{calSn(b)}
\left.\frac{d^b\cal S(n,a,x)}{dx^b} \right|_{x=1}=(-1)^{a+b}(n+1)\\
\times \int_0^1
\frac{\partial^b}{\partial x^b}\,\frac{x^b+(-1)^{n-a-b}x^{n-a+1}\left(\tfrac{t}{1-t}\right)^{n-a-b+1}}{1+\tfrac{xt}{1-t}}
\biggr|_{x=1} t^{a+b}(1-t)^{n-a-b}\,dt.
\end{multline}
By $(uv)^{(b)}=\sum_j\binom{b}{j}u^{(j)}v^{(b-j)}$, the partial derivative at $x=1$ is 
\begin{align*}
\sum_{j=0}^b&\binom{b}{j}\left((b)_j+(-1)^{n-a-b}\left(\tfrac{t}{1-t}\right)^{n-a-b+1}(n-a+1)_j\,
\right)\\
&\kern1cm
\times (-1)^{b-j}\frac{(b-j)!}{\left(1+\tfrac{t}{1-t}\right)^{b-j+1}}\cdot\left(\frac{t}{1-t}\right)^{b-j}\\
&=\sum_{j=0}^b(-1)^{b-j}\binom{b}{j}\\
&\kern.5cm
\times\biggl[b!\, t^{b-j}(1-t)+(-1)^{n-a-b}(b-j)!\,(n-a+1)_j
\frac{t^{n-a+1-j}}{(1-t)^{n-a-b}}\biggr]\\
&=b!\left[(1-t)^{b+1} +\sum_{j=0}^b (-1)^{n-a-j}\binom{n-a+1}{j}\frac{t^{n-a+1-j}}{(1-t)^{n-a-b}}\right].
\end{align*}
Substituting the last expression in \eqref{calSn(b)} and using \eqref{recbin=} we obtain
\begin{equation}\label{sum(n,a,b)=expl}
\begin{aligned}
S_{n,a,b}&=\sum_{r=a+b}^n (-1)^r\frac{\binom{r-a}{b}}{\binom{n}{r}}
=(n+1)\biggl[\frac{(-1)^{a+b}}{(n+2+b)\binom{n+b+1}{a+b}}\\
&\kern2cm
+\sum_{j=0}^b(-1)^{n+b-j}\binom{n-a+1}{j}\frac{1}{n+2+b-j}\biggr].
\end{aligned}
\end{equation}
%For  large $n$, this formula is a significant improvement of the initial definition of $S_{n,a,b}$
%if $b$ remains moderately valued. 
Using yet another identity from \cite{SWZ}, namely
\[
\sum_{j=0}^u(-1)^j\binom{u}{j}\frac{1}{v+j+1}=\frac{1}{(u+v+1)\binom{u+v}{v}},
\] 
we transform Equation \eqref{sum(n,a,b)=expl} into
\begin{equation}\label{sum(n,a,b)=expl,2}
S_{n,a,b}=(-1)^{a+b}(n+1)\sum_{i=0}^{n-a-b}(-1)^i\binom{n-a+1}{i}\frac{1}{i+a+b+1}.
\end{equation}
%This alternative formula is efficient for the extreme case, when $n - a-b$ is moderately valued
%as $n$ grows.
So, applying Formulas \eqref{sum(n,a,b)=expl}, \eqref{sum(n,a,b)=expl,2} for $n=N-1$, $a=0$ and $b=\ell-1$, 
{and using} \eqref{PA1=SN-1}, we immediately obtain the double identity \eqref{p1Nell=expl}.
% that
%\begin{multline}\label{p1Nell=expl}
%p_{A_1}(N,\ell;2)=(-1)^{N-1}N\binom{N}{\ell}^{-1}\\
%\times\biggl[\frac{(-1)^{\ell-1}}{(N+\ell)\binom{N+\ell-1}{\ell-1}}
%+\sum_{j=0}^{\ell-1}(-1)^{N+\ell-j}\binom{N}{j}\frac{1}{N+\ell-j}\biggr]\\
%=(-1)^{N+\ell}N\binom{N}{\ell}^{-1}\sum_{i=0}^{N-\ell}(-1)^i\binom{N}{i}\frac{1}{i+\ell},
%\end{multline}
%which was to be proved. 
\end{proof}
%Note that the
%two expressions in  formula \eqref{p1Nell=expl}, we just obtained for $ p_{A_1}(N,\ell;2)$,  can be efficiently computed for moderate $\ell$ and moderate $N-\ell$, respectively.
\begin{note}  A hard-working reviewer pointed out that just equivalence of \eqref{equationforA1}  and
\eqref{p1Nell=expl} follows from  classic transformation formulas in the
theory of hypergeometric series, see \cite{GasRah}, 
\cite{Bai}. However, neither \eqref{equationforA1} 
nor \eqref{p1Nell=expl} were known before.
\end{note}

\begin{example} 
Using the first expression in \eqref{p1Nell=expl}, we obtain
\[
p_{A_1}(N,1;2)=\begin{cases}
\frac{2}{N+1},&\hbox{ if $N$ is odd},\\
0,&\hbox{ if $N$ is even.}
\end{cases} 
\] 
This is equivalent to the result already mentioned in Section~\ref{cycles}, since\break $p_{A_1}(N,1;2)$
is indeed equal to the probability that $\sigma$ is a maximal cycle.
\end{example}






%For the next few values of $\ell$, we have
% \[
%p_{A_1}(N,2;2)=\left\{ \begin{array}{l@{\ }l}
%\frac{2}{N+1} \,\,\hbox{ if $N$ is odd},\\
%\\ 
%\frac{2N}{(N+2)(N-1)} \,\, \hbox{ if $N$ is even.}
%\end{array} \right. \]
%
 %\[
%p_{A_1}(N,3;2)=\left\{ \begin{array}{l@{\ }l}
%\frac{3(N^2+N-4)}{(N+1)(N+3)(N-2)} \,\,\hbox{ if $N$ is odd},\\
%\\ 
%\frac{3N}{(N+2)(N-1)} \,\, \hbox{ if $N$ is even.}
%\end{array} \right. \]

% \[
%p_{A_1}(N,4;2)=\left\{ \begin{array}{l@{\ }l}
%\frac{4(N^2+N-3)}{(N+1)(N+3)(N-2)} \,\,\hbox{ if $N$ is odd},\\
%\\ 
%\frac{4N(N^2+N-11)}{(N-3)(N-1)(N+2)(N+4)} \,\, \hbox{ if $N$ is even.}
%\end{array} \right. \]


\subsection{Probability that the elements $1,\dots,\ell$ are in the same cycle of  $\sigma$} \label{A=A2}
This time $A=A_2=\{0,\ell\}$, so that
\begin{equation} \label{startforA2}
\sum_{a\in A_2}\binom{r}{a}w^a=1+\binom{r}{\ell}w^{\ell}.
\end{equation}

Our goal in this section is to prove the following theorem and its special case of $k=2$. 
\begin{theorem} \label{formulaforA2} For all integers $\ell \geq 2$, we have
\begin{align*}
p_{A_2}(N,\ell;k)
&=\frac{1}{N!}\sum_{\la_1=1}^N(-1)^{k(\la^1-1)}\binom{N-1}{\la_1-1}^{-k+1}\sum_{s\text{ \em admissible}}\chi^{\la^*}(s)\\
&=\frac{1}{\ell}\binom{N}{\ell}^{-1}\sum_{\la_1}(-1)^{(k+1)(\la^1-1)}\binom{N-1}{\la_1-1}^{-k+1}\\
&\kern.5cm
\times \left\{1_{\{\la_1<N\}}\left[\binom{N-1}{\ell-1}-
\binom{N-\la_1-1}{\ell-1}\right]+1_{\{\la_1=N\}}\binom{N}{\ell}\right\}.
\end{align*}
\end{theorem}


\begin{proof} By and large, the proof is similar to that in the case of $A_1$, but the computation is more involved. 
The reader may want to revisit the proofs of Formulas \eqref{sumcharadmsss1} and \eqref{xila1wellxN} before 
proceeding further. 

Formula \eqref{startforA2} implies 
\begin{equation}\label{p_2(nu,ell)}
Q_{A_2}(\vec{\nu},\ell)=(N-\ell)!\,\ell!\,\, [w^{\ell}]\prod_r\frac{1}{\nu_r!}\left(\tfrac{1+\binom{r}{\ell}w^{\ell}}{r}\right)^{\nu_r}.
\end{equation}
So, {using \eqref{sumcharadmsss1}, \eqref{xila1wellxN}} and $\nu=\sum_r\nu_r$, we conclude that
\begin{multline}\label{sumcharadmsss2}
{ \chi^{\la^*}(\mathcal A)}=(-1)^{\la^1}(N-\ell)!\,\ell!\\
\times 
[\xi^{\la_1}w^{\ell}]\,\,\frac{\xi}{1-\xi}\,
\underset{1\nu_1+2\nu_2+\cdots=N}{\sum_{\vec\nu:}}\prod_r\frac{1}{\nu_r!}\left(-(1-\xi^r)
\frac{1+\binom{r}{\ell}w^{\ell}}{r}\right)^{\nu_r}.
\end{multline}
Since $\sum_r r\nu_r=N$, using the same intermediate steps as in the proof of \eqref{xila1wellxN}, we see that 
the expression in the second line of \eqref{sumcharadmsss2} equals
\begin{multline*}
[\xi^{\la_1}w^{\ell}x^N] \frac{\xi}{1-\xi}\,\sum_{\vec\nu\,\ge \mathbf 0}\prod_r\frac{(x^r)^{\nu_r}}{\nu_r!}\left(-(1-\xi^r)\frac{1+\binom{r}{\ell}w^{\ell}}{r}\right)^{\nu_r}\\
=[\xi^{\la_1}w^{\ell}x^N] \frac{\xi}{1-\xi}\,\exp\left(-\sum_{r\ge 1}x^r(1-\xi^r)
\frac{1+\binom{r}{\ell}w^{\ell}}{r}\right).
\end{multline*}
Here, using the identities
\[
\sum_{b\ge a}\binom{b}{a}z^b = \frac{z^a}{(1-z)^{a+1}},\quad  \sum_{r>1} \frac{z^r}{r} =-\log(1-z),
\]
we obtain
\begin{align*} 
\sum_{r\ge 1}x^r(1-\xi^r)&\frac{1+\binom{r}{\ell}w^{\ell}}{r}\\
&=-\log(1-x)+\log(1-x\xi) +\frac{w^{\ell}}{\ell}\sum_{r\ge 1}\binom{r-1}{\ell-1}\bigl(x^r-(x\xi)^r\bigr)\\
&=\log\frac{1-x\xi}{1-x}+\frac{w^{\ell}}{\ell}\left(\frac{x^{\ell}}{(1-x)^{\ell}}-\frac{(x\xi)^{\ell}}{(1-x\xi)^{\ell}}
\right).
\end{align*}
Consequently, we have
\begin{multline*}
[w^{\ell}]\exp\left(-\sum_{r\ge 1}x^r(1-\xi^r)
\frac{1+\binom{r}{\ell}w^{\ell}}{r}\right)\\
=\frac{1}{\ell}\frac{1-x}{1-x\xi}\left(\frac{(x\xi)^{\ell}}{(1-x\xi)^{\ell}}-\frac{x^{\ell}}{(1-x)^{\ell}}\right).
\end{multline*}
Therefore the  expression in the second line of  \eqref{sumcharadmsss2} is equal to
\begin{align*}
\frac{1}{\ell}\,[\xi^{\la_1}x^N]\,&\frac{\xi}{1-\xi}\cdot\frac{1-x}{1-x\xi}\left(\frac{(x\xi)^{\ell}}{(1-x\xi)^{\ell}}-\frac{x^{\ell}}{(1-x)^{\ell}}\right)\\
&=\frac{1}{\ell}\,[\xi^{\la_1}x^N]\,\left(\frac{1}{1-\xi}-\frac{1}{1-x\xi}\right)
\left(\frac{(x\xi)^{\ell}}{(1-x\xi)^{\ell}}-\frac{x^{\ell}}{(1-x)^{\ell}}\right)\\
&=:\frac{1}{\ell}(T_1+T_2+T_3+T_4).
\end{align*}
\bi
Here,
\begin{equation}\label{T1=}
\begin{aligned}
T_1&=[\xi^{\la_1}x^N]\,\frac{1}{1-\xi}\cdot\frac{(x\xi)^{\ell}}{(1-x\xi)^{\ell}}\\
&=[\xi^{\la_1}]\,\frac{\xi^N}{1-\xi}\,[y^N]\frac{y^{\ell}}{(1-y)^{\ell}}
=1_{\{\la_1=N\}}\binom{N-1}{\ell-1};
\end{aligned}
\end{equation}
next
\begin{equation}\label{T2=}
\begin{aligned}
T_2&=-[\xi^{\la_1}x^N]\,\frac{1}{1-\xi}\cdot\frac{x^{\ell}}{(1-x)^{\ell}}\\
&=-[x^{N-\ell}]\,\frac{1}{(1-x)^{\ell}}=-\binom{N-1}{\ell-1};
\end{aligned}
\end{equation}
next
\begin{equation}\label{T3=}
\begin{aligned}
T_3&=-[\xi^{\la_1}x^N]\,\frac{(x\xi)^{\ell}}{(1-x\xi)^{\ell+1}}\\
&=-1_{\{\la_1=N\}}\,[y^{N-\ell}]\,\frac{1}{(1-y)^{\ell+1}}=-1_{\{\la_1=N\}}\binom{N}{\ell};
\end{aligned}
\end{equation}
and finally
\begin{equation}\label{T4=}
\begin{aligned}
T_4&=[\xi^{\la_1}x^N]\,\frac{1}{1-x\xi}\,\frac{x^{\ell}}{(1-x)^{\ell}}\\
&=[x^N]\,\frac{x^{\la_1+\ell}}{(1-x)^{\ell}}=[x^{N-\la_1-\ell}]\,\frac{1}{(1-x)^{\ell}}\\
&=1_{\{\la_1<N\}}\binom{N-\la_1-1}{\ell-1}.
\end{aligned}
\end{equation}
It follows from \eqref{T1=}, \eqref{T2=}, \eqref{T3=} and \eqref{T4=} that 
\begin{multline*}
\frac{1}{\ell}(T_1+T_2+T_3+T_4)\\
=-\frac{1}{\ell}\left\{1_{\{\la_1<N\}}\left[\binom{N-1}{\ell-1}-
\binom{N-\la_1-1}{\ell-1}\right]+1_{\{\la_1=N\}}\binom{N}{\ell}\right\}.
\end{multline*}
So \eqref{sumcharadmsss2} becomes
\begin{multline}\label{sumcharadmexpl}
\chi^{\la^*}(\mathcal A)=(-1)^{\la^1-1}(N-\ell)!\,\ell!\\
\times 
\frac{1}{\ell}\left\{1_{\{\la_1<N\}}\left[\binom{N-1}{\ell-1}-
\binom{N-\la_1-1}{\ell-1}\right]+1_{\{\la_1=N\}}\binom{N}{\ell}\right\}.
\end{multline}
Combining \eqref{sumcharadmexpl} and \eqref{Psigma(s)}, we obtain the statement that was to be 
proved. 
\end{proof}

\begin{corollary} For all integers $\ell \geq 2$, we have
\begin{equation}\label{P2Nell,final2}
\begin{aligned} 
p_{A_2}(N,\ell;2)&=\frac{1}{\ell}-\frac{1}{N(N+1)}\\
&\kern5pt
+\frac{(-1)^{\ell+1}}{\ell\binom{N}{\ell}}\left[\binom{N+\ell}{\ell}^{-1}+N\sum_{j=0}^{\ell-2}
(-1)^{N-j}\binom{N-1}{j}\frac{1}{N+\ell-j}\right]\\
&=\frac{1}{\ell}-\frac{1}{N(N+1)}\\
&\kern1cm
+(-1)^{\ell+1}\binom{N-1}{\ell-1}^{-1}\sum_{i=0}^{N-\ell}(-1)^i\binom{N-1}{i}\frac{1}{i+\ell+1}.
\end{aligned}
\end{equation}
\end{corollary}

\begin{proof} By Theorem~\ref{formulaforA2}, for $k=2$ we  have: with $r:=N-\la_1$,
\begin{equation}\label{P2Nell}
\begin{aligned}
p_{A_2}(N,\ell;2)&=\frac{1}{\ell}+\frac{1}{\ell}\binom{N}{\ell}^{-1}
\sum_{r=1}^{N-1}(-1)^{r}\\
&\kern1cm
\times\binom{N-1}{r}^{-1}\left[\binom{N-1}{\ell-1}-
\binom{r-1}{\ell-1}\right] \\
&=\frac{1}{\ell}+\frac{1}{\ell}\binom{N}{\ell}^{-1} \left[\binom{N-1}{\ell-1}S_{N-1,1,0}-S_{N-1,1,\ell-1}\right].
\end{aligned}
\end{equation}
 According to \eqref{sum(n,a,b)=expl} and \eqref{sum(n,a,b)=expl,2}, we have
\begin{align*}
S_{N-1,1,0}&=S_{N-1,0,0}-1 =\bigl[1+(-1)^{N-1}\bigr]\frac{N}{N+1}-1,\\
S_{N-1,1,\ell-1}&=(-1)^{\ell}\biggl[\binom{N+\ell}{\ell}^{-1}+N\sum_{j=0}^{\ell-1}(-1)^{N-j}\binom{N-1}{j}\frac{1}{N+\ell-j}\biggr]\\
&=(-1)^{\ell}N\sum_{i=0}^{N-1-\ell}(-1)^i\binom{N-1}{i}\frac{1}{i+\ell+1}.
\end{align*}
Substituting the expression for $S_{N-1,1,0}$ and the first expression for\break $S_{N-1,1,\ell-1}$ in \eqref{P2Nell}, we obtain after simple algebra
\begin{align}
p_{A_2}(N,\ell;2)&=\frac{1}{\ell}+\left[\frac{1+(-1)^{N-1}}{N+1}-\frac{1}{N}\right]\notag\\
&\kern0pt
+\frac{(-1)^{\ell+1}}{\ell\binom{N}{\ell}}\left[\binom{N+\ell}{\ell}^{-1}+N\sum_{j=0}^{\ell-1}
(-1)^{N-j}\binom{N-1}{j}\frac{1}{N+\ell-j}\right]\notag\\
&=\frac{1}{\ell}-\frac{1}{N(N+1)}\label{P2Nell,final*}\\
&\kern0pt
+\frac{(-1)^{\ell+1}}{\ell\binom{N}{\ell}}\left[\binom{N+\ell}{\ell}^{-1}+N\sum_{j=0}^{\ell-2}
(-1)^{N-j}\binom{N-1}{j}\frac{1}{N+\ell-j}\right].\notag
\end{align}
(The term $(-1)^{N-1}/(N+1)$ and the $(\ell-1)$-th term in the sum over $j$ cancelled each other.) Using the second expression for $S_{N-1,1,\ell-1}$, we obtain the alternative formula
\begin{equation}\label{P2Nell,fin}
\begin{aligned}
p_{A_2}(N,\ell;2)&=\frac{1}{\ell}-\frac{1}{N(N+1)}\\
&\kern1cm
+(-1)^{\ell+1}\binom{N-1}{\ell-1}^{-1}\sum_{i=0}^{N-\ell}(-1)^i\binom{N-1}{i}\frac{1}{i+\ell+1}.\quad \qedhere
\end{aligned} 
\end{equation}
\end{proof}

The equivalent  formulas \eqref{P2Nell,final*} and \eqref{P2Nell,fin} are computationally efficient
for moderate $\ell$ and moderate $N-\ell$, respectively.
In particular, plugging $\ell=2,3$ into \eqref{P2Nell,final*} and simplifying, we recover Stanley's results \cite{Stanley2}.

%\[
%p_{A_2}(N,2;2)=\left\{ \begin{array}{l@{\ }l}
%\frac{1}{2} \,\,\hbox{ if $N$ is odd},\\
%\\ 
%\frac{1}{2}-\frac{2}{(N-1)(N+2)} \,\, \hbox{ if $N$ is even,}
%\end{array} \right.
%\]
%and
%\[
%p_{A_2}(N,3;2)=\left\{ \begin{array}{l@{\ }l}
%\frac{1}{3}+\frac{1}{(N-2)(N+3)} \,\,\hbox{ if $N$ is odd},\\
%\\ 
%\frac{1}{3}-\frac{1}{(N-1)(N+2)} \,\, \hbox{ if $N$ is even.}
%\end{array} \right.
%\]
%Here are the new formulas for $\ell=4,5$ obtained from \eqref{P2Nell,final}:
%denoting $(a)^{(b)}=a(a+1)\cdots (a+b-1)$,
%\[
%p_{A_2}(N,4;2)=\left\{ \begin{array}{l@{\ }l}
%\frac{1}{4}+\frac{2}{(N)^{(2)}-(2)^{(2)}}\,\, \hbox{ if $N$ is odd},\\
%\\
%\frac{1}{4}-\frac{-4(N)^{(2)}+44}{[(N)^{(2)}-(1)^{(2)}]\,[(N)_2-(3)_2]} \,\,\hbox{ if $N$ is even.}
%\end{array} \right.
%\]
%and
%\[
%p_{A_2}(N,5;2)=\left\{ \begin{array}{l@{\ }l}
%\frac{1}{5}+\frac{5(N)^{(2)}-50}{[(N)^{(2)}-(2)^{(2)}]\cdot [(N)^{(2)}-(4)^{(2)}]} \,\, \hbox{ if $N$ is odd}, \\
%\\
%\frac{1}{5}+\frac{-5(N)^{(2)}+50}{[(N)^{(2)}-(1)^{(2)}]\,[(N)^{(2)}-(3)^{(2)}]}\,\,\hbox{ if $N$ is even.}
%\end{array} \right.
%\]
% While the denominators certainly follow a simple pattern, the numerators do not exhibit
%a discernibly regular behavior, except that they are also polynomials of $(N)^{(2)}$.

\section{The probability that $\sigma$ separates the disjoint sets ${\cal S}_1,\dots,{\cal S}_t$} \label{separate}
{Let ${\cal S}_1,\dots, {\cal S}_t$ be disjoint subsets of $[N]$.} Let $\ell_j=|{\cal S}_j|$, $1\le j\le t$, $\ell=\sum_j\ell_j$. Introduce $p(N,\vec\ell;k)$, the probability that the permutation $\sigma$ separates the sets ${\cal S}_1,\dots,
{\cal S}_t$, meaning that no cycle of $\sigma$ contains a pair of elements from two distinct sets ${\cal S}_i$ and ${\cal S}_j$. 
 Bernardi et al.\ \cite{Bernardi} were able to derive a striking formula for $p(N,\vec\ell;2)$:
\begin{equation}\label{bern}
p(N,\vec\ell;2)=\frac{(N-\ell)!\prod_j\ell_j!}{(N+t)(N-1)!}
\left[\frac{(-1)^{N+\ell}\binom{N-1}{t-2}}{\binom{N+\ell}{\ell-t}}+\sum_{j=0}^{\ell-t}
\frac{(-1)^j\binom{\ell-t}{j}\binom{N+j+1}{\ell}}{\binom{N+t+j}{j}}\right],
\end{equation}
which is a sum of $\ell-t+2$ terms. Remarkably, $\prod_j\ell_j!$ aside, the rest of this expression 
does not depend on the individual $\ell_j$. Equation \eqref{bern} is very efficient for 
values of $\ell$, $t$ relatively small compared to $N$.


{In this section, we apply first our approach to obtain a formula for $p(N,\vec\ell;k)$ when $k\ge 2$.
%Similarly to $p(N,\vec\ell;2)$, it is of a form $\prod_j\ell_j!$ times an expression that
%depends on $\ell$ { and $t$}, but not on individual $\ell_j$. 
\begin{theorem}\label{generalk} Introduce
\[
K(N,\ell,t;r)=\bigl[\xi^{r-\ell+t}\eta^{N-\ell}\bigr] \left(\frac{1-\xi}{1-\eta}\right)^{t-1}(1-\xi\eta)^{-\ell-1},
\]
and define $\alpha_k(N,t)=t-1$ if $k$ is odd, and $\alpha_k(N,t)=N+t$ if $k$ is even. Then 
\begin{equation}\label{Pr(separ)}
p(N,\vec\ell;k)=\frac{(-1)^{\alpha_k(N,t)}\prod_j\ell_j!}{(N)_{\ell}}\sum_{r=\ell-t}^{N-1}
(-1)^{(k+1)r} \binom{N-1}{r}^{-k+1}K(N,\ell,t;r),
\end{equation} 
i.e., $p(N,\vec\ell;k)$ is $\prod_j\ell_j!$ times a factor dependent on $\ell$ and $t$. Consequently, the probability that the cycles of the product of $k$ random cycles of length $N$ partition the set of cardinality $\ell$ into $t$ subsets is given by
\begin{align*}
p(N,\ell,t;k)&=\frac{(-1)^{\alpha_k(N,t)}\binom{\ell-1}{t-1}}{t!\,(N)_{\ell}}
\sum_{r=\ell-t}^{N-1}(-1)^{(k+1)r} \binom{N-1}{r}^{-k+1}K(N,\ell,t;r).
\end{align*}
\end{theorem}
}%

Formula \eqref{Pr(separ)} is computationally efficient for $\ell - t$ close to $N$.
\begin{proof} {Let $\mathcal A(\vec\ell\,)$ denote the set of all permutations that separate the sets
 ${\cal S}_1,\dots,{\cal S}_t$, and let $\mathcal A(\vec\nu,\vec\ell\,)=\{s\in \mathcal A(\vec\ell\,): \vec\nu(s)=\vec\nu\}$, $Q(\vec\nu,\vec\ell\,)=|\mathcal A(\vec\nu,\vec\ell\,)|$.}
 %denote the total number of permutations of $[N]$ with
%cycle counts $\vec\nu=(\nu_1,\nu_2,\dots)$ that separate ${\cal S}_1,\dots,{\cal S}_t$.
Each cycle of such a permutation either does not contain any element of $\bigcup_j {\cal S}_j$, or
contains some of the elements of exactly one set ${\cal S}_j$. Since\break $\left|[N]\setminus \bigcup_j{\cal S}_j\right|=N-\ell$, denoting $\prod_jw_j^{\ell_j}=\vec w\,^{\vec\ell}$,
analogously to \eqref{p(nu,ell)} we have
\begin{equation}\label{QNboldell}
\begin{aligned}
\frac{Q(\vec\nu,\vec\ell\,)}
{(N-\ell)!\,\prod_j\ell_j!}&=\,[y^{N-\ell}\vec w\,^{\vec\ell}\,]\left[\prod_r\frac{1}{\nu_r!}\left(\frac{y^r+\sum_{j=1}^t\sum_{a>0}\binom{r}{a}w_j^ay^{r-a}}{r}\right)^{\nu_r}\right]\\
&=\,[y^{N-\ell}\vec w\,^{\vec\ell}\,]\left[\prod_r\frac{1}{\nu_r!}\left(\frac{-(t-1)y^r+
\sum_{j=1}^t(w_j+y)^r}{r}\right)^{\nu_r}\right].
\end{aligned}
\end{equation}
(The interested reader may wish to check this identity by following the steps of the proof of
\eqref{p(nu,ell)}.) Using 
\eqref{QNboldell}, we obtain
\begin{multline}\label{sumcharadmsss}
\chi^{\la^*}(\mathcal A(\vec\ell\,))=(-1)^{\la^1}(N-\ell)!\, \prod_j \ell_j!\\
\times 
[\xi^{\la_1}y^{N-\ell}\vec w\,^{\vec\ell}]\,\,\frac{\xi}{1-\xi}\,\sum_{\vec\nu}
\prod_r\frac{1}{\nu_r!}\\
\times\left(-\frac{(1-\xi^r)\bigl(-(t-1)y^r+\sum_j(w_j+y)^r\bigr)}{r}\right)^{\nu_r},
\end{multline}
the sum being for $\vec\nu\,\ge \mathbf 0$ with $\sum_r r\nu_r=N$.  So the  expression in the second line of
 \eqref{sumcharadmsss} equals {
\begin{align*}
&[\xi^{\la_1}x^N y^{N-\ell}\vec w\,^{\vec\ell}] \frac{\xi}{1-\xi}\sum_{\vec\nu\,\ge \mathbf 0}\prod_r\frac{(x^r)^{\nu_r}}{\nu_r!}\\
&\kern4cm
\times\left(-\frac{(1-\xi^r)\bigl[-(t-1)y^r+\sum_j(w_j+y)^r\bigr]}{r}\right)^{\nu_r}\\
&=\,[\xi^{\la_1}x^Ny^{N-\ell}\vec w\,^{\vec\ell}\,] \frac{\xi}{1-\xi}\\
&\kern2cm
\times\prod_r\exp\left(-\frac{x^r(1-\xi^r)
\bigl[-(t-1)y^r+\sum_{j=1}^t(w_j+y)^r\bigr]}{r}\right).
\end{align*}
Using $\prod_{r\ge 1} \exp(-\eta^r/r)=1-\eta$, ($|\eta|<1$), we transform the last product into
\[
\left(\frac{1-\xi xy}{1-xy}\right)^{t-1}\prod_{j=1}^t\frac{1-x(w_j+y)}{1-\xi x(w_j+y)}.
\]
Further
\begin{align*}
[\vec w\,^{\vec\ell}\,]\prod_{j=1}^t&\frac{1-x(w_j+y)}{1-\xi x(w_j+y)}=\left(\frac{1-xy}{1-\xi xy}\right)^{t}
\cdot\prod_{j=1}^t [w_j^{\ell_j}]\frac{1-\tfrac{xw_j}{1-xy}}{1-\tfrac{\xi x w_j}{1-\xi xy}}\\
&=\left(\frac{1-xy}{1-\xi xy}\right)^{t}\prod_{j=1}^t\left[\left(\frac{\xi x}{1-\xi xy}\right)^{\ell_j}-\frac{x}{1-xy}\left(\frac{\xi x}{1-\xi xy}\right)^{\ell_j-1}\right]\\
&=\left(\frac{1-xy}{1-\xi xy}\right)^{t}\left(\frac{\xi x}{1-\xi xy}\right)^{\ell-t}\left(\frac{(\xi-1)x}{(1-\xi xy)(1-xy)}\right)^t\\
&=\frac{(\xi x)^{\ell-t} x^t (\xi-1)^t}{(1-\xi xy)^{\ell+t}}.
\end{align*}
So we need
\begin{align*}
[\xi^{\la_1} x^N &y^{N-\ell}]\frac{\xi}{1-\xi}\left(\frac{1-\xi xy}{1-xy}\right)^{t-1}\frac{(\xi x)^{\ell-t} x^t (\xi-1)^t}{(1-\xi xy)^{\ell+t}}\\
&=(-1)^t [\xi^{\la_1-1-(\ell-t)}x^{N-\ell} y^{N-\ell}] (1-\xi)^{t-1}(1-xy)^{-t+1} (1-\xi xy)^{-\ell-1}\\
&=(-1)^t [\xi^{\la_1-1-(\ell-t)}z^{N-\ell}]\left(\frac{1-\xi}{1-z}\right)^{t-1}(1-\xi z)^{-\ell-1}\\
&=(-1)^t K(N,\ell,t; r), \quad r:=\la_1-1-(\ell-t).
\end{align*}
%\begin{align*}
%=&\,[\xi^{\la_1}x^Ny^{N-\ell}] \frac{\xi}{1-\xi}\,\left(\frac{1-\xi xy}{1-xy}\right)^{t-1}\left(\frac{1-xy}{1-\xi xy}\right)^{t}
%\cdot\prod_{j=1}^t [w_j^{\ell_j}]\frac{1-\tfrac{xw_j}{1-xy}}{1-\tfrac{\xi x w_j}{1-\xi xy}}\\
%=&\,[\xi^{\la_1}x^Ny^{N-\ell}] \frac{\xi}{1-\xi}\,\frac{1-xy}{1-\xi xy}
%\prod_j\left[\left(\frac{\xi x}{1-\xi xy}\right)^{\ell_j}-\frac{x}{1-xy}\left(\frac{\xi x}{1-\xi xy}\right)^{\ell_j-1}\right]\\
%=&\,[\xi^{\la_1}x^Ny^{N-\ell}] \frac{\xi}{1-\xi}\,\frac{1-xy}{1-\xi xy}\left(\frac{\xi x}{1-\xi xy}\right)
%^{\ell-t}\left(\frac{(\xi-1)x}{(1-\xi xy)(1-xy)}\right)^t\\
%=&(-1)^{t}\,[\xi^{\la_1-1-(\ell-t)}x^{N-\ell}y^{N-\ell}](1-\xi)^{t-1}(1-xy)^{-t+1}(1-\xi xy)^{-\ell-1}\\
%=:&\,(-1)^{t} K(N,\ell,t;\la_1-1).
%\end{align*}
%Thus, $\xi$ aside, we need to extract a coefficient of $(xy)^{N-\ell}$ from a power series of $xy$.  
Here}
\begin{equation}\label{K=}
\begin{aligned}
K(N,\ell,t;r)&=[\xi^{r-\ell+t}z^{N-\ell}]\,\left(\frac{1-\xi}{1-z}\right)^{t-1}(1-\xi z)^{-\ell-1}\\
&=\sum_j(-1)^{r-\Delta-j}\binom{\ell+j}{j}\binom{t-1}{r-\Delta-j}\binom{N-\Delta-j-2}{t-2},
\end{aligned}
\end{equation}
where we set $\Delta=\ell-t$. Obviously $K(N,\ell,t;r)=0$ for $r<\ell-t$, and less obviously for $r\ge N$. Indeed,
\begin{multline}\label{r>N}
[z^{N-\ell}]\,(1-\xi)^{t-1}(1-z)^{-t+1}(1-\xi z)^{-\ell+1}\\
=\sum_{j\le N-\ell}(-1)^{N-\ell-j}\binom{-t+1}{N-\ell-j}\,[z^j](1-\xi)^{t-1}(1-\xi z)^{-\ell-1},
\end{multline}
and the $[z^j]$-factor is a polynomial of $\xi$ of degree $t-1+j\le t-1+N-\ell< r-\ell+t$ if $r\ge N$.

So Equation \eqref{sumcharadmsss} becomes
\begin{equation*}
\chi^{\la^*}(\mathcal A(\vec\ell\,))=(-1)^{\la^1+t}(N-\ell)!\, \Biggl(\prod_{j=1}^t \ell_j!\Biggr) K(N,\ell, t; r).
\end{equation*}
Combining this with  Equation \eqref{Psigma(s)}, and $\la_1+\la^{1}=N+1$, we obtain the statement that was
to be proved.
\end{proof}

Notice that
\[
K(N,N,t;r)=[\xi^{r-N+t}](1-\xi)^{t-1}=(-1)^{r-N+t}\binom{t-1}{r-N+t}.
\]
Let $\ell=\sum_j\ell_j=N$.  Introducing $\beta_k(N)=N-1$ for $k$ odd, $\beta_k(N)=0$ for $k$ even,  we transform  \eqref{Pr(separ)} into
\[
p(N,\vec\ell;k)=
\frac{(-1)^{\beta_k(N)}\prod_j\ell_j!}{N!}
\sum_{r=N-t}^{N-1}
(-1)^{kr} \binom{N-1}{r}^{-k+1}\binom{t-1}{r-N+t},
\]
an alternating sum of $t$ terms. For $t=N$, note that $\ell_i=1$ for all $i$, and that $p(N,\vec\ell;k)=\pr(\sigma=\text{id})$. The resulting
formula agrees with \eqref{Pr(id)=}, since for $k$ odd and $N$ even the sum over $r\in [0,N-1]$
is zero.

\subsection{The case of $k=2$}
From now on we focus on $k=2$, and general $\vec\ell$. We begin with a relatively compact
formula that represents $p(N,\vec\ell;2)$ as a composition of one-dimensional integration operation and coefficient extraction operation applied to a bivariate rational function.

\begin{theorem} Recalling the notation $(a)_b=a(a-1)\cdots(a-b+1)$, we have
\begin{equation}\label{Psep,k=2,equation}
\begin{aligned}
p(N,\vec\ell;2)&=\frac{(-1)^{N+\ell}N\prod_j\ell_j!}{(N)_{\ell}}\\
&\kern1cm
\times [z^{N-\ell}] (1-z)^{-t+1}
\int_0^1\frac{(1-u)^{N+1}u^{\ell-t}}{(1-u+zu)^{\ell+1}}\,du.
\end{aligned}
\end{equation}
\end{theorem} 

\begin{proof}
{For $k=2$}, Equation \eqref{Pr(separ)}
 becomes
\begin{align}
p(N,\vec\ell;2)
&=\frac{(-1)^{N+t}\prod_j\ell_j!}{(N)_{\ell}}\sum_{r=\ell-t}^{N-1}(-1)^{r} \binom{N-1}{r}^{-1}K(N,\ell,t;r),
\label{Pr(separ),k=2}
\end{align}
where, by Lemma~\ref{generalk},
\[
K(N,\ell,t;r)=\bigl[\xi^{r-\ell+t}\eta^{N-\ell}\bigr]\,\left(\frac{1-\xi}{1-\eta}\right)^{t-1}(1-\xi\eta)^{-\ell-1}.
\]
In \eqref{Pr(separ),k=2} we can extend the summation to $r\in [\ell-t,\infty)$, since
$K(N,\ell,t;r)=0$ for $r\ge N$.
Using this observation  and \eqref{recbin=}, we first evaluate 
%firstNow we are going to extract the coefficient of $\xi^{r-\ell+t}$ from the expression for $K(N,\ell,t:r)$ as follows: 
\begin{align}\label{sumreduced}
\sum_{r=\ell-t}^{N-1}&(-1)^r\binom{N-1}{r}^{-1}[\xi^{r-\ell+t}]\,(1-\xi)^{t-1}(1-\xi z)^{-\ell-1}\\
\notag
&=
N\sum_{r=\ell-t}^{\infty}(-1)^r [\xi^{r-\ell+t}]\,\frac{(1-\xi)^{t-1}}{(1-\xi z)^{\ell+1}}
\int_0^1u^r(1-u)^{N-1-r}\,du\\
\notag
&=N\int_0^1(1-u)^{N-1}\left(\sum_{r=\ell-t}^{\infty}\left(-\frac{u}{1-u}\right)^r\,[\xi^{r-\ell+t}]
\frac{(1-\xi)^{t-1}}{(1-\xi z)^{\ell+1}}
\right)\,du\\
\notag
&=N\int_0^1(1-u)^{N-1}\left(-\frac{u}{1-u}\right)^{\ell-t}\left(\sum_{r=\ell-t}^{\infty}[\xi^{r-\ell+t}]
\frac{(1+\xi\,\tfrac{u}{1-u})^{t-1}}{(1+\xi z\,\tfrac{u}{1-u})^{\ell+1}}\right)\,du\\
\notag
&=N\int_0^1(1-u)^{N-1}\left(-\frac{u}{1-u}\right)^{\ell-t}\left.\frac{(1+\xi\,\tfrac{u}{1-u})^{t-1}}{(1+\xi z\,\tfrac{u}{1-u})^{\ell+1}}\right|_{\xi=1}\,du\\
\notag
&=(-1)^{\ell-t}N\int_0^1\frac{(1-u)^{N+1}u^{\ell-t}}{(1-u+zu)^{\ell+1}}\,du;
\end{align}
(in the fifth line we used $\sum_{r\ge 0} [\xi^r] f(\xi) =f(1)$ for the series $f(\xi)=\break\sum_{r\ge 0} a_r\xi^r$).
So \eqref{Pr(separ),k=2} is transformed into \eqref{Psep,k=2,equation}.
%\begin{equation}\label{Psep,k=2,transform}
%\begin{aligned}
%p(N,\vec\ell;2)=&\frac{(-1)^{N+\ell}N\prod_j\ell_j!}{(N)_{\ell}}\\
%&\times [z^{N-\ell}] (1-z)^{-t+1}
%\int_0^1\frac{(1-u)^{N+1}u^{\ell-t}}{(1-u+zu)^{\ell+1}}\,du ,
%\end{aligned}
%\end{equation} which is the formula that was to be proved. 
\end{proof}


\begin{corollary} For $\ell=N$, Formula \eqref{Psep,k=2,equation} yields
\begin{equation}\label{Psep,k=2,ell=N}
p(N,\vec\ell;2)=\frac{N\prod_j\ell_j!}{N!}\,\int_0^1u^{N-t}\,du=
\frac{\prod_j\ell_j!}{(N-1)!\,(N-t+1)}.
\end{equation}
\end{corollary}

To compare, the separation probability for a uniformly random permutation of $[N]$ is 
$\prod_j\ell_j!/N!$.

For $\ell_1=\cdots=\ell_{t-1}=1$, $\ell_t=N-t+1$, ($2\le t\le N$),  $p(N,\vec\ell;2)$ is the probability that all elements of a given subset of cardinality $t-1$ are fixed points of $\sigma^{(2)}$; the number of such subsets is $\binom{N}{t-1}$. Furthermore the probability that all the elements of $[N]$
are fixed, i.e., $\sigma^{(2)}=\text{id}$, is  $\tfrac{1}{(N-1)!}$, see \eqref{P(sigma2isid)}. So using the inclusion-exclusion formula, we obtain:
\[
\pr(\sigma^{(2)}\text{ is a derangement})=N\sum_{\tau=0}^{N-1}\frac{(-1)^{\tau}}{(N-\tau)\tau!}
+\frac{(-1)^N}{(N-1)!}.
\]
For comparison, the probability that a uniformly random permutation of $[N]$ is
a derangement equals  $\sum_{\tau=0}^N(-1)^{\tau}\tfrac{1}{\tau!}$.

More generally, if in \eqref{Psep,k=2,equation} we take the factor $(1-z)^{-t+1}$ inside the integral, and perform
extraction of the coefficient of $z^{N-\ell}$ from the resulting integrand, then we end up with an alternating-sign sum
of the beta integrals and obtain an explicit formula
\begin{equation}\label{Psep,k=2,N-ellsmall}
p(N,\vec\ell;2)=\frac{N\prod_j\ell_j!}{(N)_{\ell}}\sum_{k\le N-\ell}(-1)^k
\frac{\binom{t+k-2}{t-2}\binom{N-k}{\ell}}{(N-t+1)\binom{N-t}{k}}.
\end{equation}
This expression is computationally efficient for moderate $N-\ell$, but progressively less useful for larger values of $N-\ell$.

\subsection{An alternative formula deduced by the Gosper--Zeilberger algorithm}
In this section, we will show that Equation \eqref{Psep,k=2,equation} can be transformed so that
extraction of the coefficient of $z^{N-\ell}$ will lead to a sum with $\ell-t+2$ number of terms,
close in appearance to the formula \eqref{bern} by Bernardi et al. 

Clearly it is the outside factor $(1-z)^{-t+1}$ that causes the number of summands in 
\eqref{Psep,k=2,N-ellsmall} grow indefinitely with $N$.  To get rid
of $(1-z)^{-t+1}$, we resort to repeated integration by parts  of the integral, (denote it $I(z)$), with each step producing the outside factor $1-z$. However the factor $u^{\ell-t}$ in the integrand of $I(z)$ would have made the integration process unwieldy; so we apply it instead to $K_1(z)$, where
\[
K_{\nu}(z):=\int_0^1\frac{(1-u)^{N+\nu}}{(1-u+zu)^{t+\nu}}\,du,
\]
because 
\begin{equation}\label{I(through)K1}
I(z)=\frac{(-1)^{\ell-t}}{(t+1)^{(\ell-t)}}\,\frac{d^{\ell-t}K_1(z)}{dz^{\ell-t}}.
\end{equation}
One integration by parts leads to 
\begin{align*}
K_1(z)&=\frac{1}{N+2}+\frac{(t+1)(1-z)}{N+2}\int_0^1\frac{(1-u)^{N+2}}{(1-u+zu)^{t+2}}\,du\\
&=\frac{1}{N+2}+\frac{(t+1)(1-z)}{N+2}K_2(z).
\end{align*}
A clear pattern emerges here. Let us denote by $a^{(b)}$ the rising factorial $a(a+1)\cdots(a+b-1)$. After $\ell-1$ integrations by parts, we get
\begin{equation*}
K_1(z)=\sum_{j=1}^{\ell-1}\frac{(t+1)^{(j-1)}}{(N+2)^{(j)}}(1-z)^{j-1}
+\frac{(t+1)^{(\ell-1)}}{(N+2)^{(\ell-1)}}\,(1-z)^{\ell-1} K_{\ell}(z).
\end{equation*}
So, using \eqref{I(through)K1} and
\[
\frac{d^{\ell-t}\bigl[(1-z)^{\ell-1}K_{\ell}\bigr]}{dz^{\ell-t}}=\sum_{\mu=0}^{\ell-t}
(-1)^{\mu}\binom{\ell-t}{\mu}(\ell-1)_{\mu}(1-z)^{\ell-1-\mu}\frac{d^{\ell-t-\mu} K_{\ell}}{dz^{\ell-t-\mu}},
\]
we obtain
\begin{multline*}
(1-z)^{-t+1}I(z)\frac{(t+1)^{\ell-t}}{(-1)^{\ell-t}}
=\,(-1)^{\ell-t}\sum_{j=1}^{\ell-1}\frac{(t+1)^{(j-1)}(j-1)_{\ell-t}}{(N+2)^{(j)}}(1-z)^{j-\ell}\\
+\frac{(t+1)^{(\ell-1)}}{(N+2)^{(\ell-1)}}\sum_{\mu=0}^{\ell-t}(-1)^{\mu}\binom{\ell-t}{\mu}(\ell-1)_{\mu}(1-z)^{\ell-t-\mu}
\,\frac{d^{\ell-t-\mu} K_{\ell}(z)}{dz^{\ell-t-\mu}}.
\end{multline*}
It remains to extract the coefficient of $[z^{N-\ell}]$ in the right-hand side expression. First,
\[
[z^{N-\ell}](1-z)^{j-\ell}=(-1)^{N-\ell}\binom{j-\ell}{N-\ell}.
\]
Next, for every $r\ge 0$,
\begin{align*}
[z^r]&\frac{d^{\ell-t-\mu} K_{\ell}}{dz^{\ell-t-\mu}}= (-1)^{\ell-t-\mu}(t+\ell)^{(\ell-t-\mu)}[z^r]
\int_0^1\frac{(1-u)^{N+\ell}u^{\ell-t-\mu}}{(1-u+zu)^{2\ell-\mu}}\,du\\
&=\,(-1)^{\ell-t-\mu}(t+\ell)^{(\ell-t-\mu)}\binom{-2\ell+\mu}{r} \int_0^1(1-u)^{N-\ell+\mu-r}u^{\ell-t-\mu+r}\,du\\
&=\,(-1)^{\ell-t-\mu}\frac{(t+\ell)^{(\ell-t-\mu)}\binom{-2\ell+\mu}{r}}
{(N-t+1)\binom{N-t}{\ell-t-\mu+r}}.
\end{align*}
So
\begin{equation}\label{k-sum}
\begin{aligned}
&[z^{N-\ell}]\,\left\{(1-z)^{\ell-t-\mu}\,\frac{d^{\ell-t-\mu}\, K_{\ell}}{dz^{\ell-t-\mu}}\right\}\\
&\quad 
=\sum_{k\le \ell-t-\mu} \left\{[z^k] (1-z)^{\ell-t-\mu}\right\}\,\left\{[z^{N-\ell-k}]\,\frac{d^{\ell-t-\mu}\, K_{\ell}}{dz^{\ell-t-\mu}}\right\}\\
&\quad 
=\sum_{k\le \ell-t-\mu}(-1)^k\binom{\ell-t-\mu}{k}
\left.(-1)^{\ell-t-\mu}\frac{(t+\ell)^{(\ell-t-\mu)}\binom{-2\ell+\mu}{r}}
{(N-t+1)\binom{N-t}{\ell-t-\mu+r}}\right|_{r=N-\ell-k}.
\end{aligned}
\end{equation}
Collecting the pieces,
\begin{align*}
[z^{N-\ell}]&(1-z)^{-t+1}I(z)\frac{(t+1)^{\ell-t}}{(-1)^{\ell-t}}\\
&=(-1)^{N-t}\sum_{j=1}^{\ell-1}\frac{(t+1)^{(j-1)}(j-1)_{\ell-t}}{(N+2)^{(j)}}\binom{j-\ell}{N-\ell}\\
&\kern1cm
+(-1)^{\ell-t}\frac{(t+1)^{(\ell-1)}}{(N+2)^{(\ell-1)}}\sum_{\mu=0}^{\ell-t}\binom{\ell-t}{\mu}(\ell-1)_{\mu}(t+\ell)^{(\ell-t-\mu)}\\
&\kern2cm
\times\sum_{k\le \ell-t-\mu} (-1)^k\binom{\ell-t-\mu}{k}
\frac{\binom{-2\ell+\mu}{N-\ell-k}}
{(N-t+1)\binom{N-t}{\mu+k}}.
\end{align*}
So, since 
\[
\binom{-a}{b}=(-1)^b\binom{a+b-1}{a-1},\quad\frac{(t+1)^{(\ell-1)}(t+\ell)^{(\ell-t-\mu)}}{(t+1)^{(\ell-t)}}
=\frac{(2\ell-\mu-1)!}{\ell!},
\]
Equation \eqref{Psep,k=2,equation} becomes
\begin{equation}\label{pnell2=final?}
\begin{aligned}
p(N,&\vec\ell;2)=\frac{N\prod_j\ell_j!}{(N)_{\ell}}\\
&\kern1cm
\times
\left[(-1)^{N+\ell}\sum_{j=1}^{\ell-1}\frac{(t+1)^{(j-1)}(j-1)_{\ell-t}}{(t+1)^{(\ell-t)}(N+2)^{(j)}}
\binom{N-j-1}{\ell-j-1}\right.\\
&+\frac{1}{\ell! (N+2)^{(\ell-1)}(N-t+1)}\\
&\quad 
\times\left.\sum_{\mu=0}^{\ell-t}\binom{\ell-t}{\mu}(\ell-1)_{\mu}
\sum_{\nu=\mu}^{\ell-t} \binom{\ell-t-\mu}{\ell-t-\nu}
\frac{(N+\ell-\nu-1)_{2\ell-\mu-1}}
{\binom{N-t}{\nu}}\right];
\end{aligned}
\end{equation}
$\nu$ in the bottom sum comes from substitution $\nu=k+\mu$ in \eqref{k-sum}. Changing the
 order of summation, the double sum above equals
\begin{multline}\label{doublesum=}
\frac{(\ell-t)!}{(N-\ell)!}\sum_{\nu=0}^{\ell-t}\frac{(N+\ell-\nu-1)!}{(\ell-t-\nu)!}\frac{1}{\binom{N-t}{\nu}}
\sum_{\mu=0}^{\nu}\binom{\ell-1}{\mu}\binom{N-\ell}{\nu-\mu}\\
=\frac{(\ell-t)!}{(N-\ell)!}\sum_{\nu=0}^{\ell-t}\frac{(N+\ell-\nu-1)!}{(\ell-t-\nu)!}\,\frac{\binom{N-1}{\nu}}
{\binom{N-t}{\nu}}.
\end{multline}
Let $\Sigma(N,\ell,t)$ denote the sum over $j$ in \eqref{pnell2=final?}.

\begin{lemma} We have   
\begin{equation}\label{ell-t=1}
\Sigma(N,\ell,t)=\frac{(N-1)_{t-2}\,(\ell-t)!}{(t-2)!\,(N+t)^{(\ell-t+1)}}.
\end{equation}
\end{lemma} 

\begin{proof} 
We confirmed this conjecture via the powerful Gosper--Zeilberger algorithm, 
\cite[Chapters~5 and~6]{petkovsek}, \cite{WZ1}.
  Given $\Delta\ge 0$, introduce a function of $t\ge 2$, defined by
\[
S(t)=\sum_{j=1}^{t-1+\Delta}\frac{(t+1)^{(j-1)}(j-1)_{\Delta}}{(t+1)^{(\Delta)}(N+2)^{(j)}}\binom{N-j-1}
{t+\Delta-j-1}.
\]
The non-zero summands are those for $j\in [\Delta+1, t-1+\Delta]$.  We can extend summation to $j\in [1,\infty)$, since the last binomial is zero for $j\ge t+\Delta$. We need to show that
\begin{equation}\label{S=S*}
S(t)=S^*(t):=\frac{(N-1)_{t-2}\Delta!}{(t-2)!\,(N+t)^{(\Delta+1)}}.
\end{equation}
To do so, first we compute
\begin{align*}
&\,\quad\frac{S^*(t)}{S^*(t-1)}=\frac{\beta(t)}{\alpha(t)},\\
\alpha(t):=(t-2)&(N+t+\Delta),\quad \beta(t):=(N-t+2)(N+t-1).
\end{align*}
Next, let $F(t,j)$ stand for the $j$-term in the series $S(t)$. Introduce the ``partner'' sequence $G(t,j)$ (which again for each $t$ is $0$ for all but finitely many $j$) such that
\begin{equation}\label{Grecur}
G(t,j)-G(t,j-1)=\alpha(t)F(t,j) -\beta(t)F(t-1,j),\quad j\ge \Delta+1,
\end{equation}
and $G(t,\Delta)=0$. 

Equation \eqref{S=S*} will be proved if we demonstrate that
$G(t,j)=0$ for $j$ large enough. 

Such a sequence $G(t,j)$ can be found either by Gosper's algorithm, interpreted  by Doron Zeilberger's {\sl Maple} package EKHAD \cite{Zeilberger},
or without Gosper's algorithm  as we show below. 

Using \eqref{Grecur} and the initial condition and $G(t,\Delta)=0$,  we compute by hand and by {\sl Maple}  that 
\begin{align*}
G(t,\Delta+1)&=-\frac{(\Delta+1)!\,(\Delta+2t-2)}{(N+2)^{(\Delta+1)}}\binom{N-\Delta-2}{t-3},\\
G(t,\Delta+2)&=-\frac{(\Delta+2)!\,(\Delta+2t-2)(t+\Delta+1)}{(N+2)^{(\Delta+2)}}\binom{N-\Delta-3}{t-4},\\
G(t,\Delta+3)&=-\frac{(\Delta+3)!\,(\Delta +2t-2)(t+\Delta+2)_2}{2(N+2)^{(\Delta+3)}}
\binom{N-\Delta-4}{t-5}.
\end{align*}
The evidence is unmistakable: it must be true that for all $u\ge 1$
\begin{equation}\label{G(t,d+u)=}
G(t,\Delta+u)=-\frac{(\Delta+u)!\,(\Delta+2t-2)\binom{t+\Delta+u-1}{u-1}}{(N+2)^{(\Delta+u)}}
\binom{N-\Delta-u-1}{t-u-2}.
\end{equation}
Sure enough, the inductive step based on the recurrence \eqref{Grecur} is easily carried out with a 
guided assistance of {\sl Maple}. It remains to notice that the last binomial coefficient is zero for $u>t-2$.
\end{proof}

Now we are in a position to announce the main result of this section. 
\begin{theorem}\label{k=2separate} We have the identity
\begin{multline}\label{pnell2=final???}
p(N,\vec\ell;2)=\frac{(N-\ell)!\,\prod_j\ell_j!}{(N-1)!\,(N+t)}
\left[(-1)^{N+\ell}\frac{\binom{N-1}{t-2}}{\binom{N+\ell}{\ell-t}}\right.\\
+\frac{(N+t)(N+1)_{\ell+1}}{(N-t+1)(N+\ell)!\,(\ell)_t}
\left.\sum_{\nu=0}^{\ell-t}\frac{(N+\ell-\nu-1)!\,(N-1)_{\nu}}{(\ell-t-\nu)!\,(N-t)_{\nu}}\right].
\end{multline}
\end{theorem} 

 \begin{proof} Combining \eqref{doublesum=}
and \eqref{ell-t=1}, we transform 
\eqref{pnell2=final?} into \eqref{pnell2=final???}.
\end{proof}


The outside factor and the first  term inside the square brackets in \eqref{pnell2=final???}  are exactly those in the identity \eqref{bern} proved by Bernardi et al.\ \cite{Bernardi}.
The second inside term, a sum of $\ell-t+1$ terms, times  $\tfrac{(N+t)(N+1)_{\ell+1}}{(N-t+1)(N+\ell)!\,(\ell)_t}$, is quite different in appearance from its sum counterpart 
in \eqref{bern}. For $\ell-t\le 5$, {\sl Maple} confirms that the rational functions given by the sums in \eqref{bern} and in 
\eqref{pnell2=final???} are
identical; we did not try to prove equality in general. 

A  reviewer remarked that the equivalence of the two sums can be proved ``hypergeometrically: in hypergeometric terms
the sum is a balanced ${}_4{F}_3$-series; one applies one of Whipple's transformation formulas; there is some cancellation; then one applies the Pfaff-Saalsch\"utz summation''.


\section{Probability that  $\sigma$ blocks the 
elements of $[\ell]$}\label{isolated}

We say that the elements of $[\ell]$ are blocked in a permutation $s$ of $[N]$
if in every cycle of $s$  (1) no two elements of $[\ell]$ are neighbors, and (2) each element from $[\ell]$ has a neighbor from $[N]\setminus [\ell]$. 

Let $p(N,\ell;k)$ denote the probability of the event that $\sigma$ blocks the elements of $[\ell]$. In this final section, 
we are going to prove the following theorem. 

\begin{theorem} \label{twotermformula}
For all positive integers $\ell$ and $k$, the formula 
\begin{equation}\label{p4Nellk=}
p(N,\ell;k)=\frac{\binom{N-\ell}{\ell}}{\binom{N}{\ell}}
+(-1)^{k+1}\frac{\binom{N-\ell-1}{\ell-1}}{(N-1)^{k-1}\binom{N}{\ell}}.
\end{equation}
holds.
\end{theorem}

\begin{proof}   {Let $\mathcal A(\ell)$ denote the set of all permutations that block the elements of $[\ell]$
and let $\mathcal A(\vec\nu,\ell)=\{s\in \mathcal A(\ell): \vec\nu(s)=\vec\nu\}$, $Q(\vec\nu,\ell)=|\mathcal A(\vec\nu,\ell)|$.}
%Let us
%begin again with $Q(\vec\nu,\ell)$, the total number of permutations with cycle counts
%$\vec\nu$ such that the elements of $[\ell]$ are blocked.
To evaluate $Q(\vec{\nu},\ell)$, introduce the non-negative integers $a_{r,j}$, $b_{r,j}$ that
stand for the  numbers of elements from $[\ell]$ and $[N]\setminus [\ell]$  in the $j$-th cycle of
length $r$, $(j\le \nu_r)$, and let $\mathbf a$ and $\mathbf b$ denote the sequences of the numbers $a_{r,j}$ and $b_{r,j}$, in increasing order of the indices $r$, and then in increasing order of the indices $j$. Then 
\begin{equation}\label{restr}
\begin{aligned}
 a_{r,j}&+b_{r,j}=r,\\
 &b_{r,j}>0,\\
\sum_{r,\,j\le\nu_r}a_{r,j}&=\ell,\quad \sum_{r,\,j\le\nu_r}b_{r,j}=N-\ell.
\end{aligned}
\end{equation}
For $a_{r,j}>0$, the number of admissible cycles with parameters $a_{r,j}$, $b_{r,j}$ is
\begin{equation}\label{admcycles}
c(a_{r,j},b_{r,j}):= (a_{r,j}-1)!\,b_{r,j}!\,\binom{b_{r,j}-1}{a_{r,j}-1}=(b_{r,j}-1)!\,a_{r,j}!\,\binom{b_{r,j}}{a_{r,j}}.
\end{equation}
The last expression works for $a_{r,j}=0$ as well.

Indeed $(a_{r,j}-1)!$ is the total number of directed cycles formed by $a_{r,j}$ elements from $[\ell]$; $b_{r,j}!$ is the total number of ways to linearly order $b_{r,j}$ elements from
$[N]\setminus \ell$, and $\binom{b_{r,j}-1}{a_{r,j}-1}$ is the total number of ways to break any
such $b_{r,j}$-long sequence into $a_{r,j}$ blocks of positive lengths to be fitted between 
$a_{r,j}$ cyclically arranged elements from $[\ell]$, starting with the smallest element among them
and moving in the cycle's direction, say. 

Therefore
\begin{equation}\label{Q4nu}
\begin{aligned}
Q(\vec{\nu},\ell)&=(N-\ell)!\,\ell!
\sum_{\mathbf a,\,\mathbf b\text{ meet }
\eqref{restr}}
\prod_{r\ge1}\frac{1}{\nu_r!}\prod_{j\le \nu_r}
\frac{c(a_{r,j},b_{r,j})}{a_{r,j}!\,b_{r,j}!}\\
&=(N-\ell)!\,\ell!\,[w^{\ell}]\prod_{r\ge 1}\frac{1}{\nu_r!}\,\left(\sum_{b>0,\, a+b=r}
\frac{1}{b}\binom{b}{a}w^a\right)^{\nu_r}.
\end{aligned}
\end{equation}
Having found $Q(\vec{\nu},\ell)$, we turn to $p(N,\ell ,k)$, the probability that $\sigma$ blocks the elements of $[\ell]$.
Using \eqref{chila*(nu)}, the equality $\nu=\sum_r \nu_r$, {and}  \eqref{Q4nu}, we obtain 
\begin{multline*}
\chi^{\la^*}(\mathcal A(\vec\nu,\ell))=(-1)^{\la^1}(N-\ell)!\,\ell!\\
\times 
[\xi^{\la_1}w^{\ell}]\,\,\frac{\xi}{1-\xi}\,\prod_r\frac{1}{\nu_r!}\left[-(1-\xi^r)\left(\underset{a+b=r}{\sum_{b>0,}} 
\frac{1}{b}\binom{b}{a}w^a\right)\right]^{\nu_r}.
\end{multline*}
%Call a permutation $s$ of $[N]$ admissible if it blocks the elements of $[\ell]$. 
This identity implies
 \begin{multline}\label{sumcharadmsss4}
\chi^{\la^*}(\mathcal A(\ell))=(-1)^{\la^1}(N-\ell)!\,\ell!\\
\times 
[\xi^{\la_1}w^{\ell}]\,\,\frac{\xi}{1-\xi}\, 
\underset{1\nu_1+2\nu_2+\cdots=N}{\sum_{\vec{\nu}:}}\prod_r\frac{1}{\nu_r!}\left[-(1-\xi^r)
\left(\underset{a+b=r}{\sum_{b>0,}}\frac{1}{b}\binom{b}{a}w^a\right)\right]^{\nu_r}.
\end{multline}
The expression in the second line of \eqref{sumcharadmsss4} equals
\begin{align}
 [\xi^{\la_1}&w^{\ell}x^N] \frac{\xi}{1-\xi}\,\sum_{\vec\nu\,\ge \mathbf 0}\prod_r\frac{(x^r)^{\nu_r}}{\nu_r!}\left[-(1-\xi^r)\left(\sum_{b>0,\, a+b=r}\frac{1}{b}\binom{b}{a}w^a\right)\right]^{\nu_r}\notag\\
&=[\xi^{\la_1}w^{\ell}x^N] \frac{\xi}{1-\xi}\,\prod_r\sum_{\nu_r\ge 0}\frac{1}{\nu_r!}
\left[-x^r(1-\xi^r)\left(\sum_{b>0,\, a+b=r}\frac{1}{b}\binom{b}{a}w^a\right)\right]^{\nu_r}\notag\\
&=[\xi^{\la_1}w^{\ell}x^N] \frac{\xi}{1-\xi}\,\prod_r\exp\left[-x^r(1-\xi^r)\left(\sum_{b>0,\, a+b=r}\frac{1}{b}\binom{b}{a}w^a\right)\right]\notag\\
&=[\xi^{\la_1}w^{\ell}x^N]\frac{\xi}{1-\xi}\,\exp\left[-\sum_{r\ge 1}[x^r-(x\xi)^r]\left(\sum_{b>0,\, a+b=r}\frac{1}{b}\binom{b}{a}w^a\right)\right].
\label{[xila1wellxN]=}
\end{align}
Since 
\begin{align*}
\sum_{r\ge 1}y^r \sum_{b>0,\,a+b=r}\frac{1}{b} \binom{b}{a}w^a&=\sum_{b>0}\frac{y^b}{b}
\sum_a\binom{b}{a}(yw)^a\\
&=\sum_{b>0}\frac{y^b}{b}(1+yw)^b=\sum_{b>0}\frac{[y(1+yw)]^b}{b}\\
&=\log\frac{1}{1-y(1+yw)},
\end{align*}
the right-hand side in \eqref{[xila1wellxN]=} becomes 
\begin{align*}
[\xi^{\la_1}w^{\ell}x^N]& \frac{\xi}{1-\xi}\frac{1-x(1+xw)}{1-x\xi(1+x\xi w)}\\
&=[\xi^{\la_1}x^N] \,\frac{\xi(1-x)}{(1-\xi)(1-x\xi)}\,[w^{\ell}]\frac{1-\tfrac{x^2}{1-x}w}{1-\tfrac{(x\xi)^2}{1-x\xi}w}\\
&=[\xi^{\la_1}x^N]\,\frac{\xi(1-x)}{(1-\xi)(1-x\xi)}\left[\left(\frac{(x\xi)^2}{1-x\xi}\right)^{\ell}
-\frac{x^2}{1-x}\left(\frac{(x\xi)^2}{1-x\xi}\right)^{\ell-1}\right]\\
&=[\xi^{\la_1}x^N]\,\frac{\xi}{1-x\xi}\left(\frac{(x\xi)^2}{1-x\xi)}\right)^{\ell-1}\frac{x^2}{1-x\xi}\,(x\xi-1-\xi)\\
&=-[\xi^{\la_1}x^N]\,\left(\frac{x^{2\ell}\xi^{2\ell-1}}{(1-x\xi)^{\ell}}+\frac{x^{2\ell}\xi^{2\ell}}{(1-x\xi)^{\ell+1}}\right)\\
&=-[\xi^{\la_1-2\ell+1}x^{N-2\ell}](1-x\xi)^{-\ell}-[\xi^{\la_1-2\ell}x^{N-2\ell}](1-x\xi)^{-\ell-1}\\
&=-\binom{N-\ell-1}{\ell-1}1_{\{\la_1=N-1\}}-\binom{N-\ell}{\ell}1_{\{\la_1=N\}}.
\end{align*}
So \eqref{sumcharadmsss4} simplifies, greatly, to 
\begin{multline}\label{sum4}
{ \chi^{\la^*}(\mathcal A(\ell))}=(-1)^{\la^1-1}(N-\ell)!\,\ell!\\
\times 
\left[\binom{N-\ell-1}{\ell-1}1_{\{\la_1=N-1\}}+\binom{N-\ell}{\ell}1_{\{\la_1=N\}}\right].
\end{multline}
The rest is easy.  By \eqref{Psigma(s)},
\begin{equation}
p(N,\ell;k)
=\frac{1}{N!}\sum_{\la^*}(-1)^{k(\la^1-1)}\binom{N-1}{\la_1-1}^{-k+1}{\chi^{\la^*}(\mathcal A(\ell))}.
\end{equation}
Combining this with \eqref{sum4} we conclude that
%\label{p4Nellk=}
\[p(N,\ell;k)=\frac{\binom{N-\ell}{\ell}}{\binom{N}{\ell}}
+(-1)^{k+1}\frac{\binom{N-\ell-1}{\ell-1}}{(N-1)^{k-1}\binom{N}{\ell}}.
\]
{As a partial check, 
\begin{align*}
p(N,\ell;1)&=\frac{\binom{N-\ell}{\ell}}{\binom{N}{\ell}}+\frac{\binom{N-\ell-1}{\ell-1}}{\binom{N}{\ell}}\\
&=\frac{(N-\ell-1)!\,(n-\ell)!}{(N-1)!\, (N-2\ell)!}=\frac{c(\ell, N-\ell)}{(N-1)!},
\end{align*}
see \eqref{restr} and \eqref{admcycles}.}
\end{proof}

\begin{note} 
Equation  \eqref{p4Nellk=} shows that $\lim_{k\rightarrow \infty} p(N,\ell;k) = {\binom {N-\ell } \ell} / {\binom N  \ell}$,  the probability that the {\em uniformly} random permutation blocks $[\ell]$. 
\end{note}

\section*{Acknowledgment}
We are indebted to Frank Garvan, who generously helped us with matters involving {\sl Maple}, {and 
to Robin Pemantle for valuable suggestions. We sincerely thank the Editor for a truly productive refereeing process. An expert reviewer provided a generous, thoughtful feedback, helping us to have a fresh look at the manuscript and to
improve its quality.}
\begin{thebibliography}{99}

\bibitem{Andrews} 
G. E. Andrews, R. Askey and R. Roy, \textit{Special Functions}, 
Cambridge University Press, Cambridge, 1999.
\bibitem{Bai}
W. N. Bailey, \textit{Generalized Hypergeometric Series}, 
Cambridge University Press, Cambridge, 1972.
\bibitem{Bernardi} 
O. Bernardi, R. Du, A. Morales and R. Stanley, \textit{Separation probabilities for products of permutations}, Combin. Probab. Comput. \textbf{23} (2014), no. 2, 201--222.
\bibitem{Boc}
G.  Boccara, \textit{Nombres de repr\'esentations d'une permutation comme produit de deux cycles de 
longueurs donn\'ees}, Discrete Math. \textbf{29} (1980), 105-134.
\bibitem{bona-flynn} M. B\'ona and R. Flynn, \textit{The average number of block interchanges needed to sort a permutation and a recent result of Stanley},  Inform. Process. Lett. {\bf 109} (2009), no. 16, 927--931.
\bibitem{cangelmi} L. Cangelmi, \textit{Factorizations of an $n$-cycle into two $n$-cycles}, Europ. J. Combin. {\bf 24} (2003), 849--853.
\bibitem{Chmutov}
S. Chmutov and B. Pittel, \textit{On a surface formed  by randomly gluing together polygonal
discs}, Adv. Appl. Math. \textbf{73} (2016), 23--42.
\bibitem{DiaconisShahshahani}
P. Diaconis and M. Shahshahani, \textit{Generating a random permutation with random
transpositions}, Z. Wahr. Verw. Gebiete \textbf{57} (1981), 159--179.
\bibitem{Diaconis}
P. Diaconis, \textit{Group Representations in Probability and Statistics}, 
Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol.~11. 
Institute of Mathematical Statistics, Hayward, CA, 1988.
\bibitem{doignon} 
J.-P. Doignon and A. Labarre, \textit{On Hultman numbers}, J. Integer Seq. 10 (2007), Article~07.6.2, 13~pages.
\bibitem{FerRat}
V. F\'eray and A. Rattan, \textit{On product of long cycles: short cycle dependence and separation probabilities},
J. Algebr. Comb. \textbf{45} (2015), 183--224. 
\bibitem{GasRah}
G. Gasper and M. Rahman, \textit{Basic Hypergeometric Series}, 
Cambridge University Press, Cambridge, 1990.
\bibitem{Gou}
A. Goupil, \textit{On products of conjugacy classes of the symmetric group}, Discrete Math. \textbf{79} (1989/90), 49--57.
\bibitem{GouSch}
A. Goupil and G. Schaeffer, \textit{Factoring $n$-cycles and counting maps of given genus}, Europ. J. Combin. \textbf{19} (1998), 819--834.
\bibitem{HarerZagier}
J. Harer and D. Zagier, \textit{The Euler characteristic of the moduli space of curves}, Invent. Math.
\textbf{85} (1986), 457--485.
\bibitem{Hur}
A. Hurwitz, \textit{\"Uber Riemann'sche Fl\"achen mit gegebenen Verzweigungspunkten}, Math. Ann. \textbf{39} (1891),
1--66.
\bibitem{Jackson}
D. M. Jackson, \textit{Counting cycles in permutations by group characters, with an application
to a topological problem}, Trans. Amer. Math. Soc. \textbf{299} (1987), 785--801.
\bibitem{LandoZvonkin} 
S. K. Lando and A. K. Zvonkin, {\it Graphs on Surfaces and Their Applications},  Springer-Verlag, 2004.
\bibitem{larsen} M. Larsen and A. Shalev, \textit{Characters of symmetric groups: sharp bounds
and applications}, Invent. Math. {\bf 74} (2008), 645--687.
\bibitem{liebeck} M. W. Liebeck, N. Nikolov and A. Shalev, \textit{Product decompositions in finite simple groups}, Bull. London
Math. Soc. {\bf 44} (2012), 469--472.
\bibitem{Lovasz}
L. Lov\'asz, \textit{Combinatorial Problems and Exercises, 2nd edition}, 
North-Holland Publishing Co., Amsterdam, 1993.
\bibitem{WZ1} 
I. Nemes,  M. Petkov\^sek, H. S.  Wilf and D. Zeilberger, \textit{How to do Monthly problems with your computer},  Amer. Math. Monthly \textbf{104}  (1997), 505--519. 
\bibitem{petkovsek} M. Petkov\v{s}ek, H. Wilf and D. Zeilberger, \textit{A=B}, A.K. Peters, 1999. 
\bibitem{Pittel}
B. Pittel, \textit{Another proof of Harer--Zagier formula}, {\it Electronic J. Combin.} {\bf 23 (1)} (2016), Article~P.1.21, 11~pages.
\bibitem{PouSch}
D. Poulalhon and G. Schaeffer, \textit{Factorizations of large cycles in the symmetric group}, Discrete Math.
\textbf{254} (2002), 433--458.
\bibitem{Sagan}
B. E. Sagan, \textit{The Symmetric Group}, 
Wadsworth \& Brooks/Cole, Pacific Grove, California, 1991.
\bibitem{Sta1}
R. P. Stanley, \textit{Factorization of permutations into $n$-cycles}, Discrete Math. \textbf{37}
(1981), 255--262.
\bibitem{Stanley}
R. P. Stanley, \textit{Enumerative Combinatorics, Vol. 2}, 
Cambridge University Press, Cambridge, 1999.
\bibitem{Stanley2}
R. P. Stanley, \textit{Two enumerative results on cycles of permutations},  
Europ. J. Combin. \textbf{32} (2011), 937--943.
\bibitem{Sury}
B. Sury, \textit{Sum of the reciprocals of the binomial coefficients}, Europ. J. Combin.
\textbf{14} (1993), 351--353.
\bibitem{SWZ} 
B. Sury, T. Wang and F-Z. Zhao, \textit{Identities involving reciprocals of binomial
coefficients}, J. Integer Seq. \textbf{7} (2004), Article 04.2.8, 12~pages.
\bibitem{walsh}T. R. S. Walsh and A. B. Lehman, {\textit Counting rooted maps by genus.  I}, J. Combin. Theory, Ser.~B {\bf13} (1972), 192--218.
%\bibitem{WZ2} 
%H. S. Wilf and D. Zeilberger, \textit{An algorithmic proof theory for hypergeometric (ordinary and ``q'') multisum/integral identities},  Invent. Math. \textbf{108}  (1992), 575--633.
\bibitem{Zagier}
D. Zagier, \textit{On the distribution of the number of cycles of elements in symmetric groups},
Nieuw Arch. Wiskd. \textbf{13} (1995), 489--495.
\bibitem{Zeilberger} D. Zeilberger, The EKHAD package for {\sl Maple}, \url{http://sites.math.rutgers.edu/~zeilberg/tokhniot/EKHAD}.
 \end{thebibliography}
\end{document}


