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. Khi đếm tập con — ta ra được một con số. Đếm chuỗi nhị phân có lượng số 1 cố định — vẫn là con số đó. Đếm đường đi trên lưới — lại thấy kết quả y hệt.
Không phải ngẫu nhiên đâu. Thực chất chúng là cùng một thứ, chỉ là đang xuất hiện dưới những dạng khác nhau thôi. 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 que màu 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, tổng cộng là 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. Đầu tiên tính cho tập hợp dễ hơn (treo tranh), sau đó chia cho số phép đố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 khi xem nó là một vật thể thật, có thể cầm lên xoay và lật.
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 cũng vậy... Thứ tự khác nhau sẽ tạo ra dãy 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 đi ngày Thứ Hai khác với người đi ngày 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). Bí quyết là kết nối nó với một khái niệm quen thuộc: 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 một 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. Và đây là "kim chỉ nam" giúp mình phân biệt chúng:
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ứ
Hóa ra C(n, k) không chỉ đếm tập con — nó còn đếm chuỗi nhị phân có số lượng bit 1 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 |
Cách làm: cứ i nằm trong tập con thì điền 1 vào vị trí i, không thì điền 0. Đơ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 mấu chốt nằm ở "thứ tự"
Có một câu hỏi khiến mình lúng túng ban đầu: nếu tổ hợp là đếm kiểu "thứ tự không quan trọng", thì tại sao nó lại dùng để đế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. Thực chất bạn đang chọn một tập con vị trí — mà đã là tập con thì không cần 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: biến thể khác của cùng một công thứ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.
Một ví dụ về đường đi: P, L, P, L, L, P, P, P, P, P — khoan đã, hình như mình đếm nhầm... À đây: P, P, L, P, L, L, P, P, P. Mỗi đường đi như vậy thực chất là một anagram của 6 chữ P và 3 chữ L.
Đây chính xác là chuỗi nhị phân có số lượng bit 1 cố định, dài 9 và 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.
Quy tắc thương: Chìa khóa của mọi vấn đề
Có thể thấy, quy tắc thương chính là "công thần" đứng sau mọi bài toán đếm ở đây:
- 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 là: đếm trên một tập hợp lớn hơn (nơi mọi thứ đều có thể phân biệt được), rồi chia bớt cho sự trùng lặp. 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 có số lượng bit 1 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 số cách sắp xếp chia cho số hướng của 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 mình thấy tâm đắc nhất là mối liên hệ giữa việc đặt tên và sự thấu hiểu. Trong toán học cũng như lập trình, cái tên là điều kiện để ta tương tác với vạn vật. Bạn không thể thao tác trên thứ mà mình không gọi tên được. Công thức cho ta đáp án, nhưng cái tên mới cho ta quyền kiểm soát. Và quyền kiểm soát thì luôn có trước.
Phần 2/2 trong "Discrete Math for Algorithms"