“X”型梯状图和“T”型梯状图的反强迫多项式

The Anti-Forcing Polynomials of “X” Type and “T” Type Ladderlike Graphs

摘要: 通过某个顶点关联边的匹配情况分类计算梯子图的部分反强迫多项式，进而根据对完美匹配进行分类和图的分解，得到了“X”型梯状图和“T”型梯状图的反强迫多项式。

Abstract: The partial anti-forcing polynomials are calculated by the matching classification of a vertex associated edge in a ladder graph, and then the anti-force polynomials of the “X” type and the “T” type ladderlike graphs are obtained.

1. 引言

反强迫数的研究始于六角系统中凯库勒结构(即完美匹配)的外自由度。早在1997年李学良就已经研究了反强迫数等于1，即有强迫单边的六角系统 [1]。Vukiěević和Trinajstić首次提出反强迫数的概念 [2]，即从图中删边使得剩余子图有唯一完美匹配的删除的最少边数称图的反强迫数；他们还给出了苯类化合物 [2] 和cata-型六角系统 [3] 的反强迫数。雷洪川，叶永南，张和平等首次引入了图的完美匹配的反强迫数的概念 [4]，从图G中删除完美匹配M以外的边使得M是剩余子图的唯一完美匹配，删除的最少边数称图G的完美匹配M的反强迫数。邓汉元给出了六角链和双六角链系统的反强迫数 [5] [6]。张倩倩等人证明了cata-亚苯基系统的反强迫数等于该系统中六角形的个数 [7]。蒋晓艳等人得到了硼氮富勒烯图的反强迫数 [8]。杨琴证明了富勒烯图的反强迫数 [9]。反强迫集的概念是由Klein和Rosenfeld提出的 [10]，具体定义为从图G中删除完美匹配M以外的边使得M是剩余子图的唯一完美匹配，删除的边集合称作图G完美匹配M的反强迫集，而M的反强迫数是其最小的反强迫集的大小。图的所有完美匹配的反强迫数的集合称为图的反强迫谱。如果反强迫谱是一个整数区间，则称反强迫谱是连续的。邓凯、张和平等证明了卡塔型六角系统和偶多边形链的反强迫谱是连续的 [11]，还证明了两种类型的可构造六角系统的反强迫谱是连续的，其中包括具有强迫单边的六角系统 [12]。石玲娟研究了超立方图的反强迫谱以及(3,6)-富勒烯图的反强迫数 [13]。为了考虑具有相同反强迫数的完美匹配的个数，Hwang等人引入了反强迫多项式的概念 [14]。赵爽、张和平等得到了具有强迫边的苯基系统、平行四边形六角系统、cata-型六角系统以及一些格子图的完美匹配的反强迫多项式 [15] [16]。姚海元、王杰彬、韩振云等得到了几类梯子图以及变形梯子图完美匹配的反强迫细谱(等价于反强迫多项式)及其和卢卡斯数列、斐波那契数列之间的一些等式，从而给出了这2个数列的一些组合解释 [17] [18] [19]。近几年，尽管关于图的反强迫多项式的研究有了一些结果，但是总的来说计算方面的成果还非常少。

本文引言后的第1小节介绍了图的反强迫多项式及其根据某一顶点关联的边的分解定理等预备知识。第2小节主要是计算了梯子图的包含某特殊边的完美匹配的部分反强迫多项式。第3小节首先引入了“X”型梯状图及其退化情况“T”型梯状图的定义，其次根据“X”型梯状图的结构特点，将其完美匹配进行分类，并进一步将各类情况的反强迫多项式分解为若干梯子图的反强迫多项式之和，然后借助梯子图的剖部分及完整反强迫多项式求出了每一类完美匹配的反强迫多项式，从而得到了“X”型梯状图及“T”型梯状图的反强迫多项式。最后还给出了一些特殊梯状图的完美匹配数与Fibonacci数相关的序列之间的关系。

2. 预备知识

