完美匹配的计数理论在量子化学、晶体物理学和计算机科学中都有重要的应用, 例如, 二分图的完美匹配的数目可以方便地表示为计算积和式的值^[1-4].由于完美匹配的计数理论在化学、物理学和计算机科学中有重要的理论价值和现实意义, 所以引起人们对此问题的广泛研究^[5-16].本文研究特殊图类完美匹配的计数方法, 给出了4类图完美匹配数的显式表达式, 其研究方法为得到一般有完美匹配图的所有完美匹配数目提供了借鉴.

定义1 若图$G$的两个完美匹配$M_1$和$M_2$中有一条边不同, 则称$M_1$和$M_2$是$G$的两个不同的完美匹配.

定义2 分别连接$n$圈$u_1u_2\cdot\cdot\cdot{u_n}u_1$与$v_1v_2\cdot\cdot\cdot{v_n}v_1$的顶点$u_i$与$v_i (i=1,2,\cdot\cdot\cdot,n)$, 得到的图称为$n$棱柱, 记为$Z_n$.

定理1 $2n$个$6$圈为$C_{i1}: u_{i1}u_{i2}\cdot\cdot\cdot{u_{i6}}u_{i1}$, $C_{i2}: v_{i1}v_{i2}\cdot\cdot\cdot{v_{i6}}v_{i1}(i=1,2,\cdot\cdot\cdot,n)$, 分别连接圈$C_{i1}$和$C_{i2}$的顶点$u_{i4}$与$v_{i2}$, $u_{i5}$与$v_{i1}$; 再分别连接$C_{i1}$与$C_{i+1, 1}$, $C_{i2}$与$C_{i+1,2}$的顶点$u_{i3}$与$u_{i+1,6}$, $v_{i2}$与$v_{i+1,1} (i=1,2,\cdot\cdot\cdot,n-1)$, 这样所得的图记为$2-n(2-C_6)$, 如图 1所示. $f(n)$表示图$2-n(2-C_6)$的完美匹配的数目.则

$f(n)=\frac{13+3\sqrt{13}}{26}(\frac{7+\sqrt{13}}{2})^n+\frac{13-3\sqrt{13}}{26}(\frac{7-\sqrt{13}}{2})^n. $

证 为了求$f(n)$, 先定义1个图$G_1$, 并求其完美匹配的数目.将长为5的路$u_1u_2u_3v_1v_2v_3$的顶点$u_1$, $v_3$与圈$C_{11}$和$C_{12}$的顶点$u_{16}$, $v_{16}$分别连接一条边得到的图记为$G_1$, 如图 2所示. $\alpha(n)$表示图$G_1$的完美匹配的数目.

先求$\alpha(n)$.易知图$G_1$有完美匹配.设图$G_1$的完美匹配集合为$\mathscr{M}$, 图$G_1$含边$u_3u_2$, $u_3v_1$的完美匹配集合分别为$\mathscr{M}_1$, $\mathscr{M}_2$, 则$\mathscr{M}_i\neq\phi(i=1,2)$, $\mathscr{M}_1\cap\mathscr{M}_2=\phi$, 所以$\mathscr{M}=\mathscr{M}_1\cup\mathscr{M}_2$, 故

$\alpha(n)=|\mathscr{M}|=|\mathscr{M}_1|+|\mathscr{M}_2|.$

求$|\mathscr{M}_1|$. $\forall{M_1}\in\mathscr{M}_1$, 因为$u_3u_2\in{M_1}$, 所以$v_1v_2,u_1u_{16},v_3v_{16}, u_{11}u_{12},v_{15}v_{14}\in{M_1}$.故由$\alpha(n)$的定义知

$|\mathscr{M}_1|=\alpha(n-1).$

求$|\mathscr{M}_2|$.

情形1 $\mathscr{M}_{21}\subseteq\mathscr{M}_{2}$, $\forall{M_{21}}\in\mathscr{M}_{21}$, $u_3v_1,u_2v_2,u_1u_{16}$, $v_1v_{16},u_{11}u_{12},v_{15}v_{14}\in{M_{21}}$, 故由$\alpha(n)$的定义知, $|\mathscr{M}_{21}|=\alpha(n-1)$.

情形2 $\mathscr{M}_{22}\subseteq\mathscr{M}_{2}$, $\forall{M_{22}}\in\mathscr{M}_{22}$, $u_3v_1,u_1u_2,v_2v_3\in{M_{22}}$, 由$f(n)$的定义知, $|\mathscr{M}_{22}|=f(n)$.

