![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
In the paper, the authors recover, correct, and extend two representations for derangement numbers in terms of a tridiagonal determinant.
Public Interest Statement
A derangement is a permutation of elements of a set, such that no element appears in its original position. The number of derangements of a set is called the derangement number. The problem of counting derangements was first considered in 1708 and solved in 1713. Derangement numbers arise naturally in many different contexts. The number of derangements in various families of transitive permutation groups has been studied extensively in recent years. In the paper, by virtue of an old formula for computing derivatives of a ratio between two differentiable functions in terms of the Hessenberg determinants, the authors recover, correct, and extend two representations for derangement numbers in terms of a tridiagonal determinant.
1. Introduction
In combinatorics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. The number of derangements of a set of size n is called the derangement number and sometimes denoted by !n. The problem of counting derangements was first considered in 1708 and solved in 1713 by Pierre Raymond de Montmort, as did Nicholas Bernoulli at about the same time. Derangement numbers !n arise naturally in many different contexts. More generally, the number of derangements in various families of transitive permutation groups has been studied extensively in recent years. For more information on !n, please refer to Aigner (Citation2007), Andreescu and Feng (Citation2004), Wilf (Citation1994,Citation2006) and plenty of references therein.
The first ten derangement numbers !n for are
(1)
(1)
In Kittappa (Citation1993, p. 216, Example 2), it was given that(2)
(2)
In Janjić (Citation2012, p. 8, ) and Janjić (Citation2011, p. 5,
), it was deduced that
(3)
(3)
By the determinantal expression (3), we figure out that ,
,
, and
. It is clear that the latter two values 6 and 24 do not coincide with the numbers 9 and 44 in (1). Therefore, the expression (3) appeared in Janjić (Citation2011,Citation2012) is slightly wrong.
It is known in Comtet (Citation1974, p. 182, Theorem B) that derangement numbers !n have an exponential generating function(4)
(4)
The aim of this paper is, by computing the nth derivative of the exponential generating function D(x), to recover, correct, and extend the above determinantal representations (2) and (3) for derangement numbers !n.
Theorem 1
For , derangement numbers !n can be represented by a tridiagonal
determinant
(5)
(5)
where
2. Lemma
In order to recover Theorem 1, we need the following lemma which was reformulated in Qi (TanspsDerspsAppspsThankstex, Section 2.2, p. 849), Qi and Chapman (2ClosedspsBernspsPolyn2tex, p. 94), and Wei and Qi (EulerspsNosps3Sumtex, Lemma 2.1) from Bourbaki (Citation2004, p. 40, Exercise 5).
Lemma 1
Let u(x) and be differentiable functions, let
be an
matrix whose elements
for
, let
be an
matrix whose elements
for and
, and let
denote the determinant of the
matrix
Then the nth derivative of the ratio can be computed by
(6)
(6)
3. Proof of Theorem 1
Now we are in a position to prove Theorem 1.
Applying and
in Lemma 1 gives
as for
and
as for
and
. Consequently, employing (6) reveals
as . From (4), it follows that
This implies that(7)
(7)
Subtracting the nth row from the th row, then the
th row from the nth row, ..., then the 1st row from the 2nd row of the above determinant leads to
which can be readily rearranged as the formula (5). The proof of Theorem 1 is complete.
Remark 1
On 10 May 2016, Dr Wiwat Wanicharpichat at Naresuan University in Thailand told the first author that the matrix
is known as the “population projection matrix”. See (Kirkland & Neumann, Citation2013, p. 48, Equation (4.1)).
Remark 2
In the paper (Qi, GJMA6574tex), an alternative proof of Theorem 1 was given.
4. Cover image
Source: Author.
Acknowledgements
The authors thank Dr Sophie Moufawad at IFP Energies nouvelles in France, Dr Yuri S. Semenov at Moscow State University of Railway Engineering in Russia, Dr Wiwat Wanicharpichat at Naresuan University in Thailand, and several other mathematicians for their observations and discussion on the determinant in (7) at the ResearchGate website http://www.researchgate.net/post/What_is_the_name_of_the_matrix_or_determinant_showed_by_the_picture. The authors appreciate several anonymous mathematicians for their valuable comments on the original version of this paper, especially for their recommending the papers (Janjić, Citation2012,Citation2011, Kittappa, Citation1993) and related results in them. The authors appreciate the anonymous referees for their careful corrections to and valuable comments on the original version of this paper. See https://qifeng618.wordpress.com.
Additional information
Funding
Notes on contributors
Feng Qi
Feng Qi received his PhD degree of Science in Mathematics from University of Science and Technology of China. He is being a full professor in mathematics at Henan Polytechnic University (HPU) and Tianjin Polytechnic University. He is the founder of School of Mathematics and Informatics at HPU. He was visiting professors at Victoria University in Australia and University of Hong Kong in China. He was part-time professors at Henan University, Henan Normal University, and Inner Mongolia University for Nationalities. He visited Copenhagen University and seven universities in South Korea. He attended an academic conference held in April 2016 at Antalya by Ağrı İbrahim Çeçen University in Turkey. He is or was editors of over 20 international journals. Since 1993, he published over 600 articles. His current research interests include the analytic combinatorics, computational number theory, special functions, integral transforms, and complex functions.
References
- Aigner, M. (2007). A course in enumeration, Graduate texts in mathematics (Vol. 238). Berlin: Springer.
- Andreescu, T., & Feng, Z. (2004). A path to combinatorics for undergraduates---counting strategies. Boston-Basel-Berlin: Birkhäuser.
- Bourbaki, N. (2004). Elements of Mathematics: Functions of a Real Variable: Elementary Theory. In P. SpainElements of Mathematics. Berlin: Springer-Verlag. doi:10.1007/978-3-642-59315-4
- Comtet, L. (1974). Advanced Combinatorics: The Art of Finite and Infinite Expansions (Revised and Enlarged ed.). Dordrecht and Boston: D. Reidel Publishing.
- Janji{\’c}, M. (2011). Recurrence relations and determinants. (arXiv preprint). Retrieved from http://arxiv.org/abs/1112.2466
- Janji{\’c}, M. (2012). Determinants and recurrence sequences. Journal of Integer Sequences, 15, 21 p. (Article 12.3.5).
- Kirkland, S. J., & Neumann, M. (2013). Group inverses of M-matrices and their applications. Boca Raton, FL: CRC Press Taylor & Francis Group.
- Kittappa, R. K. (1993). A representation of the solution of the nth order linear difference equation with variable coefficients. Linear Algebra and its Applications, 193, 211–222. doi:10.1016/0024-3795(93)90278-V
- Qi, F. (2015). Derivatives of tangent function and tangent numbers. Applied Mathematics and Computation, 268, 844–858. doi:10.1016/j.amc.2015.06.123
- Qi, F. (2016). A determinantal representation for derangement numbers. Global Journal of Mathematical Analysis, 4, 17. doi:10.14419/gjma.v4i3.6574
- Qi, F., & Chapman, R. J. (2016). Two closed forms for the Bernoulli polynomials. Journal of Number Theory, 159, 89–100. doi:10.1016/j.jnt.2015.07.021
- Wei, C.-F., & Qi, F. (2015). Several closed expressions for the Euler numbers. Journal of Inequalities and Applications, 219, 8. doi:10.1186/s13660-015-0738-9
- Wilf, H. S. (1994). Generatingfunctionology (2nd ed.). Boston, MA: Academic Press.
- Wilf, H. S. (2006). Generatingfunctionology (3rd ed.). Wellesley, MA: A K Peters.