Chủ đề này có 1 trả lời

[nhungvienkimcuong]

Với mỗi số nguyên $n\ge 2$, gọi $a_n$ là số song ánh $f\colon \{1,2,\dots,n\}\to \{1,2,\dots,n\}$ thỏa mãn $f(k+1)-f(k)\neq 1$ với mọi $k=\overline{1,n-1}$.

a) Chứng minh rằng $a_n=(n-1)a_{n-1}+(n-2)a_{n-2}$ với mọi $n\ge 4$.

b) Kí hiệu $\left \lfloor x \right \rceil$ là số nguyên gần $x$ nhất. Chứng minh rằng $a_n=\frac{1}{n}\left \lfloor\frac{(n+1)!}{e} \right \rceil$ với mọi $n\ge 2$. 

[hxthanh]

$a_n$ theo định nghĩa là số các hoán vị của $\{1,2,..,n\}$ không có (hai) phần tử liên tiếp, gọi tắt là “hoán vị đẹp”
- Xây dựng các hoán vị $\{1,2,…,n\}$ từ $\{1,2,…,n-1\}$ bằng cách:
+ Thêm $n$ vào các hoán vị đẹp của $\{1,2,…,n-1\}$ có $(n-1)a_{n-1}$ cách (trừ vị trí sát bên phải của $n-1$)
+ Thêm $n$ vào các hoán vị có đúng 1 phần tử liên tiếp của $\{1,2,…,n-1\}$ - thêm $n$ vào giữa phần tử liên tiếp ấy.
- có $(n-2)a_{n-2}$ hoán vị như vậy.
Từ cách xây dựng trên ta có:
$a_n=(n-1)a_{n-1}+(n-2)a_{n-2}$ với $a_2=1,\;\; a_3=3$
…
Ta sẽ chứng minh rằng: $\boxed{a_n=\frac{(n+1)!}{n}\sum_{k=0}^{n+1}\frac{(-1)^k}{k!}}$
Chứng minh bằng quy nạp hay thế nào, tại sao lại có nó bạn vui lòng liên hệ tác giả! =))