Derangements and Alternating Sum of Permutations by Integration

Mehdi Hassani Department of Mathematics University of Zanjan University Blvd. 45371-38791 Zanjan Iran

                    mehdi.hassani@znu.ac.ir

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 (−1)^{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.

1 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 [4, Section 0.15], [11, Section 2.3.4], and [12, pp. 343–355] 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 [2] and Kayll [9]. Our simple proof differs from their and is included for completeness.

Theorem 1. Let a ≥ 1 be a fixed real. For any positive integer n let

L_{n}(a) = ∫_{1}^{a} log^{n} t dt.  (1)

Then, for any integer n ≥ 1 and for x ≥ 0,

∑_{j=0}^{n} (−1)^{j} P (n, j)x^{n−j} = \frac{(−1)^{n} n! + L_{n}(e^{x})}{e^{x}}.  (2)

More precisely, by letting x = 1 in (2) we obtain

∑_{j=0}^{n} (−1)^{j} P (n, j) = \frac{(−1)^{n} n! + L_{n}(e)}{e}.  (3)

As an application of Theorem 1, we continue our study [6] 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 (3) and D_{n} are related as follows:

D_{n} = n! ∑_{j=0}^{n} \frac{(−1)^{j}}{j!} = (−1)^{n} n! ∑_{j=0}^{n} \frac{(−1)^{n−j}}{(n − j)!} = (−1)^{n} ∑_{j=0}^{n}(−1)^{j}P (n, j).

Thus, by considering the relation (3), we obtain

D_{n} = \frac{n!}{e} + (−1)^{n} \frac{L_{n}(e)}{e},  (4)

for each integer n ≥ 1. The relation (4) 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:

Theorem 2. We have

∑_{n=1}^{∞} (D_{n} − \frac{n!}{e}) = −1 + \frac{1}{e} + \frac{Ei(2) − Ei(1)}{e^{2}} ≊ −0.218114,  (5)

where Ei denotes the exponential integral function defined by the Cauchy principal value of the integral

Ei(x) = − ∫_{−x}^{∞} \frac{e^{−z}}{z} dz,

and

∑_{n=1}^{∞} (D_{n} − \frac{n!}{e})^{2} = −\frac{(e − 1)^{2}}{e^{2}} + \frac{4}{e^{2}} ∫0^{\frac{1}{2}} h(z) dz ≊ 0.433113,  (6)

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 ≥ 1 the following multiple integral representation holds:

∑_{n=1}^{∞} (D_{n} − \frac{n!}{e})^{k} = −\frac{(e − 1)^{k}}{e^{k}} + \frac{1}{e^{k}} ∫_{0}^{1} ⋯ ∫_{0}^{1} \frac{e^{x_{1}+···+x_{k}}}{1 − (−1)^{k} x_{1} ⋯ x_{k}} dX,  (7)

where X represents the k-tuple (x_{1}, …, x_{k}).

Ismail and Simeonov [8] 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 1, 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}.

Theorem 3. Given any positive integer r, for any integer n ≥ 1 we have the asymptotic expansions

\frac{L_{n}(e)}{e} = ∑_{k=1}^{r} (−1)^{k−1} \frac{B_{k}}{n^{k}} + O (\frac{1}{n^{r+1}} ) ,  (8)

and

D_{n} = \frac{n!}{e} + ∑_{k=1}^{r} (−1)^{n+k−1} \frac{B_{k}}{n^{k}} + O (\frac{1}{n^{r+1}} ) ,  (9)

where B_{k} denotes the k-th Bell number and the constant of O-term does not exceed B_{r+1} in both expansions.

2 Two remarks

Remark 4. The relation (3) is an analogue to the identity ∑_{j=0}^{n}(−1)^{j}C(n, j) = 0. For an analogue to the identity ∑_{j=0}^{n} C(n, j) = 2^{n}, we observe that

