tailieunhanh - Bài giảng Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 1) - GVC ThS. Võ Minh Đức

Bài giảng Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 1) do GVC ThS. Võ Minh Đức biên soạn trình bày về: các nguyên lý đếm cơ bản và một số bài toán đếm cơ bản. Với các bạn chuyên ngành Toán học thì đây là một tài liệu hữu ích. | 10/3/2014 1 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk CÁC PHƯƠNG PHÁP ĐẾM VÀ NGUYÊN LÝ DIRICHLET Ch­ư¬ng II 1 10/3/2014 2 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN II. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN III. SINH CÁC HOÁN VỊ VÀ TỔ HỢP IV. NGUYÊN LÝ DIRICHLET. V. HỆ THỨC TRUY HỒI NỘI DUNG 2 10/3/2014 3 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN Nguyên lý cộng Nguyên lý nhân Nguyên lý bù trừ 10/3/2014 4 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN Nguyên lý cộng Giả sử có k công việc T1, T2, , Tk . Các công việc này có thể làm bằng n1, n2, , nk cách tương ứng và giả sử rằng không có hai việc nào có thể làm đồng thời. Khi đó số cách để làm một trong k công việc đó là: n1+ n2+ + nk 10/3/2014 5 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (2) Ví dụ 1: Một SV cần chọn một bài tập trong ba danh sách tương ứng có 23, 15 và 39 bài. Số cách chọn sẽ là: (?) 23+15+39 =77 cách. (theo nguyên lý cộng ) 10/3/2014 6 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (3) Ví dụ 2: Cho đoạn chương trình m:=0; For i:=1 to n1 do m:=m+1; For i:=1 to n2 do m:=m+1; For i:=1 to nk do m:=m+1; {m = n1} {m = n1 + n2} m = n1 + n2 + . . . + nk (theo nguyên lý cộng ) Chương trình trên cho giá trị của m là bao nhiêu? 10/3/2014 7 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (4) Nguyên lý cộng: (phát biểu dưới dạng tập hợp như sau) Nếu A1, A2, , An là các tập hợp đôi một rời nhau, khi đó số phần tử của hợp các tập hợp này bằng tổng các phần tử của các tập hợp đã cho. 10/3/2014 8 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (5) 2. Nguyên lý nhân Giả sử một công việc T nào đó được tách ra thành k công việc nhỏ hơn T1, T2, , Tk. Nếu việc Ti có thể làm bằng ni cách sau khi các công việc T1, T2, ,Ti-1 đã làm được, thì để hoàn thành công việc T cần phải có nk c¸ch. 10/3/2014 9 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk CÁC VÍ DỤ Ví dụ 1: Để đánh biển số xe môtô người ta dùng một số có | 10/3/2014 1 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk CÁC PHƯƠNG PHÁP ĐẾM VÀ NGUYÊN LÝ DIRICHLET Ch­ư¬ng II 1 10/3/2014 2 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN II. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN III. SINH CÁC HOÁN VỊ VÀ TỔ HỢP IV. NGUYÊN LÝ DIRICHLET. V. HỆ THỨC TRUY HỒI NỘI DUNG 2 10/3/2014 3 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN Nguyên lý cộng Nguyên lý nhân Nguyên lý bù trừ 10/3/2014 4 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN Nguyên lý cộng Giả sử có k công việc T1, T2, , Tk . Các công việc này có thể làm bằng n1, n2, , nk cách tương ứng và giả sử rằng không có hai việc nào có thể làm đồng thời. Khi đó số cách để làm một trong k công việc đó là: n1+ n2+ + nk 10/3/2014 5 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (2) Ví dụ 1: Một SV cần chọn một bài tập trong ba danh sách tương ứng có 23, 15 và 39 bài. Số cách chọn sẽ là: (?) 23+15+39 =77 cách. (theo nguyên lý cộng ) 10/3/2014 6 GVC, ThS. Võ