Bài giảng Toán rời rạc: Bài 2 - TS. Nguyễn Văn Hiệu

Bài 2 "Bài toán đếm" thuộc bài giảng Toán rời rạc cung cấp cho các bạn những ví dụ đếm cơ bản, nguyên lý bù trừ, hoán vị lặp, tổ hợp lặp. Với các bạn chuyên ngành Toán học thì đây là tài liệu tham khảo hữu ích.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Bài 2 - TS. Nguyễn Văn Hiệu BÀI 2BÀI TOÁN ĐẾM Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn 1 Nhắc lạiQuy tắc nhânQuy tắc cộngHoán vịChỉnh hợp (lặp)Tổ hợp (không lặp)Tổ hợp lặp ??? 2 Nôi dung2.1. Ví dụ đếm cơ bản2.2. Nguyên lý bù trừ2.3. Hoán vị lặp2.4. Tổ hợp lặp2.5. Bài tập2.1. Ví dụ đếm cơ bản Ví dụ 2.1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 42.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 52.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 62.1. Ví dụ đếm cơ bản Ví dụ 2.2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 72.1. Ví dụ đếm cơ bản Ví dụ 2.3 < kiến tha mồi> (2 x 2) (2 x 3) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 82.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 nDãy nhị phân độdài n+m và cóđúng m bit 0Số tập con củam phần tử củatập n+m phầntử m m C nm Nguyễn Văn Hiệu, 2012, Discrete Mathematics 92.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 ) A1 A2 A1 A2 N1= N(A1 ) + N(A2) N(A1 ) + N(A2) – N(A1  A2 )• Tổng quát: khi Ai Aj ≠  mọi i, j N(A1 …An) = N1 - N2 + … +(-1)n-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 102.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(A1 A2 …An) • 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 112.2.Nguyên lý bù trừ N(A1  A2  A3) = ? A1 A1 1 1 2 1 1 2 0 3A2 2 A3 A2 1 A3 1 1 1 1 N1 A1 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 122.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 132.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 142.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 ...