一类有向斐波那契相似立方体的度相关计数性质

The Enumerative Properties Related to Degree of a Class of Directed Fibonacci-Like Cubes

摘要: 匹配型分配格将偏序集和平面基本二部图紧密地联系起来。本文根据一类匹配型分配格的Hasse图，得到了一类有向斐波那契相似立方体，并研究了其度序列多项式、出度多项式和出入度多项式。

Abstract: The matchable distributive lattices closely connect the poset with the planar elementary bipartite graphs. In this paper, according to the Hasse diagrams of a class of matchable distributive lattices, a class of directed Fibonacci-like cubes is obtained and their degree sequence polynomials, out-degree polynomials and in-out degree polynomials are studied.

1. 研究背景

1993年，Hsu定义了Fibonacci立方体${\Gamma }_n$ [1]作为新的内联网拓扑结构模型，斐波那契立方体可以作为一个等距离子图嵌入到布尔立方体(超立方体)中，它还包含一些其他特殊结构，如Lucas立方体作为它的子图，因此斐波那契立方体可以在容错计算中得到应用。Fibonacci立方体及其相关立方体的很多性质被大量的学者研究[2]-[8]。特殊地，Fibonacci立方体和Lucas立方体度序列多项式[9]也得到了研究。Zhang等[10] [11]在平面基本二部图的完美匹配集合上建立了一个有限分配格——匹配型分配格的概念。斐波那契立方体是平面六a角系统fibonaccenes的共振图，所以以有向斐波那契立方体作为Hasse图的分配格是匹配型分配格。Wang等[12]研究了有限分配格的凸扩张，给出Fibonacci立方体的一种更简单的画法。继而Wang等[13]提出了匹配型Lucas立方体的结构并且用一种统一的方式得到其度序列多项式。周玉玉等[14]提出了一类新的斐波那契相似立方体——匹配型分配格并研究了该类立方体的一些特殊性质。本文对周玉玉等[14]提出的斐波那契相似立方体给出了一个定向，并讨论了其与出度、入度相关的多项式，如度序列多项式、出度多项式及出入度多项式。

2. 预备知识

如果一个集合P有二元序关系$\le$ 满足自反性、反对称性和传递性，那称P为偏序集。如果$x<y$ 且$x\le z<y$ 必有$x=z$ ，则称偏序集P中y覆盖x。偏序关系与其覆盖关系相互唯一确定，偏序集的覆盖关系可以表示为以P中元素为顶点的有向图(通常画为Hasse图)：当且仅当y覆盖x时，$\left(y,x\right)$ 是一条弧。设Q是偏序集P的一个子集，若$y\in Q$ 且$y\le z$ ，则$z\in Q$ ，则称Q为P的一个滤子，$ℱ\left(P\right)$ 表示一个偏序集P的所有滤子。P的所有滤子$ℱ\left(P\right)$ 按照反包含关系($Y^{\prime }\le Y$ 当且仅当$Y^{\prime }\supseteq Y$ )构成的偏序集是个分配格，称为滤子格，而且$ℱ\left(P\right):=\left(ℱ\left(P\right),\supseteq \right)$ 是一个有限分配格。在有限分配格$ℱ\left(P\right)$ 中，$\widehat{1}$ (或$\widehat{0}$ )表示最大(或最小)元，从$\widehat{1}$ 到$\widehat{0}$ 按元素覆盖关系给分配格$ℱ\left(P\right)$ 一个定向，这样最大元$\widehat{1}$ 只有出度，最大元$\widehat{1}$ 和最小元$\widehat{0}$ 之间的其他元素首先有入度然后有出度，而最小元$\widehat{0}$ 只有入度，这样的定向也是Z-变换图顶点间的定向，就可以定义并研究分配格的出度多项式及其出入度多项式。

引理2.1 [12]滤子格$ℱ\left(P\right)$ 可以由分配格的凸扩张“$⊞$ ”得到，对任意的$x\in P$ ，有：

$ℱ\left(P\right)\cong ℱ\left(P-x\right)⊞ℱ\left(P\ast x\right)$

其中，$P-x$ 和$P\ast x$ 分别表示$P\backslash \left\{x\right\}$ 和$P\backslash \left\{y\in P|y\le x或x\le y\right\}$ ，均为P的子偏序集。

定义2.2 [14] “L-si-Fibonaccene”是在Fibonaccene的左端第二个六角形下面连接了一个额外六角形的Cata型六角系统，如下图1所示。本文中，我们将$n\left(\ge 3\right)$ 个六角形的L-si-Fibonaccene记为$Y_n$ 。

定义2.3 [14]设$n\ge 3$ ，称在$Y_n$ 的内对偶图上的如图2所示的偏序集为${\psi }_n$ ，它是由“栅栏”(即“Zigzag”偏序)添加一个极大元得到的。

Figure 1. L-si-Fibonaccene and its inner dual graph

图1. L-si-Fibonaccene及其内对偶图

(a) n是偶数 (b) n是奇数

Figure 2. Partial order ${\psi }_n$

图2. 偏序${\psi }_n$

