1 Preliminaries

The nth derangement number or subfactorial ofn, !n, is the number of permutations of n elements, such that no element appears in its original position, i.e., is a permutation that has no fixed points. The first derangement numbers are

$$\begin{aligned} 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570 \end{aligned}$$

and the sequence is labelled in The On-Line Encyclopedia of Integer Sequences [13] as A000166.

Derangement numbers were first combinatorially studied by the French mathematician and Fellow of the Royal Society, Pierre Rémond de Montmort, in his celebrated book Essay d’analyse sur les jeux de hazard, published in 1708. The two best known recurrence relations are

$$\begin{aligned} !n=(n-1)(!(n-1)+!(n-2))\, , \quad \text{ for } n\geqslant 2, \end{aligned}$$

and

$$\begin{aligned} !n=n\left( !(n-1)\right) +(-1)^{n}\, , \quad \text{ for } n\geqslant 1, \end{aligned}$$
(1.1)

with \(!0=1\) and \(!1=0\), were established and proved by Euler in Calcul de la probabilité dans le jeu de rencontre, in 1753. They can be written in the explicit forms

$$\begin{aligned} !n=n!\sum _{k=0}^{n}{\frac{(-1)^{k}}{k!}}=\sum _{k=0}^{n}(-1)^{n-k} {n \atopwithdelims ()k} k! \end{aligned}$$

which coincides with permanent of the all ones matrix minus the identity matrix, all of order n [10] (for more details on this matter, the reader is referred to [14, Chapter 2]).

Other natural representations of the derangement numbers are those in terms of the determinant of certain tridiagonal matrices as we can find in [7, 8].

Recently, Qi, Zhao, and Guo in [12] claimed the discovery of two new identities for the derangement numbers, namely

$$\begin{aligned} !n=\sum _{k=0}^{n-2} {n \atopwithdelims ()k}(n-k-1)(!k)\, , \quad \text{ for } n\geqslant 2, \end{aligned}$$
(1.2)

and

$$\begin{aligned} n!=\sum _{k=0}^{n} {n \atopwithdelims ()k}(!k)\, , \quad \text{ for } n\geqslant 0. \end{aligned}$$
(1.3)

The proofs are based on the construction of the Hessenberg matrix

$$\begin{aligned} H_n=\left( \begin{array}{l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l} 0 &{} -1 &{} &{} &{} &{} &{}\\ {2 \atopwithdelims ()0} &{} 0 &{} -1 &{} &{} &{} &{}\\ {3 \atopwithdelims ()0} 2 &{} {3 \atopwithdelims ()1} &{} \ddots &{} \ddots &{} &{} &{}\\ \vdots &{} \vdots &{} \ddots &{} \ddots &{} \ddots &{} &{}\\ {n-2 \atopwithdelims ()0} (n-3) &{} {n-2 \atopwithdelims ()1} (n-4) &{} \ldots &{} \ddots &{} \ddots &{} -1 &{} \\ {n-1 \atopwithdelims ()0} (n-2) &{} {n-1 \atopwithdelims ()1} (n-3) &{} \ldots &{} \ldots &{} {n-1 \atopwithdelims ()n-3} &{} 0 &{} -1 \\ {n \atopwithdelims ()0} (n-1) &{} {n \atopwithdelims ()1} (n-2) &{} \ldots &{} \ldots &{} {n \atopwithdelims ()n-3} 2 &{} {n \atopwithdelims ()n-2} &{} 0 \end{array} \right) , \end{aligned}$$
(1.4)

an exponential generating function, a higher derivatives formula, and the calculation of a specific limit, which leads to

$$\begin{aligned} !n= \det H_n. \end{aligned}$$
(1.5)

Our aim here is to provide a very short proof for (1.2) using a standard result in finite differences theory. En passant, we show (1.5) based on another result involving Hessenberg matrices and recurrence relations.

Notice that (1.3) is well-known in the literature. See, for example, [6] for a simple combinatorial interpretation.

We should also point out that the terminology “Hessenberg determinant”, as well as “tridiagonal determinant”, used in many instances by the authors in [12] and elsewhere, is inaccurate as we mentioned in [1].

For relations involving Hessenberg matrices, the reader is referred, for example, to [2,3,4,5, 11, 17].

2 Proof

From the theory of finite differences we know that, for any polynomial p(x) of degree less than n,

$$\begin{aligned} \sum _{k=0}^{n}(-1)^{k}{\left( {\begin{array}{c}n\\ k\end{array}}\right) }p(k)=0\, . \end{aligned}$$
(2.1)

See, for instances, [9, p.64] or [17]. In particular, for \(n\geqslant 2\), we have

$$\begin{aligned} \sum _{k=0}^{n}(-1)^{k} {n \atopwithdelims ()k}(n-k-1)=0 \end{aligned}$$

which implies

$$\begin{aligned} \sum _{k=0}^{n-2}(-1)^{k} {n \atopwithdelims ()k}(n-k-1)=(-1)^n. \end{aligned}$$
(2.2)

Now, from (1.1), (2.2), and an elementary inductive argument, we have

$$\begin{aligned} \sum _{k=0}^{n-2} {n \atopwithdelims ()k}(n-k-1)(!k)= & {} \sum _{k=1}^{n-2} {n \atopwithdelims ()k}k(n-k-1)(!(k-1))\\&+\sum _{k=0}^{n-2}(-1)^{k} {n \atopwithdelims ()k}(n-k-1) \\= & {} n \sum _{k=0}^{n-3} {n-1 \atopwithdelims ()k}(n-k-2)(!k) +(-1)^n \\= & {} n\left( !(n-1)\right) +(-1)^{n} \\= & {} !n\, . \end{aligned}$$

Regarding the Hessenberg matrix (1.4), we know (cf., e.g., [15, Theorem 4.20] or [7, Proposition 6]), if \(a_1,a_2,\ldots \) is a sequence such that

$$\begin{aligned} a_{n+1}=p_{n,1}a_1+\cdots +p_{n,n}a_n\, , \end{aligned}$$

then

$$\begin{aligned} a_{n+1}= a_1 \det \left( \begin{array}{l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l} p_{1,1} &{} -1 &{} &{} &{} &{} \\ p_{2,1} &{} p_{2,2} &{} -1 &{} &{} &{}\\ p_{3,1} &{} p_{3,2} &{} \ddots &{} \ddots &{} &{}\\ \vdots &{} \vdots &{} \ddots &{} \ddots &{} \ddots &{}\\ p_{n-1,1} &{} p_{n-1,2} &{} \ldots &{} p_{n-1,n-2} &{} p_{n-1,n-1} &{} -1 \\ p_{n,1} &{} p_{n,2} &{} \ldots &{} p_{n,n-2} &{} p_{n,n-1} &{} p_{n,n} \end{array} \right) . \end{aligned}$$

Setting

$$\begin{aligned} a_k=!(k-1)\quad \text{ and } \quad p_{n,k}= {n \atopwithdelims ()k-1}(n-k), \end{aligned}$$

we get the desired result.