A determinantal expression and a recursive relation of the Delannoy numbers
Feng Qi
math.CO Primary 11B83, Secondary 05A15, 05A10, 11B75, 11C20, 60G50


A determinantal expression of Delannoy numbers]
A determinantal expression and a recursive relation of the Delannoy numbers

F. Qi]Feng Qi
Institute of Mathematics, Henan Polytechnic University, Jiaozuo 454010, Henan, China; College of Mathematics, Inner Mongolia University for Nationalities, Tongliao 028043, Inner Mongolia, China; School of Mathematical Sciences, Tianjin Polytechnic University, Tianjin 300387, China
mailto: F. Qi <qifeng618@gmail.com>qifeng618@gmail.com, mailto: F. Qi <qifeng618@hotmail.com>qifeng618@hotmail.com, mailto: F. Qi <qifeng618@qq.com>qifeng618@qq.com
<https://qifeng618.wordpress.com>

Dedicated to people facing and fighting COVID-19


In the paper, by a general and fundamental, but non-extensively circulated, formula for derivatives of a ratio of two differentiable functions and by a recursive relation of the Hessenberg determinant, the author finds a new determinantal expression and a new recursive relation of the Delannoy numbers. Consequently, the author derives a recursive relation for computing central Delannoy numbers in terms of related Delannoy numbers.


[2010]Primary 11B83; Secondary 05A15, 05A10, 11B75, 11C20, 60G50



This paper was typeset using -

