🧬 [THPT AI LUKATO Masterclass] Hàm Sinh — Vũ Khí Bí Mật Giải Trọn Bài Toán Đếm Cấp HSG Quốc Gia
4 kỹ thuật hàm sinh (xây khối, vành hóa, Catalan/ballot) từ cơ bản đến ứng dụng vào đề thi chọn HSG Quảng Trị 2026 — đã kiểm chứng bằng code.
MASTERCLASS · TOÁN 12 · TỔ HỢP — ĐẾM NÂNG CAO · PHẦN 2 CHUỖI "ĐẾM TRÊN ĐA GIÁC"
Hàm Sinh — Vũ Khí Bí Mật Giải Trọn Bài Toán Đếm Cấp HSG Quốc Gia
99% học sinh chỉ biết "đếm trực tiếp": tổ hợp, hoán vị, nguyên lý bù trừ. Nhưng khi bài toán có cấu trúc lặp, cấu trúc vòng, hay điều kiện ràng buộc theo từng bước — đếm trực tiếp sụp đổ. Hàm sinh (generating function) là công cụ biến một bài toán đếm thành một bài toán đại số: thay vì đếm bằng tay, ta "mã hóa" dãy số cần đếm thành hệ số của một chuỗi lũy thừa, rồi dùng đại số để khai triển. Đây là kỹ thuật hiếm được dạy đúng cách ở bậc phổ thông, nhưng lại là công cụ chuẩn mực trong các kỳ thi học sinh giỏi quốc gia và Olympiad.
4 kỹ thuật lõi
Từ xây khối tới phân rã Catalan
1 bài thi HSG thật
Đã kiểm chứng độc lập bằng code, không phải chỉ "tin lời giải"
Nối tiếp chuyên đề Burnside
Cùng đề tài tô màu đa giác, khác vũ khí
1. Vì sao hàm sinh là "vũ khí bí mật"?
Chuyên đề trước của LUKATO (🎨 Tô màu lục giác · Chu trình C₆ và Burnside) đã cho các em thấy một công cụ mạnh: Burnside , dùng khi cần đếm các cấu hình tương đương nhau qua phép đối xứng (quay, lật). Nhưng có một lớp bài toán đếm hoàn toàn khác: các đỉnh/vị trí được đánh số cố định (không quay được), nhưng cấu trúc hợp lệ lại được định nghĩa bằng một ràng buộc cục bộ lặp lại — "không có hai phần tử kề nhau cùng loại", "mọi đoạn đầu phải thỏa mãn một bất đẳng thức", "tổng các phần phải bằng đúng một số cho trước"... Đây chính là lãnh địa của hàm sinh.
Đếm trực tiếp
Hợp với bài toán "phẳng": chọn k trong n, xếp thứ tự, chia nhóm rời rạc.
✗ Bất lực khi ràng buộc lặp theo cấu trúc dây chuyền (không 2 phần tử kề cùng loại, số dư lũy tích không âm...)
Hàm sinh
Mã hóa "một khối hợp lệ" thành một đa thức/chuỗi, rồi nhân, cộng, nghịch đảo các hàm sinh y như đại số bình thường.
✓ Biến bài toán tổ hợp phức tạp thành bài toán khai triển chuỗi lũy thừa — cơ giới hóa hoàn toàn tư duy đếm
💡 Nguyên lý cốt lõi: nếu một cấu trúc được ghép từ các "khối" độc lập nối tiếp nhau, thì hàm sinh của cấu trúc lớn = tích các hàm sinh của từng loại khối. Đây là toàn bộ bí mật đằng sau 4 kỹ thuật trong bài này.
2. Hàm sinh là gì? — 3 phút hiểu bản chất
Cho một dãy số a_0, a_1, a_2, \ldots (thường a_n = "số cách làm việc gì đó với n đối tượng"). Hàm sinh của dãy này là chuỗi lũy thừa hình thức:
A(X) = a_0 + a_1 X + a_2 X^2 + \cdots = \sum_{n\ge 0} a_n X^n
X ở đây không phải một số cần tính giá trị — nó chỉ là "chỗ đánh dấu" bậc n. Việc của ta là tìm biểu thức đóng (closed-form) của A(X) bằng đại số, rồi đọc lại hệ số a_n từ khai triển đó.
Cả bài này đi theo đúng 3 bước trên: nhận diện "khối hợp lệ" → viết hàm sinh của từng khối → nhân/cộng lại → khai triển ra hệ số cần tìm.
3 khối xây dựng cơ bản (bắt buộc thuộc lòng)
Tình huống chọn · Hàm sinh của MỘT vị trí/đối tượng · Vì sao
Chọn tự do, không giới hạn số lần lặp lại (mỗi "khối" có thể lặp 0,1,2,3,... lần) · \dfrac{1}{1-X} = 1+X+X^2+\cdots · Hệ số của X^k là 1 với mọi k — "chọn đúng k lần" luôn có đúng 1 cách
Chọn có hoặc không (0 hoặc 1 lần) · 1+X · Hệ số X^0=1 (không chọn), X^1=1 (chọn 1 lần), hết
Chọn từ 0 đến m lần (có chặn trên) · 1+X+\cdots+X^m = \dfrac{1-X^{m+1}}{1-X} · Cắt chuỗi hình học tại bậc m
Ví dụ khởi động — chia kẹo có giới hạn (nguyên bản LUKATO)
Đề bài: Có 10 viên kẹo giống hệt nhau, chia cho 3 bạn An, Bình, Chi, mỗi bạn nhận từ 0 đến 4 viên . Hỏi có bao nhiêu cách chia sao cho dùng hết đúng 10 viên?
Lời giải bằng hàm sinh: mỗi bạn là một "khối" độc lập, nhận 0 đến 4 viên → hàm sinh của một bạn là 1+X+X^2+X^3+X^4. Ba bạn độc lập với nhau nên hàm sinh của cả nhóm là tích ba hàm sinh đó:
A(X) = (1+X+X^2+X^3+X^4)^3
Số cách chia đúng 10 viên chính là hệ số của X^{10} trong khai triển này. Khai triển trực tiếp (hoặc đối chiếu vét cạn từng bộ ba (a,b,c) với 0\le a,b,c\le 4 và a+b+c=10) cho hệ số X^{10} bằng 6 .
✅ Đã kiểm chứng bằng code: khai triển đa thức bằng SymPy và đếm vét cạn toàn bộ 5^3=125 bộ ba đều cho kết quả khớp nhau: 6 cách.
3. Kỹ thuật 1 — "Xây khối" (Block Building): mã hóa cấu trúc lặp nối tiếp
Khi một dãy hợp lệ được ghép từ các khối liên tiếp (mỗi khối chiếm một số vị trí cố định, các khối nối đuôi nhau không chồng lấn), ta chỉ cần: (1) liệt kê các loại khối được phép dùng, (2) viết hàm sinh của mỗi loại khối theo độ dài nó chiếm, (3) cộng các hàm sinh khối lại, rồi lấy tổng hình học (vì số khối ghép nối tiếp là tự do) để ra hàm sinh của "một dãy hợp lệ bất kỳ".
Ví dụ nguyên bản — Lát gạch một hàng (bài toán Fibonacci kinh điển)
Đề bài: Một hàng dài n ô vuông cần được lát kín bằng hai loại gạch: gạch vuông 1\times1 (ký hiệu V) và gạch đôi 1\times2 (ký hiệu D). Hỏi có bao nhiêu cách lát?
Bước 1 — Hàm sinh của một khối gạch: gạch V chiếm 1 ô → đóng góp X; gạch D chiếm 2 ô → đóng góp X^2. Hàm sinh của "một viên gạch bất kỳ" là X+X^2.
Bước 2 — Ghép nối tiếp tự do: một cách lát hợp lệ là một dãy các viên gạch nối đuôi nhau, số viên gạch không giới hạn → lấy tổng hình học của khối:
L(X) = 1+(X+X^2)+(X+X^2)^2+\cdots = \dfrac{1}{1-(X+X^2)} = \dfrac{1}{1-X-X^2}
Bước 3 — Đọc hệ số: khai triển \dfrac{1}{1-X-X^2}=\sum_{n\ge0} F_{n+1}X^n với quy ước F_1=F_2=1 (dãy Fibonacci). Vậy số cách lát hàng n ô là F_{n+1}.
✅ Đã kiểm chứng: đếm vét cạn (đệ quy) cho n=1,\ldots,11 khớp hoàn toàn với F_{n+1} — ví dụ n=6 cho 13 cách, n=10 cho 89 cách.
4. Kỹ thuật 2 — "Vành hóa": chuyển bài toán vòng tròn về bài toán đường thẳng
Kỹ thuật xây khối ở trên chỉ đúng cho một hàng thẳng (có điểm đầu, điểm cuối rõ ràng). Nhưng khi các vị trí xếp thành vòng tròn (đa giác, ghế tròn, đèn nối vòng...), vị trí cuối lại kề với vị trí đầu — hàm sinh "thẳng" không áp dụng trực tiếp được nữa. Mẹo kinh điển: cố định trạng thái của một phần tử mốc (thường là phần tử số 1), việc này "cắt" vòng tròn thành một đường thẳng, rồi áp dụng lại kỹ thuật xây khối cho phần còn lại.
Ví dụ nguyên bản — Vòng đèn LED
Đề bài: n bóng đèn LED nối thành một vòng tròn, mỗi bóng ở trạng thái BẬT (Đ) hoặc TẮT (T). Hỏi có bao nhiêu cách bật/tắt sao cho không có hai bóng TẮT liền kề nhau (kể cả cặp bóng cuối–đầu)? Minh họa với n=6.
Cố định bóng số 1:
• Nếu bóng 1 BẬT: ràng buộc "không 2 T liền kề" giữa bóng n và bóng 1 tự động thỏa (vì bóng 1 đã là Đ) → bóng 2,\ldots,n chỉ cần thỏa ràng buộc trên một hàng thẳng dài n-1 → có F_{n+1} cách (theo Kỹ thuật 1).
• Nếu bóng 1 TẮT: bóng 2 và bóng n bắt buộc phải BẬT (vì kề bóng 1) → bóng 3,\ldots,n-1 là một hàng thẳng dài n-3 → có F_{n-1} cách.
Tổng: F_{n+1}+F_{n-1} — đây chính là số Lucas L_n, một hằng đẳng thức nổi tiếng nối Fibonacci và bài toán đếm trên vòng tròn.
✅ Với n=6: F_7+F_5 = 13+5 = 18 cách — khớp hoàn toàn với đếm vét cạn toàn bộ 2^6=64 cấu hình bằng code.
📌 Ứng dụng thực chiến — đề thi chọn HSG Quảng Trị 2026
Đề bài gốc (nguồn: đề chọn HSG tỉnh Quảng Trị, năm 2026): cho đa giác lồi 2026 đỉnh A_1A_2\ldots A_{2026}. Tô màu tất cả các đỉnh bởi một trong hai màu đỏ hoặc xanh, mỗi đỉnh chỉ được tô một màu. Tính số cách tô màu sao cho không có hai đỉnh nào kề nhau đều được tô xanh.
Áp dụng ngay kỹ thuật vành hóa (đỏ ↔ Đ, xanh ↔ T, n=2026): nếu A_1 đỏ thì A_2,\ldots,A_{2026} là hàng thẳng 2025 đỉnh → F_{2027} cách; nếu A_1 xanh thì A_2, A_{2026} buộc đỏ, còn A_3,\ldots,A_{2025} là hàng thẳng 2023 đỉnh → F_{2025} cách. Tổng: F_{2027}+F_{2025}.
✅ Đã kiểm chứng độc lập bằng code (không chỉ tin theo lời giải gốc): công thức tổng quát L_n=F_{n+1}+F_{n-1} được đối chiếu bằng đếm vét cạn cho n=3 đến n=14 — khớp tuyệt đối ở mọi giá trị. Kết quả F_{2027}+F_{2025} cho đa giác 2026 đỉnh là chính xác về mặt toán học.
5. Kỹ thuật 3 — Phân rã kiểu Catalan: "điểm chạm 0 đầu tiên"
Lớp bài toán khó nhất trong hàm sinh là khi ràng buộc không chỉ nằm ở một cặp phần tử kề nhau, mà nằm ở toàn bộ mọi đoạn đầu (mọi tiền tố) của dãy — ví dụ "số dư lũy tích không bao giờ âm". Mẹo xử lý: coi mỗi bước +1/-1 là một bước đi, và phân rã dãy tại thời điểm nó chạm mốc 0 lần đầu tiên . Đây chính là ý tưởng sinh ra dãy số Catalan nổi tiếng.
Ví dụ nguyên bản — Sổ quỹ không bao giờ âm
Đề bài: Một thủ quỹ ghi lại n giao dịch liên tiếp, mỗi giao dịch hoặc nộp quỹ (+1 đơn vị) hoặc rút quỹ (−1 đơn vị). Biết quỹ bắt đầu ở mức 0 và số dư sau mỗi giao dịch không bao giờ âm . Hỏi có bao nhiêu dãy giao dịch hợp lệ với n=8?
Bước 1 — Dãy "cân bằng" (Catalan): gọi một dãy có tổng bằng 0 và mọi tiền tố \ge 0 là "cân bằng". Một dãy cân bằng khác rỗng luôn phân rã duy nhất thành (+1)\,Q\,(-1)\,S với Q,S cũng cân bằng (chính là bài toán ngoặc đúng kinh điển). Nếu gọi hàm sinh theo nửa độ dài là G(X) thì G(X)=1+XG(X)^2, giải ra G(X)=\dfrac{1-\sqrt{1-4X}}{2X} — đây chính là hàm sinh Catalan.
Bước 2 — Dãy hợp lệ (không cần quay về 0): mọi dãy hợp lệ độ dài 2n phân rã duy nhất theo các "lần chạm đáy" thành xen kẽ các khối cân bằng và các bước +1 tự do dư ra. Biến đổi đại số dẫn tới hàm sinh A(X) = \dfrac{G(X)}{2-G(X)} = \dfrac{1}{\sqrt{1-4X}} = \sum_{n\ge0}\binom{2n}{n}X^n.
Kết luận: số dãy hợp lệ độ dài 2n là \binom{2n}{n}. Với n=8 (tức 2n=8, n=4): \binom{8}{4}=70.
✅ Đã kiểm chứng: đếm vét cạn toàn bộ 2^8=256 dãy \pm1 độ dài 8, lọc theo điều kiện số dư không âm ở mọi tiền tố → đúng 70 dãy, khớp \binom{8}{4}.
📌 Ứng dụng thực chiến — đề thi chọn HSG Quảng Trị 2026 (tiếp)
Đề bài gốc (phần 2): vẫn đa giác lồi 2026 đỉnh nói trên, tô màu đỏ/xanh. Tính số cách tô màu sao cho với mọi k\in\{1,\ldots,2026\}, trong k đỉnh A_1,\ldots,A_k, số đỉnh đỏ không ít hơn số đỉnh xanh.
Đây chính xác là bài toán "sổ quỹ" ở trên với đỏ = +1, xanh = -1, và tổng độ dài n=2026 (chẵn). Áp dụng trực tiếp kết quả \binom{n}{n/2} với n=2026:
Số cách tô màu = \dbinom{2026}{1013}
✅ Đã kiểm chứng độc lập bằng code: công thức tổng quát "số dãy \pm1 độ dài n với mọi tiền tố \ge0 bằng \binom{n}{\lceil n/2\rceil}" được đối chiếu bằng đếm vét cạn cho n=1 đến n=14 — khớp tuyệt đối ở mọi giá trị (kể cả n lẻ). Với n=2026 chẵn, \lceil n/2\rceil = 1013, nên \binom{2026}{1013} là đáp số chính xác.
6. Tự kiểm tra nhanh — 6 câu hỏi hàm sinh
Tất cả các câu dưới đây là ví dụ nguyên bản của LUKATO, số liệu hoàn toàn khác đề gốc, đã được kiểm chứng độc lập bằng code. Che đáp án lại và tự làm trước khi xem!
Câu 1. Trong khai triển (1+X)^5, hệ số của X^2 là bao nhiêu? Đáp số: \binom{5}{2}=10.
Câu 2. Một tập hợp có 6 phần tử. Hỏi có bao nhiêu tập con có số phần tử chẵn (kể cả tập rỗng)? (Gợi ý: xét (1+X)^6 và cộng các hệ số ở bậc chẵn.) Đáp số: 32 tập con — đã kiểm chứng bằng khai triển đa thức: tổng hệ số bậc chẵn của (1+X)^6 bằng đúng 2^5=32.
Câu 3. Lát kín một hàng 1\times 6 bằng ba loại gạch độ dài 1, 2, 3 (không giới hạn số lượng mỗi loại). Hỏi có bao nhiêu cách? (Gợi ý: hàm sinh một viên gạch là X+X^2+X^3.) Đáp số: 24 cách — hàm sinh cả hàng là 1/(1-X-X^2-X^3), hệ số X^6 bằng 24 (kiểm chứng bằng đệ quy vét cạn).
Câu 4. Vòng 10 bóng đèn LED, không có 2 bóng TẮT liền kề (kể cả cặp cuối–đầu). Hỏi có bao nhiêu cách bật/tắt? Đáp số: F_{11}+F_9 = 89+34 = 123 cách — khớp đếm vét cạn 2^{10}=1024 cấu hình.
Câu 5. Một dãy 12 giao dịch \pm1, số dư không bao giờ âm tại bất kỳ thời điểm nào. Hỏi có bao nhiêu dãy? Đáp số: \binom{12}{6}=924 — khớp đếm vét cạn 2^{12}=4096 dãy.
Câu 6. 4 bạn chia nhau 7 viên kẹo, mỗi bạn nhận từ 0 đến 3 viên. Hỏi có bao nhiêu cách chia hết đúng 7 viên? Đáp số: 40 cách — hệ số X^7 trong (1+X+X^2+X^3)^4, khớp đếm vét cạn toàn bộ 4^4=256 bộ.
Bẫy thường gặp: khi bài toán là vòng tròn (cyclic), tuyệt đối không được dùng thẳng công thức "hàng thẳng" 1/(1-X-X^2) — phải cố định một mốc trước (Kỹ thuật 2), nếu không sẽ đếm sai vì bỏ sót ràng buộc giữa phần tử cuối và phần tử đầu.
7. Lộ trình luyện tập 5 ngày
Ngày · Nội dung · Mục tiêu
1 · Thuộc lòng 3 khối xây dựng cơ bản (1/(1-X), 1+X, chuỗi chặn trên) + làm lại ví dụ chia kẹo · Chuyển được 1 câu "chọn có điều kiện" thành hàm sinh đúng trong <2 phút
2 · Kỹ thuật xây khối — luyện lát gạch với 2, 3, rồi 4 loại gạch khác độ dài · Viết đúng hàm sinh của "một khối" mà không cần nhìn lại lý thuyết
3 · Kỹ thuật vành hóa — tự làm lại ví dụ LED với n=8, n=10, so khớp với công thức Lucas L_n · Nhận diện bài toán vòng tròn và biết "cắt" đúng chỗ
4 · Kỹ thuật Catalan/ballot — luyện phân rã "điểm chạm 0 đầu tiên" với n=6, n=10 · Viết được phương trình G=1+XG^2 mà không cần tra cứu