\documentclass[12pt,reqno]{article}

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

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

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

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

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

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

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

\DeclareMathOperator{\Ei}{\mathrm{Ei}}

\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 
Derangements and Alternating Sum of \\
\vskip .1in
Permutations by Integration}
\vskip 1cm
\large
Mehdi Hassani\\
Department of Mathematics\\
University of Zanjan\\
University Blvd.\\
45371-38791 Zanjan\\
Iran\\
\href{mailto:mehdi.hassani@znu.ac.ir}{\tt mehdi.hassani@znu.ac.ir}\\
\end{center}

\vskip .2 in

\begin{abstract}
Let $P(n,j)$ denote the number of $j$-permutations of $n$ objects. In
this paper we obtain 
the generating function for the alternating sequence
$\left(-1\right)^j P(n,j)$. Our method gives an integral representation
for the difference $D_n-\frac{n!}{e}$, where $D_n$ denotes the number of
derangements on $n$ objects. Using this integral representation, we compute
the moments of this difference, and we also get an asymptotic expansion
for $D_n$ with coefficients in terms of the Bell numbers $B_n$. 
We also give a simple proof of the irrationality of $e$.
\end{abstract}

\section{Introduction and summary of results}
Let $C(n,j)$ denote the number of $j$-combinations of $n$ objects,
and $P(n,j)$ denote the number of $j$-permutations of $n$ objects,
counting the number of ways to choose an ordered selection of
$j$ items from a set of $n$ items. Many summation
identities concerning $C(n,j)$ can be found in the literature. For example,
see \cite[Section 0.15]{table-ints-series-prods}, \cite[Section
2.3.4]{handbook-discrete-math}, and \cite[pp.\ 343--355]{spivey} for a
list of 334 identities. 

In comparison, there are
fewer summation identities 
concerning $P(n,j)$ in the literature. Our first theorem provides an
integral representation for the alternating sum over $P(n,j)$. The
relation in this theorem is equivalent to one given by Askey and Ismail
\cite{askey-ismail} and Kayll \cite{kayll}. Our simple proof differs
from their and is included for completeness.

\begin{theorem}\label{key-theorem}
Let $a\geq 1$ be a fixed real. For any positive integer $n$ let 
\begin{equation}\label{Ln-int}
L_n(a)=\int_1^a\log^n t\,d t.
\end{equation}
Then, for any integer $n\geq 1$ and for $x\geq 0$,
\begin{equation}\label{sum-P-x}
\sum_{j=0}^n \left(-1\right)^j P(n,j) x^{n-j}=\frac{\left(-1\right)^n n!+L_n(e^x)}{e^{x}}.
\end{equation}
More precisely, by letting $x=1$ in \eqref{sum-P-x} we obtain 
\begin{equation}\label{sum-P-alter}
\sum_{j=0}^n \left(-1\right)^j P(n,j)=\frac{\left(-1\right)^n n!+L_n(e)}{e}.
\end{equation}
\end{theorem}

As an application of Theorem \ref{key-theorem}, we continue our study
\cite{hassani-jis} of $D_n$, the number of derangements on a set of
cardinality $n$. We observe that the alternating sum at the left hand
side of \eqref{sum-P-alter} and $D_n$ are related as follows:
\[
D_n
=n!\sum_{j=0}^n\frac{(-1)^j}{j!}
=\left(-1\right)^n n!\sum_{j=0}^n\frac{(-1)^{n-j}}{(n-j)!}
=\left(-1\right)^n\sum_{j=0}^n (-1)^j P(n,j).
\]
Thus, by considering the relation \eqref{sum-P-alter}, we obtain
\begin{equation}\label{Dn-n!e-Ln}
D_n=\frac{n!}{e}+\left(-1\right)^n\frac{L_n(e)}{e},
\end{equation}
for each integer $n\geq 1$. The relation \eqref{Dn-n!e-Ln} is true for
$n=0$, too. This relation provides an explicit integral representation for
the difference 
\[ 
D_n-\frac{n!}{e}.
\]
Using this integral representation
we compute the moments of this difference, as follows:
\begin{theorem}\label{D-Ln-thm} We have
\begin{equation}\label{sum-Dn-n!e}
\sum_{n=1}^\infty\Big(D_n-\frac{n!}{e}\Big)=-1+\frac{1}{e}+\frac{\Ei(2)-\Ei(1)}{e^2}\approxeq -0.218114,
\end{equation}
where $\Ei$ denotes the exponential integral function defined by the Cauchy principal value of the integral
\[
\Ei(x)=-\int_{-x}^\infty\frac{e^{-z}}{z}\,d z,
\]
and
\begin{equation}\label{sum-Dn-n!e-2}
\sum_{n=1}^\infty\Big(D_n-\frac{n!}{e}\Big)^2=-\frac{\left(e-1\right)^2}{e^2}+\frac{4}{e^2}\int_0^\frac{1}{2}h(z)\,d z\approxeq 0.433113,
\end{equation}
where
\[
h(z)=\frac{e^{2z}}{\sqrt{1-z^2}}\arctan\frac{z}{\sqrt{1-z^2}}
+\frac{e^{2-2z}}{\sqrt{2z-z^2}}\arctan\frac{z}{\sqrt{2z-z^2}}.
\]
Moreover, for each integer $k\geq 1$ the following multiple integral representation holds:
\begin{equation}\label{sum-Dn-n!e-k}
\sum_{n=1}^\infty\Big(D_n-\frac{n!}{e}\Big)^k=-\frac{\left(e-1\right)^k}{e^k}+\frac{1}{e^k}\int_0^1\cdots\int_0^1\frac{e^{x_1+\dots+x_k}}{1-\left(-1\right)^k x_1\cdots x_k}\,d\mathbf{X},
\end{equation}
where $\mathbf{X}$ represents the $k$-tuple $(x_1,\dots,x_k)$.
\end{theorem}

