与Pell数相关的三角矩阵的一些组合性质
Some Combinatorial Properties of Triangu-lar Matrices Related to Pell Numbers
摘要: Pell数,记,本文主要研究由v(n,k)构成的三角矩阵以及其伴随三角矩阵的组合性质,包括:行多项式的实根性和稠密性,矩阵的渐近正态性以及全正性。
Abstract: Pell number , denote . This article studies the combina-torial proprieties of two triangular matrices, one is formed by v(n,k) and the other is the adjoin-ing triangular matrices . More precisely we study the real rootedness and density of the row polynomials, and the asymptotic normality and total positivity of the matrices.
文章引用:尚宇, 刘相芯. 与Pell数相关的三角矩阵的一些组合性质[J]. 应用数学进展, 2022, 11(8): 6007-6014. https://doi.org/10.12677/AAM.2022.118633

1. 引言

Pell数是组合数学中重要的一类组合数,近年来,Pell数列及其推广引起学者的关注 [1] [2]。Pell数列与Fibonacci数列有着密切的联系,两者之间的关系为:

P n ( x ) = F n ( 2 x ) , ( n = 0 , 1 , 2 , ) ,

Pell数列的递归表达式为

P n + 2 = 2 P n + 1 + P n , P 0 = 0 , P 1 = 1 ,

通项为:

P n = k = 0 [ ( n 1 ) / 2 ] 2 k ( n 2 k + 1 ) ,对于 n > 0 时 [1]。

由Pell数表达式,记

V ( n , k ) = 2 k ( n 2 k + 1 ) ,

V ( n , k ) 构成一个三角矩阵,在OEIS (在线整数数列查询网站)中可查为A105070,本文将研究由 V ( n , k ) 构成的三角矩阵。我们将 V ( n , k ) 的行发生函数记作 V n ( x ) ,令

V n ( x ) = k = 0 n V ( n , k ) x k ,

并且发现 V n ( x ) 有互为相伴关系的函数 U n ( x ) ,其通项为

U n ( x ) = k = 0 n U ( n , k ) x k ,

三角矩阵为

U ( n , k ) = 2 k ( n 2 k ) .

在组合学中有很多序列有这样的相伴关系,例如Morgan-Voyce多项式,王毅等人研究了其稠密性,渐近正态性以及全正性 [3]。本文我们将对 V ( n , k ) U ( n , k ) 构成的三角矩阵的行多项式的实根性,稠密性以及渐近正态性和矩阵的全正性进行研究。

V n ( x ) U n ( x ) 满足下面递归关系

{ U n ( x ) = U n 1 ( x ) + 2 x V n 1 ( x ) V n ( x ) = U n 1 ( x ) + V n 1 ( x ) (1)

对于 n 3 ,其中 U 1 = V 1 = 1 。递归方程是

{ U n ( x ) = 2 U n 1 ( x ) + ( 2 x 1 ) U n 2 ( x ) U 1 ( x ) = 1 , U 2 ( x ) = 2 x + 1

{ V n ( x ) = 2 V n 1 ( x ) + ( 2 x 1 ) V n 2 ( x ) V 1 ( x ) = 1 , V 2 ( x ) = 2 (2)

在第二节中,我们将展示以上多项式的零点都是实数并且在区间 ( , 0 ] 中。以及多项式的零点在区间 ( , 0 ] 中是稠密的。在第3节中,我们展示了多项式的系数 V ( n , k ) U ( n , k ) 近似正态分布。在第4节中,我们展示了系数矩阵 ( V ( n , k ) ) n , k 0 ( U ( n , k ) ) n , k 0 是一个全正矩阵。

2. 多项式的零点

实根性就是指多项式方程的零点为实数。多项式的实根性在组合学和其他数学分支中是重要的研究课题,多项式的实根性的主要应用是证明组合序列的单峰性,对数凹性和PF性质。只有实根的系数全为正的多项式经常出现在组合数学的研究中。对于非负有限序列而言,如果我们能证明它的生成函数的实

根性,再借助牛顿不等式就可以证明其单峰性或对数凹性:如果正系数的多项式 i = 0 n a i x i 只有实根,则

a i 2 a i 1 a i + 1 ( 1 + 1 i ) ( 1 + 1 n i ) ,对于 1 i n 1

并且数列 a 0 , a 1 , , a n 是单峰和对数凹的。下面我们要证明 V n ( x ) U n ( x ) 的实根性,在证明之前我们需要引进一个引理2.1。令RZ表示只有实数根的实多项式集合。

引理2.1 ( [4])令 F , f , g 是三个实数多项式,满足以下条件

a) F ( x ) = a ( x ) f ( x ) + b ( x ) g ( x ) ,其中 a ( x ) , b ( x ) 是两个实数多项式,则 deg F = deg f deg f + 1

b) f , g R Z g = f

c) F和g首项系数符号相同。

