\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

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

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

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

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

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

\usepackage{indentfirst}
\usepackage{manfnt}
\usepackage{mathtools}

\newcommand{\dd}{\textrm{d}}
\newcommand{\ee}{\mathrm{e}}
\newcommand{\ii}{\mathrm{i}}
\renewcommand{\aa}{\alpha}
\newcommand{\bb}{\beta}
\newcommand{\ff}{\varphi}
\renewcommand{\ll}{\lambda}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}} 
\newcommand{\RR}{\mathbb{R}}
\renewcommand{\SS}{\mathbb{S}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\MM}{\mathcal{M}}
\newcommand{\DD}{\mathcal{D}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\UU}{\mathcal{U}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\Fix}{\operatorname{Fix}}
\newcommand{\per}{\operatorname{per}}
\newcommand{\var}{\operatorname{\mathbb{V}ar}}
\renewcommand{\theta}{\varTheta}

\newcommand{\map}[3]{ { #1 } : { #2 } \rightarrow { #3 } }
\def\lah{\atopwithdelims||} % ---------------------------------  Numeri di Lah

\begin{document}

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

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

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

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

\begin{center}
\vskip 1cm{\LARGE\bf A Generalization of the \\
\vskip .00in
``Probl\`eme des Rencontres'' \\
}
\vskip 1cm
Stefano Capparelli \\
Dipartimento di Scienze di Base e Applicate per l'Ingegneria \\
Universit\'a di Roma ``La Sapienza'' \\
Via A. Scarpa 16 \\
00161 Roma \\
Italy \\
\href{mailto:stefano.capparelli@sbai.uniroma1.it}{\tt stefano.capparelli@sbai.uniroma1.it} \\
\ \\
Margherita Maria Ferrari \\
Department of Mathematics and Statistics \\
University of South Florida \\
4202 E. Fowler Avenue \\
Tampa, FL 33620 \\
USA \\
\href{mailto:mmferrari@usf.edu}{\tt mmferrari@usf.edu} \\
\ \\
Emanuele Munarini and Norma Zagaglia Salvi\footnote{This work is partially supported by MIUR (Ministero dell'Istruzione, dell'Universit\`a e della Ricerca).} \\
Dipartimento di Matematica\\
Politecnico di Milano \\
Piazza Leonardo da Vinci 32 \\
20133 Milano \\
Italy \\
\href{mailto:emanuele.munarini@polimi.it}{\tt emanuele.munarini@polimi.it} \\
\href{mailto:norma.zagaglia@polimi.it}{\tt norma.zagaglia@polimi.it}
\end{center}

\vskip .2 in

\begin{abstract}
 In this paper, we study a generalization of the classical
 \emph{probl\`eme des rencontres} (\emph{problem of coincidences}),
 where you are asked to enumerate all permutations $ \pi \in \SS_n $ with $k$ fixed points,
 and, in particular, to enumerate all permutations $ \pi \in \SS_n $ with no fixed points (derangements).
 Specifically, here we study this problem for the permutations of the $n+m$
 symbols $1$, $2$, \ldots, $n$, $v_1$, $v_2$, \ldots, $v_m$,
 where $ v_i \not\in\{1,2,\ldots,n\} $ for every $i=1,2,\ldots,m$.
 In this way, we obtain a generalization of the derangement numbers,
 the rencontres numbers and the rencontres polynomials.
 For these numbers and polynomials, we obtain the exponential generating series, some recurrences and representations,
 and several combinatorial identities. Moreover, we obtain the expectation and the variance
 of the number of fixed points in a random permutation of the considered kind.
 Finally, we obtain some asymptotic formulas
 for the generalized rencontres numbers and the generalized derangement numbers.
\end{abstract}

\section{Introduction}

The \emph{probl\`eme des rencontres}, or \emph{problem of coincidences}
(also called \emph{probl\`eme de Montmort}, or \emph{probl\`eme des chapeaux};
see (\cite{Montmort}, \cite[pp.\ 9--12,\ 32]{Comtet}, \cite[p.\ 57]{Riordan}, \cite{Abramson}),
is one of the classical problems in enumerative combinatorics and in probability.
From a combinatorial point of view,
it is the problem of enumerating all permutations $ \pi \in \SS_n $ with $k$ fixed points.
In particular, for $ k = 0 $, it reduces to the problem
of enumerating all permutations $ \pi \in \SS_n $ with no fixed points.
For the history of the original problem and its solutions,
see Takacs \cite{Takacs}.

The aim of this paper is to extend the \emph{probl\`eme des rencontres}
to the permutations of the symbols $1$, $2$, \ldots, $n$, $v_1$, $v_2$, \ldots, $v_m$,
where $ v_i \not\in\{1,2,\ldots,n\} $ for every $i=1,2,\ldots,m$.
The set of these \emph{generalized permutations} is denoted by $ \SS_n^{(m)}$.
A fixed point of a permutation $ \pi = a_1 \cdots a_n a_{n+1} \cdots a_{n+m} \in \SS_n^{(m)}$
is, by definition, an index $ i \in \{1, 2, \ldots, n \} $ such that $a_i=i$.
The permutations in $ \SS_n^{(m)} $ with no fixed points are called \emph{generalized derangements}
and their number is denoted by $ d_n^{(m)} $.
Clearly, for $m=0$ we have the ordinary derangements and the ordinary derangement numbers $ d_n $ (\seqnum{A000166} in the {\it On-Line Encyclopedia of
Integer Sequences}).

The permutations in $ \SS_n^{(m)}$ can be interpreted as particular bijective functions,
generalizing the \emph{widened permutations} (corresponding to the case $ m = 1 $)
introduced and studied in \cite{BeggasFerrariZagaglia}.
For any $m \in \NN$, an \emph{$m$-widened permutation}
is a bijection between two $(n+m)$-sets having $n$ elements in common.
More precisely, given an $n$-set $X$ and two $m$-sets $U$ and $V$,
such that $X$, $U$ and $V$ are pairwise disjoint,
we have a bijection $ \map{f}{X \cup U}{X \cup V} $.
If $U = \{u_1, \ldots,u_m\}$ and $V = \{v_1, \ldots,v_m\}$,
then $f$ is equivalent to an $(m+1)$-tuple $ (\ll_1,\ldots,\ll_m,\sigma) $,
where each $\ll_i$ is a linear order and $\sigma$ is a permutation, defined as follows:
$ \ll_i = [u_i, f(u_i), f^2(u_i), \ldots, f^h(u_i), v_j] $
where $h+1$ is the minimum positive integer such
that there exists a $ j \in \{1,2,\ldots,m\} $ such that $ f^{h+1}(u_i) = v_j $,
and $\sigma$ is the remaining permutation on $ X \setminus (X_{\ll_1}\cup\cdots\cup X_{\ll_m}) $,
where $ X_{\ll_i} = \{ f(u_i), f^2(u_i), \ldots, f^h(u_i) \} \subseteq X $.
For instance, the $4$-widened permutation
$$
 f =
 \left(
 \begin{array}{ccccccccccccc}
  1 & 2 &   3 & 4 & 5 &   6 & 7 & 8 &   9 & u_1 & u_2 & u_3 & u_4 \\
  7 & 1 & v_2 & 4 & 8 & v_4 & 2 & 6 & v_3 &   9 & v_1 &   5 &   3 \\
 \end{array}
 \right)
$$
is equivalent to the quintuple $ (\ll_1,\ll_2,\ll_3,\ll_4,\sigma) $,
where $ \ll_1 = [u_1, 9, v_3] $, $ \ll_2 = [u_2, v_1] $, $ \ll_3 = [u_3, 5, 8, 6, v_4] $, $ \ll_4 = [u_4, 3, v_2] $,
and $ \sigma = (172)(4) $.
If we consider only the second line in the two-line representation of $f$,
we have the corresponding generalized permutation
$ \pi = 7\, 1\, v_2\, 4\, 8\, v_4\, 2\, 6\, v_3\, 9\, v_1\, 5\, 3 \in \SS_9^{(4)} $.
Notice that $\pi$, or $f$, has only one fixed point in position $4$.
In particular, $\pi$ is a generalized derangement
when the corresponding $m$-widened permutation $f$, with decomposition $ (\ll_1,\ldots,\ll_m, \sigma) $,
is an \emph{$m$-widened derangement}, that is when $ \sigma $ is an ordinary derangement.
In the rest of the paper, the generalized permutations in $ \SS_n^{(m)} $
and the generalized derangements in $ \SS_n^{(m)} $
are identified with the corresponding
$m$-widened permutations and the $m$-widened derangements, respectively.

\bigskip

The paper is organized as follows.
In Section \ref{sec-gder}, we obtain an explicit formula for the generalized derangement numbers $ d_n^{(m)} $
and their exponential generating series.
Moreover, we establish the connection between these numbers
and the \emph{$r$-derangement numbers} \cite{WangMiskaMezo}.
In Section \ref{sec-Dnk}, we introduce
the generalized rencontres numbers $ D_{n,k}^{(m)} $ and the associated polynomials $ D_n^{(m)}(x) $.
Then, we obtain their exponential generating series,
some recurrences and some representations (in terms of determinants and integrals).
In Sections \ref{sec-combid} and \ref{sec-conid},
we obtain several identities involving the generalized rencontres polynomials
and other combinatorial polynomials and numbers.
In Section \ref{sec-ExpVar}, we compute the expectation and the variance of the random variable $ X_n^{(m)} $
giving the number of fixed points of a permutation in $ \SS_n^{(m)} $.
In particular, we obtain that the expectation and the variance tend to $1$ as $ n \to +\infty $.
Finally, in Section \ref{sec-asy}, we obtain some asymptotic formulas
for the generalized rencontres numbers $ D_{n,k}^{(m)} $
and the generalized derangement numbers $ d_n^{(m)} $.

\section{Generalized derangement numbers}\label{sec-gder}

Given $ n \in \NN $, let $ [ n ] = \{ 1, 2, \ldots, n \} $.
Given $ m, n \in \NN $, let $ \SS_n^{(m)} $ be the set of all permutations
of the symbols $1$, $2$, \ldots, $n$, $v_1$, $v_2$, \ldots, $v_m$.
Clearly $ |\SS_n^{(m)}| = (m+n)! $, and for $ m = 0 $ we have the ordinary permutations.
A permutation $ \pi = a_1 a_2 \cdots a_{m+n} \in \SS_n^{(m)} $ has a fixed point
when there exists an index $ i \in [ n ] $ such that $ a_i = i $.
For instance, in $ \pi = 4\, v_2\, 3\, v_3\, 5\, v_1\, 2\, 1 $
we have only two fixed points in position $3$ and $5$.
Notice that, in the general case, a fixed point can appear only in the first $n$ positions.
A \emph{generalized derangement} is a permutation in $ \SS_n^{(m)} $ with no fixed points.
The \emph{generalized derangement number} $ d_{n}^{(m)} $
is the number of generalized derangements in $ \SS_n^{(m)} $.
For $ m = 0 $, we have the ordinary derangement numbers $ d_n $
\cite[p.\ 182]{Comtet} \cite[p.\ 65]{Riordan} (\seqnum{A000166}).

\begin{theorem}
 The generalized derangement numbers can be expressed as
 \begin{equation}\label{id-dm}
  d_n^{(m)} = \sum_{k=0}^n { n \choose k } (-1)^k (m+n-k)!
 \end{equation}
 and have exponential generating series
 \begin{equation}\label{series-dm}
  d^{(m)}(t) = \sum_{n\geq0} d_n^{(m)} \frac{t^n}{n!} = \frac{m!\,\ee^{-t}}{(1-t)^{m+1}} \, .
 \end{equation}
\end{theorem}
\begin{proof}
 Identity (\ref{id-dm}) can be proved combinatorially using the inclusion-exclusion principle.
 Let $ A_i $ be the set of permutations $ \pi = a_1 a_2 \cdots a_{m+n} \in \SS_n^{(m)} $ such that $ a_i = i $,
 and let $ A_i' $ be its complementary with respect to $ \SS_n^{(m)} $,
 for every $ i = 1, \ldots, n $. Then, by the inclusion-exclusion principle, we have
 $$
  d^{(m)}_n = | A_1' \cap A_2' \cap \cdots \cap A_n' |
            = \sum_{I\subseteq[n]} (-1)^{|I|}  \left| \bigcap_{i\in I} A_i \right| \, .
 $$
 The set $ \bigcap_{i\in I} A_i $ consists of all permutations
 $ \pi = a_1 a_2 \cdots a_{m+n} \in \SS_n^{(m)} $ such that $ a_i = i $,
 for every $ i \in I $.
 So, it is equivalent to the set $ \SS_{n-|I|}^{(m)} $ and consequently its size is $ (m+n-|I|)! $.
 Hence, we have the identity
 $$ d^{(m)}_n = \sum_{I\subseteq[n]} (-1)^{|I|} (m+n-|I|)! $$
 which is equivalent to identity (\ref{id-dm}).
 Now, by identity (\ref{id-dm}), we have the generating series
 $$
  d^{(m)}(t) = \sum_{n\geq0} (-1)^n \frac{t^n}{n!} \cdot \sum_{n\geq0} (m+n)! \frac{t^n}{n!} \\
             = m!\, \ee^{-t} \cdot \sum_{n\geq0} { m+n \choose m } t^n
 $$
 which is equivalent to series (\ref{series-dm}).
\end{proof}

For the first values of $ n $, we have the generalized derangement numbers
\begin{equation}\label{IC-dmn}
 \begin{aligned}
  & d_0^{(m)} = m! \\
  & d_1^{(m)} = m!\cdot m \\
  & d_2^{(m)} = m!\cdot(m^2 + m + 1) \\
  & d_3^{(m)} = m!\cdot(m^3 + 3 m^2 + 5 m + 2) \\
  & d_4^{(m)} = m!\cdot(m^4 + 6 m^3 + 17 m^2 + 20 m + 9)\, .
 \end{aligned}
\end{equation}

\begin{remark}
 The generalized derangement numbers $ d_n^{(m)} $
 appear also in \cite{Navarrete1,Navarrete2} and form sequences
 \seqnum{A000166}, \seqnum{A000255}, \seqnum{A055790}, \seqnum{A277609}, \seqnum{A277563},
 \seqnum{A280425}, \seqnum{A280920}, \seqnum{A284204}, \seqnum{A284205}, \seqnum{A284206},
 \seqnum{A284207} in \cite{Sloane} for $ m = 0, 1, \ldots, 10 $, respectively.
 Similarly, the numbers $ d_n^{(m)}/m! $ form sequences
 \seqnum{A000166}, \seqnum{A000255}, \seqnum{A000153}, \seqnum{A000261}, \seqnum{A001909},
 \seqnum{A001910}, \seqnum{A176732}, \seqnum{A176733}, \seqnum{A176734}, \seqnum{A176735},
 \seqnum{A176736} in \cite{Sloane} for $m=0,\ldots, 10$, respectively.
 Notice that, the numbers $ d_n^{(m)}/m! $ count the generalized derangements
 when $ v_1 = \cdots = v_m = v $.
\end{remark}

\medskip

An \emph{$r$-permutation} of the set $ \{ 1, 2, \ldots, r, r+1, \ldots, n+r \} $
is a permutation in which the elements 1, 2, \ldots, $r$ belong to different cycles \cite{Broder}.
An \emph{$r$-derangement} is an $r$-permutation with no fixed points \cite{WangMiskaMezo}.
The generalized derangement numbers $ d_n^{(m)} $ and the \emph{$r$-derangement numbers} $ D_r(n) $ \cite{WangMiskaMezo}
are related as follows.
\begin{theorem}
 For every $ r, n \in \NN $, we have
 \begin{equation}\label{id-D-d}
  D_r(n) = { n \choose r } d_{n-r}^{(r)} \qquad (n\geq r)\, .
 \end{equation}
\end{theorem}
\begin{proof}
 We have the exponential generating series \cite{WangMiskaMezo}
 \begin{align*}
  \sum_{n\geq r} D_r(n) \frac{t^n}{n!}
  &= \frac{t^r\ee^{-t}}{(1-t)^{r+1}}
   = \frac{t^r}{r!}\,d^{(r)}(t)
   = \frac{t^r}{r!} \sum_{n\geq0} d_n^{(r)} \frac{t^n}{n!} \\
  &= \sum_{n\geq0} { n+r \choose r } d_n^{(r)} \frac{t^{n+r}}{(n+r)!}
   = \sum_{n\geq r} { n \choose r } d_{n-r}^{(r)} \frac{t^n}{n!} \, .
 \end{align*}
 Comparing the coefficients of $ t^n/n! $, we have identity (\ref{id-D-d}).
\end{proof}

\begin{remark}
 Let $ \map{f}{X \cup U}{X \cup V} $ be an $m$-widened permutation on a set $X$ of size $n$,
 and let $ (\ll_1,\ldots,\ll_m, \sigma) $ be its decomposition.
 Suppose that in $f$ each linear order $\ll_i$ (starting with $u_i$) ends with $v_i$,
 i.e., $ \ll_i = [ u_i, b_1, \ldots, b_h, v_i ] $.
 If we replace each linear order $ \ll_i $ with a cycle $ \gamma_i = (b_1 \cdots b_h \; n+i) $,
 by setting $ u_i = n+i $ and by removing $ v_i $,
 we obtain a permutation of the set $\{ 1, 2, \ldots, n+m \}$
 where the elements $ n+1 $, \ldots, $ n+m $ belong to different cycles.
 So, these $m$-widened permutations are equivalent to the $m$-permutations.
 In particular, if each $\ll_i$ contains at least one element of $X$, i.e., $ \ll_i \ne [u_i,v_i] $,
 and $ \sigma $ does not have fixed points,
 then we have the $m$-derangements \cite{WangMiskaMezo}.
\end{remark}

\medskip

Other properties for the generalized derangement numbers 
are obtained in next sections
as specialization of the more general properties of the generalized rencontres polynomials.

\section{Generalized rencontres numbers and polynomials}\label{sec-Dnk}

Let $ D_{n,k}^{(m)} $ be the \emph{generalized rencontres numbers},
i.e., the number of permutations $ \pi \in \SS_n^{(m)} $ with $ k $ fixed points.
Removing the $ k $ fixed points and normalizing the remaining letters,
we obtain a derangement $ \delta \in \SS_{n-k}^{(m)} $.
So, we have at once the identity
\begin{equation}\label{def-Dnk}
 D_{n,k}^{(m)} = { n \choose k } d_{n-k}^{(m)} \, .
\end{equation}
For $ m = 0 $ we have the ordinary \emph{rencontres numbers} $ D_{n,k} $, \cite[pp.\ 57,\ 58,\ 65]{Riordan},
forming sequence \seqnum{A008290}.
For $ m = 1 $ we have sequence \seqnum{A123513},
while for $ m \geq 2 $ the sequences do not appear in \cite{Sloane}.
Let $ D^{(m)} = [ D_{n,k}^{(m)} ]_{n,k\geq0} $ be the infinite lower triangular matrix
generated by the generalized rencontres numbers.
For $ m = 1 $ and $ m = 2 $, we have the matrices
\begin{small}
$$
 D^{(1)} =
 \begin{bmatrix}
  1 \\
  1 & 1 \\
  3 & 2 & 1 \\
  11 & 9 & 3 & 1 \\
  53 & 44 & 18 & 4 & 1 \\
  309 & 265 & 110 & 30 & 5 & 1 \\
  2119 & 1854 & 795 & 220 & 45 & 6 & 1 \\
  \ldots
 \end{bmatrix},
 \quad
  \frac{1}{2}D^{(2)} =
 \begin{bmatrix}
  1 \\
  2 & 1 \\
  7 & 4 & 1 \\
  32 & 21 & 6 & 1 \\
  181 & 128 & 42 & 8 & 1 \\
  1214 & 905 & 320 & 70 & 10 & 1 \\
  9403 & 7284 & 2715 & 640 & 105 & 12 & 1 \\
  \ldots
 \end{bmatrix}.
$$
\end{small}

A polynomial sequence $ \{ p_n(x) \}_{n\in\NN} $ is an \emph{Appell sequence}
\cite{Appell,MunariniA} \cite[p.\ 86]{Roman} \cite{RomanRota} \cite[p.\ 314]{VeinDale}
when its exponential generating series has the form
$$ \sum_{n\geq0} p_n(x)\,\frac{t^n}{n!} = g(t)\,\ee^{xt} $$
where $ g(t) = \sum_{n\geq0} g_n\,\frac{t^n}{n!} $ is an exponential series with $ g_0 = 1 $.
From this definition it follows that $ p_n(x) $ is a polynomial of degree $ n $ of the form
$$ p_n(x) = \sum_{k=0}^n { n \choose k } g_{n-k} x^k $$
such that $ p'_n(x) = n p_{n-1}(x) $.
Several classical polynomial sequences are of this kind \cite[p.\ 86]{Roman} \cite{RomanRota,Carlson}.
This is true also for the \emph{generalized rencontres polynomials}, defined by
\begin{equation}\label{def-Dx}
 D_{n}^{(m)}(x) = \sum_{k=0}^n D_{n,k}^{(m)} x^k = \sum_{k=0}^n { n \choose k } d_{n-k}^{(m)} x^k \, .
\end{equation}
Indeed, using series (\ref{series-dm}), we have at once
\begin{theorem}
 The polynomials $ D_{n}^{(m)}(x) $ form an Appell sequence having exponential generating series
 \begin{equation}\label{series-D}
  D^{(m)}(x;t) = \sum_{n\geq0} D_{n}^{(m)}(x)\;\frac{t^n}{n!} = d^{(m)}(t)\,\ee^{xt}
  = \frac{m!\,\ee^{(x-1)t}}{(1-t)^{m+1}} \, .
 \end{equation}
 In particular, $ D_{n}^{(m)}(x) $ has degree $ n $ and $ (D_{n}^{(m)}(x))' = n D_{n-1}^{(m)}(x) $.
\end{theorem}

Clearly, we have $ D_n^{(m)}(0) = D_{n,0}^{(m)} = d_{n}^{(m)} $ and $ D_{n}^{(m)}(1) = (m+n)! $.
Moreover, for $ m = 0 $, we have the ordinary \emph{rencontres polynomials} $ D_n(x) = D_n^{(0)}(x) $, \cite{Riordan},
whose exponential generating series are denoted simply by $ D(x;t) $.
For the first values of $ n $, we have the polynomials
\begin{equation}\label{IC-Dmnx}
 \begin{aligned}
  & D_0^{(m)}(x) = m! \\
  & D_1^{(m)}(x) = m!(x+m) \\
  & D_2^{(m)}(x) = m!(x^2+ 2 m x +  m^2 + m + 1 ) \\
  & D_3^{(m)}(x) = m!(x^3 + 3 m x^2 + 3(m^2+m+1) x + m^3 + 3 m^2 + 5 m + 2) \\
  & D_4^{(m)}(x) = m!(x^4 + 4 m x^3 + 6(m^2+m+1) x^2 + \\
  & \qquad\qquad\qquad + 4(m^3 + 3 m^2 + 5 m + 2) x + m^4 + 6 m^3 + 17 m^2 + 20 m + 9)\, .
 \end{aligned}
\end{equation}

\begin{theorem}
 The polynomials $ D_{n}^{(m)}(x) $ admit the explicit expression
 \begin{equation}\label{formula-Fx01}
  D_n^{(m)}(x) = \sum_{k=0}^n { n \choose k } (m+k)! (x-1)^{n-k}
 \end{equation}
 and satisfy the recurrences
 \begin{equation}\label{rec-Fx}
  D_{n+2}^{(m)}(x) = (x+m+n+1) D_{n+1}^{(m)}(x) - (n+1)(x-1) D_{n}^{(m)}(x)
 \end{equation}
 and
 \begin{equation}\label{rec-Fx02}
  D_{n+1}^{(m+1)}(x) = (n+1) D_{n}^{(m+1)}(x) + (m+1) D_{n+1}^{(m)}(x) \, .
 \end{equation}
 In particular, for $ x = 0 $, we have that the numbers $ d_n^{(m)} $ satisfy the recurrences
 \begin{equation}\label{rec-dn-2}
  d_{n+2}^{(m)} = (m+n+1) d_{n+1}^{(m)} + (n+1) d_n^{(m)}
 \end{equation}
 and
 \begin{equation}\label{rec-dn-1}
  d_{n+1}^{(m+1)} = (n+1) d_{n}^{(m+1)} + (m+1) d_{n+1}^{(m)} \, .
 \end{equation}
\end{theorem}
\begin{proof}
 Writing series (\ref{series-D}) as
 $$ D^{(m)}(x;t) = \frac{m!}{(1-t)^{m+1}}\cdot\ee^{(x-1)t}\, , $$
 we obtain at once identity (\ref{formula-Fx01}).
 Moreover, again by series (\ref{series-D}), we have
 $$ \frac{\partial}{\partial t}D^{(m)}(x;t) = \frac{x+m-(x-1)t}{1-t}\;D^{(m)}(x;t)\, . $$
 Hence, we have the identity
 $$ (1-t)\frac{\partial}{\partial t}D^{(m)}(x;t) = (x+m-(x-1)t)\,D^{(m)}(x;t) $$
 which is equivalent to recurrence (\ref{rec-Fx}).

 Replacing $ m $ by $ m+1 $ in (\ref{series-D}), we obtain the identity
 $$ (1-t) D^{(m+1)}(x;t) = (m+1) \frac{m!\;\ee^{(x-1)t}}{(1-t)^{m+1}} = (m+1) D^{(m)}(x;t) $$
 which is equivalent to recurrence (\ref{rec-Fx02}).
\end{proof}

\begin{remark}
 By Favard's theorem \cite[p.\ 294]{Aigner2007},
 a polynomial sequence $ \{ p_n(x) \}_{n\in\NN} $ form an \emph{orthogonal polynomial system}
 if the polynomials $ p_n(x) $ have degree $n$ with leading coefficient 1
 and satisfy a recurrence $ p_{n+2}(x) = (a_{n+1}+x) p_{n+1} - b_{n+1} p_n(x) $ with
 $ p_0(x) = 1 $ and $ p_1(x) = x+a_0 $.
 So, by recurrence (\ref{rec-Fx}) and the initial conditions listed in (\ref{IC-Dmnx}),
 we have that the polynomials $ D^{(m)}_n(x)/m! $ are orthogonal,
 with $ a_n = m+n $ and $ b_n = n(x-1) $.
\end{remark}

\medskip

\begin{remark}
 Identity (\ref{rec-dn-2}) can be proved with a combinatorial argument,
 which generalizes Euler's proof of the corresponding recurrence for the ordinary derangement numbers
 \cite[p.\ 60]{Riordan} \cite{Takacs}.
 Let $ \pi = a_1 a_2 \cdots a_{m+n+2} \in \SS^{(m)}_{n+2} $ be a derangement.
 Since $ a_1 \ne 1 $, we have the following three cases.
 (i) If $ a_1 = v_i $, then $ a_1 $ can be chosen in $m$ different ways
 and the permutation of the remaining elements is equivalent to a derangement $ \pi' $
 of the symbols $1$, \ldots, $n+1$, $v_1$, \ldots, $v_{i-1}$, $w_i$, $v_{i+1}$, \ldots, $v_m$.
 Indeed, $ \pi' $ can be obtained by deleting $ v_i $ from $ \pi $,
 by replacing $1$ by a new symbol $w_i$ and by normalizing the remaining numerical letters.
 In all, we have $ m\,d^{(m)}_{n+1} $ such permutations.
 (ii) If $ a_1 = k $ with $ k \in \{2,3,\ldots,n+2\} $ and $ a_k \ne 1 $,
 then, since $ 1 $ is not in position $ k $, we have that
 the permutation $ \pi' $ obtained by deleting $a_1=k$ from $ \pi $,
 by replacing $1$ by $k$ and by normalizing the other numerical letters,
 is a derangement in $ \SS_{n+1}^{(m)} $.
 In all, we have $ (n+1)\,d^{(m)}_{n+1} $ such permutations.
 (iii) Finally, if $ a_1 = k $ with $ k \in \{2,3,\ldots,n+2\} $ and $ a_k = 1 $,
 then the permutation $ \pi' $ obtained by deleting $1$ and $k$ from $ \pi $
 and by normalizing the other numerical letters, is a derangement in $ \SS_n^{(m)} $.
 In all, we have $ (n+1)\,d^{(m)}_n $ such permutations.
 This proves identity (\ref{rec-dn-2}).
\end{remark}

\begin{theorem}
 The numbers $ D_{n,k}^{(m)} $ satisfy the recurrences
 \begin{equation}\label{rec-Fnk00}
  (k+1) D_{n+1,k+1}^{(m)} = (n+1) D_{n,k}^{(m)}
 \end{equation}
 \begin{equation}\label{rec-Fnk01}
  D_{n+2,k+1}^{(m)} = (m+n+1) D_{n+1,k+1}^{(m)} + D_{n+1,k}^{(m)} + (n+1) D_{n,k+1}^{(m)} - (n+1) D_{n,k}^{(m)}
 \end{equation}
 \begin{equation}\label{rec-Fnk02}
  D_{n+1,k}^{(m+1)} = (n+1) D_{n,k}^{(m+1)} + (m+1) D_{n+1,k}^{(m)}
 \end{equation}
  and
 \begin{equation}\label{rec-Fnk03}
  D_{n+1,k+1}^{(m)} = D_{n,k}^{(m)} + (m+n-k-1) D_{n,k+1}^{(m)} + (k+2) D_{n,k+2}^{(m)} \, .
 \end{equation}
\end{theorem}
\begin{proof}
 Recurrence (\ref{rec-Fnk00}) is an immediate consequence of definition (\ref{def-Dnk}).
 Recurrences (\ref{rec-Fnk01}) and (\ref{rec-Fnk02}) are consequences of
 recurrences (\ref{rec-Fx}) and (\ref{rec-Fx02}), respectively.
 Recurrence (\ref{rec-Fnk03}) is equivalent to the identity
 $$ \R D_{n+1}(x) = D_{n}(x) + (m+n) \R D_{n}(x) - D'_{n}(x) + \R D'_{n}(x) \, , $$
 where we write simply $ D_n(x) $ for $ D_n^{(m)}(x) $
 and where $ \R $ is the \emph{incremental ratio},
 i.e., the linear operator defined, on every polynomial $ p(x) $, by $ \R p(x) = \frac{p(x)-p(0)}{x} $.
 So, if $ p(x) = \sum_{k=0}^n p_k x^k $, then $ \R p(x) = \sum_{k=0}^{n-1} p_{k+1} x^k $.
 The previous identity is equivalent to
 $$ \frac{D_{n+1}(x)-D_{n+1}(0)}{x} = D_{n}(x) + (m+n) \frac{D_{n}(x)-D_{n}(0)}{x} - D'_{n}(x) + \frac{D'_{n}(x)-D'_{n}(0)}{x} $$
 that is
 $$ D_{n+1}(x)-D_{n+1,0} = x D_{n}(x) + (m+n) (D_{n}(x)-D_{n,0}) - x D'_{n}(x) + D'_{n}(x) - D_{n,1} $$
 that is
 $$ D_{n+1}(x)-d_{n+1} = x D_{n}(x) + (m+n) (D_{n}(x)-d_{n}) - n x D_{n-1}(x) + n D_{n-1}(x) - n d_{n-1} $$
 that is
 $$ D_{n+1}(x)-d_{n+1} = (x+m+n) D_{n}(x)- n (x-1) D_{n-1}(x) - (m+n) d_{n} - n d_{n-1} $$
 and this identity is true by (\ref{rec-Fx}) and (\ref{rec-dn-2}).
\end{proof}

\begin{theorem}
 We have the identity
 \begin{equation}\label{id-Dx-20}
  D_{n+1}^{(m)}(x) = D_n^{(m+1)}(x) + (x-1) D_n^{(m)}(x) \, .
 \end{equation}
 In particular, for $ x = 0 $, we have the identity
 \begin{equation}\label{id-d-20}
  d_{n+1}^{(m)} = d_n^{(m+1)} - d_n^{(m)} \, .
 \end{equation}
 More in general, we have the identities
 \begin{equation}\label{id-Dx-200}
  D_{n+r}^{(m)}(x) = \sum_{k=0}^r { r \choose k } (x-1)^{r-k} D_n^{(m+k)}(x)
 \end{equation}
 and
 \begin{equation}\label{id-Dx-201}
  D_n^{(m+r)}(x) = \sum_{k=0}^r { r \choose k } (-1)^{r-k} (x-1)^{r-k} D_{n+k}^{(m)}(x) \, .
 \end{equation}
 In particular, for $ x = 0 $, we have the identities
 \begin{equation}
  d_{n+r}^{(m)} = \sum_{k=0}^r { r \choose k } (-1)^{r-k} d_n^{(m+k)}
 \end{equation}
 and
 \begin{equation}\label{id-d-201}
  d_n^{(m+r)} = \sum_{k=0}^r { r \choose k } d_{n+k}^{(m)} \, .
 \end{equation}
 Finally, we also have the identity
 \begin{equation}\label{id-d-2011}
  d^{(m)}_n = \sum_{k=0}^m {m \choose k} d_{n+k} \, .
 \end{equation}
\end{theorem}
\begin{proof}
 Identity (\ref{id-Dx-20}) is an immediate consequence of the identity
 $$
  \frac{\partial}{\partial t} D^{(m)}(x;t) = \frac{x+m-(x-1)t}{1-t}\;D^{(m)}(x;t)
  = D^{(m+1)}(x;t) + (x-1) D^{(m)}(x;t) \, .
 $$
 From the above identity, we can prove, by induction, that
 $$ \frac{\partial^r}{\partial t^r} D^{(m)}(x;t) = \sum_{k=0}^r { r \choose k } (x-1)^{r-k} D^{(m+k)}(x;t) \, . $$
 This identity is equivalent to identity (\ref{id-Dx-200}).
 Then, by applying the binomial inversion formula \cite[p.\ 147]{Roman}
 to identity (\ref{id-Dx-200}), we obtain identity (\ref{id-Dx-201}).
 Finally, identity (\ref{id-d-2011}) can be obtained from identity (\ref{id-d-201}) by setting $m=0$ and $r=m$.
\end{proof}

\begin{remark}
 Identity (\ref{id-d-20}) can be proved with the following combinatorial argument.
 Let $ f $ be an $m$-widened derangement on a set $X$ of size $n$,
 and let $ (\ll_1,\ldots,\ll_m, \sigma) $ be its decomposition.
 We have two cases. (i) The last linear order $ \ll_m $ does not contain elements of $X$,
 i.e., $ \ll_m = [u_m,v_j] $ for a suitable $ j \in [m] $.
 By deleting $ \ll_m $, and by replacing $ v_m $ by $ v_j $ whenever $ j \neq m $,
 we obtain an $(m-1)$-widened derangement on $X$.
 (ii) The last linear order $ \ll_m $ contains at least one element of $X$,
 i.e., $ \ll_m = [u_m, i_1, \ldots, i_h, v_j] $ for a suitable $ j \in [m] $.
 In this case, $f$ is equivalent to an $(m-1)$-widened derangement on $X \cup \{n+1\}$
 obtained by replacing the linear order $ \ll_m $ with the cycle $ \gamma = (i_1 \cdots i_h\, n+1) $,
 and by replacing $v_m$ with $v_j$ whenever $j\neq m$.
 Since $ \gamma $ has at least two elements, the new $(m-1)$-widened permutation is without fixed points.
 So, in conclusion, we have the identity $ d^{(m)}_n = d^{(m-1)}_n + d^{(m-1)}_{n+1} $.
\end{remark}

\begin{theorem}
 We have the identity
 \begin{equation}\label{id-Dx-000}
  \frac{D_n^{(m+1)}(x)}{n!} = (m+1) \sum_{k=0}^n \frac{D_k^{(m)}(x)}{k!} \, .
 \end{equation}
 In particular, for $ x = 0 $, we have the identity
 \begin{equation}
  \frac{d_n^{(m+1)}}{n!} = (m+1) \sum_{k=0}^n \frac{d_k^{(m)}}{k!} \, .
 \end{equation}
\end{theorem}
\begin{proof}
 By series (\ref{series-D}), we have
 $$ D^{(m+1)}(x;t) = \frac{m+1}{1-t}\;D^{(m)}(x;t) $$
 and consequently we have the identity
 $$  D^{(m+1)}_n(x) = (m+1) \sum_{k=0}^n { n \choose k } (n-k)! D^{(m)}_k(x) $$
 which simplifies in identity (\ref{id-Dx-000}).
\end{proof}

\begin{theorem}
 Let $ U_{m,n} $ be the $ m \times n $ matrix all of whose entries are equal to $ 1 $,
 $ U_n = U_{n,n} $, $ U_n(x) = U_n+(x-1)I_n $ (where $ I_n $ is the identity matrix of order $ n $),
 and let
 $$
  A_n^{(m)}(x) =
  \begin{bmatrix}
   U_n(x) & U_{n,m} \\
   U_{m,n} & U_m
  \end{bmatrix}.
 $$
 Then, we have
 \begin{equation}\label{formula-Dx-permanemt}
  D_n^{(m)}(x) = \per A_n^{(m)}(x) \, .
 \end{equation}
\end{theorem}
\begin{proof}
 Let $ A_n^{(m)}(x) = [ a_{i,j} ] $, where $ a_{i,i} = x $ for $ i = 1, 2, \ldots, n $,
 and $ a_{i,j} = 1 $ in all other cases.
 Let $ \Fix(\pi) $ be the set of fixed points of a permutation $ \pi \in \SS_n^{(m)} $.
 By the definition of the permanent of a matrix, we have
 $$
  \per A_n^{(m)}(x) = \sum_{\sigma\in\SS_{m+n}} a_{1,\sigma(1)} \cdots a_{m+n,\sigma(m+n)}
  = \sum_{S\subseteq[n]} \sum_{\pi\in\SS_n^{(m)} \atop \Fix(\pi) = S} x^{|S|}
  = \sum_{k=0}^n { n \choose k } d_{n-k}^{(m)} x^k \, .
 $$
 By definition (\ref{def-Dx}), we have identity (\ref{formula-Dx-permanemt}).
\end{proof}

\begin{remark}
 Expanding the permanent of $ A_n^{(m)}(x) $ along the last column,
 we obtain recurrence (\ref{rec-Fx02}).
\end{remark}

\begin{theorem}
 The polynomials $ D_n^{(m)}(x) $ can be expressed as the double sum
 \begin{equation}\label{formula-Dx-doubleSum}
  D_n^{(m)}(x) = \sum_{i=0}^n \sum_{j=0}^m { n \choose i } { m \choose j } (-1)^{m+n-i-j} (x+i+j-1)^i (i+j)^{m+n-i} \, .
 \end{equation}
\end{theorem}
\begin{proof}
 By identity (\ref{formula-Dx-permanemt})
 and by using \emph{Ryser's formula} \cite[p.\ 26]{Ryser} \cite{Minc}
 to evaluate the permanent of $ A = A_n^{(m)}(x) = [ a_{i,j} ] $,
 we have
 $$
  D_n^{(m)}(x) = \sum_{S\subseteq[m+n]} (-1)^{m+n-|S|} w(A_S)
  = \sum_{I\subseteq[n] \atop J\subseteq[m]} (-1)^{m+n-|I|-|J|} w(A_{I\cup J})
 $$
 where $ A_S = [ a_{i,j} ]_{i\in [m+n],\, j\in S} $ and $ w(A_S) = \prod_{k=1}^{m+n} r_k(A_S) $,
 where $ r_k(A_S) $ is the sum of all elements of the $k$th row of $ A_S $.
 Since $$ w(A_{I\cup J}) = (x+|I|+|J|-1)^i (|I|+|J|)^{m+n-i} $$
 we obtain at once identity (\ref{formula-Dx-doubleSum}).
\end{proof}

Identity (\ref{formula-Dx-doubleSum}) generalizes the formula obtained by Ryser \cite[p.\ 28]{Ryser} \cite{Abramson}
for the ordinary derangement numbers (for $m=0$ and $x=0$).

\begin{theorem}
 The polynomials $ D_n^{(m)}(x) $ admit the integral representation
 \begin{equation}\label{formula-Fx-int}
  D_n^{(m)}(x) = \int_0^{+\infty} t^m (t+x-1)^n\, \ee^{-t}\; \dd t \, .
 \end{equation}
 In particular, for $ x = 0 $, we have
 \begin{equation}\label{formula-d-int}
  d_n^{(m)} = \int_0^{+\infty} t^m (t-1)^n\, \ee^{-t}\; \dd t \, .
 \end{equation}
\end{theorem}
\begin{proof}
 By identity (\ref{formula-Fx01}) and the well-known identity
 $$ \int_0^{+\infty} t^k \ee^{-t}\; \dd t = k! \qquad k \in \NN \, , $$
 we have
 \begin{align*}
 \begin{aligned}
 \MoveEqLeft
  D_n^{(m)}(x)
   = \sum_{k=0}^n { n \choose k } (m+k)! (x-1)^{n-k}
   = \sum_{k=0}^n { n \choose k } (x-1)^{n-k} \int_0^{+\infty} t^{m+k} \ee^{-t}\; \dd t \\
  &= \int_0^{+\infty} t^m \left[ \sum_{k=0}^n { n \choose k } t^k (x-1)^{n-k} \right] \ee^{-t}\; \dd t
   = \int_0^{+\infty} t^m (t+x-1)^n \ee^{-t}\; \dd t \, .
 \end{aligned}
 \end{align*}
\end{proof}

\begin{theorem}
 We have the identities
 \begin{align}
  & D_n^{(m)}(x) = \sum_{k=0}^m { m \choose k } (1-x)^k D_{m+n-k}(x) \label{formula-Fx-Riordan01} \\
  & D_n(x) = \sum_{k=0}^n { n \choose k } \frac{(-1)^k}{(m-k)!} D_{n-k}^{(m)}(x) \label{formula-Fx-Riordan02} \, .
 \end{align}
\end{theorem}
\begin{proof}
 By identity (\ref{formula-Fx-int}), we have
 \begin{align*}
  D_n^{(m)}(x)
  &= \int_0^{+\infty} t^m (t+x-1)^n\, \ee^{-t}\; \dd t \\
  &= \int_0^{+\infty} (1-x+t+x-1)^m (t+x-1)^n\, \ee^{-t}\; \dd t \\
  &= \int_0^{+\infty} \sum_{k=0}^m { m \choose k } (1-x)^k (t+x-1)^{m-k} (t+x-1)^n\, \ee^{-t}\; \dd t \\
  &= \sum_{k=0}^m { m \choose k } (1-x)^k \int_0^{+\infty} (t+x-1)^{m+n-k}\, \ee^{-t}\; \dd t \\
  &= \sum_{k=0}^m { m \choose k } (1-x)^k D_{m+n-k}^{(0)}(x) \, .
 \end{align*}
 This is identity (\ref{formula-Fx-Riordan01}).
 Then, by identity (\ref{series-D}), we obtain the identity
 $$ (1-t)^m D^{(m)}(x;t) = m!\;\frac{\ee^{(x-1)t}}{1-t} = m!\;D(x;t) $$
 which is equivalent to identity (\ref{formula-Fx-Riordan02}).
\end{proof}

\begin{theorem}
 The polynomials $ D_n^{(m)}(x)/m! $ admit the determinantal representation
 \begin{equation}\label{formula-Dx-tridiagonal}
  \frac{D_n^{(m)}(x)}{m!} =
  \begin{vmatrix}
   a_1 & 1 \\
   b_1 & a_2 & 1 \\
       & b_2 & a_3 & 1 \\
       &     & \ddots & \ddots  & \ddots \\
       &     &        & b_{n-2} & a_{n-1} & 1 \\
       &     &        &         & b_{n-1} & a_n
  \end{vmatrix}_{n\times n}
 \end{equation}
 where $ a_k = x+m+k-1 $ and $ b_k = k(x-1) $ for $ k \geq 1 $.
\end{theorem}
\begin{proof}
 The tridiagonal determinants (also called \emph{continuants} \cite[pp.\ 516--525]{Muir} \cite{VeinDale})
 defined on the right-hand side of formula (\ref{formula-Dx-tridiagonal})
 satisfy the recurrence $ y_{n+2} - a_{n+2} y_{n+1} + b_{n+1} y_n = 0 $
 with the initial values $ y_0 = 1 $ and $ y_1 = a_1 $.
 So, the claim follows from recurrence (\ref{rec-Fx})
 and the initial values $ D_0^{(m)}(x) = m! $ and $ D_1^{(m)}(x) = m! (x+m) $.
\end{proof}

\begin{theorem}
 The polynomials $ D_n^{(m)}(x)/m! $ admit the determinantal representation
 \begin{equation}\label{formula-Fx-det}
  \frac{D_n^{(m)}(x)}{m!} =
  \begin{vmatrix}
   a_0 & - 1 \\
   a_1 & a_0 & -1 \\
   a_2 & 2a_1 & a_0 & -1 \\
   a_3 & 3a_2 & 3a_1 & a_0 & -1 \\
   \vdots & \vdots & \vdots & \vdots & \!\!\ddots & \qquad\ddots \\
   { n-2 \choose 0 } a_{n-2} & { n-2 \choose 1 } a_{n-3} & { n-2 \choose 2 } a_{n-4} &
   { n-2 \choose 3 } a_{n-5} & \cdots & { n-2 \choose n-2 } a_0 & -1 \\
   { n-1 \choose 0 } a_{n-1} & { n-1 \choose 1 } a_{n-2} & { n-1 \choose 2 } a_{n-3} &
   { n-1 \choose 3 } a_{n-4} & \cdots & { n-1 \choose n-2 } a_1 & { n-1 \choose n-1 } a_0
  \end{vmatrix}
 \end{equation}
 where $ a_0 = x+m $ and $ a_k = (m+1)k! $ for $ k \geq 1 $.
 In particular, for $x=0$, we have a similar representation for the generalized derangement numbers $ d^{(m)}_n $,
 with $ a_0 = m $ and $ a_k = (m+1)k! $ for $ k \geq 1 $.
 For $x=1$, we have a similar representation for the factorial numbers $ (m+n)! $,
 with $ a_0 = m+1 $ and $ a_k = (m+1)k! $ for $ k \geq 1 $.
\end{theorem}
\begin{proof}
 Let $ b_n $ be the $ n \times n $ determinant appearing on the right-hand side of (\ref{formula-Fx-det}).
 Then, expanding the determinant along the last column, we have the recurrence
 $$ b_{n+1} = \sum_{k=0}^n { n \choose k } a_k b_{n-k} $$
 with the initial value $ b_0 = 1 $.
 If $ a(t) = \sum_{n\geq0} a_n \frac{t^n}{n!} $ and $ b(t) = \sum_{n\geq0} b_n \frac{t^n}{n!} $,
 then we have the differential equation $ b'(t) = a(t) b(t) $.
 So, if we set
 $$ b(t) = \frac{1}{m!}\;D^{(m)}(x;t) = \frac{\ee^{(x-1)t}}{(1-t)^{m+1}} \, , $$
 then we have $ b_0 = 1 $, as requested, and
 $$ a(t) = \frac{b'(t)}{b(t)} = \frac{(x-1)(1-t)+m+1}{1-t} = x-1+\frac{m+1}{1-t}\, . $$
 Hence $ a_0 = x+m $ and $ a_k = (m+1)k! $ for $ k \geq 1 $.
 This proves identity (\ref{formula-Fx-det}).
\end{proof}

\section{Combinatorial identities}\label{sec-combid}

For the polynomials $ D_n^{(m)}(x) $ there are
many combinatorial identities.
In this section, we derive some of them.
\begin{theorem}
 We have the identities
 \begin{equation}\label{id-Appel-01}
  \sum_{k=0}^n { n \choose k } \alpha^{n-k} D^{(m)}_k(x) = D^{(m)}_n(x+\alpha)
 \end{equation}
 and
 \begin{equation}\label{id-Appel-02}
  \sum_{k=0}^n { n \choose k } D^{(r)}_k(x) D^{(s)}_{n-k}(y) =
  \frac{1}{{ r+s \choose r }} \frac{1}{r+s+1}\; D^{(r+s+1)}_n(x+y-1) \, .
 \end{equation}
 In particular, for $ x = 0 $ and $ y = 0 $, we have the identity
 \begin{equation}\label{id-wd01}
  \sum_{k=0}^n { n \choose k } d_k^{(r)} d_{n-k}^{(s)} =
  \frac{1}{{ r+s \choose r }}\,\frac{1}{r+s+1} \sum_{k=0}^n { n \choose k } (-1)^{n-k} d_k^{(r+s+1)} \, .
 \end{equation}
\end{theorem}
\begin{proof}
 Identity (\ref{id-Appel-01}) is equivalent to the identity
 $$ \ee^{\alpha t} D^{(m)}(x;t) = \frac{m!\;\ee^{(x+\alpha-1)t}}{(1-t)^{m+1}} = D^{(m)}(x+\alpha;t) \, . $$
 Similarly, identity (\ref{id-Appel-02}) is equivalent to the identity
 $$
  D^{(r)}(x;t) D^{(s)}(y;t)
  = \frac{r!s!\;\ee^{(x+y-2)t}}{(1-t)^{r+s+2}}
  = \frac{r!s!}{(r+s+1)!}\;D^{(r+s+1)}(x+y-1;t) \, .
 $$
 Finally, identity (\ref{id-wd01}) derives from the fact that
 $$ D^{(r+s+1)}(-1;t) = d^{(r+s+1)}(t)\cdot\ee^{-t}\, . $$
\end{proof}

A \emph{Sheffer matrix} \cite{Roman,RomanRota} \cite[p.\ 309]{Aigner2007}
is an infinite lower triangular matrix $ S = [ s_{n,k} ]_{n,k\geq 0} = (g(t),f(t)) $
whose columns have exponential generating series
$$ s_k(t) = \sum_{n\geq k} s_{n,k}\; \frac{t^n}{n!} = g(t)\frac{f(t)^k}{k!} \, , $$
where $ g(t) $ and $ f(t) $ are exponential formal series
with $ g_0 = 1 $, $ f_0 = 0 $, $ f_1 \ne 0 $, and
$$ s_{n,k} = \frac{n!}{k!}\; [t^n]\, g(t)f(t)^k \, . $$

The \emph{Sheffer transform} associated with the Sheffer matrix $ S = [ s_{n,k} ]_{n,k\geq 0} = (g(t),f(t)) $
is defined, for every exponential series $ h(t) = \sum_{n\geq0} h_n\, \frac{t^n}{n!} $, by
$$ (g(t),f(t))h(t) = g(t) h(f(t)) = \sum_{n\geq0} \left[ \sum_{k=0}^n s_{n,k} h_k \right] \frac{t^n}{n!} \, . $$

The \emph{$r$-Stirling numbers of the first kind} \cite{Broder}
are defined as the entries of the Sheffer matrix $ \big(\frac{1}{(1-t)^r},\log\frac{1}{1-t}\big) $, so that
$$
 \frac{1}{(1-t)^r}\frac{1}{k!}\left(\log\frac{1}{1-t}\right)^{\!\!k} =
 \sum_{n\geq k} { n \brack k }_{\!\!r} \frac{t^n}{n!} \, .
$$
In particular, for $ r = 0 $ and $ r = 1 $, we have the \emph{Stirling numbers of the first kind}
\cite[p.\ 310]{Comtet} \cite[p.\ 48]{Riordan} (\seqnum{A132393},\ \seqnum{A008275}):
$ { n \brack k }_{\!0} = { n \brack k } $ and $ { n \brack k }_{\!1} = { n+1 \brack k+1 } $.
For $ r = 1, 2, \ldots, 10 $, we have sequences
\seqnum{A130534}, \seqnum{A143491}, \seqnum{A143492}, \seqnum{A143493}, \seqnum{A049460},
\seqnum{A051338}, \seqnum{A051339}, \seqnum{A051379}, \seqnum{A051380}, \seqnum{A051523}
in \cite{Sloane}.

The \emph{$r$-Stirling numbers of the second kind} \cite{Broder}
are defined as the entries of the Sheffer matrix $ S^{(r)} = (\ee^{rt},\ee^t-1) $, so that
$$ \ee^{rt}\frac{(\ee^t-1)^k}{k!} = \sum_{n\geq k} { n \brace k }_{\!\!r} \frac{t^n}{n!} \, . $$
In particular, for $ r = 0 $ and $ r = 1 $, we have the \emph{Stirling numbers of the second kind}
\cite[p.\ 310]{Comtet} \cite[p.\ 48]{Riordan} (\seqnum{A008277}):
$ { n \brace k }_{\!0} = { n \brace k } $ and $ { n \brace k }_{\!1} = { n+1 \brace k+1 } $.
For $ r = 2, 3, 4, 5 $ we have sequences
\seqnum{A143494}, \seqnum{A143495}, \seqnum{A143496}, \seqnum{A193685} in \cite{Sloane}.
The row polynomials of $ S^{(r)} $ are the \emph{$r$-exponential polynomials}
$$ S_n^{(r)}(x) = \sum_{k=0}^n { n \brace k }_{\!\!r} x^k $$
with exponential generating series
$$ S^{(r)}(x;t) = \sum_{n\geq0} S_n^{(r)}(x)\;\frac{t^n}{n!} = \ee^{rt}\ee^{x(\ee^t-1)} \, . $$
For $r = 0$, we have the ordinary \emph{exponential polynomials} $ S_n(x) $,
whose exponential generating series are denoted by $ S(x;t) $.
Moreover, the row sums of $ S^{(r)} $ are the \emph{$r$-Bell numbers}
$ b_n^{(r)} = S_n^{(r)}(1) = \sum_{k=0}^n { n \brace k }_{\!\!r} $, \cite{Mezo},
with exponential generating series
$$ b^{(r)}(t) = \sum_{n\geq0} b_n^{(r)} \frac{t^n}{n!} = \ee^{rt}\ee^{\ee^t-1} \, . $$
For $ r = 0 $, we have the ordinary \emph{Bell numbers} $ b_n $ \cite[p.\ 210]{Comtet} (\seqnum{A000110}).

The \emph{Lah numbers} \cite[p.\ 156]{Comtet} \cite[p.\ 44]{Riordan} (\seqnum{A008297})
are defined as the entries of the Sheffer matrix
$ L = (1,\frac{t}{1-t}) $, so that
$$ \frac{1}{k!}\left(\frac{t}{1-t}\right)^{\!k} = \sum_{n\geq k} { n \lah k } \; \frac{t^n}{n!} \, . $$
The row polynomials of $ L $ are the \emph{Lah polynomials}
$$ L_n(x) = \sum_{k=0}^n { n \lah k } x^k \, , $$
with exponential generating series
$$ L(x;t) = \sum_{n\geq0} L_n(x)\,\frac{t^n}{n!} = \ee^{\frac{xt}{1-t}} \, . $$
The row sums of $ L $ are the \emph{cumulative Lah numbers} $ \ell_n = \sum_{k=0}^n { n \lah k } $,
\cite[p.\ 194]{RiordanId} (\seqnum{A000262}), with exponential generating series
$$ \ell(t) = \sum_{n\geq0} \ell_n\,\frac{t^n}{n!} = \ee^{\frac{t}{1-t}} \, . $$

\begin{theorem}
 We have the identity
 \begin{equation}\label{id-Fx-S-01}
  \sum_{k=0}^n { n \brace k }_{\!\!r} (-1)^k D_k^{(m)}(x) =
  m! \sum_{k=0}^n { n \choose k } (r-m-1)^{n-k} S_k(1-x) \, .
 \end{equation}
 In particular, for $ r = 0 $ and $ x = 0 $, we have the identity
 \begin{equation}\label{id-D0-S-01}
  \sum_{k=0}^n { n \brace k } (-1)^k d_k^{(m)} = m! \sum_{k=0}^n { n \choose k } (-1)^{n-k} (m+1)^{n-k} b_k
 \end{equation}
 and, for $ r = 1 $ and $ x = 0 $, we have the identity
 \begin{equation}\label{id-D0-S-02}
  \sum_{k=0}^n { n+1 \brace k+1 } (-1)^k d_k^{(m)} = m! \sum_{k=0}^n { n \choose k } (-1)^{n-k} m^{n-k} b_k \, .
 \end{equation}
\end{theorem}
\begin{proof}
 We have
 $$ (\ee^{rt},-\ee^t+1)\, D^{(m)}(x;t) = \ee^{rt}\frac{m!\,\ee^{(x-1)(-\ee^t+1)}}{\ee^{(m+1)t}} = m!\,\ee^{(r-m-1)t} S(1-x;t) $$
 from which we obtain identity (\ref{id-Fx-S-01}).
\end{proof}

\begin{theorem}
 The polynomials $ D_n^{(m)}(x) $ can be expressed as
 \begin{equation}\label{formula-D-Lah}
  D_n^{(m)}(x) = \frac{m!}{{ m+n \choose m }} \sum_{k=0}^n { m+n \choose m+k } { m+k \lah m } D_{n-k}(x) \, .
 \end{equation}
 In particular, for $ x = 0 $, we have
 $$  d_n^{(m)} = \frac{m!}{{ m+n \choose m }} \sum_{k=0}^n { m+n \choose m+k } { m+k \lah m } d_{n-k} \, , $$
 and for $ x = 1 $, we have
 $$ (m+n)! = \frac{m!}{{m+n \choose m}} \sum_{k=0}^n { m+n \choose m+k } { m+k \lah m } (n-k)! \, . $$
\end{theorem}
\begin{proof}
 By series (\ref{series-D}), we have
 \begin{align*}
  D^{(m)}(x;t)
  &= \frac{m!^2}{t^m}\; \frac{1}{m!}\left(\frac{t}{1-t}\right)^{\!\!m} \cdot \frac{\ee^{(x-1)t}}{1-t} \\
  &= \frac{m!^2}{t^m}\; \sum_{n\geq m} { n \lah m } \frac{t^n}{n} \cdot \sum_{n\geq0} D_n(x)\, \frac{t^n}{n!} \\
  &= \frac{m!^2}{t^m}\; \sum_{n\geq m} \left[ \sum_{k=m}^n { n \choose k } { k \lah m } D_{n-k}(x) \right] \frac{t^n}{n!} \\
  &= m!^2\; \sum_{n\geq m} \left[ \sum_{k=m}^n { n \choose k } { k \lah m } D_{n-k}(x) \right] \frac{t^{n-m}}{n!} \\
  &= m!^2\; \sum_{n\geq0} \left[ \sum_{k=m}^{m+n} { m+n \choose k } { k \lah m } D_{m+n-k}(x) \right] \frac{t^n}{(m+n)!} \\
  &= \sum_{n\geq0} \frac{m!^2n!}{(m+n)!}
      \left[ \sum_{k=0}^n { m+n \choose m+k } { m+k \lah m } D_{n-k}(x) \right] \frac{t^n}{n!}
 \end{align*}
 from which we obtain identity (\ref{formula-D-Lah}).
\end{proof}

\begin{theorem}
 We have the identity
  \begin{equation}\label{id-Fx-Lah-02}
  \sum_{k=0}^n { m+n \choose m+k } \frac{n!}{k!} (-1)^k D_k^{(m)}(x) = m! L_n(1-x) \, .
 \end{equation}
 In particular, for $ x = 0 $, we have
 \begin{equation}\label{id-wd02}
  \sum_{k=0}^n { m+n \choose m+k } \frac{n!}{k!} (-1)^k d_k^{(m)} = m! \ell_n \, .
 \end{equation}
\end{theorem}
\begin{proof}
 Consider the Sheffer matrix
 $$ \Big[ L^{(m)}_{n,k} \Big]_{n,k\geq0} = \left(\frac{1}{(1+t)^{m+1}},\frac{t}{1+t}\right) $$
 whose entries are
 $$
  L^{(m)}_{n,k}
  = \frac{n!}{k!} [t^n] \frac{1}{(1+t)^{m+1}}\left(\frac{t}{1+t}\right)^{\!\!k}
  = \frac{n!}{k!} [t^n] \frac{t^k}{(1+t)^{m+k+1}}
  = { m+n \choose m+k } \frac{n!}{k!} (-1)^{n-k} \, .
 $$
 Since
 $$
  \left(\frac{1}{(1+t)^{m+1}},\frac{t}{1+t}\right) D^{(m)}(x;t)
  = \frac{1}{(1+t)^{m+1}}\,D^{(m)}\Big(x;\frac{t}{1+t}\Big)
  = m!\,\ee^{\frac{(x-1)t}{1+t}} = m!\,L(1-x;-t) \, ,
 $$
 we obtain at once identity (\ref{id-Fx-Lah-02}).
\end{proof}

\section{Connection identities}\label{sec-conid}

Let $ \{ p_n(x) \}_{n\in\NN} $ and $ \{ q_n(x) \}_{n\in\NN} $ be two polynomial sequences.
If $ \deg p_n(x) = n $ for all $ n \in \NN $, then the sequence $ \{ p_n(x) \}_{n\in\NN} $
forms a basis for the vector space $ \RR[x] $ of polynomials
and consequently there exist some coefficients $ C_{n,k} $ for which
$$ q_n(x) = \sum_{k=0}^n C_{n,k}\, p_k(x) \, . $$
The coefficients $ C_{n,k} $ are unique and are called \emph{connection constants}
\cite[p.\ 131]{Roman} \cite{RomanRota,DamianiDAntonaNaldi,DAntonaMunarini}.
In this section, we consider some connection identities for the polynomials $ D_n^{(m)}(x) $.
Identities (\ref{def-Dx}), (\ref{formula-Fx01}), (\ref{id-Appel-01}), (\ref{formula-D-Lah})
are examples of this kind.
We use an umbral approach due to G.-C. Rota.
Suppose to have a connection identity
$$ q_n(x) = \sum_{k=0}^n C_{n,k}\, D_k^{(m)}(x) \, . $$
To obtain the connection constants, we define the linear map $ \map{\ff_m}{\RR[x]}{\RR[x]} $
by setting $ \ff_m(D_n^{(m)}(x)) = x^n $, for every $ n \in \NN $, and then by extending it by linearity.
Then, the preceding identity becomes
$$ \ff_m(q_n(x)) = \sum_{k=0}^n C_{n,k}\, x^k \, . $$
Now, we extend $ \ff_m $ to exponential formal series, as follows. First, we have
$$
 \ff_m(D^{(m)}(x;t)) =
 \ff_m\left(\sum_{n\geq0} D_n^{(m)}(x)\,\frac{t^n}{n!}\right)
 = \sum_{n\geq0} \ff_m(D_n^{(m)}(x))\,\frac{t^n}{n!}
 = \sum_{n\geq0} x^n\,\frac{t^n}{n!}
 = \ee^{xt} \, ,
$$
that is $$ \ff_m\left(\frac{m!\,\ee^{(x-1)t}}{(1-t)^{m+1}}\right) = \ee^{xt} $$
from which we have
\begin{equation}\label{def-phi}
 \ff_m(\ee^{(x-1)t}) = \frac{1}{m!}\;(1-t)^{m+1}\,\ee^{xt}\, .
\end{equation}
Now, let $ q(x;t) = \sum_{n\geq0} q_n(x)\,\frac{t^n}{n!} $
be the exponential generating series for the polynomials $ q_n(x) $.
Then, the connection constants $ C_{n,k} $ are determined by the series
$$
 \sum_{n\geq0} \left[\sum_{k=0}^n C_{n,k}\, x^k \right] \frac{t^n}{n!} =
 \sum_{n\geq0} \ff_m(q_n(x)) \frac{t^n}{n!} =
 \ff_m(q(x;t)) \, .
$$
In the next few theorems, we use this method.

\begin{theorem}
 We have the connection identity
 \begin{equation}\label{id-Fx-Con02}
  (x-1)^n = \frac{1}{m!} \sum_{k=0}^n { n \choose k } { m+1 \choose n-k } (-1)^{n-k} (n-k)!\, D_k^{(m)}(x) \, .
 \end{equation}
\end{theorem}
\begin{proof}
 In this case, we have $ q_n(x) = (x-1)^n $ and $ q(x;t) = \ee^{(x-1)t} $.
 So, by applying (\ref{def-phi}), we have the series
 $$
  \ff_m(\ee^{(x-1)t}) = \frac{1}{m!}\;(1-t)^{m+1}\,\ee^{xt}
  = \frac{1}{m!}\;\sum_{n\geq0}
    \left[ \sum_{k=0}^n { n \choose k } { m+1 \choose n-k } (-1)^{n-k} (n-k)! x^k \right] \frac{t^n}{n!}
 $$
 from which we obtain the coefficients
 $$ C_{n,k}^{(m)} = \frac{1}{m!} { n \choose k } { m+1 \choose n-k } (-1)^{n-k} (n-k)! \, . $$
 This proves identity (\ref{id-Fx-Con02}).
\end{proof}

\begin{theorem}
 We have the connection identity
 \begin{equation}\label{id-Fx-Con}
  D_n^{(r)}(x) = \sum_{k=0}^n { n \choose k } { s-r \choose n-k } \frac{r!}{s!}\, (-1)^{n-k} (n-k)!\, D_k^{(s)}(x) \, .
 \end{equation}
\end{theorem}
\begin{proof}
 In this case, we have $ q_n(x) = D_n^{(r)}(x) $ and $ q(x;t) = D^{(r)}(x;t) $.
 So, by applying (\ref{def-phi}), we have the series
 \begin{align*}
  \ff_s(D^{(r)}(x;t))
  &= \frac{r!}{(1-t)^{r+1}}\,\ff_s(\ee^{(x-1)t})
   = \frac{r!}{s!}\;(1-t)^{s-r}\,\ee^{xt} \\
  &= \frac{r!}{s!} \sum_{n\geq0}
     \left[\sum_{k=0}^n { n \choose k } { s-r \choose n-k } (-1)^{n-k} (n-k)! x^k \right] \frac{t^n}{n!}
 \end{align*}
 from which we have
 $$ C_{n,k}^{(r,s)} = { n \choose k } { s-r \choose n-k } \frac{r!}{s!}\, (-1)^{n-k} (n-k)! \, . $$
 This proves identity (\ref{id-Fx-Con}).
\end{proof}

\begin{theorem}
 We have the connection identities
 \begin{equation}\label{id-Fx-Con03}
  S^{(r)}_n(1-x) = \frac{1}{m!} \sum_{k=0}^n { n \brace k }_{\!\!r+m+1} (-1)^k\, D_k^{(m)}(x)
 \end{equation}
 and
 \begin{equation}\label{id-Fx-Con03bis}
  D_n^{(m)}(x) = m! \sum_{k=0}^n { n \brack k }_{\!\!r+m+1} (-1)^k\, S^{(r)}_k(1-x) \, .
 \end{equation}
 In particular, for $ x = 1 $, we have the identities
 \begin{align}
  & \sum_{k=0}^n { n \brace k }_{\!\!r+m+1} (-1)^k\, (m+k)! = m!\, r^n \\
  & \sum_{k=0}^n { n \brack k }_{\!\!r+m+1} (-1)^k\, r^k = \frac{(m+n)!}{m!} \, .
 \end{align}
\end{theorem}
\begin{proof}
 In this case, we have $ q_n(x) = S^{(r)}_n(1-x) $ and $ q(x;t) = \ee^{rt}\ee^{(1-x)(\ee^t-1)} $.
 So, by applying (\ref{def-phi}), we have the series
 \begin{align*}
  \ff_m(\ee^{rt}\ee^{(1-x)(\ee^t-1)})
  &= \ee^{rt} \ff_m(\ee^{(x-1)(-\ee^t+1)})
   = \frac{1}{m!}\;\ee^{(r+m+1)t}\,\ee^{-x(\ee^t-1)} \\
  &= \frac{1}{m!}\;S^{(r+m+1)}(-x;t)
   = \frac{1}{m!}\;\sum_{n\geq0} \left[ \sum_{k=0}^n { n \brace k }_{r+m+1} (-1)^k x^k \right] \frac{t^n}{n!}
 \end{align*}
 from which we have
 $$ C_{n,k}^{(m)} = \frac{(-1)^k}{m!} { n \brace k }_{r+m+1} \, . $$
 This proves identity (\ref{id-Fx-Con03}).
 Then, using the inversion formula for the $r$-Stirling numbers, we obtain identity (\ref{id-Fx-Con03bis}).
\end{proof}

\section{Expectation and variance}\label{sec-ExpVar}

Let $ X_n^{(m)} $ be the random variable counting the number of fixed points of a permutation in $ \SS_n^{(m)} $.
Then $ D_{n,k}^{(m)} $ is the number of permutations $ \pi \in \SS_n^{(m)} $ such that $ X_n^{(m)}(\pi) = k $.
So, the \emph{expectation} of $ X_n^{(m)} $,
i.e., the expected number of fixed points in a random permutation $ \pi \in \SS_n^{(m)} $,
can be expressed \cite[p.\ 284]{BenderWilliamson} as
$$
 E_n^{(m)} = \EE[X_n^{(m)}] = \frac{1}{|\SS_n^{(m)}|}\sum_{k=0}^n k D_{n,k}^{(m)}
 = \frac{1}{(m+n)!}\sum_{k=0}^n k D_{n,k}^{(m)} \, .
$$
Similarly, since
$$
 \EE[(X_n^{(m)})^2] = \frac{1}{|\SS_n^{(m)}|}\sum_{k=0}^n k^2 D_{n,k}^{(m)}
 = \frac{1}{(m+n)!}\sum_{k=0}^n k^2 D_{n,k}^{(m)} \, ,
$$
the \emph{variance} of $ X_n^{(m)} $, defined by $ \var[X_n^{(m)}] = \EE[(X_n^{(m)})^2] - \EE[X_n^{(m)}]^2 $,
can be expressed as
$$
 V_n^{(m)} = \var[X_n^{(m)}]
 = \frac{1}{(m+n)!}\sum_{k=0}^n k^2 D_{n,k}^{(m)} - \left(\frac{1}{(m+n)!}\sum_{k=0}^n k D_{n,k}^{(m)}\right)^{\!\!2}.
$$
To compute the expectation and the variance of $ X_n^{(m)} $, we need next
\begin{theorem}
 We have the identity
 \begin{equation}\label{id-krDmnk}
  \sum_{k=0}^n k^r D_{n,k}^{(m)} = n! \sum_{k=0}^{\min(n,r)} { r \brace k } \frac{(m+n-k)!}{(n-k)!} \, .
 \end{equation}
 In particular, for $ r = 1, 2 $, we have the identities
 \begin{align}
  & \sum_{k=0}^n k D_{n,k}^{(m)} = n (m+n-1)! && (n\geq1) \label{id-k1Dmnk} \\
  & \sum_{k=0}^n k^2 D_{n,k}^{(m)} = n (m+2n-2) (m+n-2)! && (n\geq2) \label{id-k2Dmnk} \, .
 \end{align}
\end{theorem}
\begin{proof}
 Let $ \theta_x = x D_x $. Then, we have the generating series
 \begin{align*}
  \begin{aligned}
   \MoveEqLeft
   \sum_{n\geq0} \left[ \sum_{k=0}^n k^r D_{n,k}^{(m)} \right] \frac{t^n}{n!}
    = \sum_{n\geq0} \left[ \sum_{k=0}^n k^r D_{n,k}^{(m)} x^k \right]_{x=1} \frac{t^n}{n!}
    = \left[ \sum_{n\geq0} \theta_x^r D_n^{(m)}(x) \frac{t^n}{n!} \right]_{x=1} \\
   &= \left[ \theta_x^r D_n^{(m)}(x;t) \right]_{x=1}
    = \frac{m!\,\ee^{-t}}{(1-t)^{m+1}} \left[ \theta_x^r \ee^{xt} \right]_{x=1}
    = \frac{m!\,\ee^{-t}}{(1-t)^{m+1}} \left[ S_r(xt)\, \ee^{xt} \right]_{x=1} \\
   &= \frac{m!}{(1-t)^{m+1}}\;S_r(t)
    = \sum_{k=0}^r { r \brace k } \frac{m!t^k}{(1-t)^{m+1}}
    = \sum_{n\geq0} \left[\sum_{k=0}^{\min(n,r)} { r \brace k } { m+n-k \choose m } m! \right] t^n
  \end{aligned}
 \end{align*}
 from which we have identity (\ref{id-krDmnk}).
 For $ r = 1 $ and $ n \geq 1 $, we have
 $$
  n! \sum_{k=0}^{1} { 1 \brace k } \frac{(m+n-k)!}{(n-k)!} =
  n! \, \frac{(m+n-1)!}{(n-1)!} = n (m+n-1)! \, .
 $$
 For $ r = 2 $ and $ n \geq 2 $, we have
 \begin{align*}
  n! \sum_{k=0}^{2} { 2 \brace k } \frac{(m+n-k)!}{(n-k)!}
  &= n! \left( \frac{(m+n-1)!}{(n-1)!} + \frac{(m+n-2)!}{(n-2)!} \right) \\
  &= n (m+2n-2) (m+n-2)! \, .
 \end{align*}
\end{proof}

In the ordinary case ($m=0$), we have the well known remarkable fact that the expectation and variance
of the number of fixed points in a random permutation in $ \SS_n $ are always equal to $1$.
In the general case ($m\geq1$), the expectation and variance
of the number of fixed points in a random permutation in $ \SS_n^{(m)} $ are no more always equal to $1$,
even though this is true asymptotically.
More precisely, we have
\begin{theorem}
 For $ n \geq 2 $, we have
 \begin{equation}
  E_n^{(m)} = \frac{n}{m+n}
  \qquad\text{and}\qquad
  V_n^{(m)} = \frac{n(m^2+2mn+n^2-2m-n)}{(m+n)^2(m+n-1)} \, .
 \end{equation}
 Moreover, we have
 \begin{equation}
  \lim_{n\to+\infty} E_n^{(m)} = 1
  \qquad\text{and}\qquad
  \lim_{n\to+\infty} V_n^{(m)} = 1 \, .
 \end{equation}
\end{theorem}
\begin{proof}
 By identity (\ref{id-k1Dmnk}), we have that the expectation is given by
 $$ E_n^{(m)} = \frac{1}{(m+n)!} \sum_{k=0}^n k D_{n,k}^{(m)} = \frac{n(m+n-1)!}{(m+n)!} = \frac{n}{m+n}\, . $$
 Similarly, by identities (\ref{id-k1Dmnk}) and (\ref{id-k2Dmnk}), we have that the variance is given by
 \begin{align*}
  V_n^{(m)}
  &= \frac{1}{(m+n)!} \sum_{k=0}^n k^2 D_{n,k}^{(m)} - \left(\frac{1}{(m+n)!}\sum_{k=0}^n k D_{n,k}^{(m)}\right)^{\!\!2} \\
  &= \frac{n(m+2n-2)(m+n-2)!}{(m+n)!} - \left(\frac{n}{(m+n)}\right)^{\!\!2} \\
  &= \frac{n(m+2n-2)}{(m+n)(m+n-1)} - \frac{n^2}{(m+n)^2} \\
  &= \frac{n(m^2+2mn+n^2-2m-n)}{(m+n)^2(m+n-1)} \, .
 \end{align*}
 Finally, it is easy to see that $ E_n^{(m)} \sim 1 $ and $ V_n^{(m)} \sim 1 $ for $ n \to +\infty $.
\end{proof}

\section{Asymptotics}\label{sec-asy}

We conclude by obtaining some asymptotic results
for the generalized rencontres numbers $ D_{n,k}^{(m)} $
and the generalized derangement numbers $ d_n^{(m)} $.

\begin{theorem}
 We have the asymptotic equivalence
 \begin{equation}\label{asy-dmn}
  \frac{d_n^{(m)}}{n!} \sim n^m \ee^{-1} \qquad \text{ for } n \to +\infty \, .
 \end{equation}
\end{theorem}
\begin{proof}
 Wang et al. \cite{WangMiskaMezo} proved that
 $$ D_r(n) \sim \frac{(n+r)!}{r!}\;\ee^{-1} \qquad \text{ for } n \to +\infty \, . $$
 Then, by relation (\ref{id-D-d}), for $ n \to +\infty $, we have
 $$
  \frac{d_n^{(m)}}{n!}
  = \frac{1}{n!}\;\frac{1}{{ n+m \choose m }}\; D_m(n+m)
  \sim \frac{1}{n!}\; \frac{1}{{ n+m \choose m }}\; \frac{(n+2m)!}{m!}\;\ee^{-1}
  = \frac{(n+2m)!}{(n+m)!}\;\ee^{-1} \, .
 $$
 By applying the Stirling formula $ n! \sim n^n \ee^{-n} \sqrt{2n\pi} $, for $ n \to +\infty $, we have
 \begin{align*}
  \frac{d_n^{(m)}}{n!}
  & \sim \frac{(n+2m)^{n+2m}\ee^{-n-2m}\sqrt{2(n+2m)\pi}}{(n+m)^{n+m}\ee^{-n-m}\sqrt{2(n+m)\pi}}\;\ee^{-1} \\
  & = \left(1+\frac{m}{n+m}\right)^{\!\!n} \frac{(n+2m)^{2m}}{(n+m)^{m}}\;\sqrt{\frac{n+2m}{n+m}}\;\ee^{-m-1}
    \sim \ee^m \frac{n^{2m}}{n^m}\;\ee^{-m-1}
    = n^m\;\ee^{-1} \, .
 \end{align*}
\end{proof}

\begin{remark}
 From the asymptotic relation (\ref{asy-dmn}), we have that the series $ d^{(m)}(t) $ converges for $ |t| < 1 $.
 So, for instance, for $ t = 1/2 $ and $ t = -1/2 $, by series (\ref{series-dm}), we have
 $$
  \sum_{n\geq0} \frac{d_n^{(m)}}{2^nn!} = m!\,2^{m+1}\,\ee^{-1/2}
  \qquad\text{and}\qquad
  \sum_{n\geq0} (-1)^n\,\frac{d_n^{(m)}}{2^nn!} = m!\,\Big(\frac{2}{3}\Big)^{\!m+1}\,\ee^{1/2} \, .
 $$
\end{remark}

\begin{theorem}
 We have the asymptotic equivalences
 \begin{equation}\label{asy-Dmnk01}
  \frac{D_{n,k}^{(m)}}{n!} \sim \frac{(n-k)^m}{k!}\;\ee^{-1} \qquad \text{ for } n \to +\infty
 \end{equation}
 and
 \begin{equation}\label{asy-Dmnk02}
  \frac{D_{n,k}^{(m)}}{(m+n)!} \sim \frac{\ee^{-1}}{k!} \qquad \text{ for } n \to +\infty \, .
 \end{equation}
\end{theorem}
\begin{proof}
 By definition (\ref{def-Dnk}) and equivalence (\ref{asy-dmn}), for $ n \to +\infty $, we have
 $$
  \frac{D_{n,k}^{(m)}}{n!} = \frac{1}{k!}\;\frac{d_{n-k}^{(m)}}{(n-k)!}
  \sim \frac{1}{k!}\;(n-k)^{m}\;\ee^{-1} \, .
 $$
 Then, by using this equivalence and the Stirling formula $ n! \sim n^n\ee^{-n}\sqrt{2n\pi} $, we have
 \begin{align*}
  \frac{D_{n,k}^{(m)}}{(m+n)!}
  & \sim \frac{n!}{(n+m)!}\;\frac{(n-k)^m}{k!}\;\ee^{-1}
   \sim \frac{n^n\ee^{-n}\sqrt{2n\pi}}{(n+m)^{n+m}\ee^{-n-m}\sqrt{2(n+m)\pi}}\;\frac{(n-k)^m}{k!}\;\ee^{-1} \\
  & = \left(1+\frac{m}{n}\right)^{\!\!-n}\sqrt{\frac{n}{n+m}}\;\left(\frac{n-k}{n+m}\right)^{\!\!m}\;\frac{\ee^{m-1}}{k!}
    \sim \ee^{-m}\;\frac{\ee^{m-1}}{k!}
    = \frac{\ee^{-1}}{k!} \, .
 \end{align*}
 This completes the proof.
\end{proof}

\begin{thebibliography}{99}
 \bibitem{Abramson}
  M. Abramson,
  A note on permanents,
  \emph{Canad. Math. Bull.} \textbf{14} (1971), 1--4.
 \bibitem{Aigner2007}
  M. Aigner,
  \emph{A Course in Enumeration},
  Springer, 2007.
 \bibitem{Appell}
  P. Appell,
  Sur une classe de polyn\^omes,
  \emph{Ann. Sci. \'Ecole Norm. Sup.} (2) \textbf{9} (1880), 119--144.
 \bibitem{BeggasFerrariZagaglia}
  F. Beggas, M. M. Ferrari and N. Zagaglia Salvi,
  Combinatorial interpretations and enumeration of particular bijections,
  \emph{Riv. Mat. Univ. Parma} \textbf{8} (2017), 161--169.
 \bibitem{BenderWilliamson}
  E. A. Bender and S. G. Williamson,
  \emph{Foundations of Combinatorics with Applications},
  Dover, 2006.
 \bibitem{Broder}
  A. Z. Broder,
  The $r$-Stirling numbers,
  \emph{Discrete Math.} \textbf{49} (1984),  241--259.
 \bibitem{Carlson}
  B. C. Carlson,
  Polynomials satisfying a binomial theorem,
  \emph{J. Math. Anal. Appl.} \textbf{32} (1970), 543--558.
 \bibitem{Comtet}
  L. Comtet,
  \emph{Advanced Combinatorics},
  Reidel, 1974.
 \bibitem{DamianiDAntonaNaldi}
  E. Damiani, O. D'Antona and G. Naldi,
  On the connection constants,
  \emph{Stud. Appl. Math.} \textbf{85} (1991), 289--302.
 \bibitem{DAntonaMunarini}
  O. M. D'Antona and E. Munarini,
  A combinatorial interpretation of the connection constants for persistent sequences of polynomials,
  \emph{European J. Combin.} \textbf{26} (2005), 1105--1118.
 \bibitem{Mezo}
  I. Mez\"o,
  The $r$-Bell numbers,
  \emph{J. Integer Seq.} \textbf{14} (2011), Article 11.1.1.
 \bibitem{Minc}
  H. Minc,
  \emph{Permanents},
  Addison-Wesley, 1978.
 \bibitem{Montmort}
  P. R. Montmort,
  \emph{Essay d'Analyse sur les Jeux de Hazard},
  1708, (Second edition, 1713).
\bibitem{Muir}
  T. Muir,
  \emph{The Theory of Determinants in the Historical Order of Developement},
  Dover, 1960.
 \bibitem{MunariniA}
  E. Munarini,
  Combinatorial identities for Appell polynomials,
  \emph{Appl. Anal. Discrete Math.}, to be published.
 \bibitem{Navarrete1}
  E. Navarrete,
  Forbidden patterns and the alternating derangement sequence,
  preprint, 2016, \url{https://arxiv.org/abs/1610.01987}.
 \bibitem{Navarrete2}
  E. Navarrete,
  Generalized $k$-shift forbidden substrings in permutations,
  preprint, 2017, \url{https://arxiv.org/abs/1610.06217}.
 \bibitem{Riordan}
  J. Riordan,
  \emph{An Introduction to Combinatorial Analysis},
  John Wiley \& Sons, 1958.
 \bibitem{RiordanId}
  J. Riordan,
  \emph{Combinatorial Identities},
  John Wiley \& Sons, 1968.
 \bibitem{Roman}
  S. Roman,
  \emph{The Umbral Calculus},
  Academic Press, 1984.
 \bibitem{RomanRota}
  S. M. Roman and G.-C. Rota,
  The umbral calculus,
  \emph{Adv. in Math.} \textbf{27} (1978), 95--188.
 \bibitem{Ryser}
  H. J. Ryser,
  \emph{Combinatorial Mathematics},
  John Wiley and Sons, 1963.
 \bibitem{Sloane}
  N. J. A. Sloane,
  \emph{On-Line Encyclopedia of Integer Sequences},
  \url{http://oeis.org/}.
 \bibitem{Takacs}
  L. Tak\'acs,
  The problem of coincidences,
  \emph{Arch. Hist. Exact Sci.} \textbf{21} (1979/80), 229--244.
 \bibitem{VeinDale}
  R. Vein and P. Dale,
  \emph{Determinants and Their Applications in Mathematical Physics},
  Springer-Verlag, 1999.
 \bibitem{WangMiskaMezo}
  C. Wang, P. Miska and I. Mez\"o,
  The $r$-derangement numbers,
  \emph{Discrete Math.} \textbf{340} (2017), 1681--1692.
\end{thebibliography}

\bigskip

\hrule
\bigskip
\noindent
\emph{2000 Mathematics Subject Classification}:
Primary: 05A19, Secondary: 05A05, 05A15, 05A40, 11B73. \\
\emph{Keywords}: permutation, derangement, rencontres number, rencontres polynomial, probl\`eme des rencontres,
 permanent, Ryser's formula, Appell polynomial, Sheffer matrix, connection constant,
 generating function, umbral calculus, orthogonal polynomial,
 $r$-Stirling number, $r$-exponential polynomial, Bell number, Lah number, Lah polynomial.
\bigskip
\hrule
\bigskip
\noindent
(Concerned with sequences 
\seqnum{A000110},
\seqnum{A000153},
\seqnum{A000166},
\seqnum{A000255},
\seqnum{A000261},
\seqnum{A000262},
\seqnum{A001909},
\seqnum{A001910},
\seqnum{A008275},
\seqnum{A008277},
\seqnum{A008290},
\seqnum{A008297},
\seqnum{A049460},
\seqnum{A051338},
\seqnum{A051339},
\seqnum{A051379},
\seqnum{A051380},
\seqnum{A051523},
\seqnum{A055790},
\seqnum{A123513},
\seqnum{A130534},
\seqnum{A132393},
\seqnum{A143491},
\seqnum{A143492},
\seqnum{A143493},
\seqnum{A143494},
\seqnum{A143495},
\seqnum{A143496},
\seqnum{A176732},
\seqnum{A176733},
\seqnum{A176734},
\seqnum{A176735},
\seqnum{A176736},
\seqnum{A193685},
\seqnum{A277563},
\seqnum{A277609},
\seqnum{A280425},
\seqnum{A280920},
\seqnum{A284204},
\seqnum{A284205},
\seqnum{A284206}, and
\seqnum{A284207}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 1 2017;
revised version received  February 19 2018.
Published in {\it Journal of Integer Sequences}, March 7 2018.
\bigskip
\hrule

\bigskip

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

\end{document}

.