東京大学 1981年度 前期日程 第2次学力試験理系数学 第1問

まず $2k>n$ のときは、互いに交わらない2要素集合を $k$ 個作るための元が足りないので $f(n,k)=0$ である。以下 $2k\leqq n$ とする。

互いに交わらない2要素部分集合を $k$ 個選ぶには、まず $S$ から使う $2k$ 個の元を選ぶ。選んだ $2k$ 個を2個ずつの組に分ける方法は ${\displaystyle \frac{(2k)!}{2^{k}k!}}$ 通りである。したがって$$f(n,k)={}_n{\mathrm{C}}_{2k}{\displaystyle \frac{(2k)!}{2^{k}k!}}={\displaystyle \frac{n!}{(n-2k)!2^{k}k!}}$$である。

また $$f(n,1)={}_n{\mathrm{C}}_2={\displaystyle \frac{n(n-1)}{2}}$$ である。$k\geqq 2$ で $f(n,k)=f(n,1)$ とすると、$2k\leqq n$ でなければならず、両辺を整理して $${\displaystyle \frac{(n-2)!}{(n-2k)!}}=2^{k-1}k!$$ を得る。 $k=2$ のときは $(n-2)(n-3)=4$ である。しかし $n\geqq 4$ なので左辺は $2\cdot 1=2$, $3\cdot 2=6$, $4\cdot 3=12$, $\dots$ と増加し、4にはならない。したがって解はない。 $k=3$ のときは $(n-2)(n-3)(n-4)(n-5)=24$ である。$n\geqq 6$ であり、$n=6$ のとき左辺は $4\cdot 3\cdot 2\cdot 1=24$ となる。$n\geqq 7$ では左辺はこれより大きいので、解は $n=6$ だけである。

最後に $k\geqq 4$ を考える。$n\geqq 2k$ だから$${\displaystyle \frac{(n-2)!}{(n-2k)!}}\geqq (2k-2)!$$である。ここで$$R_k={\displaystyle \frac{(2k-2)!}{2^{k-1}k!}}$$とおくと、$R_4=15\mathrm{/}4>1$ であり、$${\displaystyle \frac{R_{k+1}}{R_k}}={\displaystyle \frac{(2k)(2k-1)}{2(k+1)}}={\displaystyle \frac{k(2k-1)}{k+1}}>1(k\geqq 4)$$である。したがって $(2k-2)!>2^{k-1}k!$ がすべての $k\geqq 4$ で成り立ち、等式は不可能である。

以上より、求める組は $(n,k)=(6,3)$ だけである。

1組目、2組目と順に2要素集合を選び、最後に組を選んだ順序 $k!$ を除く。
得られる積の式から $f(n,k)=f(n,1)$ を調べる。

$k$ 個の組に仮の順序を付けて選ぶと$${}_n{\mathrm{C}}_2{}_{n-2}{\mathrm{C}}_2\cdots {}_{n-2k+2}{\mathrm{C}}_2$$通りである。同じ $k$ 組が $k!$ 回ずつ現れるから$$f(n,k)={\displaystyle \frac{{}_n{\mathrm{C}}_2{}_{n-2}{\mathrm{C}}_2\cdots {}_{n-2k+2}{\mathrm{C}}_2}{k!}}={\displaystyle \frac{n!}{(n-2k)!2^{k}k!}}\mathrm{.}$$ただし $2k>n$ では $f(n,k)=0$ である。

$f(n,k)=f(n,1)$ は$$(n-2)(n-3)\cdots (n-2k+1)=2^{k-1}k!$$と同値である。$k=2$ では $(n-2)(n-3)=4$ に整数解はない。
$k=3$ では$$(n-2)(n-3)(n-4)(n-5)=24$$となり、$n=6$ だけが解である。

$k\geqq 4$ では左辺は $n=2k$ のときでも $(2k-2)!$ 以上である。$${\displaystyle \frac{(2k-2)!}{2^{k-1}k!}}$$は $k=4$ で $15\mathrm{/}4>1$、さらに $k$ とともに増加するので等式は不可能である。
よって$$(n,k)=(6,3)$$だけである。