Đếm bắt đầu hay ho khi mọi thứ lặp lại
Đăng ngày 18 tháng 3, 2026 ... views
Một điều mình nhận ra càng ngày càng rõ khi học toán rời rạc: những bài đếm tưởng chừng đơn giản thường là những bài dễ sai nhất. Bạn nghĩ ra công thức, logic nghe hợp lý, rồi — sai. Không phải vì suy luận tệ, mà vì cách đếm bị lệch một chút.
Vấn đề cốt lõi: khi các phần tử lặp lại hoặc chồng chéo, cách đếm thông thường sẽ hỏng. Và các kỹ thuật để sửa — đếm phần bù, quy tắc thương, song ánh — lại là những ý tưởng dùng đi dùng lại nhiều nhất trong tổ hợp.
Trong bài này, mình muốn đi qua hành trình từ đếm chuỗi cơ bản đến hoán vị rồi anagram, vì nó là một hành trình từ "dễ quá" sang "khoan, sao lại sai?" rồi đến "ồ, hay thật."
Đếm "ít nhất một" bằng cách loại bỏ cái không muốn
Bài toán kinh điển: có bao nhiêu mật khẩu 8 ký tự (gồm chữ số, chữ thường, chữ hoa) chứa ít nhất một chữ hoa?
Cách tiếp cận trực tiếp — chọn một chữ hoa, chọn vị trí, điền phần còn lại — nghe hợp lý nhưng rất rối. Có cách gọn hơn nhiều.
Mẹo ở đây là đếm phần bù: đếm tất cả, rồi trừ đi những cái bạn không muốn.
Vế đầu là mọi mật khẩu 8 ký tự khả thi — 62 ký tự, 8 vị trí, mỗi vị trí tùy chọn. Vế thứ hai là mật khẩu hoàn toàn không có chữ hoa — chỉ còn 36 ký tự. Trừ đi, bạn còn lại đúng những mật khẩu có ít nhất một chữ hoa.
Cách này hiệu quả vì "ít nhất một" rất khó đếm trực tiếp, nhưng "không có cái nào" thì dễ. Phần bù làm hết việc nặng.
Cái bẫy overcounting
Đây là đáp án sai mà trông cực kỳ thuyết phục:
Logic: chọn 1 trong 26 chữ hoa, chọn 1 trong 8 vị trí, điền 7 vị trí còn lại tùy ý. Nghe hoàn hảo. Nhưng sai — vì đếm trùng.
Biểu thức này thực ra đếm bộ ba: (chữ hoa, vị trí, chuỗi 7 ký tự). Nhưng một mật khẩu có nhiều chữ hoa sẽ được tạo ra bởi nhiều bộ ba khác nhau. Chuỗi "FA65B227" có thể sinh ra từ việc chọn F ở vị trí 1 hoặc chọn A ở vị trí 4 — hai bộ ba khác nhau, cùng một chuỗi.
Dấu hiệu rõ ràng nhất: 26 × 8 × 62⁷ thực ra lớn hơn 62⁸ — tổng số mật khẩu. Không thể có nhiều mật khẩu "có ít nhất một chữ hoa" hơn tổng số mật khẩu được.
Nếu ánh xạ từ đối tượng bạn xây dựng đến tập hợp mong muốn không phải song ánh (bijection), bạn đang đếm trùng.
Luyện tập: chuỗi 4 chữ số có ít nhất một số 0
Cùng ý tưởng, quy mô nhỏ hơn. Có bao nhiêu chuỗi 4 chữ số (0-9) chứa ít nhất một số 0?
Có nhiều đáp án đúng — và đó chính là phần thú vị.
Cách B: Đếm phần bù
Tổng trừ đi chuỗi không có số 0. Gọn và rõ ràng.
Cách C: Đếm theo số lượng số 0
Đây dùng quy tắc tổng — chia tập hợp thành các nhóm không giao nhau (đúng 1 số 0, đúng 2, đúng 3, đúng 4) rồi cộng lại. Số 6 trong vế thứ hai là "chọn 2 từ 4" — số cách chọn 2 trong 4 vị trí để đặt số 0. Mình sẽ nói về tổ hợp chính thức ở bài sau, nhưng ý tưởng khá trực quan.
Cách D: Đếm theo vị trí số 0 đầu tiên
Nếu số 0 đầu tiên ở vị trí 1: 3 vị trí còn lại tùy ý (10³). Nếu ở vị trí 2: vị trí 1 phải khác 0 (9), phần còn lại tùy ý (10²). Tương tự cho các vị trí sau.
Ba cách đúng, ba biểu thức trông khác hẳn nhau, đều bằng 3.439. Mỗi lần bạn tìm ra cách đếm mới cho cùng một tập hợp, bạn được một đẳng thức toán học miễn phí. Lập luận đếm chứng minh đại số.
Cách A: Cách sai
4 × 9³ = 2916. Đây đếm chuỗi có đúng một số 0 — chọn vị trí cho số 0 duy nhất, điền phần còn lại bằng chữ số khác 0. Công thức không sai, nhưng nó trả lời một câu hỏi khác — thiếu mất những chuỗi có 2, 3, hoặc 4 số 0.
Từ chuỗi sang kẹo: song ánh như công cụ đếm
Đây là bài toán trông chẳng liên quan gì đến chuỗi: có bao nhiêu cách phân phát 10 viên kẹo khác nhau cho 4 đứa trẻ khác nhau?
Kẹo phân biệt (Twix, Skittles, M&M's...). Trẻ phân biệt. Mỗi viên kẹo thuộc về đúng một đứa. Bất kỳ đứa nào cũng có thể nhận 0, 1, hoặc cả 10 viên.
Đáp án là 4¹⁰. Lý do: song ánh — ánh xạ một-một đến thứ mình đã biết cách đếm.
Nghĩ thế này: xây một chuỗi dài 10 trên bảng chữ cái {A, B, C, D}. Mỗi vị trí đại diện cho một viên kẹo. Ký tự ở vị trí đó cho biết đứa trẻ nào nhận kẹo đó.
| Vị trí | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Kẹo | Twix | M&M's | Skittles | Kit Kat | 3Musk | Snickers | Mounds | AlmJoy | Reese's | Hershey's |
| Trẻ | D | D | C | A | D | A | C | C | A | A |
Chuỗi "DDCADACCAA" ứng với đúng một cách phân phát. Mỗi cách phân phát ứng với đúng một chuỗi, và ngược lại. Đó là song ánh. Nên số cách phân phát bằng số chuỗi dài 10 trên bảng 4 ký tự: 4¹⁰ = 1,048,576.
Sức mạnh của song ánh là biến bài toán đếm khó hiểu thành bài toán quen thuộc. Chỉ cần chứng minh ánh xạ là một-một và toàn ánh, hai tập hợp phải cùng kích thước.
Hoán vị: khi không được lặp lại
Chuỗi trên bảng chữ cái cho phép lặp — bạn dùng cùng ký tự nhiều lần. Nhưng nếu mỗi ký tự chỉ được xuất hiện một lần?
Có bao nhiêu chuỗi 3 chữ cái từ {A, B, C, D, E} mà không lặp?
Mỗi lần điền một vị trí, bạn mất đi một ký tự. Vị trí 1: 5 chọn. Vị trí 2: 4 chọn. Vị trí 3: 3 chọn. Tổng: 5 × 4 × 3 = 60.
Đây gọi là hoán vị — cụ thể là r-hoán vị, với r là số vị trí cần điền.
Công thức tổng quát
Số cách sắp xếp r vật từ n vật phân biệt:
Tích này có đúng r thừa số. Bạn cũng viết được dạng giai thừa:
với n! = n × (n-1) × (n-2) × ... × 1.
Dạng giai thừa hoạt động vì mẫu (n-r)! triệt tiêu phần "đuôi" không cần. Ví dụ:
Thử thay đổi n và r ở đây:
Hoán vị P(n, r)
Số cách sắp xếp r vật từ n vật phân biệt
Khi r bằng n: sắp xếp tất cả
Khi sắp xếp toàn bộ n vật:
Theo công thức:
Để ra kết quả n!, ta cần 0! = 1. Có hai lý do cho quy ước này:
- Đại số: làm công thức hoạt động — không cần trường hợp đặc biệt cho r = n.
- Tổ hợp: có bao nhiêu cách sắp xếp 0 vật? Đúng một cách — không làm gì cả. Chỉ có một cách sắp xếp rỗng.
Quy ước không phải tùy tiện. Nó là giá trị duy nhất khiến cả đại số lẫn tổ hợp nhất quán.
Anagram: khi chữ cái lặp lại
Hoán vị giả sử mọi vật đều khác nhau. Nhưng nếu một số giống hệt nhau thì sao? Đó là lúc anagram xuất hiện — sắp xếp lại một tập hợp có thể chứa phần tử trùng (multiset).
Tất cả khác nhau: MILES
Các chữ M, I, L, E, S đều khác nhau. Số anagram là 5! = 120.
Một vài trong số đó là từ tiếng Anh: Miles, Slime, Limes. Nhưng mình đang đếm tất cả cách sắp xếp, không chỉ từ có nghĩa.
Một nhóm lặp: EETS
Xét các chữ E, E, T, S. Nếu tất cả khác nhau — giả sử E₁, E₂, T, S — sẽ có 4! = 24 hoán vị.
Nhưng vì hai chữ E giống nhau, hoán đổi E₁ và E₂ cho ra cùng chuỗi. Với mỗi anagram phân biệt, có 2! hoán vị trông giống hệt nhau.
Chiến lược: làm các phần tử trùng thành khác nhau, đếm tất cả, rồi chia cho số cách các phần tử trùng tự sắp xếp nội bộ.
Nhiều nhóm lặp: ASSESSOR
Đây là lúc công thức tỏa sáng. A-S-S-E-S-S-O-R có 8 chữ:
| Chữ cái | Số lần |
|---|---|
| S | 4 |
| A | 1 |
| E | 1 |
| O | 1 |
| R | 1 |
Công thức tổng quát:
với N là tổng số chữ cái, và k₁, k₂, ..., kₘ là số lần xuất hiện của mỗi chữ phân biệt.
Kiểm tra nhanh: tổng các kᵢ phải bằng N. Với ASSESSOR: 4 + 1 + 1 + 1 + 1 = 8. Nếu không khớp, bạn đếm tần suất sai rồi.
Mẹo tô màu
Đây là mô hình giúp mọi thứ trở nên rõ ràng. Lấy ASSESSOR và tô màu mỗi chữ S khác nhau — S₁ đỏ, S₂ xanh dương, S₃ xanh lá, S₄ cam. Bây giờ cả 8 ký tự đều khác nhau, nên có 8! hoán vị.
Nhưng mỗi anagram thực tế ứng với nhiều hoán vị có màu — cụ thể là 4! cái, vì bạn có thể sắp xếp lại 4 chữ S màu mà chuỗi thực tế không đổi.
Đây gọi là quy tắc thương — mở rộng sang tập dễ đếm hơn, đếm, rồi chia cho kích thước lớp tương đương (số "bản sao" ứng với mỗi phần tử thực).
Thử ngay
Nhập bất kỳ từ nào bên dưới và xem số anagram cập nhật theo thời gian thực:
Máy tính Anagram
Nhập một từ để xem có bao nhiêu cách sắp xếp lại chữ cái
Widget tô màu từng nhóm chữ cái và hiển thị công thức đầy đủ. Thử các từ có nhiều chữ lặp (như "MISSISSIPPI") để thấy số lượng giảm đáng kể so với N!.
Quy tắc thương xuất hiện ở khắp nơi
Công thức anagram là một trường hợp của kỹ thuật rộng hơn: đếm theo nhóm.
- Mở rộng sang tập lớn hơn, dễ đếm hơn (ví dụ: coi các vật giống nhau là khác nhau)
- Đếm tập mở rộng
- Chia cho số phần tử trong mỗi nhóm ứng với một phần tử gốc
Kỹ thuật này xuất hiện ở khắp nơi — đếm hình học có đối xứng, đếm hợp chất hóa học có nguyên tử giống nhau, đếm cách chia bài khi thứ tự chất không quan trọng. Chiến lược luôn giống nhau: làm mọi thứ khác nhau, đếm, rồi tính cho các đối xứng.
Một vài điều mình rút ra được
- Đếm phần bù thường là cách gọn nhất để xử lý điều kiện "ít nhất một" — đếm tất cả, trừ đi cái không muốn
- Overcounting xảy ra khi cách xây dựng của bạn có thể tạo ra cùng một đối tượng theo nhiều cách — luôn kiểm tra xem ánh xạ có phải song ánh không
- Kiểm tra nhanh: nếu số lượng "ít nhất một X" vượt quá tổng số, chắc chắn có gì đó sai
- Nhiều cách đếm đúng cho cùng bài toán tặng bạn đẳng thức toán học miễn phí — đại số phải khớp vì các tập hợp giống nhau
- Song ánh biến bài toán đếm lạ thành bài toán quen — nếu ánh xạ là một-một và toàn ánh, số lượng phải bằng nhau
- Giai thừa đếm cách sắp xếp các vật phân biệt: n! cách sắp xếp n vật
- 0! = 1 vừa cần thiết về mặt đại số, vừa tự nhiên về mặt tổ hợp — chỉ có đúng một cách sắp xếp không có gì
- Hoán vị P(n, r) đếm cách chọn r vật từ n vật, mỗi thừa số đại diện cho một lựa chọn bị thu hẹp
- Anagram của multiset dùng quy tắc thương: N! chia cho tích các giai thừa nhóm lặp
- Mẹo tô màu là then chốt — làm các vật giống nhau thành khác nhau, đếm, rồi chia đi các đối xứng
- Khi tổng các giai thừa ở mẫu bằng số ở tử, bạn biết mình đã tính đủ mọi chữ cái
- Quy tắc thương tổng quát hóa ra ngoài anagram, áp dụng cho mọi tình huống khi bạn có thể mở rộng sang tập dễ hơn rồi chia theo lớp tương đương
Điều cuối cùng — quy tắc thương — là pattern mình thấy quay đi quay lại nhiều nhất. Cùng một ý tưởng dù bạn đang đếm anagram, đối xứng hình học, hay cách sắp xếp mà một số vị trí hoán đổi được. Làm mọi thứ khác nhau khi điều đó giúp đếm dễ hơn, rồi chia đi sự giống nhau. Khi bạn nhận ra nó một lần, bạn bắt đầu thấy nó ở khắp mọi nơi.
Phần 1/2 trong "Discrete Math for Algorithms"