MathLabs

第5题

设 nn 为正整数。有 n(n+1)n(n+1) 个房间排成一个 (n+1)×n(n+1)\times n 的方格阵。每两个相邻房间之间有一扇门。求选取一个门的子集并将其锁上的方法数，使得存在两个房间 SS 与 GG 满足： (i) SS 在第一行，GG 在第 (n+1)(n+1) 行。 (ii) 只用未锁的门就能从 SS 到达 GG。
第 5/5 步：恢复自由的门以完成计算
上一步下一步
answer=2 n2+(n−1)2−1⋅22(n−1)=22n2−2\text{answer}=2^{\,n^2+(n-1)^2-1}\cdot 2^{2(n-1)}=2^{2n^2-2}
详细分析

G\mathcal{G} 的边上 2 n2+(n−1)2−12^{\,n^2+(n-1)^2-1} 种可达的上锁方式，都可与第一行、最后一行内部门的 22(n−1)2^{2(n-1)} 种上锁方式（第一步）自由组合，因为那些门不影响 AA 与 BB 是否连通。由此得到使首行某房间能到达末行某房间的上锁方式共有 22n2−22^{2n^2-2} 种。