20201104一个经典题
qwaszx
·
·
个人记录
题意：求 n\times m 的 01 矩阵中，满足不存在形如 \begin{matrix}01\\10\end{matrix} 或 \begin{matrix}10\\01\end{matrix} 的子矩阵（可以不连续）的矩阵个数.
之前见过一次被打爆了，某模拟赛又见了一次，所以来仔细研究了一下.
两个等价的问题：每次把一行或一列染黑或染白求可行局面个数；定义两个矩形等价为它们每行每列的和都相同，求大小为 1 的等价类数量.
考虑用二分图来处理，左部点代表行，右部点代表列，如果 (i,j) 的格子是黑色那么就从第 i 行向第 j 列连边，否则从第 j 列向第 i 行连边，那么这样子左右任意两个点之间都有连边. 我们需要注意到这张图的一些性质:
- 如果有环，那么一定存在一个四元环（对于更大的环，在中间的连边一定会产生一个更小的环）
- 一个矩阵满足限制当且仅当对应的二分图无环
- 如果无环，那么一定是分层图，每层是一些行或一些列，行列交替出现
于是我们来枚举有 x 个行的层和 y 个列的层，显然 |x-y|\leq 1，那么我们要把 n 行划分到 x 个行等价类中，这个方案数是 x!\begin{Bmatrix}n\\x\end{Bmatrix}. 那么我们就可以写出答案的表达式:
\sum_{i\geq 0}i!(i+1)!\begin{Bmatrix}n\\i\end{Bmatrix}\begin{Bmatrix}m\\i+1\end{Bmatrix}+\sum_{i\geq 0}(i+1)!i!\begin{Bmatrix}n\\i+1\end{Bmatrix}\begin{Bmatrix}m\\i\end{Bmatrix}+\sum_{i\geq 0}i!i!\begin{Bmatrix}n\\i\end{Bmatrix}\begin{Bmatrix}m\\i\end{Bmatrix}+\sum_{i\geq 1}i!i!\begin{Bmatrix}n\\i\end{Bmatrix}\begin{Bmatrix}m\\i\end{Bmatrix}
我们可以稍加整理得到
\sum_{i\geq 0}(i!)^2\begin{Bmatrix}n+1\\i+1\end{Bmatrix}\begin{Bmatrix}m+1\\i+1\end{Bmatrix}
对 n,m 建立 BGF 就有
\begin{aligned}
&\sum_{n\geq 0}\sum_{m\geq 0}\frac{x^ny^m}{n!m!}f_{n,m}\\
=&\sum_{i\geq 0}\left(\sum_{n\geq 0}i!\begin{Bmatrix}n+1\\i+1\end{Bmatrix}\frac{x^n}{n!}\right)\left(\sum_{m\geq 0}i!\begin{Bmatrix}m+1\\i+1\end{Bmatrix}\frac{y^m}{m!}\right)\\
=&\sum_{i\geq 0}e^x(e^x-1)^ie^y(e^y-1)^i\\
=&\frac{e^xe^y}{1-(e^x-1)(e^y-1)}\\
=&\frac{1}{e^{-x}+e^{-y}-1}
\end{aligned}
我们可以稍加变形得到另一个计算式:
\begin{aligned}
&\frac{1}{e^{-x}+e^{-y}-1}\\
=&\frac{e^x}{1-e^x(1-e^{-y})}\\
=&\sum_{i\geq 0}e^{x(i+1)}(1-e^{-y})^i\\
=&\sum_{n,m\geq 0}\frac{x^n}{n!}\frac{y^m}{m!}\sum_{i\geq 0}(i+1)^n(-1)^{i+m}i!\begin{Bmatrix}m\\i\end{Bmatrix}
\end{aligned}
这就给出了
f_{n,m}=\sum_{i\geq 0}(i+1)^n(-1)^{i+m}i!\begin{Bmatrix}m\\i\end{Bmatrix}
我们还可以不展开 y 来看一下每个 n 对应的 y 的生成函数:
\sum_{n\geq 0}\frac{x^n}{n!}\sum_{i\geq 0}(i+1)^n(1-e^{-y})^i
我们记
F_n(y)=\sum_{i\geq 0}(i+1)^n(1-e^{-y})^i
我们可以得到 F_n(y) 和 F_{n-1}(y) 之间的递推关系：
\left((1-e^{-y})F_{n-1}(y)\right)'=e^{-y}F_n(y)
也就是
F_n(y)=F_{n-1}(y)+(e^y-1)F_{n-1}'(y)
展开它我们就能得到
f_{n,m}=f_{n-1,m}+\sum_{i=0}^{m-1}\binom{m}{i}f_{n-1,i+1}
这就解决了之前遗留下来的若干问题 虽然感觉还有更多的东西可以发现(