Luận văn Thạc sĩ Toán học: Một số phương pháp tính toá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ố

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:75

Thêm vào BST

Báo xấu

16
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn tổng hợp một số dạng bài tập đặc trưng góp phần nâng cao tư duy tổ hợp của học sinh cũng như giúp học sinh lựa chọn kiến thức trong quá trình giải một bài toán tổ hợp. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số phương pháp tính toá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ố

ĐẠ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 TOÁ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 TOÁ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ố: 8 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 này được hoàn thành tại 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 đối với 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 và động viên tác giả trong suốt thời gian nghiên cứu vừa qua. Xin chân thành cảm ơn tới các quý thầy, cô giáo đã trực tiếp giảng dạy lớp cao học Toán K11, các bạn học viên, và các bạn đồng nghiệp đã tạo điều kiện thuận lợi, động viên giúp đỡ tác giả trong quá trình học tập và nghiên cứu tại trường. Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người thân luôn khuyến khích động viên tác giả trong suốt quá trình học cao học và viết luận văn này. Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót và hạn chế. Tác giả mong nhận được những ý kiến đóng góp của các thầy cô và các bạn đọc để luận văn được hoàn thiện hơ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 1 Chương 1. MỘT SỐ TÍNH CHẤT CỦA TẬP HỢP HỮU HẠN 2 1.1 Một số khái niệm cơ bản liên quan đến tập hợp . . . . . . . . . . . 2 1.1.1 Công thức tính lực lượng của tập hợp . . . . . . . . . . . . 3 1.1.2 Một số nguyên lý cơ bản của phép đếm . . . . . . . . . . . 4 1.2 Các quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Quy tắc cộng . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Quy tắc nhân . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.6 Khai triển lũy thừa của nhị thức . . . . . . . . . . . . . . . . . . . 8 Chương 2. ĐẲNG THỨC, BẤT ĐẲNG THỨC VÀ MỘT SỐ BÀI TOÁN CỰC TRỊ TRONG TỔ HỢP 9 2.1 Một số đẳng thức cơ bản trong tổ hợp . . . . . . . . . . . . . . . . 9 2.2 Một số bất đẳng thức thông dụng . . . . . . . . . . . . . . . . . . 11 2.3 Các bài toán cực trị rời rạc liên quan . . . . . . . . . . . . . . . . 13 Chương 3. MỘT SỐ PHƯƠNG PHÁP XÁC ĐỊNH LỰC LƯỢNG CỦA TẬP HỮU HẠN 30 3.1 Một số phương pháp đếm trong số học . . . . . . . . . . . . . . . . 30 3.1.1 Nguyên lý bao hàm và loại trừ . . . . . . . . . . . . . . . . 30 3.1.2 Phương pháp đếm số lần xuất hiện của mỗi phần tử trong tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.1.3 Đếm theo phương pháp thiết lập hệ thức truy hồi . . . . . 42 3.2 Một số bài toán đếm trong hình học tổ hợp . . . . . . . . . . . . . 49
iii 3.3 Một số tính toán khác trên tập rời rạc . . . . . . . . . . . . . . . . 58 KẾT LUẬN 69 TÀI LIỆU THAM KHẢO 70
1 Mở đầu Toán học tổ hợp được nghiên cứu từ khá sớm. Hiện nay trong giáo dục phổ thông, toán học tổ hợp là một trong những nội dung quan trọng, thường xuyên xuất hiện trong các đề thi THPT Quốc Gia và đề thi chọn học sinh giỏi các cấp. Trong các bài toán tổ hợp có một lớp các bài toán đếm. Bài toán đếm rất phong phú kể cả dạng phát biểu đến cách giải. Độ khó của bài toán đếm được trải rất rộng - từ những bài toán dễ với các số liệu cụ thể, có thể kiểm chứng bằng trực giác đến những bài toán khó hơn, với những dữ liệu đầu vào bằng chữ mà kết quả của nó được biểu diễn bằng một công thức toán học. Có những công thức được tìm ra qua một vài suy luận đơn giản nhưng cũng có những công thức mà việc tìm thấy chúng phải kéo dài rất lâu. Bài toán đếm giúp học sinh phát huy tốt khả năng tư duy sáng tạo. Nhằm đáp ứng nhu cầu bồi dưỡng học sinh giỏi và phát triển tư duy cho học sinh tôi chọn đề tài “Một số phương pháp tính toá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 tổng hợp một số dạng bài tập đặc trưng góp phần nâng cao tư duy tổ hợp của học sinh cũng như giúp học sinh lựa chọn kiến thức trong quá trình giải một bài toán tổ hợp. Cấu trúc luận văn gồm 3 chương. Chương 1. Một số tính chất của tập hợp hữu hạn. Chương 2. Đẳng thức, bất đẳng thức và một số bài toán cực trị tổ hợp. Chương 3. Một số phương pháp xác định lực lượng của tập hữu hạn.
2 Chương 1. 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 các khái niệm cơ bản liên quan đến tập hợp, các phép toán cơ bản của tập hợp, các công thức liên quan đến hoán vị chỉnh hợp và tổ hợp, công thức tính lực lượng của tập hợp và một số nguyên lý đếm nâng cao nhằm chuẩn bị cơ sở cho việc giải các bài toán trong chương 2 và chương 3. Các kết quả trong chương 1 được trích dẫn từ tài liệu tham khảo [3]. 1.1 Một số khái niệm cơ bản liên quan đến tập hợp Định nghĩa 1.1. Tập B được gọi là tập con của tập A nếu mỗi phần tử của nó đều thuộc tập A. Ký hiệu B ⊆ A. Định nghĩa 1.2. Khi B là tập con của tập A và B 6= A, thì B được gọi là tập con thực sự của tập A. Ký hiệu B ⊂ A. Định nghĩa 1.3. Tập hợp không chứa một phần tử nào được gọi là tập hợp rỗng. Ký hiệu là ∅. Định nghĩa 1.4. Cho tập A, số phần tử trong tập A được gọi là lực lượng của tập A, ký hiệu là |A|. Định nghĩa 1.5. Cho các tập hợp A, B , tập gồm các phần tử hoặc thuộc tập A hoặc thuộc tập B được gọi là hợp của tập A và tập B . Ký hiệu là A ∪ B hoặc A ∨ B. Định nghĩa 1.6. Cho các tập hợp A, B , tập hợp gồm các phần tử thuộc đồng thời cả tập A và tập B được gọi là giao của tập A và tập B . Kí hiệu là A ∩ B hoặc A ∧ B.
3 Định nghĩa 1.7. Tập hợp gồm các phần tử thuộc A nhưng không thuộc B được gọi là hiệu của tập A và tập B . Ký hiệu là A\B . Định nghĩa 1.8. Giả sử tập B là tập con của tập A, tập gồm tất cả các phần tử thuộc A, nhưng không thuộc B được gọi là phần bù của tập B trong tập A và ký hiệu là CA (B). 1.1.1 Công thức tính lực lượng của 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 là các tập hữu hạn ta đặt m X N1 = |A1 | i=1 X N2 = |Ai ∩ Ai | 1≤i
4 = 1 − (1 − 1)k = 1. m S Rõ ràng, với mỗi a 6∈ Ai , ở cả vế trái và vế phải của (1.1) số lần a được đếm i=1 là 0 lần. Như vậy, với mọi phần tử a, số lần a được đếm ở vế trái và vế phải của (1.1) là như nhau. Do đó ta có điều phải chứng minh. 1.1.2 Một số nguyên lý cơ bản của phép đếm Nguyên lý cộng Cho A1 , A2 , . . . Am là các tập hữu hạn từng đôi một rời nhau. Khi đó ta có m X |A1 ∪ A2 ∪ . . . ∪ Am | = |Ai |. i=1 Nguyên lý nhân Nếu A1 , A2 , . . . Am là các tập hữu hạn thì |A1 × A2 × · · · × Am | = |A1 ||A2 | . . . |Am |. Nguyên lý trừ Nếu Y là một tập con của một tập hữu hạn X thì |X \ Y | = |X| − |Y |. Nguyên lý bù trừ (công thức Sieve) Giả sử A1 , A2 , . . . Am là các tập con của một tập hữu hạn X , kí hiệu Ai là phần bù của Ai trong X , (i = 1; 2; . . . m) thì |A1 ∩ A2 . . . ∩ Am | = |A1 ∪ A2 ∪ . . . ∪ Am | m X X = |X| + (−1)k |Ai1 ∩ Ai2 . . . ∩ Aik |. k=1 a≤i1
5 Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất N k đồ vật. (Ở đây, dxe là giá trị của hàm trần của số thực x, đó là số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x. Khái niệm này đối ngẫu với hàm sàn [x] - giá trị của hàm sàn hay hàm phần nguyên tại x - là số nguyên lớn nhất có giá trị nhỏ hơn hoặc bằng x.) Nguyên lí Dirichlet mở rộng Nếu nhốt n con thỏ vào m ≥ 2 cái chuồng thì tồn tại một chuồng có ít nhất n+m−1 m con thỏ. Ta chứng minh nguyên lí Dirichlet mở rộng như sau. Giả sử trái lại, mọi chuồng thỏ có không đến n+m−1 n−1 n−1 = +1 = +1 m m m con thỏ, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng n−1 m con. Suy ra tổng số con thỏ không vượt quá n−1 m· ≤ n − 1. m Điều này vô lí, vì có n con thỏ. Vậy giả thiết phản chứng là sai. Nguyên lí Dirichlet mở rộng được chứng minh. Nguyên lí cực hạn Nguyên lí cực hạn được phát biều đơn giản như sau. Nguyên lí 1: Trong một tập hữu hạn và khác rỗng các số thực luôn luôn có thể chọn được số bé nhất và số lớn nhất. Nguyên lí 2: Trong một tập khác rỗng hữu hạn các số tự nhiên luôn luôn có thể chọn được số bé nhất. 1.2 Các quy tắc đếm cơ bản 1.2.1 Quy tắc cộng Nội dung quy tắc. Nếu có m1 cách chọn đối tượng a1 , m2 cách chọn đối tượng a2 ,. . . , mn cách chọn đối tượng an , trong đó cách chọn đối tượng ai (1 ≤ i ≤ n) không phụ thuộc vào bất kỳ cách chọn đối tượng aj nào (1 ≤ j ≤ n, i 6= j), thì Pn sẽ có mk cách chọn đối tượng a1 , hoặc a2 ,. . . , hoặc an . k=1
6 Phát biểu bằng ngôn ngữ tập hơp như sau. Cho n tập Ak (1 ≤ k ≤ n) với |Ak | = mk và ∀i, j (1 ≤ i, j ≤ n) Ai ∩ Aj = ∅, khi i 6= j . Khi đó số cách chọn a1 , hoặc a2 ,. . . , hoặc an trong các tập tương [n ứng Ak (1 ≤ k ≤ n) sẽ bằng số cách chọn phần tử a thuộc Ak và bằng k=1
[n
Xn
Ak
= |Ak |.
i=1 k=1 1.2.2 Quy tắc nhân Cho n đối tượng a1 , a2 , . . . , an . Nếu có m1 cách chọn đối tượng a1 và với mỗi cách chọn a1 có m2 cách chọn đối tượng a2 , sau đó với mỗi cách chọn a1 , a2 có m3 cách chọn a3 ,. . . Cuối cùng với mỗi cách chọn a1 , a2 , . . . , an−1 có mn cách chọn đối tượng an . Như vậy sẽ có m1 .m2 . . . . .mn−1 .mn cách chọn các đối tượng a1 , rồi a2 , rồi a3 ,. . . , rồi an . Phát biểu bằng ngôn ngữ tập hợp như sau. Giả sử có n tập hợp Ak (1 ≤ k ≤ n) với |Ak | = mk . Khi đó, số cách chọn bộ gồm n phần tử (a1 , a2 , . . . , an ) với ai ∈ Ai (1 ≤ i ≤ n) sẽ là n Y S = |A1 × A2 × · · · × An | = m1 × m2 × · · · × mn = mk . k=1 1.3 Hoán vị Định nghĩa 1.9. Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó được gọi là một hoán vị của n phần tử đã cho. Kí hiệu số hoán vị của n phần tử bằng Pn . Ta có công thức tính số hoán vị của n phần tử Pn = n! Định nghĩa 1.10. Hoán vị lặp là bộ sắp thứ tự các phần tử của một tập hợp mà trong đó mỗi phần tử xuất hiện ít nhất một lần. Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i (1 ≤ i ≤ k) xuất hiện ni lần được kí hiệu là P (n1 , n2 , . . . , nk ) và được tính bằng công thức n! P (n1 , n2 , . . . , nk ) = . n1 !n2 ! . . . nk !
7 Định nghĩa 1.11. Số hoán vị vòng quanh của n phần tử khác nhau ký hiệu là (Qn ) và được tính bằng công thức Qn = (n − 1)! 1.4 Chỉnh hợp Định nghĩa 1.12. Cho tập hợp A gồm n phần tử. Mỗi cách xếp thứ tự cho k phần tử (0 ≤ k ≤ n) của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử thuộc A. Kí hiệu số chỉnh hợp chập k của n phần tử là Akn . Công thức tính số chỉnh hợp chập k của n phần tử. n! Akn = n(n − 1) . . . (n − k + 1) = · (n − k)! Định nghĩa 1.13. Cho tập hữu hạn X gồm n phần tử. Mỗi dãy có độ dài k các phần tử của tập X , mà mỗi phần tử có thể lặp lại nhiều lần và được sắp xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập k của n phần tử thuộc tập X . Số chỉnh hợp lặp chập k của n phần tử, kí hiệu là Akn , bằng số ánh xạ từ tập k phần tử đến tập n phần tử và bằng nk , do đó ta có công thức Akn = nk . 1.5 Tổ hợp Định nghĩa 1.14. Cho tập A gồm n phần tử. Mỗi tập con gồm k (0 ≤ k ≤ n) phần tử thuộc A được gọi là một tổ hợp chập k của n phần tử đã cho. Số tổ hợp chập k (0 ≤ k ≤ n) của n phần tử, được kí hiệu là Cnk Công thức tính số tổ hợp chập k (0 ≤ k ≤ n) của n phần tử n! Cnk = . k!(n − k)! Định nghĩa 1.15. Cho tập hợp A = {a1 , a2 , . . . , an }. Một tổ hợp lặp chập m (m không nhất thiết phải nhỏ hơn n) của n phần tử thuộc A là một bộ gồm m phần tử, mà mỗi phần tử này là một trong những phần tử của A.
8 Ta sử dụng Cnm để kí hiệu số tổ hợp lặp chập m của n phần tử. Khi đó m Cnm = Cn+m−1 . 1.6 Khai triển lũy thừa của nhị thức Ta có công thức khai triển của (x + y)n Cho mỗi số tự nhiên n > 1 ta có n X n (x + y) = Cnk xn−k y k . k=0 Ta có thể tính nhanh các hệ số trong khai triển trên bằng tam giác Pascal. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
9 Chương 2. ĐẲNG THỨC, BẤT ĐẲNG THỨC VÀ MỘT SỐ BÀI TOÁN CỰC TRỊ TRONG TỔ HỢP Trong chương này, tác giả nhắc lại một số đẳng thức cơ bản trong tổ hợp và một số bất đẳng thức cơ bản trong đại số. Trên cơ sở lý thuyết đó tiến hành giải quyết các bài toán về cực trị tổ hợp liên quan đến việc ước lượng các phần tử của tập hữu hạn. Trong chương 2, tác giả sử dụng các tài liệu tham khảo [1], [2], [3] và [4]. 2.1 Một số đẳng thức cơ bản trong tổ hợp Tính chất 2.1 (Tính chất đối xứng). Với mọi số tự nhiên n, k ∈ N thỏa mãn 0 ≤ k ≤ n ta có Cnk = Cnn−k . Tính chất 2.2 (Tính chất tam giác Pascal). Cnk + Cnk+1 = Cn+1 k+1 . Tính chất 2.3 (Công thức tính tổng theo cột). n X Ckm = Cn+1 m+1 . k=0 Chứng minh. Áp dụng công thức Pascal, ta có: n X n X Ckm = m+1 (Ck+1 − Ckm+1 ) = Cn+1 m+1 − C0m+1 = Cn+1 m+1 . k=0 k=0