设图G是一个简单图， $\mathcal{M}=\mathcal{M}\left(G\right)$ 是其所有完美匹配构成的集合。设 $M\in \mathcal{M}\left(G\right)$ 是G的一个完美匹配， $S\subseteq E\left(G\right)\backslash M$，若M是 $G-S$ 的唯一完美匹配，则称S为M的一个反强迫集。M的最小反强迫集的大小称为M的反强迫数，记为 $af\left(G,M\right)$。图G的(最小)反强迫数是一个整体概念，其值等于G中所有完美匹配反强迫数的最小值，记为 $af\left(G\right)$。类似的，图G的所有完美匹配的最大反强迫数的最大值叫做G的最大反强迫数，记为 $Af\left(G\right)$。设 $\mathcal{A}$ 是G中M-交错圈组成的集合。若 $\mathcal{A}$ 中任意两个M-交错圈不交或仅交于M中的边，我们称 $\mathcal{A}$ 是一个相容M-交错集。图G的最大相容M-交错集的大小，即包含的M-交错圈的个数，记为 $c^{\prime }\left(M\right)$。

引理1 [4]：若M是图G的一个完美匹配，则 $af\left(G,M\right)\ge c^{\prime }\left(M\right)$。特别若图G是平面二部图，则

$af\left(G,M\right)=c^{\prime }\left(M\right).$

定义1 [14] [15]：图G的反强迫多项式是一个有如下形式的计数多项式：

$P\left(G,x\right)={\displaystyle \underset{M\in \mathcal{M}}{\sum }{x}^{af\left(G,M\right)}}.$

实际上，若记 $k_i$ 是G的反强迫数为 $af\left(G,M\right)=i$ 的完美匹配的个数，则经过简单的合并同类项有

$P\left(G,x\right)={\displaystyle \underset{i=0}{\overset{Af\left(G\right)}{\sum }}{k}_i{x}^i}.$

若G没有完美匹配，则 $P\left(G,x\right)=0$；若G有唯一的完美匹配，则 $P\left(G,x\right)=1$。特别地，对空图我们有 $P\left(G,x\right)=1$。

Fibonacci数列 $F\left(n\right)$ 是以 $F\left(0\right)=0,F\left(1\right)=1$ 为初始值， $F\left(n\right)=F\left(n-1\right)+F\left(n-2\right)$ 为递推公式的序列(注，文献 [21] 中的定义其初始值与标准定义相差一位)。

引理2 [20] [21]：Fibonacci数 $F\left(n\right)$ 等于杨辉矩阵中与主对角线垂直的第n条斜线上诸元素之和，即

$F\left(n+1\right)={\displaystyle \underset{i=0}{\overset{n}{\sum }}\left(\begin{array}{c}n-i\\ i\end{array}\right)}.$

定理1：设 $\mathcal{M}$ 是图G的所有完美匹配构成的集合，若G的顶点u关联t条边 $e_1,e_2,\cdots ,e_t$，则G的反强迫多项式有如下分解式

$P\left(G,x\right)={\displaystyle \underset{i=1}{\overset{t}{\sum }}{\displaystyle \underset{\begin{array}{l}M\in \mathcal{M}\\ e_i\in M\end{array}}{\sum }{x}^{af\left(G,M\right)}}}.$

证明 我们将图G的完美匹配按其所含的顶点u关联的t条边 $e_1,e_2,\cdots ,e_t$ 进行分类有

$P\left(G,x\right)={\displaystyle \underset{M\in \mathcal{M}\left(G\right)}{\sum }{x}^{af\left(G,M\right)}}={\displaystyle \underset{i=1}{\overset{t}{\sum }}{\displaystyle \underset{\begin{array}{l}M\in \mathcal{M}\\ e_i\in M\end{array}}{\sum }{x}^{af\left(G,M\right)}}}.$

定理得证。

3. 梯子图的反强迫多项式

定义2梯子图 $L_n$ 是路 $P_n$ 和 $P_2$ 的笛卡尔积，即 $L_n=P_n\times P_2$。

通常，我们把一个梯子图 $L_n=P_n\times P_2$ 水平放置(如图1所示)，其顶点从上到下、从左到右依次记为 $a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_n$，其中 $a_i{b}_i$ 称为竖直边， $a_i{a}_{i+1}$ 称为水平边，相应地匹配中的边分别称为竖直匹配边和水平匹配边。

定理2 [15] [17]：梯子图 $L_n\left(n\ge 1\right)$ 的反强迫多项式为

