Math Labs

Bài 1

Gọi pn(k)p_n(k) là số hoán vị của tập {1,…,n}\{1, \ldots, n\}, n≥1n \ge 1, có đúng kk điểm bất động. Chứng minh rằng ∑k=0nk⋅pn(k)=n!\sum_{k=0}^{n} k \cdot p_n(k) = n!. (Một hoán vị ff của tập SS là một song ánh từ SS lên chính nó; một phần tử ii của SS là điểm bất động của ff nếu f(i)=if(i) = i.)
Bước 1 trên 4: Đọc tổng đã cho như phép đếm các cặp điểm bất động
Bước trướcBước tiếp
Hiểu nôm na

Thay vì gộp các hoán vị theo số điểm bất động chúng có, chỉ cần đếm lần lượt từng cặp (hoán vị, điểm bất động) đang tồn tại — tổng số vẫn như vậy, chỉ nhìn từ góc khác.

∑k=0nk⋅pn(k)=#{(f,i):f is a permutation of {1,…,n}, f(i)=i}\sum_{k=0}^{n} k \cdot p_n(k) = \#\{(f,i) : f \text{ is a permutation of } \{1,\ldots,n\},\ f(i)=i\}
Phân tích chi tiết

Một hoán vị có đúng kk điểm bất động đóng góp đúng kk vào số hạng k⋅pn(k)k \cdot p_n(k), mỗi điểm bất động một đơn vị. Lấy tổng theo kk, ∑k=0nk⋅pn(k)\sum_{k=0}^{n} k \cdot p_n(k) đếm mọi cặp (f,i)(f,i) trong đó ff là một hoán vị của {1,…,n}\{1,\ldots,n\} và ii là một điểm bất động của ff, tức f(i)=if(i)=i.