\documentclass[12pt,reqno]{article}
%\sloppy

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


\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.2in}
\setlength{\textheight}{8.0in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}



\begin{document}
\makeatletter

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


\def\endofproofmark{$\Box$}


\def\RR{{\mathbb R}}
\def\NN{{\mathbb N}}



\def\endofproofmark{$\Box$}

\begin{center}
\vskip 1cm {\LARGE\bf Derangements and Applications} \vskip 1cm
\large Mehdi Hassani\\
\vskip .5cm
Department of Mathematics\\
Institute for Advanced
Studies in Basic Sciences\\
Zanjan, Iran\\
\href{mailto:mhassani@iasbs.ac.ir}{\tt mhassani@iasbs.ac.ir}\\
\end{center}

\date{}
%\maketitle

\pagestyle{myheadings}
%%%%%%%%%%%%%%%%%%%%%%%%%MACROS%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theo}{Theorem}[section]
\newtheorem{prop}[theo]{Proposition}
\newtheorem{lemma}[theo]{Lemma}
\newtheorem{cor}[theo]{Corollary}
\newtheorem{problem}{Problem}
\def\frameqed{\framebox(5.2,6.2){}}
\def\deshqed{\dashbox{2.71}(3.5,9.00){}}
\def\ruleqed{\rule{5.25\unitlength}{9.75\unitlength}}
\def\myqed{\rule{8.00\unitlength}{12.00\unitlength}}
\def\qed{\hbox{\hskip 6pt\vrule width 7pt height11pt depth1pt\hskip 3pt}
\bigskip}
\newenvironment{proof}{\trivlist\item[\hskip\labelsep{\bf Proof}:]}{\hfill
 $\frameqed$ \endtrivlist}
\newcommand{\COM}[2]{{#1\choose#2}}
%%%%%%%%%%%%%%%%%%%END%OF%MACROS%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\thispagestyle{empty}
\null
\addtolength{\textheight}{2cm}

\begin{abstract}

In this paper we introduce some formulas for the number of
derangements.  Then we define the derangement function and use the
software package MAPLE to obtain some integrals related to the
incomplete gamma function and also to some hypergeometric
summations.



\end{abstract}

\section{Introduction and motivation}
A permutation of $S_n=\{1,2,3,\cdots,n\}$ that has no fixed points
is a \textit{derangement} of $S_n$. Let $D_n$ denote the number of
derangements of $S_n$. It is well-known that
\begin{equation}
D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!},
\end{equation}
\begin{equation}
D_n=\|\frac{n!}{e}\|\hspace{5mm}(\|~\|~\mbox{denotes the nearest
integer}).
\end{equation}
We can rewrite (2) as follows:
$$
D_n=\lfloor\frac{n!}{e}+\frac{1}{2}\rfloor.
$$
We can generalize the above formula replacing $\frac{1}{2}$ by
every $m\in [\frac{1}{3},\frac{1}{2}]$. In fact we have:

\begin{theo}
Suppose $n\geq1$ is an integer, we have

\begin{equation}
D_n=\left\{ \begin{array}{ll}
\lfloor\frac{n!}{e}+m_1\rfloor, & n ~{\rm is ~odd}, m_1\in[0,\frac{1}{2}]; \\
\lfloor\frac{n!}{e}+m_2\rfloor, & n ~{\rm is ~even},
m_2\in[\frac{1}{3},1].
\end{array}
\right.
\end{equation}
\end{theo}

For a proof of this theorem, see Hassani [3].  At the end of the
next
section we give another proof of it.\\

On the other hand, the idea of proving (2) leads to a family of
formulas for the number of derangements, as follows:  we have
$$
|\frac{n!}{e}-D_n|\leq\frac{1}{(n+1)}+\frac{1}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)(n+3)}+\cdots .
$$
Let $M(n)$ denote the right side of above inequality.   We have
$$
M(n)<\frac{1}{(n+1)}+\frac{1}{(n+1)^2}+\cdots=\frac{1}{n},
$$
and therefore
\begin{eqnarray}
D_n=\lfloor\frac{n!}{e}+\frac{1}{n}\rfloor\hspace{5mm}(n\geq2).
\end{eqnarray}
Also we can get a better bound for $M(n)$ as follows
$$
M(n)<\frac{1}{n+1}(1+\frac{1}{(n+2)}+\frac{1}{(n+2)^2}+\cdots)=\frac{n+2}{(n+1)^2},
$$
and similarly
\begin{eqnarray}
D_n=\lfloor\frac{n!}{e}+\frac{n+2}{(n+1)^2}\rfloor\hspace{5mm}(n\geq2).
\end{eqnarray}
The above idea is extensible, but before extending we recall a
useful formula (see [2, 3]). For every positive integer $n\geq1$,
we have
\begin{eqnarray}
\sum_{i=0}^{n}\frac{n!}{i!}=\lfloor en!\rfloor.
\end{eqnarray}