Ismail and Simeonov \cite{ismail-simeonov} derived the asymptotics of
certain combinatorial numbers defined on multi-sets when the number of
sets tends to infinity, but the sizes of the sets remain fixed. Their
study includes the asymptotics of generalized derangements, numbers
related to $k$-partite graphs, and exponentially weighted derangements. As
another application of Theorem \ref{key-theorem}, by using the integral
representation for the difference $D_n-\frac{n!}{e}$ we deduce a full
asymptotic expansion for $D_n$ with coefficients in terms of the Bell
numbers $B_n$.

\begin{theorem}\label{Dn-n!e-asym-thm}
Given any positive integer $r$, for any integer $n\geq 1$ we have the asymptotic expansions
\begin{equation}\label{Ln-e-e-asym}
\frac{L_n(e)}{e}=\sum_{k=1}^r\left(-1\right)^{k-1}\frac{B_k}{n^k}+O\left(\frac{1}{n^{r+1}}\right),
\end{equation}
and
\begin{equation}\label{Dn-n!e-asym}
D_n=\frac{n!}{e}+\sum_{k=1}^r\left(-1\right)^{n+k-1}\frac{B_k}{n^k}+O\left(\frac{1}{n^{r+1}}\right),
\end{equation}
where $B_k$ denotes the $k$-th Bell number and the constant of $O$-term does
not exceed $B_{r+1}$ in both expansions.
\end{theorem}

\section{Two remarks}

\begin{remark}
The relation \eqref{sum-P-alter} is an analogue to the identity $\sum_{j=0}^n (-1)^j C(n,j)=0$. For an analogue to the identity $\sum_{j=0}^n C(n,j)=2^n$, we observe that
\[
0<e-\sum_{j=0}^n\frac{1}{j!}=\sum\limits_{j=1}^\infty\frac{1}{(n+j)!}
=\frac{1}{n!}\sum\limits_{j=1}^\infty\prod\limits_{k=1}^j\frac{1}{n+k}
<\frac{1}{n!}\sum\limits_{j=1}^\infty\frac{1}{(n+1)^j}=\frac{1}{n \cdot n!}.
\]
Thus, for each $n\geq 1$ we obtain 
\begin{equation}\label{sum-P-floor-e}
\sum_{j=0}^n P(n,j)=n!\sum_{j=0}^n\frac{1}{j!}=\lfloor e\,n!\rfloor.
\end{equation}
The author previously
introduced some enumerative
applications of the relation \eqref{sum-P-floor-e} concerning the number
of paths and cycles in complete graphs \cite{hassani-mg, hassani-springer}.
\end{remark}

\begin{remark} 
The relation \eqref{sum-P-alter} enables us to provide a simple proof of the irrationality of the number $e$. We observe that $0\leq\log t\leq 1$ for $1\leq t\leq e$. Thus,
\[
0<L_n(e)\leq\int_1^ed t=e-1<e,
\]
which implies $0<\frac{L_n(e)}{e}<1$ for each positive integer $n$. Now we assume that $e$ is rational. Let $e=\frac{\alpha}{\beta}$ for some positive integers $\alpha$ and $\beta$. The relation \eqref{sum-P-alter} with $n=\alpha$ gives
\[
\sum_{j=0}^\alpha (-1)^j P(n,j)=(-1)^\alpha(\alpha-1)!\beta+\frac{L_\alpha(e)}{e},
\]
implying that $\frac{L_\alpha(e)}{e}$ is an integer, a contradiction.
\end{remark}