定理2.4 [11]设$n\ge 3$ ，$M\left(Y_n\right)\cong ℱ\left({\psi }_n\right)$ 是L-si-Fibonaccene $Y_n$ 的匹配型分配格，其Hasse图同构于$Y_n$ 的有向Z-变换图。

以${\Psi }_3$ 为例，给出具体的${\Psi }_3$ 的构造过程。${\Psi }_3$ 对应的偏序如下图3所示。

Figure 3. Partially ordered set ${\Psi }_3$ corresponding to ${\Psi }_3$

图3. ${\Psi }_3$ 对应的偏序集${\psi }_3$

其中，${\psi }_3$ 的滤子有$\{\varnothing \}$ 、$\left\{x_1\right\}$ 、$\left\{x_2\right\}$ 、$\left\{x_1,x_2\right\}$ 、$\left\{x_1,x_2,x_3\right\}$ 。然后按滤子的反包含关系构成一个滤子格，是匹配型分配格，覆盖关系为反包含关系，集合之间差一个元素。根据这样的构造就能得到${\Psi }_3$ ，如图4所示。

Figure 4. ${\Psi }_3$

图4. ${\Psi }_3$

定理2.5 [14]当$n\ge 5$ 时，有：

${\Psi }_n\cong {\Psi }_{n-1}⊞{\Psi }_{n-2}\cong \left({\Psi }_{n-2}⊞{\Psi }_{n-3}\right)⊞{\Psi }_{n-2}$ .

根据定理2.5就可以得到如图5所示的${\Psi }_n$ 的递归结构图。

(a) n是偶数 (b) n是奇数

Figure 5. Recursive structure diagram of ${\Psi }_n$

图5. ${\Psi }_n$ 的递归结构图

前七个有向斐波那契相似立方体${{\Psi }^{\prime }}_0$ 、${{\Psi }^{\prime }}_1$ 、${{\Psi }^{\prime }}_2$ 、${{\Psi }^{\prime }}_3$ 、${{\Psi }^{\prime }}_4$ 、${{\Psi }^{\prime }}_5$ 、${{\Psi }^{\prime }}_6$ ，如图6所示，其中${{\Psi }^{\prime }}_0$ 表示只有一个顶点的平凡格或图。

Figure 6. Directed Fibonacci-like cubes ${{\Psi }^{\prime }}_0,\cdots ,{{\Psi }^{\prime }}_6$

图6. 有向斐波那契相似立方体${{\Psi }^{\prime }}_0,\cdots ,{{\Psi }^{\prime }}_6$

在画上述有向立方体的过程中，若y覆盖x，则将y放在x上方，当忽略掉所有弧的方向就得到偏序集的Hasse图。由此前七个斐波那契相似立方体，也就是其Hasse图，${{\Psi }^{\prime }}_0$ 、${{\Psi }^{\prime }}_1$ 、${{\Psi }^{\prime }}_2$ 、${{\Psi }^{\prime }}_3$ 、${{\Psi }^{\prime }}_4$ 、${{\Psi }^{\prime }}_5$ 、${\Psi }_6$ ，如图7所示。

Figure 7. Fibonacci-like cubes ${\Psi }_0,\cdots ,{\Psi }_6$

图7. 斐波那契相似立方体${\Psi }_0,\cdots ,{\Psi }_6$

3. 度相关计数性质

1) 度序列多项式

设$d_{n,k}:=d_k\left({\Psi }_n\right)$ 表示${\Psi }_n$ 中度为k的顶点数目，也可表示为$d_{n,k}=\left|\left\{v\in V\left({\Psi }_n\right)|{\mathrm{deg}}_{{\Psi }_n}\left(v\right)=k\right\}\right|$ ，则称如下计数多项式

$D_n\left(x\right)={\displaystyle \sum _{k\ge 0}{d}_{n,k}}{x}^k$

为${\Psi }_n$ 的度序列多项式。部分$D_n\left(x\right)$ 如下：

$\begin{array}{l}{D}_0\left(x\right)=1,\\ D_1\left(x\right)=2x,\\ D_2\left(x\right)=4x^2,\\ D_3\left(x\right)=x+3x^2+x^3,\\ D_4\left(x\right)=x+7x^3+x^4,\\ D_5\left(x\right)=2x^2+7x^3+4x^4+x^5,\\ D_6\left(x\right)=2x^2+4x^3+12x^4+4x^5+x^6.\end{array}$

通过在${\Psi }_n$ 的递归结构中虚添一个${\Psi }_{n-3}$ 及部分边，如图8所示。可得$d_{n,k}$ 的递归结构。

Figure 8. Modified recursive relationship diagram of ${\Psi }_n$

图8. 修改过的${\Psi }_n$ 的递归关系图

命题3.1 当$n\ge 5$ 时，

$d_{n,k}=d_{n-1,k-1}+d_{n-2,k-1}-d_{n-3,k-2}+d_{n-3,k-1}.$

由命题3.1可得如下推论。

命题3.2 当$n\ge 5$ 时，

$D_n\left(x\right)=x{D}_{n-1}\left(x\right)+x{D}_{n-2}\left(x\right)+\left(x-x^2\right)D_{n-3}\left(x\right).$

因此，可得$D_n\left(x\right)$ 的生成函数。

