Đến nội dung


Chú ý

Hệ thống gửi email của diễn đàn đang gặp vấn đề với một số tài khoản Gmail do chính sách bảo mật tăng cường của Google. Nếu bạn không nhận được email từ diễn đàn, xin hãy tạm thời dùng một địa chỉ email khác ngoài Gmail (trước hết bạn nên kiểm tra thùng rác hoặc thư mục spam của hộp thư, hoặc dùng chức năng tìm kiếm trong hộp thư với từ khoá "diendantoanhoc.org" để chắc chắn là email không nhận được).

BQT đang cố gắng khắc phục, mong các bạn thông cảm.


Hình ảnh

$\sum^n_{k=0}{kP_n(k)}=n!$

đếm bằng 2 cách

  • Please log in to reply
Chủ đề này có 2 trả lời

#1 Saturina

Saturina

    Binh nhất

  • Thành viên mới
  • 26 Bài viết
  • Giới tính:Nam
  • Đến từ:Hương Canh-Bình Xuyên-Vĩnh Phúc
  • Sở thích:Functional equation and algebra

Đã gửi 24-11-2022 - 23:13

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

$Em$ $đẹp$ $như$ $chiếc$ $cúp$ $Euro$ $2020$ $vậy$
$Vì$ $em$ $là$ $của$ $người$ $Ý$ $chứ$ $không$ $phải$ $Anh$ :(
:( :( 

 

$Thì$ $chả$ $thế$ $à$ $?$

 


#2 Hoang72

Hoang72

    Sĩ quan

  • Thành viên
  • 466 Bài viết
  • Giới tính:Nam
  • Đến từ:Hà Tĩnh
  • Sở thích:Codingg

Đã gửi 28-11-2022 - 23:13

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!$.



#3 nhungvienkimcuong

nhungvienkimcuong

    Thiếu úy

  • Thành viên
  • 575 Bài viết
  • Giới tính:Nam
  • Đến từ:Daklak
  • Sở thích:đã từng có

Đã gửi 29-11-2022 - 14:51

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!$

Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra  ~O) 

Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em  :wub: 

Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh  :ukliam2: 






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: đếm bằng 2 cách

1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh