Hoán vị, chỉnh hợp, tổ hợp

Điền k vị trí có thứ tự lần lượt, với số đối tượng còn đủ điều kiện giảm một sau mỗi vị trí, chính là bối cảnh của quy tắc nhân cho các bước liên tiếp độc lập.

Bước 1 (thiết lập các vị trí): gọi tên $k$ vị trí cần điền, theo thứ tự, là vị trí 1 đến vị trí $k$. Điền mỗi vị trí bằng một trong $n$ đối tượng, không dùng lại đối tượng đã đặt, là một công việc gồm $k$ bước liên tiếp.

Bước 2 (áp dụng quy tắc nhân): vị trí 1 có thể điền theo $n$ cách. Sau khi điền, một đối tượng đã dùng, nên vị trí 2 có $n-1$ cách, bất kể vị trí 1 đã chọn đối tượng nào. Tiếp tục như vậy, vị trí $k$ có $n-k+1$ cách, vì đã dùng $k-1$ đối tượng. Theo quy tắc nhân, tổng số cách là tích $n(n-1)\cdots(n-k+1)$.

Bước 3 (viết lại dưới dạng thương của giai thừa): nhân và chia cho phần đuôi bị thiếu $(n-k)!$ cho $n(n-1)\cdots(n-k+1) = \frac{n(n-1)\cdots(n-k+1)\cdot (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!}$, đúng là $A_n^k = \frac{n!}{(n-k)!}$.

Bước 4 (trường hợp riêng $k=n$): thay $k=n$ vào cho $A_n^n = \frac{n!}{0!} = \frac{n!}{1} = n!$ bằng cách dùng $0! = 1$, khôi phục lại số hoán vị $P_n = n!$.

Mỗi tập con không thứ tự cỡ k có thể biến thành một chỉnh hợp có thứ tự theo đúng k! cách, nên số đếm có thứ tự đếm lặp mỗi tập con cùng một hệ số k!; chia đi loại bỏ sự đếm lặ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)!}$.

Đây thực chất là quy tắc cộng: tách mọi tập con cỡ k theo việc chúng có chứa một phần tử cố định hay không cho hai trường hợp rời nhau, cộng lại đúng bằng tổng.

Bước 1 (cố định một phần tử và tách theo việc có chứa nó hay không): cố định một đối tượng $x$ trong $n$ đối tượng. Mỗi tập con $k$ phần tử hoặc chứa $x$ hoặc không chứa; hai trường hợp này rời nhau và cùng nhau phủ hết $C_n^k$ tập con.

Bước 2 (đếm tập con chứa x): một tập con chứa $x$ được tạo bằng cách chọn $k-1$ phần tử còn lại từ $n-1$ đối tượng kia, cho $C_{n-1}^{k-1}$ tập con như vậy.

Bước 3 (đếm tập con không chứa x): một tập con không chứa $x$ được tạo bằng cách chọn cả $k$ phần tử từ $n-1$ đối tượng còn lại, cho $C_{n-1}^k$ tập con như vậy.

Bước 4 (áp dụng quy tắc cộng): vì hai trường hợp rời nhau và phủ hết mọi tập con cỡ k, quy tắc cộng cho $C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$.