定理3.3 $D_n\left(x\right)$ 的生成函数为：

${\displaystyle \sum _{n\ge 0}{D}_n\left(x\right)y^n}=\frac{1+xy+\left(-x+2x^2\right)y^2+\left(2x^2-3x^3\right)y^3+\left(x-3x^2+2x^3\right)y^4}{1-xy-x{y}^2-\left(x-x^2\right)y^3}.$

证明 由命题3.2得：

$\begin{array}{c}{\displaystyle \sum _{n\ge 0}{D}_n}\left(x\right)y^n={\displaystyle \sum _{n\ge 5}{D}_n}\left(x\right)y^n+{\displaystyle \sum _{n=0}^4{D}_n}\left(x\right)y^n\\ ={\displaystyle \sum _{n\ge 5}\left(x{D}_{n-1}\left(x\right)+x{D}_{n-2}\left(x\right)+\left(x-x^2\right)D_{n-3}\left(x\right)\right)y^n}+{\displaystyle \sum _{n=0}^4{D}_n}\left(x\right)y^n\\ =x{\displaystyle \sum _{n\ge 5}{D}_{n-1}}\left(x\right)y^n+x{\displaystyle \sum _{n\ge 5}{D}_{n-2}}{y}^n+x{\displaystyle \sum _{n\ge 5}{D}_{n-3}}\left(x\right)y^n-x^2{\displaystyle \sum _{n\ge 5}{D}_{n-3}}\left(x\right)y^n+{\displaystyle \sum _{n=0}^4{D}_n}\left(x\right)y^n\\ =xy{\displaystyle \sum _{n\ge 0}{D}_n}\left(x\right)y^n-xy\left(D_0\left(x\right)+D_1\left(x\right)y+D_2\left(x\right)y^2+D_3\left(x\right)y^3\right)+x{y}^2{\displaystyle \sum _{n\ge 0}{D}_n}\left(x\right)y^n\\ -x{y}^2\left(D_0\left(x\right)+D_1\left(x\right)y+D_2\left(x\right)y^2\right)+x{y}^3{\displaystyle \sum _{n\ge 0}{D}_n}\left(x\right)y^n-x{y}^3\left(D_0\left(x\right)+D_1\left(x\right)y\right)\\ -x^2{y}^3{\displaystyle \sum _{n\ge 0}{D}_n}\left(x\right)y^n+x^2{y}^3\left(D_0\left(x\right)+D_1\left(x\right)y\right)+D_0\left(x\right)+D_1\left(x\right)y+D_2\left(x\right)y^2\\ +D_3\left(x\right)y^3+D_4\left(x\right)y^4\\ =\left(xy+x{y}^2+x{y}^3-x^2{y}^3\right){\displaystyle \sum _{n\ge 0}{D}_n}\left(x\right)y^n+1+xy+2x^2{y}^3-3x^3{y}^3-3x^2{y}^4\\ +2x^3{y}^4-x{y}^2+2x^2{y}^2+x{y}^4.\end{array}$

推论3.4 当$n\ge 5$ 时，${\Psi }_n$ 中度为k的顶点个数为：

$\begin{array}{c}{d}_{n,k}={\displaystyle \sum _{j=0}^k\left(\begin{array}{c}j\\ n-k-j\end{array}\right)}\left(2\left(\begin{array}{c}n-2j-2\\ k-j-2\end{array}\right)+\left(\begin{array}{c}n-2j\\ k-j\end{array}\right)+\left(\begin{array}{c}n-2j-1\\ k-j-1\end{array}\right)-3\left(\begin{array}{c}n-2j-3\\ k-j-3\end{array}\right)\right)\\ +{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}j\\ n-k-j-1\end{array}\right)}\left(2\left(\begin{array}{c}n-2j-3\\ k-j-2\end{array}\right)+2\left(\begin{array}{c}n-2j-4\\ k-j-3\end{array}\right)-\left(\begin{array}{c}n-2j-2\\ k-j-1\end{array}\right)\right)\\ +{\displaystyle \sum _{j=0}^k\left(\left(\begin{array}{c}j\\ n-j-k-3\end{array}\right)\left(\begin{array}{c}n-2j-4\\ k-j-1\end{array}\right)-3\left(\begin{array}{c}j\\ n-k-j-2\end{array}\right)\left(\begin{array}{c}n-2j-4\\ k-j-2\end{array}\right)\right)}.\end{array}$

证明 利用二项式展开，

$\frac{x^n}{{\left(1-x\right)}^{n+1}}={\displaystyle \sum _{j\ge n}\left(\begin{array}{c}j\\ n\end{array}\right)x^j}.$

我们先考虑部分展开，

$f\left(x,y\right)=\frac{1}{\left(1-xy\right)\left(1-x{y}^2\right)-x{y}^3}$

$\begin{array}{c}f\left(x,y\right)=\frac{1}{\left(1-xy\right)\left(1-x{y}^2\right)-x{y}^3}\\ =\frac{{\left(1-xy\right)}^{-1}{\left(1-x{y}^2\right)}^{-1}}{1-x{y}^3{\left(1-xy\right)}^{-1}{\left(1-x{y}^2\right)}^{-1}}\\ ={\displaystyle \sum _{t\ge 0}{x}^t{y}^{3t}}{\left(1-xy\right)}^{-t-1}{\left(1-x{y}^2\right)}^{-t-1}\end{array}$

