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。
第 2/5 步：构造转置-取补对合
上一步下一步
f(H):di,j∈f(H)  ⟺  dj,i∉H,ei,j∈f(H)  ⟺  ej,i∉H;f(f(H))=Hf(H):\quad d_{i,j}\in f(H)\iff d_{j,i}\notin H,\quad e_{i,j}\in f(H)\iff e_{j,i}\notin H;\qquad f(f(H))=H
详细分析

将 G\mathcal{G} 的边标记为对 1≤i,j≤n1\le i,j\le n 的 di,jd_{i,j} 与对 1≤i,j≤n−11\le i,j\le n-1 的 ei,je_{i,j}，以反映方格阵的行与列。在 G\mathcal{G} 的边子集上定义 ff：对每条带标记的边，规定其属于 f(H)f(H) 当且仅当把它的两个下标互换后得到的边不属于 HH。由于下标互换两次还原为原边、取反两次还原为原来的归属，故 f(f(H))=Hf(f(H))=H，即 ff 是一个对合。