Derangements and Applications

Mehdi Hassani

Department of Mathematics Institute for Advanced Studies in Basic Sciences Zanjan, Iran

                     mhassani@iasbs.ac.ir

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.

1 Introduction and motivation

A permutation of S_{n} = {1, 2, 3, ⋯, n} that has no fixed points is a derangement of S_{n}. Let D_{n} denote the number of derangements of S_{n}. It is well-known that

D_{n} = n! ∑_{i=0}^{n} \frac{(−1)^{i}}{i!} ,  (1)
D_{n} = ∥\frac{n!}{e}∥ (∥ ∥ denotes the nearest integer).  (2)

We can rewrite (2) as follows:

D_{n} = ⌊\frac{n!}{e} + \frac{1}{2}⌋.

We can generalize the above formula replacing \frac{1}{2} by every m ∈ [\frac{1}{3}, \frac{1}{2}]. In fact we have:

Theorem 1.1 Suppose n ≥ 1 is an integer, we have

D_{n} = \{ \begin{matrix}⌊\frac{n!}{e} + m_{1}⌋, & n is odd, m_{1} ∈ [0, \frac{1}{2}]; \\ ⌊\frac{n!}{e} + m_{2}⌋, & n is even, m_{2} ∈ [\frac{1}{3}, 1]. \end{matrix}  (3)

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}| ≤ \frac{1}{(n + 1)} + \frac{1}{(n + 1)(n + 2)} + \frac{1}{(n + 1)(n + 2)(n + 3)} + · · · .

Let M(n) denote the right side of above inequality. We have

M(n) < \frac{1}{(n + 1)} + \frac{1}{(n + 1)^{2}} + ⋯ = \frac{1}{n},

and therefore

D_{n} = ⌊\frac{n!}{e} + \frac{1}{n}⌋ (n ≥ 2).  (4)

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}} + ⋯) = \frac{n + 2}{(n + 1)^{2}} ,

and similarly

D_{n} = ⌊\frac{n!}{e} + \frac{n + 2}{(n + 1)^{2}} ⌋ (n ≥ 2).  (5)

The above idea is extensible, but before extending we recall a useful formula (see [2, 3]). For every positive integer n ≥ 1, we have

∑_{i=0}^{n} \frac{n!}{i!} = ⌊en!⌋.  (6)

2 New families and some other formulas

Theorem 2.1 Suppose m is an integer and m ≥ 3. The number of derangements of n distinct objects (n ≥ 2) is

D_{n} = ⌊(\frac{⌊e(n + m − 2)!⌋}{(n + m − 2)!} + \frac{n + m}{(n + m − 1)(n + m − 1)!} + e^{−1})n!⌋ − ⌊en!⌋.  (7)

Proof: For m ≥ 3 we have

|\frac{n!}{e} − D_{n}| < \frac{1}{(n + 1)}(1 + \frac{1}{(n + 2)}(⋯ 1 + \frac{1}{(n + m − 1)}(\frac{n + m}{n + m − 1}) ⋯)).

Let M_{m}(n) denote the right side of the above inequality; we have

(n + 1)(n + 2)(n + 3) ⋯ (n + m − 1)M_{m}(n) =

(n + 2)(n + 3) ⋯ (n + m − 1) + (n + 3) ⋯ (n + m − 1) + ⋯ + (n + m − 1) + \frac{n + m}{n + m − 1},

and dividing by (n + 1)(n + 2)(n + 3) ⋯ (n + m − 1) we obtain

M_{m}(n) = n!(\frac{n + m}{(n + m − 1)(n + m − 1)!} + ∑_{i=n+1}^{n+m−2} \frac{1}{i!}).

Therefore

D_{n} = ⌊\frac{n!}{e} + n!(\frac{n + m}{(n + m − 1)(n + m − 1)!} + ∑_{i=n+1}^{n+m−2} \frac{1}{i!})⌋.  (8)

Now consider (6) and rewrite (8) by using ∑_{i=n+1}^{n+m−2} \frac{1}{i!} = ∑_{i=0}^{n+m−2} \frac{1}{i!} − ∑_{i=0}^{n} \frac{1}{i!}. The proof is complete.

Corollary 2.2 For n ≥ 2, we have

D_{n} = ⌊(e + e^{−1})n!⌋ − ⌊en!⌋.  (9)