$P\left(L_n,x\right)={\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-q\\ q\end{array}\right)x^{n-q-1}}+\delta \left(n\right)={\displaystyle \underset{t=\lfloor \frac{n}{2}\rfloor }{\overset{n-1}{\sum }}\left(\begin{array}{c}t+1\\ n-t-1\end{array}\right)x^t}+\delta \left(n\right).$

Figure 1. Ladder graphs L_n

图1. 梯子图L_n

其中，若n为奇数则 $\delta \left(n\right)=0$，若n为偶数则 $\delta \left(n\right)=x^{\frac{n}{2}}$。

这里我们记 ${\mathcal{M}}_i$ 是 $L_n$ 的包含第i条竖直边 $a_i{b}_i$ 的完美匹配的集合， $1\le i\le n$。记 $M_i^{\ast }$ 是 $L_n$ 的包含第i条水平边 $a_i{a}_{i+1}$ 的完美匹配的集合， $1\le i\le n-1$。

定理3：我们有部分反强迫多项式

$P_1\left(L_n,x\right):={\displaystyle \underset{M\in {\mathcal{M}}_1}{\sum }{x}^{af\left(G,M\right)}}=\{\begin{array}{l}0,n=0\\ 1,n=1\\ xP\left(L_{n-1},x\right),n\ge 2为偶数\\ xP\left(L_{n-1},x\right)-x^{\frac{n+1}{2}}+x^{\frac{n-1}{2}},n\ge 3为奇数\end{array}$

由定理2可以得出以下结论。

推论1：我们有部分反强迫多项式

$P_1\left(L_n,x\right)={\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-1}}.$

定理4：我们有部分反强迫多项式

$P_1^{\ast }\left(L_n,x\right):={\displaystyle \underset{M\in {\mathcal{M}}_1^{\ast }}{\sum }{x}^{af\left(G,M\right)}}=\{\begin{array}{l}1,n=0\\ 0,n=1\\ xP\left(L_{n-2},x\right),n\ge 2\end{array}$

推论2：我们有部分反强迫多项式

$P_1^{\ast }\left(L_n,x\right)={\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)x^{n-q-2}}+\delta \left(n\right).$

由定理3和定理4，就可以得出 $L_n$ 的反强迫多项式关于顶点 $a_1$ 关联边的匹配情况的分解表达式。

推论3： $L_n$ 的反强迫多项式满足如下递推关系

