近年の大学入試を母関数で斬る！！(1)二項係数編

近年の東大入試に頻出！二項係数の合同式を「母関数」でエレガントに解く

大学入試の整数問題、特に二項係数の性質を問う問題は、多くの受験生を悩ませるテーマの一つです。一見すると複雑な合同計算や組み合わせ論的考察が必要に思えますが、「母関数」という統一的な視点を用いることで、驚くほど見通しよく解けることがあります。
今回は、近年の東京大学の入試で出題された問題や、その類題・予想問題を通して、母関数を用いたエレガントな解法を紹介します。

対象となる問題

まずは、今回取り上げる問題を見てみましょう。異なる年度に出題されていますが、実はすべて同じ根っこを持つ問題です。

今回はこれらの問題をすべて「p進法と母関数」という統一的な方針で解いていきます。

母関数とは？

まず、このアプローチの主役である「母関数」を定義します。

難しく聞こえるかもしれませんが、要は数列を一つの多項式（または級数）で表現する道具です。これにより、数列という離散的な対象を、多項式という代数的で連続的な対象として扱えるようになり、計算の見通しが格段に良くなります。

二項係数と母関数

では、二項係数 ${}_nC_k$ の母関数は何でしょうか。これはまさに、高校数学で学ぶ二項定理そのものです。
数列 $\{ {}_nC_0, {}_nC_1, \dots, {}_nC_n \}$ の母関数は、
$$ (1+x)^n = \sum_{k=0}^{n} {}_nC_k x^k $$
となります。つまり、多項式 $(1+x)^n$ を展開したときの $x^k$ の係数が ${}_nC_k$ に対応するのです。
この考え方を用いると、${}_nC_k$ を $p$ で割った余りを調べたいという整数問題は、多項式 $(1+x)^n$ を法 $p$ で考え、その係数を調べたいという多項式の合同式の問題に変換できます。これが我々の基本方針です。

応用の方針：p進法との融合

法 $p$ の世界では、多項式は普段とは少し違う振る舞いをします。特に重要なのが、素数 $p$ を法とするときの次の性質です。

となります。

このように、非常に強力な関係式が得られます。（これは1999年や2026年予想問題の(1)そのものです）
この式と、指数の $p$ 進法展開 を組み合わせるのが、問題を解く鍵となります。例えば、$n$ を $p$ 進法で $n = n_d p^d + \dots + n_1 p + n_0$ と表すと、
$$ (1+x)^n = (1+x)^{n_d p^d} \cdots (1+x)^{n_1 p} (1+x)^{n_0} $$
と分解できます。これを法 $p$ で考えると、
$$(1+x)^n \equiv (1+x^{p^d})^{n_d} \cdots (1+x^p)^{n_1} (1+x)^{n_0} \pmod p $$
となり、係数の性質を調べることができます。

【解答】1999年 東大 問題

• 方針：$(1+x)^m \pmod 2$ の係数を調べる。
• 解法：
  法を2とすると、先ほどの強力な関係式より、
  $$ (1+x)^m = (1+x)^{2^k} \equiv 1+x^{2^k} = 1+x^m \pmod 2 $$
  この多項式の係数を見ると、$x^0$ と $x^m$ の係数は $1$ ですが、その間の $x^n$ ($0<n<m$) の係数はすべて $0$ です。
  ${}_mC_n$ は $(1+x)^m$ の $x^n$ の係数なので、${}_mC_n \equiv 0 \pmod 2$、すなわち ${}_mC_n$ は偶数です。

• 方針：$(1+x)^m \pmod 2$ の係数がすべて1になる条件を考える。
• 解法：
  条件は、多項式で表現すると、
  $$ (1+x)^m \equiv \sum_{n=0}^{m} 1 \cdot x^n = 1+x+x^2+\dots+x^m \pmod 2 $$
  となります。右辺は等比数列の和なので、$(1+x)$ を掛けると、
  $$ (1+x)^{m+1} \equiv (1+x)(1+x+\dots+x^m) = 1+x^{m+1} \pmod 2 $$
  (1)の考察から、この形が成り立つのは $m+1$ が2のべき乗のとき、すなわち $m+1=2^k$ のときです。
  よって、求める $m$ は $m=2^k-1$ ($k$ は自然数) の形で表される数です。これは2進法で書くと 11...1 と1が並ぶ数に対応します。

