Luận văn Thạc sĩ Toán học: Tập hợp và cực trị tập hợp

Mục đích của luận văn là nhắc lại một số kiến thức cơ bản về bản số của tập hợp. Từ đó giải thích chi tiết các nguyên lý đếm, và các khái niệm cơ bản của tổ hợp. Nội dung này được kết thúc bằng bài toán đếm số ánh xạ, đơn ánh, toàn ánh, song ánh giữa các tập hữu hạn. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Tập hợp và cực trị tập hợp ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC CHU THỊ HẢI YẾNTẬP HỢP VÀ CỰC TRỊ TẬP 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 CHU THỊ HẢI YẾNTẬP HỢP VÀ CỰC TRỊ TẬP HỢP LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8460113 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. TRẦN NGUYÊN AN Thái Nguyên - 2018 3Mục lụcMở đầu 5Chương 1. Tập hợp, ánh xạ và tổ hợp 7 1.1 Tập hợp, ánh xạ . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Chương 2. Cực trị tập hợp 24 2.1 Một số định lý trong lý thuyết cực trị tập hợp . . . . . . . . . 24 2.2 Một số dạng toán cực trị tập hợp . . . . . . . . . . . . . . . . 28 2.2.1 Sử dụng ánh xạ . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Sử dụng nguyên lý tổ hợp . . . . . . . . . . . . . . . . 30 2.2.3 Đếm hai cách . . . . . . . . . . . . . . . . . . . . . . . 32 2.2.4 Quy nạp - Truy hồi . . . . . . . . . . . . . . . . . . . . 35 2.2.5 Phương pháp ma trận liên thuộc . . . . . . . . . . . . 37 2.2.6 Khoảng cách Hamming - chặn Plotkin . . . . . . . . . 40Kết luận 45Tài liệu tham khảo 46 4Lời cảm ơnTrong quá trình làm luận văn, tôi nhận được sự hướng dẫn và giúp đỡ tậntình của TS. Trần Nguyên An - Trường Đại học Sư phạm - Đại học TháiNguyên. Tôi xin được bày tỏ lòng biết ơn sâu sắc đến thầy. Tôi xin gửi lời cảm ơn chân thành đến quý thầy cô giảng dạy lớp Cao họckhóa Cao học Toán khóa 10Q (2016-2018) - Trường Đại học Khoa học - Đạihọc Thái Nguyên, đã truyền thụ đến cho tôi nhiều kiến thức và kinh nghiệmnghiên cứu khoa học. Xin trân trọng cảm ơn Sở Giáo dục và Đào tạo Hải Phòng, Ban Giámhiệu và các đồng nghiệp ở Trường THPT Phạm Ngũ Lão, Thủy Nguyên, HảiPhòng, đã tạo mọi điều kiện thuận lợi để tác giả học tập và nghiên cứu. Lời cuối cùng, tác giả muốn dành để tri ân bố mẹ và gia đình vì đã chiasẻ những khó khăn để tác giả hoàn thành công việc học tập của mình. 5Mở đầuKhái niệm tập hợp là nền tảng để xây dựng các khái niệm khác như số, hình,hàm số,. . . trong Toán học. Nghiên cứu lý thuyết tập hợp hiện đại do Cantorvà Dedekind khởi xướng vào thập niên 1870. Mục đích đầu tiên của luận vănlà nhắc lại một số kiến thức cơ bản về bản số của tập hợp. Từ đó giải thíchchi tiết các nguyên lý đếm, và các khái niệm cơ bản của tổ hợp. Nội dungnày được kết thúc bằng bài toán đếm số ánh xạ, đơn ánh, toàn ánh, songánh giữa các tập hữu hạn. Mục đích tiếp theo của luận văn là tìm hiểu lý thuyết cực trị tập hợp.Những bài toán trong lý thuyết cực trị tập hợp thường có dạng: cho một tập(hay một họ các tập) F thỏa mãn một số điều kiện cho trước, tìm max hoặcmin của lực lượng của F. Khi nào dấu đẳng thức xảy ra ? Luận văn quantâm đến một số bài toán. Cho F là một họ các tập con của một tập có nphần tử X. Để đơn giản ta thường xét X là tập [n] = {1, 2, 3, ..., n}.Bài toán 1. Giả sử bất kỳ hai phần tử nào của F cũng có giao khác rỗng. Hỏi giá trị lớn nhất có thể của |F|?Bài toán 2. Giả sử A * B với mọi phần tử A, B của F. Hỏi giá trị lớn nhất có thể của |F|? Các bài toán có thêm các điều kiện của F và các bài toán về cực trị tậphợp liên quan ở phổ thông cũng được tìm hiểu trong luận văn. Ngoài các phần Mở đầu, Kết luận, Tài liệu tham khảo, nội dung của luậnvăn được trình bày trong hai chương. 6• Chương 1. Tập hợp, ánh xạ và tổ hợp. Trong chương này chúng tôi sẽ trình bày về lực lượng của tập hợp, các quy tắc đếm, các quy tắc tổ hợp và giải quyết bài toán đếm ánh xạ giữa các tập hữu hạn. Nguyên lý Dirichlet và một số mở rộng cũng được trình bày trong chương này.• Chương 2. Cực trị tập hợp. Chương này trình bày các Định lý Erd¨os - Ko - Rado, Định lý Sperner, Bất đẳng thức Lubell - Yamamoto - Meshalkin. Cuối cùng luận văn trình bày một số dạng toán cực trị tập hợp ở phổ thông. Thái Nguyên, ngày 05 tháng 5 năm 2018 Tác giả Chu Thị Hải Yến 7Chương 1Tập hợp, ánh xạ và tổ hợp1.1 Tập hợp, ánh xạTập hợp là một khái niệm nguyên thuỷ (cơ bản) của toán học, không địnhnghĩa. Ta hiểu tập hợp là những vật, những đối tượng của toán học,. . . , đượcgom lại do một tính chất chung nào đó. Chẳng hạn, người ta nói Tập hợpcác sinh viên trong một lớp, tập hợp các lớp học trong một trường học,tập hợp N các số tự nhiên, tập hợp Z các số nguyên, tập hợp Q các sốhữu tỉ, tập hợp R các số thực,. . . Các tập hợp thường được ký hiệu bởi các chữ in hoa: X, Y, Z, . . .. Các vậttrong tập hợp gọi là các phần tử của tập hợp ấy và thường được ký hiệu bởicác chữ in thường: x, y, z, . . . , a, b, c, . . .. Tập hợp, phép toán trên tập hợp vàmột số tính chất là những kiến thức quen thuộc nên ta không nhắc lại ở đây. Để hiểu đầy đủ hơn về lý thuyết tổ hợp, ta nhắc lại khái niệm ánh xạ,đây cũng là kiến thức chuẩn bị cho chương sau.Định nghĩa 1.1.1. (i) Một ánh xạ f từ tập X đến tập Y là một quy tắccho tương ứng mỗi phần tử x ∈ X với một phần tử duy nhất y ∈ Y. Khi đóta viết f (x) ...