0 < e − ∑_{j=0}^{n} \frac{1}{j!} = ∑_{j=1}^{∞} \frac{1}{(n + j)!} = \frac{1}{n!} ∑_{j=1}^{∞} ∏_{k=1}^{j} \frac{1}{n + k} < \frac{1}{n!} ∑_{j=1}^{∞} \frac{1}{(n + 1)^{j}} = \frac{1}{n · n!}.

Thus, for each n ≥ 1 we obtain

∑_{j=0}^{n} P (n, j) = n! ∑_{j=0}^{n} \frac{1}{j!} = ⌊e n!⌋.  (10)

The author previously introduced some enumerative applications of the relation (10) concerning the number of paths and cycles in complete graphs [5, 7].

Remark 5. The relation (3) enables us to provide a simple proof of the irrationality of the number e. We observe that 0 ≤ log t ≤ 1 for 1 ≤ t ≤ e. Thus,

0 < L_{n}(e) ≤ ∫_{1}^{e} dt = 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{α}{β} for some positive integers α and β. The relation (3) with n = α gives

∑_{j=0}^{α}(−1)^{j}P (n, j) = (−1)^{α}(α − 1)!β + \frac{L_{α}(e)}{e},

implying that \frac{L_{α}(e)}{e} is an integer, a contradiction.

3 Proof of Theorem 1

Proof. Using integration by parts we obtain

∫ log^{r} t dt = t log^{r} t − r ∫ log^{r−1} t dt.

Thus, the recurrence L_{j}(a) = a log^{j} a − jL_{j−1}(a) holds for any integer j ≥ 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 ≤ j ≤ n yields