【解答】2015年 東大 問題

${}_{2015}C_m$ が偶数となる最小の自然数 $m$ を求めよ。

• 方針：$m=1, 2, 3, \dots$ と調べるとき、初めて ${}_{2015}C_m \equiv 0 \pmod 2$ となる $m$ を探す。これは、2015の2進法展開に関係する。
• 解法：
  2015 を2進法で表します。
  $2015 = 1024 + 991 = 1024 + 512 + 479 = \dots$
  $2015 = 1024+512+256+128+64+31 = 1024+512+256+128+64+16+8+4+2+1$
  $$ 2015 = 2^{10}+2^9+2^8+2^7+2^6+2^4+2^3+2^2+2^1+2^0 $$
  $$ 2015{(10)} = 11111011111{(2)} $$
  母関数を法2で考えると、
  $$ (1+x)^{2015} \equiv (1+x^{2^{10}})(1+x^{2^9})\cdots(1+x^{2^1})(1+x^{2^0}) \pmod 2 $$
  この右辺を展開したとき、 $x^m$ の係数が ${}_{2015}C_m$ になります。
  展開後の各項の係数はすべて1であり、同じ次数の項は現れません。
  ${}_{2015}C_m$ が奇数になるのは、$m$ が $2^0, 2^1, \dots, 2^{10}$ のうち、2015の2進展開に含まれるものの和で一意に書ける場合です。
  一方で、${}_{2015}C_m$ が偶数になるのは、そうでない場合です。
  最小の自然数 $m$ を探しているので、$m=1, 2, 3, \dots$ と見ていきましょう。
  • $m=1$: $1 = 2^0$ なので、${}_{2015}C_1 \equiv 1 \pmod 2$ (奇数)。
  • $m=2$: $2 = 2^1$ なので、${}_{2015}C_2 \equiv 1 \pmod 2$ (奇数)。
  • $m=3$: $3 = 2^1+2^0$ なので、${}_{2015}C_3 \equiv 1 \pmod 2$ (奇数)。
  • $m=4$: $4 = 2^2$ なので、${}_{2015}C_4 \equiv 1 \pmod 2$ (奇数)。
  • ...
  • $m=31$: $31=16+8+4+2+1$。これらは全て2015の2進展開に含まれるので奇数。
  • $m=32$: $32=2^5$。2015の2進展開には $2^5$ の項が含まれていません。したがって、右辺の展開で $x^{32}$ の項を作ることはできません。
    よって、${}_{2015}C_{32} \equiv 0 \pmod 2$ となります。
    したがって、求める最小の $m$ は 32 です。

【解答】2021年 東大 問題

• 方針：$(1+x)^{2021} \pmod 4$ を考え、$x^{37}$ の係数を求める。法が4なので少し複雑になる。
• 解法：
  まず、$(1+x)^{2^k} \pmod 4$ を考えます。
  $(1+x)^2 = 1+2x+x^2$
  $(1+x)^4 = (1+2x+x^2)^2 \equiv 1+4x+4x^2+2x^2+4x^3+x^4 \equiv 1+2x^2+x^4 \pmod 4$
  $(1+x)^8 \equiv (1+2x^2+x^4)^2 \equiv 1+2(2x^2)+x^8 \equiv 1+4x^2+x^8 \equiv 1+2x^4+x^8 \pmod 4$
  帰納的に、$k \ge 1$ で
  $$ (1+x)^{2^k} \equiv 1+2x^{2^{k-1}}+x^{2^k} \pmod 4 $$
  が示せます。
  $2021 = 1024+997 = 1024+512+485 = \dots$
  $2021 = 1024+512+256+128+64+32+4+1 = 2^{10}+2^9+2^8+2^7+2^6+2^5+2^2+2^0$
  $x^{37}$ の係数を考えたいのですが、$37 = 32+4+1$ です。
  $(1+x)^{2021}$ を法4で分解すると、
  $$ (1+x)^{2021} \equiv (1+2x^{512}+x^{1024})\cdots(1+2x^{16}+x^{32})(1+2x^2+x^4)(1+x) \pmod 4 $$
  ${}_{2021}C_{37}$は、この積を展開したときの $x^{37}$ の係数です。
  そのためこの積から $x^{37}=x^{32}x^4x^1$ を作る組み合わせを考えます。
  ここで、重要なポイントは、$x^{32}$ という指数を持つ項が、上記の積の中に2種類存在することです。

