Abstract
We provide a very short proof of a Qi-Zhao-Guo closed form for derangements numbers based on the determinants of certain Hessenberg matrices. The proof is grounded on a basic result on finite sequences and an inductive argument.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
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
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
and
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
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
and
The proofs are based on the construction of the Hessenberg matrix
an exponential generating function, a higher derivatives formula, and the calculation of a specific limit, which leads to
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,
See, for instances, [9, p.64] or [17]. In particular, for \(n\geqslant 2\), we have
which implies
Now, from (1.1), (2.2), and an elementary inductive argument, we have
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
then
Setting
we get the desired result.
References
Anđelić, M., da Fonseca, C.M.: A short proof for a determinantal formula for generalized Fibonacci numbers. Matematiche (Catania) 74, 363–367 (2019)
Barrios Rolania, D.: On the Darboux transform and the solutions of some integrable systems. RACSAM 113, 1359–1378 (2019)
Barrios Rolania, D., Garcia-Ardila, J.C.: Geronimus transformations for sequences of \(d\)-orthogonal polynomials. RACSAM 114 (2020), #26
Costabile, F.A., Gualtieri, M.I., Napoli, A.: Polynomial sequences: elementary basic methods and application hints. A survey. RACSAM 113, 3829–3862 (2019)
da Fonseca, C.M.: An identity between the determinant and the permanent of Hessenberg type-matrices. Czechoslovak Math. J. 61, 917–921 (2011)
He, Y., Pan, J.: Some recursion formulae for the number of derangement and Bell numbers. J. Math. Res. Appl. 36, 15–22 (2016)
Janjić, M.: Determinants and recurrence sequences. J. Integer Seq. 15 (2012), Article 12.3.5 (2012)
Kittappa, R.K.: A representation of the solution of the \(n\)th order linear difference equation with variable coefficients. Linear Algebra Appl. 193, 211–222 (1993)
Knuth, D.E.: The Art of Computer Programming, vol. 1, Fundamental Algorithms, Third Edition, Addison-Wesley, Boston, NJ, (1997)
Liu, C.L.: Introduction to Combinatorial Mathematics. McGraw-Hill, New York (1968)
Merca, M.: A note on the determinant of a Toeplitz-Hessenberg matrix. Spec. Matrices 1, 10–16 (2013)
Qi, F., Wang, J.L., Guo, B.N.: Closed forms for derangement numbers in terms of the Hessenberg determinants. RACSAM 112, 933–944 (2018)
Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences, https://oeis.org/
Stanley, R.P.: Enumerative Combinatorics, Vol.1, 2nd Edition, Cambridge Studies in Advanced Mathematics (Book 49), Cambridge University Press, (2011)
Vein, R., Dale, P.: Determinants and Their Applications in Mathematical Physics, Applied Mathematical Sciences 134, Springer-Verlag, New York (1999)
Verde-Star, L.: Polynomial sequences generated by infinite Hessenberg matrices. Spec. Matrices 5, 64–72 (2017)
Verde-Star, L.: Divided differences and combinatorial identities. Stud. Appl. Math. 85, 215–242 (1991)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Fonseca, C.M.d. On a closed form for derangement numbers: an elementary proof. RACSAM 114, 146 (2020). https://doi.org/10.1007/s13398-020-00879-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s13398-020-00879-3