MathLabs

第5問

nn を正の整数とする。(n+1)×n(n+1)\times n 型に並んだ n(n+1)n(n+1) 個の部屋がある。隣り合う二部屋の間には扉が一つある。扉の部分集合を選んで施錠し、次を満たす二部屋 SS、GG が存在するようにする方法の数を求めよ。 (i) SS は第 1 行、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 を、各ラベル付き辺について、その二つの添字を入れ替えた辺が HH に属さないときに限りその辺が f(H)f(H) に属する、として定義する。添字の入れ替えを二回行うと元の辺に戻り、否定を二回行うと元の所属関係に戻るので f(f(H))=Hf(f(H))=H となり、ff は対合である。