易知$\mathscr{M}_2=\mathscr{M}_{21}{\cup}\mathscr{M}_{22}$, $\mathscr{M}_{21}{\cap}\mathscr{M}_{22}=\phi$, 故$|\mathscr{M}_{2}|=f(n)+\alpha(n-1)$.故

$\alpha(n)=f(n)+2\alpha(n-1).$

(1)

再求$f(n)$.易知图$2-n(2-C_6)$有完美匹配.设图$2-n(2-C_6)$的完美匹配集合为$\mathscr{M}$, 图$2-n(2-C_6)$含边$u_{16}u_{11},u_{16}u_{15}$的完美匹配集合分别为$\mathscr{M}_1, \mathscr{M}_2$, 则$\mathscr{M}_i\neq\phi(i=1,2)$, $\mathscr{M}_1\cap\mathscr{M}_2=\phi$, 所以$\mathscr{M}=\mathscr{M}_1\cup\mathscr{M}_2$.故$f(n)==|\mathscr{M}_1|+|\mathscr{M}_2|$.

求$|\mathscr{M}_1|$.

情形1 $\mathscr{M}_{11}\subseteq\mathscr{M}_{1}$, $\forall{M_{11}}\in\mathscr{M}_{11}$, $u_{16}u_{11},u_{12}u_{13},u_{15}u_{14},v_{16}v_{11},v_{12}v_{13},v_{15}v_{14}\in{M_{11}}$, 由$f(n)$的定义知, $|\mathscr{M}_{11}|=f(n-1)$.

情形2 $\mathscr{M}_{12}\subseteq\mathscr{M}_{1}$, $\forall{M_{12}}\in\mathscr{M}_{12}$, $u_{16}u_{11},u_{12}u_{13},u_{15}u_{14} ,v_{16}v_{15},v_{11}v_{12},v_{14}v_{13}\in{M_{12}}$, 由$f(n)$的定义知, $|\mathscr{M}_{12}|=f(n-1)$.

情形3 $\mathscr{M}_{13}\subseteq\mathscr{M}_{1}$, $\forall{M_{13}}\in\mathscr{M}_{13}$, $u_{16}u_{11},u_{12}u_{13}$, $u_{15}v_{11},u_{14}v_{12},v_{16}v_{15}$, $v_{14}v_{13}\in{M_{13}}$, $f(n)$的定义知, $|\mathscr{M}_{13}|=f(n-1)$.

易知$\mathscr{M}_1=\mathscr{M}_{11}{\cup}\mathscr{M}_{12}{\cup}\mathscr{M}_{13}$, $\mathscr{M}_{1i}{\cap}\mathscr{M}_{1j}=\phi(1\leq{i}<j\leq3)$, 故$|\mathscr{M}_{1}|=3f(n-1)$.

求$|\mathscr{M}_2|$.

情形1 $\mathscr{M}_{21}\subseteq\mathscr{M}_{2}$, $\forall{M_{21}}\in\mathscr{M}_{21}$, $u_{16}u_{15},u_{11}u_{12},u_{13}u_{14}$, $v_{16}v_{11}$, $v_{15}v_{14}$, $v_{12}v_{13}\in{M_{21}},$由$f(n)$的定义知, $|\mathscr{M}_{21}|=f(n-1)$.

情形2 $\mathscr{M}_{22}\subseteq\mathscr{M}_{2}$, $\forall{M_{22}}\in\mathscr{M}_{22}$, $u_{16}u_{15},u_{11}u_{12},u_{13}u_{26}$, $u_{14}v_{12},v_{16}v_{11}$, $v_{15}v_{14}$, $v_{13}v_{26}$, $u_{21}u_{22}$, $v_{25}v_{24}\in{M_{22}}$, 由$\alpha(n)$的定义知, $|\mathscr{M}_{22}|=\alpha(n-2)$.

情形3 $\mathscr{M}_{23}\subseteq\mathscr{M}_{2}$, $\forall{M_{23}}\in\mathscr{M}_{23}$, $u_{16}u_{15},u_{11}u_{12}, u_{13}u_{14},v_{16}v_{15},v_{11}v_{12}$, $v_{14}v_{13}\in{M_{23}}$, $f(n)$的定义知, $|\mathscr{M}_{23}|=f(n-1)$.

易知$\mathscr{M}_2=\mathscr{M}_{21}{\cup}\mathscr{M}_{22}{\cup}\mathscr{M}_{23}$, $\mathscr{M}_{2i}{\cap}\mathscr{M}_{2j}=\phi(1\leq{i}<j\leq3)$, 故

