Tóm tắt luận văn Thạc sĩ Khoa học: Số các ánh xạ không phân rã được trên tập hữu hạn

BỘ GIÁO DỤC VÀ ĐÀO TẠO<br /> ĐẠI HỌC ĐÀ NẴNG<br /> <br /> NGUYỄN VĂN TIẾN<br /> <br /> SỐ CÁC ÁNH XẠ KHÔNG PHÂN RÃ<br /> ĐƯỢC TRÊN TẬP HỮU HẠN<br /> <br /> Chuyên ngành: Phương pháp Toán sơ cấp<br /> Mã số: 60.46.40<br /> <br /> TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC<br /> <br /> Đà Nẵng - Năm 2011<br /> <br /> Công trình được hoàn thành tại<br /> ĐẠI HỌC ĐÀ NẴNG<br /> <br /> Người hướng dẫn khoa học: TS. Nguyễn An Khương<br /> <br /> Phản biện 1: TS. Lê Hải Trung<br /> Phản biện 2: PGS. TS. Nguyễn Gia Định<br /> <br /> Luận văn sẽ được bảo vệ trước Hội đồng chấm<br /> Luận văn tốt nghiệp thạc sĩ khoa học họp tại Đại học Đà Nẵng<br /> vào ngày 28 tháng 5 năm 2011.<br /> <br /> Có thể tìm hiểu luận văn tại:<br /> - Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng.<br /> - Thư viện trường Đại học sư phạm, Đại học Đà Nẵng.<br /> <br /> 1<br /> <br /> MỞ ĐẦU<br /> 1. Lý do chọn đề tài<br /> Tổ hợp là một lĩnh vực quan trọng của toán học nói chung và toán rời<br /> rạc nói riêng. Các bài toán tổ hợp có nội dung phong phú, được nghiên cứu<br /> và ứng dụng rộng rãi trong thực tế đời sống và trên nhiều lĩnh vực khác<br /> nhau, đặc biệt là xác suất thống kê.<br /> Hiện nay, kiến thức cơ bản về tổ hợp đã được đưa vào chương trình giảng<br /> dạy ở lớp 11. Trong những kì thi tuyển sinh đại học, thi học sinh giỏi quốc<br /> gia, thi Olympic toán quốc tế, thi Olympic sinh viên giữa các trường đại<br /> học và cao đẳng thì các bài toán tổ hợp hay được đề cập và thường thuộc<br /> loại khó. Đối với những bài toán tổ hợp phức tạp việc áp dụng các kiến<br /> thức cơ bản để giải sẽ gặp nhiều khó khăn, nên cần có những phương pháp<br /> sắc bén hơn.<br /> Chính vì những lí do trên, chúng tôi chọn đề tài "Số ánh xạ không phân<br /> rã được trên tập hữu hạn"nhằm nghiên cứu về số các ánh xạ trên các tập<br /> hữu hạn thỏa mãn tính chất mà chúng tôi gọi là "không phân rã được".<br /> <br /> 2. Mục đích nghiên cứu<br /> Mục đích của đề tài là đề xuất thêm phương pháp chứng minh mới, hoàn<br /> toàn bằng sơ cấp để tính số ánh xạ không phân rã được trên tập hữu hạn.<br /> <br /> 3. Đối tượng và phạm vi nghiên cứu<br /> Đối tượng nghiên cứu là số ánh xạ không phân rã được.<br /> Phạm vi nghiên cứu là số ánh xạ không phân rã được trên tập hữu hạn.<br /> <br /> 2<br /> <br /> 4. Phương pháp nghiên cứu<br /> Đọc hiểu và sử lý tài liệu tham khảo đồng thời làm việc theo sự hướng<br /> dẫn của người hướng dẫn khoa học.<br /> <br /> 5. Ý nghĩa khoa học và thực tiễn của đề tài<br /> Hệ thống hóa các phương pháp tìm số ánh xạ không phân rã được trên<br /> tập hữu hạn.<br /> Đưa ra cách chứng minh mới cho việc tìm số ánh xạ không phân rã được<br /> trên tập hữu hạn.<br /> <br /> 6. Cấu trúc luận văn<br /> Luận văn được chia làm bốn chương.<br /> Chương 1: Kiến thức chuẩn bị.<br /> Trong phần này chúng tôi giới thiệu những kiến thức và các kết quả cơ<br /> bản về các quy tắc đếm, sử dụng quy tắc song ánh, phân hoạch tổ hợp để<br /> giải quyết các bài toán tổ hợp, đồng thời nêu khái niệm về xích và độ dài<br /> của xích.<br /> Chương 2: Các số tổ hợp cơ bản.<br /> Chương này chúng tôi nhắc lại các số tổ hợp cơ bản, đó là các số Hoán<br /> vị, Chỉnh hợp, Tổ hợp, số Stirling loại một, số Stirling loại hai và số Bell<br /> cùng với số các ánh xạ đặc biệt trên tập hữu hạn.<br /> Chương 3: Dãy nhị thức.<br /> Trong chương này luận văn giới thiệu sơ lược về dãy nhị thức Pn (t)n≥0 .<br /> Chương 4: Ánh xạ không phân rã được.<br /> Đây là chương cơ bản và quan trọng nhất của luận văn chúng tôi đưa ra<br /> một số khái niệm mới như ánh xạ không phân rã được từ tập [n] vào chính<br /> nó. Đặc biệt chúng tôi đưa ra cách chứng minh mới để tìm số ánh xạ không<br /> phân rã được trên tập hữu hạn.<br /> <br /> 3<br /> <br /> Chương 1<br /> KIẾN THỨC CHUẨN BỊ<br /> 1.1<br /> 1.1.1<br /> <br /> Quy tắc cộng, quy tắc nhân<br /> Quy tắc cộng<br /> <br /> Nếu có m1 cách chọn đối tượng a1 , m2 cách chọn đối tượng a2 , ..., mn<br /> cách chọn đối tượng an , trong đó cách chọn đối tượng ai (1 ≤ i ≤ n) không<br /> phụ thuộc vào bất kì cách chọn đối tượng aj nào (1 ≤ j ≤ n, i = j) thì<br /> n<br /> <br /> mk cách chọn đối tượng a1, hoặc a2, ..., hoặc an.<br /> <br /> sẽ có<br /> k=1<br /> <br /> Để vận dụng có hiệu quả, ta chuyển qui tắc này sang dạng sau:<br /> Cho n tập hợp Ak (1 ≤ k ≤ n) với |Ak | = mk và ∀i, j(1 ≤ i, j ≤<br /> n)Ai ∩ Aj = ∅, khi i = j . Khi đó số cách chọn a1, hoặc a2, ..., hoặc an sẽ<br /> n<br /> <br /> bằng số cách chọn các phần tử a ∈<br /> <br /> Ak và |<br /> k=1<br /> <br /> 1.1.2<br /> <br /> n<br /> <br /> n<br /> <br /> |Ak |.<br /> <br /> Ak | =<br /> k=1<br /> <br /> k=1<br /> <br /> Quy tắc nhân<br /> <br /> Cho n đối tượng a1 , a2 , ..., an . Nếu có m1 cách chọn đối tượng a1 và ứng<br /> với mỗi cách chọn a1 ta có m2 cách chọn đối tượng a2 , sau đó với mỗi cách<br /> chọn a1 , a2 ta có m3 cách chọn đối tượng a3 , ... Cuối cùng với mỗi cách<br /> chọn a1 , a2 , ..., an−1 ta có mn cách chọn đối tượng an .<br /> Vậy sẽ có m1 .m2 .....mn−1 .mn cách chọn các đối tượng a1 , rồi a2 ,..., rồi<br /> an .<br /> Chú ý 1. Để vận dụng có hiệu quả, ta chuyển quy tắc nhân sang dạng<br /> sau:<br /> <br />