場合の数

更新日時 2022/04/16

二項係数の有名公式一覧と2つの証明方針二項係数の有名公式を紹介し，それぞれ代数的な方法と組み合わせ的な方法で導きます。
特に3つ目の公式は整数問題にも応用することができる重要な公式です。
→ 二項係数の有名公式一覧と2つの証明方針

包除原理の２通りの証明

包除原理

$|A\cup B|=|A|+|B|-|A\cap B|$

$|A\cup B\cup C|\\ =|A|+|B|+|C|\\ -|A\cap B|-|B\cap C|-|C\cap A|\\ +|A\cap B\cap C|$

より一般に，

$|A_1\cup A_2\cup\cdots\cup A_n|$

$=\displaystyle\sum_{k=1}^n(-1)^{k-1}$ （ $k$ 個の「かつ」の総和）

$=\displaystyle\sum_{i}|A_i|-\sum_{i < j}|A_i\cap A_j|$

$+\sum_{i < j < k}|A_i\cap A_j\cap A_k|$

$-\cdots +(-1)^{n-1}|A_1\cap\cdots\cap A_n|$

→ 包除原理の２通りの証明

攪乱順列（完全順列）の個数を求める公式

$1, 2,\cdots, n$ を並び替えてできる順列のうち，全ての $i=1, 2, \cdots, n$ に対して $i$ 番目が $i$ でないものの個数 $a_n$ は，以下の式で表される：

$a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}$

→ 攪乱順列（完全順列）の個数を求める公式

ヴァンデルモンドの畳み込みの3通りの証明

ヴァンデルモンドの畳み込み

以下の恒等式が成立する：

$\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n$

ただし， $p < k$ のとき ${}_p\mathrm{C}_k=0$ と約束する。

→ ヴァンデルモンドの畳み込みの3通りの証明

カタラン数の意味と漸化式

カタラン数

$c_n=\dfrac{1}{n+1}{}_{2n}\mathrm{C}_{n}={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}$

で定義されるカタラン数は場合の数の問題で頻繁に登場する。

→ カタラン数の意味と漸化式

モンモールの問題の応用

1987年国際数学オリンピックキューバ大会の第一問の2通りの解法を紹介します。

問題

$p_n(k)$ を不動点をちょうど $k$ 個持つ $n$ 次の置換の数とする。

このとき， $\displaystyle\sum_{k=0}^nk\cdot p_n(k)=n!$ を証明せよ。

ただし， $n$ 次の置換とは，集合 $S=\{1,2,\cdots,n\}$ から $S$ への一対一対応であり， $f(i)=i$ を満たすとき $i$ を置換 $f$ の不動点と呼ぶ。

→ モンモールの問題の応用

同じものを含む円順列の裏技公式

同じものを含む円順列の個数はバーンサイドの公式を使って求めることができる。

円順列の個数 $=\dfrac{1}{|G|}\displaystyle\sum_{g\in G}\phi(g)$

→ 同じものを含む円順列の裏技公式

n本の直線の交点の数

問題

平面上に $n$ 本の直線を引くとき交点の数の最大値 $a_n$ を求めよ。

→ n本の直線の交点の数

スターリング数の漸化式と3つの意味第二種スターリング数
S(n,k)S(n,k)S(n,k)
 の同値な性質を3つ解説します。あまり馴染みのない数ですが美しい性質を持っています。
→ スターリング数の漸化式と3つの意味

分割数の意味と性質・ヤング図形の活躍

分割数：自然数 $n$ をいくつかの自然数の和で表す方法の数を $n$ の分割数と言う。

数え上げの有名な話題です。自然数の分割にまつわるごく基本的なこと。

→ 分割数の意味と性質・ヤング図形の活躍

全射の個数の証明とベル数

$n$ 人を区別のある（ちょうど） $k$ 個のチームに分ける場合の数は，

$\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n$

$k=2,\:3$ の問題は大学入試として適度な難易度です。覚える必要はありませんが，導出できるようになっておきましょう。

→ 全射の個数の証明とベル数

写像12相（場合の数の有名問題）nnn
 個の玉を
kkk
 個の箱に入れる場合の数を数える問題を考えます。状況によって12パターンの問題設定が考えられるので写像12相(Twelvefold way)と呼ばれている有名な問題です。
写像という言葉は知らなくても理解できる問題です。後半はかなり難しいので読めるとこまで読んでみてください。
→ 写像12相（場合の数の有名問題）

Erdös-Ko-Radoの定理

$n$ 個の要素からなる集合 $\{1,2,\cdots,n\}$ から要素数が $k$ の部分集合たちを以下の条件を満たすようにできるだけたくさん選びたい。

条件：選んだ部分集合のどの二つを選んでも共通元が存在する。

$n\geq 2k$ のとき，選べる部分集合の限界 $N$ は， $N={}_{n-1}\mathrm{C}_{k-1}$ 個である。

組み合わせの有名な定理です。証明は数学オリンピックの練習問題としては難し目ですが，非常にエレガントです。

→ Erdös-Ko-Radoの定理

Erdös Szekersの定理とその証明

Erdös--Szekeresの定理

$a,b$ を正の整数とする。各項が相異なる長さ $ab+1$ の数列があるとき，以下の二つのうち少なくとも一つは必ず存在する。

