|
|
Last edited by Czhang271828 2023-5-23 17:10给定偶数个顶点的平面图 $G$, 能否找到若干条不重的边, 使得恰好覆盖所有顶点?
如此帖结论: 用 $1\times 2$-长方形覆盖 $n\times m$ 长方形的方法总数为
\begin{align*}
\sqrt{2^{mn}\prod_{l=1}^n\prod_{k=1}^{m/2}\left[(\cos\dfrac{\pi k}{m+1})^2+(\cos\dfrac{\pi l}{n+1})^2\right]}.
\end{align*}
例如用 $1\times 2$ 长方形覆盖 $8\times 8$ 棋盘的方法数为 $12988816=3604^2$.
考虑此贴原问题, 即 $m=2$. 通项为
\begin{align*}
\sqrt{\prod_{l=1}^n\left[1+\left(2\cos\dfrac{\pi l}{n+1}\right)^2\right]}=\prod_{l=1}^{\lfloor n/2\rfloor }\left[1+\left(2\cos \dfrac{\pi l}{n+1}\right)^2\right].
\end{align*}
也就是 Fibonacci 数列的乘积通项.
Kasteleyn 定理描述了一般平面图的完美匹配问题(二聚覆盖). 对给定平面图 $G$,
1. 存在一种定向, 使得每个面上仅有奇数条边为逆时针朝向, 简单证明见此.
2. 上述定向图中, 邻接矩阵行列式值的开方(即, 反对称矩阵的 Pfaffian)等于完美匹配数, 证明基本等同此贴. |
|