\section{Proof of Theorem \ref{key-theorem}}
\begin{proof}
Using integration by parts we obtain
\[
\int\log^r t\,d t=t\log^{r}t-r\int\log^{r-1} t \,d t.
\]
Thus, the recurrence $L_j(a)=a\log^j a-jL_{j-1}(a)$ holds for any integer $j\geq 1$. Multiplying both sides of this recurrence by $\frac{(-1)^j}{j!}$,
we can rewrite it as
\[
\frac{(-1)^j}{j!}L_j(a)-\frac{(-1)^{j-1}}{(j-1)!}L_{j-1}(a)=\frac{(-1)^j}{j!}a\log^j a.
\]
Summing over $1\leq j\leq n$ yields
\[
\frac{(-1)^n}{n!}L_n(a)-L_{0}(a)=\sum_{j=1}^n\frac{(-1)^j}{j!}a\log^j a.
\]
Note that $L_{0}(a)=a-1$. Thus,
\[
\frac{(-1)^n}{n!}L_n(a)=-1+\sum_{j=0}^n\frac{(-1)^j}{j!}a\log^j a=-1+\sum_{j=0}^n\frac{(-1)^{-j}}{j!}a\log^j a,
\]
and
\[
L_n(a)=(-1)^{n+1}n!+a\sum_{j=0}^n\left(-1\right)^{n-j}\frac{n!}{j!}\log^{j} a.
\]
After a change of variables in the summation we get
\[
L_n(a)=(-1)^{n+1}n!+a\sum_{j=0}^n\left(-1\right)^j P(n,j)\log^{n-j} a.
\]
Letting $a=e^x$ for $x\geq 0$ we get \eqref{sum-P-x},
which concludes the proof.
\end{proof}