假设 f ( r ) = 0 时,有 b ( r ) 0 ,则 F R Z f = F 。特别地,若 f ( r ) = 0 b ( r ) < 0 g f f F

定理2.2 V n ( x ) U n ( x ) 是实根的。

证明由引理2.1根据 V ( n , k ) U ( n , k ) 的递归公式(2)可推出 V n ( x ) U n ( x ) 只有实根,运用归纳假设法来证明

1) 当n = 2时, U 2 ( x ) = 2 x + 1 具备实根性。

2) 假设n = k时成立,即

a) deg U k ( x ) = deg U k 1 ( x ) (k为奇数) deg U k ( x ) = deg U k 1 ( x ) + 1 (k为偶数),

b) U k 1 ( x ) , U k 2 ( x ) R Z U k 2 ( x ) = U k 1 ( x )

c) U k 1 ( x ) U k ( x ) 有相同符号的首项系数。

U k 1 = 0 时, b ( r ) 0 ,则 U k R Z ,且 U k 1 = U k ,可得以下条件

a) deg U k + 1 ( x ) = deg U k ( x ) (k为偶数) deg U k + 1 ( x ) = deg U k ( x ) + 1 (k为奇数),

b) U k 1 ( x ) , U k ( x ) R Z U k 1 ( x ) = U k ( x )

c) U k + 1 ( x ) U k ( x ) 有相同符号的首项系数。

U k = 0 时,因为系数都大于零,则实根一定小于零, b ( r ) = ( 2 x 1 ) 0 ,符合引理2.1,实根性得证。 ¨

实际上 V n ( x ) U n ( x ) 的根可以写出显示表达,为了给出 V n ( x ) U n ( x ) 根的显示表达我们引进引理2.3和引理2.4。

引理2.3 ( [5])令 { z n } n 0 是满足 z n = a z n 1 + b z n 2 , n = 2 , 3 , ,线性递推关系的一个序列。

a 2 + 4 b > 0 ,则序列的闭式为

z n = ( z 1 z 0 λ 2 ) λ 1 n + ( z 0 λ 1 z 1 ) λ 2 n λ 1 λ 2 , n = 0 , 1 , 2 , , (3)

其中 λ 1 = a + a 2 + 4 b 2 , λ 2 = a a 2 + 4 b 2 是特征方程的根。

引理2.4 ( [6])令 λ 1 , λ 2 R ,且 n N

i) 若n为奇数,则 λ 1 n λ 2 n = ( λ 1 λ 2 ) s = 1 n 1 2 [ ( λ 1 + λ 2 ) 2 4 λ 1 λ 2 cos 2 s π n ]

ii) 若n为偶数,则 λ 1 n λ 2 n = ( λ 1 λ 2 ) ( λ 1 + λ 2 ) s = 1 n 1 2 [ ( λ 1 + λ 2 ) 2 4 λ 1 λ 2 cos 2 s π n ]

iii) 若n为奇数,则 λ 1 n + λ 2 n = ( λ 1 + λ 2 ) s = 1 n 1 2 [ ( λ 1 + λ 2 ) 2 4 λ 1 λ 2 cos 2 ( 2 s 1 ) π 2 n ]