$|\mathscr{M}_{2}|=2f(n-1)+\alpha(n-2).$

综上所述

$f(n)=5f(n-1)+\alpha(n-2),$

(2)

把 (1) 式代入 (2) 式, 得

$f(n)=5f(n-1)+f(n-2)+2\alpha(n-3),$

(3)

由 (2) 式, 得

$ f(n-1)=5f(n-2)+\alpha(n-3),$

(4)

$(3)-2{\times}(4)$式, 得

$ f(n)=7f(n-1)-9f(n-2).$

(5)

(5) 式的特征方程的根为$x=\frac{7\pm\sqrt{13}}{2}$.易知$f(1)=5$, $f(2)=26$, 所以 (5) 式的通解为

$f(n)=\frac{13+3\sqrt{13}}{26}(\frac{7+\sqrt{13}}{2})^n+\frac{13-3\sqrt{13}}{26}(\frac{7-\sqrt{13}}{2})^n. $

定理2 $n$个4棱柱$Z_4^i$的顶点集为$V(Z_4^i)=\{u_{i1},u_{i2},u_{i3},u_{i4}, v_{i1}, v_{i2}, v_{i3}, v_{i4}\}$ $(i=1,2,\cdots,n)$, 分别连接4棱柱$Z_4^i$和$Z_4^{i+1}$的顶点$v_{i1}$和$v_{i+1,1}$, $v_{i2}$和$v_{i+1,4}$, $v_{i3}$和$v_{i+1,3}$ $(i=1,2,\cdot\cdot\cdot,n-1)$.这样得到的图记为$3-nZ_4$, 如图 5所示. $g(n)$表示图$3-nZ_4$的完美匹配的数目.则$g(n)=9\times11^n$.

证 为了求$g(n)$, 先定义2个图$G_2$和$G_3$, 并求其完美匹配的数目.将长为1的路$v_1v_2$的端点$v_1$和$v_2$分别与图$3-nZ_4$的顶点$v_{14}$和$v_{13}$, $v_{11}$和$v_{14}$各连接一条边得到的图分别记为$G_2$, $G_3$, 如图 4, 5所示.易知图$G_2$, $G_3$均有完美匹配. $\beta(n)$, $\gamma(n)$分别表示图$G_2$, $G_3$的完美匹配的数目.显然$G_2\cong{G_3}$, 故$\beta(n)=\gamma(n)$.

先求$\beta(n)$.设图$G_2$的完美匹配的集合为$\mathscr{M}$, $G_2$含边$u_1u_2,u_1u_{15}$的完美匹配集合分别为$\mathscr{M}_1$, $\mathscr{M}_2$.则$\mathscr{M}_i\neq\phi(i=1,2)$, $\mathscr{M}_1\cap\mathscr{M}_2=\phi$, 所以$\mathscr{M}=\mathscr{M}_1\cup\mathscr{M}_2$, $\alpha(n)=|\mathscr{M}_1|+|\mathscr{M}_2|$.

求$|\mathscr{M}_1|$. $\forall{M_{1}}\in\mathscr{M}_{1}$, 因为$v_1v_2\in{M_1}$, 所以由$g(n)$的定义知, $|\mathscr{M}_1|=g(n)$.

求$|\mathscr{M}_2|$.

情形1 $\mathscr{M}_{21}\subseteq\mathscr{M}_{2}$, $\forall{M_{21}}\in\mathscr{M}_{21}$, $v_1v_{14},v_2v_{13},u_{14}u_{11},u_{13}u_{12}\in{M_{21}}$, 故由$\gamma(n)$的定义知, $|\mathscr{M}_{21}|=\gamma(n-1)=\beta(n-1)$.

情形2 $\mathscr{M}_{22}\subseteq\mathscr{M}_{2}$, $\forall{M_{22}}\in\mathscr{M}_{22}$, $v_1v_{14},v_2v_{13}, u_{14}u_{13},u_{11}v_{11},u_{12}v_{12}\in{M_{22}}$, 故由$g(n)$的定义知, $|\mathscr{M}_{22}|=g(n-1)$.

情形3 $\mathscr{M}_{23}\subseteq\mathscr{M}_{2}$, $\forall{M_{23}}\in\mathscr{M}_{23}$, $v_1v_{14},v_2v_{13},u_{14}u_{13},u_{11}u_{12}\in{M_{23}}$, 故由$\gamma(n)$的定义知, $|\mathscr{M}_{23}|=\gamma(n-1)=\beta(n-1)$.

