Tổ hợp

Ta dùng tổ hợp khi chọn ra một số đối tượng từ một tập hợp các đối tượng, trong đó thứ tự chọn không có ý nghĩa. Bài toán điển hình là xổ số chọn 6 số từ 49 số: trong thùng quay có 49 số, người ta rút ra 6 số, và các số được rút theo thứ tự nào cũng như nhau.

Xây dựng công thức

Cho một tập hợp M, chẳng hạn M = {a; b; c; d; e}. Khi đó một tổ hợp chập k là một tập con K ⊆ M có đúng k phần tử. Vì K là một tập hợp nên tất nhiên thứ tự không có ý nghĩa. Như vậy một tổ hợp chập 3 của tập hợp M có thể là {a; b; d} hoặc {b; c; d}.

Điểm khác với chỉnh hợp là ở chỉnh hợp thứ tự có ý nghĩa, nên (a; b; e) và (e; b; a) là hai chỉnh hợp khác nhau; nhưng chúng là cùng một tổ hợp, vì (a; b; e) và (e; b; a) gồm cùng các phần tử. Với tổ hợp, ta không quan tâm các phần tử xếp theo thứ tự nào.

Tuy vậy, có thể dùng chỉnh hợp để tìm công thức tính số tất cả các tổ hợp khác nhau. Ta biết rằng số chỉnh hợp chập k của một tập hợp gồm n phần tử bằng

$${\mathrm{A}}_n^k=\frac{n!}{(n-k)!}.$$

Nếu tính số tất cả các chỉnh hợp chập 3 của tập hợp M = {a; b; c; d; e} ở trên, ta được ${\mathrm{A}}_5^3=60$ chỉnh hợp khác nhau. Nhưng trong đó, với mỗi bộ ba ta có cả tất cả các hoán vị của nó. Tức là ta có bộ ba abc, nhưng cũng có các bộ ba acb, bac, bca, cab và cba. Đó là 6 chỉnh hợp khác nhau, nhưng chỉ là một tổ hợp, vì chúng đều gồm cùng các phần tử.

Vậy với một bộ ba cho trước, có bao nhiêu hoán vị khác nhau của bộ ba đó? Đúng 3!. Nói cách khác, số chỉnh hợp chập 3 nhiều gấp đúng 3! lần số tổ hợp chập 3. Thay vì đếm một tổ hợp, ta đếm 3! chỉnh hợp, ứng với mỗi hoán vị của bộ ba đó. Do đó nếu chia số chỉnh hợp cho 3! thì được số tổ hợp.

Tổng quát hoá cách làm trên: nếu cần tìm số tất cả các tổ hợp chập k khác nhau của một tập hợp gồm n phần tử thì số đó, kí hiệu là ${\mathrm{C}}_n^k$, bằng

$${\mathrm{C}}_n^k=\frac{{\mathrm{A}}_n^k}{k!},$$

tức là số chỉnh hợp chia cho k!, số hoán vị của mỗi bộ k phần tử. Viết công thức tính số chỉnh hợp ra, ta biến đổi được:

$${\mathrm{C}}_n^k=\frac{{\mathrm{A}}_n^k}{k!}=\frac{n!}{(n-k)!}\cdot \frac{1}{k!}=\frac{n!}{(n-k)!\cdot k!}.$$

Ví dụ: số tổ hợp chập 2 của tập hợp {a; b; c} là

$${\mathrm{C}}_3^2=\frac{3!}{1!\cdot 2!}=3$$

và đó là các tổ hợp: {a; b}, {a; c} và {b; c}. Với các tổ hợp chập 3 của tập hợp ban đầu M = {a; b; c; d; e}, ta được số

$${\mathrm{C}}_5^3=\frac{5!}{(5-3)!\cdot 3!}=10$$

và đó là các tổ hợp: {a; b; c}, {a; b; d}, {a; b; e}, {a; c; d}, {a; c; e}, {a; d; e}, {b; c; d}, {b; c; e}, {b; d; e}, {c; d; e}.

Kí hiệu số tổ hợp

Sách giáo khoa Việt Nam viết số tổ hợp là ${\mathrm{C}}_n^k$, nhưng ở nước ngoài và ở bậc đại học còn thường gặp cách viết sau, gọi là hệ số nhị thức:

$$(\genfrac{}{}{0ex}{}{n}{k})$$

Kí hiệu này trông giống một phân số không có gạch ngang phân số (dù theo thói quen ta hay muốn vẽ thêm), nhưng có dấu ngoặc tròn (dấu ngoặc không được bỏ). Tiếng Anh đọc là “n choose k”. Giá trị của số này bằng ${\mathrm{C}}_n^k$:

$${\mathrm{C}}_n^k=\frac{n!}{(n-k)!\cdot k!}$$

Chẳng hạn nếu có một tập hợp gồm 5 phần tử và ta chọn ra các bộ 4 phần tử thì số các bộ đó là

$${\mathrm{C}}_5^4=\frac{5!}{1!\cdot 4!}=5.$$

Các hệ thức cơ bản

