2岐阜大学 2021年 数学 第2問解答・解説

縦に隣り合う席は同時に選べないから、各列の選択数は0または1である。選択数1の列を占有列とする。占有列が連続する極大区間を1つ固定すると、その区間の最初の列で上段・下段のどちらを選ぶかの2通りを決めれば、同じ段の左右隣席を選ばないため残りの段は交互に定まる。空列をはさんだ区間どうしには制約がない。したがって、占有列の連続区間数をrとすると、固定した占有パターンから得られる選び方は$2^r$通りである。

(1) $k=n$では空列がなく、1区間なので$2^1=2$。

(2) $k=n-1$では空列は1つ。指定列$n-1$が空列で、$n\geq3$より占有区間は$1,\ldots,n-2$と$n$の$2$区間だから$2^2=4$。

(3) 空列が端の2位置のいずれかなら$r=1$で各$2$通り。空列が内部の$n-2$位置のいずれかなら$r=2$で各$4$通り。よって$2\cdot2+(n-2)\cdot4=4n-4$。

(4) 空列$2$つの場合、$r=1$となる位置の組は$(1,2),(1,n),(n-1,n)$の$3$組で、寄与は$3\cdot2=6$。$r=2$となる組は、端の$1$位置とそれに隣接しない内部位置を空ける$2(n-3)$組、および内部の隣り合う$2$位置を空ける$n-3$組で、寄与は$3(n-3)\cdot4$。$r=3$となる組は、内部位置$n-2$個から隣り合わない$2$位置を選ぶ$\displaystyle \binom{n-2}{2}-(n-3)=\frac{(n-3)(n-4)}2$組で、寄与は$\displaystyle 8\cdot\frac{(n-3)(n-4)}2$。合計は$6+12(n-3)+4(n-3)(n-4)=4n^2-16n+18$.