Tài liệu ứng dụng hàm sinh trong tổ hợp

Header Page 1 of 161. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Đinh Thị Hiền ỨNG DỤNG HÀM SINH TRONG TỔ HỢP KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Hà Nội – Năm 2016 Footer Page 1 of 161. Header Page 2 of 161. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Đinh Thị Hiền ỨNG DỤNG HÀM SINH TRONG TỔ HỢP Chuyên ngành: Toán ứng dụng Mã số: KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. TRẦN VĨNH ĐỨC Hà Nội – Năm 2016 Footer Page 2 of 161. Header Page 3 of 161. LỜI CẢM ƠN Trước khi trình bày nội dung chính của bản khóa luận, em xin bày tỏ lòng biết ơn sâu sắc tới Tiến sĩ Trần Vĩnh Đức đã tận tình hướng dẫn để em có thể hoàn thành đề tài này. Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Toán, Trường Đại học Sư phạm Hà Nội 2 đã dạy bảo em tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện đề tài thực tập này. Hà Nội, ngày tháng 05 năm 2016 Sinh viên Đinh Thị Hiền Footer Page 3 of 161. Header Page 4 of 161. LỜI CAM ĐOAN Em xin cam đoan, dưới sự hướng dẫn của TS. Trần Vĩnh Đức đề tài "Ứng dụng hàm sinh trong tổ hợp" được hoàn thành không trùng với bất kỳ đề tài nào khác. Trong quá trình hoàn thành đề tài, em đã thừa kế những thành tựu của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, tháng 05 năm 2016 Sinh viên Đinh Thị Hiền Footer Page 4 of 161. Header Page 5 of 161. Mục lục Lời mở đầu 1 1 Hàm sinh 4 1.1 Ứng dụng của đa thức trong tổ hợp . . . . . . . . . . . . 4 1.2 Chuỗi lũy thừa . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Một số phép toán với dãy và hàm sinh của chúng . . . . 14 1.5 Tính hệ số của hàm sinh . . . . . . . . . . . . . . . . . . 21 1.6 Hàm sinh mũ . . . . . . . . . . . . . . . . . . . . . . . . 24 2 Ứng dụng của hàm sinh trong tổ hợp 3 26 2.1 Dùng hàm sinh là đa thức . . . . . . . . . . . . . . . . . 26 2.2 Dùng hàm sinh là các chuỗi lũy thừa vô hạn . . . . . . . 29 2.3 Số Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4 Số Catalan . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5 Công thức truy hồi và hàm sinh . . . . . . . . . . . . . . 37 2.6 Đếm bằng hàm sinh . . . . . . . . . . . . . . . . . . . . 39 Một số ví dụ điển hình 46 i Footer Page 5 of 161. Header Page 6 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền Kết luận 57 Tài liệu tham khảo 58 ii Footer Page 6 of 161. Header Page 7 of 161. Lời mở đầu 1. Lý do chọn đề tài Một đặc trưng của các bài toán tổ hợp là số cấu hình phải xem xét thường rất lớn. Và vì thế việc giải quyết chúng đòi hỏi một khối lượng tính toán khổng lồ. Trong thời gian khá dài, khi mà các ngành toán học như phép tính vi phân, phép tích phân, phương trình vi phân,. . . phát triển như vũ bão, thì dường như tổ hợp nằm ngoài sự phát triển và ứng dụng của toán học. Lý thuyết tổ hợp thực sự phát triển nhanh khi xuất hiện máy tính điện tử. Các phương pháp của tổ hợp rất phù hợp cho hướng giải quyết các bài toán trên máy tính. Các bài toán tổ hợp có thể được giải quyết bằng nhiều phương pháp, ví dụ như • Phương pháp sử dụng nguyên lí bù trừ. • Phương pháp song ánh. • Phương pháp hàm sinh. • Phương pháp quỹ đạo. Trong số các phương pháp trên, mỗi phương pháp đều có ưu, nhược điểm riêng. Phương pháp hàm sinh có ưu điểm tổng quát, có thể ứng dụng cho nhiều lớp bài toán. Có thể nói, hàm sinh là một trong những Footer Page 7 of 161. Header Page 8 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền phương pháp bất ngờ, tổng quát, và hữu hiệu nhất để giải quyết các bài toán tổ hợp phức tạp. Với mong muốn tìm hiểu sâu hơn vấn đề này dưới góc độ của một sinh viên sư phạm Toán cùng sự hướng dẫn tận tình của thầy giáo - TS. Trần Vĩnh Đức, em xin mạnh dạn trình bày hiểu biết của mình về đề tài: “ Ứng dụng hàm sinh trong tổ hợp” 2. Mục đích nghiên cứu Nghiên cứu lý thuyết về tổ hợp và lý thuyết hàm sinh. Từ đó nhằm hệ thống các phương pháp giải các bài toán tổ hợp bằng phương pháp hàm sinh và ứng dụng của nó vào nghiên cứu, học tập cũng như trong thực tiễn. Việc thực hiện đề tài này đã giúp em bước đầu làm quen với công việc nghiên cứu khoa học và tìm hiểu sâu sắc hơn về Toán rời rạc. 3. Nhiệm vụ nghiên cứu Nhiệm vụ của đề tài này là nghiên cứu về lý thuyết hàm sinh, công thức truy hồi, chuỗi lũy thừa,. . . . Từ đó đưa ra hệ thống các phương pháp và những ứng dụng điển hình của hàm sinh trong giải các bài toán tổ hợp. 4. Đối tượng và phạm vi nghiên cứu Hàm sinh và ứng dụng hàm sinh trong tổ hợp. Footer Page 8 of 161. 2 Header Page 9 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền 5. Phương pháp nghiên cứu Đọc, dịch, và tổng hợp tài liệu. 6. Cấu trúc đề tài Nội dung của khóa luận chủ yếu được dịch và tổng hợp từ chương 12 của cuốn sách: • Jiri Matousek và Jaroslav Nesetril (2008), Invitation to Discrete Mathematics, 2nd edition, Oxford University Press. Ngoài phần mở đầu, kết luận, danh mục tài liệu tham khảo, khóa luận bao gồm 3 chương: • Chương 1: Hàm sinh. • Chương 2: Ứng dụng hàm sinh trong tổ hợp. • Chương 3: Một số ví dụ điển hình. Footer Page 9 of 161. 3 Header Page 10 of 161. Chương 1 Hàm sinh Chương này bắt đầu xem xét ứng dụng của đa thức và chuỗi lũy thừa hình thức trong các bài toán tổ hợp. Sau đó, chúng ta định nghĩa hàm sinh, rút ra một vài kết quả cơ bản, và sử dụng chúng để giải một số bài toán đếm. 1.1 Ứng dụng của đa thức trong tổ hợp Làm thế nào để chúng ta nhân các đa thức p (x) = x + x2 + x3 + x4 và q (x) = x + x3 + x4 ? Quy tắc thật là đơn giản! Nhân từng số hạng của p (x) với từng số hạng của q (x) và cộng tất cả các tích này lại với nhau. Cộng các tích trong trường hợp này rất đơn giản vì tất cả các tích đó đều có hệ số 1. Trong cách này, ta tính toán được: p (x) q (x) = x8 + 2x7 + 2x6 + 3x5 + 2x4 + x3 + x2 . Bây giờ chúng ta sẽ đặt một câu hỏi khác. Chúng ta chọn một lũy thừa của x, ví dụ x5 , và muốn biết hệ số của nó trong p (x) q (x), mà Footer Page 10 of 161. 4 Header Page 11 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền không cần nhân hai đa thức. Trong trường hợp này, x5 xuất hiện do 1. nhân x trong p (x) với x4 trong q(x), 2. hoặc bằng cách nhân x2 trong p (x) với x3 trong q (x), 3. hoặc bằng cách nhân x4 trong p (x) với x trong q (x). Với mỗi một khả năng, ta cộng thêm 1 vào hệ số kết quả, và do đó hệ số của x5 trong tích p (x) q (x) là 3. Giả sử chúng ta có 4 đồng bạc có giá trị 1, 2 , 3 và 4 đồng (đây là các số mũ của x trong đa thức p (x)), và 3 đồng vàng với giá trị 1, 3, và 4 đồng. Có bao nhiêu cách trả lại 5 đồng dùng một đồng bạc và một đồng vàng? Một cách toán học, hệ số của x5 là số cặp có thứ tự (i, j) thỏa mãn i+j =5 i ∈ {1, 2, 3, 4} j ∈ {1, 3, 4} Chúng ta hãy chỉ quan tâm đến xây dựng hai đa thức đặc biệt. Cho I và J là tập hữu hạn số tự nhiên. Chúng ta hãy hình thành các đa thức ∑ ∑ p (x) = i∈I xi và q (x) = j∈J xj (lưu ý rằng các hệ số trong đa thức đó là 0 và 1). Sau đó, đối với bất kỳ số r tự nhiên, số lượng các khả năng (i, j) của phương trình i+j =r với i ∈ I và j ∈ J bằng hệ số của xr trong tích số p (x) q (x). Footer Page 11 of 161. 5 Header Page 12 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền Khái quát từ bài toán trên, chúng ta có thể xem xét kết quả của tích 3 đa thức hoặc thậm chí nhiều hơn. Để minh họa, chúng ta đi vào ví dụ đầu tiên. Ví dụ 1.1. Có bao nhiêu cách trả lại 10 đồng nếu ta chỉ có 4 tờ một đồng, 3 tờ hai đồng, và 2 tờ 5 đồng? Giải. Đây chính là số nghiệm nguyên của phương trình i1 + i2 + i3 = 10 thỏa mãn i1 ∈ {0, 1, 2, 3, 4} , i2 ∈ {0, 2, 4, 6} , i3 ∈ {0, 5, 10} . Ở đây, i1 , i2 , i3 tương ứng là tổng số tiền 1 đồng, 2 đồng và 5 đồng cần trả lại. Ta khẳng định rằng số nghiệm của phương trình này cũng chính là hệ số x10 của đa thức ( 1 + x + x2 + x3 + x 4 )( 1 + x2 + x4 + x6 )( ) 1 + x5 + x10 . Thật vậy, hệ số của x10 được tính từ tích của xi1 trong dấu ngoặc đầu tiên, xi2 trong dấu ngoặc thứ hai, và xi3 trong dấu ngoặc thứ ba sao cho xi1 .xi2 .xi3 = xi1 +i2 +i3 = x10 . Đẳng thức này tương đương với i1 + i2 + i3 = 10. Nhân đa thức ta tìm được hệ số của x10 là 4. Footer Page 12 of 161. 6 Header Page 13 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền Ví dụ 1.2. Chứng minh rằng ( ) ( ) ( ) ( ) n n n n n (1 + x)n = + x+ x2 + . . . + x . 0 1 2 n Giải. Vế trái của công thức trên chính là tích của n đa thức (1 + x). Tương tự như trong Ví dụ 1.1, hệ số của xr của vế trái chính là số nghiệm của phương trình i1 + i2 + . . . + in = r với i1 , i2 , . . . , in ∈ {0, 1}. Đây chính là số cách chọn r phần tử từ tập n ( ) phần tử {i1 , . . . , in } để gán số 1. Số này bằng nr . Hai ví dụ sau đây nhằm chỉ ra tính hiệu quả của việc sử dụng đa thức trong chứng minh đẳng thức tổ hợp. Ví dụ 1.3. Chứng minh rằng n2n−1 ( ) ( ) ( ) ( ) n n n n = +2 +3 + ... + n . 1 2 3 n Giải. Lấy đạo hàm cả hai vế của của công thức trong Ví dụ 1.2, ta được n(1 + x)n−1 ( ) ( ) ( ) ( ) n n n n . + . . . + nxn−1 + 3x2 + 2x = n 3 2 1 Thay x = 1, ta được công thức cần chứng minh. Ví dụ 1.4. Chứng minh rằng ( )2 ( ) ( )2 ( )2 2n n n n . = + ... + + n n 1 0 Footer Page 13 of 161. 7 Header Page 14 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền Giải. Xét đẳng thức (1 + x)n (1 + x)n = (1 + x)2n . • Với vế phải, hệ số của xn theo công thức nhị thức là (2n) n . • Với vế trái, ta khai triển hai đa thức (1 + x)n theo công thức nhị thức rồi nhân lại với nhau. Hệ số xn trong tích này là ( )( ) ( )( ) ( )( ) n n n n n n + + ... + . 0 n 1 n−1 n 0 Vậy đẳng thức được chứng minh. Một số các bài toán và các công thức khác có thể được làm tương tự. Nhưng nếu chúng ta thử một số tính toán phức tạp hơn, chúng ta sẽ sớm gặp phải hạn chế, trên thực tế là chúng ta đã xét với đa thức chỉ có hữu hạn số hạng, nhưng còn với trường hợp vô hạn lũy thừa của x. 1.2 Chuỗi lũy thừa Chúng ta cùng nhắc tới một số lý thuyết về chuỗi lũy thừa vô hạn. Định nghĩa 1.1. Một chuỗi lũy thừa là chuỗi vô hạn có dạng a0 + a1 x + a2 x2 + · · · với a0 , a1 , a2 , . . . là các số thực và x là một biến thực. Chuỗi lũy thừa như vậy sẽ thường được kí hiệu bằng a (x). Footer Page 14 of 161. 8 Header Page 15 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền Ví dụ 1.5. Chuỗi lũy thừa 1 + x + x2 + x 3 + · · · là chuỗi với tất cả các hệ số ai đều bằng 1. Nếu x là một số thực trong khoảng (−1, 1), khi đó chuỗi này hội tụ và tổng của nó bằng 1/(1 − x). Như vậy chuỗi lũy thừa trên xác định hàm số 1/(1 − x). Và ngược lại, hàm số này chứa tất cả các thông tin về chuỗi. Thật vây, chuỗi lũy thừa trên là chuỗi Taylor của hàm 1/(1 − x) tại x = 0. Do đó, hàm số 1/(1 − x) có thể được hiểu như là một hóa thân của dãy vô hạn (1, 1, 1, . . .) và ngược lại. Sự chuyển đổi của dãy vô hạn thành hàm số và ngược lại là một bước quan trọng trong phương pháp hàm sinh. Mệnh đề sau đây nói rằng nếu các số hạng của dãy (a0 , a1 , a2 , . . .) không tăng quá nhanh thì chuỗi lũy thừa tương ứng a (x) = a0 + a1 x + a2 x2 + . . . định nghĩa một hàm của biến thực x, ít nhất là trong một số lân cận nhỏ của 0. Hơn nữa, từ những hiểu biết về các giá trị của hàm số này, chúng ta có thể xây dựng lại dãy (a0 , a1 , a2 , . . .) một cách duy nhất. Mệnh đề 1.1. Cho (a0 , a1 , a2 , . . .) là một dãy các số thực và giả sử rằng với một số số thực K, ta có |an | ≤ K n với mọi n ≥ 1. Khi đó, với ( ) ∑ i mọi x ∈ − K1 , K1 , chuỗi a (x) = ∞ i=0 ai x hội tụ, và do đó giá trị của tổng trên định nghĩa một hàm biến số thực x trong khoảng này. Hàm số này cũng được ký hiệu bởi a (x). Các giá trị của hàm số a (x) trong lân cận của 0 xác định tất cả các số hạng của dãy a0 , a1 , a2 , . . . một cách duy nhất. Nghĩa là, hàm số a (x) có đạo hàm mọi cấp 0, và với n = 0, 1, 2, . . ., Footer Page 15 of 161. 9 Header Page 16 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền ta có: a(n) (0) an = n! (với a(n) (0) là đạo hàm cấp n của hàm a (x) tại điểm 0). 1.3 Hàm sinh Hàm sinh là một trong những sáng tạo thần tình, bất ngờ, nhiều ứng dụng của Toán rời rạc. Nói một cách nôm na, hàm sinh chuyển những bài toán về dãy số thành những bài toán về hàm số. Điều này là rất tuyệt vời vì chúng ta có trong tay một rất nhiều công cụ làm việc với các hàm số. Bằng cách này, chúng ta có thể sử dụng hàm sinh trong việc giải các dạng toán về phép đếm. Trong phần này, các dãy số sẽ được để trong dấu ngoặc ⟨⟩ để phân biệt với các đối tượng toán học khác. Định nghĩa 1.2. Cho ⟨go , g1 , g2 , · · ·⟩ là một dãy các số thực. Hàm sinh của dãy số ⟨go , g1 , g2 , · · ·⟩ là chuỗi lũy thừa vô hạn G (x) = g0 + g1 x + g2 x2 + · · · . Ta sử dụng kí hiệu mũi tên hai phía để chỉ tương ứng giữa một dãy số và hàm sinh của nó như sau: ⟨go , g1 , g2 , · · ·⟩ ←→ g0 + g1 x + g2 x 2 + · · · . Ví dụ, dưới đây là một vài dãy số và hàm sinh của chúng ⟨0, 0, 0, 0, · · ·⟩ Footer Page 16 of 161. ←→ 0 + 0x + 0x2 + 0x3 + · · · = 0 10 Header Page 17 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền ⟨1, 0, 0, 0, · · ·⟩ ←→ 1 + 0x + 0x2 + 0x3 + · · · = 1 ⟨3, 2, 1, 0, · · ·⟩ ←→ 3 + 2x + 1x2 + 0x3 + · · · = 3 + 2x + x2 . Qui tắc ở đây rất đơn giản: Số hạng thứ i của dãy số (đánh số từ 0) là hệ số của xi trong hàm sinh. Ở ví dụ trên, các dãy số chỉ có một số hữu hạn số khác 0 nên hàm sinh của nó là một đa thức. Nhưng đối với dãy có vô hạn số khác 0, liệu ta có thể tìm được một công thức đóng cho chúng? Xây dựng hàm sinh: Trong các bài tập về hàm sinh, chúng sẽ gặp ( ) những câu hỏi như “tìm hàm sinh của dãy 1, 12 , 13 , 41 , ... ? ” Tất nhiên, theo định nghĩa hàm sinh là 1 + 12 x + 31 x2 + 14 x3 + ... , nhưng công thức đóng của nó là gì? Nói cách khác, liệu dãy lũy thừa này có xác định một số hàm số nào không? Câu trả lời thường có thể được tìm thấy bằng cách một quá trình “lắp ráp”, giống như trong một nhà xưởng. Ta có một nguồn cung cấp các bộ phận, trong trường hợp này các dãy như (1, 1, 1, . . .) mà ngay lập tức biết hàm sinh của nó. Chúng ta có các phép tính đơn giản trên dãy và các phép toán tương ứng của chúng trên các hàm sinh. Chẳng hạn như, biết hàm sinh a (x) của dãy (a0 , a1 , a2 , . . .) thì hàm sinh của dãy (0, a0 , a1 , a2 , . . .) bằng xa (x). Với một số kỹ năng, ta có thể “lắp ráp” các dãy ta muốn. Chúng ta hãy bắt đầu với một nguồn cung cấp của các “bộ phận”. Các ví dụ khác nhau của chuỗi Taylor (hay Maclaurin) đề cập trong các giờ học giải tích thuộc nguồn cung cấp như thế. Ví dụ, ta có x x 2 x3 + + + · · · = − ln (1 − x) 1 2 3 Footer Page 17 of 161. 11 Header Page 18 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền (đúng với mọi x ∈ (−1, 1)) và 1+ x x2 x3 + + + · · · = ex 1 2 3 (đúng với mọi số thực x). Rất nhiều ví dụ có thể được tìm thấy trong phép tính ở sách giáo khoa. Từ đó, ta tìm hiểu ví dụ sau. Ví dụ 1.6. Hãy tìm công thức đóng cho hàm sinh của dãy số ⟨1, 1, 1, · · ·⟩. Giải. Giải. Đặt G (x) = 1 + x + x2 + x2 + · · · . Từ đó, suy ra xG (x) = x + x2 + x3 + x4 + · · · . Ta có G (x) − xG (x) = (1 + x + · · · + xn + · · ·) − (x + · · · + xn + · · ·) = 1 + (x − x) + · · · + (xn − xn ) + · · · =1 Chia cả hai vế cho 1 − x, ta được công thức đóng cho G (x) G (x) = 1 . 1−x Nói cách khác, ta có ⟨1, 1, 1, · · ·⟩ ←→ 1 . 1−x 1 + x + x2 + x3 + · · · = 1/(1 − x) cũng chính là công thức tính tổng của cấp số nhân lùi vô hạn. Footer Page 18 of 161. 12 Header Page 19 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền Công thức trên cho chúng ta công thức tường minh cho hàm sinh của hàng loạt dãy số: ⟨1, 1, 1, 1, · · ·⟩ ←→ 1 + x + x2 + x3 + · · · = 1/(1 − x) ⟨1, −1, 1, −1, · · ·⟩ ←→ 1 − x + x2 − x3 + · · · = 1/(1 + x) ⟨ ⟩ 1, a, a2 , a3 , · · · ←→ 1 + a.x + a2 .x2 + a3 .x3 + · · · = 1/(1 − ax) /( ) ⟨1, 0, 1, 0, · · ·⟩ ←→ 1 + x2 + x3 + x4 + · · · = 1 1 − x2 . Định lý 1.1 (Công thức nhị thức tổng quát). Cho một số thực r tùy ý và số nguyên không âm k bất kì, ta định nghĩa hệ số nhị thức (rk ) theo công thức: ( ) r r(r − 1)(r − 2) . . . (r − k + 1) = . k k! () () () (đặt 0r = 1). Khi đó, hàm số (1 + x)r là hàm sinh của dãy 0r , 1r , (r ) 2 ,. . . Chuỗi lũy thừa (r ) 0 + (r ) (r ) 2 x + 1 2 x + · · · luôn hội tụ với |x| < 1. Với các ứng dụng tổ hợp, cần lưu ý rằng với r là một số nguyên âm, các hệ () số nhị thức kr có thể được biểu diễn bằng cách sử dụng hệ số nhị thức “thông thường” (chỉ liên quan đến số nguyên không âm): ) ) ( ( ( ) r k −r + k − 1 k −r + k − 1 . = (−1) = (−1) −r − 1 k k Do đó cho lũy thừa nguyên âm 1 − x ta thu được: 1 = (1 − x)n ( ) ( ) ( ) ( ) n−1 n n+1 2 n+k−1 k + x+ x +· · ·+ x +· · · . n−1 n−1 n−1 n−1 / Lưu ý rằng phương trình 1 (1 − x) = 1 + x + x2 + · · · là một trường hợp Footer Page 19 of 161. 13 Header Page 20 of 161. Khóa luận tốt nghiệp Đại học Đinh Thị Hiền đặc biệt cho n = 1. 1.4 Một số phép toán với dãy và hàm sinh của chúng Phép màu của hàm sinh nằm ở chỗ ta có thể chuyển các phép toán thực hiện trên dãy số thành các phép toán thực hiện trên hàm sinh tương ứng của chúng. Từ đó ta có thể dễ dàng thực hiện các phép toán. Xét hai dãy số và hàm sinh tương ứng của chúng như sau: ⟨f0, f1 , f2 , . . .⟩ ←→ F (x) , ⟨g0, g1 , g2 , . . .⟩ ←→ G (x) . Dưới đây là một số phép toán quan trọng trên các dãy số và hàm sinh tương ứng. a. Phép cộng: Cộng hai hàm sinh tương ứng với việc cộng các số hạng của dãy số theo đúng chỉ số. ⟨f0 + g0 , f1 + g1 , f2 + g2 , · · ·⟩ ←→ F (x) + G (x) Chứng minh. Ta có ⟨f0 + g0 , f1 + g1 , · · ·⟩ ←→ (f0 + g0 ) + (f1 + g1 ) x + · · · = (f0 + f1 x + · · ·) + (g0 + g1 x + · · ·) = F (x) + G (x) . Footer Page 20 of 161. 14