\section{New families and some other formulas}

\begin{theo}
Suppose $m$ is an integer and $m\geq3$. The number of derangements
of $n$ distinct objects $(n\geq2)$ is
\begin{eqnarray}
D_n=\lfloor(\frac{\lfloor
e(n+m-2)!\rfloor}{(n+m-2)!}+\frac{n+m}{(n+m-1)(n+m-1)!}+e^{-1})n!\rfloor
-\lfloor en!\rfloor.
\end{eqnarray}
\end{theo}
\begin{proof}
For $m\geq3$ we have
$$
|\frac{n!}{e}-D_n|<\frac{1}{(n+1)}(1+\frac{1}{(n+2)}(
\cdots1+\frac{1}{(n+m-1)}(\frac{n+m}{n+m-1})\cdots)).
$$
Let $M_m(n)$ denote the right side of the above inequality; we
have\\
$$
(n+1)(n+2)(n+3)\cdots(n+m-1)M_m(n)=
$$
$$
(n+2)(n+3)\cdots(n+m-1)+(n+3)\cdots(n+m-1)+\cdots+(n+m-1)+\frac{n+m}{n+m-1},
$$
and dividing by $(n+1)(n+2)(n+3)\cdots(n+m-1)$ we obtain
$$
M_m(n)=n!(\frac{n+m}{(n+m-1)(n+m-1)!}+\sum_{i=n+1}^{n+m-2}\frac{1}{i!}).
$$
Therefore
\begin{eqnarray}
D_n=\lfloor\frac{n!}{e}+n!(\frac{n+m}{(n+m-1)(n+m-1)!}
+\sum_{i=n+1}^{n+m-2}\frac{1}{i!})\rfloor.
\end{eqnarray}
Now consider (6) and rewrite (8) by using
$\sum_{i=n+1}^{n+m-2}\frac{1}{i!}=
\sum_{i=0}^{n+m-2}\frac{1}{i!}-\sum_{i=0}^{n}\frac{1}{i!}$. 
The proof is complete.
\end{proof}
\begin{cor} For $n\geq2$, we have
\begin{eqnarray}
D_n=\lfloor(e+e^{-1})n!\rfloor-\lfloor en!\rfloor.
\end{eqnarray}
\end{cor}
\begin{proof} We give two proofs.\\
Method 1. Because (7) holds for all $m\geq3$, we have
$$
D_n=\lim_{m\rightarrow\infty}\lfloor(\frac{\lfloor
e(n+m-2)!\rfloor}{(n+m-2)!}
+\frac{n+m}{(n+m-1)(n+m-1)!}+e^{-1})n!\rfloor-\lfloor en!\rfloor
$$
$$
=\lfloor(e+e^{-1})n!\rfloor-\lfloor en!\rfloor.
$$
Method 2. By using (6), we have
$$
M(n)=n!(e-\sum_{i=0}^{n}\frac{1}{i!})=en!-\lfloor
en!\rfloor=\{en!\} \hspace{5mm}(n\geq1,\{~\}~\mbox{denotes the
fractional part}),
$$
and the proof follows.
\end{proof}
Now
$$
\lim_ {m\rightarrow\infty} M_m(n)=M(n),
$$
\\
and if we put $M_1(n)=\frac{1}{n}$ and
$M_2(n)=\frac{n+2}{(n+1)^2}$ (see formulas (4) and (5)), then
$$
M_{m+1}(n)<M_m(n)\hspace{5mm}(n\geq1).
$$

