Xem mẫu
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
PHẠM THỊ HIÊN
MỘT SỐ BÀI TOÁN TỔ HỢP ĐẾM
LUẬN VĂN THẠC SĨ KHOA HỌC
MỤC LỤC
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
PHẠM THỊ HIÊN
MỘT SỐ BÀI TOÁN TỔ HỢP ĐẾM
Chuyên ngành: Phương pháp toán sơ cấp
Mã số: 60460113
LUẬN VĂN THẠC SĨ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. Lê Anh Vinh
Hà Nội – Năm 2014
MỤC LỤC....................................................................................3 MỞ ĐẦU.......................................................................................1 CHƯƠNG 1 CƠ SỞ LÍ THUYẾT VỀ TỔ HỢP...................2 1.1 Nhắc lại về tập hợp ..........................................................................2 1.2 Quy tắc cộng và quy tắc nhân............................................................3 1.3 Giai thừa và hoán vị ...........................................................................5 1.4 Chỉnh hợp, tổ hợp .............................................................................6 1.5 Chỉnh hợp lặp, hoán vị lặp và tổ hợp lặp........................................7 1.5.1 Chỉnh hợp lặp.............................................................................7 1.5.2 Hoán vị lặp ..................................................................................7 1.5.3 Tổ hợp lặp ..................................................................................8 CHƯƠNG 2 MỘT SỐ BÀI TOÁN TỔ HỢP CƠ BẢN......9 2.1 Một số bài toán đếm không lặp.......................................................10 2.1.1 Bài toán lập số..........................................................................10 2.1.2 Bài toán chọn vật, chọn người, sắp xếp.................................18 2.1.3 Bài toán tương tự.......................................................................29
2.2 Một số bài toán đếm có lặp...........................................................31 2.2.1 Bài toán lập số...........................................................................31 2.2.2 Bài toán đếm sử dụng tổ hợp lặp.............................................36 2.2.3 Bài toán đếm sử dụng chỉnh hợp lặp.......................................40 2.2.4 Bài toán đếm sử dụng hoán vị lặp............................................41 2.2.5 Bài toán phân bố các đồ vật vào trong hộp..............................42 2.2.6 Bài toán tương tự.......................................................................43
CHƯƠNG 3 MỘT SỐ BÀI TOÁN TỔ HỢP SỬ DỤNG PHÉP ĐẾM NÂNG CAO..........................................................45
3.1 Một số bài toán sử dụng nguyên lý bù trừ......................................46 3.1.1 Nguyên lý bù trừ.......................................................................46 3.1.2 Các bài toán giải bằng phương pháp bù trừ............................47 3.2 Một số bài toán giải bằng phương pháp song ánh.........................54 3.2.1 Phương pháp song ánh..............................................................54 3.2.2 Các bài toán tổ hợp giải bằng phương pháp song ánh............55 3.3 Một số bài toán giải bằng phương pháp hàm sinh.........................56 3.3.1 Bài toán chọn các phần tử riêng biệt........................................57 3.3.2 Bài toán chọn các phần tử có lặp..............................................58 3.4 Một số bài toán giải bằng phương pháp hệ thức truy hồi............62 3.4.1 Khái niệm mở đầu và mô hình hóa bằng hệ thức truy hồi.....62 3.4.2 Các bài toán tổ hợp giải bằng hệ thức truy hồi.......................62 3.4.3 Các bài toán tương tự................................................................65
3.5 Bài toán giải bằng nguyên lí cực hạn khả năng xảy ra nhiều nhất, ít nhất.............................................................................................66 3.6 Bài toán giải bằng phương pháp sắp xếp thứ tự...........................66
3.7 Bài toán giải bằng phương pháp liệt kê các trường hợp..............68 KẾT LUẬN.................................................................................71 TÀI LIỆU THAM KHẢO.........................................................72
...
- tailieumienphi.vn
nguon tai.lieu . vn