\section{Proof of Theorem \ref{D-Ln-thm}}
\begin{proof}
We conclude from \eqref{Dn-n!e-Ln} that
\begin{align*}
\sum_{n=1}^\infty\Big(D_n-\frac{n!}{e}\Big)
&=\sum_{n=1}^\infty\left(-1\right)^n\frac{L_n(e)}{e}
=\frac{1}{e}\lim_{N\to\infty}\sum_{n=1}^N\left(-1\right)^nL_n(e)\\
&=\frac{1}{e}\lim_{N\to\infty}\sum_{n=1}^N\left(-1\right)^n\int_1^e\log^n t\,d t
=\frac{1}{e}\lim_{N\to\infty}\int_1^e\sum_{n=1}^N\left(-\log t\right)^nd t\\
&=\frac{1}{e}\lim_{N\to\infty}\int_1^e-\frac{\log t}{1+\log t}\left(1+\left(-\log t\right)^{N+1}\right)d t.
\end{align*}
Now we use the bounded convergence theorem \cite[Theorem 3.26]{axler} to interchange the limit and integral in the last relation. Consequently,
\begin{align*}
\sum_{n=1}^\infty\Big(D_n-\frac{n!}{e}\Big)
&=-\frac{1}{e}\int_1^e\lim_{N\to\infty}\frac{\log t}{1+\log t}\left(1+\left(-\log t\right)^{N+1}\right)d t\\
&=-\frac{1}{e}\int_1^{e}\frac{\log t}{1+\log t}\left(1+\lim_{N\to\infty}\left(-\log t\right)^{N+1}\right)d t\\
&=-\frac{1}{e}\int_1^{e}\frac{\log t}{1+\log t}\,d t
=-\frac{1}{e}\int_1^{e}\frac{\log t}{1+\log t}\,d t.
\end{align*}
To evaluate the last integral we apply the change of variable $-z=1+\log t$, satisfying $t=e^{-1-z}$ and $d t=-t\,d z=-\frac{1}{e}\,e^{-z}d z$. Therefore
\begin{align*}
\int_1^{e}\frac{\log t}{1+\log t}\,d t
&=\frac{1}{e}\int_{-2}^{-1}\left(1+\frac{1}{z}\right)e^{-z}\,d z\\
&=\frac{1}{e}\int_{-2}^{-1}e^{-z}\,d z-\frac{1}{e}\left(-\int_{-2}^{-1}\frac{e^{-z}}{z}\right)d z
=\frac{e^2-e}{e}-\frac{\Ei(2)-\Ei(1)}{e}.
\end{align*}
This gives \eqref{sum-Dn-n!e}. To prove \eqref{sum-Dn-n!e-2} we follow an argument due to LeVeque \cite{leveque}, which has been described by Aigner and Ziegler \cite[Chapter 9]{proofs}. In \eqref{Ln-int} we apply the change of variable $z=\log t$, satisfying $t=e^{z}$ and $d t=e^zd z$. Accordingly,
\begin{equation}\label{Ln-e-int-0-1}
L_n(e)=\int_0^1 z^ne^z\,d z.
\end{equation}
Repeated use of \eqref{Ln-e-int-0-1} shows that
\[
L_n(e)^2
=\left(\int_0^1 x^ne^x\,d x\right)\left(\int_0^1 y^ne^y\,d y\right)
=\int_0^1\int_0^1\left(xy\right)^ne^{x+y}\,d A_{x,y}.
\]
Hence, we conclude from \eqref{Dn-n!e-Ln} that
\begin{align*}
\sum_{n=1}^\infty\Big(D_n-\frac{n!}{e}\Big)^2
&=-\frac{L_0(e)^2}{e^2}+\frac{1}{e^2}\sum_{n=0}^\infty L_n(e)^2\\
&=-\frac{\left(e-1\right)^2}{e^2}+\frac{1}{e^2}\sum_{n=0}^\infty\int_0^1\int_0^1\left(xy\right)^ne^{x+y}\,d A_{x,y}.
\end{align*}
Since the function $e^{x+y}$ is bounded on the region $[0,1]\times [0,1]$, uniform convergence of the geometric series allows us to change the order of sum and integrals. Accordingly,
\[
\sum_{n=1}^\infty\Big(D_n-\frac{n!}{e}\Big)^2=-\frac{\left(e-1\right)^2}{e^2}+\frac{1}{e^2}\,I,
\]
where
\[
I=\int_0^1\int_0^1\frac{e^{x+y}}{1-xy}\,d A_{x,y}.
\]
The same reasoning applies to the case of other moments. Thus, meanwhile we obtain \eqref{sum-Dn-n!e-k}. Let us compute $I$. For this purpose, we apply the change of coordinates. Let $u=\frac{y+x}{2}$ and $v=\frac{y-x}{2}$. We get the new domain of integration from old domain by first rotating it by $-45^\circ$ and then shrinking it by a factor of $\sqrt{2}$. This new domain of integration and the function to be integrated are symmetric with respect to the $u$-axis. Also, $d A_{x,y}=2d A_{u,v}$. Therefore,
\begin{align*}
I
&=4\int_0^\frac{1}{2}\int_0^u\frac{e^{2u}}{1-u^2+v^2}\,d v\,d u
+4\int_\frac{1}{2}^1\int_0^{1-u}\frac{e^{2u}}{1-u^2+v^2}\,d v\,d u\\
&=4\int_0^\frac{1}{2}\frac{e^{2u}}{\sqrt{1-u^2}}\arctan\frac{u}{\sqrt{1-u^2}}\,d u
+4\int_\frac{1}{2}^1\frac{e^{2u}}{\sqrt{1-u^2}}\arctan\frac{1-u}{\sqrt{1-u^2}}\,d u.
\end{align*}
Substituting $u=1-z$ in the last integral and simplifying yields \eqref{sum-Dn-n!e-2}. This is the desired conclusion.
\end{proof}