$\begin{array}{c}={\displaystyle \sum _{t\ge 0}\frac{x{y}^t}{{\left(1-xy\right)}^{t+1}}}\frac{{\left(x{y}^2\right)}^t}{{\left(1-x{y}^2\right)}^{t+1}}{x}^{-t}\\ ={\displaystyle \sum _{t\ge 0}{\displaystyle \sum _{i\ge t}\left(\begin{array}{c}i\\ t\end{array}\right)}}{\left(xy\right)}^i{\displaystyle \sum _{j\ge t}\left(\begin{array}{c}j\\ t\end{array}\right)}{\left(x{y}^2\right)}^j{x}^{-t}\\ ={\displaystyle \sum _{n\ge 0}{\displaystyle \sum _{k=0}^n{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j\\ k-j\end{array}\right)}}}\left(\begin{array}{c}j\\ n-k-j\end{array}\right)x^k{y}^n\end{array}$

所以(其中符号$\left[x^k\right]f\left(x,y\right)$ 表示$f\left(x,y\right)$ 中$x^k$ 的系数)

$\left[x^k\right]\left[y^n\right]f\left(x,y\right)={\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j\\ k-j\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j\end{array}\right).$

记

$\begin{array}{l}\frac{1+xy+2x^2{y}^3-3x^3{y}^3-3x^2{y}^4+2x^3{y}^4-x{y}^2+2x^2{y}^2+x{y}^4}{\left(1-xy\right)\left(1-x{y}^2\right)-x{y}^3}\\ =f\left(x,y\right)+xyf\left(x,y\right)+2x^2{y}^{3}f\left(x,y\right)-3x^3{y}^{3}f\left(x,y\right)-3x^2{y}^{4}f\left(x,y\right)\\ +2x^3{y}^{4}f\left(x,y\right)-x{y}^{2}f\left(x,y\right)+2x^2{y}^{2}f\left(x,y\right)+x{y}^{4}f\left(x,y\right)\end{array}$

则

$\begin{array}{l}\left[x^k\right]\left[y^n\right]\frac{1+xy+2x^2{y}^3-3x^3{y}^3-3x^2{y}^4+2x^3{y}^4-x{y}^2+2x^2{y}^2+x{y}^4}{\left(1-xy\right)\left(1-x{y}^2\right)-x{y}^3}\\ =\left[x^k\right]\left[y^n\right]f\left(x,y\right)+\left[x^{k-1}\right]\left[y^{n-1}\right]f\left(x,y\right)+2\left[x^{k-2}\right]\left[y^{n-3}\right]f\left(x,y\right)\\ -3\left[x^{k-3}\right]\left[y^{n-3}\right]f\left(x,y\right)-3\left[x^{k-2}\right]\left[y^{n-4}\right]f\left(x,y\right)+2\left[x^{k-3}\right]\left[y^{n-4}\right]f\left(x,y\right)\\ -\left[x^{k-1}\right]\left[y^{n-2}\right]f\left(x,y\right)+2\left[x^{k-2}\right]\left[y^{n-2}\right]f\left(x,y\right)+\left[x^{k-1}\right]\left[y^{n-4}\right]f\left(x,y\right)\\ ={\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j\\ k-j\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j\end{array}\right)+{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j-1\\ k-j-1\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j\end{array}\right)\\ +2{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j-3\\ k-j-2\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j-1\end{array}\right)-3{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j-3\\ k-j-3\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j\end{array}\right)\\ -3{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j-4\\ k-j-2\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j-2\end{array}\right)+2{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j-4\\ k-j-3\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j-1\end{array}\right)\\ -{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j-2\\ k-j-1\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j-1\end{array}\right)+2{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j-2\\ k-j-2\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j\end{array}\right)\\ +{\displaystyle \sum _{j=0}^k\left(\begin{array}{c}n-2j-4\\ k-j-1\end{array}\right)}\left(\begin{array}{c}j\\ n-k-j-3\end{array}\right).\end{array}$

注释1 当$x=1$ 时，求解命题3.2中$D_n\left(x\right)$ 的递推关系，可得${\Psi }_n\left(n\ge 2\right)$ 的顶点数为$f\left(n\right)+3f\left(n-1\right)$ ，其中$f\left(n\right)$ 是第n个斐波那契数。

2) 入度和出度多项式

设${\Psi }_n$ 的入度多项式为$D_n^{-}\left(x\right)={\displaystyle \sum _{k=0}^{n-1}{d}_{n,k}^{-}}{x}^k$ ，其中$d_{n,k}^{-}$ 表示${{\Psi }^{\prime }}_n$ 中入度为k的顶点个数。部分入度多项式$D_n^{-}\left(x\right)$ 如下所示：

