Chuyên đề này sẽ luôn được bổ sung mong các bạn ủng hộ
Bài toán 1 (PUTNAM 2005 ) Cho $S_{n}$ là tập các hoán vị của tập hợp $\left \{ 1,2,... n\right \}.$. Xét $\pi \in S_{n}$ , đặt $\sigma (\pi )=1$ nếu $\pi$ là hoán vị chẵn và $\sigma (\pi )=-1$ nếu$\pi$ là hoán vị lẻ. Gọi $\nu (\pi )$ là số các điểm bất động của hoán vị $\pi$.
Chứng minh đẳng thức :
$\sum_{\pi \in S_{n}}^{} \therefore \frac{\sigma (\pi )}{\nu (\pi )+1}=(-1)^{n+1}\frac{n}{n+1}$
Lời giải
Đặt $I$ là ma trận đơn vị cấp n , $J_{x}$ là ma trận có các phần tử trên đường chéo chính bằng $x$ và các phần tử còn lại bằng 1. Khi đó
$J_{x}=\begin{bmatrix} x & 1 & ... &1 \\ 1& x &... &1 \\... & ... &... & ...\\1 & 1 & ... &x \end{bmatrix}$
Ta có thể dễ dàng tính được định thức của ma trận này $detJ_{x}=(x+n-1)(x-1)^{n-1}$ ( có thể tìm thấy trong nhiều tài liệu hiện nó nên không nêu ra ở đây)
Mặc khác, chúng ta có thể tính tổng này theo tổng các hoán vị :
$detJ_{x}=\sum_{\pi \in S_{n}}sgn(\pi )x^{\upsilon (\pi )}$
Lấy tích phân từ 0 tới 1 ( có sử dụng đến phép đổi biến $y=1-x$ ta thu được
$\sum_{\pi \in S_{n}}\frac{sgn(\pi )}{\upsilon(\pi )+1}=\int_{0}^{1}(x+n-1)(x-1)^{n-1}dx=\int_{0}^{1}(-1)^{n+1}(n-y)y^{n-1}dy=(-1)^{n+1}\frac{n}{n+1}$
Chú ý $\sigma (\pi )$ trong định nghĩa của bài toán chính là định nghĩa về dấu của phép thế nên ta có được đpcm
