›
›

Các phương pháp đếm và nguyên lý Dirichlet - ThS. Võ Minh Đức (Phần 1)

pptx 35 trang phuongnguyen 4580
Download
Bạn đang xem 20 trang mẫu của tài liệu "Các phương pháp đếm và nguyên lý Dirichlet - ThS. Võ Minh Đức (Phần 1)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxcac_phuong_phap_dem_va_nguyen_ly_dirichlet_ths_vo_minh_duc_p.pptx

Nội dung text: Các phương pháp đếm và nguyên lý Dirichlet - ThS. Võ Minh Đức (Phần 1)

  1. ChCh­­ưư¬¬ng￿ng￿IIII CÁC PHƯƠNG PHÁP ĐẾM VÀ NGUYÊN LÝ DIRICHLET 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 1
  2. NNỘỘI￿DUNGI￿DUNG 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 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2
  3. I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN 1. Nguyên lý cộng 2. Nguyên lý nhân 3. Nguyên lý bù trừ 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 3
  4. I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN 1. 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à: nn11+￿n+￿n22+￿+￿ +￿n+￿nkk￿￿ 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 4
  5. 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 ) 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 5
  6. 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; {m￿=￿n1} For i:=1 to n2 do m:=m+1; {m￿=￿n1￿+￿n2} For i:=1 to nk do m:=m+1; Chương￿ trình￿ trên￿ cho￿ giá￿ trị￿ của￿ m￿ là￿ bao￿nhiêu? m￿=￿n1￿+￿n2￿+￿.￿.￿.￿+￿nk￿(theo￿nguyên￿lý￿cộng￿) 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 6
  7. 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. 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 7
  8. 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ó nn11.n.n22 nnk￿￿￿￿k￿￿￿￿cc¸¸ch.ch. 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 8
  9. CÁC VÍ DỤ Ví dụ 1: Để đánh biển số xe môtô người ta dùng một số có 4 chữ số, hỏi có bao nhiêu biển số xe được đánh? ĐÁP SỐ: 104 cách 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 9
  10. CÁC VÍ DỤ Ví dụ 2: Để ghi nhãn cho những chiếc ghế trong một giảng đường người ta dùng một chuỗi kí tự, kí tự đầu tiên là một chữ cái và các kí tự còn lại là các chữ số biểu diễn một số nguyên dương không vượt quá 100. Nhiều nhất có thể có bao nhiêu chiếc ghế được ghi nhãn? Giải: Có 26 cách chọn chữ cái, mỗi cách chọn lại có 100 cách chọn số. Vậy theo NLN có: 26.100= 2600 cách 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 10
  11. CÁC VÍ DỤ Ví dụ 3: Có bao nhiêu xâu nhị phân có độ dài n? Giải: Xâu nhị phân đó có dạng là: x1x2x3 xn,, trong đó xi là 0 hoặc 1. x1 có 2 cách chọn, x2 có 2 cách chọn, , xn có 2 cách chọn. Theo nguyên lý nhân ta có: 2*2*2 *2 = 2n (n lần số 2). Vậy có 2n xâu nhị phân có độ dài n. 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 11
  12. CÁC VÍ DỤ Ví dụ 4: Giá trị của m bằng bao nhiêu sau khi đoạn chương trình sau đây được thực hiện? m:=0; For i1:=1 to n1 do For i2:=1 to n2 do . . . For ik-1:=1 to nk-1 do For ik:=1 to nk do m:=m+1; GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 6/14/2021 12
  13. I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (6) Nguyên lý nhân: Nếu A1, A2, , Ak là các tập hợp hữu hạn, khi đó số phần tử của tập hợp tích Đề-Các (Descarts) của các tập hợp này bằng tích của số các phần tử của mọi tập hợp thành phần. Vậy theo quy tắc nhân ta có: |A1 x A2 x . . . x Ak| = |A1|* |A2|* *|Ak| 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 13
  14. I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (7) 3. Nguyên lý bù trừ: Nếu A1, A2 là các tập hợp hữu hạn, khi đó số phần tử của hợp của 2 tập hợp A1, A2 sẽ là Vấn￿đề￿đặt￿ra:￿￿mở￿rộng￿cho￿k￿tập￿hợp? 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 14
  15. I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (8) VÍ DỤ Trong một kỳ thi TN THPT, thống kê số học sinh đạt điểm 10 được như sau: tỉnh Đắk Lắk có 310 học sinh đạt điểm 10 môn Toán, 123 học sinh đạt điểm 10 môn Vật lý. Trong đó có 53 em vừa đạt điểm 10 môn Toán vừa đạt điểm 10 môn Vật Lý. Hỏi có bao nhiêu em đạt điểm 10? 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk
  16. II. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 1. Chỉnh hợp lặp 2. Chỉnh hợp không lặp 3. Hoán vị 4. Tổ hợp 5. Tổ hợp lặp 6. Hoán vị của tập hợp có các phần tử giống nhau 7. Phân bổ các đồ vật vào trong hộp 8. So sánh các cấu hình tổ hợp 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 16
  17. 2.1 Chỉnh hợp lặp Một cách sắp xếp có thứ tự k phần tử có thể lặp lại của một MỘT tập hợp có n phần tử được gọi SỐ là một chỉnh hợp lặp chập k từ BÀI tập n phần tử. TOÁN • Số chỉnh hợp lặp chặp k từ ĐẾM k CƠ tập n phần tử là n kí hiệu BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 17
  18. 2.1 Chỉnh hợp lặp VÍ DỤ: Sinh viên đọc và thảo luận các ví MỘT dụ trong sách (tr. 49) SỐ BÀI Thời gian : 10 phút. TOÁN ĐẾM CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 18
  19. 2.2 Chỉnh hợp không lặp CH: Nêu khái niệm chỉnh hợp không lặp? MỘT Đọc các ví dụ (tr. 50) SỐ BÀI TOÁN Thời gian : 10 phút. Công￿th c￿tính￿ch nh￿h p￿không￿l p￿ch p￿ ĐẾM ứ ỉ ợ ặ ậ k￿của￿n:￿ CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 19
  20. 2.3 HOÁN VỊ Hoán vị của n phần tử khác nhau là một cách sắp xếp có thứ tự n phần tử MỘT đó. SỐ Nhận xét: Hoán vị và chỉnh hợp không BÀI lặp có gì tương đồng không? TOÁN ĐẾM Hoán vị là chỉnh hợp không lặp có CƠ k=n. BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 20
  21. 2.3 HOÁN VỊ VÍ DỤ: Đọc sách (tr.51) MỘT Thời gian 5 phút SỐ BÀI TOÁN ĐẾM CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 21
  22. 2.4 Tổ hợp lặp Một tổ hợp lặp chập k của một tập MỘT hợp gồm n phần tử là một cách chọn SỐ không có thứ tự k phần tử có thể lặp BÀI lại của tập đã cho. TOÁN ĐẾM CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 22
  23. THẢO LUẬN 1. Đọc ví dụ 2.5.2 và 2.5.3 trong TL1 (Tr.54-55) MỘT SỐ Thời gian: 7 phút BÀI 2. Kết luận? TOÁN ĐẾM Số tổ hợp lặp chặp k từ tập n phần tử là: CƠ BẢN ChúChú ý:ý: kk cócó thểthể lớnlớn hơnhơn n.n. 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 23
  24. Bài toán 1 Có các loại giấy bạc 5.000đ, 10.000đ, 20.000đ, 50.000đ, 100.000đ, MỘT 200.000đ, 500.000đ. Có bao nhiêu SỐ BÀI cách chọn 5 tờ giấy bạc từ thùng đựng TOÁN tiền trên? biết rằng: ĐẾM 1. số tờ của mỗi loại không < 5. CƠ BẢN 2. số tờ giấy bạc 5.000đ và 10.000đ là 4 tờ, còn lại không ít hơn 5 tờ. 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 24
  25. Bài toán 2 MỘT Số nghiệm nguyên không âm của phương SỐ trình sau là bao nhiêu? BÀI x1 + x2 + x3 = 15 TOÁN ĐẾM CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 25
  26. Giải bài toán 1 1. LẤY 5 TỜ giấy bạc: tổ hợp lặp chập 5 từ 7 MỘT phần tử SỐ BÀI TOÁN 2. số tờ giấy bạc 5.000đ và 10.000đ là 4 tờ, ĐẾM còn lại không ít hơn 5 tờ. (ĐS: 460) CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 26
  27. Giải bài toán 2: Số nghiệm nguyên không âm của phương trình là số tổ hợp lặp chập 15 từ tập có 3 MỘT phần tử SỐ BÀI TOÁN ĐẾM Mở rộng bài toán 2: CƠ Sao cho x1>1, x2>2, x3>3 thì có bao nhiêu BẢN nghiệm nguyên thỏa mãn điều kiện trên? Bài tập SV làm ở nhà? 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 27
  28. 2.5 Tổ hợp không lặp Đọc các ví dụ 2.4.1, 2.4.2 (tr. 52) CH: Nêu khái niệm tổ hợp không lặp? MỘT SỐ BÀI Thời gian : 10 phút. TOÁN Công￿th c￿tính￿t ￿h p￿không￿l p￿ch p￿k￿ ĐẾM ứ ổ ợ ặ ậ của￿n:￿ CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 28
  29. 2.6 Hoán vị của một tập hợp có các phần tử giống nhau a) Trong bài toán đếm, một số phần MỘT tử có thể giống nhau. Tránh đếm SỐ hơn một lần. BÀI TOÁN vBài toán: Có thể nhận bao nhiêu xâu ĐẾM khác nhau bằng cách sắp xếp lại các CƠ chữ cái của từ SUCCESS. BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 29
  30. Mệnh đề 1 Số hoán vị của n phần tử trong đó MỘT có n1 phần tử như nhau thuộc loại 1, SỐ n2 phần tử như nhau thuộc loại 2, , BÀI và nk phần tử như nhau thuộc loại k, TOÁN bằng ĐẾM CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 30
  31. 2.7 Sự phân bố các đồ vật vào trong hộp Nhiệm vụ : Đọc sách TL1 trang 57 MỘT Ví dụ 2.7.1 SỐ Có bao nhiêu cách chia những xấp BÀI bài 5 quân cho mỗi một trong 4 người TOÁN ĐẾM chơi từ một cỗ bài chuẩn 52 quân? CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 31
  32. Giải ví dụ 2.7.1 SốSố cáchcách NgườiNgười đầuđầu tiêntiên cócó thểthể nhậnnhận đượcđược 55 quânquân bàibài làlà MỘT SỐ SốSố cáchcách NgườiNgười thứthứ haihai cócó thểthể đượcđược chiachia 55 BÀI quânquân bàibài bằngbằng TOÁN SốSố cáchcách NgườiNgười thứthứ baba cócó thểthể nhậnnhận đượcđược 55 ĐẾM quânquân bàibài bằngbằng CƠ VàVà sốsố cáchcách ngườingười thứthứ tưtư nhậnnhận đượcđược 55 BẢN quânquân bàibài bằngbằng theotheo NLNL nhânnhân tata có:có: 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 32
  33. Mệnh đề 2 Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau sao cho có ni MỘT vật được đặt vào trong hộp thứ i, với i = SỐ 1, 2, , k bằng BÀI TOÁN ĐẾM CƠ BẢN 6/14/2021 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 33