Gợi ý: Bài này có thể chuyển về bài sau. Cho một bảng \(n \times n\), mỗi ô đơn vị được điền một số từ \(1\) đến \(k\). Hỏi có bao nhiêu cách điền mà mỗi hàng và mỗi cột đều có ít nhất một số \(1\).

Ý tưởng là dùng nguyên lý bao hàm loại trừ. Gọi \(A_i\) là số cách để hàng \(i\) không có số 1 nào, \(B_i\) là số cách để cột \(i\) không có số \(1\) nào. Đáp số sẽ là \(k^{n^2}-|A_1 \cup A_2 \cup ... \cup A_n \cup B_1 \cup B_2 \cup ... \cup B_n|\), tức là tổng số bảng trừ đi hợp của tất cả các bảng không hợp lệ.

Để tính giá trị của hợp các tập hợp trên, chúng ta sẽ dùng công thức bao hàm loại trừ. Đồng thời lưu ý rằng để tính \(|A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_x} \cap B_{j_1} \cap B_{j_2} \cap ... \cap B_{j_y}|\)chúng ta chỉ cần quan tâm đến số hàng và số cột của nó, tức là \(x\) và \(y\).

Từ đó chúng ta có thể gộp những tập con có chung số hàng và số cột lại.