Bài toán đếm và những sự lặp lại thú vị

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 toán đếm tưởng chừng "đơn giản" lại là những cái bẫy dễ đánh lừa chúng ta 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?

Lối suy nghĩ trực tiếp (chọn chữ, chọn chỗ, rồi điền nốt) nghe rất logic, thế nhưng việc đếm "ít nhất một" theo cách này lại là một mớ hỗn độn. 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à tổng số mật khẩu 8 ký tự có thể có — với 62 ký tự cho mỗi vị trí, mỗi vị trí có thể là bất kỳ ký tự nào. 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ễ. Mọi thứ trở nên nhẹ nhàng hơn nhiều nhờ đếm phần bù.

📚 Lưu ý thực tế: NIST SP 800-63B-4 — chuẩn xác thực mà phần lớn hệ thống ở Mỹ đang theo — khuyến nghị mật khẩu tối thiểu 8 ký tự nhưng cố ý không bắt buộc các quy tắc về loại ký tự kiểu như "phải có chữ hoa". Hệ thống hiện đại đối chiếu mật khẩu với danh sách đã rò rỉ thay vì áp các ràng buộc về loại ký tự. Bài "ít nhất một X" ở đây là ví dụ giáo khoa, không phải chính sách bảo mật hiện hành.

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.

Nếu bạn thích cách dùng những lập luận đếm để giải quyết vấn đề thực tế, video Why this puzzle is impossible của 3Blue1Brown dùng một lập luận đếm chẵn lẻ rất tương tự để chứng minh một bài toán bàn cờ không có lời giải trừ khi kích thước bàn cờ là lũy thừa của 2 — minh họa đẹp cho việc đếm tinh tế giúp ta thấy cấu trúc mà lập luận thuần túy không thấy được.

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ách A: Cách sai

4 × 9³ = 2916. Phép tính này đếm những 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.

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. Cứ mỗi lần tìm ra một cách đếm mới cho cùng một tập hợp, bạn coi như đã "bỏ túi" được một đẳng thức toán học mà chẳng cần tốn công chứng minh. Chính logic đếm này là lời giải thích sinh động cho các công thức đại số.

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 trẻ khác nhau?

Mỗi viên kẹo là một loại khác nhau (Twix, Skittles, M&M's...). Bốn trẻ là bốn cá nhân khác nhau. Mỗi viên kẹo thuộc về đúng một trẻ. Bất kỳ trẻ nào cũng có thể nhận 0, 1, hoặc cả 10 viên.

Đáp án là 4¹⁰. Bí mật nằm ở song ánh (bijection) — chúng ta biến bài toán này thành một bài toán khác dễ hơn bằng cách thiết lập một liên kết 1-1 với thứ mà ta đã biết cách đếm.

Hãy nghĩ thế này: ta tạo ra một chuỗi dài 10 ký tự bằng 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 đó.

Chuỗi "DDCADACCAA" ứng với đúng một cách phân phát: trẻ D nhận kẹo Twix, M&M's và Three Musketeers; trẻ C nhận Skittles, Mounds và Almond Joy; trẻ A nhận Kit Kat, Snickers, Reese's và Hershey's; còn trẻ B không nhận được gì. 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 khi điền xong một vị trí, số lượng ký tự bạn còn lại sẽ giảm đi một. Vị trí 1: có 5 cách chọn. Vị trí 2: 4 cách. Vị trí 3: 3 cách. 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:

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:

1. Đạ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.
2. 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.

Có thể kiểm chứng bằng cách liệt kê hết tất cả:

6 cách bắt đầu bằng E, 3 cách bằng S, 3 cách bằng T. Tổng cộng là 6 + 3 + 3 = 12, đúng bằng 4!/2!.

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 chính là lúc công thức phát huy tối đa tác dụng. A-S-S-E-S-S-O-R có 8 chữ:

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 của từng "nhóm trùng" (tức là số lượng cách sắp xếp trông giống hệt nhau).

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:

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.

1. 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)
2. Đếm tập mở rộng
3. 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 các hình hình học có tính đối xứng, đếm các 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.

Nếu ý tưởng tổng quát hóa này hấp dẫn bạn, video Group theory, abstraction, and the 196,883-dimensional monster của 3Blue1Brown là phần tiếp theo tự nhiên — đối xứng → nhóm → quỹ đạo → nhóm hữu hạn 'sporadic' lớn nhất. Quy tắc thương hóa ra chỉ là phần nổi của một tảng băng khổng lồ.

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. Cứ coi như mọi thứ đều khác nhau cho dễ tính, rồi sau đó mới "chia" bớt cho sự giống nhau. Khi đã biết quy luật này, bạn sẽ thấy nó xuất hiện ở khắp mọi nơi.