\section{Proof of Theorem \ref{Dn-n!e-asym-thm}}
\begin{proof} We conclude from the integral representation \eqref{Ln-e-int-0-1} that
\[
L_n(e)=\int_0^1 z^ne^z\,d z
=\int_0^1 z^n\sum_{j=0}^\infty\frac{z^j}{j!}\,d z
=\int_0^1 \sum_{j=0}^\infty\frac{z^{n+j}}{j!}\,d z.
\]
Since the last sum converges uniformly for $0\leq z\leq 1$, we may change the order of sum and integral. Therefore,
\[
L_n(e)=\sum_{j=0}^\infty\int_0^1\frac{z^{n+j}}{j!}\,d z
=\sum_{j=0}^\infty\frac{1}{j!(n+j+1)}.
\]
An easy computation shows that
\[
\frac{1}{n+b}=\sum_{k=1}^r \left(-1\right)^{k-1}\frac{b^{k-1}}{n^k}+\frac{\left(-1\right)^r}{n+b}\left(\frac{b}{n}\right)^r,
\]
for $n+b\neq 0$. If we take $b=j+1$, then
\begin{align*}
L_n(e)
&=\sum_{j=0}^\infty\sum_{k=1}^r\frac{\left(-1\right)^{k-1}}{n^k}\frac{\left(j+1\right)^{k-1}}{j!}
+\left(-1\right)^r\sum_{j=0}^\infty\frac{1}{j!(n+j+1)}\left(\frac{j+1}{n}\right)^r\\
&=\sum_{k=1}^r\frac{\left(-1\right)^{k-1}}{n^k}\sum_{j=0}^\infty\frac{\left(j+1\right)^{k-1}}{j!}
+\frac{\left(-1\right)^r}{n^r}\sum_{j=0}^\infty\frac{\left(j+1\right)^r}{j!(n+j+1)}.
\end{align*}
Dobi\'{n}ski's formula \cite[p.\ 178]{w-em} states that the $k$-th Bell number $B_k$ equals
\[
B_k=\frac{1}{e}\sum_{j=0}^\infty\frac{j^k}{j!}.
\]
On account of this formula, we have
\[
\sum_{j=0}^\infty\frac{\left(j+1\right)^{k-1}}{j!}
=\sum_{j=0}^\infty\frac{\left(j+1\right)^{k}}{(j+1)!}
=\sum_{j=1}^\infty\frac{j^k}{j!}
=\sum_{j=0}^\infty\frac{j^k}{j!}=e\,B_k,
\]
and
\[
\sum_{j=0}^\infty\frac{\left(j+1\right)^r}{j!(n+j+1)}\leq
\frac{1}{n}\sum_{j=0}^\infty\frac{\left(j+1\right)^r}{j!}
=\frac{1}{n}\sum_{j=0}^\infty\frac{\left(j+1\right)^{r+1}}{(j+1)!}
=\frac{e\,B_{r+1}}{n}.
\]
Therefore, we obtain \eqref{Ln-e-e-asym}. This gives \eqref{Dn-n!e-asym} when substituted in \eqref{Dn-n!e-Ln}, and this is precisely the assertion of the theorem.
\end{proof}

\section{Acknowledgments} The author is greatly indebted to the referee for a thorough reading of the manuscript and helpful comments.

\begin{thebibliography}{10}

\bibitem{proofs}
M. Aigner and G. M. Ziegler, \textit{Proofs from The Book}, 6th edition,
Springer, 2018. 

\bibitem{askey-ismail}
R. A. Askey and M. E. H. Ismail, Permutation problems and special functions, \textit{Canadian J. Math.} \textbf{28} (1976), 853--874.

\bibitem{axler}
S. Axler, \textit{Measure, Integration \& Real Analysis}, Graduate Texts
in Mathematics 282, Springer, 2020.

\bibitem{table-ints-series-prods}
I. S. Gradshteyn and I. M. Ryzhik, \textit{Table of Integrals, Series,
and Products}, 7th Edition, Academic Press, 2007.

\bibitem{hassani-mg}
M. Hassani, Cycles in graphs and derangements, \textit{Math. Gaz.}
\textbf{88} (2004), 123--126.

\bibitem{hassani-jis}
M. Hassani, Derangements and applications, \textit{J. Integer Sequences}
\textbf{6} (2003), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL6/Hassani/hassani5.html}{Article 03.1.2}.

\bibitem{hassani-springer}
M. Hassani, Enumeration by $e$, in T. M. Rassias and N. J. Daras, eds.,
\textit{Modern Discrete Mathematics and Analysis: With Applications
in Cryptography, Information Systems and Modelling}, Springer, 2018,
pp.\ 227--233.

\bibitem{ismail-simeonov}
M. E. H. Ismail and P. Simeonov, Asymptotics of generalized derangements, \textit{Adv. Comput. Math.} \textbf{39} (2013), 101--129.

\bibitem{kayll}
P. M. Kayll, Integrals don't have anything to do with discrete math,
do they? \textit{Math. Mag.} \textbf{84} (2011), 108--119.

\bibitem{leveque}
W. J. LeVeque, \textit{Topics in Number Theory}, Vol.~1, Addison-Wesley,
1956.

\bibitem{handbook-discrete-math} 
K. H. Rosen, J. G. Michaels, J. L. Gross, J. W. Grossman, and D. R. Shier,
\textit{Handbook of Discrete and Combinatorial Mathematics}, CRC Press,
2000.

\bibitem{spivey}
M. Z. Spivey, \textit{The Art of Proving Binomial Identities}, CRC
Press, 2019.

\bibitem{w-em}
E. W. Weisstein, \textit{CRC Concise Encyclopedia of Mathematics},
2nd edition, CRC Press, 2003.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A16, 11B73, 26A06.

\noindent \emph{Keywords: } 
derangement, permutation, Bell number, integration by parts.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000166} and
\seqnum{A000110}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 23 2020;
revised version received July 28 2020.
Published in {\it Journal of Integer Sequences},
July 29 2020.

\bigskip
\hrule
\bigskip

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

\end{document}