Tài liệu Số catalan và ứng dụng

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHAN BÍCH HOÀI SỐ CATALAN VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHAN BÍCH HOÀI SỐ CATALAN VÀ ỨNG DỤNG 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ố: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. ĐÀM VĂN NHỈ Thái Nguyên - 2016 i Mục lục Lời mở đầu Chương 1. Kiến thức chuẩn bị 1.1 Quan hệ tương đương và ánh xạ 1.1.1 Quan hệ tương đương . . 1.1.2 Ánh xạ và phép toán . . 1.1.3 Nguyên lý Bù-Trừ . . . . 1.2 Tổ hợp . . . . . . . . . . . . . . 1.2.1 Phương pháp quy nạp . 1.2.2 Quy tắc đếm . . . . . . 1.2.3 Khái niệm tổ hợp . . . . 1.3 Khai triển (x1 + x2 + · · · + xk )n 1.4 Chuỗi Taylor-Maclaurin . . . . 1 . . . . . . . . . . . . . . . . . . . . Chương 2. Số Catalan 2.1 Hàm sinh thường và số Catalan . . 2.1.1 Chuỗi lũy thừa hình thức và 2.1.2 Số Catalan . . . . . . . . . 2.2 Cây và số Catalan . . . . . . . . . 2.3 Phân hoạch và số Catalan . . . . . 2.4 Tam giác Pascal và số Catalan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . hàm sinh thường . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 4 6 8 8 12 13 13 15 . . . . . . 18 18 18 25 31 37 44 Kết luận 51 Tài liệu tham khảo 52 1 Lời mở đầu Dãy số Fibonacy và dãy Lucas được ví như “hai vì sao sáng trong bầu trời rộng lớn các dãy số nguyên”. Các ứng dụng phong phú của chúng tạo nên tính hấp dẫn. Hơn nữa, cùng với sự dễ dàng đánh giá của các dãy số này đã thu hút được sự quan tầm của những nhà toán học chuyên nghiệp lẫn không chuyên. Tuy nhiên, các số Catalan thậm chí tuyệt vời. Nó được ví là giống như “Ngôi sao Bắc cực trong bầu trời đêm”, chúng là ánh sáng tuyệt đẹp và tỏa sáng trong bầu trời toán học. Chúng tiếp tục cung cấp mảnh đất màu mỡ cho các nhà lý thuyết số, đặc biệt là những người đam mê số Catalan và khoa học máy tính. Từ khi xuất bản của Euler về bài toán tam giác phân đa diện lồi (năm 1751) và bài toán dãy dấu ngoặc đơn của Catalan (năm 1838), đã có gần 400 bài báo và các vấn đề về số Catalan đã xuất hiện trong ấn phẩm định kỳ khác nhau. Chúng toát ra vẻ đẹp và tính phổ biến của số Catalan. Nhiều nhà toán học chuyên nghiệp và không chuyên có thể biết dãy Catalan, nhưng có thể không quen với vô số sự xuất hiện bất ngờ, các ứng dụng thiết thực, tính chất, hoặc các mối quan hệ thú vị và đáng ngạc nhiên trong số rất nhiều ví dụ của chúng. Số Catalan được sử dụng trong nhiều lĩnh vực như đại số, số học, hình học, lỹ thuyết đồ thị, .... Xuất phát từ những lí do đó nên tôi mạnh dạn chọn đề tài: “Số Catalan và ứng dụng” dưới sự hướng dẫn của PGS. TS. Đàm Văn Nhỉ. Đây là một bài tổng quan về số Catalan và ứng dụng của nó. Trong luận văn này chúng tôi trình bày lại một vài kết quả chẳng hạn như hàm sinh thường, số Catalan, tam giác Pascal, hệ số tổ hợp, ... Qua đề tài này giúp người đọc hiểu sâu hơn về nguồn gốc và tính chất của số Catalan, 2 thấy được sự phổ biến của số Catalan trong nhiều bài toán đếm khác nhau của toán học. Nôi dung của luận văn gồm hai chương: Chương 1. Kiến thức chuẩn bị. Chương này trình bày có hệ thống các kiến thức cơ sơ, các công cụ hỗ trợ liên tiếp nhau để xây dựng công thức tổng quát của dãy đệ quy bằng phương pháp hàm sinh. Chương 2. Số Catalan. Chương 2 là nội dung chính của luận văn, trong chương này, chúng tôi trình bày đầy đủ tính chất của số Catalan. Một số ứng dụng tiêu biểu của số Catalan bao gồm đếm số cây đồ thị, đếm số phân hoạch không cắt nhau. Mục cuối cùng trình bày nhiều cách khác nhau đều thu được số Catalan từ tam giác Pascal. Luận văn được hoàn thành dưới sự hướng dẫn tận tình của PGS. TS. Đàm Văn Nhỉ. Tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy đã tận tâm truyền đạt kiến thức, giúp đỡ tác giả hoàn thành luận văn này. Trong quá trình học tập và làm luận văn, tác giả nhận được sự quan tâm, giúp đỡ của Khoa Toán, Trường Đại học Khoa học - Đại học Thái Nguyên, các thầy cô đã tham gia giảng dạy lớp cao học Toán K8YB. Tác giả xin chân thành cảm ơn sự giúp đỡ quý báu đó. Thái Nguyên, tháng 6 năm 2016 Học viên Phan Bích Hoài 3 Chương 1 Kiến thức chuẩn bị Chúng tôi bắt đầu luận văn bằng cách trình bày các công cụ cần thiết để xây dựng số Catalan. Dạng tổng quát của số Catalan có thể được xây dựng thông qua phương pháp hàm sinh. Nhưng trước khi bắt đầu với phương pháp hàm sinh, ta cần nhắc lại các định nghĩa về ánh xạ, quy tắc đếm, truy hồi, qui nạp, chuỗi Maclaurin, chuỗi lũy thừa hình thức. Nội dung của chương này được tham khảo trong các tài liệu [1, 2] và nhiều tài liệu khác. 1.1 1.1.1 Quan hệ tương đương và ánh xạ Quan hệ tương đương Giả thiết tập X 6= ∅. Tích Đềcác X × X được định nghĩa như dưới đây: X × X = {(x, y)|x, y ∈ X}. Định nghĩa 1.1.1. Tập con S của X × X được gọi là một quan hệ hai ngôi trong X nếu (x, y) ∈ S, khi đó ta nói x có quan hệ S với y và viết xSy. Định nghĩa 1.1.2. Giả thiết X 6= ∅ và S = 6 ∅ là một quan hệ hai ngôi trong X. Quan hệ S được gọi là một quan hệ tương đương trong X nếu nó thỏa mãn ba điều kiện sau đây: (i) (Phản xạ) Với mọi x ∈ X có xSx. 4 (ii) (Đối xứng) Với mọi x, y ∈ X, nếu có xSy thì cũng có ySx. (iii) (Bắc cầu) Với mọi x, y, z ∈ X, nếu có xSy và ySz thì cũng có xSz. Khi S là một quan hệ tương đương trong X thì ta thường ký hiệu ∼ thay cho S. Đặt C(x) = {y ∈ X|y ∼ x} và gọi nó là một lớp tương đương với x làm đại diện. Dễ dàng chỉ ra các tính chất sau: Tính chất 1.1.3. Giả sử ∼ là quan hệ tương đương trong X 6= ∅. Khi đó (1) Với mọi x ∈ X có x ∈ C(x). (2) Với mọi y, z ∈ C(x) có y ∼ z và y, z ∼ x. (3) Với mọi x, y ∈ X, có hoặc C(x) ∩ C(y) = ∅ hoặc C(x) = C(y). (4) Tập thương X/ ∼ là tập các lớp tương đương không giao nhau. 1.1.2 Ánh xạ và phép toán Giả thiết tập X và tập Y đều khác rỗng. Tích Đềcác X × Y được định nghĩa như sau: X × Y = {(x, y)|x ∈ X, y ∈ Y }. Số phần tử của tập X hữu hạn gọi là lực lượng của X và được ký hiệu bởi |X|. Mệnh đề 1.1.4. Nếu |X| = m và |Y | = n đều là những số hữu hạn thì |X × Y | = |X|.|Y | = mn. Định nghĩa 1.1.5. Một quy tắc f đặt tương ứng mỗi phần tử x ∈ X với một phần tử xác định duy nhất y ∈ Y được gọi là một ánh xạ và được biểu diễn thành f : X → Y, x 7→ y = f (x). Tập X được gọi là tập nguồn hay miền xác định, tập Y được gọi là tập đích hay miền giá trị của ánh xạ f. Phần tử y = f (x) được gọi là ảnh của x và x được gọi là tạo ảnh của y. 5 Định nghĩa 1.1.6. Hai ánh xạ f, g : X → Y được gọi là bằng nhau và được viết f = g nếu f (x) = g(x) với mọi x ∈ X. Ánh xạ id : X → X, x 7→ x, được gọi là ánh xạ đồng nhất. Với tập con A ⊂ X, ánh xạ in : A → X, a 7→ a, được gọi là phép nhúng chìm. Định nghĩa 1.1.7. Ánh xạ f : N → R, n 7→ an = f (n), còn được gọi là một dãy số. Tập tất cả các ảnh an được gọi là dãy (an ) với số hạng thứ n là an . Dãy (an ) được gọi là một cấp số cộng nếu có số cố định d để an+1 = an + d với mọi n ∈ N. Trong trường hợp này d còn được gọi là công sai của cấp số cộng (an ). Định nghĩa 1.1.8. Xét dãy số (an ). Dãy (an ) được gọi là một cấp số nhân nếu có số cố định q để an+1 = an .q với mọi n ∈ N. Trong trường hợp này q còn được gọi là công bội của cấp số nhân (an ). Định nghĩa 1.1.9. Cho hai tập hợp khác rỗng X và Y. Ánh xạ f : X → Y được gọi là một đơn ánh nếu mọi a, b ∈ X, a 6= b thì f (a) 6= f (b). Khi f là một đơn ánh thì ta thường nói rằng, f là ánh xạ 1-1 từ X vào Y. Ánh xạ f : X → Y được gọi là một toàn ánh nếu với mỗi y ∈ Y đều tồn tại x ∈ X để y = f (x). Khi f là một toàn ánh thì ta thường nói rằng, f là ánh xạ từ X lên Y. Chú ý rằng, trong trường hợp này ta có f (X) = Y hay Imf = Y. Định nghĩa 1.1.10. Cho hai tập hợp khác rỗng X và Y. Ánh xạ f : X → Y được gọi là một song ánh nếu f đồng thời vừa là đơn ánh và cũng là toàn ánh. Sự liên quan giữa lực lượng tập hợp và ánh xạ qua các chú ý sau đây: Xét ánh xạ f : X → Y với |X|, |Y | < ∞. Khi đó (1) Nếu f là đơn ánh thì |X| 6 |Y |. (2) Nếu f là toàn ánh thì |X| > |Y |. (3) Nếu f là song ánh thì |X| = |Y |. 6 1.1.3 Nguyên lý Bù-Trừ Khi xét bài toán tổ hợp, ta thường phải đếm xem có bao nhiêu cấu hình có thể tạo ra với những yêu cầu đặt trước. Nói chung, để đếm các cấu hình đã cho người ta tìm cách đưa các cấu hình về loại quen thuộc qua việc phân ra thành các lớp để áp dụng nguyên lý cộng dưới đây: |A ∪ B| = |A| + |B| − |A ∩ B|. Tổng quát nguyên lý cộng ta có Nguyên lý Bù-Trừ. Cái khó của việc vận dụng nguyên lý Bù-Trừ là việc phân lớp như thế nào để dễ dàng có được các số đếm. Giả sử A1 , . . . , An là những tập con của tập A. Các số sk được xác định qua s0 = |A| s1 = |A1 | + |A2 | + · · · + |An | s2 = |A1 ∩ A2 | + |A1 ∩ A3 | + · · · + |An−1 ∩ An | ··· sk = ··· X |Ai1 ∩ Ai2 ∩ · · · ∩ Aik | 16i1 2 giả thiết kết luận đúng cho n − 1 tập. Đặt A = Ai . Theo i=1 công thức (1) ta có | n [ Ai | = |A ∪ An | = |A| + |An | − |A ∩ An |. i=1 Sử dụng giả thiết qui nạp cho |A| và |A∩An | sẽ nhận được công thức. Hệ quả 1.1.12. e0 = s0 −s1 +s2 −· · ·+(−1)n sn ; s0 = e0 +e1 +e2 +· · ·+en . Chứng minh. Hiển nhiên e0 = |A| − | n S Ai | và theo Định lý 1.1.11 ta i=1 nhận được e0 = s0 − s1 + s2 − · · · + (−1)n sn . Vì |A| = |A \ n S i=1 Ai | + | n S Ai | i=1 nên ta nhận được s0 = e0 + e1 + e2 + · · · + en . Ví dụ 1.1.13. Có bao nhiêu số tự nhiên n ∈ A = {1, 2, . . . , 105} có ước chung không tầm thường với số 105. Lời giải. Viết 105 = 3.5.7. Số tự nhiên n có ước chung không tầm thường với số 105 phải chia hết cho hoặc 3 hoặc 5 hoặc 7. Ký hiệu A3 = {3k|k ∈ N} ⊂ A, A5 = {5k|k ∈ N} ⊂ A và A7 = {7k|k ∈ N} ⊂ A. 105 105 105 Ta có |A3 | = [ ] = 35, |A5 | = [ ] = 21, |A7 | = [ ] = 15; và 3 5 7 105 105 105 |A3 ∩ A5 | = [ ] = 7, |A3 ∩ A7 | = [ ] = 5, |A5 ∩ A7 | = [ ] = 3. 15 21 35 105 ] = 1. Số T các số thuộc A có ước chung Tính |A3 ∩ A5 ∩ A7 | = [ 105 không tầm thường với số 105 là T = |A3 ∪ A5 ∪ A7 | = (35 + 21 + 15) − (7 + 5 + 3) + 1 = 57. Vậy T = 57. 8 Ví dụ 1.1.14. Có bao nhiêu số tự nhiên n ∈ [1, 2005] mà không chia hết cho một số nào trong các số 2,3,11,13. Lời giải. Ký hiệu A = {1, 2, . . . , 2005} và Ai là tập con của A gồm tất 2005 cả các số nguyên dương chia hết cho i. Ta có |A2 | = [ ] = 1002, |A3 | = 2 2005 2005 2005 [ ] = 668, |A11 | = [ ] = 182 và |A13 | = [ ] = 154; ta lại có 3 11 13 2005 2005 2005 ] = 334, |A2 ∩A11 | = [ ] = 91, |A2 ∩A13 | = [ ]= |A2 ∩A3 | = [ 6 22 26 2005 2005 77, |A3 ∩ A11 | = [ ] = 60, |A3 ∩ A13 | = [ ] = 51, |A11 ∩ A13 | = 33 39 2005 2005 ] = 14. Tính |A2 ∩ A3 ∩ A11 | = [ ] = 30, |A2 ∩ A3 ∩ A13 | = [ 143 66 2005 2005 2005 [ ] = 25, |A2 ∩ A11 ∩ A13 | = [ ] = 7, |A3 ∩ A11 ∩ A13 | = [ ] = 4, 78 286 429 2005 |A2 ∩ A3 ∩ A11 ∩ A13 | = [ ] = 2. Số T các số thuộc A không chia hết 858 cho 2, 3, 11, 13 là T = |A| − |A2 ∪ A3 ∪ A11 ∪ A13 | = 2005 − (1002 + 668 + 182 + 154) + + (334 + 91 + 77 + 60 + 51 + 14) − (30 + 25 + 7 + 4) + 2 = 562. Vậy T = 562. 1.2 1.2.1 Tổ hợp Phương pháp quy nạp Trước hết ta thừa nhận tiên đề sau: Tiên đề. Tập các số tự nhiên N là một tập sắp thứ tự tốt tức là mỗi tập khác rỗng các số tự nhiên đều có phần tử bé nhất. Dựa vào tiên đề trên, chúng ta có thể chứng minh nguyên lý quy nạp, một nguyên lý hữu hiệu chứng minh tính đúng của các mệnh đề P (n) với mọi số nguyên dương n. Hai kết quả dưới đây đôi khi cũng được gọi là nguyên lý thứ nhất và nguyên lý thứ hai của nguyên lý quy nạp toán học. ? Phương pháp quy nạp thứ nhất: Mệnh đề P (n) là đúng với mọi số tự nhiên n > α nếu 9 (1) Bước cơ sở: Mệnh đề P (α) đúng. (2) Bước quy nạp: Nếu P (n) đúng thì P (n + 1) cũng đúng, trong đó n > α, n ∈ N. Như vậy, sau khi kiểm tra bước cơ sở và chứng minh tính đúng của mệnh đề P (n + 1) dưới giả thiết mệnh đề P (n) đúng, ta kết luận P (n) đúng cho mọi số tự nhiên n > α. ? Phương pháp quy nạp thứ hai: Mệnh đề P (n) là đúng với mọi số tự nhiên n > α nếu (1) Bước cơ sở: Mệnh đề P (α) đúng. (2) Bước quy nạp: Mệnh đề P (n + 1) là đúng khi các mệnh đề P (α), P (α + 1), . . . , P (n) đều đúng, trong đó n > α, n ∈ N. Ví dụ 1.2.1. Cho số nguyên n > 2 và Pn = n!. Chứng minh rằng 2Pn > 2n . Lời giải. Với n = 2 ta có 2P2 = 4 = 22 . Như vậy kết luận đúng cho n = 2. Giả sử kết luận đúng cho n > 2. Khi đó 2Pn > 2n , vậy 2Pn+1 = (n + 1) · 2Pn > (n + 1)2n > 2 · 2n = 2n+1 . Từ đó ta suy ra 2Pn > 2n , ∀ n > 2. Ví dụ 1.2.2. Chứng minh rằng với số nguyên n > 6 ta luôn có n! > 3n . Lời giải. Bởi vì 7! = 5040 > 2189 = 37 nên kết luận đúng cho n = 7. Giả sử kết luận đã đúng với số tự nhiên n với n > 7 tức là n! > 3n . Xét (n + 1)! = n!(n + 1) > 3n (n + 1). Vì n + 1 > 3 nên (n + 1)! > 3n+1 tức mệnh đề đúng với n + 1. Vậy n! > 3n đúng với mọi số nguyên n > 6. Ví dụ 1.2.3. Chứng minh rằng với số nguyên n > 0 ta có đồng nhất thức 1 · 2 + 2 · 22 + · · · + n2n = (n − 1)2n+1 + 2. Lời giải. Với n = 1 ta có 1 · 2 = 2 = (1 − 1)21+1 + 2 và như vậy kết luận bài toán đúng. Giả sử kết luận đúng với n. Khi đó 1·2+2·22 +· · ·+n·2n = (n − 1)2n+1 + 2. Ta nhận được 1 · 2 + 2 · 22 + · · · + n · 2n + (n + 1) · 2n+1 = 10 (n − 1)2n+1 + 2 + (n + 1)2n+1 = n2n+2 + 2 và như thế kết luận cũng đúng với n + 1. Tóm lại, ta có đồng nhất thức 1 · 2 + 2 · 22 + · · · + n · 2n = (n − 1)2n+1 + 2. Ví dụ 1.2.4. Chứng minh rằng với số nguyên n > 0 ta có đồng nhất thức 2 n 1 2n + 3  1 + + ··· + n = 3− . 3 32 3 4 3n 1 1 2 · 1 + 3 Lời giải. Với n = 1 ta có = 3− . Giả sử kết luận đúng 3 4  3 1 2 n 1 2n + 3  3− , điều này suy ra với n. Khi đó + 2 + · · · + n = 3 3 3 4 3n 1 2 n n + 1 1 2n + 3  n + 1 + + · · · + n + n+1 = 3− + n+1 3 32 3 3 4 3n 3  1 2(n + 1) + 3  = 3− 4 3n+1 và như thế kết luận cũng đúng với n + 1. Tóm lại, ta có đồng nhất thức n 1 2 2n + 3  1 + + ··· + n = 3− . 3 32 3 4 3n Ví dụ 1.2.5. Những loại tiền xu nào có thể đổi qua các đồng 5 xu và 7 xu. Chứng minh. Ta thấy ngay 5 = 1.5 + 0.7, 7 = 0.5 + 1.7, 10 = 2.5 + 0.7, 12 = 1.5 + 1.7 14 = 0.5 + 2.7, 15 = 3.5 + 0.7, 17 = 2.5 + 1.7, 20 = 4.5 + 0.7 21 = 0.5 + 3.7, 22 = 3.5 + 1.7, 24 = 2.5 + 2.7, 25 = 5.5 + 0.7 26 = 1.5 + 3.7, 27 = 4.5 + 1.7, 28 = 0.5 + 4.7, 29 = 3.5 + 2.7 19 = 1.5 + 2.7. Giả sử số nguyên n > 30 và có biểu diễn n = r.5 + s.7, r, s ∈ N. Khi đó n + 1 = r.5 + s.7 + 1. 11 Nếu s > 2 thì n + 1 = r.5 + s.7 + 1 = (r + 3).5 + (s − 2).7. Nếu s 6 1 thì r > 4 và n + 1 = r.5 + s.7 + 1 = (r − 4).5 + (s + 3).7. Như vậy, mọi n > 24 (xu) đều đổi được qua hai loại tiền 5 xu và 7 xu và 23 xu là đồng tiền lớn nhất không thể đổi qua 5 xu và 7 xu. Ví dụ 1.2.6 (Italian MO 2007). Giả sử số nguyên n > 2. Xác định giá trị lớn nhất của số thực cn , dn biết rằng bất đẳng thức (1) (2) n P 1 > cn i=1 1 + ai n P 1 > dn i=1 1 + 2ai thỏa mãn cho mọi số thực dương a1 , . . . , an với tích n Q ai = 1. i=1 1 Lời giải. (1) Đặt f (x) = . Theo chứng minh trên có bất đẳng 1+x n n P P 1 n √ n thức f (ai ) > nf ( a1 a2 . . . an ) hay > . Dấu = xảy ra khi 2 i=1 i=1 1 + ai n a1 = a2 = · · · = an = 1. Vậy cn lớn nhất là bằng . 2 1 (2) Đặt g(y) = với y = 2x. Theo chứng minh trên có bất đẳng 1+y n n √ P P 1 n thức g(2ai ) > ng( n 2n a1 a2 . . . an ) hay > . Dấu = xảy ra 3 i=1 1 + 2ai i=1 n khi a1 = a2 = · · · = an = 1. Như vậy dn lớn nhất là bằng . 3 1 Ví dụ 1.2.7 (Ireland 2015). Xét đa thức f (x) = (x2 +1). Giả sử a1 = 3 2 và an+1 = f (an ), n = 1, 2, 3, . . . . Chứng minh n X i=1 1 1 < . 1 + f (ai ) 4 1 = ai+1 − 1 2 2 1 1 1 = = − > 0. Ta nhận được = a2i − 1 (ai − 1)(ai + 1) ai − 1 ai + 1 ai + 1 Lời giải. Hiển nhiên f (an ) > 1 với mọi số nguyên n > 1 và 12 1 1 − , i = 1, . . . , n. Biến đổi ai − 1 ai+1 − 1 n X i=1 n n  X X 1 1 1 1 = = − . 1 + f (ai ) 1 + a a − 1 a − 1 i+1 i+1 i+2 i=1 i=1 n P Do vậy 1 1 1 1 1 = − < = . a2 − 1 an+2 − 1 a2 − 1 4 i=1 1 + f (ai ) 1.2.2 Quy tắc đếm Trước tiên ta giới thiệu hai quy tắc đếm cơ bản sau đây thường được sử dụng: (1) [Quy tắc cộng] Giả sử có s công việc. Việc thứ nhất có thể làm n1 cách, việc thứ hai có thể làm n2 cách,..., việc thứ s có thể làm ns cách và không có hai công việc nào có thể làm đồng thời. Như vậy có n1 + n2 + · · · + ns cách làm s công việc đó. (2) [Quy tắc nhân] Giả sử một việc được chia ra làm s công đoạn. Công đoạn thứ nhất có thể làm n1 cách, công đoạn thứ hai có thể làm n2 cách,..., công đoạn thứ s có thể làm ns cách và công việc hoàn thành khi các công đoạn đều đã xong. Như vậy có n1 .n2 · · · ns cách thực hiện công việc có s công đoạn đó. Quy tắc cộng và quy tắc nhân thường được phát biểu bằng ngôn ngữ tập hợp: Mệnh đề 1.2.8. Giả sử A1 , A2 , . . . , As là những tập hữu hạn phần tử s S rời nhau. Khi đó lực lượng của hợp Ak cho bởi công thức k=1 | s [ k=1 Ak | = s X |Ak |. k=1 Mệnh đề 1.2.9. Giả sử A1 , A2 , . . . , As là những tập hữu hạn phần tử. Khi đó lực lượng của tích Đềcác A1 × A2 × . . . × As được cho bởi công thức s Y |A1 × A2 × . . . × As | = |Ak |. k=1 13 1.2.3 Khái niệm tổ hợp Định nghĩa 1.2.10. Mỗi tập con gồm k phần tử của một tập n phần tử khác nhau được gọi là một tổ hợp chập k của tập n phần tử đó. Ký hiệu số tổ hợp chập k của tập gồm n phần tử khác nhau là Ckn hoặc
n k . Kết quả sau đây là hiển nhiên. Mệnh đề 1.2.11. Số các tổ hợp chập k của một tập gồm n phần tử n! . khác nhau là Ckn = k!(n − k)! k k+1 Dễ dàng kiểm tra C0n = Cnn = 1, Ckn = Cn−k = Ck+1 n , Cn + Cn n+1 . Ví dụ 1.2.12. Chứng minh rằng, với hai số tự nhiên n, k thỏa mãn
2 0 6 k 6 n luôn có bất đẳng thức Cn2n+k . Cn2n−k 6 Cn2n . Lời giải. Với k = 0, bất đẳng thức trên hiển nhiên đúng. Với k > 0 ta sẽ chỉ ra Cn2n+k . Cn2n−k 6 Cn2n+k−1 . Cn2n−k+1 . Bất đẳng thức này tương đương (2n + k)! (2n − k)! (2n + k − 1)! (2n − k + 1)! . 6 . n!(n + k)! n!(n − k)! n!(n + k − 1)! n!(n − k + 1)! hay 1 1 6 : đúng. Vậy n+k n+k−1 Cn2n+k . Cn2n−k 6 Cn2n+k−1 . Cn2n−k+1
2 và từ đây suy ra Cn2n+k . Cn2n−k 6 · · · 6 Cn2n . 1.3 Khai triển (x1 + x2 + · · · + xk )n Mệnh đề 1.3.1 (Newton). Công thức khai triển lũy thừa (x + y)n như sau: n   X n r n−r n (x + y) = xy . r r=0 Chứng minh. Ta chứng minh kết quả bằng phương pháp qui nạp theo n. Với n = 0, 1 công thức hiển nhiên đúng. Giả sử công thức đúng với 14 n. Ta chỉ ra nó đúng với n + 1. Thật vậy, theo giả thiết quy nạp ta có biến đổi: n hX i r r n−r n+1 n (x + y) = (x + y) (x + y) = Cn x y (x + y) = n X Crn xr+1 y n−r + r=0 = r=0 n X Crn xr y n−r+1 r=0 C0n y n+1 + ··· + h + h C0n + C1n Cn−1 + Cnn n i i n n xy + x y+ h C1n + C2n Cnn xn+1 = i x2 y n−1 n+1 X Crn+1 xr y n+1−r . r=0 n+1 Từ đó suy ra (x + y) = n+1 P Crn+1 xr y n+1−r . Vậy ta suy ra công thức r=0 đúng với n + 1. Tóm lại, công thức đúng với mọi số nguyên không âm n.
Sự xuất hiện của các con số nk trong định lý này là nguồn gốc của tên của chúng: hệ số nhị thức. Định lý 1.3.2 (Định lý đa thức). Nếu n là một số nguyên không âm, thì  X n (x1 + x2 + · · · + xk )n = x1r1 xr22 · · · xrkk , (1.1) r1 , r2 , . . . , rk trong đó tổng lấy trên tất cả các nghiệm không âm của phương trình r1 + r2 + · · · + rk = n, và   n n! . = r1 !r2 ! · · · rk ! r1 , r2 , . . . , rk Ví dụ 1.3.3. Ta không nhất thiết phải tính tất cả 510 = 9765625 phép nhân trong khai triển của (a+b+c+d+e)10 chỉ để xác định hệ số của a4 d6 !
10! 10! 10 Từ định lý khai triển đa thức, 4,0,0,6,0 = = = 210. Lưu ý 4!0!0!6!0! 4!6!
4 6 10 rằng 210 = 10 4 cũng là hệ số của a d trong (a + d) , như trong định lý nhị thức Newton. Đặt b = c = e = 0 trong (a + b + c + d + e)10 không ảnh

10 10 hưởng đến hệ số của a4 d6 . Ngoài ra, lưu ý rằng 4,0,0,6,0 = 0,0,6,0,4 . Nên hệ số của c6 e4 cũng bằng 210, kéo theo tính đối xứng của (a+b+c+d+e)10 . 15 Tính hữu ích của định lý đa thức không chỉ giới hạn trong việc chọn ra các hệ số đơn. Ví dụ khai triển của tất cả 34 = 81 số hạng của (x+y +z)4 sẽ có dạng     4 4 4 2 xz 3 + · · · + z 4 . x + ··· + xy z + · · · + 1, 2, 1 1, 0, 3 Từ định lý đa thức, ta có thể suy ra được nhiều đẳng thức bằng cách thay các giá trị biến khác nhau trong định lý đa thức. Đặt x = y = z = 1
P n trong (x + y + z)n , thu được 3n = r+s+t=n r,s,t . Định lý đa thức cho ta biết rằng xr11 xr22 · · · xrkk xuất hiện trong số k n
tích trong khai triển của (x1 + x2 + · · · + xk )n với bội r1 ,r2n,...,rk , nhưng điều này không cho ta biết có bao nhiêu số hạng đơn thức khác nhau có
dạng r1 ,r2n,...,rk xr11 xr22 · · · xkrk xuất hiện trong khai triển. Định lý 1.3.4. Số đơn thức khác nhau bậc n có k biến x1 , x2 , . . . , xk là
n+k−1 . n
Chứng minh. Do phương trình r1 + r2 + · · · + rk = n có đúng n+k−1 n nghiệm nguyên không âm. 1.4 Chuỗi Taylor-Maclaurin Định nghĩa 1.4.1. Cho hàm f khả vi đến cấp (n + 1) tại a ∈ X tức là f ∈ C n tại lân cận của a và có đạo hàm cấp n + 1 tại a. Gọi đa thức Pn (x) với deg Pn (x) ≤ n thỏa mãn điều kiện Pn(k) (a) = f (k) (a) k = 0, 1, . . . , n là đa thức Taylor của f (x) tại lân cận điểm a, hay là phần chính qui của khai triển hữu hạn bậc n của a tại f (x). Định nghĩa 1.4.2. Nếu a = 0 thì Pn (x) gọi là đa thức Maclaurin của f (x). Định lý 1.4.3. Nếu Pn (x) là đa thức Taylor của f (x) tại lân cận của a thì nó là duy nhất và có dạng Pn (x) = f (a) + f 0 (a) f (n) (a) (x − a) + · · · + (x − a)n . 1! n! 16 Chứng minh. Giả sử tồn tại đa thức thứ hai là Qn (x) khi đó hiệu Pn (x) − Qn (x) là đa thức có bậc không vượt quá n và có nghiệm x = a bội n + 1 chứng tỏ Pn (x) = Qn (x). Đặt Pn (x) = A0 + A1 (x − a) + · · · + An (x − a)n Pn(k) (a) = k!Ak = f Chứng tỏ Pn (x) = (k) f (k) (a) (a) ⇒ Ak = k! n X f (k) (a) k=0 k! (k = 0, 1, . . . , n). (x − a)n . Cho Pn (x) là đa thức Taylor của f (x) tại lân cận của a. Gọi rn (x) = f (x) − Pn (x) là phần dư Taylor bậc n tại a của f (x). Hệ quả 1.4.4. Phần dư rn (x) có dạng f (n+1) (c) rn (x) = (x − a)n+1 với c ∈ (a, x), (n + 1)! hay c = a + θ(x − a), 0 < θ < 1, gọi phần dư trong dạng Langrange. (n) Chứng minh. Rõ ràng rn (a) = rn0 (a) = · · · = rn (a) = 0. Đặt G(x) = (x − a)n+1 thì G(a) = G0 (a) = · · · = G(n) (a) = 0 và G(n+1) (a) = (n + 1)!. Với x 6= a và x ∈ Ωδ (a), theo định lý Cauchy sẽ có rn0 (c1 ) rn (x) rn (x) − rn (a) = = 0 , c1 ∈ (a, x) G(x) G(x) − G(a) G (c1 ) rn0 (x) rn0 (x) − rn0 (a) rn00 (c1 ) = = , c2 ∈ (a, c1 ) G0 (x) G0 (x) − G0 (a) G00 (c1 ) Sau (n + 1) lần áp dụng định lý Cauchy, kết quả sẽ là (n+1) rn (x) rn (c) = (n+1) với c ∈ (a, cn ) ⊂ (a, cn−1 ) ⊂ · · · ⊂ (a, x) G(x) G (c) (n+1) mà rn (c) = f (n+1) (c), G(n+1) (c) = (n + 1)!. Suy ra f (n+1) (c) rn (x) = (x − a)n+1 (n + 1)! 17 Định nghĩa 1.4.5. Gọi công thức f (x) = n X f (k) (a) k=0 k! f (n+1) (a + θ(x − a)) (x − a) + (x − a)n+1 (n + 1)! k là công thức Taylor bậc n, hay khai triển hữu hạn bậc n hàm f (x) tại lân cận của a. Định nghĩa 1.4.6. Gọi công thức f (x) = n X f (k) (0) k=0 k! f (n+1) (θx) n+1 (x) + (x) (n + 1)! k là công thức Maclaurin bậc n, hay khai triển hữu hạn bậc n hàm f (x) tại lân cận của 0. Nếu f (n+1) bị chặn trong lân cận của a thì rõ ràng rn (x) = (x − a)n f (n+1) (c) (x − a) dần đến 0 khi x → a nghĩa là rn (x) = o((x − a)n ). (n + 1)! Với giả thiết f (n+1) bị chặn trong lân cận của a thì có thể lấy gần đúng f (x) ở lân cận của a bằng đa thức Pn (x) với sai số là rn (x) = O((x−a)n ). Ví dụ 1.4.7. Tìm khai triển Maclaurin của hàm f (x) = (1 + x)α , α ∈ R, x ∈ X, X phụ thuộc α. Với x ở lân cận của 0 thì f ∈ C ∞ . f (k) (x) = α(α − 1) · · · (α − k + 1)(1 + x)α−k f (k) (0) = α(α − 1) · · · (α − k + 1). Suy ra (1+x)α = 1+αx+α(α−1) x2 xn +. . .+α(α−1) · · · (α−n+1) +· · · 2 n!