Now we find bounds sharper than $\{en!\}$ for $e^{-1}n!-D_n$ and
consequently another family of formulas for $D_n$. This family is
an extension of (9).
\begin{theo}
Suppose $m$ is an integer and $m\geq1$. The number of derangements
of $n$ distinct objects $(n\geq2)$ is
\begin{eqnarray}
D_n=\lfloor(\frac{\{e(n+2m)!\}}{(n+2m)!}+
\sum_{i=1}^{m}\frac{n+2i-1}{(n+2i)!}+e^{-1})n!\rfloor.
\end{eqnarray}
\end{theo}
\begin{proof}
Since $m\geq1$ we have
$$
\frac{e^{-1}n!-D_n}{(-1)^{n+1}}=
n!\sum_{i=1}^{\infty}(\frac{1}{(n+2i-1)!}-\frac{1}{(n+2i)!})<
n!(\sum_{i=1}^{m}\frac{n+2i-1}{(n+2i)!}+\sum_{i=2m+1}^{\infty}\frac{1}{(n+i)!}).
$$
Let $N_m(n)$ denote the right member of above inequality.
Considering (6), we have
$$
N_m(n)=n!(
\sum_{i=1}^{m}\frac{n+2i-1}{(n+2i)!}+\frac{\{e(n+2m)!\}}{(n+2m)!}),
$$
and for $(n\geq2)$, $D_n=\lfloor e^{-1}n!+N_m(n)\rfloor$. This completes the proof.
\end{proof}
\begin{cor} For all integers $m, n\geq1$, we have
$$
N_{m+1}(n)<N_m(n),\ \ \ N_1(n)<\{en!\}.
$$
\end{cor}
Therefore we have the following chain of bounds for
$|\frac{n!}{e}-D_n|$
$$
|\frac{n!}{e}-D_n|<\cdots<N_2(n)<N_1(n)<\{en!\}<\cdots<M_2(n)<M_1(n)<1\hspace{5mm}(n\geq2).
$$
{\bf Question 1.} Can we find the following limit?
$$
\lim_ {m\rightarrow\infty} N_m(n).
$$
Before going to the next section we give our proof of Theorem 1.
The idea of present proof is hidden in Apostol's analysis [1],
where he proved the irrationality of $e$ by using (11). And now,
\begin{proof} (Proof of Theorem 1) Suppose $k\geq1$ be an integer, we have
\begin{eqnarray}
0<\frac{1}{e}-\sum_{i=0}^{2k-1}\frac{(-1)^i}{i!}<\frac{1}{(2k)!}
\end{eqnarray}
so, for every $m_1$, we have
$$
m_1<\frac{(2k-1)!}{e}+m_1-\sum_{i=0}^{2k-1}\frac{(-1)^i(2k-1)!}{i!}<
m_1+\frac{1}{2}
$$
if $0\leq m_1\leq\frac{1}{2}$ , then
$$
\sum_{i=0}^{2k-1}\frac{(-1)^i(2k-1)!}{i!}=\lfloor\frac{(2k-1)!}{e}+m_1\rfloor.
$$
Similarly since (11), for every $m_2$ we have
$$
m_2-1<\frac{(2k)!}{e}+m_2-\sum_{i=0}^{2k}\frac{(-1)^i(2k)!}{i!}<m_2.
$$
Now, if $m_2\geq\frac{1}{3}$, then
$$
0<\frac{(2k)!}{e}+m_2-\sum_{i=0}^{2k}\frac{(-1)^i(2k)!}{i!}
$$
therefore, if $\frac{1}{3}\leq m_2\leq 1$, we obtain
$$
\sum_{i=0}^{2k}\frac{(-1)^i(2k)!}{i!}=\lfloor\frac{(2k)!}{e}+m_2\rfloor.
$$
This completes the proof.
\end{proof}
In the next section there are some applications of the proven
results.

\section{The derangement function, incomplete gamma and hypergeometric functions}

