1. BÀI TOÁN XẾP TUYẾN TÍNH (TRÊN ĐƯỜNG THẲNG)
Xếp các phần tử cùng một loại
1.1. Kỹ thuật Bó phần tử (Block Technique) -- "Đứng cạnh nhau"
- Bản chất: Gom $k$ phần tử có ràng buộc kề nhau thành một khối duy nhất $X$.
- Quy trình:
- Hoán vị nội bộ các phần tử trong khối $X$: có $k!$ cách.
- Xếp khối $X$ cùng $(n-k)$ phần tử còn lại: có $(n-k+1)!$ cách.
- Tổng số cách: $k! \times (n-k+1)!$.
1.2. Kỹ thuật Hoán vị lặp (Multinomial) -- Phần tử lặp lại
- Bản chất: Sắp xếp $n$ phần tử, trong đó có $n_1$ loại 1, $n_2$ loại 2, $\dots$, $n_k$ loại $k$ ($\sum n_i = n$).
- Công thức:
$$ P_n(n_1, n_2, \dots, n_k) = \frac{n!}{n_1! \, n_2! \, \dots \, n_k!} $$
1.3. Kỹ thuật Tính tổng theo từng hàng (Digit-Sum by Column)
- Bản chất: Tính tổng của tất cả các số lập được bằng cách xét tính đối xứng xuất hiện của mỗi chữ số $d \in D$ ở từng vị trí.
- Công thức: $\text{Tổng} = \left(\sum d_i\right) \times (\text{Số lần xuất hiện ở 1 hàng}) \times \underbrace{11\dots1}_{m \text{ chữ số}}$.
1.4. Kỹ thuật Lùa cừu vào chuồng (Quy trình đếm độc lập)
- Bản chất: Phân rã bài toán đếm phức tạp thành một chuỗi các công đoạn (quy tắc nhân), chọn các phần tử có ràng buộc gắt gao nhất trước.
Xếp phần tử nhiều loại / Khoảng cách phức tạp
2.1. Kỹ thuật Vách ngăn -- "Không đứng cạnh nhau"
- Bản chất: Xếp $m$ phần tử tự do làm vách ngăn trước, tạo ra $m+1$ khoảng trống (khe hở). Đặt $k$ phần tử không kề nhau vào khe ($k \le m+1$).
- Công thức cơ bản: $m! \times A_{m+1}^k$.
2.2. Kỹ thuật Đánh số thứ tự (Vách ngăn Level 2)
- Giả thiết: Chọn $k$ phần tử từ $\{1, 2, \dots, n\}$ sao cho khoảng cách giữa 2 phần tử $\ge d$ (tức là $x_{i+1} - x_i \ge d$).
- Đại số hóa quy luật:
$$ 1 \le x_1 < x_2 < \dots < x_k \le n \quad \text{với } x_{i+1} - x_i \ge d $$
- Đổi biến: Đặt $y_i = x_i - (i-1)(d-1)$. Hệ điều kiện trở thành:
$$ 1 \le y_1 < y_2 < \dots < y_k \le n - (k-1)(d-1) $$
- Số cách chọn: $C_{n - (k-1)(d-1)}^k$.
2.3. Bài toán Chia kẹo Euler (Phương trình nghiệm nguyên)
- Dạng nguyên dương: Số nghiệm nguyên dương ($x_i \ge 1$) của phương trình $x_1 + \dots + x_k = n$ là: $$ C_{n-1}^{k-1} $$
- Dạng nguyên không âm: Số nghiệm nguyên không âm ($x_i \ge 0$) là: $$ C_{n+k-1}^{k-1} $$
- Dạng có điều kiện biên ($x_i \ge c_i$): Đổi biến $y_i = x_i - c_i + 1 \ge 1$ đưa về dạng nguyên dương.
2.4. Các Mô hình lai (Hybrid) & Bổ đề Kaplansky
- Block & Gap: Vừa có nhóm kề nhau, vừa có nhóm rời nhau: Bó khối $\Rightarrow$ Xếp vách ngăn tự do $\Rightarrow$ Đặt khối vào khe hở.
- Bổ đề Kaplansky thẳng: Số tập con $k$ phần tử từ $\{1, \dots, n\}$ không chứa 2 phần tử liên tiếp là $C_{n-k+1}^k$.
- Bổ đề Kaplansky tròn: Chọn $k$ phần tử từ $n$ phần tử trên đường tròn sao cho không có 2 phần tử kề nhau: $$ \frac{n}{n-k} C_{n-k}^k $$
2. BÀI TOÁN XẾP PHI TUYẾN (VÒNG TRÒN, Ô LƯỚI)
2.1. Hoán vị vòng tròn (Circular Permutation)
- Số cách xếp $n$ phần tử khác nhau vào bàn tròn $n$ vị trí: $(n-1)!$.
- Phá vỡ tính đối xứng: Cố định 1 phần tử làm mốc $\Rightarrow$ Các vị trí còn lại trở thành bài toán thẳng.
2.2. Xếp trên Ô lưới / Đường đi ngắn nhất (Grid Walking)
- Đếm đường đi ngắn nhất từ $(0,0)$ đến $(m,n)$ qua lưới (bước phải $R$, đi lên $U$): Hoán vị lặp của $m$ bước $R$ và $n$ bước $U \Rightarrow C_{m+n}^m$.
2.3. Xếp phần tử không đối diện nhau qua tâm bàn tròn
- Phương pháp: Dùng nguyên lý bù trừ hoặc đếm gián tiếp: Tổng số cách trừ đi các trường hợp có ít nhất $1, 2, \dots$ cặp đối diện.
3. ĐẾM SỐ HỌC VÀ CÁC TÍNH CHẤT ĐỒNG DƯ
Tương quan Số học & Ước số
3.1. Phân tích Thừa số nguyên tố & Đếm số ước
- Cho $N = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$. Số ước nguyên dương của $N$ là: $$ d(N) = (a_1 + 1)(a_2 + 1)\dots(a_k + 1) $$
3.2. Kỹ thuật Gián tiếp tương quan (Bù trừ / Song ánh)
- Thiết lập ánh xạ 1-1 (song ánh) hoặc dùng công thức phủ định $N(\text{thỏa mãn}) = N(\text{tổng}) - N(\text{vi phạm})$.
Bài toán Chia hết & Cấu trúc Đồng dư
3.3. Cân bằng phần tử khóa (Key-Element)
- Khi lập số $m$ chữ số thỏa mãn điều kiện chia hết, chọn tự do $m-1$ chữ số đầu. Luôn tồn tại số cách cố định cho chữ số cuối cùng để tổng chia hết.
3.4. Phân tập Đồng dư (Partition by Modulo Classes)
- Phân chia tập số thành các lớp đồng dư modulo $m$: $X_0, X_1, \dots, X_{m-1}$. Chọn $k$ số có tổng chia hết cho $m$ quy về việc kết hợp các lớp đồng dư sao cho $\sum r_i \equiv 0 \pmod m$.
4. HÌNH HỌC TỔ HỢP TRONG ĐA GIÁC ĐỀU
Cho đa giác đều $A_1A_2\dots A_n$ ($n$ đỉnh) nội tiếp đường tròn $(O)$.
Đếm Tam giác & Tứ giác
4.1. Đếm các loại Tam giác
- Tam giác vuông: Chỉ có khi $n$ chẵn ($n = 2m$). $$ N_{\text{vuông}} = \frac{n}{2} \times (n - 2) $$
- Tam giác đều: Chỉ có khi $n \ \vdots \ 3$. $$ N_{\text{đều}} = \frac{n}{3} $$
- Tam giác cân (không đều): $$ N_{\text{cân}} = n \times \left[ \frac{n - 1}{2} \right] - 2 \times N_{\text{đều}} \quad (\text{nếu } n \ \vdots \ 3) $$
- Tam giác tù / nhọn:
- Tù: Cố định 1 đỉnh góc tù, đếm 2 đỉnh nằm cùng nửa đường tròn.
- Nhọn: $N_{\text{nhọn}} = C_n^3 - N_{\text{vuông}} - N_{\text{tù}}$.
4.2. Đếm Tứ giác & Đường chéo
- Số đường chéo: $\frac{n(n-3)}{2}$.
- Số tứ giác bất kỳ: $C_n^4$.
- Hình chữ nhật: Có khi $n$ chẵn $\Rightarrow N_{\text{HCN}} = C_{n/2}^2$.
- Hình thang cân: Chọn 1 trục đối xứng $\Rightarrow$ Chọn 2 cặp đỉnh đối xứng qua trục đó.
5. CHUYÊN ĐỀ NÂNG CAO KHÁC
5.1. Bài toán Phân phối / Chia đồ vật
- Vật KHÁC NHAU vào hộp KHÁC NHAU: Dùng hoán vị lặp (nếu phân hoạch) hoặc nguyên lý Bù trừ / số Stirling loại 2.
- Vật GIỐNG NHAU vào hộp GIỐNG NHAU: Phân hoạch $n = x_1 + \dots + x_k$ với $x_1 \ge \dots \ge x_k$. Chặn biến lớn nhất và bấm Casio tổng $\sum f(x_1)$.
5.2. Kỹ thuật Đối xứng / Trục định vị (CSC, CSN)
- CSC: $a+c=2b \Rightarrow$ $b$ là tâm đối xứng.
- CSN: $ac=b^2 \Rightarrow$ phân tích nguyên tố & đối xứng số mũ.
- Biểu đồ Venn: Cố định các vùng giao nhau trước.
5.3. Xác suất nâng cao & Quy hoạch truy hồi
- Cây điều kiện & Markov: Lập sai phân $u_n = a u_{n-1} + b u_{n-2} \Rightarrow$ Casio / PT đặc trưng.
- Dừng phép thử Bernoulli: Dừng ở ván $n$ khi thắng ván $k$: $$ P = p \times \left[ C_{n-1}^{k-1} \, p^{k-1} \, (1-p)^{(n-1)-(k-1)} \right] $$
- Tô màu TDM: Tô $n$ đỉnh bằng $k$ màu, kề nhau khác màu: $$ P_n(k) = (k-1)^n + (-1)^n(k-1) $$