【数IA場合の数】C の性質と素数の関係(九州大2021理系第5問)

以下の問いに答えよ。（九州大2021）

(1) 自然数 $n,k$ が $2\leqq k\leqq n-2$ をみたすとき，$_n\text{C}_k>n$ であることを示せ。

(2) $p$ を素数とする。$k\leqq n$ をみたす自然数の組 $(n,k)$ で $_n\text{C}_k=p$ となるものをすべて求めよ。

分母と分子をずらしてみる

(1)から始めます。

まず，C の具体的な形を考えてみましょう。

たとえば，$_6\text{C}_3$ なら

$\cfrac{6\cdot5\cdot4}{3\cdot2\cdot1}$

となります。

これを，$n,k$ を使って表すと

$_n\text{C}_k=\cfrac{n\times(n-1)\times(n-2)\times\cdots\times(n-k+1)}{k\times(k-1)\times(k-2)\times\cdots\times1}$

となります。

$2\leqq k\leqq n-2$ ・・・①　より

$k\leqq n-2$ となるので，これをもとに分母と分子を 2 つずらして式を書いてみます。

$=\cfrac{n}{1}\times\cfrac{n-1}{1}\times\cfrac{n-2}{k}\times\cfrac{n-3}{k-1}\times\cdots\times\cfrac{n-k+1}{3}\times\cfrac{1}{2}\times\cfrac{1}{1}$

こうしてみると，上の不等式の関係から

$\cfrac{n-2}{k}\geqq1$，$\cfrac{n-3}{k-1}\geqq1$，…，$\cfrac{n-k+1}{3}\geqq1$

が成り立ちます。

よって，式の残りの部分との不等式は

$\cfrac{n(n-1)}{2}\leqq_n\text{C}_k$

となります。

今度は，①から

$2\leqq n-2$

が成り立つので

$3\leqq n-1$
$\cfrac{3}{2}\leqq\cfrac{n-1}{2}$

よって

$1\leqq\cfrac{n-1}{2}$

が成り立ちます。これより

$n\leqq\cfrac{n(n-1)}{2}$

が成り立つので

$n\leqq\cfrac{n(n-1)}{2}\leqq _n\text{C}_k$

$n\leqq_n\text{C}_k$　（証明終わり）

C と素数の関係

(2)に進みます

$_n\text{C}_k=p$ として，いくつかパターンを考えてみます。

たとえば，$n=6$ とすると，$k$ は自然数だから，$_6\text{C}_1,\space_6\text{C}_2,\space_6\text{C}_3,\space_6\text{C}_4,\space_6\text{C}_5,\space_6\text{C}_6$ について考えることになります。

まず，$_6\text{C}_1=6$ だから，$k=1$ のとき，$_n\text{C}_1=n$ が成り立ちます。

よって，$_p\text{C}_1=p$ が成り立つので

$(n,k)=(p,1)$

次に，$_6\text{C}_5=_6\text{C}_1=6$ となるので，$k=n-1$ のときも，上と同じことが成り立ちます。

よって，

$(n,k)=(p,p-1)$

最後について考えると，$_6\text{C}_6=1$ だから，$n=k$ のとき $_n\text{C}_k=1$ が成り立ちます。しかし，1 は素数ではないので，$n=k$ は不適です。

あとは，$\space_6\text{C}_2,\space_6\text{C}_3,\space_6\text{C}_4$ のパターンが残りました。これは (1) の不等式 $2\leqq k\leqq n-2$ の場合ということです。

(1)より

$_n\text{C}_k=p>n$

$p>n$

となります。

ここで

$p=_n\text{C}_k=\cfrac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$

とすると

$pk!=n(n-1)(n-2)\cdots(n-k+1)$

となります。

このとき，$p>n$ の条件から，式の右辺は $p$ より小さい自然数の積であり，素数 $p$ を因数に含みません。

よって，恒等式は成立しません。

したがって

$(n,k)=(p,1),(p,p-1)$ （答え）