Định lý công thức tổ hợp

Bước 1 (nhóm các chỉnh hợp theo tập con nền): mỗi chỉnh hợp chập $k$ của $n$ đối tượng trước hết chọn ra một tập con $k$ phần tử rồi xếp thứ tự nó. Nhóm $A_n^k$ chỉnh hợp vào các nhóm, mỗi nhóm ứng với một tập con $k$ phần tử có thể có, sao cho hai chỉnh hợp cùng nhóm khi và chỉ khi chúng dùng cùng một tập đối tượng.

Bước 2 (cỡ mỗi nhóm): cố định một tập con $k$ phần tử, các chỉnh hợp dựng từ nó ứng đúng với các cách xếp thứ tự tập con đó, và có $k!$ cách xếp như vậy (một hoán vị của $k$ đối tượng). Vậy mỗi nhóm có đúng $k!$ chỉnh hợp.

Bước 3 (quy tắc cộng qua các nhóm): các nhóm rời nhau (một chỉnh hợp thuộc đúng một nhóm) và có $C_n^k$ nhóm theo định nghĩa, mỗi nhóm cỡ $k!$. Quy tắc cộng ($k!$ cộng với chính nó $C_n^k$ lần) cho $A_n^k = C_n^k \cdot k!$.

Bước 4 (giải ra số tổ hợp): chia cả hai vế cho $k!$ và thay $A_n^k = \frac{n!}{(n-k)!}$ vào cho $C_n^k = \dfrac{A_n^k}{k!}$, tức $C_n^k = \frac{n!}{k!(n-k)!}$.