Toán học - Bài 2: Bài toán đếm

BÀI 2 BÀI TOÁN ĐẾM 1 Giáo viên: TS. Nguyễn Văn Hiệu Email: [email protected] 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 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 2.1. Ví dụ đếm cơ bản Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4 Ví dụ 2.1 2.1. Ví dụ đếm cơ bản Ví dụ 2.1 (tổng quát) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5 A B 2.1. Ví dụ đếm cơ bản Ví dụ 2.1 (tổng quát) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6 A,B n! n-1! n-1! -- -- AB BA 2.1. Ví dụ đếm cơ bản Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7 Ví dụ 2.2 2.1. Ví dụ đếm cơ bản Ví dụ 2.3 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8 (2 x 2) (2 x 3) 2.1. Ví dụ đếm cơ bản Ví dụ 2.3 (tổng quát) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9 Sang phải - 1 Đi xuống - 0 Số đoạn sang phải: n Số đoạn đi xuống: m 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ử m n mC m n 2.2.Nguyên lý bù trừ • A1và A2 là hai tập hưu hạn, A1 A2 ≠  • Tổng quát: khi Ai Aj ≠  mọi i, j • 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. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10 N(A1 A2 ) = N(A1) + N(A2) – N(A1 A2) N(A1An) = N1 - N2 + +(-1) n-1 Nn  N1 = N(A1) + + N(Am) ,  .  Nm= N(A1 A2   Am). A1 A2 N1= N(A1 ) + N(A2) A1 A2 N(A1 ) + N(A2) – N(A1 A2 ) 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 • Ni - là tổng số phần tử của X thỏa mản i tính chất. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11 N(X) - N(A1A2An) Tổng số phần tử thỏa mản ít nhất một tính chất Ak nào đó A1 A3 A2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12 3 2 2 1 1 1 A1 A3 A2 0 1 1 1 1 1 A1 A3 A2 1 1 1 1 1 1 N1 N1 - N2 + N3 2 1 1 N1 - N2 b) c) N(A1  A2  A3) = ? 2.2.Nguyên lý bù trừ 2.2.Nguyên lý bù trừ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13 • 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 ) 2.2.Nguyên lý bù trừ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14 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ố. 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: Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15 0 0 1 1 256 + 265 - 64 ------ 448 0 0 1 1 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 2.2.Nguyên lý bù trừ • • N = n! • Nk - là số tất cả các cách bỏ thư sao cho có k lá thư đúng địa chỉ. Nk = C k n (n-k)! = n!/k! = n! - (n!/1! – n!/2! + +(-1)n-1 n!/n! ) = n!(1 - 1/1! +1/2! + +(-1)n-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 = N - (N1 - N2 + +(-1) n-1 Nn ) N N 2.2.Nguyên lý bù trừ  Ví dụ 2.2.4  Ví dụ 2.2.5  Ví dụ 2.2.6 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à: Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19 1 1 2 1 2 1 1 2 ! ( , ) ( , ) ... ( ... , ) ! ! ... ! k k k n C n n C n n n C n n n n n n n n             2.3. Hoán vị lặp SUCCESS. • 3 S • 2 C • 1 U • 1 E 7! • 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ổ • C(1,1)- chọn 1 chổ cho kí tự S Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20 •Ví dụ 2.3.1. SUCCESS 7! (7,3) (4,2) (2,1) (1,1) 420 3! 2!1!1! C C C C        2.3. Hoán vị lặp Ví dụ 2.3.2. MISSISSIPPI Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21 11! (11,1) (10,4) (6,4) (2,2) 1! 4! 4! 2! C C C C       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 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: Nguyễn Văn Hiệu, 2012, Discrete Mathematics 23 ( 1, 1) ( 1, )C n k n C n k k      2.4. Tổ hợp lặp Đếm cách mua mâm ngũ quả từ 3 loại: Cam, Quýt, Xoài. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 24 (3 1 5,5) (3 1 5,3 1)     C C Ví dụ 2.4.1. 2.4. Tổ hợp lặp • 1 0 0 0 0 đ • 2 0 0 0 0 đ • 5 0 0 0 0 đ • 1 0 0 0 0 0 đ • 2 0 0 0 0 0 đ • 5 0 0 0 0 0 đ • 5 0 0 0 đ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 25 Ví dụ 2.4.2. 2.4. Tổ hợp lặp • 1 0 .0 0 0 đ • 2 0 .0 0 0 đ • 5 0 .0 0 0 đ • 1 0 0 .0 0 0 đ • 2 0 0 .0 0 0 đ • 5 0 0 .0 0 0 đ • 5 0 0 0 đ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 26 2.3. Tổ hợp lặp • 1 0 .0 0 0 đ • 2 0 .0 0 0 đ • 5 0 .0 0 0 đ • 1 0 0 .0 0 0 đ • 2 0 0 .0 0 0 đ • 5 0 0 .0 0 0 đ • 5 0 0 0 đ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 27 C(7+5−1,5) = 462. 2.4. Tổ hợp lặp Phương trình x1 + x2 + x3 = 15 với x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 28 Loai 1 x1≤15 Loai 2 x2≤15 Loại 3 x3≤15 C(3+15−1, 15) = C(3+15−1, 2) = 136 Ví dụ 2.4.3 2.4. Tổ hợp lặp 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 Ví dụ 2.4.4- 2.3.6 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 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 2.4. Tổ hợp lặp 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 Giải Ví dụ 2.4.6: • 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 2.5. Bài tập • Bài tập 2.5.2: Nguyễn Văn Hiệu, 2012, Discrete Mathematics 35 2.5. Bài tập • Bài tập 2.5.3: Nguyễn Văn Hiệu, 2012, Discrete Mathematics 36 2.5. Bài tập THAT’S ALL; THANK YOU What NEXT? BÀI TOÁN ĐẾM NÂNG CAO