Bài toán:
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?
Lời giải:
Dựa trên quy tắc gộp vào loại ra
B1: Có n! tất cả các hoán vị n phần tử
B2: Xây dựng phép đếm
+ Để có k điểm bất động ta chọn ra k trong n phần tử và giữ nguyên vị trí k phần tử này: Có $C_n^k$ cách
+ (n-k) phần tử còn lại có $(n-k)!$
Có $C_n^k(n-k)!=\dfrac{n!}{k!}$ cách tạo thành các hoán vị có k phần tử bất động theo phép đếm trênB3: Loại đi các phần tử đếm lặp
Trong phép đếm như trên, sẽ có phần tử có k+1 điểm bất động bị đếm lặp phải loại ra. Cũng theo phép đếm trên số hoán vị có k+1 phần tử bất động là $\dfrac{n!}{(k+1)!}$
...
Số các hoán vị không có điểm bất động tính theo phương pháp đếm như trên sẽ là
$S_n=n!-\dfrac{n!}{1!}+\dfrac{n!}{2!}-...+\dfrac{(-1)^nn!}{n!}$
$S_n=n!(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-...+\dfrac{(-1)^n}{n!})$
Thú vị ở chỗ công thức này có thể viết dưới dạng sau:
$S_n=n!\sum\limits_{k=0}^{n}\dfrac{(-1)^k}{k!}= \lfloor\dfrac{n!+1}{e}\rfloor$
Trong đó e là cơ số của logarit tự nhiên: e=2,718281828459..., kí hiệu [ ] là phần nguyên
Kiểm nghiệm một tí đã!
Với n=4 số hoán vị gồm 4 phần tử không bất động sẽ là $S_4=\lfloor\dfrac{4!+1}{e}\rfloor=9$
Cụ thể từ {1,2,3,4}
có {2,3,4,1}; {2,4,1,3}; {2,1,4,3}; {3,1,4,2}; {3,4,1,2}; {3,4,2,1}; {4,1,2,3}; {4,3,1,2}; {4,3,2,1}
Xét khai triển Taylor của hàm $y=e^x$
$e^x=1+\dfrac{x}{1!}+\dfrac{x^2}{2!}+...+\dfrac{x^n}{n!}+...$
Chuỗi hàm này hội tụ $\forall x$
Tại $x=-1$
$e^{-1}=\dfrac{1}{e}=\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-...+\dfrac{(-1)^n}{n!}+...$
Khi đó:
$n!(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-...+\dfrac{(-1)^n}{n!})>n!e^{-1}$ nếu n chẵn
$n!(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-...+\dfrac{(-1)^n}{n!})<n!e^{-1}$ nếu n lẻ
Hay:
$n!(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-...+\dfrac{(-1)^n}{n!})+e^{-1}>(n!+1)e^{-1}$ nếu n chẵn
$n!(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-...+\dfrac{(-1)^n}{n!})+e^{-1}<(n!+1)e^{-1}$ nếu n lẻ
Từ đây suy ra:
$[n!(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-...+\dfrac{(-1)^n}{n!})+e^{-1}]=\lfloor(n!+1)e^{-1}\rfloor$
$n!(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-...+\dfrac{(-1)^n}{n!})=\lfloor\dfrac{n!+1}{e}\rfloor$
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 15-12-2010 - 01:33