易知$\mathscr{M}_2=\mathscr{M}_{21}{\cup}\mathscr{M}_{22}{\cup}\mathscr{M}_{23}$, $\mathscr{M}_{2i}{\cap}\mathscr{M}_{2j}=\phi(1\leq{i}<j\leq3)$, 故$|\mathscr{M}_{2}|=f(n-1)+2\beta(n-1)$.故

$ \beta(n)=g(n)+g(n-1)+2\beta(n-1).$

(6)

再求$g(n)$.易知图$3-nZ_4$有完美匹配.设图$3-nZ_4$的完美匹配集合为$\mathscr{M}$, 图$3-nZ_4$含边$u_{14}u_{11},u_{14}v_{14},u_{14}u_{13}$的完美匹配集合分别为$\mathscr{M}_1,\mathscr{M}_2,\mathscr{M}_3$, 则$\mathscr{M}_i\neq\phi(i=1,2,3)$, $\mathscr{M}_{i}{\cap}\mathscr{M}_{j}=\phi(1\leq{i}<j\leq3)$, 所以$\mathscr{M}=\mathscr{M}_{1}{\cup}\mathscr{M}_{2}{\cup}\mathscr{M}_{3}$.故$g(n)=|\mathscr{M}_1|+|\mathscr{M}_2|+|\mathscr{M}_3|$, 由图$3-nZ_4$的对称性知, $|\mathscr{M}_1|=|\mathscr{M}_3|$, 故$g(n)=2|\mathscr{M}_1|+|\mathscr{M}_2|$.

求$|\mathscr{M}_1|$.

情形1 $\mathscr{M}_{11}\subseteq\mathscr{M}_{1}$, $\forall{M_{11}}\in\mathscr{M}_{11}$, $u_{14}u_{11},v_{14}v_{11},u_{13}v_{13},u_{12}v_{12}\in{M_{11}}$, 故由$g(n)$的定义知, $|\mathscr{M}_{11}|=g(n-1)$.

情形2 $\mathscr{M}_{12}\subseteq\mathscr{M}_{1}$, $\forall{M_{12}}\in\mathscr{M}_{12}$, $u_{14}u_{11},v_{14}v_{11},u_{13}u_{12}\in{M_{12}}$, 由$\beta(n)$的定义知, $|\mathscr{M}_{12}|=\beta(n-1)$.

情形3 $\mathscr{M}_{13}\subseteq\mathscr{M}_{1}$, $\forall{M_{13}}\in\mathscr{M}_{13}$, $u_{14}u_{11},v_{14}v_{13},u_{13}u_{12}\in{M_{13}}$, 由$\gamma(n)$的定义知, $|\mathscr{M}_{13}|=\gamma(n-1)=\beta(n-1)$.

易知$\mathscr{M}_1=\mathscr{M}_{11}{\cup}\mathscr{M}_{12}{\cup}\mathscr{M}_{13}$, $\mathscr{M}_{1i}{\cap}\mathscr{M}_{1j}=\phi(1\leq{i}<j\leq3)$, 故$|\mathscr{M}_{1}|=g(n-1)+2\beta(n-1)$.

求$|\mathscr{M}_2|$.

情形1 $\mathscr{M}_{21}\subseteq\mathscr{M}_{2}$, $\forall{M_{21}}\in\mathscr{M}_{21}$, $u_{14}v_{14},u_{11}v_{11},u_{12}v_{12}$, $u_{13}v_{13}\in{M_{21}}$, 故由$g(n)$的定义知, $|\mathscr{M}_{21}|=g(n-1)$.

情形2 $\mathscr{M}_{22}\subseteq\mathscr{M}_{2}$, $\forall{M_{22}}\in\mathscr{M}_{22}$, $u_{14}v_{14},u_{11}v_{11},u_{13}u_{12}\in{M_{22}}$, 由$\beta(n)$的定义知, $|\mathscr{M}_{22}|=\beta(n-1)$.

情形3 $\mathscr{M}_{23}\subseteq\mathscr{M}_{2}$, $\forall{M_{23}}\in\mathscr{M}_{23}$, $u_{14}v_{14},u_{13}v_{13},u_{11}u_{12}\in{M_{23}}$, 由$\gamma(n)$的定义知, $|\mathscr{M}_{23}|=\gamma(n-1)=\beta(n-1)$.