$P\left(L_n,x\right)=\{\begin{array}{l}P\left(L_0,x\right)=1,n=0\\ P\left(L_1,x\right)=1,n=1\\ P_1\left(L_n,x\right)+P_1^{\ast }\left(L_n,x\right)=xP\left(L_{n-1},x\right)+xP\left(L_{n-2},x\right)+\xi \left(n\right),n\ge 2\end{array}$

其中 $\xi \left(n\right)=x^{\frac{n-1}{2}}-x^{\frac{n+1}{2}}$，若n为奇数； $\xi \left(n\right)=0$，若n为偶数。

定理5：我们有部分反强迫多项式

$P_i^{\ast }\left(L_n,x\right):={\displaystyle \underset{M\in {\mathcal{M}}_i^{\ast }}{\sum }{x}^{af\left(G,M\right)}}=\{\begin{array}{l}{x}^{2}P\left(L_{i-1},x\right)P\left(L_{n-i-1},x\right),n为偶数,i为偶数\\ x^2\left(P\left(L_{i-1},x\right)-x^{\frac{i-1}{2}}\right)\left(P\left(L_{n-i-1},x\right)-x^{\frac{n-i-1}{2}}\right)+x^{\frac{i}{2}}\left(P\left(L_{n-i-1},x\right)-x^{\frac{n-i-1}{2}}\right)\\ +x^{\frac{n-i}{2}}\left(P\left(L_{i-1},x\right)-x^{\frac{i-1}{2}}\right)+x^{\frac{n}{2}},n为偶数,i为奇数\text{;}\\ x^{2}P\left(L_{i-1},x\right)P\left(L_{n-i-1},x\right)+\left(x-x^2\right)x^{\frac{n-i-1}{2}}P\left(L_{i-1},x\right),n为奇数,i为偶数\text{;}\\ x^{2}P\left(L_{i-1},x\right)P\left(L_{n-i-1},x\right)+\left(x-x^2\right)x^{\frac{i-1}{2}}P\left(L_{n-i-1},x\right),n为奇数,i为奇数\text{.}\end{array}$

证明：设M是 $L_n$ 的包含第i条水平边 $a_i{a}_{i+1}$ 的完美匹配，由文献 [17] 中引理6的证明过程可知：

情形1：当n为偶数，i为偶数时，交错4-圈两边一定会有竖直匹配边，此时会多出一个与交错4-圈相容的交错圈使得反强迫数增加一，也就是反强迫多项式多乘一个x，这时直接从交错4-圈处断开，交错4-圈独占一段即多项式的另一x，左右两边各一段，则有

$x^{2}P\left(L_{i-1},x\right)P\left(L_{n-i-1},x\right).$

情形2：当n为偶数，i为奇数时，当交错4-圈两边都有竖直匹配边，则有

$x^2\left(P\left(L_{i-1},x\right)-x^{\frac{i-1}{2}}\right)\left(P\left(L_{n-i-1},x\right)-x^{\frac{n-i-1}{2}}\right);$

当交错4-圈或左、或右有竖直匹配边，此时不存在与所有4-圈都是M-相容的交错圈，所以反强迫数不变，则有

$x{x}^{\frac{i-1}{2}}\left(P\left(L_{n-i-1},x\right)-x^{\frac{n-i-1}{2}}\right)+x{x}^{\frac{n-i-1}{2}}\left(P\left(L_{i-1},x\right)-x^{\frac{i-1}{2}}\right);$

当交错4-圈两边都没有竖直匹配边，此时反强迫数为 $\frac{n}{2}$，则有项 $x^{\frac{n}{2}}$。

n为奇数时证明情况类似。

推论4：由定理5有以下关系式成立

$\begin{array}{l}{P}_j^{\ast }\left(L_n,x\right)=P_{n-j}^{\ast }\left(L_n,x\right);\\ P_2^{\ast }\left(L_n,x\right)=x{P}_1\left(L_{n-2},x\right);\\ P_3^{\ast }\left(L_n,x\right)=x{P}_1^{\ast }\left(L_{n-2},x\right)+x^2{P}_1\left(L_{n-3},x\right)=x^{2}P\left(L_{n-4},x\right)+x^2{P}_1\left(L_{n-3},x\right)\\ =x^{2}P\left(L_{n-4},x\right)+x{P}_2^{\ast }\left(L_{n-1},x\right)=x{P}_1^{\ast }\left(L_{n-2},x\right)+x{P}_2^{\ast }\left(L_{n-1},x\right)\end{array}$

定理6：我们有部分反强迫多项式

$\begin{array}{l}{P}_i\left(L_n,x\right):={\displaystyle \underset{M\in {\mathcal{M}}_i}{\sum }{x}^{af\left(G,M\right)}}=P_1\left(L_i,x\right)P_1\left(L_{n+1-i},x\right)\\ =\{\begin{array}{l}{x}^{2}P\left(L_{i-1},x\right)\left[xP\left(L_{n-i},x\right)-x^{\frac{n-i+2}{2}}+x^{\frac{n-i}{2}}\right],n为偶数,i为偶数\text{;}\\ x\left[xP\left(L_{i-1},x\right)-x^{\frac{i+1}{2}}+x^{\frac{i-1}{2}}\right]P\left(L_{n-i-1},x\right),n为偶数,i为奇数;\\ x^{2}P\left(L_{i-1},x\right)P\left(L_{n-i-1},x\right),n为奇数,i为偶数\text{;}\\ \left[xP\left(L_{i-1},x\right)-x^{\frac{i+1}{2}}+x^{\frac{i-1}{2}}\right]\left[xP\left(L_{n-i},x\right)-x^{\frac{n-i+2}{2}}+x^{\frac{n-i}{2}}\right],n为奇数,i为奇数\text{.}\end{array}\end{array}$

证明：设M是 $L_n$ 的包含第i条竖直边 $a_i{b}_i$ 的完美匹配。由文献 [17] 中分解定理知，我们可以将图从第i条竖直边 $a_i{b}_i$ 处分解成 $L^{\left(1\right)}=L_i$ 和 $L^{\left(2\right)}=L_{n+1-i}$， $L^{\left(1\right)}\cap L^{\left(2\right)}=\left\{a_i{b}_i\right\}$， $M_1$， $M_2$ 是 $L^{\left(1\right)}$ 和 $L^{\left(2\right)}$ 的完美匹配， $M_1\cap M_2=\left\{a_i{b}_i\right\}$， $M_1\cup M_2=M$。有 $af\left(M\right)=af\left(M_1\right)+af\left(M_2\right)$。则

$\begin{array}{c}{P}_i\left(L_n,x\right)={\displaystyle \underset{M\in {\mathcal{M}}_i}{\sum }{x}^{af\left(L_n,M\right)}}={\displaystyle \underset{\begin{array}{l}{M}_1\in \mathcal{M}\left(L_i\right),a_i{b}_i\in M_1\\ M_2\in \mathcal{M}\left(L_{n+1-i}\right),a_i{b}_i\in M_2\end{array}}{\sum }{x}^{af\left(L_i,M_1\right)+af\left(L_{n+1-i},M_2\right)}}\\ ={\displaystyle \underset{M_1\in \mathcal{M}\left(L_i\right),a_i{b}_i\in M_1}{\sum }{x}^{af\left(L_i,M_1\right)}}{\displaystyle \underset{M_2\in \mathcal{M}\left(L_{n+1-i}\right),a_i{b}_i\in M_2}{\sum }{x}^{af\left(L_{n+1-i},M_2\right)}}\\ =P_1\left(L_i,x\right)P_1\left(L_{n+1-i},x\right)\end{array}$

4. “X”型梯状图和“T”型梯状图的反强迫多项式

定义3：将一个梯子图水平放置，从梯子图内部某个方格子(称分叉方格子)处向与梯子图上下方向各延伸出一个梯子图，记从交叉方格子处，向上、向左、向右、向下分别有 $n_1,n_2,n_3,n_{\text{4}}$ 个方格子，我们把这样得到的方格子图称为“X”型梯状图(如图2所示)，记为 $X{L}_{n_1,n_2,n_3,n_4}$。

Figure 2. “X” type ladderlike graph $X{L}_{n_1,n_2,n_3,n_4}$

图2. “X”型梯状图 $X{L}_{n_1,n_2,n_3,n_4}$

我们称从交叉方格子处向上、向左、向右、向下方向的边中与虚线相交的边均为竖直边，在完美匹配中的竖直边称为竖直匹配边；其余边为水平边，在完美匹配中的水平边称为水平匹配边。

定义4：当“X”型梯状图的 $n_4=1$ 时，我们把这样的退化“X”型梯状图称为“T”型梯状图(如图3所示)，记为 $T{L}_{n_1,n_2,n_3}=X{L}_{n_1,n_2,n_3,1}$。

引理3：若M是 $X{L}_{n_1,n_2,n_3,n_4}$ 或 $T{L}_{n_1,n_2,n_3}$ 的完美匹配，则其水平匹配边必成对出现，即(非交叉)方格子中的两条相对水平边同时在M中。

证明：设M是 $X{L}_{n_1,n_2,n_3,n_4}$ 的完美匹配，若 $X{L}_{n_1,n_2,n_3,n_4}$ 的某一对水平边 $e\in M,e^{\prime }\notin M$，则整个图无竖直匹配边且至少存在两个M-非饱和的点，与M是 $X{L}_{n_1,n_2,n_3,n_4}$ 的完美匹配矛盾，所以 $e\in M$ 时必有与其相对应的 $e^{\prime }\in M$。

Figure 3. “T” type ladderlike graph $T{L}_{n_1,n_2,n_3}$

图3. “T”型梯状图 $T{L}_{n_1,n_2,n_3}$

因 $X{L}_{n_1,n_2,n_3,n_4}$ 是平面二部图，由引理1易知有下面的结论。

引理4：若G是方格子链 $X{L}_{n_1,n_2,n_3,n_4}$ 或 $T{L}_{n_1,n_2,n_3}$，M是G的完美匹配，水平边 $e\notin M$，若存在G的最大M-相容交错集使其中的所有M-交错圈都不包含边e，则我们就可以从该方格子将G分解开来，即从G中删去边e和对边 $e^{\prime }$，不妨记分解得到的图为 $G_1,G_2$， $M\cap E\left(G_1\right)=M_1$， $M\cap E\left(G_2\right)=M_2$，则有

$af\left(G,M\right)=af\left(G_1,M_1\right)+af\left(G_2,M_2\right)$

我们可以对交叉方格子的四个顶点，多次应用定理1，从而将 $X{L}_{n_1,n_2,n_3,n_4}$ 的完美匹配分为8小类(如图4所示)：

(a) (b) (c) (d)(e) (f) (g) (h)

Figure 4. The 8 small class matching method of $X{L}_{n_1,n_2,n_3,n_4}$

图4. $X{L}_{n_1,n_2,n_3,n_4}$ 的8小类匹配方式

其中，(b)可以通过旋转得到(a)，同样(c)可以由(d)、(e)、(f)得到，(g)可以由(h)得到，因此我们将八小类匹配通过旋转得到3类，记(a)、(b)为类型1，(c)、(d)、(e)、(f)为类型2，(g)、(h)为类型3。

易知， $T{L}_{n_1,n_2,n_3}$ 的完美匹配分为6小类(如图5所示)：

(a)(b) (c)(d)(e) (f)

Figure 5. The 6 small class matching method of $T{L}_{n_1,n_2,n_3}$

图5. $T{L}_{n_1,n_2,n_3}$ 的6小类匹配方式

其中，(a)、(b)为类型1，(c)、(d)、(e)为类型2，(f)为类型3。

定理7： $X{L}_{n_1,n_2,n_3,n_4}$ 的反强迫多项式满足

$\begin{array}{l}P\left(X{L}_{n_1,n_2,n_3,n_4},x\right)={\displaystyle \underset{i=1}{\overset{4}{\sum }}{\displaystyle \underset{\begin{array}{l}M\in \mathcal{M}\\ e_i\in M\end{array}}{\sum }{x}^{af\left(X{L}_{n_1,n_2,n_3,n_4},M\right)}}}=P_{n_2}^{\ast }\left(L_{n_2+n_3},x\right)P_1\left(L_{n_1},x\right)P_1\left(L_{n_4},x\right)\\ +P_{n_1}^{\ast }\left(L_{n_1+n_4},x\right)P_1\left(L_{n_2},x\right)P_1\left(L_{n_3},x\right)+xP\left(L_{n_1-1},x\right)P\left(L_{n_4-1},x\right)P_1\left(L_{n_2},x\right)P_1\left(L_{n_3-1},x\right)\\ +xP\left(L_{n_1-1},x\right)P\left(L_{n_4-1},x\right)P_1\left(L_{n_2},x\right)P_1\left(L_{n_3-1},x\right)+xP\left(L_{n_1-1},x\right)P\left(L_{n_4-1},x\right)P_1\left(L_{n_2-1},x\right)P_1\left(L_{n_3},x\right)\\ +xP\left(L_{n_1-1},x\right)P\left(L_{n_4-1},x\right)P_1\left(L_{n_2-1},x\right)P_1\left(L_{n_3},x\right)+xP\left(L_{n_2-1},x\right)P\left(L_{n_3-1},x\right)P_1\left(L_{n_1-1},x\right)P_1\left(L_{n_4},x\right)\\ +x{P}_{n_2-1}^{\ast }\left(L_{n_2+n_3-2},x\right)P_{af}\left(L_{n_1-1},x\right)P_{af}\left(L_{n_4-1},x\right)+x{P}_{n_1-1}^{\ast }\left(L_{n_1+n_4-2},x\right)P\left(L_{n_2-1},x\right)P\left(L_{n_3-1},x\right)\end{array}$

证明：根据前面的分类情况，分别计算 $X{L}_{n_1,n_2,n_3,n_4}$ 的三种类型的反强迫多项式，然后按照旋转方式适当调整一下参数的下标即可。称一个匹配交错圈跨过一个方格子，若该匹配交错圈恰包含该方格子上的两条边。

情形1：不妨设完美匹配方式如图6，此时存在水平方向跨过交叉方格子且与交叉方格子相容的M-交错圈，不存在以其他方式跨过交叉方格子的M-交错圈，因此根据引理4有以下分解(这里我们用图本身来表示其反强迫多项式，下同)

Figure 6. A breakdown diagram of $X{L}_{n_1,n_2,n_3,n_4}$ when there is a Type 1 match

图6. 具有类型1匹配时的 $X{L}_{n_1,n_2,n_3,n_4}$ 分解示意图

故而有

$P_{n_2}^{\ast }\left(L_{n_2+n_3},x\right)P_1\left(L_{n_1},x\right)P_1\left(L_{n_4},x\right).$

情形2：不妨设完美匹配方式如图7，此时不存在以任何跨过交叉方格子的M-交错圈(但可能包含交叉方格子的3条或4条边)，故根据引理4有以下分解

Figure 7. A breakdown diagram of $X{L}_{n_1,n_2,n_3,n_4}$ when there is a Type 2 match

图7. 具有类型2匹配时 $X{L}_{n_1,n_2,n_3,n_4}$ 的分解示意图

故而有

$xP\left(L_{n_1-1},x\right)P\left(L_{n_4-1},x\right)P_1\left(L_{n_2},x\right)P_1\left(L_{n_3-1},x\right).$

情形3：不妨设完美匹配方式如图8，此时存在竖直方向跨过交叉方格子且与交叉方格子相容的M-交错圈，不存在以任何跨过交叉方格子的M-交错圈，故根据引理4有以下分解

Figure 8. A breakdown diagram of $X{L}_{n_1,n_2,n_3,n_4}$ when there is a Type 3 match

图8. 具有类型3匹配时 $X{L}_{n_1,n_2,n_3,n_4}$ 的分解示意图

故而有

$x{P}_{n_1-1}^{\ast }\left(L_{n_1+n_4-2},x\right)P\left(L_{n_2-1},x\right)P\left(L_{n_3-1},x\right).$

综上，定理得证。

特别的，当 $n_1=n_2=n_3=n_4=n$ 时，有

推论5： $X{L}_{n,n,n,n}$ 的反强迫多项式满足

$P\left(X{L}_{n,n,n,n},x\right)=\{\begin{array}{l}2{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-1}}\right]}^4+4x{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-2}}\right]}^2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-1}}\right]\\ \left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)x^{n-q-2}}\right]+2x\left[{\left[x^2{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)x^{n-q-3}}\right]}^2+2x^{\frac{n}{2}}\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)x^{n-q-3}}\right]+x^{n-1}\right]\\ {\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-2}}\right]}^2,n为偶数;\\ 2\left[x^2{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-2}}\right]}^2+2x^{\frac{n+1}{2}}\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-2}}\right]+x^n\right]{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-1}}\right]}^2\\ +4x{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-2}+x^{\frac{n-1}{2}}}\right]}^2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-1}}\right]\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)x^{n-q-2}}\right]\\ +2x^3{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)x^{n-q-3}}\right]}^2{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)x^{n-q-2}+x^{\frac{n-1}{2}}}\right]}^2,n为奇数.\end{array}$