$\begin{array}{l}{D}_0^{-}\left(x\right)=1,\\ D_1^{-}\left(x\right)=1,\\ D_2^{-}\left(x\right)=1+2x+x^2,\\ D_3^{-}\left(x\right)=1+3x+x^2,\\ D_4^{-}\left(x\right)=1+4x+3x^2+x^3,\\ D_5^{-}\left(x\right)=1+5x+6x^2+2x^3,\\ D_6^{-}\left(x\right)=1+6x+10x^2+5x^3+x^4,\\ D_7^{-}\left(x\right)=1+7x+15x^2+11x^3+3x^4,\\ D_8^{-}\left(x\right)=1+8x+21x^2+21x^3+8x^4+x^5,\\ D_9^{-}\left(x\right)=1+9x+28x^2+36x^3+19x^4+4x^5.\end{array}$

引理3.5 [12]设L是一个有限分配格。如果K是L的一个割，则：

$d_k^{-}\left(L⊞K\right)=d_k^{-}\left(L\right)+d_{k-1}^{-}\left(K\right).$

由引理3.5我们有如下命题。

命题3.6 当$n\ge 0$ 时，$d_{n,0}^{-}=1$ ；当$n\ge 3$ ，$k\ge 1$ 时，

$d_{n,k}^{-}=d_{n-1,k}^{-}+d_{n-2,k-1}^{-}.$

命题3.7 当$n\ge 3$ 时，

$D_n^{-}\left(x\right)=D_{n-1}^{-}\left(x\right)+x{D}_{n-2}^{-}\left(x\right).$

定理3.8 $D_n^{-}\left(x\right)$ 的生成函数为：

${\displaystyle \sum _{n\ge 0}{D}_n^{-}}\left(x\right)y^n=\frac{1+\left(x+x^2\right)y^2}{1-y-x{y}^2}.$

证明

$\begin{array}{c}{\displaystyle \sum _{n=0}^{\infty }{D}_n^{-}}\left(x\right)y^n={\displaystyle \sum _{n=3}^{\infty }{D}_n^{-}}\left(x\right)y^n+{\displaystyle \sum _{n=0}^2{D}_n^{-}}\left(x\right)y^n\\ ={\displaystyle \sum _{n=3}^{\infty }\left(D_{n-1}^{-}\left(x\right)+x{D}_{n-2}^{-}\left(x\right)\right)y^n}+{\displaystyle \sum _{n=0}^2{D}_n^{-}}\left(x\right)y^n\\ ={\displaystyle \sum _{n=3}^{\infty }{D}_{n-1}^{-}}\left(x\right)y^n+x{\displaystyle \sum _{n=3}^{\infty }{D}_{n-2}^{-}}\left(x\right)y^n+{\displaystyle \sum _{n=0}^2{D}_n^{-}}\left(x\right)y^n\\ =y{\displaystyle \sum _{n=3}^{\infty }{D}_{n-1}^{-}}\left(x\right)y^{n-1}+x{y}^2{\displaystyle \sum _{n=3}^{\infty }{D}_{n-2}^{-}}\left(x\right)y^{n-2}+{\displaystyle \sum _{n=0}^2{D}_n^{-}}\left(x\right)y^n\\ =y{\displaystyle \sum _{n=0}^{\infty }{D}_n^{-}}\left(x\right)y^n-y\left(D_0^{-}\left(x\right)+D_1^{-}\left(x\right)y\right)+x{y}^2{\displaystyle \sum _{n=0}^{\infty }{D}_n^{-}}\left(x\right)y^n\\ -x{y}^2{D}_0^{-}\left(x\right)+D_0^{-}\left(x\right)+D_1^{-}\left(x\right)y+D_2^{-}\left(x\right)y^2\\ =\left(y+x{y}^2\right){\displaystyle \sum _{n=0}^{\infty }{D}_n^{-}}\left(x\right)y^n+1+x{y}^2+x^2{y}^2.\end{array}$

推论3.9 当$n\ge 0$ 时，

$D_n^{-}\left(x\right)=\left({\displaystyle \sum _{k=0}^{\frac{n}{2}}\left(\begin{array}{c}n-k\\ k\end{array}\right)}+{\displaystyle \sum _{k=1}^{\frac{n}{2}}\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}+{\displaystyle \sum _{k=2}^{\frac{n}{2}+1}\left(\begin{array}{c}n-k\\ k-2\end{array}\right)}\right)x^k;$

利用二项式展开有如下证明。

证明