1：長さ $a+1$ の部分列で，単調増加なもの

2：長さ $b+1$ の部分列で，単調減少なもの

→ Erdös Szekersの定理とその証明

ニム（複数山の石取りゲーム）の必勝法ニム，山崩しゲーム，石取りゲームなどと呼ばれるゲームについて。ニムには2進法を用いた必勝法があります。
→ ニム（複数山の石取りゲーム）の必勝法

道順の場合の数を求めるテクニック定期試験や入試で頻出の「道順の場合の数を求める問題（最短経路問題）」について。有名なテクニックである書き込み方式について解説します。漸化式を使って場合の数を求める，動的計画法の入り口。
→ 道順の場合の数を求めるテクニック

偽物のコインと天秤の有名問題天秤を使って偽物（重さの異なる）のコイン（金貨ということもある）を見つけ出すという有名問題について紹介します。
→ 偽物のコインと天秤の有名問題

8パズル，15パズルの不可能な配置と判定法

8パズル，15パズルにおいて，完成した形から2枚のパネルの場所を交換した状態からスタートしても完成させることはできない。

→ 8パズル，15パズルの不可能な配置と判定法

パスカルの三角形の性質とフラクタル

パスカルの三角形において，偶数を0，奇数を1と書きなおしたものを考えると面白い規則性がある。

→ パスカルの三角形の性質とフラクタル

二項定理の意味と２通りの証明

二項定理

二項定理とは， $n$ 乗の式を展開するための以下のような公式のことです。

$(a+b)^n=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_ka^{n-k}b^{k}$

二項定理は見た目が少し複雑ですが，慣れてしまえば難しくありません。 二項定理の意味 と， 二項定理の2通りの証明 を解説します。

→ 二項定理の意味と２通りの証明

ランダムウォークの基礎（一次元，高校範囲）

確率 $\dfrac{1}{2}$ で $+1$ ポイント， $\dfrac{1}{2}$ で $-1$ ポイントとなるゲームを繰り返すような確率モデルを一次元ランダムウォークと言う。

ランダムウォークは入試にも頻繁に登場する＆現実の様々な現象の記述に使える重要なモデルです。

→ ランダムウォークの基礎（一次元，高校範囲）

重複組合せの公式と例題（玉，整数解の個数）

$n$ 種類のものから重複を許して $r$ 個選ぶ場合の数は ${}_n\mathrm{H}_r={}_{n+r-1}\mathrm{C}_r$ 通り。

→ 重複組合せの公式と例題（玉，整数解の個数）

テトリスのブロックの種類を数える問題テトリスのブロックの種類を列挙してみます！数え上げのよい練習問題。
→ テトリスのブロックの種類を数える問題

0の階乗を1と定義する理由

Q：なぜ $0!=1$ なのか？

A：そう定義すると都合がよいから。

→ 0の階乗を1と定義する理由

和の法則と積の法則（場合の数）と例題場合の数を数える基本的な考え方「和の法則」「積の法則」について解説します。
→ 和の法則と積の法則（場合の数）と例題

交代順列の数とタンジェント数，セカント数交代順列の数とタンジェント数，セカント数が等しいという感動的な定理について紹介します。
→ 交代順列の数とタンジェント数，セカント数

Isolation Lemmaとその証明

$\mathcal{F}$ を $E=\{e_1,\dots,e_n\}$ の部分集合族とする。

$E$ の各要素 $e_i$ に重み $w(e_i)$ を割り当てる。 $w(e_i)$ はそれぞれ独立に $\{1,\dots,N\}$ の中から一様ランダムに選ぶ。

$F\in \mathcal{F}$ の重みを $w(F)=\displaystyle\sum_{e\in F}w(e)$ と定義する。

このとき，確率 $1-\dfrac{n}{N}$ 以上で $\mathcal{F}$ の要素の中で重みを最小にするものはただ一つである。

離散最適化のややマニアックな定理を紹介します。

→ Isolation Lemmaとその証明

多項定理の例題と2通りの証明

多項定理

$(x_1+x_2+\cdots +x_k)^n$ を展開したときの $x_1^{e_1}x_2^{e_2}\cdots x_k^{e_k}$ の係数は

$e_1+e_2+\cdots +e_k=n$ かつ各 $e_i$ が非負なら $\dfrac{n!}{e_1!e_2!\cdots e_k!}$

（そうでないなら $0$ ）

多項定理は二項定理の拡張です（ $k=2$ のときは二項定理）。前半は具体例，後半は証明です。

→ 多項定理の例題と2通りの証明

二項係数の和，二乗和，三乗和二項係数の総和，二乗和，三乗和に関する美しい公式を解説します。
nnn
 は
000
 以上の任意の整数とします。
→ 二項係数の和，二乗和，三乗和

順列と組合せの違いと例題

順列：順番を区別する

組合せ：順番を区別しない

前半は順列，組合せの意味。後半は練習問題です。

→ 順列と組合せの違いと例題

円順列の公式と2通りの考え方

円順列の公式

異なる $n$ 個のものを円形に並べる方法の総数は $(n-1)!$ 通り

円順列について，意味・公式・2通りの考え方・例題を解説します。

→ 円順列の公式と2通りの考え方

この記事の編集者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！