- Hoán vị lặp: Kỹ thuật gom khối, xen kẽ vào khe trống, bài toán lập số và bài toán đếm đường đi trên lưới tọa độ.
- Hoán vị vòng quanh: Nguyên lý chọn điểm mốc, bài toán bàn tròn có thứ tự/không thứ tự, quan hệ kề nhau - đối diện và vòng lật ngược.
- Hoán vị sai chỗ (Derangement): Công thức bao hàm - loại trừ, hệ thức truy hồi, bài toán đúng cố định \(r\) vị trí và ứng dụng xếp xe trên bàn cờ.
A. NGUYÊN TẮC CHỌN PHƯƠNG PHÁP
- Nếu tráo đổi hai phần tử cùng tính chất/cùng loại mà cấu hình sắp xếp không thay đổi: Áp dụng hoán vị lặp.
- Nếu các trạng thái sắp xếp trùng khít nhau thông qua một phép quay quanh tâm: Cố định một phần tử làm mốc để chuyển về hoán vị thẳng.
- Nếu bài toán yêu cầu đối chiếu vị trí sau khi xếp với vị trí ban đầu: Phân loại theo số lượng phần tử giữ nguyên vị trí.
1. HOÁN VỊ LẶP
Xét bài toán sắp xếp \(n\) phần tử thành một hàng ngang, trong đó gồm \(k\) loại khác nhau với số lượng tương ứng là \(n_1, n_2, \dots, n_k\) (các phần tử cùng loại hoàn toàn giống nhau) sao cho \(n_1 + n_2 + \dots + n_k = n\). Khi đó, số cách xếp phân biệt được xác định bởi công thức:
\[ P_n(n_1, n_2, \dots, n_k) = \frac{n!}{n_1! \, n_2! \cdots n_k!} \]Các dạng toán thường gặp:
Dạng 1. Phương pháp gom khối: Khi các phần tử cùng một loại bắt buộc phải đứng cạnh nhau liên tiếp, ta coi toàn bộ nhóm đó là một khối duy nhất, sau đó tiến hành hoán vị các khối và những phần tử tự do còn lại.
Dạng 2. Phương pháp xếp khe (vách ngăn):
- Sắp xếp nhóm đối tượng không bị ràng buộc trước để tạo ra các khoảng trống (khe). Giả sử có \(m\) đối tượng thì tạo ra \(m + 1\) khe (bao gồm cả hai đầu).
- Nếu cần tạo thành đúng hai khối từ \(r \ge 2\) phần tử giống nhau: Chọn 2 khe khác nhau rồi biểu diễn \(r\) thành tổng của hai số nguyên dương theo thứ tự từ trái sang phải.
- Nếu yêu cầu không có hai phần tử cùng loại nào đứng cạnh nhau: Đặt tối đa một phần tử vào mỗi khe trống.
Dạng 3. Bài toán lập số: Chú ý điều kiện chữ số đầu tiên phải khác 0. Ta có thể chọn chữ số đầu tiên trước rồi hoán vị các chữ số còn lại, hoặc lấy tổng số cách xếp trừ đi các trường hợp có chữ số 0 đứng đầu.
Dạng 4. Đường đi trên lưới ô vuông và thứ tự ưu tiên:
- Mỗi đường đi trên lưới gồm \(a\) bước sang phải và \(b\) bước lên trên tương ứng với một hoán vị của hai loại bước đi. Tổng số đường đi ngắn nhất là \(C_{a+b}^a\).
- Nếu lộ trình buộc phải đi qua một điểm cố định: Nhân số cách đi độc lập trên hai đoạn nối tiếp.
- Nếu lộ trình phải tránh một điểm cố định: Lấy tổng số đường đi trừ đi số đường đi qua điểm đó.
- Trường hợp mỗi cột có một quy tắc xử lý với thứ tự cố định, mỗi kế hoạch xử lý là một chuỗi các cột được chọn. Nếu cột thứ \(i\) có \(n_i\) công việc, ta áp dụng công thức hoán vị lặp cho chuỗi này.
2. HOÁN VỊ VÒNG QUANH (HOÁN VỊ TRÒN)
Nhận dạng: Xếp \(n \ge 2\) phần tử đôi một phân biệt xung quanh một vòng tròn khép kín, trong đó hai cách xếp được xem là trùng nhau nếu cách này thu được từ cách kia qua một phép quay. Bằng cách cố định 1 phần tử làm mốc định vị, \(n - 1\) phần tử còn lại được sắp xếp theo chiều kim đồng hồ.
\[ Q_n = (n - 1)! \]Các trường hợp đặc biệt:
- Ghế phân biệt: Nếu các vị trí ngồi được đánh số cụ thể hoặc có một vị trí đặc thù làm mốc (như ghế sát cửa sổ, cửa ra vào), bài toán trở thành hoán vị thẳng và có \(n!\) cách xếp.
- Ràng buộc kề nhau hoặc đối diện: Cố định người thứ nhất làm chuẩn. Khi đó, người thứ hai có đúng 2 ghế bên cạnh để chọn (nếu \(n \ge 3\)), hoặc 1 ghế đối diện trực diện (khi \(n\) là số chẵn). Sau đó, xếp các vị trí còn lại theo quy tắc thông thường.
- Vòng có thể lật ngược (chuỗi hạt, vòng đeo tay): Với \(n \ge 3\) hạt phân biệt, mỗi cách xếp theo phép quay sẽ tương đương với một cách xếp theo chiều ngược lại khi lật mặt phẳng. Nếu hai cấu hình đối xứng này được xem là một, số cách tạo vòng là:
3. HOÁN VỊ SAI CHỖ (DERANGEMENT)
Gọi \(D_n\) là số hoán vị của \(n\) phần tử sao cho không có bất kỳ phần tử nào nằm ở vị trí ban đầu của nó. Sử dụng nguyên lý bù trừ (Bao hàm - Loại trừ), với \(n \ge 1\), ta có công thức tổng quát:
\[ D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right) \]Các dạng toán và tính chất:
Dạng 1. Sai chỗ hoàn toàn: Có thể tính trực tiếp qua công thức tổng quát hoặc sử dụng hệ thức truy hồi:
\[ D_0 = 1, \quad D_1 = 0 \] \[ D_n = (n - 1)(D_{n-1} + D_{n-2}) \quad (\forall n \ge 2) \](Các giá trị quen thuộc: \(D_1 = 0\), \(D_2 = 1\), \(D_3 = 2\), \(D_4 = 9\), \(D_5 = 44\), \(D_6 = 265\)...)
Dạng 2. Đúng chính xác \(r\) vị trí: Chọn ra \(r\) phần tử giữ nguyên vị trí ban đầu, sau đó làm sai chỗ toàn bộ \(n - r\) phần tử còn lại. Số cách là:
\[ C_n^r \cdot D_{n-r} \]Dạng 3. Ứng dụng tính xác suất: Khi mọi cách hoán vị có cùng khả năng xuất hiện, chia số cấu hình thuận lợi cho không gian mẫu là \(n!\). Ví dụ, xác suất có ít nhất một phần tử nằm đúng vị trí xuất phát là:
\[ P = 1 - \frac{D_n}{n!} \]Dạng 4. Bài toán bàn cờ và ghép cặp:
- Xếp \(n\) quân xe không ăn nhau trên bàn cờ \(n \times n\) sao cho mỗi hàng và mỗi cột có đúng một quân xe: Tương ứng với một hoán vị của tập hợp các cột. Quân xe nằm trên đường chéo chính đại diện cho một vị trí cố định (không bị sai chỗ).
- Với bài toán ghép cặp đôi mới từ các cặp ban đầu: Đánh số hai nhóm tương ứng sao cho cặp gốc cùng số thứ tự, bài toán đưa về đếm số hoán vị sai chỗ.
Lưu ý quan trọng: Trước khi áp dụng công thức giải, hãy kiểm tra kỹ ba yếu tố: các đối tượng có hoàn toàn phân biệt hay giống nhau, vị trí xếp có đánh số phân biệt không và có vị trí nào bị hạn chế/cấm hay không.