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

[Saturina]

Cho số tự nhiên $n \ge 1$. Một hoán vị của tập $A= {1,2,3,...,n}$ được gọi là hoán vị bảo tồn $a \in A$ nếu như phần tử $a$ ở nguyên vị trí cũ của nó trong hoán vị mới. Kí hiệu $P_n(k)$ là số hoán vị bảo tồn đúng $k$ phần tử của $A$. Chứng minh rằng: $$\sum^n_{k=0}{kP_n(k)}=n!$$

Bài viết đã được chỉnh sửa nội dung bởi Saturina: 29-11-2022 - 20:57

[Hoang72]

Ta xét bài toán phụ: Cho $A = \{a_1,a_2,...,a_n\}$ và $B = \{b_1,b_2,...,b_n\}$. Đếm số song ánh $f: A\to B$ sao cho $f(a_i)\neq b_i,\forall i = \overline{1,n}$.

Bằng nguyên lí bao hàm loại trừ, dễ dàng chứng minh được kết quả của bài toán trên là: $\sum_{i=0}^n (-1)^i\frac{n!}{i!}$.

Như vậy, với mỗi $k=\overline{0,n}$ thì: $P_{n}(k) = \frac{n!}{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$.

Từ đây, dẫn đến: $\sum_{k=0}^n kP_n(k) = n!\sum_{k=1}^n\sum_{i=0}^{n-k}\frac{(-1)^i}{i!(k-1)!}$.

Ta chỉ cần chứng minh $\sum_{k=1}^n\sum_{i=0}^{n-k}\frac{(-1)^i}{i!(k-1)!} = 1$.

Rõ ràng tổng ở vế trái cũng chính là: $\sum_{k+i< n}\frac{(-1)^i}{i!k!}$.

Ta chứng minh $S_n = \sum_{k+i< n}\frac{(-1)^i}{i!k!}=1$ bằng phép quy nạp.

Khi $n=1$ thì đẳng thức đúng. Giả sử đẳng thức đúng với $n\in\mathbb N^*$.

Ta chứng minh đẳng thức đúng với $n+1$.

Dễ thấy: $S_{n+1} - S_n =\sum_{i+k = n}\frac{(-1)^i}{i!k!} = \frac{1}{n!}\sum_{i=0}^n(-1)^i\binom{n}{i}$.

Ta dễ dàng chứng minh được $\sum_{i=0}^n(-1)^i\binom{n}{i}=0$ bằng cách chứng minh số tập con có chẵn phần tử của $\{1;2;...;n\}$ là $2^{n-1}$.

Suy ra $S_{n+1} - S_n = 0$ hay $S_{n+1}=1$.

Theo nguyên lí quy nạp ta có $S_n=1,\forall n\in\mathbb N^*$.

Vậy $\sum_{k=0}^n kP_n(k) = n!$.

[nhungvienkimcuong]

Cho số tự nhiên $n \ge 1$. Một hoán vị của tập $A= {1,2,3,...,n}$ được gọ là hoán vị bảo tồn $a \in A$ nếu như phần tử $a$ ở nguyên vị trí cũ của nó trong hoán vị mới. Kí hiệu $P_n(k)$ là số hoán vị bảo tồn đúng $k$ phần tử của $A$. Chứng minh rằng: $$\sum^n_{k=0}{kP_n(k)}=n!$$

Định nghĩa $a$ được hoán vị bảo tồn bởi hoán vị cũng đồng nghĩa $a$ là điểm cố định của hoán vị đó. Ta sẽ đếm bằng hai cách: tổng số điểm cố định trong tất cả hoán vị của tập hợp $\{1,2,\dots,n\}$

• Đếm theo hoán vị: Tổng này chính là vế trái.
• Đếm theo phần tử: Có $(n-1)!$ hoán vị sao cho $i$ là điểm cố định, do đó tổng cần tính bằng $\sum_i(n-1)!=n\times (n-1)!=n!$