$\begin{array}{c}{\displaystyle \sum _{n\ge 0}{D}_n^{-}}\left(x\right)y^n=\frac{1+x{y}^2+x^2{y}^2}{1-y-x{y}^2}\\ =\left(1+x{y}^2+x^2{y}^2\right){\displaystyle \sum _{j\ge 0}{\left(y+x{y}^2\right)}^j}\\ ={\displaystyle \sum _{j\ge 0}{\left(y+x{y}^2\right)}^j}+x{y}^2{\displaystyle \sum _{j\ge 0}{\left(y+x{y}^2\right)}^j}+x^2{y}^2{\displaystyle \sum _{j\ge 0}{\left(y+x{y}^2\right)}^j}\\ ={\displaystyle \sum _{j\ge 0}{y}^j}{\left(1+xy\right)}^j+{\displaystyle \sum _{j\ge 0}x}{y}^{j+2}{\left(1+xy\right)}^j+{\displaystyle \sum _{j\ge 0}{x}^2}{y}^{j+2}{\left(1+xy\right)}^j\\ ={\displaystyle \sum _{j\ge 0}{\displaystyle \sum _{n-j=0}^j\left(\begin{array}{c}j\\ n-j\end{array}\right)x^{n-j}{y}^n}}+{\displaystyle \sum _{j\ge 0}{\displaystyle \sum _{n-j-2=0}^j\left(\begin{array}{c}j\\ n-j-2\end{array}\right)x^{n-j-1}{y}^n}}+{\displaystyle \sum _{j\ge 0}{\displaystyle \sum _{n-j-2=0}^j\left(\begin{array}{c}j\\ n-j-2\end{array}\right)x^{n-j}{y}^n}}\\ ={\displaystyle \sum _{n\ge 0}{\displaystyle \sum _{j=\frac{n}{2}}^n\left(\begin{array}{c}j\\ n-j\end{array}\right)x^{n-j}{y}^n}}+{\displaystyle \sum _{n\ge 0}{\displaystyle \sum _{j=\frac{n}{2}-1}^{n-2}\left(\begin{array}{c}j\\ n-j-2\end{array}\right)x^{n-j-1}{y}^n}}+{\displaystyle \sum _{n\ge 0}{\displaystyle \sum _{j=\frac{n}{2}-1}^{n-2}\left(\begin{array}{c}j\\ n-j-2\end{array}\right)x^{n-j}{y}^n}}\\ ={\displaystyle \sum _{n\ge 0}\left({\displaystyle \sum _{k=0}^{\frac{n}{2}}\left(\begin{array}{c}n-k\\ k\end{array}\right)}+{\displaystyle \sum _{k=1}^{\frac{n}{2}}\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}+{\displaystyle \sum _{k=2}^{\frac{n}{2}+1}\left(\begin{array}{c}n-k\\ k-2\end{array}\right)}\right)x^k{y}^n}.\end{array}$

且易得

$d_{n,k}^{-}=\left(\begin{array}{c}n-k\\ k\end{array}\right)+\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)+\left(\begin{array}{c}n-k\\ k-2\end{array}\right).$

注释2 因为在有限分配格$ℱ\left(P\right)$ 中，$d_{n,k}^{+}$ 和$d_{n,k}^{-}$ 都等于P中只有k个元素的极大反链的个数[12]，也就是说，$d_{n,k}^{+}=d_{n,k}^{-}$ ，所以出度多项式与入度多项式是相同的。

3) 出入度多项式

称如下计数多项式

$P\left({\Psi }_n\right):=P\left({\Psi }_n;x,y\right)={\displaystyle \sum _{i,j}{p}_{ij}}{x}^i{y}^j$

为${\Psi }_n$ 的出入度多项式，其中$p_{ij}$ 表示${{\Psi }^{\prime }}_n$ 中出度为i、入度为j的顶点个数。部分出入度多项式$P\left({\Psi }_n\right)$ 如下所示：

$\begin{array}{l}P\left({\Psi }_0\right)=1,\\ P\left({\Psi }_1\right)=x+y,\\ P\left({\Psi }_2\right)=x^2+2xy+y^2,\\ P\left({\Psi }_3\right)=x^2+y+2xy+x{y}^2,\\ P\left({\Psi }_4\right)=x^3+y+3x^{2}y+3x{y}^2+x{y}^3,\\ P\left({\Psi }_5\right)=x^3+xy+3x^{2}y+x^{3}y+y^2+3x{y}^2+2x^2{y}^2+x{y}^3+x^2{y}^3,\\ P\left({\Psi }_6\right)=x^4+xy+x^{2}y+4x^{3}y+y^2+3x{y}^2+5x^2{y}^2+x^3{y}^2+2x{y}^3+3x^2{y}^3+x^2{y}^4.\end{array}$ (1)

类似于图6的方式，在图4 ${\Psi }_n$ 的递归图中虚补一个${\Psi }_{n-4}$ ，之后用容斥原理就可得到如下结论。

命题3.10

当$n\ge 6$ 时，