Let's find other formulas for $D_n$.   The computer algebra program MAPLE
yields that
$$
D_n=(-1)^n\texttt{hypergeom}([1,-n],[~~],1),
$$
and
$$
D_n=e^{-1}\Gamma(n+1,-1),
$$
where $\texttt{hypergeom}([1,-n],[~~],1)$ is MAPLE's notation for
a hypergeometric function.  More generally,
$\texttt{hypergeom}([a_1~~a_2~\cdots~a_p],[b_1~~b_2~\cdots~b_q],x)$
is defined as follows (see [4]),
$$
~_pF_q\left[\begin{array}{cccc}
  a_1 & a_2 & \cdots & a_p \\
  b_1 & b_2 & \cdots & b_q
\end{array};x\right]=\sum_{k\geq 0}t_k
x^k$$
where
$$
\frac{t_{k+1}}{t_k}=
\frac{(k+a_1)(k+a_2)\cdots(k+a_p)}{(k+b_1)(k+b_2)\cdots(k+b_q)(k+1)}x.
$$
Also $\Gamma(n+1,-1)$ is an incomplete gamma function and
generally defined as follows:
$$
\Gamma(a,z)=\int_{z}^{\infty}e^{-t}t^{a-1}dt\hspace{5mm}(Re(a)>0),
$$
Now, because we know the value of $D_n$, we can estimate some
summations and integrals. To do this, we define the
\textit{derangement function}, a natural generalization of
derangements, denoted by $D_n(x)$, for every integer $n\geq0$ and
every real $x$ as follows:
$$
D_n(x) = \left\{ \begin{array}{ll}
n!\sum_{i=0}^{n}\frac{x^i}{i!}, & x\neq0; \\
n!, & x=0.
\end{array}
\right.
$$
It is easy to obtain the following generalized recursive relations:
$$
D_n(x)=(x+n)D_{n-1}(x)-x(n-1)D_{n-2}(x)=x^n+nD_{n-1}(x),\hspace{5mm}
(D_0(x)=1,D_1(x)=x+1).
$$
Note that $D_n(x)$ is a nice polynomial. 
Its value for $x=-1$ is
$D_n$, for $x=0$ is the number of permutations of $n$ distinct
objects and for $x=1$ is $w_{n+2}=$ the number of distinct paths
between every pair of vertices in a complete graph on $n+2$
vertices, and
$$
D_n(1)=\lfloor en!\rfloor\hspace{5mm}(n\geq1),\hspace{5mm} ({\rm
see\ [3]}).
$$
A natural question is \\\\
{\bf Question 2.} Is there any combinatorial meaning for the
value of $D_n(x)$ for other values of $x$?\\\\
The above definitions yield
$$
D_n(x)=x^n~_2F_0\left[\begin{array}{cc}
  1 & -n \\
  -
\end{array};-\frac{1}{x}\right]\hspace{5mm}(x\neq 0),
$$
and
\begin{eqnarray}
D_n(x)=e^x\Gamma(n+1,x).
\end{eqnarray}
We obtain
$$
~_2F_0\left[\begin{array}{cc}
  1 & -n \\
  -
\end{array};-1\right]=\lfloor en!\rfloor,
$$
and
$$
~_2F_0\left[\begin{array}{cc}
  1 & -n \\
  -
\end{array};1\right]=
(-1)^n\left\lfloor\frac{n!+1}{e}\right\rfloor.
$$
Also we have some corollaries.
\begin{cor}
For every real $x\neq0$ we have
$$
~_1F_1\left[\begin{array}{c}
  n+1 \\
  n+2
\end{array};-x\right]=\frac{(n+1)(n!-e^{-x}D_n(x))}{x^{n+1}}.
$$
\end{cor}
\begin{proof}
Obvious.
\end{proof}
\begin{cor}
For every integer $n\geq1$ we have
$$
\int_{-1}^{\infty}e^{-t}t^ndt=e\left\lfloor\frac{n!+1}{e}\right\rfloor,
$$
$$
\int_{0}^{\infty}e^{-t}t^ndt=n!,
$$
$$
\int_{1}^{\infty}e^{-t}t^ndt =\frac{\lfloor en!\rfloor}{e},
$$
and
$$
\int_{0}^{1}e^{-t}t^ndt =\frac{\{en!\}}{e},
$$
$$ \int_{-1}^{0}e^{-t}t^ndt =\left\{
\begin{array}{cc}
-e\{\frac{n!}{e}\} & n ~{\rm is ~odd},\\
e-e\{\frac{n!}{e}\} & n ~{\rm is ~even}.
\end{array}
\right.
$$
$$
\int_{-1}^{1}e^{-t}t^ndt=e\lfloor(e+e^{-1})n!\rfloor-(e+e^{-1})\lfloor
en!\rfloor,
$$
\end{cor}
\begin{proof}
Use relations (3), (6), (9), (12) and the definition of
derangement function in the case $x=0$.
\end{proof}
{\bf Question 3.} Are there any similar formulas for
$~_2F_0\left[\begin{array}{cc}
  1 & -n \\
  -
\end{array};-\frac{1}{x}\right]$ ?
In other words,
given any real number $x$, is there an interval $I$ (dependent on
$x$) such that
$$
n!\sum_{i=0}^{n}\frac{x^i}{i!}=\lfloor e^x
n!+m\rfloor\hspace{5mm}(m\in I_x) ?
$$

\section{Acknowledgements}
I would like to express my gratitude to Dr. J. Rooin for his
valuable guidance. Also I thank the referee for
his/her priceless comments on the third section.

\begin{thebibliography}{99}
\bibitem{apostol}
%1
T.M. Apostol, {\em Mathematical Analysis}, Addison-Wesley, 1974.

\bibitem{cameron}
%2
P.J. Cameron, {\em Combinatorics: Topics, Techniques, Algorithms},
Cambridge University Press, 1994.

\bibitem{hassani}
%3
M. Hassani, Cycles in graphs and derangements, {\em 
Math.\ Gazette}, to appear.

\bibitem{petkovsek-wilf-zeilberger}
%4
M. Petkov\v{s}ek, H.S. Wilf and D. Zeilberger, $A=B$, A. K. Peters,
1996.  Also available at {\tt http://www.cis.upenn.edu/\char'176wilf/AeqB.html}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 05A10,
33B20, 33C20.\ \

\noindent \emph{Keywords: $e$, derangements, derangement
function, incomplete gamma function, hypergeometric function}

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence \seqnum{A000166}.)

\vspace*{+.1in} \noindent Received February 17, 2003;
revised version received  February 24, 2003.
Published in {\it Journal of Integer Sequences} February 25, 2003.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.



\end{document}