易知$\mathscr{M}_2=\mathscr{M}_{21}{\cup}\mathscr{M}_{22}{\cup}\mathscr{M}_{23}$, $\mathscr{M}_{2i}{\cap}\mathscr{M}_{2j}=\phi(1\leq{i}<j\leq3)$, 故$|\mathscr{M}_{1}|=g(n-1)+2\beta(n-1)$.故

$g(n)=3g(n-1)+6\beta(n-1),$

(7)

把 (6) 式代入 (7) 式, 得

$g(n)=9g(n-1)+6g(n-2)+12\beta(n-2),$

(8)

由 (7) 式, 得

$g(n-1)=3g(n-2)+6\alpha(n-2),$

(9)

$(8)-2\times(9)$式, 得$g(n)=11g(n-1)=11^{n-1}g(1)$, 易知$g(1)=9$.故$g(n)=9\times11^{n-1}$.

定理3 4个顶点的完全图分别为$K_4^{i1}$和$K_4^{i2}$, 其中$V(K_4^{i1})=\{u_{i1},u_{i2},u_{i3},u_{i4}\}$, $V(K_4^{i2})=\{v_{i1},v_{i2},v_{i3},v_{i4}\}$ $(i=1,2,\cdots,n)$.分别连接圈$K_4^{i1}$和$K_4^{i2}$的顶点$u_{i2}$与$v_{i2}$, $u_{i3}$与$v_{i3}$; 再分别连接$K_4^{i1}$和$K_4^{i+1,1}$, $K_4^{i2}$和$K_4^{i+1,2}$的顶点$u_{i2}$与$u_{i+1,3}$, $v_{i2}$与$v_{i+1,3}$ $(i=1,2,\cdots,n-1)$, 这样所得的图记为$2-n(2-K_4)$, 如图 6所示. $\sigma(n)$表示图$2-n(2-K_4)$的完美匹配的数目.则

$\sigma(n)=\frac{85+9\sqrt{85}}{170}(\frac{11+\sqrt{85}}{2})^n+\frac{85-9\sqrt{85}}{170}(\frac{11-\sqrt{85}}{2})^n. $

证 为了求$\sigma(n)$, 先定义1个图$G_4$, 并求其完美匹配的数目.将长为1的路$uv$的端点$u$和$v$分别与图$2-n(2-K_4)$的顶点$u_{13}$和$v_{13}$各连接一条边, 得到的图记为$G_4$, 如图 7所示.易知图$G_4$有完美匹配. $\gamma(n)$表示图$G_4$的完美匹配的数目.

求$\gamma(n)$.设图$G_4$的完美匹配的集合为$\mathscr{M}$, $G_4$含边$uv$, $uu_{13}$的完美匹配集合分别为$\mathscr{M}_1,\mathscr{M}_2$.则$\mathscr{M}_i\neq\phi(i=1,2)$, $\mathscr{M}_{1}{\cap}\mathscr{M}_{2}=\phi$, 所以$\mathscr{M}=\mathscr{M}_{1}{\cup}\mathscr{M}_{2}$, $\gamma(n)==|\mathscr{M}_{1}|+|\mathscr{M}_{2}|$.

求$|\mathscr{M}_1|$. $\forall{M_{1}}\in\mathscr{M}_{1}$, 由于$uv\in{M_{1}}$, 所以由$\sigma(n)$的定义知, $|\mathscr{M}_{1}|=\sigma(n)$.

求$|\mathscr{M}_2|$. $\forall{M_{2}}\in\mathscr{M}_{2}$, $uu_{13},vv_{13},u_{11}u_{14},v_{11}v_{14}\in{M_{2}}$, 由$\gamma(n)$的定义知, $|\mathscr{M}_{2}|=\gamma(n-1)$.故

$\gamma(n)=\sigma(n)+\gamma(n-1).$

(10)

再求$\sigma(n)$.易知图$2-n(2-K_4)$有完美匹配.设图$2-n(2-K_4)$的完美匹配的集合为$\mathscr{M}$, 图$2-n(2-K_4)$含边$u_{11}u_{13},u_{11}u_{14},u_{11}u_{12}$的完美匹配的集合分别为$\mathscr{M}_1,\mathscr{M}_2,\mathscr{M}_3$, 则$\mathscr{M}_i\neq\phi(i=1,2,3)$, $\mathscr{M}_{i}{\cap}\mathscr{M}_{j}=\phi(1\leq{i}<j\leq3)$, 所以$\mathscr{M}=\mathscr{M}_{1}{\cup}\mathscr{M}_{2}{\cup}\mathscr{M}_{3}$.故$\sigma(n)==|\mathscr{M}_1|+|\mathscr{M}_2|+|\mathscr{M}_3|$.

