图的完美匹配计数理论在很多领域有广泛的应用，其中的计数思想和方法对组合数学产生了重要影响，因此受到众多学者的关注^[1-16].本文用嵌套递推方法给出了2类2-边连通图完美匹配数目的计算公式.

定义1  设图G是有完美匹配的图，若图G的两个完美匹配M₁和M₂中有一条边不同，则称M₁和M₂是G的两个不同的完美匹配.

定义2  n个8圈为C₈ⁱ：u_i1u_i2u_i3u_i4u_i5u_i6u_i7u_i8u_i1.分别连接圈C₈ⁱ的顶点u_i1与u_i6，u_i2与u_i5，u_i3与u_i8，u_i4与u_i7(i=1，2，…，n)，再将圈C₈ⁱ和圈C₈ⁱ⁺¹顶点u_i3与u_i+1，8，u_i4与u_i+1，7分别连接起来(i=1，2，…，n－1)，这样得到的图记为2－nD₈，如图 1所示.

定义3  n个6圈为C₆ⁱ：u_i1u_i2u_i3u_i4u_i5u_i6v_i1.分别连接圈C₆ⁱ的顶点u_i1与u_i4，u_i2与u_i6，u_i3与u_i5(i=1，2，…，n)，再将圈C₆ⁱ和圈C₆ⁱ⁺¹顶点u_i2与u_i+1，6，u_i3与u_i+1，5分别连接起来(i=1，2，…，n－1)，这样得到的图记为2－nD₆，如图 2所示.

定理1  设图 2-nD₈的完美匹配数记为f(n)，则

证  易知图 2-nD₈有完美匹配.为了求函数f(n)的解析式，先定义图G₁，并求其完美匹配的数目.将路v₁v₂的端点v₁和v₂分别与图 2-nD₈的顶点u₁₈和u₁₇各连接一条边，所得到的图记为G₁，如图 3所示.

易知图G₁有完美匹配，设g(n)表示图G₁的完美匹配的数.

先求g(n)的表达式.设图G₁完美匹配的集合为M，G₁含边v₁v₂，v₁u₁₈的完美匹配集合分别为M₁，M₂，则M₁∩M₂=ϕ，M=M₁∪M₂，g(n)=|M|=|M₁|+|M₂|.

求|M₁|.因为v₁v₂∈M₁，所以v₁u₁₈，${v_2}{u_{17}} \notin {M_1}$.由f(n)的定义知，|M₁|=f(n).

求|M₂|.由g(n)的定义知，M₂中包含边v₁u₁₈，v₂u₁₇，u₁₁u₁₂，u₁₅u₁₆的完美匹配数为g(n－1)；

由g(n)的定义知，M₂中包含边v₁u₁₈，v₂u₁₇，u₁₁u₁₆，u₁₂u₁₅的完美匹配数为g(n－1)；

由f(n)的定义知，M₂中包含边v₁u₁₈，v₂u₁₇，u₁₁u₁₆，u₁₂u₁₃，u₁₄u₁₅的完美匹配数为f(n－1).

M₂中上述3类完美匹配互不包含，互不相交，且穷尽了M₂中所有完美匹配，故

综上所述，就有

再求f(n).设图 2-nD₈完美匹配的集合为M⁽¹⁾，图 2-nD₈含边u₁₁u₁₈，u₁₈u₁₃，u₁₈u₁₇的完美匹配集合分别为M₃，M₄，M₅，则M_i∩M_j=ϕ(3≤i＜j≤5)，M⁽¹⁾=M₃∪M₄∪M₅，f(n)=|M⁽¹⁾|=|M₃|+|M₄|+|M₅|.

求|M₃|.由f(n)的定义知，M₃中包含边u₁₁u₁₈，u₁₂u₁₃，u₁₄u₁₇，u₁₅u₁₆的完美匹配数为f(n－1)；

由g(n)的定义知，M₃中包含边u₁₁u₁₈，u₁₇u₁₆，u₁₂u₁₅的完美匹配数为g(n－1)；

由f(n)的定义知，M₃中包含边u₁₁u₁₈，u₁₇u₁₆，u₁₂u₁₃，u₁₄u₁₅的完美匹配数为f(n－1).

M₃中上述3类完美匹配互不包含，互不相交，且穷尽了M₃中所有完美匹配，故

求|M₄|.由f(n)的定义知，M₄中包含边u₁₁u₁₂，u₁₃u₁₈，u₁₆u₁₇，u₁₄u₁₅的完美匹配数为f(n－1)；