iv) 若n为偶数,则 λ 1 n + λ 2 n = ( λ 1 + λ 2 ) s = 1 n 2 [ ( λ 1 + λ 2 ) 2 4 λ 1 λ 2 cos 2 ( 2 s 1 ) π 2 n ]

定理2.5 V n ( x ) U n ( x ) 的因式分解形式和根为

V n ( x ) = k = 1 n 1 2 ( x + V n , k ) , V n , k = 1 2 cos 2 k π n 1 2 . (4)

U n ( x ) = 1 2 k = 1 n 1 2 ( x + U n , k ) , U n , k = 1 2 cos 2 ( 2 k 1 ) π 2 n 1 2 . (5)

证明 通过 V n ( x ) U n ( x ) 的递推关系(2)由引理2.3我们可以得到 V n ( x ) U n ( x ) 的Binet形式

V n ( x ) = λ 1 n λ 2 n λ 1 λ 2 = ( 1 + 2 x ) n ( 1 2 x ) n 2 2 x ( x 0 , n 1 ) ,

U n = λ 1 n + λ 2 n 2 = ( 1 + 2 x ) n + ( 1 2 x ) n 2 ( x 0 , n 1 ) . (6)

这里 λ 1 , 2 = 1 ± 2 x 是特征方程 λ 2 2 λ ( 2 x 1 ) λ = 0 的两个根。

由引理2.4可以知道

V n ( x ) = λ 1 n λ 2 n λ 1 λ 2 = k = 1 n 1 2 [ ( λ 1 + λ 2 ) 2 4 λ 1 λ 2 cos 2 k π n ] = k = 1 n 1 2 [ x + ( 1 2 cos 2 k π n 1 2 ) ] .

类似的可以得到 U n ( x ) 的因式分解形式以及根的表达式

U n ( x ) = 1 2 k = 1 n 1 2 ( x + 1 2 cos 2 ( 2 k 1 ) π 2 n 1 2 ) . ¨

显然 V n ( x ) U n ( x ) 的所有零点都在区间 ( , 0 ] 中。下面我们将证明这些零点在区间 ( , 0 ] 中是稠密的。在证明之前我们还需要知道定义2.6和引理2.7。

定义2.6 令 ( f n ( x ) ) n 0 为复多项式序列。如果存在序列 ( z n ) n 0 使得 f n ( z n ) = 0 且当 n + z n x 。现在假设 ( f n ( x ) ) n 0 是满足递归关系

f n + k ( x ) = j = 1 k c j ( x ) f n + k j ( x )

的多项式序列,其中 c j ( x ) 是x中的多项式。令 λ j ( x ) 是相关特征方程

λ k + j = 1 k c j ( x ) λ k j = 0

的所有根。众所周知,如果 λ j ( x ) 是不同的,则

f n ( x ) = j = 1 k α j ( x ) λ j n ( x ) , (7)

其中 α j ( x ) 由初始条件确定。

引理2.7 ( [7])在非退化条件下,在(7)中没有 α j ( x ) 完全为零,且对于单位模长的 ω C ,没有 i j 使 λ i ( x ) = ω λ j ( x ) ,那么x是 ( f n ( x ) ) n 0 的零极限当且仅当

i) 两个或多个 λ i ( x ) 具有相等的模数,并且模数严格地大于其他。

ii) 存在指数j使得 λ j ( x ) 的模数严格大于所有其他 λ i ( x ) 的模数,并且 α j ( x ) = 0

定理2.8 V n ( x ) U n ( x ) 的零点在区间 ( , 0 ] 中是稠密的。

证明我们先证明 V n ( x ) 的稠密性,因为 U n ( x ) V n ( x ) 的递推关系是相同的,所以证明也是相同的。我们提出了一个更强的结果:每个 x ( , 0 ] 是序列 ( V n ( x ) ) n 1 的零极限。

引理2.7的非退化条件由 V n ( x ) 的Binet形式成立。故序列 ( V n ( x ) ) n 1 的零极限是满足 | λ 1 ( x ) | = | λ 2 ( x ) | 的实数x。因为 | λ 1 ( x ) | = | λ 2 ( x ) | ,则 | 1 + 2 x | = | 1 2 x | 。换句话说, 2 x 必须是纯虚数(允许0是纯虚数)。因此 2 x 0 ,即 x 0 ,即可证明 V n ( x ) 的零点在区间 ( , 0 ] 中是稠密的。 ¨

