Nguyên Lý Bù Trừ Tổng Quát Và ứng Dụng Trong Tổ Hợp | Xemtailieu

Trang chủ » Nguyên Lý Bù Trừ Tổng Quát » Nguyên Lý Bù Trừ Tổng Quát Và ứng Dụng Trong Tổ Hợp | Xemtailieu

Có thể bạn quan tâm

logo xemtailieu Xemtailieu Tải về Nguyên lý bù trừ tổng quát và ứng dụng trong tổ hợp
  • pdf
  • 4 trang
Định nghĩa 0.0.1. Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này, ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. Cho A1 , A2 là hai tập hữu hạn, khi đó | A1 ∪ A2 |=| A1 | + | A2 | − | A1 ∩ A2 | . Từ đó, với ba tập hữu hạn A1 , A2 , A3 , ta có: | A1 ∪ A2 ∪ A3 |=| A1 | + | A2 | + | A3 | − | A1 ∩ A2 | − | A1 ∩ A3 | − | A2 ∩ A3 | + | A1 ∩ A2 ∩ A3 |, và bằng quy nạp, với k tập hữu hạn A1 , A2 , ..., Ak , ta có: | A1 ∪ A2 ∪ ... ∪ Ak |= N1 − N2 + N3 − · · · + (−1)k−1 Nk , trong đó Nm (1 6 m 6 k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho, nghĩa là X | Ai1 ∩ Ai2 ∩ · · · ∩ Aim |. Nm = 16i1

Từ khóa » Nguyên Lý Bù Trừ Tổng Quát