zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:37

Báo xấu

166
lượt xem 20
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn 1
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 Ví dụ 2.1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
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
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
2.1. Ví dụ đếm cơ bản Ví dụ 2.2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
2.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 8
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ử m m C nm Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
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 ) 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 10
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(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 11
2.2.Nguyên lý bù trừ N(A1  A2  A3) = ? A1 A1 1 1 2 1 1 2 0 3 A2 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 12
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
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
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
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 - (N1 - N2 + … +(-1)n-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ỉ. Nk = Ckn (n-k)! = n!/k! N = 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
2.2.Nguyên lý bù trừ  Ví dụ 2.2.4  Ví dụ 2.2.5< Số người tham gia tất cả khóa học>  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à: n! C (n, n1 )  C (n  n1 , n2 )  ...  C (n  n1  n2  ...  nk 1 , nk )  n1 ! n2 ! ...  nk ! Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19
2.3. Hoán vị lặp •Ví dụ 2.3.1. SUCCESS • 3S • 2C • 1U SUCCESS. • 1E • 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! C (7,3)  C (4, 2)  C (2,1)  C (1,1)   420 3! 2!1!1! Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.