推论6：梯状图 $X{L}_{n,n,n,n}$ 的完美匹配的个数为 $2F{\left(n\right)}^{2}F{\left(n+1\right)}^2$。

证明：通过引理2和上述推论进行证明：上述推论中，当 $x=1$ 时，可得 $X{L}_{n,n,n,n}$ 的完美匹配的个数。

若n是偶数，则

$\begin{array}{l}2{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^4+2\left[{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]}^2+2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]+1\right]{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^2\\ 4{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]\\ =2F{\left(n\right)}^4+4F{\left(n\right)}^{2}F\left(n\right)F\left(n-1\right)+2F{\left(n-1\right)}^{2}F{\left(n\right)}^2\\ =2F{\left(n\right)}^2\left(F{\left(n\right)}^2+2F\left(n\right)F\left(n-1\right)+F{\left(n-1\right)}^2\right)=2F{\left(n\right)}^{2}F{\left(n+1\right)}^2\end{array}$

若是奇数，则

$\begin{array}{l}2\left[{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^2+2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]+1\right]{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^2+4{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)+1}\right]}^2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]\\ \left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]+2{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]}^2{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)+1}\right]}^2\\ =2F{\left(n\right)}^{2}F{\left(n\right)}^2+4F{\left(n\right)}^{2}F\left(n\right)F\left(n-1\right)+2F{\left(n-1\right)}^{2}F{\left(n\right)}^2=2F{\left(n\right)}^{2}F{\left(n+1\right)}^2\end{array}$