3. 渐近正态性

a ( n , k ) 是一个双指数非负数序列, p ( n , k ) = a ( n , k ) j = 0 n a ( n , j ) 表示正态化概率。如果序列 a ( n , k ) 满足

下式,我们就说序列 a ( n , k ) 通过中心极限定理是渐近正态的 [8]

lim n sup x R | k μ n + x σ n p ( n , k ) 1 2 π x e t 2 2 d t | = 0. (8)

其中 μ n σ n 2 分别是 a ( n , k ) 的均值和方差。如果序列 a ( n , k ) 满足下式,通过R上的局部极限定理,我们就称序列 a ( n , k ) 是渐近正态的

lim n sup x R | σ n p ( n , μ n + x σ n ) 1 2 π e x 2 2 | = 0. (9)

那么就有

n , a ( n , k ) ~ e x 2 2 j = 0 n a ( n , j ) σ n 2 π ,

其中 k = μ n + x σ n x = Ο ( 1 ) 。显然,从(9)可以推出(8)成立。

许多著名的组合序列都具有中心和局部极限定理。例如,著名的de Moivre-Laplace定理指出通过中

心和局部极限定理可以证明二项式系数 ( n k ) 是渐近正态的。其他示例包括第一类无符号斯特林数 c ( n , k )

第二类斯特林数 S ( n , k ) 和欧拉数 A ( n , k ) 。下面我们要证明 V n ( x ) U n ( x ) 的矩阵是渐近正态的,为了证明渐近正态性,我们需要用到引理3.1。

引理3.1 ( [3])令 A n ( x ) = k = 0 n a ( n , k ) x k 只有实根且 A n ( x ) = i = 1 n ( x + r i ) ,其中所有的 a ( n , k ) r i 都是非负的,令

μ n = i = 1 n 1 1 + r i , σ n 2 = i = 1 n r i ( 1 + r i ) 2 .

σ n 2 + ,则 a ( n , k ) 是渐近正态的。

定理3.2 V ( n , k ) = 2 k ( n 2 k + 1 ) 是渐近正态的,并且均值 μ n = 2 n ( 1 1 2 ) 和方差 σ n 2 = n ( 3 2 4 ) 2

证明:我们只证明 V ( n , k ) 的结果, U ( n , k ) 的证明是相似的。通过定理2.5我们有均值为

μ n = k = 1 n 1 1 2 + 1 2 cos 2 k π n 2 n π 0 π cos 2 θ 1 + cos 2 θ d θ = 2 n ( 1 1 2 ) .

方差为

σ n 2 = k = 1 n 1 2 cos 2 k π n 1 2 ( 1 2 + 1 2 cos 2 k π n ) 2 n π 0 π 2 sin 2 x cos 2 x + 2 + 1 cos 2 x d x = n ( 3 2 4 ) 2 .

n 时, μ n σ n 2 ,所以由引理3.1可以得知 V ( n , k ) 是渐近正态的。 ¨

4. 全正性