Với số tổ hợp và n ∈ ℕ^* ta có:

$$\begin{array}{rcl}{\mathrm{C}}_n^0={\mathrm{C}}_n^n={\mathrm{C}}_0^0& =& 1\\ {\mathrm{C}}_n^1& =& n\end{array}$$

Ngoài ra với n, k ∈ ℕ và k ≤ n ta có

$$\begin{array}{rcl}{\mathrm{C}}_n^{n-k}& =& {\mathrm{C}}_n^k.\end{array}$$

Và với n, k ∈ ℕ và k < n ta có

$$\begin{array}{rcl}{\mathrm{C}}_n^k+{\mathrm{C}}_n^{k+1}& =& {\mathrm{C}}_{n+1}^{k+1}.\end{array}$$

Máy tính

Máy tính sau đây tính số tổ hợp chập k của n.

Ví dụ có lời giải

1. Bắt đầu với xổ số chọn 6 số từ 49 số đã nhắc đến ở trên. Từ thùng quay chứa 49 quả bóng, người ta rút ra 6 quả. Có thể rút ra bao nhiêu kết quả khác nhau?

   Trước hết: thứ tự rút các số có ý nghĩa không? Không, ta chỉ đoán các số, không đoán thứ tự của chúng. Ta dùng tổ hợp. Có tất cả 49 quả bóng, rút ra 6 quả, ta được số tổ hợp

   $${\mathrm{C}}_{49}^6=\frac{49!}{(49-6)!\cdot 6!}=\frac{49!}{43!\cdot 6!}=13.983.816$$

   Có tất cả 13.983.816 kết quả có thể rút ra. Nhân tiện, từ đó suy ra xác suất trúng giải với một vé là 1/13.983.816, tức là 0,00000715112%.

2. Tại một buổi giao lưu văn nghệ ở làng có 13 bạn nữ mà Nam muốn mời nhảy. Nam biết rằng trong một buổi tối anh có thể nhảy với 4 bạn nữ khác nhau. Nam có thể chọn từ bao nhiêu nhóm 4 bạn khác nhau?

   Đây lại là một ví dụ đơn giản về tổ hợp, thứ tự không có ý nghĩa, Nam nhảy với bạn đầu tiên cũng hay như với bạn cuối cùng. Ta có tập hợp gồm 13 bạn nữ, mỗi lần chọn ra 4 bạn. Điều này dẫn đến số tổ hợp

   $${\mathrm{C}}_{13}^4=715.$$

3. Có một nhóm 50 người, một nửa là nam và một nửa là nữ. Có bao nhiêu nhóm 3 người khác nhau, nếu nhóm không được chỉ gồm một giới (tức là trong nhóm không được có 3 nam hoặc 3 nữ)?

   Đây là bài toán tổ hợp phức tạp hơn một chút. Nếu loại các nhóm 3 người cùng giới thì chỉ còn 2 cách lập nhóm: 2 nam và 1 nữ, hoặc 1 nam và 2 nữ; số tổ hợp của loại thứ nhất (2 nam và 1 nữ) bằng số tổ hợp của loại thứ hai. Vì vậy chỉ cần tính số tổ hợp của loại thứ nhất rồi nhân với 2. Bây giờ thì lại dễ dàng. Ta tính số cặp nam khác nhau, tức là tổ hợp chập 2 của 25, rồi nhân với số cách chọn 1 nữ (bằng 25, xem các hệ thức cơ bản ở trên, cụ thể là dòng thứ hai). Cuối cùng nhân kết quả này với 2 là được đáp số.

   $$2\cdot {\mathrm{C}}_{25}^2\cdot {\mathrm{C}}_{25}^1=15000.$$

4. Trong một hộp có 15 sản phẩm, trong đó có 4 sản phẩm bị lỗi. Có bao nhiêu cách chọn 6 sản phẩm sao cho

   • không có sản phẩm nào bị lỗi? Lúc này ta chọn 6 sản phẩm từ 15 − 4 = 11 sản phẩm không bị lỗi. Ta được số tổ hợp

     $${\mathrm{C}}_{11}^6=462.$$

   • có đúng 1 sản phẩm bị lỗi? Ta chọn một tập hợp gồm 5 sản phẩm tốt và 1 sản phẩm lỗi. Có tất cả 11 sản phẩm tốt và 4 sản phẩm lỗi. Áp dụng quy tắc nhân, ta được kết quả:

     $${\mathrm{C}}_{11}^5\cdot {\mathrm{C}}_4^1=1848$$

   • có nhiều nhất 1 sản phẩm bị lỗi? Ta dùng các kết quả trước. Có tất cả 462 cách chọn đúng 6 sản phẩm tốt và 1848 cách chọn 5 sản phẩm tốt và 1 sản phẩm lỗi. Áp dụng quy tắc cộng, cộng các kết quả này lại, ta được điều cần tìm, tức là nhiều nhất 1 sản phẩm lỗi (= hoặc không có sản phẩm lỗi nào, hoặc có đúng 1). Kết quả là: 462 + 1848 = 2310.