由f(n)的定义知，M₄中包含边u₁₃u₁₈，u₁₄u₁₇，u₁₁u₁₆，u₁₂u₁₅的完美匹配数为f(n－1)；

由f(n)的定义知，M₄中包含边u₁₃u₁₈，u₁₄u₁₇，u₁₁u₁₂，u₁₅u₁₆的完美匹配数为f(n－1).

M₄中上述3类完美匹配互不包含，互不相交，且穷尽了M₄中所有完美匹配，故

求|M₅|.由g(n)的定义知，M₅中包含边u₁₁u₁₂，u₁₅u₁₆，u₁₇u₁₈的完美匹配数为g(n－1)；

由g(n)的定义知，M₅中包含边u₁₇u₁₈，u₁₁u₁₆，u₁₂u₁₅的完美匹配数为g(n－1)；

由f(n)的定义知，M₅中包含边u₁₇u₁₈，u₁₁u₁₆，u₁₂u₁₃，u₁₄u₁₅的完美匹配数为f(n－1).

M₅中上述3类完美匹配互不包含，互不相交，且穷尽了M₅中所有完美匹配，故

综上所述，有

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

由(1)式，得

由(3)－(4)式，得

如图 4知，f(1)=9.

如图 5知，g(1)=12.

由(1)式，得

线性递推式(5)的特征方程为x²－11x+9=0，特征根为$x = \frac{{11 \pm \sqrt {85} }}{2}$.故(5)式的通解为

所以(5)式满足f(1)=9，f(2)=90的解为

定理2  设图 2-nD₆的完美匹配数记为σ(n)，则σ(n)=4·5^n－1.

证  易知图 2-nD₆有完美匹配.为了求函数σ(n)的解析式，先定义图G₄，并求其完美匹配的数目.将长为1的路v₁v₂的端点v₁和v₂分别与图 2-nD₆的顶点u₁₆和u₁₅各连接一条边，所得到的图记为G₄，如图 6所示.

易知图G₄有完美匹配，设τ(n)表示图G₄的完美匹配数.设图G₄完美匹配的集合为M⁽²⁾，G₄含边v₁v₂，v₁u₁₆的完美匹配集合分别为M₆，M₇，则M₆∩M₇=ϕ，M⁽²⁾=M₆∪M₇，τ(n)=|M⁽²⁾|=|M₆|+|M₇|.

求|M₆|.因为v₁v₂∈M₆，所以由σ(n)的定义知，|M₆|=σ(n).

求|M₇|.由τ(n)的定义知，M₇中包含边v₁u₁₆，v₂u₁₅，u₁₁u₁₄的完美匹配数为τ(n－1)；

由σ(n)的定义知，M₇中包含边v₁u₁₆，v₂u₁₅，u₁₁u₁₂，u₁₃u₁₄的完美匹配数为σ(n－1).

M₇中上述2类完美匹配互不包含，互不相交，且穷尽了M₇中所有完美匹配，故

综上所述，有

再求σ(n).设图 2-nD₆的完美匹配的集合为M⁽³⁾，图 2-nD₆含边u₁₁u₁₆，u₁₂u₁₆，u₁₅u₁₆的完美匹配集合分别为M₈，M₉，M₁₀，则M_i∩M_j=ϕ(8≤i＜j≤10)，M⁽³⁾=M₈∪M₉∪M₁₀，σ(n)=|M⁽³⁾|=|M₈|+|M₉|+|M₁₀|.

求|M₈|.因为u₁₁u₁₆，u₁₄u₁₅∈M₈，所以由τ(n)的定义知，|M₈|=τ(n－1).

求|M₉|.因为u₁₂u₁₆，u₁₃u₁₅，u₁₁u₁₄∈M₈，所以由σ(n)的定义知，|M₉|=σ(n－1).

求|M₁₀|.由τ(n)的定义知，M₁₀含边u₁₅u₁₆，u₁₁u₁₄的完美匹配数为τ(n－1)；

由σ(n)的定义知，M₁₀含边u₁₅u₁₆，u₁₁u₁₂，u₁₃u₁₄的完美匹配数为σ(n－1).

M₁₀中上述2类完美匹配互不包含，互不相交，且穷尽了M₁₀中所有完美匹配，故

综上所述，有

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

如图 7知，σ(1)=4.

故(8)式满足σ(1)=4的解为