ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TÔ THỊ LAN MỘT SỐ PHƯƠNG PHÁP TÍNH TỐN VÀ ƯỚC LƯỢNG LỰC LƯỢNG CỦA CÁC TẬP HỮU HẠN SINH BỞI HÀM SỐ LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TƠ THỊ LAN MỘT SỐ PHƯƠNG PHÁP TÍNH TỐN VÀ ƯỚC LƯỢNG LỰC LƯỢNG CỦA CÁC TẬP HỮU HẠN SINH BỞI HÀM SỐ Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TSKH Nguyễn Văn Mậu THÁI NGUYÊN - 2019 i LỜI CẢM ƠN Luận văn hoàn thành trường Đại học Khoa học - Đại học Thái Nguyên Tác giả xin bày tỏ lòng biết ơn sâu sắc GS.TSKH Nguyễn Văn Mậu (Trường ĐH Khoa học Tự nhiên, ĐHQGHN), thầy trực tiếp hướng dẫn tận tình động viên tác giả suốt thời gian nghiên cứu vừa qua Xin chân thành cảm ơn tới quý thầy, cô giáo trực tiếp giảng dạy lớp cao học Toán K11, bạn học viên, bạn đồng nghiệp tạo điều kiện thuận lợi, động viên giúp đỡ tác giả trình học tập nghiên cứu trường Tác giả xin bày tỏ lòng biết ơn sâu sắc tới gia đình người thân ln khuyến khích động viên tác giả suốt q trình học cao học viết luận văn Mặc dù có nhiều cố gắng luận văn khó tránh khỏi thiếu sót hạn chế Tác giả mong nhận ý kiến đóng góp thầy bạn đọc để luận văn hồn thiện Xin chân thành cảm ơn! Thái Nguyên, tháng 10 năm 2019 Tác giả Tô Thị Lan ii Mục lục MỞ ĐẦU Chương MỘT SỐ TÍNH CHẤT CỦA TẬP HỢP HỮU HẠN 1.1 Một số khái niệm liên quan đến tập hợp 1.1.1 Cơng thức tính lực lượng tập hợp 1.1.2 Một số nguyên lý phép đếm 1.2 Các quy tắc đếm 1.2.1 Quy tắc cộng 1.2.2 Quy tắc nhân 1.3 Hoán vị 1.4 Chỉnh hợp 1.5 Tổ hợp 1.6 Khai triển lũy thừa nhị thức Chương ĐẲNG THỨC, BẤT ĐẲNG THỨC VÀ TOÁN CỰC TRỊ TRONG TỔ HỢP 2.1 Một số đẳng thức tổ hợp 2.2 Một số bất đẳng thức thông dụng 2.3 Các toán cực trị rời rạc liên quan 2 5 6 7 MỘT SỐ BÀI Chương MỘT SỐ PHƯƠNG PHÁP XÁC ĐỊNH LỰC LƯỢNG CỦA TẬP HỮU HẠN 3.1 Một số phương pháp đếm số học 3.1.1 Nguyên lý bao hàm loại trừ 3.1.2 Phương pháp đếm số lần xuất phần tử tập hợp 3.1.3 Đếm theo phương pháp thiết lập hệ thức truy hồi 3.2 Một số tốn đếm hình học tổ hợp 9 11 13 30 30 30 38 42 49 iii 3.3 Một số tính tốn khác tập rời rạc 58 KẾT LUẬN 69 TÀI LIỆU THAM KHẢO 70 Mở đầu Toán học tổ hợp nghiên cứu từ sớm Hiện giáo dục phổ thơng, tốn học tổ hợp nội dung quan trọng, thường xuyên xuất đề thi THPT Quốc Gia đề thi chọn học sinh giỏi cấp Trong tốn tổ hợp có lớp toán đếm Bài toán đếm phong phú kể dạng phát biểu đến cách giải Độ khó toán đếm trải rộng - từ tốn dễ với số liệu cụ thể, kiểm chứng trực giác đến toán khó hơn, với liệu đầu vào chữ mà kết biểu diễn cơng thức tốn học Có cơng thức tìm qua vài suy luận đơn giản có cơng thức mà việc tìm thấy chúng phải kéo dài lâu Bài toán đếm giúp học sinh phát huy tốt khả tư sáng tạo Nhằm đáp ứng nhu cầu bồi dưỡng học sinh giỏi phát triển tư cho học sinh chọn đề tài “Một số phương pháp tính tốn ước lượng lực lượng tập hữu hạn sinh hàm số ” Luận văn tổng hợp số dạng tập đặc trưng góp phần nâng cao tư tổ hợp học sinh giúp học sinh lựa chọn kiến thức q trình giải tốn tổ hợp Cấu trúc luận văn gồm chương Chương Một số tính chất tập hợp hữu hạn Chương Đẳng thức, bất đẳng thức số toán cực trị tổ hợp Chương Một số phương pháp xác định lực lượng tập hữu hạn Chương MỘT SỐ TÍNH CHẤT CỦA TẬP HỢP HỮU HẠN Trong chương này, tác giả nhắc lại khái niệm liên quan đến tập hợp, phép tốn tập hợp, cơng thức liên quan đến hoán vị chỉnh hợp tổ hợp, cơng thức tính lực lượng tập hợp số nguyên lý đếm nâng cao nhằm chuẩn bị sở cho việc giải toán chương chương Các kết chương trích dẫn từ tài liệu tham khảo [3] 1.1 Một số khái niệm liên quan đến tập hợp Định nghĩa 1.1 Tập B gọi tập tập A phần tử thuộc tập A Ký hiệu B ⊆ A Định nghĩa 1.2 Khi B tập tập A B = A, B gọi tập thực tập A Ký hiệu B ⊂ A Định nghĩa 1.3 Tập hợp không chứa phần tử gọi tập hợp rỗng Ký hiệu ∅ Định nghĩa 1.4 Cho tập A, số phần tử tập A gọi lực lượng tập A, ký hiệu |A| Định nghĩa 1.5 Cho tập hợp A, B , tập gồm phần tử thuộc tập A thuộc tập B gọi hợp tập A tập B Ký hiệu A ∪ B A ∨ B Định nghĩa 1.6 Cho tập hợp A, B , tập hợp gồm phần tử thuộc đồng thời tập A tập B gọi giao tập A tập B Kí hiệu A ∩ B A ∧ B Định nghĩa 1.7 Tập hợp gồm phần tử thuộc A không thuộc B gọi hiệu tập A tập B Ký hiệu A\B Định nghĩa 1.8 Giả sử tập B tập tập A, tập gồm tất phần tử thuộc A, không thuộc B gọi phần bù tập B tập A ký hiệu CA (B) 1.1.1 Cơng thức tính lực lượng tập hợp • Cho hai tập A, B ta có |A ∪ B| = |A| + |B| − |A ∩ B| • Cho ba tập A, B, C ta có |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C| • Tổng quát Cho A1 , A2 , Am tập hữu hạn ta đặt m |A1 | N1 = i=1 |Ai ∩ Ai | N2 = 1≤i