1. 引言
1993年,作为内联网模型,Hsu定义了Fibonacci立方体
[1] 。由于该立方体具有类似超立方的良好性质,可以承载许多超立方上的算法 [2] ,进而引发了对其相关图类及其性质的一系列研究。Munarini和Zagaglia Salvi定义了卢卡斯立方体
[3] [4] 。此外,Fibonacci立方体和卢卡斯立方体的秩生成函数 [5] 、立方体多项式 [6] [7] 、最大立方体多项式 [8] 、不相交立方体多项式 [9] [10] 和度序列多项式 [11] 也得到了研究。同时,Klavžar,Munarini等人 [3] [6] [8] [10] [11] [12] 研究了大量与卢卡斯立方体相关的性质,及其无向Hasse-图上的计数性质;Munarini等人 [5] 还研究了其有向Hasse-图上的秩多项式等计数性质。张和平等人 [13] [14] 在平面基本二部图的完美匹配集合上建立了一个有限分配格——匹配型分配格的概念,并研究了其一些基本性质。Klavžar和Žigert Pleteršek [15] 发现了Fibonacci立方体是Fibonaccenes的共振图。Yao和Zhang进一步证明了定向的Fibonacci立方体都是匹配型分配格 [16] [17] ,其Hasse图同构于Fibonaccenes的共振有向图。然而与斐波那契立方体结构和性质相似的匹配型分配格和立方体的研究成果非常少。本文主要通过提出一个新的偏序集,从而得到了一类新的匹配型分配格,忽略掉其Hasse图中的方向后就得到一个结构和性质都与斐波那契立方体相似的新立方体——L-斐波那契相似立方体,并研究了L-斐波那契相似立方体的一些计数性质。
2. 预备知识
如果一个集合P的序关系 ≤ 满足自反性,反对称性和传递性,那这个集合称为偏序集。设Q是偏序集P的一个子集,则Q也满足P中的偏序关系:任给
,若在Q中
当且仅当在P中
。
表示x被y覆盖或y覆盖x,如果
且x与y之间再无其它元素 [18] 。设K(可能为空)为偏序集P的一个子集,若
,
且
时,有
,则称K为凸的 [19] 。设集合Q是偏序集P的一个子集,若
且
则
,那么Q称为P的一个滤子 [18] ,
表示一个偏序集P的所有滤子。所有滤子
按照反包含关系(
当且仅当
)构成的偏序集是个分配格,称为滤子格,而且
是一个有限分配格。在有限分配格
中,
(或
)表示最大(或最小)元 [19] 。若分配格仅含有一个元素,则称分配格是平凡的。设L是一个有限分配格,如果存在一个平面弱基本二部图G使得
,则称L为匹配型分配格,其中
是在图G的所有完美匹配上建立的有限分配格 [13] 。
设L是一个有限分配格,K是L的一个凸子格(即区间),若L的任意极大链至少包含K的一个元素,则称K为L的一个割。L关于K的凸扩张
是集合
(
是K的拷贝)上的一个分配格( [20] ),其导出关系为:
,在L中,若
,
,在L中,若
且
,
,在L中,若
且
,
,在K中,若
。
本文中用到但没解释的概念见文献 [18] [19] 。
一个六角系统是一个没有割点的有限连通平面图,它的每个内面都被边长为1的正六边形包围 [21] 。Fibonaccenes或“Zigzag”六角形链在六角系统中被广泛研究。斐波那契立方体是“Zigzag”六角形链的Z-变换图或共振图 [15] 。我们将“Zigzag”六角形链简单修改得到了一种新的六角系统,并从其内对偶图上得到了一个偏序集,该偏序集的滤子格同构于该六角系统的匹配型分配格(其Hasse图同构于共振有向图 [13] )。
定义2.1 “L-si-Fibonaccene”是在Fibonaccene的左端第二个六角形下面连接了一个额外六角形的Cata型六角系统,如下图1所示。本文中我们将有
个六角形的L-si-Fibonaccene记为
。
Figure 1. L-si-Fibonaccene and its inner dual graph
图1. L-si-Fibonaccene及其内对偶图
定义2.2 设
,称在
的内对偶图上的如图2所示的偏序集为L-栅栏,它是由“栅栏”(即“Zigzag”偏序)添加一个极大元得到的,记为
。
定理2.3 [14] 设
,
是L-si-Fibonaccene
的匹配型分配格,其Hasse图同构于
的有向Z-变换图。
定义2.4 将L-栅栏的滤子格
称为L-斐波那契相似立方体,记为
,为方便计,
同时也表示
的Hasse图。
前七个L-斐波那契相似立方体
,
,
,
,
,
,
,如图3所示(其中
表示只有一个顶点的平凡格或图)。
Figure 3. L-Fibonacci similar cube
,
,
图3. L-斐波那契相似立方体
,
,
引理2.5 [20] 滤子格
是可以由分配格的凸扩张得到,对任意的
有,
,
其中
和
分别表示
和
上的子偏序集。
定理2.6 当
时有,
.
证明 在
和
中,分别令
和
,则根据引理2.5得
定理2.6得证。
注释2.7 根据上述定理的证明和n的奇偶性,我们得到
的递归结构。当n为偶数时,
的所有滤子分为以下三类:不含
,
的滤子(因而是
的滤子,故其导出子格同构于
);含
但不含
的滤子(因为
是个极大元,所以删除
之后是
的滤子,反之亦然,故其导出子格同构于
);同时包含
和
的滤子(因为
是个极大元,
是个极小元,所以删除
(同时必须删去
和
)之后是
的滤子,反之亦然,故其导出子格同构于
)。由反包含关系可以得知第一类中的滤子大于第二类中对应的滤子,第二类中的滤子大于第三类中对应的滤子(如图4(a)所示)。当n为奇数时,
的所有滤子分为以下三类:不含
,
,
的滤子(因而是
的所有滤子,故其导出子格同构于
);含
但不含
的滤子(因为
是个极大元,所以删除
之后是
的所有滤子,反之亦然,故其导出子格同构于
);同时包含
和
的滤子(因为
是个极大元,
是个极小元,所以删除
和
之后是
的所有滤子,反之亦然,故其导出子格同构于
)。由反包含关系可以得知第一类中的滤子大于第二类中对应的滤子,第二类中的滤子大于第三类中对应的滤子(如图4(b)所示)。
3. 计数性质
3.1. 秩生成函数
设
的秩生成函数为
,其中
表示
中秩为k的元素的数目。其中部分
的秩生成函数如下:
Figure 4. The recursive structure diagram of
图4.
的递归结构图
引理3.1 [20] 设L是一个有限分配格且K是L的一个割,则
的秩生成函数为
其中
表示L中任意元素x的高。
由引理3.1我们有如下命题。
命题3.2 当
时,
换句话说,当
时,
设
,
,当
时,我们有
我们有
和
的递推关系。
命题3.3 设
,
,
证明 由上述得,当
时,
相似地,我们可得到
的递推关系。
由命题3.3可得
和
的生成函数,也可通过当
时,
直接得到。
定理3.4
和
的生成函数为
且
证明 由命题3.3得,
同理可得
的生成函数。
证明完毕。
设
[22] 表示
中
的系数,并且有
在OEIS [23] 中参考数列A027907。
定理3.5
且
证明 其中多项式
可如下定义
所以有
此外,
中
的系数可如下得到
所以,由
,我们有
同理,
可由
得到。
证毕。
由定理3.4我们可得到关于
的生成函数的结论。
定理3.6
的生成函数为
证明 由
和
的定义,
证毕。
在秩生成函数中取
我们有
的顶点生成函数为
推论3.7
因此有顶点的递推关系为
顶点序列中去掉
,
得到OEIS中的类斐波那契数列A104449 (去掉前两项:(3, 1) 4, 5, 9, 14, 23, 37, 60, 97...)。
3.2. 立方体多项式
设
的立方体多项式为
,其中
表示
中k维立方体的个数。其中部分立方体多项式
如下:
引理3.8. [20] 设L是一个有限分配格且K是L的一个割。则
由引理3.8我们可得
的递推关系。
命题3.9 当
时,
由此易得
的递推关系。
命题3.10 当
时,
证明 由命题3.9可得,
证毕。
定理3.11
的生成函数为
证明
证毕。
立方体多项式可从
的生成函数中导出。
推论3.12 当
时,
并且有
证明
所以,
因此,可得
。
3.3. 极大立方体多项式
极大立方体是指不包含在其他更高维立方体中的立方体。设的极大立方体多项式为
,其中
表示
中极大k维立方体的数目,其部分极大立方体多项式
如下:
由定理2.6和注释2.7可得
的递推关系。
命题3.13 当
时,
由命题3.13易得
递推关系。
命题3.14 当
时,
推论3.15 当
时,我们有
-Padovan数列
定义为:
,
,
,其中
(在OEIS [23] }中参考数列A000931)。因此我们有如下推论。
推论3.16 当
时,
此外,由命题3.14我们可得
的生成函数。
定理3.17
的生成函数为
证明 由命题3.14得,
将
利用二项式展开可得如下结论。
推论3.18 当
时,
证明 此证明分为两部分进行
其中第一部分为
第二部分为
证毕。
基金项目
国家自然科学基金项目(NO. 12161081)。
NOTES
*通讯作者。