求$|\mathscr{M}_1|$.

情形1 $\mathscr{M}_{11}\subseteq\mathscr{M}_{1}$, $\forall{M_{11}}\in\mathscr{M}_{11}$, $u_{11}u_{13},u_{14}u_{12},v_{13}v_{12},v_{14}v_{11}\in{M_{11}}$, 故由$\sigma(n)$的定义知, $|\mathscr{M}_{11}|=\sigma(n-1)$.

情形2 $\mathscr{M}_{12}\subseteq\mathscr{M}_{1}$, $\forall{M_{12}}\in\mathscr{M}_{12}$, $u_{11}u_{13}, u_{14}u_{12},v_{13}v_{14},v_{12}v_{11}\in{M_{12}}$, 由$\sigma(n)$的定义知, $|\mathscr{M}_{12}|=\sigma(n-1)$.

情形3 $\mathscr{M}_{13}\subseteq\mathscr{M}_{1}$, $\forall{M_{13}}\in\mathscr{M}_{13}$, $u_{11}u_{13},u_{14}u_{12},v_{13}v_{11},v_{14}v_{12}\in{M_{13}}$, 由$\sigma(n)$的定义知, $|\mathscr{M}_{13}|=\sigma(n-1)$.

显然, $\mathscr{M}_1=\mathscr{M}_{11}{\cup}\mathscr{M}_{12}{\cup}\mathscr{M}_{13}$, $\mathscr{M}_{1i}{\cap}\mathscr{M}_{1j}=\phi(1\leq{i}<j\leq3)$, 故$|\mathscr{M}_{1}|=3\sigma(n-1)$.

求$|\mathscr{M}_2|$.

情形1 $\mathscr{M}_{21}\subseteq\mathscr{M}_{2}$, $\forall{M_{21}}\in\mathscr{M}_{21}$, $u_{11}u_{14},u_{13}u_{12},v_{13}v_{12},v_{14}v_{11}\in{M_{21}}$, 故由$\sigma(n)$的定义知, $|\mathscr{M}_{21}|=\sigma(n-1)$.

情形2 $\mathscr{M}_{22}\subseteq\mathscr{M}_{2}$, $\forall{M_{22}}\in\mathscr{M}_{22}$, $u_{11}u_{14},u_{13}u_{12},v_{13}v_{14},v_{12}v_{11}\in{M_{22}}$, 由$\sigma(n)$的定义知, $|\mathscr{M}_{22}|=\sigma(n-1)$.

情形3 $\mathscr{M}_{23}\subseteq\mathscr{M}_{2}$, $\forall{M_{23}}\in\mathscr{M}_{23}$, $u_{11}u_{14},u_{13}u_{12},v_{13}v_{11},v_{14}v_{12}\in{M_{23}}$, 由$\sigma(n)$的定义知, $|\mathscr{M}_{23}|=\sigma(n-1)$.

情形4 $\mathscr{M}_{24}\subseteq\mathscr{M}_{2}$, $\forall{M_{24}}\in\mathscr{M}_{24}$, $u_{11}u_{14},u_{13}v_{13},v_{14}v_{11}\in{M_{24}}$, 由$\gamma(n)$的定义知, $|\mathscr{M}_{24}|=\gamma(n-1)$.

显然, $\mathscr{M}_2=\mathscr{M}_{21}{\cup}\mathscr{M}_{22}{\cup}\mathscr{M}_{23}{\cup}\mathscr{M}_{24}$, $\mathscr{M}_{2i}{\cap}\mathscr{M}_{2j}=\phi(1\leq{i}<j\leq4)$, 故$|\mathscr{M}_{2}|=3\sigma(n-1)+\gamma(n-1)$.

求$|\mathscr{M}_3|$.

情形1 $\mathscr{M}_{31}\subseteq\mathscr{M}_{3}$, $\forall{M_{31}}\in\mathscr{M}_{31}$, $u_{13}u_{14},u_{11}u_{12},v_{13}v_{12},v_{14}v_{11}\in{M_{31}}$, 故由$\sigma(n)$的定义知, $|\mathscr{M}_{31}|=\sigma(n-1)$.

