組合せの公式(定理)

第1段階(部分順列を元の部分集合ごとにまとめる):$n$ 個から $k$ 個を選ぶ部分順列はそれぞれ、まずある $k$ 個の部分集合を選び、それを並べ替えたものである。$A_n^k$ 個の部分順列を、可能な $k$ 個の部分集合ごとに1つのグループにまとめ、2つの部分順列が同じ対象の集合を使うときにちょうど同じグループに入るようにする。

第2段階(各グループの大きさ):ある $k$ 個の部分集合を1つ固定すると、それから作られる部分順列はその部分集合の並べ方にちょうど対応し、そのような並べ方は $k!$ 通りある($k$ 個の対象の順列)。したがって各グループはちょうど $k!$ 個の部分順列を持つ。

第3段階(グループにわたる加法の法則):各グループは互いに素であり(1つの部分順列はちょうど1つのグループに属す)、定義によりグループは $C_n^k$ 個あり、それぞれの大きさは $k!$ である。加法の法則($k!$ を $C_n^k$ 回足し合わせる)により $A_n^k = C_n^k \cdot k!$ が得られる。

第4段階(組合せの数について解く):両辺を $k!$ で割り、$A_n^k = \frac{n!}{(n-k)!}$ を代入すると $C_n^k = \dfrac{A_n^k}{k!}$、すなわち $C_n^k = \frac{n!}{k!(n-k)!}$ が得られる。