Đề tài nghiên cứu trình bày một số lý thuyết cơ bản về nguyên lý quy nạp và hai quy tắc đếm cơ bản, hoán vị, chỉnh hợp, tổ hợp, nhị thức Newton và đồ thị cây. Tác giả đã nhắc lại được các kiến thức cơ bản về tổ hợp trong chương trình toán trung học phổ thông. Đồng thời nêu được một số khái niệm về tổ hợp suy rộng, đó là: Hoán vị lặp, chỉnh hợp lặp, tổ hợp lặp. Trình bày bốn nguyên lý cơ bản trong tổ hợp và các ví dụ áp dụng các nguyên lý đó. | ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - NGUYỄN NGỌC MAI MỘT VÀI NGUYÊN LÝ VÀ BÀI TOÁN TỔ HỢP LUẬN VĂN THẠC SỸ TOÁN HỌC HÀ NỘI- 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - NGUYỄN NGỌC MAI MỘT VÀI NGUYÊN LÝ VÀ BÀI TOÁN TỔ HỢP Chuyên ngành PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số 60460113 LUẬN VĂN THẠC SỸ TOÁN HỌC Người hướng dẫn khoa học PGS. TS. ĐÀM VĂN NHỈ HÀ NỘI- 2014 Mục lục Mở đầu 3 1 Kiến thức chuẩn bị 5 Nguyên lý quy nạp . . . . . . . . . . . . . . . . . . . . 5 Hai quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . 8 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . 11 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . 14 Ứng dụng trong số học . . . . . . . . . . . . . . 16 Nhị thức Newton . . . . . . . . . . . . . . . . . . . . . 18 Đồ thị cây . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 Một vài nguyên lý trong tổ hợp 26 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . 26 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . 26 Nguyên lý Dirichlet áp dụng trong hình học tổ hợp 31 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . 34 Nguyên lý cực hạn . . . . . . . . . . . . . . . . . . . . . 42 Nguyên lý bất biến . . . . . . . . . . . . . . . . . . . . 51 3 Một vài đồng nhất thức trong tổ hợp 60 Xây dựng đồng nhất thức qua hệ phương trình . . . . . 60 Xây dựng đồng nhất thức qua số phức . . . . . . . . . 66 Xây dựng đồng nhất thức qua hàm sinh . . . . . . . . . 69 Khái niệm hàm sinh . . . . . . . . . . . . . . . . 70 Một số đồng nhất thức liên quan đến hàm sinh . 70 Ứng dụng của hàm sinh . . . . . . . . . . . . . . 71 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . 78 1 Lời cảm ơn Tôi .
