tailieunhanh - Luận văn Thạc sĩ Toán học: Một số vấn đề về bài toán đếm trong tổ hợp

Luận văn được viết dựa chủ yếu trên tài liệu chính để tham khảo. Mục đích chính của luận văn là trình bày, khẳng định lại các kết quả đã có trong toán học tổ hợp bằng lí luận đếm từ cơ bản đến nâng cao, phục vụ cho công việc giảng dạy môn toán tổ hợp ở bậc THPT. | ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC -------------- ------------- NGUYỄN THỊ BÍCH PHƯỢNG MỘT SỐ VẤN ĐỀ VỀ BÀI TOÁN ĐẾM TRONG TỔ HỢP LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC -------------- ------------- NGUYỄN THỊ BÍCH PHƯỢNG MỘT SỐ VẤN ĐỀ VỀ BÀI TOÁN ĐẾM TRONG TỔ HỢP Chuyên ngành Phương pháp Toán sơ cấp Mã số 8460113 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Hoàng Lê Trường THÁI NGUYÊN - 2018 i Mục lục MỞ ĐẦU ii Chương 1. Bài toán đếm 1 Định lí nhị thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Lựa chọn với sự lặp lại . . . . . . . . . . . . . . . . . . . . . . . . . 5 Phân hoạch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Đếm lặp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Nguyên tắc trung bình . . . . . . . . . . . . . . . . . . . . . . . . . 12 Nguyên tắc bao hàm loại trừ . . . . . . . . . . . . . . . . . . . . . . 15 Chương 2. Đếm nâng cao 19 Chặn cỡ của các tập giao . . . . . . . . . . . . . . . . . . . . . . . . 19 Đồ thị không có chu trình độ dài 4 . . . . . . . . . . . . . . . . . . 23 Vấn đề của Zarankiewicz . . . . . . . . . . . . . . . . . . . . . . . . 32 Tính trù mật của ma trận nhị phân . . . . . . . . . . . . . . . . . 36 KẾT LUẬN 39 TÀI LIỆU THAM KHẢO 40 ii MỞ ĐẦU Toán học tổ hợp là một trong những nội dung quan trọng trong giáo dục phổ thông. Học sinh thường gặp khó khăn khi giải quyết các bài toán này. Vì vậy tìm hiểu sâu thêm về toán tổ hợp là rất cần thiết. Trong toán học tổ hợp bài toán đếm là một trong những bài toán cơ bản. Phép đếm là một công cụ đắc lực trong toán học và là một điều rất tự nhiên trong cuộc sống con người. Nhiều kết quả đã biết trong toán học tổ hợp đều có thể được giải thích chỉ bằng phép đếm. Luận văn được viết dựa chủ yếu trên tài liệu chính để tham khảo là 4 . Mục đích chính của luận văn là trình bày khẳng định lại các kết quả đã có trong toán học tổ