二項係数の正体 ― nCrはなぜこんなに万能なのか

パスカルの三角形，格子経路，二項定理を通じて二項係数の多面的な姿を解説します．mod p での高速計算（階乗テーブル＋逆元）や Lucas の定理など，競プロで必須の知識も扱います．

2026年2月27日

二項係数 $(r n)$ は「 $n$ 個から $r$ 個選ぶ」という素朴な意味をもつ数ですが，数学のあらゆる場面に顔を出します．パスカルの三角形，格子経路，二項定理，そして競プロの mod 演算まで ― なぜ $(r n)$ はこんなにも万能なのでしょうか？

1 二項係数の定義と基本性質

定義 1 (二項係数).

非負整数

n, r

（

0 \leq r \leq n

）に対して，二項係数を

(r n) = \frac{n !}{r ! ( n - r )!}

と定義します．

r > n

のときは

(r n) = 0

とします．

注意 2.

(r n)

が常に整数であることは，定義からは自明ではありません．しかし組合せ的意味（

n

個から

r

個選ぶ方法の数）を考えれば，整数でなければならないことは明らかです．この「代数的には非自明だが組合せ的には自明」という現象は，二項係数の面白い特徴です．

2 パスカルの恒等式 ― 二項係数の再帰構造

定理 3 (パスカルの恒等式).

1 \leq r \leq n - 1

のとき，

(r n) = (r - 1 n - 1) + (r n - 1)

が成り立ちます．

証明.

n

個の要素の中から特定の要素

x

を1つ固定します．

r

個の部分集合は，

x

を含むものと含まないものに分類されます．

x

を含む部分集合の数は，残り

n - 1

個から

r - 1

個を選ぶので

(r - 1 n - 1)

通りです．

x

を含まない部分集合の数は，残り

n - 1

個から

r

個を選ぶので

(r n - 1)

通りです．

この2つの場合は互いに素なので，加法原理より

(r n) = (r - 1 n - 1) + (r n - 1)

です． □

注意 4.

この恒等式からパスカルの三角形が構成されます．各行が

(0 n), (1 n), \dots, (n n)

で，各数が左上と右上の和です．パスカルの三角形は二項係数のテーブルであり，漸化式を使ったDPテーブルそのものでもあります．

3 格子経路との対応

定理 5 (格子経路の数).

(0, 0)

から

(a, b)

への最短格子経路（右と上にのみ移動）の数は

(a a + b)

です．

証明.

最短経路は，右に

a

回，上に

b

回移動する列です．全

a + b

回の移動のうち，「右」の

a

回をどこに配置するかで経路が決まるので，

(a a + b)

通りです． □

例 6.

(0, 0)

から

(3, 2)

への最短格子経路は

(3 5) = 10

通りです．例えば「右右上右上」「上右右右上」などがあります．

注意 7.

格子経路の解釈は強力です．パスカルの恒等式は，

(a, b)

に到達するには

(a - 1, b)

（左から来る）か

(a, b - 1)

（下から来る）のどちらかであることに対応しています．

4 二項定理

定理 8 (二項定理).

任意の

x, y

と非負整数

n

に対して，

(x + y)^{n} = r = 0 \sum n (r n) x^{r} y^{n - r}

が成り立ちます．

証明.

(x + y)^{n} = (x + y) (x + y) \dots (x + y)

を展開するとき，

n

個の因子それぞれから

x

か

y

を1つ選んで掛け合わせます．

x^{r} y^{n - r}

の項が現れるのは，

n

個の因子のうち

r

個から

x

を選ぶ場合で，その選び方は

(r n)

通りです． □

例 9 (特殊値).

x = y = 1

を代入すると

\sum_{r = 0}^{n} (r n) = 2^{n}

（

n

元集合の部分集合の総数）．

x = 1, y = - 1

を代入すると

\sum_{r = 0}^{n} (- 1)^{r} (r n) = 0

（偶数個選ぶ場合と奇数個選ぶ場合が同数）．

5 mod $p$ での高速計算

競プロでは $(r n) mod p$ （ $p$ は素数，典型的に $p = 1 0^{9} + 7$ ）を高速に求める場面が頻出します．

注意 10 (階乗テーブル + 逆元).

以下の前処理を

O (n)

で行います：

階乗テーブル： $fact [i] = i! mod p$ を $i = 0, 1, \dots, n$ について計算
逆元テーブル： $inv_fact [i] = (i!)^{- 1} mod p$ を計算（フェルマーの小定理 $a^{p - 1} \equiv 1 (mod p)$ より $a^{- 1} \equiv a^{p - 2} (mod p)$ ）

すると

(r n) \equiv fact [n] \cdot inv_fact [r] \cdot inv_fact [n - r] (mod p)

で

O (1)

で計算できます．

6 Lucas の定理

定理 11 (Lucas の定理).

p

を素数とし，

n

と

r

を

p

進展開して

n = \sum n_{i} p^{i}

，

r = \sum r_{i} p^{i}

とすると，

(r n) \equiv i \prod (r _{i} n _{i}) (mod p)

が成り立ちます．

注意 12.

Lucas の定理は

n

が非常に大きい（

n > 1 0^{18}

など）が

p

が小さい場合に使えます．各桁の二項係数は

p

未満の値なので前処理なしで計算可能です．ただし

p

が大きい場合は階乗テーブル法の方が実用的です．

7 まとめ

二項係数は「選ぶ」以外にも格子経路・多項式展開・集合分割など多様な顔をもちます
パスカルの恒等式は再帰構造（＝DP）の源泉です
二項定理は代数と組合せ論の橋渡しです
mod $p$ での計算は階乗テーブル + 逆元が基本，大きい $n$ には Lucas の定理を使います

次の記事では，「足して引いて」を繰り返す不思議な原理 ― 包除原理の本質に迫ります．

組合せ論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 フォロワー·105 記事

二項係数の正体 ― nCrはなぜこんなに万能なのか

1 二項係数の定義と基本性質

2 パスカルの恒等式 ― 二項係数の再帰構造

3 格子経路との対応

4 二項定理

5 mod $p$ での高速計算

6 Lucas の定理

7 まとめ

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

1 二項係数の定義と基本性質

2 パスカルの恒等式 ― 二項係数の再帰構造

3 格子経路との対応

4 二項定理

5 modpでの高速計算

6 Lucas の定理

7 まとめ

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

5 mod $p$ での高速計算