A recovery of two determinantal representations for derangement numbers

Abstract

In the paper, the authors recover, correct, and extend two representations for derangement numbers in terms of a tridiagonal determinant.

Keywords:

• derangement number
• determinantal representation
• tridiagonal determinant
• generating function

AMS Subject Classifications:

• 05A05
• 05A15
• 11B83
• 11C20
• 15A15

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 (2007), Andreescu and Feng (2004), Wilf (1994,2006) and plenty of references therein.

The first ten derangement numbers !n for $0\le n\le 9$ are(1) $$\begin{array}{c}\hfill 0,1,2,9,44,265,1854,14833,133496.\end{array}$$(1)

In Kittappa (1993, p. 216, Example 2), it was given that(2) $$\begin{array}{c}\hfill !(n+2)={\left|\begin{array}{ccccccc}2& -1& 0& \cdots & 0& 0& 0\\ 3& 3& -1& \cdots & 0& 0& 0\\ 0& 4& 4& \cdots & 0& 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 0& 0& 0& \cdots & n-1& -1& 0\\ 0& 0& 0& \cdots & n& n& -1\\ 0& 0& 0& \cdots & 0& n+1& n+1\end{array}\right|}_{n\times n},n\in \mathbb{N}.\end{array}$$(2)

In Janjić (2012, p. 8, $5^{\circ }$) and Janjić (2011, p. 5, $5^{\circ }$), it was deduced that(3) $$\begin{array}{c}\hfill !(r+1)=\left|\begin{array}{ccccccc}1& 1& 0& 0& \cdots & 0& 0\\ -1& 1& 2& 0& \cdots & 0& 0\\ 0& -1& 2& 3& \cdots & 0& 0\\ 0& 0& -1& 3& \cdots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& 0& \cdots & r-1& r\\ 0& 0& 0& 0& \cdots & -1& r\end{array}\right|,r\in \mathbb{N}.\end{array}$$(3)

By the determinantal expression (3), we figure out that $!2=1$, $!3=2$, $!4=6$, and $!5=24$. 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ć (2011,2012) is slightly wrong.