• $k=5$ の項 $(1+2x^{16}+x^{32})$ に含まれる「$x^{32}$」（係数 1）

• $k=6$ の項 $(1+2x^{32}+x^{64})$ に含まれる「$2x^{32}$」（係数 2）
  このため、$x^{37}$ を作る組み合わせは、次の2通りが考えられます。

組み合わせ①

この組み合わせでは、$k=0$ の項から $x^1$（係数 1）、$k=2$ の項から $x^4$（係数 1）、そして \textbf{$k=5$ の項から $x^{32}$（係数 1）} をそれぞれ選びます。その他の項からはすべて定数項 $1$ を選びます。 この組み合わせから得られる係数は $1 \times 1 \times 1 = \boldsymbol{1}$ です。

組み合わせ②

こちらの組み合わせでは、$k=0$ の項から $x^1$（係数 1）、$k=2$ の項から $x^4$（係数 1）、そして \textbf{$k=6$ の項から $2x^{32}$（係数 2）} を選びます。その他の項からはすべて定数項 $1$ を選びます。 この組み合わせから得られる係数は $1 \times 1 \times 2 = \boldsymbol{2}$ です。

$x^{37}$ の項は、これら2つの組み合わせの和として現れます。 したがって、${}_{2021}C_{37}$ を4で割った余りは、 $$ {}_{2021}C_{37} \equiv 1 + 2 = 3 \pmod 4 $$ となり、求める余りは$\boldsymbol{3}$です

【解答】2026年 予想問題

• 数学的帰納法で示します。
  • $k=0$ のとき、$(1+x)^1 \equiv 1+x^1$ で成立。
  • $k=j$ で成立を仮定、$(1+x)^{2^j} \equiv 1+x^{2^j} \pmod 2$
  • $k=j+1$ のとき、
    $(1+x)^{2^{j+1}} = ((1+x)^{2^j})^2 \equiv (1+x^{2^j})^2 = 1+2x^{2^j}+(x^{2^j})^2 \equiv 1+x^{2^{j+1}} \pmod 2$
    よって、すべての非負整数 $k$ で成立します。

• 2026を2進法で表します。
  $2026 = 1024+960+42 = 1024+512+256+128+64+32+8+2$
  $$ 2026 = 2^{10}+2^9+2^8+2^7+2^6+2^5+2^3+2^1 $$
  よって、(1)の結果から、
  $$ (1+x)^{2026} \equiv (1+x^{2^{10}})(1+x^{2^9})(1+x^{2^8})(1+x^{2^7})(1+x^{2^6})(1+x^{2^5})(1+x^{2^3})(1+x^{2^1}) \pmod 2 $$

• ${}_{2026}C_m$ が奇数 $\iff {}_{2026}C_m \equiv 1 \pmod 2$
• これは、(2)で得られた多項式の展開後の $x^m$ の係数が $1$ になることを意味します。
• (2)の右辺を展開すると、各項は異なる $x$ のべき乗の項となり、係数はすべて $1$ です。例えば、$x^{2^{10}+2^9}$ や $x^{2^3+2^1}$ などです。
• したがって、${}_{2026}C_m$ が奇数になる $m$ の個数は、(2)の右辺を展開したときの項の数と一致します。
• 右辺は、8個の $(1+x^k)$ という形の式の積です。展開後の項の数は、各因子から「1」か「$x^k$」のどちらかを選ぶ組み合わせの総数に等しくなります。
• よって、項の総数は $2 \times 2 \times \dots \times 2$ (8回) = $2^8$ です。
• 求める個数は 256個 となります。

まとめ

見てきたように、${}_nC_k \pmod p$ に関する問題は、母関数 $(1+x)^n$ を法 $p$ で考え、指数の $p$ 進法展開を利用することで、非常に見通しよく解くことができます。この方法は、個々の問題を場当たり的に解くのではなく、「二項係数とは、$(1+x)^n$ の展開係数である」という構造的な理解に基づいているため、応用範囲が広く強力です。
一見難解に見える整数問題も、適切な道具（視点）を持つことで、その美しい構造を解き明かすことができます。ぜひ、母関数という強力な武器を身につけてみてください。