$P\left({\Psi }_n\right)=\{\begin{array}{l}x\left(y+1\right)P\left({\Psi }_{n-2}\right)+yP\left({\Psi }_{n-3}\right)+xy\left(1-x\right)P\left({\Psi }_{n-4}\right),若n为偶数,\\ y\left(x+1\right)P\left({\Psi }_{n-2}\right)+xP\left({\Psi }_{n-3}\right)+xy\left(1-y\right)P\left({\Psi }_{n-4}\right),若n为奇数.\end{array}$

令$A_m\left(x,y\right)=P\left({\Psi }_{2m};x,y\right)$ ，$B_m\left(x,y\right)=P\left({\Psi }_{2m+1};x,y\right)$ ，则

$\{\begin{array}{l}{A}_m\left(x,y\right)=x\left(y+1\right)A_{m-1}\left(x,y\right)+y{B}_{m-2}\left(x,y\right)+xy\left(1-x\right)A_{m-2}\left(x,y\right),\left(m\ge 3\right),\\ B_m\left(x,y\right)=y\left(x+1\right)B_{m-1}\left(x,y\right)+x{A}_{m-1}\left(x,y\right)+xy\left(1-y\right)B_{m-2}\left(x,y\right),\left(m\ge 3\right).\end{array}$

命题3.11 当$m\ge 5$ 时，

$\{\begin{array}{l}{A}_m=\left(2xy+x+y\right)A_{m-1}-xy\left(xy+2x+2y-1\right)A_{m-2}+xy\left(x^{2}y+x{y}^2-x-y+1\right)A_{m-3}\\ -x^2{y}^2\left(1-x\right)\left(1-y\right)A_{m-4}\\ B_m=\left(2xy+x+y\right)B_{m-1}-xy\left(xy+2x+2y-1\right)B_{m-2}+xy\left(x^{2}y+x{y}^2-x-y+1\right)B_{m-3}\\ -x^2{y}^2(1-x)(1-y)B_{m-4}.\end{array}$

证明 由命题3.10，当$m\ge 3$ 时，

$\begin{array}{c}x{A}_{m-1}=B_m-\left(x+1\right)y{B}_{m-1}-xy\left(1-y\right)B_{m-2}\\ =\frac{A_{m+2}-x\left(y+1\right)A_{m+1}-x\left(1-x\right)y{A}_m}{y}-\frac{\left(x+1\right)y\left(A_{m+1}-x\left(y+1\right)A_m-x\left(1-x\right)y{A}_{m-1}\right)}{y}\\ -\frac{xy\left(1-y\right)\left(A_m-x\left(y+1\right)A_{m-1}-x\left(1-x\right)y{A}_{m-2}\right)}{y}\\ =\frac{A_{m+2}-\left(2xy+x+y\right)A_{m+1}+xy\left(xy+2x+2y-1\right)A_m}{y}\\ +\frac{xy(x+y-x^{2}y-x{y}^2)A_{m-1}+x^2{y}^2\left(1-x\right)\left(1-y\right)A_{m-2}}{y}\end{array}$

因此

$\begin{array}{c}{A}_{m+2}=\left(2xy+x+y\right)A_{m+1}-xy\left(xy+2x+2y-1\right)A_m+xy\left(x^{2}y+x{y}^2-x-y+1\right)A_{m-1}\\ -x^2{y}^2\left(1-x\right)\left(1-y\right)A_{m-2}.\end{array}$

所以，当$m\ge 5$ 时，

$\begin{array}{c}{A}_m=\left(2xy+x+y\right)A_{m-1}-xy\left(xy+2x+2y-1\right)A_{m-2}+xy\left(x^{2}y+x{y}^2-x-y+1\right)A_{m-3}\\ -x^2{y}^2\left(1-x\right)\left(1-y\right)A_{m-4}.\end{array}$

类似地，可以得到$B_m$ 的递推关系。

由命题3.11，可以得到$P\left({\Psi }_n\right)$ 的递推公式。

定理3.12 当$n\ge 10$ 时，

$\begin{array}{c}P\left({\Psi }_n\right)=\left(2xy+x+y\right)P\left({\Psi }_{n-2}\right)-xy\left(xy+2x+2y-1\right)P\left({\Psi }_{n-4}\right)\\ +xy\left(x^{2}y+x{y}^2-x-y+1\right)P\left({\Psi }_{n-6}\right)-x^2{y}^2(1-x)(1-y)P\left({\Psi }_{n-8}\right).\end{array}$

根据定理3.12可以得到$P\left({\Psi }_n\right)$ 的生成函数。

定理3.13 $P\left({\Psi }_n\right)$ 的生成函数为：

${\displaystyle \sum _{n\ge 0}P}\left({\Psi }_n\right)t^n=\frac{N\left(x,y,t\right)}{D\left(x,y,t\right)},$

其中，

$\begin{array}{l}N\left(x,y,t\right)=1+\left(x+y\right)t-\left(x^2-x+xy-y+y^2\right)t^2-\left(x^{2}y-y+y^2\right)t^3\\ -\left(xy\left(1-x+x^2-y+2xy\right)+y\left(y^2-1\right)\right)t^4+xy\left(-x+x^2-y+xy+y^2\right)t^5\\ +xy\left(x-1\right)\left(y-1\right)\left(x+2y-1\right)t^6-xy\left(x-1\right)\left(y-1\right)\left(x+y-1\right)t^7\\ D\left(x,y,t\right)=1-\left(x+y+xy\right)t^2-xy\left(1-x-y\right)t^4-xy\left(x-1\right)\left(y-1\right)t^6\end{array}$

证明 由命题3.10和1)，我们有：

$\begin{array}{c}{\displaystyle \sum _{n\ge 0}P}\left({\Psi }_n\right)t^n={\displaystyle \sum _{n\ge 10}P}\left({\Psi }_n\right)t^n+{\displaystyle \sum _{n=0}^{9}P}\left({\Psi }_n\right)t^n\\ ={\displaystyle \sum _{n\ge 10}(\left(2xy+x+y\right)P\left({\Psi }_{n-2}\right)-xy\left(xy+2x+2y-1\right)P\left({\Psi }_{n-4}\right)}\\ \text{}+xy\left(x^{2}y+x{y}^2-x-y+1\right)P\left({\Psi }_{n-6}\right)-x^2{y}^2\left(1-x\right)\left(1-y\right)P\left({\Psi }_{n-8}\right))t^n+{\displaystyle \sum _{n=0}^{9}P}\left({\Gamma }_n\right)t^n\\ =(\left(2xy+x+y\right)t^2-xy\left(xy+2x+2y-1\right)t^4+xy\left(x{y}^2+x^{2}y-x-y+1\right)t^6\\ -x^2{y}^2\left(1-x\right)\left(1-y\right)t^8){\displaystyle \sum _{n\ge 0}P}\left({\Psi }_n\right)t^n-\left(2xy+x+y\right)t^2{\displaystyle \sum _{n=0}^{7}P}\left({\Psi }_n\right)t^n\\ +xy\left(xy+2x+2y-1\right)t^4{\displaystyle \sum _{n=0}^{5}P}\left({\Psi }_n\right)t^n-xy\left(x^{2}y+x{y}^2-x-y+1\right)t^6{\displaystyle \sum _{n=0}^{3}P}\left({\Psi }_n\right)t^n\\ +x^2{y}^2\left(1-x\right)\left(1-y\right)t^8{\displaystyle \sum _{n=0}^{1}P}\left({\Psi }_n\right)t^n+{\displaystyle \sum _{n=0}^{9}P}\left({\Psi }_n\right)t^n\\ =(\left(2xy+x+y\right)t^2-xy\left(xy+2x+2y-1\right)t^4+xy\left(x{y}^2+x^{2}y-x-y+1\right)t^6\\ -x^2{y}^2\left(1-x\right)\left(1-y\right)t^8){\displaystyle \sum _{n\ge 0}P}\left({\Psi }_n\right)t^n+1+\left(x+y\right)t+\left(x^2-x-y+y^2\right)t^2\\ +\left(y-2x^{2}y-y^2-x{y}^2\right)t^3+\left(y-y^3+xy\left(-1+2x-2x^2+2y-3xy-y^2\right)\right)t^4\\ +xy\left(-x+x^2-2y+xy+x^{2}y+2y^2\right)t^5\\ +xy\left(-1+2x-x^2+2y-3xy+x^{3}y-2y^2+x{y}^2+2x^2{y}^2+y^3\right)t^6\\ +xy\left(1-2x+x^2-2y+3xy-x^{3}y+y^2-x^2{y}^2-x{y}^3\right)t^7\\ +x^2{y}^2\left(1-2x+x^2-3y+4xy-x^{2}y+2y^2-2x{y}^2\right)t^8\\ +x^2{y}^2\left(-1+2x-x^2+2y-3xy+x^{2}y-y^2+x{y}^2\right)t^9\end{array}$

由定理3.13中生成函数的分母$D\left(x,y,t\right)=1-\left(x+y+xy\right)t^2-xy\left(1-x-y\right)t^4-xy\left(x-1\right)\left(y-1\right)t^6$ ，我们可以得到$P\left({\Psi }_n\right)$ 的另外一个递推关系。

推论3.14 当$n\ge 6$ ，

$P\left({\Psi }_n\right)=\left(x+y+xy\right)P\left({\Psi }_{n-2}\right)+xy\left(1-x-y\right)P\left({\Psi }_{n-4}\right)+xy\left(x-1\right)\left(y-1\right)P\left({\Psi }_{n-6}\right).$

注释3 出入度多项式是综合出度和入度的一个二元多项式，度序列多项式、出度多项式和入度多项式是其特殊形式。分析出入度多项式$P\left({\Psi }_n;x,y\right)={\displaystyle \sum _{i,j}{p}_{ij}}{x}^i{y}^j$ ，当$y=x$ 时，此时$p_{ij}$ 表示${\Psi }_n$ 中度为$i+j$ 的顶点个数；当$x=1$ 时，此时$y^j$ 前面的系数${\displaystyle \sum _{i\ge 0}{p}_{ij}}$ 表示${\Psi }_n$ 中出度为j的顶点个数；当$y=1$ 时，此时$x^i$ 前面的系数${\displaystyle \sum _{j\ge 0}{p}_{ij}}$ 表示${\Psi }_n$ 中入度为i的顶点个数。由此可知，$P\left({\Psi }_n;x,1\right)$ 、$P\left({\Psi }_n;1,x\right)$ 、$P\left({\Psi }_n;x,x\right)$ 和$P\left({\Psi }_n;1,1\right)$ 分别是${\Psi }_n$ 的出度多项式、入度多项式、度多项式和顶点个数。这就给了我们一种得到定理3.3和定理3.8的新方式，同时也检验了前后所得结论的一致性。

斐波那契立方体的研究具有重要的应用价值，尤其在实现常见的系统通信源语方面。我们新建立的斐波那契相似立方体在性质和结构方面都与斐波那契立方体有很强大的关联，下一步期待能将我们得到的立方体，尤其是有向立方体的相关性质与容错计算、系统通信源语等方面联系起来。

基金项目

国家自然科学基金(12161081)。

NOTES

^*通讯作者。