Tiêu đề C8 - C1 - QUY TAC DEM - ALG.docx ✅

MỤC LỤC §1 – QUY TẮC ĐẾM 2 Ⓐ. Tóm tắt kiến thức 2 Ⓑ. Trắc nghiệm Đ/S 5 Ⓒ. Trả lời ngắn 9 Ⓓ. Câu hỏi trắc nghiệm 16 §1 – QUY TẮC ĐẾM
Ⓐ. Tóm tắt kiến thức   ❶. Quy tắc cộng và sơ đồ hình cây  Quy tắc cộng  Giả sử một công việc nào đó có thể thực hiện theo một trong hai phương án khác nhau:  Phương án 1 có 1n cách thực hiện.  Phương án 2 có 2n cách thực hiện.  Khi đó số cách thực hiện công việc là : 12nn cách ➀. Một công việc được hoàn thành bởi một trong hai hành động. Nếu hành động này có m cách thực hiên, hành động kia có n cách thực hiên không trùng với bất kì cách nào của hành động thứ nhất thì công việc đó có m + n cách thực hiện.  Chú ý: số phần tử của tập hợp hữu hạn X được kí hiệu là X hoặc nX ➁. Quy tắc cộng được phát biểu ở trên thực chất là quy tắc đếm số phần tử của hợp hai tập hợp hữu hạn không giao nhau: Nếu A và B là các tập hợp hữu hạn không giao nhau thì nABnAnB Lý thuyết
 Mở rộng: Một công việc được hoàn thành bởi một trong k hành động 123,,,...,kAAAA .Nếu hành động A 1 có m 1 cách thực hiện, hành động A 2 có m 2 cách thực hiện,…, hành động A k có m k cách thực hiện và các cách thực hiên của các hành động trên không trùng nhau thì công việc đó có 123...kmmmm cách thực hiện. ❷. Quy tắc nhân ➀. Một công việc được hoàn thành bởi hai hành động liên tiếp.Nếu có m cách thực hiện hành động thứ nhất và ứng với mỗi cách đó có n cách thực hiện hành động thứ hai thì công việc đó có m.n cách thực hiện. Lý thuyết
➁. Mở rộng: Một công việc được hoàn thành bởi k hành động123,,,...,kAAAAliên tiếp. Nếu hành động A 1 có m 1 cách thực hiện, ứng với mỗi cách thực hiện hành động A 1 có m 2 cách thực hiện hành động A 2 ,…, có m k cách thực hiện hành động A k thì công việc đó có 123.......kmmmm cách hoàn thành.  NHẬN XÉT CHUNG: ➀. Để đếm số cách lựa chọn để thực hiện một công việc A bằng quy tắc cộng, ta thực hiện các bước như sau:  Bước 1: Phân tích xem có bao nhiêu phương án riêng biệt để thực hiện công việc A (có nghĩa công việc A có thể hoàn thành một trong các phương án A 1 , A 2 ,...,A n ).  Bước 2: Đếm số cách chọn 12,,...,nxxx trong các phương án 12,,...,nAAA .  Bước 3: Dùng quy tắc cộng ta tính được số cách lựa chọn để thực hiện công việc A là: 12nxxxx . ➁. Để đếm số cách lựa chọn để thực hiện công việc A bằng quy tắc nhân, ta thực hiện các bước sau:  Bước 1: Phân tích xem có bao nhiêu công đoạn liên tiếp cần phải tiến hành để thực hiện công việc A (giả sử A chỉ hoàn thành sau khi tất cả các công đoạn 12,,...,nAAA hoàn thành).  Bước 2: Đếm số cách chọn 12,,...,nxxx trong các công đoạn 12,,...,nAAA .  Bước 3: Dùng quy tắc nhân ta tính được số cách lựa chọn để thực hiện công việc A là: 12...nxxxx . ➂. Cách đếm gián tiếp (đếm phần bù)  Trong trường hợp hành động H chia nhiều trường hợp thì ta đi đếm phần bù của bài toán như sau: Lý thuyết