Hoán vị không bất động

Hôm nay có 2 sự kiện xảy ra với mình. Cả hai đều "biến động". Sự kiện thứ nhất thì mình đã post ở dưới rồi. Sự kiện thứ 2 là mình đã học được thêm 1 kiến thức quan trọng. Đó là Hoán vị không bất động. Vui vì biết thêm được 1 cái mới. Buồn vì bây giờ mình mới biết đến nó.

Định nghĩa:
Cho tập hợp $ A=\{1,2,...,n \}$. Một hoán vị $ B=\{x_1,x_2,...,x_n\} ; x_i \in A; i=\overline{1,n}$ được gọi là hoán vị có k điểm bất động nếu có đúng k phần tử $ x_i \in B$ sao cho $ x_i=i$.

Bài toán 1:
Có bao nhiêu hoán vị của n phần tử mà không có phần tử nào bất động?
Để giải quyết bài toán này, ta cần biết đến nguyên lý bù - trừ.

Định lý (Nguyên lý Bù-trừ)
Nếu $ A_1,A_2,...,A_n$ là các tập hữu hạn thì:

$$ \left |\bigcup_{i=1}^{n}A_i \right| =  \sum_{i=1}^{n}\left | A_i \right| -  \sum_{1\leq i<j\leq n}\left | A_i\cap A_j \right|+...+ (-1)^{n+1}\left | \bigcap_{i=1}^{n}A_i \right|.$$

Chứng minh
Ta sẽ chứng minh rằng mỗi phần tử bất kì của tập $ A=\bigcup_{i=1}^n A_i$ được đếm đúng 1 lần ở vế phải.
Thật vậy, xét phần tử bất kì $x \in A$ giả sử $x$ xuất hiện trong đúng $m$ tập $ A_i$. Khi đó, ở vế phải, số lần $x$ được đếm là:

$$ C_{m}^{1} - C_{m}^{2} + ... +  (-1)^{m+1}C_m^m=C_m^0 = 1$$

Ta có điều phải chứng minh.

Quay lại bài toán, ta sẽ tìm số các hoán vị không bất động bằng cách lấy tổng số các hoán vị trừ đi số các hoán vị có $k$ điểm bất động $(k = 1, 2, ..., n)$. Gọi $S_n$ là số hoán vị không bất động. Khi đó:

$ S_n = P_n - \left ( \sum_{i=1}^{n}\left | A_i \right |-\sum_{1\leq i<j\leq n}\left | A_i\cap A_j \right| +...

+ (-1)^{n+1}\left | \bigcap_{i=1}^{n}A_i \right| \right ).$

Trong đó $ A_i$ là tập hợp các hoán vị bất động phần tử $i$. Ta sẽ đi tính các số hạng bên vế phải. Muốn vậy ta tính số hoán vị có $k$ điểm bất động. Để tạo được hoán vị dạng này, ta chọn $k$ phần tử từ $n$ phần tử ban đầu và giữ bất động chúng. Có $ C_n^k$ cách.
Hoán vị $n - k$ phần tử còn lại, có $(n - k)!$ cách
Vậy có: $ C_n^k.(n-k)! = \frac{n!}{k!}$.

Áp dụng nguyên lý bù-trừ, ta có:

$$ S_n = n!-\frac{n!}{1!}+\frac{n!}{2!} - ... - (-1)^{n+1}\frac{n!}{n!}$$

Bài toán này thú vị vì nó không dừng lại ở đây. Ta sẽ đi tìm một biểu thức gọn hơn cho $ S_n$.

Xét khai triển Taylor cho hàm số $ f(x) = e^x$:

$$ e^x=1+ \frac{x}{1!} + \frac{x^2}{2!} + ... + \frac{x^n}{n!} + ...$$

Với $x = - 1$, ta có

$$ \frac{1}{e}=1 +  -\frac{1}{1!} +  \frac{1}{2!} + ... +  (-1)^n\frac{1}{n!} + ...$$

Khi đó:

$$n!\left (\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-...+\frac{(-1)^n}{n!} \right )+e^{-1} > \frac{n!+1}{e} , \text{ nếu n chẵn}$$

$$n!\left (\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-...+\frac{(-1)^n}{n!} \right )+e^{-1}<\frac{n!+1}{e} , \text{ nếu n lẻ}$$

Từ đây suy ra:

$$\left [ n! \left ( \frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-...+ \frac{(-1)^n}{n!} \right ) + e^{-1} \right ]=\left [ \frac{n!+1}{e} \right ]$$

Vậy $ S_n= \left [(n!+1)e^{-1} \right ] $

Bài toán này có ứng dụng là bài toán gửi thư. Nhưng sau đây tôi xin giới thiệu một ứng dụng khác của bài toán này.

Bài toán 2 : Có bao nhiêu cách xếp 8 con xe lên bàn cờ vua sao cho không có con xe nào nằm trên đường chéo chính (đường chéo nối góc ở bên trái và góc dưới bên phải) và không có con nào "ăn" con nào?

Giải

Đánh số bàn cờ vua như sau:
* Các hàng đánh số từ 1 đến 8 theo chiều từ trên xuống dưới;
* Các cột đánh số từ 1 đến 8 theo chiều từ trái qua phải.
Theo cách đánh số, đường chéo chính (trên bên trái - dưới bên phải) là:

$$ (1;1);(2;2);(3;3);(4;4);(5;5);(6;6);(7;7);(8;8)$$

Vì bàn cờ vua có 8 dòng, 8 cột nên ở mỗi dòng sẽ chỉ có đúng 1 quân xe, mỗi cột có đúng một quân xe.
Ta đánh số thứ tự quân xe theo cột mà chúng đứng.

$$12345678$$

Khi đó mỗi cách xếp thỏa mãn yêu cầu đầu bài tương ứng với 1 cách sắp xếp các chỉ số hàng sao cho không có hai chỉ số hàng bất kì nào trùng nhau và không có cặp chỉ số hàng và chỉ số cột bằng nhau. Chằng hạn:

$$ \begin{matrix} 12345678\\23456781 \end{matrix}$$

Như vậy số cách xếp là một hoán vj không bất động của 8 phần tử.
Số cách xếp là:

$$ \left [\frac{8!+1}{e} \right ] = 14833$$