综上， $X{L}_{n,n,n,n}$ 的完美匹配的个数为 $2F{\left(n\right)}^{2}F{\left(n+1\right)}^2$ 结论成立。

由定义知 $T{L}_{n_1,n_2,n_3}$ 是 $X{L}_{n_1,n_2,n_3,n_4}$ 的 $n_4=1$ 的特例。

推论7： $T{L}_{n_1,n_2,n_3}$ 的反强迫多项式满足

$\begin{array}{c}P\left(X{L}_{n_1,n_2,n_3},x\right)=P_{n_2}^{\ast }\left(L_{n_2+n_3},x\right)P_1\left(L_{n_1},x\right)+xP\left(L_{n_1-1},x\right)P_1\left(L_{n_2},x\right)P_1\left(L_{n_3},x\right)\\ +x{P}_1\left(L_{n_1-1},x\right)P\left(L_{n_2-1},x\right)P\left(L_{n_3-1},x\right)+xP\left(L_{n_1-1},x\right)P_1\left(L_{n_2},x\right)P_1\left(L_{n_3-1},x\right)\\ +xP\left(L_{n_1-1},x\right)P_1\left(L_{n_2-1},x\right)P_1\left(L_{n_3},x\right)+x{P}_{n_2-1}^{\ast }\left(L_{n_2+n_3-2},x\right)P\left(L_{n_1-1},x\right)\end{array}$