Proof: We give two proofs. Method 1. Because (7) holds for all m ≥ 3, we have

D_{n} = lim_{m→∞}⌊(\frac{⌊e(n + m − 2)!⌋}{(n + m − 2)!} + \frac{n + m}{(n + m − 1)(n + m − 1)!} + e^{−1})n!⌋ − ⌊en!⌋

= ⌊(e + e^{−1})n!⌋ − ⌊en!⌋.

Method 2. By using (6), we have

M(n) = n!(e − ∑_{i=0}^{n} \frac{1}{i!}) = en! − ⌊en!⌋ = \{en!\} (n ≥ 1, \{ \} denotes the fractional part),

and the proof follows.

Now

lim_{m→∞} 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) (n ≥ 1).

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).

Theorem 2.3 Suppose m is an integer and m ≥ 1. The number of derangements of n distinct objects (n ≥ 2) is

D_{n} = ⌊(\frac{\{e(n + 2m)!\}}{(n + 2m)!} + ∑_{i=1}^{m} \frac{n + 2i − 1}{(n + 2i)!} + e^{−1})n!⌋.  (10)

Proof: Since m ≥ 1 we have

\frac{e^{−1}n! − D_{n}}{(−1)^{n+1}} = n! ∑_{i=1}^{∞}(\frac{1}{(n + 2i − 1)!} − \frac{1}{(n + 2i)!}) < n!(∑_{i=1}^{m} \frac{n + 2i − 1}{(n + 2i)!} + ∑_{i=2m+1}^{∞} \frac{1}{(n + i)!}).

Let N_{m}(n) denote the right member of above inequality. Considering (6), we have

N_{m}(n) = n!(∑_{i=1}^{m} \frac{n + 2i − 1}{(n + 2i)!} + \frac{\{e(n + 2m)!\}}{(n + 2m)!}),

and for (n ≥ 2), D_{n} = ⌊e^{−1}n! + N_{m}(n)⌋. This completes the proof.

Corollary 2.4 For all integers m, n ≥ 1, we have

N_{m+1}(n) < N_{m}(n), N_{1}(n) < {en!}.

Therefore we have the following chain of bounds for |\frac{n!}{e} − D_{n}|

|\frac{n!}{e} − D_{n}| < ⋯ < N_{2}(n) < N_{1}(n) < \{en!\} < ⋯ < M_{2}(n) < M_{1}(n) < 1 (n ≥ 2).

Question 1. Can we find the following limit?

lim_{m→∞} 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,

Proof: (Proof of Theorem 1) Suppose k ≥ 1 be an integer, we have

0 < \frac{1}{e} − ∑_{i=0}^{2k−1} \frac{(−1)^{i}}{i!} < \frac{1}{(2k)!}  (11)

so, for every m_{1}, we have

m_{1} < \frac{(2k − 1)!}{e} + m_{1} − ∑_{i=0}^{2k−1} \frac{(−1)^{i}(2k − 1)!}{i!} < m_{1} + \frac{1}{2}

if 0 ≤ m_{1} ≤ \frac{1}{2} , then

∑_{i=0}^{2k−1} \frac{(−1)^{i}(2k − 1)!}{i!} = ⌊\frac{(2k − 1)!}{e} + m_{1}⌋.

Similarly since (11), for every m_{2} we have

m_{2} − 1 < \frac{(2k)!}{e} + m_{2} − ∑_{i=0}^{2k} \frac{(−1)^{i}(2k)!}{i!} < m_{2}.

Now, if m_{2} ≥ \frac{1}{3}, then

0 < \frac{(2k)!}{e} + m_{2} − ∑_{i=0}^{2k} \frac{(−1)^{i}(2k)!}{i!}

therefore, if \frac{1}{3} ≤ m_{2} ≤ 1, we obtain

∑_{i=0}^{2k} \frac{(−1)^{i}(2k)!}{i!} = ⌊\frac{(2k)!}{e} + m_{2}⌋.

This completes the proof. In the next section there are some applications of the proven results.

3 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}hypergeom([1, −n], [ ], 1),

and

D_{n} = e^{−1}Γ(n + 1, −1),