如果一个(有限或无限)矩阵的所有子矩阵都是非负的,则称为全正矩阵(简称TP)。令 ( a n ) n 0 为非负数的无限序列(我们将有限序列 a 0 , a 1 , , a n 与无限序列 a 0 , a 1 , , a n , 0 , 0 , 。定义其Toeplitz矩阵

[ a i j ] = [ a 0 a 1 a 0 a 2 a 1 a 0 ] ,

如果对应的Toeplitz矩阵是TP,我们就说这个序列是一个Pólya频率(简称PF)序列。PF序列的一个基本特征由Schoenberg和Edrei指出:序列 ( a n ) n 0 是PF当且仅当它的生成函数满足

n 0 a n x n = a x k e γ x j 0 ( 1 + α j x ) j 0 ( 1 β j x ) .

其中 a > 0 , k N , α j , β j , γ > 0 ,并且 j 0 ( α j + β j ) < + 。在这种情况下,我们也说相应的生成函数是PF。我们这一节要证明pell数和函数表达法的原函数相关的三角矩阵的全正性,用Riordan矩阵来证明全正性,下面我们介绍Riordan矩阵的概念。

d ( x ) h ( x ) 是两个形式幂级数。用 R = ( d ( x ) , h ( x ) ) 表示一个无限矩阵,其第k列的生成函数是 h k ( x ) d ( x ) 对于 k = 0 , 1 , 2 , ,当 d ( 0 ) = 1 , h ( 0 ) = 0 h ( 0 ) = 0 时,我们说R是Riordan矩阵。Riordan矩阵在枚举组合学中起着重要的统一作用,许多著名的组合矩阵都是Riordan矩阵。例如,帕斯卡三角形

P = [ ( n k ) ] 是一个Riordan矩阵,并且 P = ( 1 1 x , x 1 x ) 。对于Riordan矩阵的全正性有着各种各样的研究,

我们在证明全正性之前要知道引理4.1。

引理4.1 ( [9])如果 d ( x ) h ( x ) 都是PF,那么Riordan数组 R = ( d ( x ) , h ( x ) ) 是TP。

定理4.2 U和V都是全正矩阵。

证明: V n ( x ) U n ( x ) 多项式的系数矩阵分别为

V ( n , k ) = 2 k ( n 2 k + 1 ) = ( 1 2 3 2 4 8 ) ,

U ( n , k ) = 2 k ( n 2 k ) = ( 1 1 2 1 6 1 12 4 ) .

由系数矩阵可以求得V的第k列的生成函数为

n k 2 k ( n 2 k + 1 ) x n = 2 k x 2 k + 1 m 0 ( 2 k + 1 + m 2 k + 1 ) x m = 2 k x 2 k + 1 ( 1 x ) 2 k + 2 .

因此V是Riordan矩阵,并且 V = ( x ( 1 x ) 2 , 2 x 2 ( 1 x ) 2 ) 。类似的可以得到 U = ( 1 1 x , 2 x 2 ( 1 x ) 2 ) 。从引理4.1即可得出U和V都是全正矩阵。

5. 结论

V ( n , k ) = 2 k ( n 2 k + 1 ) 构成的三角矩阵以及其伴随三角矩阵 U ( n , k ) = 2 k ( n 2 k ) 的行多项式是实根的,并且零点在区间 ( , 0 ] 中是稠密的。 V ( n , k ) U ( n , k ) 构成的三角矩阵是具备渐近正态性以及全正性的。

参考文献

[1] Ivie, J. (1970) Problem B-161. Fibonacci Quarterly, 8, 107-108.
[2] 杨胜良, 高晓. Riordan矩阵与Pell数[J]. 兰州理工大学学报, 2017(43): 148-151.
[3] 裴毅, 王毅. Morgan-Voyce多项式的一些新性质[J]. 数学研究及应用: 中文版, 2019(39): 6.
[4] Liu, L.L. and Wang, Y. (2007) A Unified Approach to Polynomial Sequences with Only Real Zeros. Advances in Applied Mathematics, 38, 542-560.
https://doi.org/10.1016/j.aam.2006.02.003
[5] Brualdi, R.A. (1992) Introductory Combinatorics. 2nd Edition, North-Holland, Amsterdam.
[6] Beraha, S., Kahane, J. and Weiss, N.J. (1978) Limits of Zeros of Recursively Defined Families of Polynomials. Studies in Foundations and Com-binatorics, 1, 213-232.
[7] Barnard, S. and Child, J.F. (1955) Higher Algebra. Macmillan, London.
[8] Bender, E.A. (1973) Central and Local Limit Theorems Applied to Asymptotic Enumeration. Journal of Combinatorial Theory, Series A, 15, 91-111.
https://doi.org/10.1016/0097-3165(73)90038-1
[9] Chen, X. and Wang, Y. (2019) Notes on the Total Positivity of Riordan Arrays. Linear Algebra and Its Applications, 569, 156-161.
https://doi.org/10.1016/j.laa.2019.01.015