情形2 $\mathscr{M}_{32}\subseteq\mathscr{M}_{3}$, $\forall{M_{32}}\in\mathscr{M}_{32}$, $u_{13}u_{14},u_{11}u_{12},v_{13}v_{14},v_{12}v_{11}\in{M_{32}}$, 由$\sigma(n)$的定义知, $|\mathscr{M}_{32}|=\sigma(n-1)$.

情形3 $\mathscr{M}_{33}\subseteq\mathscr{M}_{3}$, $\forall{M_{33}}\in\mathscr{M}_{33}$, $u_{13}u_{14},u_{11}u_{12},v_{13}v_{11},v_{14}v_{12}\in{M_{33}}$, 由$\sigma(n)$的定义知, $|\mathscr{M}_{33}|=\sigma(n-1)$.

显然, $\mathscr{M}_3=\mathscr{M}_{31}{\cup}\mathscr{M}_{32}{\cup}\mathscr{M}_{33}$, $\mathscr{M}_{3i}{\cap}\mathscr{M}_{3j}=\phi(1\leq{i}<j\leq3)$, 故$|\mathscr{M}_{3}|=3\sigma(n-1)$.

综上所述

$\sigma(n)=9\sigma(n-1)+\gamma(n-1).$

(11)

把 (10) 式代入 (11) 式, 得

$\sigma(n)=10\sigma(n-1)+\gamma(n-2),$

(12)

再由 (11) 式, 得

$\sigma(n-1)=9\sigma(n-2)+\gamma(n-2),$

(13)

$(12)-(13)$式, 得

$\sigma(n)=11\sigma(n-1)-9\sigma(n-2).$

(14)

(14) 式的特征方程的根为$x=\frac{11\pm\sqrt{85}}{2}$.易知$\sigma(1)=10$, $\gamma(1)=11$.故由 (11) 式得$\sigma(2)=101$.所以 (14) 式的通解为

$\sigma(n)=\frac{85+9\sqrt{85}}{170}(\frac{11+\sqrt{85}}{2})^n+\frac{85-9\sqrt{85}}{170}(\frac{11-\sqrt{85}}{2})^n. $

定理4 $n$个6圈$C^i_6:\ u_{i1}u_{i2}\cdot\cdot\cdot{u_{i6}}u_{i1}$和4圈$C^i_4:\ v_{i1}v_{i2}v_{i3}v_{i4}v_{i1}$, 分别连接$C^i_6$与$C^i_4$的顶点$u_{i1}$与$v_{i1}$, $u_{i2}$与$v_{i2}$, $u_{i4}$与$v_{i3}$, $u_{i5}$与$v_{i4}(i=1,2,\cdots, {n})$; 再分别连接$C^i_6$与$C^{i+1}_6$的顶点$u_{i2}$和$u_{i+1,1}$, $u_{i3}$和$u_{i+1,6}$, $u_{i4}$和$u_{i+1,5}(i=1,2,\cdots, {n-1})$, 这样得到的图记为$3-n(C_4-C_6)$, 如图 8所示. $\psi(n)$表示图$3-n(C_4-C_6)$的完美匹配的数目.则$\psi(n)=6\times9^{n-1}$.

证 为了求$\psi(n)$, 先定义1个图$G_5$, 并求其完美匹配的数目.将长为1的路$u_1u_2$的端点$u_1$和$u_2$分别与图$3-n(C_4-C_6)$的顶点$u_{11}$和$u_{16}$各连接一条边, 得到的图记为$G_5$, 如图 9所示.易知图$G_5$有完美匹配. $\delta(n)$表示图$G_5$的完美匹配的数目.

求$\delta(n)$.设图$G_5$的完美匹配的集合为$\mathscr{M}$, $G_5$含边$u_1u_2$, $u_1u_{11}$的完美匹配集合分别为$\mathscr{M}_1$, $\mathscr{M}_2$, 则$\mathscr{M}_1\cap\mathscr{M}_2=\phi$.所以$\mathscr{M}=\mathscr{M}_1\cup\mathscr{M}_2$, $\delta(n)==|\mathscr{M}_{1}|+|\mathscr{M}_{2}|$.

求$|\mathscr{M}_{1}|$. $\forall{M_1}\in\mathscr{M}_1$, 因为$u_1u_2\in{M_1}$, 所以由$\psi(n)$的定义知, $|\mathscr{M}_{1}|=\psi(n)$.

求$|\mathscr{M}_2|$.

