1981年(昭和55年)東京大学-数学(理科)[1] - [別館]球面倶楽部零八式markIISR

2023.08.22記

[1] $\textsf{S}=\{1,\,2,\,\cdots\cdots,\,n\}$ ，ただし $n\geqq2$ ，とする． $2$ つの要素から成る $\textsf{S}$ の部分集合を $k$ 個とり出し，そのうちのどの2つも交わりが空集合であるようにする方法は何通りあるか．

つぎに，この数（つまり何通りあるかを表す数）を $f(n,k)$ で表したとき， $f(n,k)=f(n,1)$ をみたすような $n$ と $k$ （ただし， $k\geqq2$ ）をすべて求めよ．

2020.11.25記
難しそうに見えるけど， $n$ 人からペアを $k$ 個取り出すというだけの話．

[解答]
$2k\gt n$ のとき $0$ ，
$2k\leqq n$ のとき $\dfrac{n(n-1)}{2}\times\cdots\times\dfrac{(n-2k+1)(n-2k)}{2}÷k!$
$=\dfrac{{}_n\mbox{P}_{2k}}{2^k\times k!}$
となる．

ここで $f(n,k)=f(n,1)$ となるのは
$\dfrac{{}_n\mbox{P}_{2k}}{2^k\times k!}＝\dfrac{n(n-1)}{2}$
から ${}_{n-2}\mbox{P}_{2k-2}=2^{k-1}k!$ となるときである．

ここで $n-2 \geqq 2k-2$ だから，
${}_{n-2}\mbox{P}_{2k-2}$
$\geqq (2k-2)\times (2k-3)\times (2k-4)\times (2k-6)\times\cdots\times 2$
$=2^{k-1}(2k-3)\times (k-1)!$
となるので
$2^{k-1}k!\geqq 2^{k-1}(2k-3)\times (k-1)!$
つまり
$k\geqq 2k-3\Leftrightarrow k\leqq 3$
が必要である．