It is known in Comtet (1974, p. 182, Theorem B) that derangement numbers !n have an exponential generating function(4) $$\begin{array}{c}\hfill D(x)=\frac{e^{-x}}{1-x}=\sum _{n=0}^{\infty }!n\frac{x^n}{n!}.\end{array}$$(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 $n\in \{0\}\cup \mathbb{N}$, derangement numbers !n can be represented by a tridiagonal $(n+1)\times (n+1)$ determinant(5) $$\begin{array}{ccc}\hfill !n& =-\left|\begin{array}{ccccccccc}-1& 1& 0& 0& 0& \cdots & 0& 0& 0\\ 0& 0& 1& 0& 0& \cdots & 0& 0& 0\\ 0& -1& 1& 1& 0& \cdots & 0& 0& 0\\ 0& 0& -2& 2& 1& \cdots & 0& 0& 0\\ 0& 0& 0& -3& 3& \cdots & 0& 0& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 0& 0& 0& 0& 0& \cdots & n-3& 1& 0\\ 0& 0& 0& 0& 0& \cdots & -(n-2)& n-2& 1\\ 0& 0& 0& 0& 0& \cdots & 0& -(n-1)& n-1\end{array}\right|\hfill & \hfill =-|e_{ij}{|}_{(n+1)\times (n+1)},\\ \hfill \end{array}$$(5)

where$$\begin{array}{c}\hfill e_{ij}=\left\{\begin{array}{cc}1,\hfill & i-j=-1;\hfill \\ i-2,\hfill & i-j=0;\hfill \\ 2-i,\hfill & i-j=1;\hfill \\ 0,\hfill & i-j\ne 0,\pm 1.\hfill \end{array}\right.\end{array}$$

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 (2004, p. 40, Exercise 5).

Lemma 1

Let u(x) and $v(x)\ne 0$ be differentiable functions, let $U_{(n+1)\times 1}(x)$ be an $(n+1)\times 1$ matrix whose elements $u_{k,1}(x)=u^{(k-1)}(x)$ for $1\le k\le n+1$, let $V_{(n+1)\times n}(x)$ be an $(n+1)\times n$ matrix whose elements$$\begin{array}{c}\hfill v_{i,j}(x)=\left\{\begin{array}{cc}\left(\begin{array}{c}i-1\hfill \\ j-1\hfill \end{array}\right)v^{(i-j)}(x),\hfill & i-j\ge 0\hfill \\ 0,\hfill & i-j<0\hfill \end{array}\right.\end{array}$$

for $1\le i\le n+1$ and $1\le j\le n$, and let $\left|W_{(n+1)\times (n+1)}(x)\right|$ denote the determinant of the $(n+1)\times (n+1)$ matrix$$\begin{array}{c}\hfill W_{(n+1)\times (n+1)}(x)=\left[\begin{array}{cc}{U}_{(n+1)\times 1}(x)\hfill & V_{(n+1)\times n}(x)\hfill \end{array}\right].\end{array}$$

Then the nth derivative of the ratio $\frac{u(x)}{v(x)}$ can be computed by(6) $$\begin{array}{c}\hfill \frac{{\text{d}}^n}{\text{d}{x}^n}\left[\frac{u(x)}{v(x)}\right]={(-1)}^n\frac{\left|W_{(n+1)\times (n+1)}(x)\right|}{v^{n+1}(x)}.\end{array}$$(6)

3. Proof of Theorem 1

Now we are in a position to prove Theorem 1.

Applying $u(x)=e^x$ and $v(x)=1+x$ in Lemma 1 gives$$\begin{array}{c}\hfill u_{k,1}={(e^x)}^{(k-1)}=e^x\to 1\end{array}$$

as $x\to 0$ for $1\le k\le n+1$ and$$\begin{array}{cc}\hfill v_{i,j}& =\left(\begin{array}{c}i-1\hfill \\ j-1\hfill \end{array}\right){(1+x)}^{(i-j)}=\left\{\begin{array}{cc}\left(\begin{array}{c}i-1\hfill \\ j-1\hfill \end{array}\right)(1+x),& i-j=0\\ \left(\begin{array}{c}i-1\hfill \\ j-1\hfill \end{array}\right),& i-j=1\\ 0,& i-j\ne 0,1\end{array}\right.\hfill \\ & =\left\{\begin{array}{cc}1+x,& i-j=0\\ i-1,& i-j=1\\ 0,& i-j\ne 0,1\end{array}\right.\to \left\{\begin{array}{cc}1,& i-j=0\\ i-1,& i-j=1\\ 0,& i-j\ne 0,1\end{array}\right.\hfill \end{array}$$

as $x\to 0$ for $1\le i\le n+1$ and $1\le j\le n$. Consequently, employing (6) reveals$$\begin{array}{cc}\hfill \frac{{\text{d}}^{n}D(-x)}{\text{d}{x}^n}& =\frac{{(-1)}^n}{{(1+x)}^{n+1}}\left|\begin{array}{ccccccc}{e}^x& 1+x& 0& 0& \cdots & 0& 0\\ e^x& 1& 1+x& 0& \cdots & 0& 0\\ e^x& 0& 2& 1+x& \cdots & 0& 0\\ e^x& 0& 0& 3& \cdots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ e^x& 0& 0& 0& \cdots & 1+x& 0\\ e^x& 0& 0& 0& \cdots & n-1& 1+x\\ e^x& 0& 0& 0& \cdots & 0& n\end{array}\right|\hfill \\ \hfill & \to {(-1)}^n\left|\begin{array}{ccccccc}1& 1& 0& 0& \cdots & 0& 0\\ 1& 1& 1& 0& \cdots & 0& 0\\ 1& 0& 2& 1& \cdots & 0& 0\\ 1& 0& 0& 3& \cdots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& 0& 0& 0& \cdots & 1& 0\\ 1& 0& 0& 0& \cdots & n-1& 1\\ 1& 0& 0& 0& \cdots & 0& n\end{array}\right|\hfill \end{array}$$

as $x\to 0$. From (4), it follows that$$\begin{array}{c}\hfill D(-x)=\frac{e^x}{1+x}=\sum _{k=0}^{\infty }{(-1)}^n!n\frac{x^n}{n!}.\end{array}$$

This implies that(7) $$\begin{array}{c}\hfill {(-1)}^n!n=\underset{x\to 0}{lim}\frac{{\text{d}}^{n}D(-x)}{\text{d}{x}^n}={(-1)}^n\left|\begin{array}{ccccccc}1& 1& 0& 0& \cdots & 0& 0\\ 1& 1& 1& 0& \cdots & 0& 0\\ 1& 0& 2& 1& \cdots & 0& 0\\ 1& 0& 0& 3& \cdots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& 0& 0& 0& \cdots & 1& 0\\ 1& 0& 0& 0& \cdots & n-1& 1\\ 1& 0& 0& 0& \cdots & 0& n\end{array}\right|.\end{array}$$(7)

Subtracting the nth row from the $(n+1)$th row, then the $(n-1)$th row from the nth row, ..., then the 1st row from the 2nd row of the above determinant leads to$$\begin{array}{c}\hfill !n=\left|\begin{array}{ccccccc}1& 1& 0& 0& \cdots & 0& 0\\ 0& 0& 1& 0& \cdots & 0& 0\\ 0& -1& 1& 1& \cdots & 0& 0\\ 0& 0& -2& 2& \cdots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& 0& \cdots & 1& 0\\ 0& 0& 0& 0& \cdots & n-2& 1\\ 0& 0& 0& 0& \cdots & -(n-1)& n-1\end{array}\right|\end{array}$$

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$$\begin{array}{c}\hfill \left(\begin{array}{ccccccc}1& 1& 0& 0& \cdots & 0& 0\\ 1& 1& 1& 0& \cdots & 0& 0\\ 1& 0& 2& 1& \cdots & 0& 0\\ 1& 0& 0& 3& \cdots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& 0& 0& 0& \cdots & 1& 0\\ 1& 0& 0& 0& \cdots & n-1& 1\\ 1& 0& 0& 0& \cdots & 0& n\end{array}\right)\end{array}$$

is known as the “population projection matrix”. See (Kirkland & Neumann, 2013, 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ć, 2012,2011, Kittappa, 1993) 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

The authors received no direct funding for this research.

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.