Erdös-Ko-Radoの定理

選ぶ全ての部分集合に $1$ が含まれていれば自動的に条件は満たされる。

よって，$\{2,3,\cdots, n\}$ から要素数 $k-1$ の部分集合を全て選び（選び方は ${}_{n-1}\mathrm{C}_{k-1}$ 通り）それに $1$ を追加したものたちを考えればよい。

選んだ一つの区間の数字を。 $a_1,a_2,\cdots, a_k$ とする。他の選んだ区間はその区間をまたぐ必要があり，（$1\leq i\leq k-1$ なる $i$ が存在して）$a_i$ と $a_{i+1}$ の間に境界がないといけない。

$a_i$ と $a_{i+1}$ の間を境界とする長さ $k$ の区間は二つあるが，$n\geq 2k$ よりそれらは共通元を持たないのでどちらか一つしか選べない。よって，最初に選んだ区間以外に選べるのは最大で $k-1$ 個なので全部で選べる区間の数は $k$ 個以下。

「 ${1,2,\cdots, n}$ の円周上への並べ方」と「選んだ部分集合でその円周のとある区間に対応しているもの」のペア $P$ がいくつあるかを二通りの方法で数える。

（例えば，$n=4,k=2$ で部分集合の中で $\{1,2\}$ と $\{2,3\}$ を選んだとき，上記のペアは図の赤丸と青丸に対応している。この丸の数を二通りの方法で数える。)

・「円順列それぞれに対してペアの数を数える」

まず，円周上への並べ方は全部で $(n-1)!$ 通り。補題により一つの並べ方に対して選べる区間の数は最大で $k$ 個なので，ペア $P$ の数は $(n-1)!k\:$ 以下。

・「赤丸と青丸を別々に数える」：

選んだ部分集合は $N$ 個あり。一つの部分集合に対して，それがとある区間となるような円周上への並べ方は全部で $k!(n-k)!$ 通りである。よって，ペア $P$ の数は $k!(n-k)!N$

以上から，$k!(n-k)!N\leq (n-1)!k$ となる。これを変形すると，$N\leq {}_{n-1}\mathrm{C}_{k-1}$ を得る。