\frac{(−1)^{n}}{n!} L_{n}(a) − L_{0}(a) = ∑_{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 + ∑_{j=0}^{n} \frac{(−1)^{j}}{j!} a log^{j} a = −1 + ∑_{j=0}^{n} \frac{(−1)^{−j}}{j!} a log^{j} a,

and

L_{n}(a) = (−1)^{n+1}n! + a ∑_{j=0}^{n} (−1)^{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 ∑_{j=0}^{n} (−1)^{j} P (n, j) log^{n−j} a.

Letting a = e^{x} for x ≥ 0 we get (2), which concludes the proof.

4 Proof of Theorem 2

Proof. We conclude from (4) that

∑_{n=1}^{∞} (D_{n} − \frac{n!}{e}) = ∑_{n=1}^{∞} (−1)^{n} \frac{L_{n}(e)}{e} = \frac{1}{e} lim_{N→∞} ∑_{n=1}^{N} (−1)^{n} L_{n}(e)

= \frac{1}{e} lim_{N→∞} ∑_{n=1}^{N} (−1)^{n} ∫_{1}^{e} log^{n} t dt = \frac{1}{e} lim_{N→∞} ∫_{1}^{e} ∑_{n=1}^{N} (− log t)^{n} dt

= \frac{1}{e} lim_{N→∞} ∫_{1}^{e} −\frac{log t}{1 + log t} (1 + (− log t)^{N+1}) dt.

Now we use the bounded convergence theorem [3, Theorem 3.26] to interchange the limit and integral in the last relation. Consequently,

∑_{n=1}^{∞} (D_{n} − \frac{n!}{e}) = −\frac{1}{e} ∫_{1}^{e} lim_{N→∞} \frac{log t}{1 + log t} (1 + (− log t)^{N+1}) dt

= −\frac{1}{e} ∫_{1}^{e} \frac{log t}{1 + log t} (1 + lim_{N→∞} (− log t)^{N+1}) dt

= −\frac{1}{e} ∫_{1}^{e} \frac{log t}{1 + log t} dt = −\frac{1}{e} ∫_{1}^{e} \frac{log t}{1 + log t} dt.

To evaluate the last integral we apply the change of variable −z = 1 + log t, satisfying t = e^{−1−z} and dt = −t dz = −\frac{1}{e} e^{−z}dz. Therefore

∫_{1}^{e} \frac{log t}{1 + log t} dt = \frac{1}{e} ∫_{−2}^{−1} (1 + \frac{1}{z}) e^{−z} dz

= \frac{1}{e} ∫_{−2}^{−1} e^{−z} dz − \frac{1}{e} (− ∫_{−2}^{−1} \frac{e^{−z}}{z} ) dz = \frac{e^{2} − e}{e} − \frac{Ei(2) − Ei(1)}{e}.

This gives (5). To prove (6) we follow an argument due to LeVeque [10], which has been described by Aigner and Ziegler [1, Chapter 9]. In (1) we apply the change of variable z = log t, satisfying t = e^{z} and dt = e^{z}dz. Accordingly,

L_{n}(e) = ∫_{0}^{1} z^{n}e^{z} dz.  (11)

Repeated use of (11) shows that

L_{n}(e)^{2} = (∫_{0}^{1} x^{n}e^{x} dx) (∫_{0}^{1} y^{n}e^{y} dy) = ∫_{0}^{1} ∫_{0}^{1} (xy)^{n} e^{x+y} dA_{x,y}.

Hence, we conclude from (4) that

∑_{n=1}^{∞} (D_{n} − \frac{n!}{e})^{2} = −\frac{L_{0}(e)^{2}}{e^{2}} + \frac{1}{e^{2}} ∑_{n=0}^{∞} L_{n}(e)^{2}

= −\frac{(e − 1)^{2}}{e^{2}} + \frac{1}{e^{2}} ∑_{n=0}^{∞} ∫_{0}^{1} ∫_{0}^{1} (xy)^{n} e^{x+y} dA_{x,y}.

Since the function e^{x+y} is bounded on the region [0, 1] × [0, 1], uniform convergence of the geometric series allows us to change the order of sum and integrals. Accordingly,

∑_{n=1}^{∞} (D_{n} − \frac{n!}{e})^{2} = −\frac{(e − 1)^{2}}{e^{2}} + \frac{1}{e^{2}} I,

where

I = ∫_{0}^{1} ∫_{0}^{1} \frac{e^{x+y}}{1 − xy} dA_{x,y}.

The same reasoning applies to the case of other moments. Thus, meanwhile we obtain (7). 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^{∘} 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, dA_{x,y} = 2dA_{u,v}. Therefore,

I = 4 ∫0^{\frac{1}{2}} ∫_{0}^{u} \frac{e^{2u}}{1 − u^{2} + v^{2}} dv du + 4 ∫ 1_{\frac{1}{2}} ∫_{0}^{1−u} \frac{e^{2u}}{1 − u^{2} + v^{2}} dv du

= 4 ∫0^{\frac{1}{2}} \frac{e^{2u}}{\sqrt{1 − u^{2}}} arctan \frac{u}{\sqrt{1 − u^{2}}} du + 4 ∫ 1_{\frac{1}{2}} \frac{e^{2u}}{\sqrt{1 − u^{2}}} arctan \frac{1 − u}{\sqrt{1 − u^{2}}} du.

Substituting u = 1 − z in the last integral and simplifying yields (6). This is the desired conclusion.

5 Proof of Theorem 3

Proof. We conclude from the integral representation (11) that

L_{n}(e) = ∫_{0}^{1} z^{n}e^{z} dz = ∫_{0}^{1} z^{n} ∑_{j=0}^{∞} \frac{z^{j}}{j!} dz = ∫_{0}^{1} ∑_{j=0}^{∞} \frac{z^{n+j}}{j!} dz.

Since the last sum converges uniformly for 0 ≤ z ≤ 1, we may change the order of sum and integral. Therefore,

L_{n}(e) = ∑_{j=0}^{∞} ∫_{0}^{1} \frac{z^{n+j}}{j!} dz = ∑_{j=0}^{∞} \frac{1}{j!(n + j + 1)}.

An easy computation shows that

\frac{1}{n + b} = ∑_{k=1}^{r} (−1)^{k−1} \frac{b^{k−1}}{n^{k}} + \frac{(−1)^{r}}{n + b} (\frac{b}{n})^{r} ,

for n + b ≠ 0. If we take b = j + 1, then

L_{n}(e) = ∑_{j=0}^{∞} ∑_{k=1}^{r} \frac{(−1)^{k−1}}{n^{k}} \frac{(j + 1)^{k−1}}{j!} + (−1)^{r} ∑_{j=0}^{∞} \frac{1}{j!(n + j + 1)} (\frac{j + 1}{n})^{r}

= ∑_{k=1}^{r} \frac{(−1)^{k−1}}{n^{k}} ∑_{j=0}^{∞} \frac{(j + 1)^{k−1}}{j!} + \frac{(−1)^{r}}{n^{r}} ∑_{j=0}^{∞} \frac{(j + 1)^{r}}{j!(n + j + 1)}.

Dobiński’s formula [13, p. 178] states that the k-th Bell number B_{k} equals

B_{k} = \frac{1}{e} ∑_{j=0}^{∞} \frac{j^{k}}{j!} .

On account of this formula, we have

∑_{j=0}^{∞} \frac{(j + 1)^{k−1}}{j!} = ∑_{j=0}^{∞} \frac{(j + 1)^{k}}{(j + 1)!} = ∑_{j=1}^{∞} \frac{j^{k}}{j!} = ∑_{j=0}^{∞} \frac{j^{k}}{j!} = e B_{k},

and

∑_{j=0}^{∞} \frac{(j + 1)^{r}}{j!(n + j + 1)} ≤ \frac{1}{n} ∑_{j=0}^{∞} \frac{(j + 1)^{r}}{j!} = \frac{1}{n} ∑_{j=0}^{∞} \frac{(j + 1)^{r+1}}{(j + 1)!} = \frac{e B_{r+1}}{n} .

Therefore, we obtain (8). This gives (9) when substituted in (4), and this is precisely the assertion of the theorem.

6 Acknowledgments

The author is greatly indebted to the referee for a thorough reading of the manuscript and helpful comments.

References

[1] M. Aigner and G. M. Ziegler, Proofs from The Book, 6th edition, Springer, 2018.

[2] R. A. Askey and M. E. H. Ismail, Permutation problems and special functions, Canadian J. Math. 28 (1976), 853–874.

[3] S. Axler, Measure, Integration & Real Analysis, Graduate Texts in Mathematics 282, Springer, 2020.

[4] I. S. Gradshteyn and I. M. Ryzhik, Table of Integrals, Series, and Products, 7th Edition, Academic Press, 2007.

[5] M. Hassani, Cycles in graphs and derangements, Math. Gaz. 88 (2004), 123–126.

[6] M. Hassani, Derangements and applications, J. Integer Sequences 6 (2003), Article 03.1.2.

[7] M. Hassani, Enumeration by e, in T. M. Rassias and N. J. Daras, eds., Modern Discrete Mathematics and Analysis: With Applications in Cryptography, Information Systems and Modelling, Springer, 2018, pp. 227–233.

[8] M. E. H. Ismail and P. Simeonov, Asymptotics of generalized derangements, Adv. Comput. Math. 39 (2013), 101–129.

[9] P. M. Kayll, Integrals don’t have anything to do with discrete math, do they? Math. Mag. 84 (2011), 108–119.

[10] W. J. LeVeque, Topics in Number Theory, Vol. 1, Addison-Wesley, 1956.

[11] K. H. Rosen, J. G. Michaels, J. L. Gross, J. W. Grossman, and D. R. Shier, Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.

[12] M. Z. Spivey, The Art of Proving Binomial Identities, CRC Press, 2019.

[13] E. W. Weisstein, CRC Concise Encyclopedia of Mathematics, 2nd edition, CRC Press, 2003.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A16, 11B73, 26A06. Keywords: derangement, permutation, Bell number, integration by parts.

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

Received March 23 2020; revised version received July 28 2020. Published in Journal of Integer Sequences, July 29 2020.

Return to Journal of Integer Sequences home page.