[
    [
    December 30, 2023
=====================





§ MOTIVATIONS

The Delannoy numbers, denoted by D(p,q) for p,q≥0, form an array of positive integers which are related to lattice paths enumeration and other problems in combinatorics. For more information on their history and status in combinatorics, please refer to <cit.> and closely related references therein.
In <cit.> and <cit.>, the explicit formulas

    D(p,q)=∑_i=0^ppiqi2^i
      and  
    D(p,q)=∑_i=0^qqip+q-iq

were given.
The first few values of the Delannoy numbers D(p,q) for 0≤ p,q≤8 are listed in Table <ref>.

It is well known <cit.> that the Delannoy numbers D(p,q) satisfy a simple recurrence

    D(p,q)=D(p-1,q)+D(p-1,q-1)+D(p,q-1)

and can be generated by

    1/1-x-y-xy=∑_p,q=0^∞ D(p,q)x^py^q.

When taking n=p=q, the numbers D(n)=D(n,n) are known <cit.> as central Delannoy numbers which have the generating function

    1/√(1-6x+x^2) =∑_n=0^∞ D(n)x^k
    =1+3x+13x^2+63x^3+….

The first nine central Delannoy numbers D(n) for 0≤ n≤ 8 are listed as blacked numbers in Table <ref>.
We found on the https://mathscinet.ams.org/mathscinet/MathSciNet on 27 March 2020 that the phrase “Delannoy number” appeared in the titles of the references <cit.>. The Delannoy numbers D(p,q) were also investigated in <cit.>. The Delannoy numbers D(p,q) have some connections with the Schröder numbers. For some recent results on the Schröder numbers, please refer to <cit.> and closely related references.
In <cit.>, considering the generating function (<ref>), among other things, the authors expressed central Delannoy numbers D(n) by an integral

    D(n)=1/π∫_3-2√(2) ^3+2√(2) 1/√((t-3+2√(2) ) (3+2√(2) -t)) 1/t^n+1t

and by a determinant

    D(n)=(-1)^n
    
    a_1     1     0    …   0    0   0
    
    a_2     a_1     1    …   0    0   0
    
    a_3     a_2     a_1    …    0   0   0
    ⋮   ⋮   ⋮   ⋱   ⋮   ⋮   ⋮
    
    a_n-2    a_n-3    a_n-4   …   a_1   1    0
    
    a_n-1    a_n-2    a_n-3   …    a_2   a_1   1
    
    a_n    a_n-1    a_n-2   …   a_3    a_2    a_1

for n∈ℕ, where

    a_n=(-1)^n+1/6^n∑_ℓ=1^n (-1)^ℓ6^2ℓ(2ℓ-3)!!/(2ℓ)!!ℓn-ℓ.

Making use of the integral expression <ref>, the authors derived in <cit.> some new analytic properties, including some product inequalities and determinantal inequalities, of central Delannoy numbers D(n).
In combinatorial number theory, it is a significant and meaningful work to express concrete sequences or arrays of integer numbers or polynomials in terms of tridiagonal determinants or the Hessenberg determinants.
In this respect, the Bernoulli numbers and polynomials <cit.>, the Euler numbers and polynomials <cit.>, (central) Delannoy numbers and polynomials <cit.>, the Horadam polynomials <cit.>, (generalized) Fibonacci numbers and polynomials <cit.>, the Lucas polynomials <cit.>, and the like, have been represented via tridiagonal determinants or the Hessenberg determinants, and consequently many remarkable relations have been obtained. For more information in this area and direction, please refer to <cit.> and closely related references therein.
In this paper, by a general and fundamental, but non-extensively circulated, formula for derivatives of a ratio of two differentiable functions in <cit.> and by a recursive relation of the Hessenberg determinant in <cit.>, we find a new determinantal expression and a new recursive relation of the Delannoy numbers D(p,q). Consequently, we derive a recursive relation for computing central Delannoy numbers D(n) in terms of related Delannoy numbers D(p,q).



§ A DETERMINANTAL EXPRESSION OF THE DELANNOY NUMBERS

In this section, by virtue of a general and fundamental, but non-extensively circulated, formula for derivatives of a ratio of two differentiable functions in <cit.>, we find a new determinantal expression of the Delannoy numbers D(p,q).


For p,q≥0, the Delannoy numbers D(p,q) can be determinantally expressed by

    D(p,q)=(-1)^q/q!L_(q+1)×1(p)     M_(q+1)× q(p)_(q+1)×(q+1),

where

    L_(q+1)×1(p)   =[ ⟨ p⟩_0,⟨ p⟩_1,…,⟨ p⟩_q ]^T,
    
    M_(q+1)× q(p)   =[ (-1)^i-ji-1j-1⟨ p+1⟩_i-j ]_1≤ i≤ q+1
     1≤ j≤ q,
    ⟨ z⟩_n   =
    
    z(z-1)…(z-n+1),     n≥1;
    
    1,    n=0

is known as the n-th falling factorial of the number z∈ℂ, and T denotes the transpose of a matrix. Consequently, central Delannoy numbers D(n) for n≥0 can be determinantally expressed as

    D(n)=(-1)^n/n!L_(n+1)×1(n)     M_(n+1)× n(n)_(n+1)×(n+1).




We recall a general and fundamental, but non-extensively circulated, formula for derivatives of a ratio of two differentiable functions.
Let u(t) and v(t)0 be two n-th differentiable functions for n∈ℕ. Exercise 5) in <cit.> reads that the n-th derivative of the ratio u(t)/v(t) can be computed by

    ^n/x^n[u(t)/v(t)]
    =(-1)^n|W_(n+1)×(n+1)(t)|/v^n+1(t),

where U_(n+1)×1(t) is an (n+1)×1 matrix whose elements satisfy u_k,1(t)=u^(k-1)(t) for 1≤ k≤ n+1, V_(n+1)× n(t) is an (n+1)× n matrix whose elements meet v_i,j(t)=i-1j-1v^(i-j)(t) for 1≤ i≤ n+1 and 1≤ j≤ n, and |W_(n+1)×(n+1)(t)| is the determinant of the (n+1)×(n+1) matrix

    W_(n+1)×(n+1)(t)=[  U_(n+1)×1(t) V_(n+1)× n(t) ]_(n+1)×(n+1).

It is easy to see that

    ∂^p/∂ x^p(1/1-x-y-xy)
    =p!(1+y)^p/[1-x-(1+x)y]^p+1.

Making use of the formula (<ref>) gives

    ∂^p+q/∂ y^q∂ x^p(1/1-x-y-xy)
    =p!∂^q/∂ y^q(1+y)^p/[1-x-(1+x)y]^p+1
    
    =p!(-1)^q/[1-x-(1+x)y]^(p+1)(q+1)
    ×|
    
    (1+y)^p     [1-x-(1+x)y]^p+1
    ⟨ p⟩_1(1+y)^p-1   (-1)^1⟨ p+1⟩_1(1+x)^1[1-x-(1+x)y]^p
    ⟨ p⟩_2(1+y)^p-2   (-1)^2⟨ p+1⟩_2(1+x)^2[1-x-(1+x)y]^p-1
    ⟨ p⟩_3(1+y)^p-3   (-1)^3⟨ p+1⟩_3(1+x)^3[1-x-(1+x)y]^p-2
    ⋮   ⋮
    ⟨ p⟩_q-2(1+y)^p-q+2   (-1)^q-2⟨ p+1⟩_q-2(1+x)^q-2[1-x-(1+x)y]^p-q+3
    ⟨ p⟩_q-1(1+y)^p-q+1   (-1)^q-1⟨ p+1⟩_q-1(1+x)^q-1[1-x-(1+x)y]^p-q+2
    ⟨ p⟩_q(1+y)^p-q   (-1)^q⟨ p+1⟩_q(1+x)^q[1-x-(1+x)y]^p-q+1.
    
    0
    11[1-x-(1+x)y]^p+1
    21(-1)^1⟨ p+1⟩_1(1+x)^1[1-x-(1+x)y]^p
    31(-1)^2⟨ p+1⟩_2(1+x)^2[1-x-(1+x)y]^p-1
    ⋮
    q-21(-1)^q-3⟨ p+1⟩_q-3(1+x)^q-3[1-x-(1+x)y]^p-q+4
    q-11(-1)^q-2⟨ p+1⟩_q-2(1+x)^q-2[1-x-(1+x)y]^p-q+3
    q1(-1)^q-1⟨ p+1⟩_q-1(1+x)^q-1[1-x-(1+x)y]^p-q+2
    
    0   …
    
    0   …
    22[1-x-(1+x)y]^p+1   …
    32(-1)^1⟨ p+1⟩_1(1+x)^1[1-x-(1+x)y]^p   …
    ⋮   ⋱
    q-22(-1)^q-4⟨ p+1⟩_q-4(1+x)^q-4[1-x-(1+x)y]^p-q+5   …
    q-12(-1)^q-3⟨ p+1⟩_q-3(1+x)^q-3[1-x-(1+x)y]^p-q+4   …
    q2(-1)^q-2⟨ p+1⟩_q-2(1+x)^q-2[1-x-(1+x)y]^p-q+3   …
    
    0                                                            
    
    0                                                            
    
    0                                                            
    
    0                                                            
    ⋮
    q-2q-2[1-x-(1+x)y]^p+1
    q-1q-2(-1)⟨ p+1⟩_1(1+x)[1-x-(1+x)y]^p
    qq-2⟨ p+1⟩_2(1+x)^2[1-x-(1+x)y]^p-1
    .
    
                                                              0
    
                                                              0
    
                                                              0
    
                                                              0
    ⋮
    
                                 0
    q-1q-1[1-x-(1+x)y]^p+1
    qq-1(-1)⟨ p+1⟩_1(1+x)[1-x-(1+x)y]^p|
    →(-1)^qp!
    |
    ⟨ p⟩_0         (-1)^0⟨ p+1⟩_0            0                                 
    ⟨ p⟩_1         (-1)^1⟨ p+1⟩_1           11(-1)^0⟨ p+1⟩_0          
    ⟨ p⟩_2         (-1)^2⟨ p+1⟩_2           21(-1)^1⟨ p+1⟩_1          
    ⟨ p⟩_3         (-1)^3⟨ p+1⟩_3           31(-1)^2⟨ p+1⟩_2           
    ⋮   ⋮   ⋮
    ⟨ p⟩_q-2    (-1)^q-2⟨ p+1⟩_q-2   q-21(-1)^q-3⟨ p+1⟩_q-3
    ⟨ p⟩_q-1    (-1)^q-1⟨ p+1⟩_q-1   q-11(-1)^q-2⟨ p+1⟩_q-2
    ⟨ p⟩_q         (-1)^q⟨ p+1⟩_q         q1(-1)^q-1⟨ p+1⟩_q-1.
    .
    
    0    …                                                        0                                                             0
    
    0   …                                                         0                                                             0
    22(-1)^0⟨ p+1⟩_0   …                    0                                                             0
    32(-1)^1⟨ p+1⟩_1   …                    0                                                             0
    ⋮   ⋱   ⋮   ⋮
    q-22(-1)^q-4⟨ p+1⟩_q-4   …   q-2q-2(-1)^0⟨ p+1⟩_0                                0
    q-12(-1)^q-3⟨ p+1⟩_q-3   …   q-1q-2(-1)^1⟨ p+1⟩_1    q-1q-1(-1)^0⟨ p+1⟩_0
    q2(-1)^q-2⟨ p+1⟩_q-2   …   qq-2(-1)^2⟨ p+1⟩_2    qq-1(-1)^1⟨ p+1⟩_1
    |

as x,y→0. Consequently, we have

    D(p,q)=1/p!q!∂^p+q/∂ y^q∂ x^p(1/1-x-y-xy)
    
    =(-1)^q/q![ ⟨ p⟩_ij ]_0≤ i≤ q
     j=1   [ (-1)^i-ji-1j-1⟨ p+1⟩_i-j ]_1≤ i≤ q+1
     1≤ j≤ q_(q+1)×(q+1).

The determinantal expression (<ref>) is thus proved.
From (<ref>), we readily see that, when n=p=q, central Delannoy numbers D(n) for n≥0 can be expressed as (<ref>).
The proof of Theorem <ref> is complete.



Since the symmetric property D(p,q)=D(q,p), from the determinantal expression (<ref>) in Theorem <ref>, it follows that

    L_(q+1)×1(p)     M_(q+1)× q(p)_(q+1)×(q+1)
    
    =(-1)^p-qq!/p!L_(p+1)×1(q)     M_(p+1)× p(q)_(p+1)×(p+1).

For example, when p=8 and q=3, we have

    L_4×1(8)     M_4×3(8)_4×4
    =-3!/8!L_9×1(3)     M_9×8(3)_9×9.

This means that, when computing D(p,q), if p≥ q, it would be sufficient to compute the determinant

    L_(q+1)×1(p)     M_(q+1)× q(p)_(q+1)×(q+1).




The determinantal expression (<ref>) is different from and simpler than (<ref>) established in <cit.>.




§ A RECURSIVE RELATION OF THE DELANNOY NUMBERS

In this section, by virtue of a recursive relation of the Hessenberg determinant in <cit.>, we will find a new recursive relation of the Delannoy numbers D(p,q).


For p,q≥0, the Delannoy numbers D(p,q) satisfy the recursive relation

    D(p,q)=pq +(-1)^q-1∑_r=0^q-1(-1)^rp+1q-rD(p,r).

Consequently, central Delannoy numbers D(n) for n≥0 satisfy

    D(n)=1+(-1)^n+1∑_r=0^n-1(-1)^rn+1r+1D(n,r).




Let Q_0=1 and

    Q_n=
    
    e_1,1    e_1,2    0    …    0     0
    
    e_2,1    e_2,2    e_2,3   …    0     0
    
    e_3,1    e_3,2    e_3,3   …    0     0
    ⋮   ⋮   ⋮   ⋮   ⋮   ⋮
    
    e_n-2,1    e_n-2,2    e_n-2,3   …    e_n-2,n-1    0 
    
    e_n-1,1    e_n-1,2    e_n-1,3   …    e_n-1,n-1    e_n-1,n
    
    e_n,1    e_n,2    e_n,3   …    e_n,n-1    e_n,n

for n∈ℕ. In <cit.>, it was proved that the sequence Q_n for n≥0 satisfies Q_1=e_1,1 and

    Q_n=∑_r=1^n(-1)^n-re_n,r(∏_j=r^n-1e_j,j+1) Q_r-1

for n≥2, where the empty product is understood to be 1. Replacing the determinant Q_r by (-1)^r-1(r-1)!D(p,r-1) in (<ref>) for 1≤ r≤ n in the recursive relation (<ref>) and simplifying give

    D(p,n-1)=⟨ p⟩_n-1/(n-1)!
    +(-1)^n∑_r=2^n(-1)^r⟨ p+1⟩_n-r+1/(n-r+1)!D(p,r-2)

which is equivalent to the recursive relation (<ref>).
When n=p=q in (<ref>), we can see that central Delannoy numbers D(n) satisfy the recursive relation (<ref>).
The proof of Theorem <ref> is complete.



The recursive relation (<ref>) is different from (<ref>).



The recursive relation (<ref>) demonstrates that we can compute central Delannoy numbers D(n) in terms of the Delannoy numbers D(p,q). However, the Delannoy numbers D(p,q) can not be expressed in terms of central Delannoy numbers D(n).



The recursive relation (<ref>) can be rearranged as

    D(n)=1-∑_r=0^n-1(-1)^n-rn+1r+1D(n,r)
    =1-∑_r=1^n(-1)^rn+1rD(n,n-r).




The recursive relation (<ref>) can also be written as

    1-D(1)   =-1/1!⟨2⟩_1D(1,0),
    
    1-D(2)   =-1/1!⟨3⟩_1D(2,1)+1/2!⟨3⟩_2D(2,0),
    
    1-D(3)   =-1/1!⟨4⟩_1D(3,2)+1/2!⟨4⟩_2D(3,1) +-1/3!⟨4⟩_3D(3,0),
    
    1-D(4)   =-1/1!⟨5⟩_1D(4,3)+1/2!⟨5⟩_2D(4,2) +-1/3!⟨5⟩_3D(4,1) +1/4!⟨5⟩_4D(4,0),

and so on. Consequently, making use of the symmetry relation D(p,q)=D(q,p), we can reformulate the recursive relation (<ref>) as

    [   D(1);   D(2);   D(3);   D(4);      ⋮; D(n-1);   D(n) ]
    =
    [ 1; 1; 1; 1; ⋮; 1; 1 ]
    -
    M_n× n[           -1/1!;            1/2!;           -1/3!;            1/4!;               ⋮; (-1)^n-1/(n-1)!;       (-1)^n/n! ],

where

    M_n× n=(
    ⟨2⟩_1D(0,1)   0   0                                                                        
    ⟨3⟩_1D(1,2)   ⟨3⟩_2D(0,2)   0                                                  
    ⟨4⟩_1D(2,3)   ⟨4⟩_2D(1,3)   ⟨4⟩_3D(0,3)                            
    ⟨5⟩_1D(3,4)   D⟨5⟩_2(2,4)   ⟨5⟩_3D(1,4)                            
    ⋮   ⋮   ⋮
    ⟨ n⟩_1D(n-2,n-1)   ⟨ n⟩_2D(n-3,n-1)   ⟨ n⟩_3D(n-4,n-1)             
    ⟨ n+1⟩_1D(n-1,n)   ⟨ n+1⟩_2D(n-2,n)   ⟨ n+1⟩_3D(n-3,n)
    .
    .
    
    0   …    0   0
    
    0   …    0   0
    
    0   …    0   0
    ⟨5⟩_4D(0,4)   …    0   0
    ⋮   ⋱   ⋮   ⋮
    ⟨ n⟩_4D(n-5,n-1)   …   ⟨ n⟩_n-1D(0,n-1)   0
    ⟨ n+1⟩_4D(n-4,n)   …   ⟨ n+1⟩_n-1D(1,n)   ⟨ n+1⟩_nD(0,n)
    ).




The recursive relation (<ref>) should be new. Therefore, the recursive relation (<ref>) should be new. Furthermore, the determinantal expression (<ref>) should also be new. Interesting!



This paper is a revised version of the electronic preprint <cit.>.




 §.§ Acknowledgements

The author thanks Christer Oscar Kiselman (Department of Information Technology, Uppsala University, Sweden) for his careful corrections, helpful suggestions, and valuable comments in April 2020 on the original version of this paper.
The author thanks anonymous referees for their careful corrections and valuable comments on the original version of this paper.


mmn

