Tổ hợp chỉ là hoán vị mà quên mất thứ tự
Đăng ngày 18 tháng 3, 2026 ... views
Càng học về đếm, mình càng nhận ra một điều thú vị: cùng một con số cứ xuất hiện đi xuất hiện lại trong những bối cảnh hoàn toàn khác nhau. Đếm tập con — được một số. Đếm chuỗi nhị phân có đúng bao nhiêu số 1 — cùng số đó. Đếm đường đi trên lưới — lại cùng số đó.
Đây không phải trùng hợp. Đó là dấu hiệu cho thấy các đối tượng này thực ra là cùng một thứ, chỉ mặc trang phục khác nhau. Và công cụ hé lộ mối liên hệ đó chính là tổ hợp — hay "n chọn k" — một trong những biểu thức linh hoạt nhất của tổ hợp học.
Trong bài trước, mình đã đi từ đếm phần bù đến hoán vị rồi anagram. Bài này tiếp nối ngay từ đó: mình sẽ xem quy tắc thương áp dụng thế nào cho đối xứng hình học, rồi suy ra tổ hợp từ hoán vị, và cuối cùng khám phá rằng tập con, chuỗi nhị phân, và đường đi trên lưới đều được đếm bởi cùng một công thức.
Đối xứng khiến việc đếm khó hơn — và quy tắc thương giải quyết nó
Bài toán vui: bạn có bốn màu ống nhựa khác nhau — đỏ, xanh dương, xanh lá, vàng — và muốn ghép thành hình vuông. Có bao nhiêu hình vuông khác nhau?
Câu trả lời phụ thuộc vào "khác nhau" nghĩa là gì. Nếu treo mỗi hình lên tường như tranh (cố định hướng), mọi cách sắp xếp đều khác nhau. Cho ta 4! = 24 hình.
Nhưng nếu coi chúng là vật thể vật lý — có thể cầm lên, xoay, lật — thì nhiều trong 24 "bức tranh" đó thực ra là cùng một hình vuông.
Hình vuông có 8 hướng đối xứng: 4 phép xoay (0, 90, 180, 270 độ) nhân 2 phép lật (mặt trước và mặt sau). Mỗi hình vuông vật lý xuất hiện dưới dạng đúng 8 bức tranh khác nhau. Nên số hình thật sự khác nhau là 24 / 8 = 3.
Đây là quy tắc thương từ bài trước, áp dụng cho hình học thay vì chữ cái. Mở rộng sang tập dễ hơn (tranh), đếm nó, chia cho kích thước nhóm (đối xứng).
Cách nhìn khéo hơn
Có cách khác không cần chia. Cố định một màu — giả sử đỏ ở dưới cùng. Giờ bạn chỉ cần chọn màu đối diện (trên cùng). Có 3 lựa chọn: xanh dương, xanh lá, hoặc vàng.
Khi đã chọn trên và dưới, hai cạnh còn lại có thể hoán đổi bằng cách lật hình. Nên chúng không tạo ra hình mới. Vậy chính xác có 3 hình.
Cả hai cách cho cùng đáp án. Cách quy tắc thương có tính hệ thống hơn (và tổng quát hóa cho mọi hình), còn cách trực tiếp cần trực giác hình học hơn nhưng tránh được số lớn.
Tổng quát hóa cho hình khác
Với lục giác đều có 6 cạnh màu khác nhau, có 6 phép xoay và 2 phép lật = 12 hướng đối xứng. Số lục giác khác nhau là 6! / 12 = 720 / 12 = 60.
Quy luật: tổng số cách sắp xếp chia cho số hướng đối xứng. Áp dụng cho mọi đa giác đều dùng ống nhựa.
Bước ngoặt lớn: từ dãy sang tập con
Mọi thứ mình đã đếm trước giờ — chuỗi, hoán vị, anagram — đều liên quan đến thứ tự. Vị trí 1 quan trọng, vị trí 2 quan trọng. Hai dãy khác nhau nếu các phần tử ở thứ tự khác nhau.
Nhưng đôi khi thứ tự không quan trọng. Bạn chỉ quan tâm những phần tử nào được chọn, không quan tâm thứ tự sắp xếp.
Chọn 7 người từ lớp 50 người đi chơi như một nhóm — bạn không quan tâm ai được chọn trước. Đó chỉ là một tập hợp 7 người. Đó là tổ hợp.
Chọn 7 người mà mỗi người đi một ngày khác nhau trong tuần — giờ thứ tự quan trọng (người thứ Hai khác người thứ Ba). Đó là hoán vị.
Ký hiệu cho tổ hợp là C(n, k), thường viết là "n chọn k." Nó đếm số tập con k phần tử của tập hợp n phần tử.
Suy ra công thức: hoán vị chia bớt thứ tự
Đây là cách tính C(n, k). Mẹo là nối nó với thứ mình đã biết: P(n, k).
Xét việc chọn 7 sinh viên từ 50 cho các ngày khác nhau trong tuần. Đó là P(50, 7) — bài toán hoán vị.
Nhưng mình có thể chia quá trình đó thành hai bước:
- Chọn 7 sinh viên nào đi (tổ hợp: C(50, 7) cách)
- Sắp xếp 7 sinh viên đó theo các ngày (hoán vị của 7: 7! cách)
Vì cả hai cách đều đếm cùng tập hợp:
Giải cho C(n, k):
Đó là công thức tổ hợp. k! ở mẫu chính xác là bước "quên thứ tự" — chia bớt tất cả các cách sắp xếp k phần tử đã chọn.
Ví dụ cụ thể
Tử số là P(50, 7). Chia cho 7! = 5,040 để bỏ đi thứ tự. Kết quả là 99,884,400.
Thử các giá trị khác:
Tổ hợp C(n, k)
Số cách chọn k vật từ n vật phân biệt (không phân biệt thứ tự)
Chú ý C(n, k) luôn nhỏ hơn P(n, k) — vì tổ hợp gộp tất cả k! cách sắp xếp cùng tập con lại thành một.
Câu hỏi then chốt: thứ tự có quan trọng không?
Phần khó nhất của bài toán đếm không phải công thức — mà là nhận ra công thức nào áp dụng. Đây là cách mình phân biệt:
Hoán vị = dãy. Nếu các phần tử có vai trò, vị trí, hoặc nhãn khiến thứ tự tạo ra kết quả khác nhau, dùng P(n, k).
Tổ hợp = tập con. Nếu bạn chỉ chọn nhóm và thứ tự không liên quan, dùng C(n, k).
Ví dụ nhanh
| Tình huống | Thứ tự? | Loại |
|---|---|---|
| Chọn 7 sinh viên đi chơi nhóm | Không | C(50, 7) |
| Chọn 7 sinh viên, mỗi người một ngày | Có | P(50, 7) |
| Chọn trưởng nhóm, thư ký, thủ quỹ, MC từ 20 người | Có | P(20, 4) |
| Chọn 4 người đi hội nghị cùng nhau | Không | C(20, 4) |
Bài trưởng nhóm/thư ký/thủ quỹ/MC là hoán vị vì đổi ai giữ vai trò nào tạo ra kết quả khác — dù cùng 4 người được chọn. Bài hội nghị là tổ hợp vì 4 người chỉ đi cùng nhau thôi.
Chuỗi nhị phân và tập con là cùng một thứ
Đây là phần mình thấy hay nhất. Hóa ra C(n, k) không chỉ đếm tập con — nó còn đếm chuỗi nhị phân mật độ cố định (chuỗi nhị phân dài n có đúng k số 1).
Lý do là một song ánh tuyệt đẹp.
Song ánh
Lấy tập {1, 2, 3, 4} và xét tất cả tập con 2 phần tử. Có C(4, 2) = 6 tập:
| Tập con | Chuỗi nhị phân |
|---|---|
{1, 2} | 1100 |
{1, 3} | 1010 |
{1, 4} | 1001 |
{2, 3} | 0110 |
{2, 4} | 0101 |
{3, 4} | 0011 |
Quy tắc: vị trí i được số 1 nếu i nằm trong tập con, số 0 nếu không. Đơn giản vậy thôi.
Áp dụng cho mọi n và k. Mỗi tập con k phần tử ánh xạ đến đúng một chuỗi nhị phân có k số 1, và ngược lại. Vì đây là song ánh, hai tập có cùng kích thước: C(n, k).
Đếm chuỗi nhị phân trực tiếp
Bạn cũng có thể tính C(n, k) mà không cần biết song ánh — chỉ cần đếm trực tiếp chuỗi nhị phân.
Có bao nhiêu chuỗi nhị phân dài 8 có đúng 3 số 1?
Cách 1: Chọn vị trí. Có 8 vị trí. Chọn 3 vị trí đặt số 1. Đó là C(8, 3).
Cách 2: Anagram. Chuỗi có 3 số 1 và 5 số 0 chính là anagram của "00000111." Từ bài trước, số anagram là:
Và đó chính xác là C(8, 3) = 56.
Đây là điều mình thích nhất ở tổ hợp học — ba cách suy nghĩ hoàn toàn khác nhau (tập con, chuỗi nhị phân, anagram) đều hội tụ về cùng một công thức. Sự hội tụ đó không phải ngẫu nhiên; nó nói lên điều gì đó sâu sắc về cấu trúc.
Điểm tinh tế về "thứ tự"
Có một câu hỏi khiến mình lúng túng ban đầu: nếu tổ hợp đếm thứ "thứ tự không quan trọng," tại sao nó lại đếm chuỗi nhị phân, nơi thứ tự 0 và 1 rõ ràng quan trọng?
Giải đáp: trong chuỗi nhị phân, thứ tự các bit quan trọng để xác định chuỗi nào. Nhưng thứ tự bạn chọn vị trí cho số 1 thì không quan trọng. Bạn đang chọn một tập con vị trí — và đó là phần không thứ tự.
C(8, 3) đếm số cách chọn 3 vị trí từ 8. Khi đã chọn xong, chuỗi được xác định. "Tổ hợp" nói về việc chọn, không phải về chuỗi cuối cùng.
Đường đi trên lưới: cùng công thức đội lốt khác
Giả sử bạn di chuyển trên lưới 6 x 3 ô vuông, bắt đầu từ góc dưới-trái, muốn đến góc trên-phải. Chỉ được đi sang phải hoặc lên — không quay lại.
Để đi từ góc dưới-trái đến góc trên-phải, bạn phải đi đúng 6 bước sang phải và 3 bước lên — tổng 9 bước. Mỗi đường đi chỉ là cách sắp xếp khác nhau của 9 bước này.
Đây chính xác là chuỗi nhị phân mật độ cố định dài 9 có 3 số 1 (nếu Lên = 1, Phải = 0). Hoặc tương đương, mình đang chọn 3 trong 9 bước nào là "đi lên."
Thử các kích thước lưới khác:
Đường đi trên lưới
Số đường đi ngắn nhất trên lưới chỉ đi phải và lên
Chú ý: C(9, 3) = C(9, 6) = 84. Đây là tính đối xứng của tổ hợp — chọn 3 phần tử để đưa vào cũng giống chọn 6 phần tử để bỏ ra. Chọn 3 trong 9 bước đi lên tương đương chọn 6 bước đi phải.
Tổng quát hóa
Với lưới m x n, bạn cần m bước phải và n bước lên, tổng m + n bước. Số đường đi là:
Bài toán đường đi, tập con, chuỗi nhị phân, anagram — tất cả là cùng một bài toán đếm mặc trang phục khác nhau. Mỗi lần gặp, bạn có thể chuyển sang dạng nào dễ giải nhất.
Mọi thứ đều quay về quy tắc thương
Nhìn lại bài này và bài trước, quy tắc thương cứ làm hết việc nặng:
- Anagram: mở rộng bằng cách tô màu chữ giống nhau, đếm hoán vị, chia cho đối xứng nội bộ
- Hình học đối xứng: đếm tất cả hướng, chia cho đối xứng xoay/lật
- Tổ hợp: đếm hoán vị (chọn có thứ tự), chia cho k! (số cách sắp xếp mỗi tập con)
Quy luật luôn giống nhau: đếm tập lớn hơn nơi mọi thứ phân biệt, rồi chia bớt phần thừa. Một ý tưởng duy nhất đứng sau bốn kỹ thuật đếm khác nhau.
Một vài điều mình rút ra được
- Tổ hợp đếm tập con (chọn không thứ tự), còn hoán vị đếm dãy (sắp xếp có thứ tự) — ranh giới là thứ tự có quan trọng hay không
- Công thức tổ hợp C(n, k) = n! / (k!(n-k)!) chỉ là P(n, k) chia bớt k! cách sắp xếp
- Khi phân vân dùng hoán vị hay tổ hợp, hãy hỏi: "nếu mình đổi thứ tự các phần tử đã chọn, kết quả có khác không?" — nếu có thì hoán vị, nếu không thì tổ hợp
- Tập con và chuỗi nhị phân mật độ cố định là cùng một thứ nhờ song ánh tự nhiên: phần tử trong tập con ứng với vị trí số 1 trong chuỗi
- Chuỗi nhị phân mật độ cố định cũng là anagram của từ gồm k số 1 và (n-k) số 0 — ba góc nhìn, một công thức
- Đường đi trên lưới m x n tương đương chọn n trong (m+n) bước nào đi lên — lại một tổ hợp đội lốt
- Tính đối xứng C(n, k) = C(n, n-k) rất trực quan: chọn k phần tử đưa vào cũng giống chọn n-k phần tử bỏ ra
- Đếm đối xứng vật lý (hình vuông, lục giác) dùng cùng quy tắc thương như anagram — tổng cách sắp chia cho số hướng mỗi vật
- Quy tắc thương là sợi dây nối anagram, đối xứng hình học, tổ hợp, và chuỗi nhị phân — một ý tưởng mặc bốn bộ đồ
- Đặt tên cho thứ gì đó ("n chọn k") là một bước tiến thật sự, ngay cả trước khi tính ra con số — có ký hiệu giúp bạn suy luận về cấu trúc
Điều cuối đó — về việc đặt tên trước khi tính — là thứ mình nhớ nhất. Trong toán cũng như lập trình, đặt tên cho thứ gì đó thường là bước đầu tiên để hiểu nó. Bạn không thể thao tác trên thứ bạn không gọi tên được. Công thức quan trọng, nhưng cái tên đến trước.
Phần 2/2 trong "Discrete Math for Algorithms"