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