推论8： $T{L}_{n,n,n}$ 的反强迫多项式为

推论9：梯状图 $T{L}_{n,n,n}$ 的完美匹配的个数为 $F\left(n\right)F\left(n+1\right)F\left(n+2\right)$。

证明：通过引理2和上述推论进行证明：上述推论中，当 $x=1$ 时，可得 $T{L}_{n,n,n}$ 的完美匹配的个数。

若n是偶数，则

$\begin{array}{l}{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^3+\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^2+\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^2\\ +2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]\\ +\left[{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]}^2+2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]+1\right]\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]\\ =F{\left(n\right)}^3+F{\left(n\right)}^3+F\left(n-1\right)F{\left(n\right)}^2+2F{\left(n\right)}^{2}F\left(n-1\right)+F{\left(n-1\right)}^{2}F(\; n\; )\end{array}$

$\begin{array}{l}=2F{\left(n\right)}^3+3F{\left(n\right)}^{2}F\left(n-1\right)+F\left(n\right)F{\left(n-1\right)}^2\\ =F\left(n\right)\left(F\left(n\right)+F\left(n-1\right)\right)\left(F\left(n+1\right)+F\left(n\right)\right)\\ =F\left(n\right)F\left(n+1\right)F\left(n+2\right)\end{array}$

