›
›

Bài giảng Toán rời rạc - Bài 2: Bài toán đếm - Nguyễn Văn Hiệu

pdf 37 trang cucquyet12 6520
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Bài 2: Bài toán đếm - Nguyễn Văn Hiệu", để 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:

  • pdfbai_giang_toan_roi_rac_bai_2_bai_toan_dem_nguyen_van_hieu.pdf

Nội dung text: Bài giảng Toán rời rạc - Bài 2: Bài toán đếm - Nguyễn Văn Hiệu

  1. BÀI 2 BÀI TOÁN ĐẾM Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn 1
  2. Nhắc lại Quy tắc nhân Quy tắc cộng Hoán vị Chỉnh hợp (lặp) Tổ hợp (không lặp) Tổ hợp lặp ??? 2
  3. Nôi dung 2.1. Ví dụ đếm cơ bản 2.2. Nguyên lý bù trừ 2.3. Hoán vị lặp 2.4. Tổ hợp lặp 2.5. Bài tập
  4. 2.1. Ví dụ đếm cơ bản Ví dụ 2.1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
  5. 2.1. Ví dụ đếm cơ bản Ví dụ 2.1 (tổng quát) A B Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
  6. 2.1. Ví dụ đếm cơ bản Ví dụ 2.1 (tổng quát) A,B n! n-1! n-1! AB BA Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6
  7. 2.1. Ví dụ đếm cơ bản Ví dụ 2.2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
  8. 2.1. Ví dụ đếm cơ bản Ví dụ 2.3 (2 x 2) (2 x 3) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
  9. 2.1. Ví dụ đếm cơ bản Ví dụ 2.3 (tổng quát) Sang phải - 1 Số đoạn sang phải: n Đi xuống - 0 Số đoạn đi xuống: m n Dãy nhị phân độ dài n+m và có đúng m bit 0 Số tập con của m phần tử của tập n+m phần tử C m m nm Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
  10. 2.2.Nguyên lý bù trừ • A1 và A2 là hai tập hưu hạn, A1 A2 ≠  N(A1 A2 ) = N(A1) + N(A2) – N(A1 A2) A A A A2 1 2 1 N = N(A ) + N(A ) N(A ) + N(A ) – N(A  A ) 1 1 2 1 2 1 2 • Tổng quát: khi Ai Aj ≠  mọi i, j n-1 N(A1 An) = N1 - N2 + +(-1) Nn • Nk là tổng phần tử của tất cả các giao của k tập lấy từ n tập.  N1 = N(A1) + + N(Am) ,  .  Nm= N(A1 A2   Am). Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
  11. 2.2.Nguyên lý bù trừ • Nguyên lý bù trừ – Ak tính chất nào đó cho trên X – tổng số phần tử của X không thỏa mản bất cứ tính chất Ak N(X) - N(A A  A ) 1 2 n • Ni - là tổng số phần tử của X thỏa mản i tính chất. Tổng số phần tử thỏa mản ít nhất một tính chất Ak nào đó Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
  12. 2.2.Nguyên lý bù trừ N(A1  A2  A3) = ? 1 A1 A1 1 1 1 2 2 0 3 1 2 A2 A3 A2 A3 1 1 1 1 A 1 N1 1 N1 - N2 1 1 b) 1 A2 1 A3 1 1 N1 - N2 + N3 c) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12
  13. 2.2.Nguyên lý bù trừ • Ví dụ 2.2.1 Hỏi tập X={1,2, 50} có bao nhiêu số không chia hết cho bất các số 2, 3, 4 ? Ai = { x € X: x % i ==0 } i=2,3,4. A2A3A4 là tập chia hết ít nhất 1 trong 3 số N (X) - N(A2A3A4) = N- (N1 - N2 + N3 ) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13
  14. 2.2.Nguyên lý bù trừ Ta có: • N = 50 số. • N1 = N(A2) + N(A3) + N(A4) = [50/2] + [50/3] + [50/4] = 25 + 16 + 12 =53. • N2 = N(A2  A3) + N(A3  A4) + N(A2  A4) = [50/6] + [50/12] + [50/4] = 8 + 4 + 12 = 24. • N3 = N(A2  A3  A4) = [50/12] = 4. • Suy ra 50 – ( 53 – 24 + 4 ) = 17 số. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14
  15. 2.2.Nguyên lý bù trừ Ví dụ 2.2.2 Có bao nhiêu xâu nhị phân độ dài 10 hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11? HD: 256 0 0 + 1 1 265 - 0 0 1 1 64 448 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
  16. 2.2.Nguyên lý bù trừ • Ví dụ 2.2.3 (bài toán bỏ thư) Có n lá thư và n phong bì ghi sẳn địa chỉ. Bỏ ngẫu nhiên các lá thư vào phong bì. Hỏi xác suất để không một lá thư bỏ đúng địa chỉ. – HD: X – là tập hợp tất cả các cách bỏ thư. A k – là tính chất lá thư thứ k bỏ đúng địa chỉ. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
  17. 2.2.Nguyên lý bù trừ n-1 • N = N - (N1 - N2 + +(-1) Nn ) • N = n! • Nk - là số tất cả các cách bỏ thư sao cho có k lá thư đúng địa chỉ. k Nk = C n (n-k)! = n!/k! n-1 = n! - (n!/1! – n!/2! + +(-1) n!/n! ) n-1 = n!(1 - 1/1! +1/2! + +(-1) /n! ) • Xác suất cần tìm: 1 - 1/1! +1/2! + +(-1)n-1/n! Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17
  18. 2.2.Nguyên lý bù trừ . Ví dụ 2.2.4 . Ví dụ 2.2.5 . Ví dụ 2.2.6
  19. 2.3. Hoán vị lặp . Bài toán: Số hoán vị của n pt: – có n1 phần tử như nhau thuộc loại 1, – có n2 phần tử như nhau thuộc loại 2, – . , – có nk phần tử như nhau thuộc lại k. . ĐN: Một cách sắp xếp n pt trên gọi là một hoán vi lặp. . Tổng số hoán vị lặp của n phần là: n! CnnCnnn(,)(1 1 ,) ( 2   Cnnn 1 2 nnkk 1 ,) n12! n !   nk ! Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19
  20. 2.3. Hoán vị lặp •Ví dụ 2.3.1. SUCCESS • 3 S • 2 C • 1 U SUCCESS. • 1 E • C(7,3)- chọn 3 chổ cho kí tự S, còn lại 4 chổ • C(4,2) – chọn 2 chổ cho kí tự C, còn 2 chổ • C(2,1)- chọn 1 chổ cho kí tự U, còn lại 1 chổ 7! • C(1,1)- chọn 1 chổ cho kí tự S 7! CCCC(7,3) (4,2)  (2,1)  (1,1) 420 3! 2!1!1!   Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20
  21. 2.3. Hoán vị lặp Ví dụ 2.3.2. MISSISSIPPI 11! CCCC(11,1) (10,4)  (6,4)  (2,2) 1! 4! 4! 2! Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21
  22. 2.4. Phân bố đồ vật vào túi . Ví dụ 2.3.3. Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong 4 người chơi từ một cỗ bài chuẩn 52 quân? . Tổng quát: 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 vật được đặt vào trong hộp thứ i, với i = 1, 2, , k
  23. 2.4. Tổ hợp lặp Cho n loại, mỗi loại có không ít hơn k phần tử: Một tổ hợp lặp chập k từ n loại – một bộ không có thứ tự k phần tử lấy từ n loại (các phần tử có thể lặp, k >n ) Số tổ hợp lặp chập k của n loại: C( n k 1, n 1) C ( n k 1, k ) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 23
  24. 2.4. Tổ hợp lặp Ví dụ 2.4.1. Đếm cách mua mâm ngũ quả từ 3 loại: Cam, Quýt, Xoài. CC(3 1 5,5) (3 1 5,3 1) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 24
  25. 2. Ví 4 dụ . Tổ hợp lặp • 10000đ 2.4.2. 2.4.2. • 20000đ Nguyễn 2012, DiscreteVăn MathematicsHiệu, • 50000đ • 100000đ • 200000đ • 500000đ • 5000đ 25
  26. 2. 4 • 10.000đ . Tổ hợp lặp • 20.000đ Nguyễn 2012, DiscreteVăn MathematicsHiệu, • 50.000đ • 100.000đ • 200.000đ • 500.000đ • 5000đ 26
  27. 2. 3 • 10.000đ . Tổ hợp lặp • 20.000đ Nguyễn 2012, DiscreteVăn MathematicsHiệu, C(7+5−1,5) • 50.000đ =462. • 100.000đ • 200.000đ • 500.000đ • 5000đ 27
  28. 2.4. Tổ hợp lặp Ví dụ 2.4.3 Phương trình x1 + x2 + x3 = 15 với x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0. Loai 1 Loai 2 Loại 3 x1≤15 x2≤15 x3≤15 C(3+15−1, 15) = C(3+15−1, 2) = 136 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 28
  29. 2.4. Tổ hợp lặp Ví dụ 2.4.4- 2.3.6 Ví dụ 2.4.4: x1 + x2 + x3 = 12 với x1 ≥ 1 , x2 ≥ -2 , x3 ≥3 . Ví dụ 2.4.5: x1 + x2 + x3 ≤ 12 với x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 . Ví dụ 2.4.6: x1 + x2 + x3 = 11 với 3 ≥ x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 . Nguyễn Văn Hiệu, 2012, Discrete Mathematics 29
  30. 2.3. Tổ hợp lặp • Ví dụ 2.4.4: Đặt: `x1 = x1 – 1 ≥ 0, `x2 = x2 + 2 ≥ 0 , `x3 = x3 -3 ≥ 0, Bài toán gốc tương đương: `x1 + `x2 + `x3 = 10 với `x1 ≥ 0 , `x2 ≥ 0 , `x3 ≥0 . Kết quả: C(3+10−1, 10) = C(3+10−1, 2) = 66. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 30
  31. 2.4. Tổ hợp lặp Giải Ví dụ 2.4.5: • Đặt ẩn phụ x4 ≥ 0 , • Bài toán gốc tương đương: x1 + x2 + x3 + x4 = 12 với x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 , x4 ≥ 0 , . • Kết quả: C(12+4-1,12) = C(12+4-1,3)=455 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 31
  32. 2.4. Tổ hợp lặp Giải Ví dụ 2.4.6: x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 3 ≥ x1 ≥ 0,x2 ≥ 0,x3 ≥ 0 x1 ≥ 4 , x2 ≥ 0 , x3 ≥ 0 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 32
  33. 2.5. Bài tập • Bài tập 2.5.1: Ngôn ngữ C chuẩn qui định đặt tên biến không quá 8 ký tự. Các ký tự trong tên biến chỉ được phép là các chữ cai (từ A đến Z) hoặc là các chữ số (từ 0 đến 9) và phải bắt đầu bằng chữ cái. Hỏi có thể định nghĩa bao nhiêu biến khác nhau Nguyễn Văn Hiệu, 2012, Discrete Mathematics 34
  34. 2.5. Bài tập • Bài tập 2.5.2: Nguyễn Văn Hiệu, 2012, Discrete Mathematics 35
  35. 2.5. Bài tập • Bài tập 2.5.3: Nguyễn Văn Hiệu, 2012, Discrete Mathematics 36
  36. THAT’S ALL; THANK YOU What NEXT? BÀI TOÁN ĐẾM NÂNG CAO