第5問

$S$ は第 1 行の任意の部屋、$G$ は最終行の任意の部屋でよいので、適当な組が存在するかどうかは、第 1 行内の部屋を結ぶ $n-1$ 個の扉、および最終行内の $n-1$ 個の扉が施錠されているかどうかには依らない。そのような自由な扉は合計 $2(n-1)$ 個ある。第 1 行を一つの頂点 $A$ に、最終行を一つの頂点 $B$ につぶすと、残りの部屋と扉はグラフ $\mathcal{G}$ をなし、辺は $n^2+(n-1)^2$ 個であり、問題はこれらの辺の部分集合 $H$ のうち $A$ と $B$ が $H$ で連結であるものを数えることに帰着する。