若n是奇数，则

$\begin{array}{l}\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)+1}\right]{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^2+\left[{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]}^2+2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]+1\right]\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]\\ +\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)+1}\right]}^2+2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)+1}\right]\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-1}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)}\right]\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]\\ +{\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-3}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-2-q\\ q\end{array}\right)}\right]}^2\left[{\displaystyle \underset{q=0}{\overset{\lfloor \frac{n-2}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-1-q\\ q\end{array}\right)+1}\right]\\ =F{\left(n\right)}^3+F{\left(n\right)}^3+F\left(n-1\right)F{\left(n\right)}^2+2F{\left(n\right)}^{2}F\left(n-1\right)+F{\left(n-1\right)}^{2}F\left(n\right)\\ =F\left(n\right)F\left(n+1\right)F\left(n+2\right)\end{array}$

综上所述， $T{L}_{n,n,n}$ 的完美匹配的个数为 $F\left(n\right)F\left(n+1\right)F\left(n+2\right)$。

注：梯状图 $X{L}_{n,n,n,n}$ 的完美匹配个数 $2F{\left(n\right)}^{2}F{\left(n+1\right)}^2$ 和 $T{L}_{n,n,n}$ 的完美匹配个数 $F\left(n\right)F\left(n+1\right)F\left(n+2\right)$ 是两个已知的序列，在OEIS [22] 中的编号分别为A060635和A065563，前一个序列在该网站上的解释是一个特殊图方格子图的二米诺覆盖方式数，其实就是梯状图 $X{L}_{n,n,n,n}$ 的完美匹配的个数，而后一序列网站上没有组合解释，推论9给出了其中一个组合解释。

基金项目

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