情形1 $\mathscr{M}_{21}\subseteq\mathscr{M}_{2}$, $\forall{M_{21}}\in\mathscr{M}_{21}$, $u_1u_{11},u_2u_{16},u_{15}v_{14},v_{11}v_{12}$, $v_{13}u_{14}\in{M_{21}}$, 故由$\delta(n)$的定义知, $|\mathscr{M}_{21}|=\delta(n-1)$.

情形2 $\mathscr{M}_{22}\subseteq\mathscr{M}_{2}$, $\forall{M_{22}}\in\mathscr{M}_{22}$, $u_1u_{11},u_2u_{16},u_{15}u_{14},v_{11}v_{12},v_{13}u_{14}\in{M_{22}}$, 由$\delta(n)$的定义知, $|\mathscr{M}_{22}|=\delta(n-1)$.

情形3 $\mathscr{M}_{23}\subseteq\mathscr{M}_{2}$, $\forall{M_{23}}\in\mathscr{M}_{23}$, $u_1u_{11},u_2u_{16},u_{15}u_{14},v_{11}v_{14},v_{12}u_{13}\in{M_{23}}$, 由$\delta(n)$的定义知, $|\mathscr{M}_{23}|=\delta(n-1)$.

因为$\mathscr{M}_2=\mathscr{M}_{21}{\cup}\mathscr{M}_{22}{\cup}\mathscr{M}_{23}$, $\mathscr{M}_{2i}{\cap}\mathscr{M}_{2j}=\phi(1\leq{i}<j\leq3)$, 故$|\mathscr{M}_{2}|=3\delta(n-1)$.

综上所述

$\delta(n)=\psi(n)+3\delta(n-1).$

(15)

求$\psi(n)$.易知图$3-n(C_4-C_6)$有完美匹配.设图$3-n(C_4-C_6)$的完美匹配的集合为$\mathscr{M}$, $3-n(C_4-C_6)$含边$u_{16}u_{11}$, $u_{16}u_{15}$的完美匹配集合分别为$\mathscr{M}_1$, $\mathscr{M}_2$, 所以$\mathscr{M}=\mathscr{M}_1\cup\mathscr{M}_2$, $\psi(n)==|\mathscr{M}_{1}|+|\mathscr{M}_{2}|$.由图$3-n(C_4-C_6)$的对称性可知, $|\mathscr{M}_{1}|=|\mathscr{M}_{2}|$, 故$\psi(n)=2|\mathscr{M}_{1}|$.

求$|\mathscr{M}_1|$.

情形1 $\mathscr{M}_{11}\subseteq\mathscr{M}_{1}$, $\forall{M_{11}}\in\mathscr{M}_{11}$, $u_{16}u_{11},u_{15}v_{14},v_{11}v_{12},v_{13}u_{14}\in{M_{11}}$, 故由$\delta(n)$的定义知, $|\mathscr{M}_{11}|=\delta(n-1)$.

情形2 $\mathscr{M}_{12}\subseteq\mathscr{M}_{1}$, $\forall{M_{12}}\in\mathscr{M}_{12}$, $u_{16}u_{11},u_{15}u_{14},v_{14}u_{13},v_{11}v_{12}\in{M_{12}}$, 故由$\delta(n)$的定义知, $|\mathscr{M}_{12}|=\delta(n-1)$.

情形3 $\mathscr{M}_{13}\subseteq\mathscr{M}_{1}$, $\forall{M_{13}}\in\mathscr{M}_{13}$, $u_{16}u_{11},u_{15}u_{14},v_{11}v_{14},v_{12}v_{13}\in{M_{13}}$, 故由$\delta(n)$的定义知, $|\mathscr{M}_{13}|=\delta(n-1)$.

因为$\mathscr{M}_1=\mathscr{M}_{11}{\cup}\mathscr{M}_{12}{\cup}\mathscr{M}_{13}$, $\mathscr{M}_{1i}{\cap}\mathscr{M}_{1j}=\phi(1\leq{i}<j\leq3)$, 故$|\mathscr{M}_{1}|=3\delta(n-1)$.

综上所述

$\psi(n)=6\delta(n-1),$

(16)

把 (15) 式代入 (16) 式, 得

$\psi(n)=6\psi(n-1)+18\delta(n-2),$

(17)

再由 (16) 式, 得

$\psi(n-1)=6\delta(n-2),$

(18)

$(17)-3\times(18)$式, 得$\psi(n)=9\psi(n-1)=9^{n-1}\psi(1)$, 易知$\psi(1)=6$.故$\psi(n)=6\times9^{n-1}$.