【東京工業大学2021年度前期入試数学第3問】素数となるカタラン数

東工大の第3問はカタラン数に関する問題です。これも難しくはないですが、とらえどころのない問題です。

東京工業大学　本館
2011年5月19日、03撮影、Wikipediaより

問題

以下の問いに答えよ．

(1) 正の整数 n に対して，二幸係数に関する次の等式を示せ．

n × (2n)Cn = (n+1) × (2n)C(n-1)

(2) 正の整数 n に対して，
　　　a(n) = (2n)Cn / (n+1)
とおく．このとき，n ≧ 4 ならば a(n) > n + 2 であることを示せ．

(3) a(n) が素数となる正の整数 n をすべて求めよ．

(注) テキストではわかりにくいため、(1) の式に意図的に × の記号を入れています。また、(3) はいつものように a(n) の n は a の添え字です。

解答解説

(1) は何も考えずに式を書いていけばおしまいです。
・n × (2n)Cn = n × (2n)! / (n!)^2 = (2n)! / {(n-1)! × n!}
・(n+1) × (2n)C(n-1) = (n+1) × (2n)! / {(n-1)! × (n+1)!} = (2n)! / {(n-1)! × n!}
であるので、n × (2n)Cn = (n+1) × (2n)C(n-1) が成立します。また、n と n + 1 は互いに素であるので、(2n)Cn は n + 1 の倍数になります。

(2) は、a(n) > n + 2 を数学的帰納法で証明します。a(4) = (8C4)/5 = 8 × 7 × 6 × 5/(4 × 3 × 2 × 1 × 5) = 14 > 6 = 4 + 2 であるので、n = 4 のときは成立します。

k を 4 以上の任意の整数として、a(k) > k + 2 が成立しているならば a(k+1) > k + 3 が成立することを示します。

a(k+1) = (2k+2)C(k+1) / (k+2) = (2k+2)! / {(k+1)! × (k+1)! × (k+2)} = {(2k+2)(2k+1)/(k+1)(k+2)} × a(k) = {2(2k+1)/(k+2)} × a(k) > 2(2k+1)(k+2)/(k+2) = 2(2k+1) = 4k + 2

が成立します。ここで、2(2k+1)/(k+2) > 0 であることに注意してください。

したがって、k が 4 以上の整数であるので、(4k + 2) - (k + 3) = 3k - 1 > 0 となり、a(k+1) > 4k + 2 > k + 3 が成立します。

よって、n に関する数学的帰納法により、n ≧ 4 ならば a(n) > n + 2 が言えました。

(3) ですが、n が 5以上のときには (2) を使って a(n) が素数にならないことを示します。

k を 4 以上の整数とします。

(2) から a(k+1) = {2(2k+1)/(k+2)} × a(k) となります。(1) より a(k), a(k+1) は整数であるので、pq = k+2、2(2k+1)/p と a(k)/q がともに整数であるような正の整数p, q が存在します。

このとき、a(k+1) = {2(2k+1)/p} × {a(k)/q} と表されます。

ここで、k ≧ 4 であるので、2(2k+1) - (k+2) = 3k > 0 かつ a(k) > k + 2 より 2(2k+1)/p > 2(2k+1)/(k+2) > 1 かつ a(k)/q > a(k)/(k+2) > 1 となり、2(2k+1)/p と a(k)/p はともに 2 以上の整数であることから、a(k+1) は合成数となります。

よって、n ≧ 5 のとき、a(n) は素数にはなりません。

あとは n = 1, 2, 3, 4 について具体的に値を求めると、a(1) = 1, a(2) = 2, a(3) = 5, a(4) = 14 であるので、a(n) が素数となるのは n = 2, 3 のときのみとなります。

感想

問題にある数列 a(n) がカタラン数というやつで、例えば、n対の ( と ) からなる正しい系列(カッコ開くとカッコ閉じるが一対一に対応している系列)が a(n) 通りであることが知られています。

n = 1 のときは ( ) の1通り、
n = 2 のときは ( ) ( ) と ( ( ) ) の2通り、
n = 3 のときは ( ) ( ) ( )，( ) ( ( ) )，( ( ) ) ( )，( ( ) ( ) )，( ( ( ) ) ) の5通り。

カタラン数

他にもいろいろとあるようで、場合の数とカタラン数の関係を証明する問題も面白いとは思いますが、今回はカタラン数そのものの性質を問う問題でした。

さて、この問題ですが、(3) の a(n) が素数となる n を求めさせるのが主問題で、(1) と (2) はそのための誘導問題です。

(2n)Cn という数を考えてみると分かると思いますが、n が大きくなると多くの種類の因数を持ちます。ですので、a(n) が素数となる n は小さい数に限定されることが直感として分かるかと思います。

そう考えれば、(3) の答えも解き方も予想が付くと思います。実際、書き方はいろいろとありそうですが、(2) を使って n ≧ 5 のときをまとめて処理するという方針が基本となるでしょう。

全体として、この問題も誘導に沿っていけば難しい問題ではないと思います。しかも、第2問よりも計算量が少ないので、短時間で解答できるでしょう。

(3) がもしかすると悩ましいのかもしれませんが、個人的には難易度の点で歯ごたえのない問題でした。