1쪽
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC QUY NHƠN —————————————— NGUYỄN THỊ QUÀ MỘT SỐ BÀI TOÁN TỔ HỢP SƠ CẤP LIÊN QUAN ĐẾN VẤN ĐỀ SẮP XẾP VÀ PHÂN HOẠCH TRÊN TẬP HỮU HẠN LUẬN VĂN THẠC SĨ TOÁN HỌC Bình Định - 2022
자료 내용
2쪽
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC QUY NHƠN —————————————— NGUYỄN THỊ QUÀ MỘT SỐ BÀI TOÁN TỔ HỢP SƠ CẤP LIÊN QUAN ĐẾN VẤN ĐỀ SẮP XẾP VÀ PHÂN HOẠCH TRÊN TẬP HỮU HẠN Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8460113 Khóa: 23 (2020 - 2022) LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: PGS.TSKH. HUỲNH VĂN NGÃI Bình Định - 2022
3쪽
LỜI CAM ĐOAN Luận văn này được hoàn thành tại Trường Đại học Quy Nhơn. Tác giả xin cam đoan rằng nội dung trình bày trong luận văn là trung thực và không trùng lặp với các đề tài khác tính đến thời điểm hiện tại. Đề tài “Một số bài toán tổ hợp sơ cấp liên quan đến vấn đề sắp xếp và phân hoạch trên tập hữu hạn” là kết quả nghiên cứu của tác giả dưới sự hướng dẫn khoa học của PGS.TSKH. Huỳnh Văn Ngãi. Tác giả cũng xin cam đoan rằng các kết quả được trình bày trong luận văn được tham khảo và trích dẫn từ các tài liệu đảm bảo tính rõ ràng và chính xác. Bình Định, ngày 25 tháng 7 năm 2022 Tác giả Nguyễn Thị Quà
4쪽
MỤC LỤC LỜI CAM ĐOAN MỤC LỤC DANH MỤC KÝ HIỆU LỜI MỞ ĐẦU 1 Chương 1 CÁC SỐ TỔ HỢP CƠ BẢN VÀ HÀM SINH 4 1.1 Các nguyên tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . 4 1.1.1 Nguyên tắc cộng . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Nguyên tắc nhân . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Nguyên tắc bù trừ . . . . . . . . . . . . . . . . . . . . 6 1.2 Các cấu hình tổ hợp cơ bản . . . . . . . . . . . . . . . . . . . 7 1.2.1 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.2 Hoán vị lặp . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.3 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.4 Chỉnh hợp lặp . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.6 Tổ hợp lặp . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.7 Nhị thức Newton . . . . . . . . . . . . . . . . . . . . . 9 1.3 Hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5쪽
1.3.1 Hệ số nhị thức tổng quát . . . . . . . . . . . . . . . . . 10 1.3.2 Chuỗi luỹ thừa hình thức . . . . . . . . . . . . . . . . 11 1.3.3 Hàm sinh thường . . . . . . . . . . . . . . . . . . . . . 13 1.3.4 Áp dụng hàm sinh vào hệ thức truy hồi . . . . . . . . . 15 Chương 2 SỐ STIRLING LOẠI HAI VÀ SỐ CATALAN 22 2.1 Số Stirling loại hai . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.1 Một số định nghĩa và tính chất cơ bản . . . . . . . . . 22 2.1.2 Một số bài tập áp dụng liên quan đến số Stirling loại hai 27 2.2 Số Catalan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2.1 Một số định nghĩa và tính chất cơ bản . . . . . . . . . 35 2.2.2 Một số bài tập áp dụng liên quan đến số Catalan . . . 41 Chương 3 BÀI TOÁN CHIA KẸO EULER VÀ PHÂN HOẠCH SỐ NGUYÊN 48 3.1 Bài toán chia kẹo Euler . . . . . . . . . . . . . . . . . . . . . . 48 3.1.1 Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1.2 Một số bài toán mở rộng của bài toán chia kẹo Euler . 50 3.2 Phân hoạch của số nguyên . . . . . . . . . . . . . . . . . . . . 61 3.2.1 Một số định nghĩa và tính chất cơ bản . . . . . . . . . 61 3.2.2 Một số bài tập áp dụng liên quan đến phân hoạch của số nguyên . . . . . . . . . . . . . . . . . . . . . . . . . 85 Chương 4 MỘT SỐ BÀI TOÁN SƠ CẤP LIÊN QUAN 90 4.1 Một số bài toán sơ cấp liên quan đến bài toán chia kẹo Euler . 90 4.2 Một số bài toán sơ cấp liên quan khác . . . . . . . . . . . . . 102 Kết luận 112 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6쪽
DANH MỤC KÝ HIỆU N : Tập các số tự nhiên. N˚ : Tập các số tự nhiên khác 0. Z : Tập các số nguyên. R : Tập các số thực. R` : Tập các số thực không âm. |A| : Số phần tử của tập hợp A. rns : Tập hợp t1,2,¨ ¨ ¨ , nu. x P A : phần tử x thuộc tập hợp A. x R A : phần tử x không thuộc tập hợp A. A Ă B : Tập hợp A con tập hợp B. A X B : Tập hợp A giao với tập hợp B. A Y B : Tập hợp A hợp với tập hợp B. AzB : Tập hợp A hiệu tập hợp B. řn ai : a1 ` a2 ` ¨ ¨ ¨ ` an. iř“1 an : a0 ` a1 ` `a2 ` ¨ ¨ ¨. ně0
7쪽
LỜI MỞ ĐẦU Lý thuyết tổ hợp được hình thành như một ngành toán học vào khoảng thế kỷ XVII bằng một loạt các công trình nổi tiếng của các nhà Toán học lỗi lạc như Pascal, Fermat, Leibniz, ... Đặc biệt vào khoảng cuối thế kỷ XX, với sự xuất hiện của máy tính, lý thuyết tổ hợp phát triển ngày càng mạnh mẽ, và ngày nay, nó đã trở thành một phần quan trọng của toán học nói chung và toán học rời rạc nói riêng. Nó không chỉ có nội dung phong phú, đa dạng, mà còn có nhiều ứng dụng trong các lĩnh vực khác của toán học như: đại số, lý thuyết xác suất, lý thuyết ergodic (ergodic theory), hình học.., cũng như các ngành khoa học ứng dụng khác như: khoa học máy tính, vật lý thống kê và nhiều ứng dụng trong thực tế đời sống. Những bài toán tổ hợp liên quan đến vấn đề sắp xếp, phân hoạch tập hợp đóng vai trò quan trọng trong lý thuyết tổ hợp nói chung, và trong tổ hợp sơ cấp trong chương trình toán phổ thông nói riêng. Đặc biệt, trong những năm gần đây, các bài toán tổ hợp liên quan đến vấn đề sắp xếp, phân hoạch tập hợp cũng thường xuyên xuất hiện trong các kỳ thi chọc sinh giỏi Toán quốc gia và quốc tế. Có rất nhiều những kết quả lý thuyết sâu sắc cũng như những ứng dụng đã đạt được trong vài chục năm gần đây. Riêng trong toán tổ hợp sơ cấp, mặc dù có nhiều tài liệu tổ hợp dành cho chương trình phổ thông, tuy nhiên gần như chưa có (ít nhất ở Việt Nam) một tài liệu có hệ thống về các vấn đề liên quan đến bài toán phân hoạch trên tập hữu hạn. Vì vậy, với sự hướng dẫn khoa học của thầy PGS.TSKH. Huỳnh Văn Ngãi, tôi đã chọn đề tài “Một số bài toán tổ hợp sơ cấp liên quan đến vấn đề sắp xếp và phân hoạch trên tập hữu hạn” cho luận văn thạc sĩ của mình. Mục tiêu của Luận văn là tập trung giải quyết một số bài toán tổ hơp sơ 1
8쪽
2 cấp liên quan đến vấn đế sắp xếp và phân hoạch trên các tập hữu hạn như: các bài toán về các số Stirling, số Catalan, bài toán chia kẹo Euler, bài toán phân hoạch số nguyên,... Ngoài phần Mở đầu, Kết luận, Tài liệu tham khảo, nội dung của Luận văn được chia làm bốn chương. ‚ Chương 1: Trình bày một số kiến thức cơ bản về các số tổ hợp cơ bản và hàm sinh, nhằm sử dụng cho các chương tiếp theo. ‚ Chương 2: Trình bày một số kiến thức cơ bản của các số Stirling, số Catalan và một số ứng dụng của chúng. ‚ Chương 3: Trình bày bài toán chia kẹo Euler, một số bài toán mở rộng của bài toán chia kẹo Euler và một số kiến thức cơ bản về phân hoạch của số nguyên cũng như các ứng dụng của nó. ‚ Chương 4: Sưu tầm và hệ thống một số bài toán tổ hợp sơ cấp trong các đề thi học sinh giỏi Toán quốc tế, quốc gia, các đề ôn và thi chọn đội tuyển học sinh giỏi các tỉnh, thành phố liên quan đến bài toán sắp xếp và phân hoạch trên các tập hữu hạn. Luận văn được hoàn thành dưới sự hướng dẫn khoa học của thầy PGS. TSKH. Huỳnh Văn Ngãi, Khoa Toán và Thống kê, Trường Đại học Quy Nhơn. Nhân dịp này, tôi xin được bày tỏ sự kính trọng và lòng biết ơn sâu sắc đến Thầy, đã tận tình giúp đỡ và truyền đạt những kiến thức cũng như những kinh nghiệm quý báu trong suốt quá trình học tập và nghiên cứu, thực hiện Luận văn, để tôi có thể hoàn thành Luận văn một cách tốt nhất. Tôi cũng xin gửi lời cảm ơn đến Ban giám hiệu nhà trường, Phòng Đào tạo Sau Đại học, Khoa Toán và Thống kê, cùng quý thầy cô đã giảng dạy lớp cao học, chuyên ngành Phương pháp Toán sơ cấp K23, Trường Đại học Quy Nhơn, đã tạo điều kiện thuận lợi cho tôi trong suốt quá trình học tập và nghiên cứu, thực hiện đề tài. Tôi cũng xin được gửi lời cảm ơn đến Lãnh đạo Sở Giáo dục và Đào tạo Phú Yên, Ban giám hiệu nhà trường, cùng quý thầy cô, đồng nghiệp trường THCS & THPT Nguyễn Khuyến và các bạn lớp cao học, chuyên ngành Phương pháp Toán sơ cấp K23, đã nhiệt tình giúp đỡ và tạo điều kiện
9쪽
3 thuận lợi cho tôi trong suốt quá trình học tập và nghiên cứu, thực hiện đề tài. Cuối cùng, tôi xin chân thành cảm ơn gia đình và những người thân, bạn bè của tôi, đã động viên và hỗ trợ tinh thần rất tốt cho tôi trong suốt thời gian học tập và nghiên cứu, thực hiện đề tài. Mặc dù luận văn được thực hiện với sự nổ lực và cố gắng hết sức của bản thân nhưng do điều kiện thời gian có hạn, trình độ kiến thức và kinh nghiệm nghiên cứu còn hạn chế nên Luận văn cũng khó tránh khỏi những thiếu sót. Tôi rất mong nhận được sự góp ý của quý thầy, cô để luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn!
10쪽
Chương 1 CÁC SỐ TỔ HỢP CƠ BẢN VÀ HÀM SINH Trong chương này chúng tôi trình bày một số kiến thức cơ bản về các số tổ hợp cơ bản như: Hoán vị, chỉnh hợp, tổ hợp, các nguyên tắc đếm... và các kiến thức cơ bản về hàm sinh, nhằm sử dụng cho các chương tiếp theo. Các kiến thức cơ bản trong chương này chủ yếu được tham khảo từ các tài liệu [1],[2], [3], [7]. 1.1 Các nguyên tắc đếm cơ bản 1.1.1 Nguyên tắc cộng Định lý 1.1 ([1]). Nếu A1, A2, ..., An là các tập hợp hữu hạn, đôi một không giao nhau thì |A1 Y A2 Y ¨ ¨ ¨ Y An| “ |A1| ` |A2| ` ¨ ¨ ¨ ` |An|. Nguyên tắc này trong chương trình phổ thông được phát biểu như sau: Giả sử một công việc được thực hiện theo một trong n phương án A1, A2, ..., An. Phương án A1 có m1 cách thực hiện, phương án A2 có m2 cách thực hiện ,..., phương án An có mn cách thực hiện. Khi đó công việc có thể được thực hiện bởi m1 ` m2 ` ... ` mn cách. 4
11쪽
5 Ví dụ 1.1. Trên giá sách của Nam có n1 quyển giáo khoa, n2 quyển sách bài tập, n3 quyển truyện tranh, n4 quyển tiểu thuyết (tất cả đều khác nhau). Hỏi Nam có bao nhiêu cách chọn một quyển sách để đọc? Lời giải. Gọi A1, A2, A3, A4 lần lượt là tập hợp các sách giáo khoa, sách bài tập, truyện tranh, tiểu thuyết. Khi đó ta có A1, A2, A3, A4 là các tập hữu hạn, đôi một không giao nhau. Theo nguyên tắc cộng, số cách Nam có thể chọn một quyển sách để đọc là |A1 Y A2 Y A3 Y A4| “ |A1| ` |A2| ` |A3| ` |A4| “ n1 ` n2 ` n3 ` n4 (cách). 1.1.2 Nguyên tắc nhân Định lý 1.2 ([1]). Cho X1, X2,¨ ¨ ¨ , Xn là các tập hữu hạn. Khi đó số bộ giá trị px1, x2,¨ ¨ ¨ , xnq thoả mãn xi P Xi, @i “ 1,2,¨ ¨ ¨ , n là |X1|.|X2|.¨ ¨ ¨ .|Xn|. Nguyên tắc này trong chương trình phổ thông được phát biểu như sau: Giả sử một công việc được thực hiện bởi n công đoạn A1, A2, ..., An liên tiếp nhau. Công đoạn A1 có thể được thực hiện theo m1 cách, công đoạn A2 có thể được thực hiện theo m2 cách,..., Công đoạn An có thể được thực hiện theo mn cách. Khi đó công việc có thể được thực hiện theo m1.m2.¨ ¨ ¨ .mn cách. Ví dụ 1.2. Có bao nhiêu số nguyên dương có k chữ số, với k nguyên dương? Lời giải. Một số nguyên dương có k chữ số chính là một bộ giá trị px1, x2, . . . , xkq, trong đó xi là chữ số thứ i trong số nguyên của chúng ta cần tìm. Khi đó x1 P t1,2,¨ ¨ ¨ ,9u và xi P t0,1,2,¨ ¨ ¨ ,9u, với 2 ď i ď k. Do đó, |X1| “ 9 và |Xi| “ 10, với mọi 2 ď i ď k. Vậy theo nguyên tắc nhân, số các số nguyên dương có k chữ số, với k nguyên dương là 9.10k´1 (số).
앞 11페이지만 표시됩니다. 전체를 보려면 자료를 다운로드하세요.
댓글 (0)
댓글이 없습니다. 첫 댓글을 남겨보세요!