where hypergeom([1, −n], [ ], 1) is MAPLE’s notation for a hypergeometric function. More generally, hypergeom([a_{1} a_{2} ⋯ a_{p}], [b_{1} b_{2} ⋯ b_{q}], x) is defined as follows (see [4]),

pF_{q} [ \begin{matrix}a_{1} & a_{2} & ⋯ & a_{p} \\ b_{1} & b_{2} & ⋯ & b_{q} \end{matrix} ; x] = ∑_{k≥0} t_{k}x^{k}

where

\frac{t_{k+1}}{t_{k}} = \frac{(k + a_{1})(k + a_{2}) ⋯ (k + a_{p})}{(k + b_{1})(k + b_{2}) ⋯ (k + b_{q})(k + 1)}x.

Also Γ(n + 1, −1) is an incomplete gamma function and generally defined as follows: Γ(a, z) = ∫_{z}^{∞} e^{−t}t^{a−1}dt (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 derangement function, a natural generalization of derangements, denoted by D_{n}(x), for every integer n ≥ 0 and every real x as follows:

D_{n}(x) = \{ \begin{matrix}n! ∑_{i=0}^{n} \frac{x^{i}}{i!} , & x ≠ 0; \\ n!, & x = 0. \end{matrix}

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), (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) = ⌊en!⌋ (n ≥ 1), (see [3]).

A natural question is

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} _{2}F_{0} [ \begin{matrix}1 & −n \\ − \end{matrix} ; −\frac{1}{x}] (x ≠ 0),

and

D_{n}(x) = e^{x}Γ(n + 1, x).  (12)

We obtain

2F_{0} [ \begin{matrix}1 & −n \\ − \end{matrix} ; −1] = ⌊en!⌋,

and

2F_{0} [ \begin{matrix}1 & −n \\ − \end{matrix} ; 1] = (−1)^{n} ⌊\frac{n! + 1}{e}⌋ .

Also we have some corollaries.

Corollary 3.1 For every real x ≠ 0 we have

1F_{1} [ \begin{matrix}n + 1 \\ n + 2 \end{matrix} ; −x] = \frac{(n + 1)(n! − e^{−x}D_{n}(x))}{x^{n+1}}.

Proof: Obvious.

Corollary 3.2 For every integer n ≥ 1 we have

∫_{−1}^{∞} e^{−t}t^{n}dt = e ⌊\frac{n! + 1}{e}⌋ ,

∫_{0}^{∞} e^{−t}t^{n}dt = n!,

∫_{1}^{∞} e^{−t}t^{n}dt = \frac{⌊en!⌋}{e},

and

∫_{0}^{1} e^{−t}t^{n}dt = \frac{\{en!\}}{e},

∫_{−1}^{0} e^{−t}t^{n}dt = \{ \begin{matrix}−e\{\frac{n!}{e}\} & n is odd, \\ e − e\{\frac{n!}{e}\} & n is even. \end{matrix}

∫_{−1}^{1} e^{−t}t^{n}dt = e⌊(e + e^{−1})n!⌋ − (e + e^{−1})⌊en!⌋,

Proof: Use relations (3), (6), (9), (12) and the definition of derangement function in the case x = 0.

Question 3. Are there any similar formulas for _{2}F_{0} [ \begin{matrix}1 & −n \\ − \end{matrix} ; −\frac{1}{x}] ? In other words, given

any real number x, is there an interval I (dependent on x) such that

n! ∑_{i=0}^{n} \frac{x^{i}}{i!} = ⌊e^{x}n! + m⌋ (m ∈ I_{x})?

4 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.

References

[1] T.M. Apostol, Mathematical Analysis, Addison-Wesley, 1974.

[2] P.J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.

[3] M. Hassani, Cycles in graphs and derangements, Math. Gazette, to appear.

[4] M. Petkovšek, H.S. Wilf and D. Zeilberger, A = B, A. K. Peters, 1996. Also available

    at http://www.cis.upenn.edu/~wilf/AeqB.html.

2000 Mathematics Subject Classification: 05A10, 33B20, 33C20. Keywords: e, derangements, derangement function, incomplete gamma function, hypergeometric function

(Concerned with sequence \underline{A000166}.)

Received February 17, 2003; revised version received February 24, 2003. Published in Journal of Integer Sequences February 25, 2003.

Return to Journal of Integer Sequences home page.