Bài toán đếm nâng cao trong tổ hợp và ứng dụng

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRƯƠNG NHẬT LÝ BÀI TỐN ĐẾM NÂNG CAO TRONG TỔ HỢP VÀ ỨNG DỤNG Chuyên ngành: PHƯƠNG PHÁP TỐN SƠ CẤP Mã số: 60.46.40 TĨM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng – Năm 2011 2 Cơng trình được hồn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS.TSKH. TRẦN QUỐC CHIẾN Phản biện 1: Phản biện 2: Luận văn được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp Thạc sĩ Khoa học, họp tại Đại học Đà Nẵng vào 22 ngày tháng 10 năm 2011 Cĩ thể tìm hiểu luận văn tại: - Trung tâm Thơng tin – Học liệu, Đại học Đà Nẵng - Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng 3 MỞ ĐẦU 1. LÝ DO CHỌN ĐỀ TÀI Tổ hợp cĩ vị trí đặc biệt trong tốn học khơng chỉ như là những đối tượng để nghiên cứu mà cịn đĩng vai trị như một cơng cụ đắc lực của các mơ hình rời rạc của giải tích, đại số, ... Các bài tốn tổ hợp ngày càng chiếm một vị trí quan trọng trong các kỳ thi olympic, vơ địch tốn ... Tốn tổ hợp là một dạng tốn khĩ, địi hỏi tư duy lơgic, tư duy thuật tốn cao, tính hình tượng tốt, phù hợp với mục đích tuyển chọn học sinh cĩ khả năng và năng khiếu tốn học. Hơn nữa, nội dung các bài tốn kiểu này ngày càng gần với thực tế cuộc sống chúng ta, và điều đĩ hồn tồn phù hợp với xu hướng của tốn học hiện đại. Chính vì những lý do trên, chúng tơi đã nghiên cứu và chọn đề tài “Bài tốn đếm nâng cao trong tổ hợp và ứng dụng” nhằm hệ thống các phương pháp giải đồng thời nâng cao hơn nữa nhận thức và ứng dụng của nĩ trong học tập, nghiên cứu và cơng tác sau này. 2. MỤC ĐÍCH NGHIÊN CỨU Nghiên cứu lý thuyết về lý thuyết tổ hợp và từ đĩ nhằm hệ thống các phương pháp giải bài tốn đếm 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. Đề tài cũng được làm tài liệu tham khảo cho học sinh, sinh viên đại học và cao đẳng, học viên cao học, thi học sinh giỏi cấp quốc gia, quốc tế và những ai quan tâm đến lý thuyết tổ hợp. 3. NHIỆM VỤ NGHIÊN CỨU Nhiệm vụ của đề tài này là nghiên cứu về các cấu hình tổ hợp từ cơ bản đến nâng cao, nguyên lý bù trừ, lý thuyết về hàm sinh, cơng thức truy hồi... Từ đĩ đưa ra được hệ thống các phương pháp và ứng dụng điển hình của bài tốn đếm nâng cao trong tổ hợp. 4. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU • Lý thuyết về các cấu hình tổ hợp cơ bản và mở rộng và các kiến thức liên quan đến bài tốn đếm. • Phương pháp giải bài tốn đếm và các bài tốn áp dụng. • Ứng dụng của bài tốn đếm tổ hợp. 5. PHƯƠNG PHÁP NGHIÊN CỨU Sử dụng phương pháp nghiên cứu tài liệu liên quan đến luận văn để thu thập thơng tin, từ đĩ phân tích, hệ thống và phân loại các phương pháp giải cũng như một số ứng dụng điển hình liên quan đến bài tốn đếm trong tổ hợp. 4 6. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI Đề tài hệ thống kiến thức về các nguyên lý đếm, các cấu hình tổ hợp, lý thuyết hàm sinh, hệ thức truy hồi và các kiến thức liên quan đến bài tốn đếm tổ hợp. Từ đĩ hình thành các phương pháp từ cơ bản đến nâng cao và một số ứng dụng liên quan đến bài tốn đếm. Qua đĩ bổ sung thêm cho các em học sinh, sinh viên về các phương pháp giải các bài tốn đếm tổ hợp từ cơ bản đến khĩ và rất khĩ, đặc biệt là trước các kì thi học sinh giỏi từ cấp tỉnh, cấp quốc gia đến thi Olympic quốc tế và các kỳ thi khác. Đề tài cịn cĩ thể làm nguồn tham khảo cho những ai quan tâm đến lý thuyết tổ hợp mà cụ thể là phương pháp giải và ứng dụng của bài tốn đếm tổ hợp. 7. CẤU TRÚC CỦA LUẬN VĂN Luận văn được cấu trúc bởi 3 chương: Chương 1: Tổng quan về tổ hợp Chương 2: Một số phương pháp đếm nâng cao Chương 3: Một số ứng dụng Chương 1 TỔNG QUAN VỀ TỔ HỢP 1.1. SƠ LƯỢC VỀ LỊCH SỬ TỔ HỢP Cĩ thể nĩi tư duy tổ hợp ra đời rất sớm. Vào thời nhà Chu ở Trung Quốc người ta đã biết đến những hình vuơng thần bí. Thời cổ Hi lạp, thế kỷ thứ 4 trước Cơng nguyên, nhà triết học Kxenokrat đã biết cách tính số các từ khác nhau lập từ bảng chữ cái cho trước. Tuy nhiên cĩ thể nĩi rằng, lý thuyết tổ hợp được hình thành như một ngành tốn học mới vào thể kỷ 17 bằng một loạt cơng trình nghiên cứu của các nhà tốn học xuất sắc như Pascal, Fermat, Euler, Leibnitz … Các bài tốn tổ hợp cĩ đặc trưng bùng nổ tổ hợp với số cấu hình tổ hợp khổng lồ. Vì vậy trong thời gian dài, khi mà các ngành tốn học như Phép tính vi phân, Phép tính tích phân, phương trình vi phân… phát triển như vũ bão, thì dường như nĩ nằm ngồi sự phát triển và ứng dụng của tốn học. Tình thế thay đổi từ khi xuất hiện máy tính và sự phát triển của tốn học hữu hạn. Nhiều vấn đề tổ hợp đã được giải quyết trên máy tính và phát triển rất mạnh mẽ. 1.2. CÁC DẠNG BÀI TỐN TỔ HỢP Dạng 1: Bài tốn tồn tại Dạng 2: Bài tốn đếm Dạng 3: Bài tốn liệt kê Dạng 4: Bài tốn tối ưu tổ hợp 5 1.3. CÁC CẤU HÌNH TỔ HỢP CƠ BẢN VÀ MỞ RỘNG 1.3.1. Hai nguyên lý đếm cơ bản 1.3.1.1. Nguyên lý cộng 1.3.1.2. Nguyên lý nhân 1.3.2. Các cấu hình tổ hợp 1.3.2.1. Hốn vị khơng lặp 1.3.2.2. Hốn vị lặp 1.3.2.3. Chỉnh hợp khơng lặp 1.3.2.4. Chỉnh hợp lặp Định nghĩa 1.4: Chỉnh hợp lặp chập k của n phần tử khác nhau là một bộ cĩ thứ tự gồm k thành phần lấy từ n phần tử đã cho, các phần tử cĩ thể được lặp lại. Định lí 1.2: Số lượng các chỉnh hợp lặp chập k của n phần tử được kí hiệu và xác định bởi cơng thức sau: knA = AR(n, k) = nk. 1.3.2.5. Tổ hợp khơng lặp 1.3.2.6. Tổ hợp lặp Định nghĩa 1.6: Tổ hợp lặp chập k của n phần tử khác nhau là một nhĩm khơng phân biệt thứ tự gồm k phần tử trích từ n phần tử đã cho, trong đĩ các phần tử cĩ thể đựợc lặp lại. Định lý 1.3: Giả sử X cĩ n phần tử khác nhau. Khi đĩ số tổ hợp lặp chập k của n phần tử của X, được ký hiệu và xác định bởi cơng thức sau: CR(n, k) = C(k + n - 1, n - 1) = C(k + n - 1, k). Ví dụ 1.56. Bất phương trình x1 + x2 + x3 ≤ 11 (1) cĩ mấy nghiệm nguyên khơng âm ? Lời giải: Số nghiệm của bất phương trình (1) chính bằng số nghiệm nguyên của phương trình: x1 + x2 + x3 + x4 = 11 với ix 0, i = 1, 2, 3, 4.≥ Mỗi nghiệm của phương trình ứng với một cách chọn 11 phần tử từ một tập cĩ 4 loại, sao cho cĩ x1 phần tử loại 1, x2 phần tử loại 2, x3 phần tử loại 3, x4 phần tử loại 4 được chọn. Vì vậy số nghiệm bằng số tổ hợp lặp chập 11 từ tập cĩ 4 phần tử. Theo định lý 1.3 số đĩ bằng: C(4 + 11 - 1, 11) = C(14, 11) = 364. 1.3.3. Phân hoạch thứ tự tổ hợp và phân hoạch khơng thứ tự 1.3.3.1. Phân hoạch thứ tự tổ hợp Định nghĩa 1.7: Cho X là tập gồm n phần tử khác nhau, r n≤ và S X⊂ cĩ r phần tử. Một phân hoạch { }1 2 kS , S , ..., S cĩ thứ tự của S gọi là một phân hoạch thứ tự tổ hợp chập r của X. Nếu r = n thì gọi là phân hoạch thứ tự của X. Cho các số nguyên dương 1 2 kn , n , ..., n thỏa 1 2 kn n ... n r.+ + + = Số các phân hoạch thứ tự tổ hợp chập r của X dạng { }1 2 kS , S , ..., S cĩ 6 1 1 2 2 k kS n , S n , ..., S n , = = = được kí hiệu là 1 2 kC(n; n ,n , ...,n ) . Một cấu hình tổ hợp kiểu này được xây dựng qua các bước như sau: Bước 1: Chọn 1n phần tử từ X cho 1S , cĩ C( 1n, n ) khả năng. Bước 2: Chọn 2n phần tử từ X\S1 cho 2S , cĩ C( 1 2n n ,n− ) khả năng. … Bước k: Chọn kn phần tử từ X\ 1 2 k 1(S S ... S )−∪ ∪ ∪ cho kS , cĩ C( 1 2 k 1 kn n n ... n ,n−− − − − ) khả năng. Theo nguyên lý nhân suy ra: 1 2 kC(n; n ,n , ...,n ) = C( 1n,n ).C( 1 2n n ,n− )..…C( 1 2 k 1 kn n n ... n ,n−− − − − ) = 1 2 k 1 2 k n! P(n; n ,n , ..., n ,n r). n !n !.....n !(n r)! = −− Vậy ta cĩ định lí sau: Định lý 1.4: Số lượng các phân hoạch thứ tự tổ hợp chập r của X cĩ n phần tử bằng 1 2 kC(n;n ,n ,...,n ) = 1 2 k 1 2 k n! P(n;n ,n ,...n ,n r); n !n !...n !(n r)! = −− 1 2 kC(n;n ,n ,...,n ) được gọi là hệ số đa thức. Ví dụ 1.57. 17 sinh viên đi dạ hội bằng 5 xe khác nhau theo thứ tự cĩ số chỗ ngồi tương ứng là 4, 3, 3, 4, 1. Hãy xác định số cách chở 17 sinh viên bằng 5 xe, trong đĩ cĩ 2 sinh viên phải đi bằng phương tiện khác. Lời giải: Mỗi cách chở là một phân hoạch thứ tự tổ hợp chập 15 của 17 với số phần tử trong mỗi tập con tương ứng là 4, 3, 3, 4, 1. Vì vậy số cách chở là: C(17;4,3,3,4,1) = 17! 4!3!3!4!1! = 8576568000. 1.3.3.2. Phân hoạch khơng thứ tự Định nghĩa 1.8: Cho X là tập gồm n phần tử khác nhau, các số nguyên dương 1 2 kn ,n ,...,n và 1 2 kp ,p ,...,p thỏa 1 1 2 2 k kn p n p ... n p n.+ + + = Một hệ thống các tập con của X với 1p tập lực lượng 1n , 2p tập lực lượng 2n , …, kp tập lực lượng kn gọi là phân hoạch khơng thứ tự của X. Định lý 1.5: Số phân hoạch khơng thứ tự của X với 1p tập lực lượng 1n , 2p tập lực lượng 2n , …, kp tập lực lượng kn là: 1 2 k 1 1 2 2 k k p p p 1 2 k 1 1 2 2 k k C(n; n , ..., n , n , ..., n , ..., n , ..., n ) n! p !p !...p ! p !(n !) p !(n !) ... p !(n !) = Trong tử số 1 1 2 2 k kC(n; n , ..., n , n , ..., n , ..., n , ..., n ) số 1n lặp lại 1p lần, 2n lặp lại 2p lần, …, kn lặp lại kp lần. Ví dụ 1.60. Phân phối n quả cầu phân biệt vào m hộp phân biệt sao cho: Hộp 1 chứa 1n vật, hộp 2 chứa 2n vật, …, hộp m chứa mn vật: 1 2 mn n ... n n + + + = 7 Hỏi cĩ bao nhiêu cách phân phối khác nhau, khơng kể thứ tự cầu trong mỗi hộp. Lời giải: Cĩ thể phân phối bằng m bước như sau: Bước 1: Chọn 1n phần tử từ n cầu cho hộp 1, cĩ C( 1n,n ) cách Bước 2: Chọn 2n phần tử từ n - 1n cho hộp 2, cĩ C( 1 2n n ,n− ) cách … Bước m: Chọn mn phần tử từ 1 2 m 1n n n ... n −− − − − cho hộp m, cĩ C( 1 2 m 1 mn n n ... n ,n−− − − − ) khả năng. Theo nguyên lý nhân suy ra số cách phân phối là: C( 1n,n ) .C( 1 2n n ,n− ) .C( 1 2 m 1 mn n n ... n ,n−− − − − ) = 1 2 m n! n !n !...n ! . Chương 2 MỘT SỐ PHƯƠNG PHÁP ĐẾM NÂNG CAO 2.1. NGUYÊN LÝ BÙ TRỪ Với n tập hữu hạn A1, A2, ..., An ta cĩ định lý tổng quát sau: Định lý 2.1: Với n tập hợp A1, ..., An bất kỳ ta cĩ cơng thức |A1∪ ... ∪ An| = n i i=1 A ∑ - 1 i j n | |i jA A ≤ < ≤ ∩∑ + ...+ (-1)n-1|A1∩A2∩...∩An| (1) Hay ta cĩ thể phát biểu cách khác như sau: | A1 ∪ A2 ∪ ... ∪ An| = N1 − N2 + N3 − ... + (−1)n-1Nn trong đĩ Nm (1 ≤ m ≤ n) là tổng phần tử của tất cả các giao m tập lấy từ n tập đã cho, nghĩa là: Nm = 1 2 m 1 2 m i i i 1 i i ... i n | A A ... A | ≤ < < < ≤ ∩ ∩ ∩∑ Ví dụ 2.6. Cĩ bao nhiêu cách xếp 8 con xe lên bàn cờ quốc tế đã bị gạch đi một đường chéo chính sao cho khơng cĩ con nào ăn con nào. Lời giải: Cĩ 8! cách xếp 8 con xe lên bàn cờ quốc tế sao cho khơng cĩ con nào ăn con nào. Ta cần đếm số cách xếp khơng hợp lệ, tức là số cách xếp cĩ ít nhất một con xe nằm trên đường chéo. Gọi Ai là tập hợp các cách xếp cĩ quân xe nằm ở ơ (i, i). Ta cần tìm |A1∪...∪A8|. Nhưng dễ dàng thấy rằng |Ai| = 7!, |Ai∩Aj| = 6! , ..., |A1∩...∩A8| = 1 nên từ định lý trên ta suy ra: |A1 ∪ ... ∪ A8| = 18C .7! - 28C .6! + 38C .5! - ... - 88C .0! = 8! 8! 8!8! ...2! 3! 8!− + − − . Như vậy số cách xếp 8 con xe lên bàn cờ quốc tế đã bị gạch đi một đường chéo chính sao cho khơng cĩ con nào ăn con nào bằng: 8 8! – ( 8! 8! 8!8! ... 2! 3! 8! − + − − ) = 8!( ... 2! 3! 8! 1 1 1 +− + ) Ví dụ 2.8. Trong tập S = {1, 2, ..., 280} cĩ mấy số khơng chia hết cho 2, 3, 5, 7. Lời giải: Ta đếm xem trong tập S cĩ bao nhiêu số chia hết cho ít nhất một trong các số 2, 3, 5, 7. Kí hiệu A1 = {k ∈ S: k chia hết cho 2}, A2 = {k ∈ S: k chia hết cho 3}, A3 = {k ∈ S: k chia hết cho 5}, A4 = {k ∈ S: k chia hết cho 7}. Khi đĩ 1 2 3 4A A A A∪ ∪ ∪ là tập các số chia hết cho ít nhất một trong các số 2, 3, 5, 7. Ta cĩ: 1 2 3 4 280 280 280 280| A | 140; | A | 93; | A | 56; | A | 40 2 3 5 7         = = = = = = = =               ; 1 2 1 3 1 4 2 3 2 4 3 4 280 280 280| A A | 46; | A A | 28; | A A | 20; 2.3 2.5 2.7 280 280 280| A A | 18; | A A | 13; | A A | 8; 15 21 35       ∩ = = ∩ = = ∩ = =                 ∩ = = ∩ = = ∩ = =           1 2 3 1 2 4 1 3 4 2 3 4 280 280| A A A | 9; | A A A | 6; 30 42 280 280| A A A | 4; | A A A | 2; 70 105     ∩ ∩ = = ∩ ∩ = =           ∩ ∩ = = ∩ ∩ = =       1 2 3 4 280| A A A A | 1. 210   ∩ ∩ ∩ = =   Do đĩ theo nguyên lý bù trừ ta cĩ | 1 2 3 4A A A A∪ ∪ ∪ | = 216. Vậy trong tập S cĩ 280 – 216 = 64 số khơng chia hết cho 2, 3, 5, 7. 2.2. PHƯƠNG PHÁP SONG ÁNH 2.2.1. Định nghĩa 2.1 Cho ánh xạ f: A →B. • Ánh xạ f được gọi là một đơn ánh nếu với hai phần tử bất kì a1, a2 ∈A mà a1 ≠ a2 thì f(a1) ≠ f(a2), tức là f(a1) = f(a2) ⇔ a1 = a2. • Ánh xạ f được gọi là một tồn ánh nếu với mọi b∈B đều tồn tại a ∈A để cho f(a) = b. • Ánh xạ f được gọi là một song ánh (tương ứng 1-1) nếu với mọi b∈B, tồn tại và duy nhất a∈A để f(a) = b. Nĩi cách khác f là song ánh khi và chỉ khi nĩ vừa là đơn ánh vừa là tồn ánh. 2.2.2. Định lý 2.2 Cho A và B là hai tập hữu hạn. Khi đĩ: • Nếu cĩ một đơn ánh f: A →B thì |A| ≤ |B|. • Nếu cĩ một tồn ánh f: A →B thì |A| ≥ |B|. • Nếu cĩ một song ánh f: A →B thì |A| = |B|. 9 Phương pháp song ánh dựa vào một ý tưởng rất đơn giản: Nếu tồn tại một song ánh từ A vào B thì |A| = |B|. Do đĩ, muốn chứng minh hai tập hợp cĩ cùng số phần tử, chỉ cần xây dựng một song ánh giữa chúng. Hơn nữa, ta cĩ thể đếm được số phần tử của một tập hợp A (kí hiệu |A|), ta cĩ thể xây dựng song ánh từ A vào một tập hợp B mà ta đã biết cách đếm số phần tử. Bởi B cĩ cùng số phần tử với A nhưng cĩ cấu trúc được mơ tả khác A nên ta cĩ thể đếm được số phần tử của B dễ dàng hơn việc đếm số phần tử của A. Ví dụ 2.14 (APMO 1998). Giả sử Fk là tập hợp tất cả các bộ (A1, A2, ..., Ak), trong đĩ Ai (i = 1, 2, ..., k) là một tập con của tập E = {1, 2, ..., 1998}. Kí hiệu |A| là số phần tử của tập A. Hãy tính: 1 2 k k k 1 2 k (A ,A ,...,A ) F S | A A ... A | ∈ = ∪ ∪ ∪∑ (1) Lời giải: Lời giải thứ nhất ta cĩ thể dùng phương pháp quy nạp khá tự nhiên về mặt ý tưởng, tuy rất cồng kềnh và địi hỏi nhiều kĩ năng tính tốn. Lời giải thứ hai cũng tính Sk thơng qua việc tính T(i, k) là số các bộ: (A1, A2, ..., Ak) F,∈ sao cho 1 2 kA A ... A i∪ ∪ ∪ = tuy nhiên với một cách nhìn khác như sau: Với i phần tử n1, n2, ..., ni thuộc {1, 2, ..., n} ta đếm xem cĩ bao nhiêu bộ (A1, A2, ..., Ak) thỏa mãn điều kiện 1 2 kA A ... A∪ ∪ ∪ = {n1, n2, ..., ni} (2), từ đĩ tính được T(i, k) và Sk. Ta cho các phần tử n1, n2, ..., ni “đăng ký” cĩ mặt trong các tập hợp Ai theo qui tắc: nếu, chẳng hạn n1 đăng kí cĩ mặt trong A1, A2 và khơng cĩ mặt trong các tập cịn lại thì phiếu đăng kí của n1 được ghi là (1, 1, 0, 0, ..., 0), cịn nếu n1 chỉ cĩ mặt trong Ak thì ghi phiếu là (0, 0, ..., 1). Phiếu đăng kí là hợp lệ nếu cĩ ít nhất một số 1 (nếu khơng, phần tử tương ứng sẽ khơng cĩ mặt trong 1 2 kA A ... A∪ ∪ ∪ ). Với i phiếu đăng kí của n1, n2, ..., ni ta lập được 1 bộ (A1, A2, ..., Ak). Dễ thấy rằng với hai bộ phiếu đăng kí khác nhau, ta cĩ hai bộ tập hợp (A1, A2, ..., Ak) khác nhau và như vậy số bộ (A1, A2, ..., Ak) thỏa mãn (2) bằng số bộ phiếu đăng kí hợp lệ. Vì phiếu đăng kí của np, p = 1, 2, ..., i gồm k số 0 hoặc 1 và phải cĩ ít nhất một số 1 nên np cĩ 2k – 1 cách ghi phiếu đăng kí (do trừ ra xâu (0, 0, ..., 0) và như vậy theo nguyên lý nhân cĩ tất cả (2k – 1)i bộ phiếu đăng kí hợp lệ khác nhau. Cuối cùng, chú ý rằng cĩ inC cách chọn i phần tử n1, n2, ..., ni từ n phần tử nên ta cĩ: T(i, k) = i k inC (2 1)− suy ra: Sk = n n i k i n i 0 i 0 iT(i,k) iC (2 1) = = = −∑ ∑ = n(2k – 1).2k(n-1). (nhờ khai triển (1 + x)n và lấy đạo hàm, cho x = 2k – 1 và nhân hai vế với 2k – 1). Ví dụ 2.15 (Vơ địch Liên Xơ). Cĩ một nhĩm người mà trong đĩ, mỗi cặp khơng quen nhau cĩ đúng hai người quen chung, cịn mỗi cặp quen nhau thì khơng cĩ người quen chung. Chứng minh rằng số người quen của mỗi người là như nhau. 10 Lời giải: Nếu a quen b và tập các người quen của a và b (khơng kể a, b) lần lượt là A và B. Mỗi người a’ thuộc A sẽ quen với duy nhất một người thuộc B (do a’ và b khơng quen nhau, hơn nữa họ đã cĩ một người quen chung là a). Tương tự, mỗi người thuộc B cũng quen với duy nhất một người thuộc A. Vậy tồn tại một song ánh đi từ A tới B, tức a và b cĩ số người quen bằng nhau. Nếu a khơng quen b thì tồn tại c quen cả a và b. Do đĩ, số người quen của a và b bằng nhau do cùng bằng số người quen của c (suy ra từ trên). 2.3. HỆ THỨC TRUY HỒI 2.3.1. Khái niệm mở đầu và mơ hình hĩa bằng hệ thức truy hồi Định nghĩa 2.2: Hệ thức truy hồi (hay cơng thức truy hồi) đối với dãy số {an} là cơng thức biểu diễn an qua một hay nhiều số hạng đi trước của nĩ, cụ thể là a0, a1, a2, …, an-1 với n ≥ n0 nguyên dương nào đĩ. Dãy số được gọi là lời giải hay nghiệm của hệ thức truy hồi nếu các số hạng của nĩ thỏa mãn hệ thức truy hồi này. Các giá trị gán cho một số hữu hạn các số hạng đầu của dãy gọi là các điều kiện ban đầu hay điều kiện biên của hệ thức truy hồi. Ví dụ 2.18. Hệ thức truy hồi cho dãy số Fibonacci là Fn = Fn-1 + Fn-2 với n ≥ 3 và F1 = F2 = 1. 2.3.2. Giải hệ thức truy hồi 2.3.2.1. Giải hệ thức truy hồi bằng phương pháp lặp Ta cĩ thể dùng một trong hai phương án sau: Hoặc ta đi thay thế liên tiếp cơng thức truy hồi vào chính nĩ, mỗi lần thay như vậy bậc n sẽ giảm ít nhất 1 đơn vị, cho đến khi đạt giá trị ban đầu. Hoặc là ta xuất phát từ điều kiện đầu ta sẽ tính một số số hạng đầu và nhận ra qui luật, sau đĩ dự đốn số hạng tổng quát và dùng phương pháp chứng minh qui nạp để chứng minh tính đúng đắn của cơng thức vừa dự đốn đĩ. Ví dụ 2.22 (Bài tốn tháp Hà Nội) ‘‘Cĩ ba cọc 1, 2, 3. Ở cọc 1 cĩ n đĩa xếp chồng lên nhau sao cho đĩa nằm dưới lớn hơn đĩa nằm trên. Hãy chuyển tất cả các đĩa từ cọc 1 sang cọc 3 cĩ thể dùng cọc 2 làm cọc trung gian với điều kiện mỗi lần chỉ được chuyển 1 đĩa từ cọc này sang cọc khác và luơn đảm bảo đĩa nằm dưới lớn hơn đĩa nằm trên’’. Bài tốn đặt ra là: Tìm số lần di chuyển đĩa ít nhất cần thực hiện để giải xong bài tốn trên. Lời giải: Phương pháp di chuyển như sau: Gọi sn là số lần di chuyển đĩa ít nhất cần thực hiện. • Chuyển n-1 đĩa từ cọc 1 sang cọc 2 (lấy cọc 3 làm trung gian) ta cĩ sn-1 phép chuyển. • Chuyển đĩa lớn nhất ở cọc 1 sang cọc số 3: ta cĩ 1 phép chuyển. 11 • Chuyển n-1 đĩa ở cọc số 2 về cọc số 3 (lấy cọc 1 làm trung gian) ta cĩ sn-1 phép chuyển. Do vậy, để chuyển n chiếc đĩa từ cọc số 1 sang cọc số 3, ta cần ít nhất sn-1 + 1 + sn-1 = 2.sn-1 + 1 phép chuyển. Vậy ta cĩ cơng thức truy hồi của dãy số s0, s1, s2, … là: sn = 2.sn-1 + 1 và s1 = 1 (s2 = 3, s3 = 7). Ta cĩ: sn = 2sn-1 + 1 = 2(2sn-2+1) + 1 = 22.sn-2 + 2 + 1= 22(2sn-3 +1)+2+1 = 23sn-3 + 22 + 2 + 1= ….. = 2n-1.s1 + 2n-2 + 2n-3 + … + 2 + 1 = 2n-1 + 2n-2 + 2n-3 + … + 2 + 1 n 1 n1 22. 1 2 2 1 1 2 − − = + = − + + − = 2n – 1. Ví dụ 2.23. (Olympic Bungari, 1995) Cho số nguyên n ≥ 2. Hãy tìm số các hốn vị (a1, a2, ..., an) của 1, 2, …, n sao cho tồn tại duy nhất một chỉ số i ∈{1, 2, …, n-1} thỏa mãn ai > ai+1. Lời giải: Gọi Sn là số các hốn vị thỏa mãn điều kiện bài tốn. Để ý rằng số các hốn vị mà an = n là Sn-1 (Bởi vì Sn-1 là số các hốn vị (a1, a2, ..., an-1) của 1, 2, …, n-1 sao cho tồn tại duy nhất một chỉ số i ∈{1, 2, …, n - 2} thỏa mãn ai > ai+1). Cịn số các hốn vị (a1, a2, ..., an) thỏa mãn điều kiện bài tốn với ai = n (1 ≤ i ≤ n-1) là i 1n 1C .−− Do đĩ: Sn = Sn-1 + n 1 i 1 n 1 i 1 C − − − = =∑ Sn-1 +2n-1 – 1. (Do n i 1 n 1 n 1 i 1 C 2− − − = =∑ ). Hiển nhiên: S2 = 1, tương tự ví dụ 2.22 ta sẽ cĩ: Sn = 2n - n - 1. 2.3.2.2. Giải hệ thức truy hồi tuyến tính hệ số hằng Định nghĩa 2.3: Hệ thức truy hồi tuyến tính bậc k là hệ thức truy hồi cĩ dạng: an = c1(n). an-1 + c2(n). an-2 + ... + ck(n). an-k + f(n) (T) trong đĩ c1(n), c2(n), ..., ck(n) và f(n) là các hàm theo n và ck(n) ≠ 0 với n∀ • Với hệ thức truy hồi (T) thì hệ thức truy hồi sau an = c1(n). an-1 + c2(n). an-2 + ... + ck(n). an-k (T0) được gọi là hệ thức truy hồi tuyến tính thuần nhất bậc k ứng với (T). • Nếu ci(n) = ci , i = 1, 2, ..., k , đều là các hằng số, ck(n) ≠ 0 thì (T) được gọi là hệ thức truy hồi tuyến tính hệ số hằng bậc k và (T0) tương ứng được gọi là hệ thức truy hồi tuyến tính thuần nhất hệ số hằng bậc k. • Điều kiện ban đầu (điều kiện biên) của (T) là giả thiết một số phần tử đầu của dãy cĩ giá trị cho trước: a0 = C0, a1 = C1, a2 = C2, ... ∗ Phương trình đặc trưng của hệ thức truy hồi (T0) cĩ hệ số hằng: rk − c1r k-1 − c2r k-2 − ... − ck-1r – ck = 0 (1) Phương trình (1) được gọi là phương trình đặc trưng của hệ thức truy hồi (T0), nghiệm của nĩ gọi là nghiệm đặc trưng của hệ thức truy hồi. Nghiệm của phương trình đặc trưng dùng để biểu diễn cơng thức tất cả các nghiệm (nghiệm tổng quát) của hệ thức truy hồi (T0). 12 ∗ Các định lý sau ta xét các hệ thức truy hồi (T) và (T0) ở trên với hệ số hằng: Định lý 2.3: Nếu a1, a2, ..., am là các nghiệm của (T0) thì a = c1a1 + c2a2 + ... + cmam (với c1, c2, ..., cm là các hằng số tùy ý) cũng là nghiệm của hệ thức truy hồi (T0). Định lý 2.4: Nếu r là nghiệm bội m (m≥ 1) của phương trình đặc trưng (1) thì rn, nrn, n2rn, …, nm-1rn là các nghiệm của (T0), và khi đĩ (c0+c1n+c2n2 +…+ cm-1nm-1) .rn, (c0, c1, ..., cm-1 là các hằng số tùy ý) cũng là nghiệm của (T0). Hệ quả 2.1: Nếu r1, r2, …, rq tương ứng là các nghiệm bội m1, m2, …, mq (mi ≥ 1, i = 1, 2, …, q) của phương trình đặc trưng (1), thì nghiệm tổng quát của (T0) cĩ dạng: an = a1(n) + a2(n) + ... + aq(n), trong đĩ: ai(n) = (Ci,0 + nCi,1 + n2Ci,2 +…+ i i m 1 i,m 1n .C − − ). nir , i 1,2,...,q∀ = Với Ci,j , j = 0, 1, 2, …, mi-1 , là các hằng số bất kỳ. Hệ quả 2.2: Cho c1, c2, ..., ck là các số thực. Giả sử rằng phương trình đặc trưng rk − c1r k-1 − c2r k-2 − ... − ck-1r – ck = 0 cĩ k nghiệm phân biệt r1, r2, ..., rk (cĩ thể phức). Khi đĩ dãy {an} là nghiệm của hệ thức truy hồi (T0) thì nghiệm đĩ cĩ dạng an = α1r1 n + α2r2 n + ... + αkrk n , trong đĩ α1, α2, ..., αk là các hằng số. Định lý 2.5: Nghiệm tổng quát của (T) cĩ dạng an = hn + gn Trong đĩ gn là một nghiệm riêng nào đĩ của (T) và hn là nghiệm tổng quát của hệ thức truy hồi tuyến tính thuần nhất (T0) ứng với (T). Định lý 2.6: [4, tr.62] Cho hệ thức truy hồi tuyến tính khơng thuần nhất hệ số hằng bậc k: an + C1.an-1 + C2.an-2 + ... + Ck.an-k = f(n) (T) trong đĩ f(n) = Ps(n) (là đa thức bậc s của n) Phương trình đặc trưng của (T) là: rk + C1rk-1 + C2rk-2 + ... + Ck-1r + Ck = 0 (1) • Nếu phương trình đặc trưng (1) khơng cĩ nghiệm r = 1 thì nghiệm riêng của (T) cĩ dạng *na = Qs(n). • Nếu phương trình đặc trưng (1) cĩ nghiệm bội m là r = 1 thì nghiệm riêng của (T) cĩ dạng *na = n m .Qs(n). Định lý 2.7: (Mở rộng của định lý 2.6) Cho hệ thức truy hồi tuyến tính khơng thuần nhất hệ số hằng bậc k: an + C1.an-1 + C2.an-2 + ... + Ck.an-k = f(n) (T) trong đĩ f(n) = Ps(n). nβ (là đa thức bậc s của n, và β là một hằng số) Phương trình đặc trưng của (T) là: rk + C1rk-1 + C2rk-2 + ... + Ck-1r + Ck = 0 (1) • Nếu β khơng phải là nghiệm của phương trình đặc trưng (1) thì nghiệm riêng của (T) cĩ dạng *na = Qs(n).β n (trong đĩ Qs(n) là đa thức cĩ bậc s). • Nếu β là nghiệm bội m (m ≥ 1) của phương trình đặc trưng (1) thì nghiệm riêng của (T) cĩ dạng *na = nm.Qs(n).β n (trong đĩ Qs(n) là đa thức cĩ bậc s). 13 Định lý 2.8: (Nguyên lý chồng chất nghiệm) Cho hệ thức truy hồi tuyến tính khơng thuần nhất hệ số hằng bậc k: an = C1.an-1 + C2.an-2 + ... + Ck.an-k + f(n) (T) Nếu thành phần khơng thuần nhất f(n) của (T) cĩ dạng f(n) = p1(n) + p2(n) + ... + pm(n) thì nghiệm riêng của (T) cĩ dạng gn = f1(n) + f2(n) + ... + fm(n), trong đĩ fi(n), i 1,m= là nghiệm riêng của hệ thức truy hồi khơng thuần nhất tương ứng: an = C1.an-1 + C2.an-2 + ... + Ck.an-k + fi(n), i 1,m= . Ví dụ 2.33. Giải cơng thức truy hồi an = 4an-1 – 4an-2 + n2n + 3n + 4 , n ≥ 2 (T) Lời giải: • Phương trình thuần nhất tương ứng cĩ nghiệm tổng quát là hn = c1.2n + c2.n2n • Ta cĩ thành phần khơng thuần nhất là f(n) = n2n + 3n + 4 do đĩ để tìm nghiệm riêng gn của (T) ta lần lượt đi tìm nghiệm riêng của 3 hệ thức truy hồi sau: an = 4an-1 – 4an-2 + 4 ; an = 4an-1 – 4an-2 + 3n ; an = 4an-1 – 4an-2 + n2n * Với hệ thức an = 4an-1 – 4an-2 + 4 (T1) Ta cĩ thành phần khơng thuần nhất là f1(n) = 4 = 4.1n và do 1 khơng là nghiệm của phương trình đặc trưng nên nghiệm riêng của (T1) cĩ dạng c.1n, thay vào (T1) ta được c = 4. Vậy nghiệm riêng của (T1) là 4. * Với hệ thức an = 4an-1 – 4an-2 + 3n (T2) Ta cĩ thành phần khơng thuần nhất là f2(n) = 3n = 1.3n và 3 khơng là nghiệm của phương trình đặc trưng nên nghiệm riêng của (T2) cĩ dạng c.3n, thay vào (T2) ta được c = 9. Vậy nghiệm riêng của (T2) là 9.3n. * Với hệ thức an = 4an-1 – 4an-2 + n2n (T3) Ta cĩ thành phần khơng thuần nhất là f3(n) = n.2n và 2 là nghiệm bội 2 của phương trình đặc trưng nên nghiệm riêng của (T3) cĩ dạng n2(c1n + c2)2n, thay vào (T3) ta cĩ: n2(c1n + c2)2n = 4( )2n 1− [c1(n - 1) + c2]2n-1 - 4( )2n 2− [c1(n - 2) + c2]2n-2 + n2n chia cả hai vế cho 2n-2 sau đĩ khai triển và cân bằng hệ số (của đa thức ẩn n) ta được: c1 = 1 6 , c2 = 1 2 . Vậy nghiệm riêng của (T3) là n2( 16 n + 1 2 )2n. Từ ba trường hợp trên suy ra nghiệm riêng của hệ thức truy hồi (T) là gn = 4 + 9.3n + n2( 16 n + 1 2 )2n. Vậy nghiệm tổng quát của (T) là: an = c1.2n + c2.n2n +4 + 9.3n + n2( 16 n + 1 2 )2n. 14 2.4. PHƯƠNG PHÁP ĐẾM BẰNG HÀM SINH Cĩ rất nhiều bài tốn tổ hợp như bài tốn phân hoạch tập hợp, bài tốn đếm, tìm dãy số trong các đề thi học sinh giỏi quốc gia, quốc tế là các bài tốn rất khĩ. Hàm sinh là một cơng cụ hiệu lực để giải quyết dạng bài tập này. Khái niệm hàm sinh khá đơn giản, dễ hiểu nhưng lại cĩ ứng dụng rất hay vào việc giải các dạng bài tốn trên. 2.4.1. Định nghĩa 2.4 Cho dãy số {an}. Chuỗi lũy thừa hình thức vơ hạn F(x) = nn n 0 a x ≥ ∑ gọi là hàm sinh thường sinh bởi dãy số {an}. Kí hiệu: {an} ↔F(x) hay {an} ↔F. 2.4.2. Cơng thức khai triển Taylor Giả sử f(x) là hàm số liên tục, cĩ đạo hàm mọi cấp trên khoảng (a, b); x0∈(a, b). Khi đĩ ta cĩ cơng thức khai triển Taylor: f(x) = (n) n0 n 0 f (x ) x n!≥ ∑ . 2.4.3. Cơng thức nhị thức Newton mở rộng • Với α là một số thực và k là số nguyên khơng âm. Lúc đĩ hệ số nhị thức Newton mở rộng kCα được định nghĩa như sau: k ( 1)...( k 1) , k 0 C k! 1, k 0 α α α − α − + > =   = • Cho x là số thực với |x| < 1 và α là một số thực. Lúc đĩ: k k k 0 (1 x) C x . ∞ α α = + =∑ Tức là: 2 n( 1) ( 1)...( n 1)(1 x) 1 x x ... x ... 2 n! α α α − α α − α − ++ = + α + + + + 2.4.4. Tính chất của hàm sinh Cho {an} ↔F(x) , {bn} ↔G(x) khi đĩ ta cĩ các tính chất sau: (1) {an ± bn}↔F(x) ± G(x) (2) {kan}↔kF(x) , ∀k∈R (3) {(n+1)an+1} ↔ F’(x) (4) {an-an-1} ↔ (1-x)F(x) (5) {nan} ↔ xF’(x) (6) {an+h} ↔ 2 3 h 1 0 1 2 3 h 1 h F(x) a a x a x a x ... a x , N x h − − − − − − − − ∈ (7) {k.an ± h.bn}↔k.F(x) + h.G(x) (8) {a0+a1+a2+...+an} ↔ F(x)1 x− (9) {cn} = { i j i j n a b + = ∑ } = { n k n k k 0 a b − = ∑ } ↔F(x).G(x) 15 2.4.5. Một số khai triển đại số thường dùng trong việc sử dụng hàm sinh (1) 2 k1 1 x x ... x ... 1 x = + + + + + − (2) 1 1 x+ = 1 – x + x2 – x3 + … (3) 1 1 ax− = 1 + ax + a2x2 + a3x3 + …+ anxn +… (4) (1 + x)n = 1 2 2 n nn n n1 C x C x ... C x+ + + + (5) n 1 kn k 1n k 0 1 C x(1 x) ∞ − + − = = − ∑ = 2 3n(n 1) n(n 1)(n 2)1 nx x x ... 2 3! + + + + + + + (6) ( )k k 2 k k 1 k 2x x ... x x x ...1 x 1 x x + += + + + = + + +− (7) k 1 2 k1 x 1 x x ... x 1 x + − = + + + + − (8) 2 4 62 1 1 x x x ... 1 x = + + + + − (9) 2 4 6 3 5 72 x x(1 x x x ...) x x x x ... 1 x = + + + + = + + + + − (10) 22 1 1 2x 3x ...(1 x) = + + +− + (n+1)x n +... (11) 2 n2 1 x 1 3x 5x ... (2n 1)x ...(1 x) + = + + + + + + − (12) 2 2 3 2 n 3 x x x 4x 9x ... n x ...(1 x) + = + + + + + − (13) 2 3 n x nx x xe 1 x ... x ... 2! 3! n! = + + + + + + (14) 2 3 n nx x xln(1 x) x ... x ... 2 3 n − − = + + + + + (15) n k k kn n 0 (1 ax) C a x ∞ = + =∑ 2.4.6. Phương pháp đếm bằng hàm sinh Hàm sinh cĩ thể được áp dụng trong các bài tốn đếm. Nĩi riêng, các bài tốn chọn các phần tử từ một tập hợp thơng thường sẽ dẫn đến các hàm sinh. Khi hàm sinh được áp dụng theo cách này, hệ số của xn chính là số cách chọn n phần tử. 2.4.6.1. Chọn các phần tử khác nhau Hàm sinh cho dãy các hệ số nhị thức được suy ra trực tiếp từ định lý nhị thức i 0 1 k k k k k k k{C } C C x ... C x (1 x)↔ + + + = + 16 Như vậy hệ số của xn trong (1 + x)k là nkC bằng số cách chọn n phần tử phân biệt từ một tập hợp gồm k phần tử khơng phân biệt thứ tự. Ví dụ, hệ số của x2 là 2nC , số cách chọn 2 phần tử từ tập hợp k phần tử. Tương tự, hệ số của xk+1 là số cách chọn k + 1 phần tử từ tập hợp k phần tử và như thế, bằng 0. 2.4.6.2. Xây dựng hàm sinh để giải bài tốn đếm Hàm sinh cho số cách chọn n phần tử từ tập hợp k phần tử là (1 + x)k. Đây chính là cơng thức hàm sinh mà ta đã nhận được bằng cách sử dụng định lý nhị thức. Chúng ta cĩ thể mở rộng điều này qua định lý sau đây: Định lý 2.8. (Quy tắc xoắn) Gọi A(x) là hàm sinh cho cách chọn các phần tử từ tập hợp A và B(x) là hàm sinh cho cách chọn các phần tử từ tập hợp B. Nếu A và B là rời nhau thì hàm sinh cho cách chọn các phần tử từ A ∪ B là A(x).B(x). 2.4.6.3. Chọn các phần tử cĩ lặp Hàm sinh của cách chọn các phần tử từ tập hợp n phần tử cĩ lặp là n 1 (1 x)− . Như vậy theo cơng thức Taylor số cách chọn k phần tử cĩ lặp từ n phần tử bằng k n k 1C .+ − Một cách tiếp cận khác, ta lập luận như sau: Với k > 0, ta cĩ nn k 1{C , n 0, 1, 2, ...} + − = ↔F(x) = k 1 (1 x)− Thậy vậy, ta cĩ k 1 (1 x)− = k1 1 x     −  = ( 1 + x + x2 + x3 + ... )k Nếu ta khai triển biểu thức trên bằng cách thực hiện nhân phá ngoặc, thì số lần xuất hiện số hạng xn sẽ bằng số nghiệm nguyên khơng âm của phương trình: x1 + x2 + ..... + xk = n. Ta đã biết số nghiệm của phương trình này bằng: nn k 1C + − . Như vậy hệ số của xn chính bằng số cách chọn n vật từ tập cĩ k loại đồ vật. Nhận xét 2.7: Ví dụ trên đã áp dụng qui tắc xoắn gợi ý cho ta phương pháp giải nhiều bài tốn đếm. Chẳng hạn với hàm sinh: F(x) = (1 + x + x2 + x3 + x4 + x5)(1 + x + x2)(1 + x + x2 + x3 ) Giả sử 31 2 xx xx , x , x tương ứng là các số hạng lấy từ các thừa số thứ nhất, thứ hai và ba của vế phải, suy ra 0 ≤ x1 ≤ 5, 0 ≤ x2 ≤ 2, 0 ≤ x3 ≤ 3. Khi khai triển vế phải các thừa số này sẽ cho ta số hạng xn, với n = x1 + x2 + x3. Như thế hệ số của xn trong F(x) sẽ là số nghiệm nguyên khơng âm của phương trình x1 + x2 + x3 = n thỏa mãn: 0 ≤ x1 ≤ 5, 0 ≤ x2 ≤ 2, 0 ≤ x3 ≤ 3. Như vậy hệ số này cũng cho ta số cách chọn n vật từ tập cĩ 3 loại vật, gồm 5 vật loại 1, 2 vật loại 2 và 3 vật loại 3. 17 Ví dụ 2.41. Bây giờ ta xét một bài tốn đếm rất khĩ chịu. Cĩ bao nhiêu nhiêu cách sắp một giỏ n trái cây thoả mãn các điều kiện ràng buộc sau: • Số táo phải chẵn • Chỉ cĩ thể cĩ nhiều nhất 4 quả cam • Số chuối phải chia hết cho 5 • Chỉ cĩ thể cĩ nhiều nhất 1 quả đào Chẳng hạn, ta cĩ 7 cách sắp giỏ trái cây cĩ 6 trái: Táo 6 4 4 2 2 0 0 Chuối 0 0 0 0 0 5 5 Cam 0 2 1 4 3 1 0 Đào 0 0 1 0 1 0 1 Lời giải: Các điều kiện ràng buộc này quá phức tạp và cĩ cảm giác như việc đi tìm lời giải là vơ vọng. Nhưng ta hãy xem hàm sinh sẽ xử lý bài tốn này thế nào. Trước hết, ta đi tìm hàm sinh cho số cách chọn táo. Cĩ 1 cách chọn 0 quả táo, cĩ 0 cách chọn 1 quả táo (vì số táo phải chẵn), cĩ 1 cách chọn 2 quả táo, cĩ 0 cách chọn 3 quả táo … Như thế ta cĩ hàm sinh cho số cách chọn táo là A(x) = 1 + x2 + x4 + … = 1 . 2 1 x− Tương tự, hàm sinh cho số cách chọn chuối là B(x) = 1 + x5 + x10 + … = 5 1 . 1 x− Bây giờ, ta cĩ thể chọn 0 quả cam bằng 1 cách, 1 quả cam bằng 1 cách, … Nhưng ta khơng thể chọn hơn 4 quả cam, vì thế ta cĩ C(x) = 1 + x + x2 + x3 + x4 = 5 . 1 x 1 x− − Và tương tự, hàm sinh cho số cách chọn đào là D(x) = 1 + x = 2 . 1 x 1 x− − Theo quy tắc xoắn, hàm sinh cho cách chọn từ cả 4 loại trái cây bằng 5 2 2 3 2 5 2 1 1 1 x 1 x 1A(x).B(x).C(x).D(x) . . . 1 2x 3x 4x ... 1 x 1 x1 x 1 x (1 x) − − = = = + + + + − − − − − Gần như tất cả được giản ước với nhau! Chỉ cịn lại 2 1 (1 x)− mà ta đã tìm được chuỗi luỹ thừa từ trước đĩ. Như thế số cách sắp giỏ trái cây gồm n trái cây đơn giản bằng n + 1. Điều này phù hợp với kết quả mà ta đã tìm ra trước đĩ, vì cĩ 7 cách sắp cho giỏ 6 trái cây. Thật là thú vị! Ví dụ 2.42. Tìm hàm sinh cho số nghiệm nguyên dương lẻ của phương trình x1 + x2 + x3 +...+ xk = n Lời giải: Hàm sinh cần tìm là: f(x) = (x + x3 + x5 + x7 + ...)k = ( ) k...2 4 6x 1 x x x + + + +  = k 21 x x    −  = k 2 k(1 x ) x − . 18 Chương 3 MỘT SỐ ỨNG DỤNG 3.1. MỘT SỐ ỨNG DỤNG CỦA HỆ THỨC TRUY HỒI 3.1.1. Ứng dụng bài tốn tìm số hạng tổng quát của hệ thức truy hồi vào giải một số bài tốn về dãy số và tổ hợp Bài tốn 3.2 (Olympic tốn sinh viên tồn quốc – 2004). Cho dãy số (bn) xác định bởi hệ thức sau: b0 = 0, bn = nn 1b ( 1) ,2004 n 1 − + − ≥ . Tính 2n n lim b →+∞ . Lời giải: Phương trình đặc trưng r - 1 2004 = 0 ⇔ r = 1 2004 Nghiệm tổng quát của hệ thức truy hồi thuần nhất tương ứng là n n 1 1b C . . 2004   =     f(n) = (-1)n nên chọn *nb = C2.(-1)n. Thay vào hệ thức truy hồi ở đề bài ta được: C2 = 2004 2005 ⇒ * nb = 2004 2005 .(-1)n. ⇒ Cơng thức tổng quát của dãy số cần tìm là bn = n 1 1C . 2004       + 2004 2005 .( )n1− . Đề cho b0 = 0 ⇒ 0 = 1C + 2004 2005 ⇒ 1C = 2004 2005 − Vậy cơng thức tổng quát của dãy số cần tìm là: bn = n2004 1 . 2005 2004   −     + 2004 2005 .( )n1− = ( )( ) n n 1 2004 1 2005. 2004 − − − − . Suy ra 2n n lim b →+∞ = ( ) ( ) ( ) ( ) 2 2 n n 2n n n 1 n 1n n 1 2004 1 1 (2004) 1 2004lim lim . 20052005. 2004 2005. 2004− −→+∞ →+∞     − − − −      = =           Bài tốn 3.7. (IMO 1967) Trong một cuộc thi đấu thể thao cĩ m huy chương, được phát trong n ngày thi đấu. Ngày thứ nhất, người ta phát một huy chương và 1 7 số huy chương cịn lại. Ngày thứ hai, người ta phát hai huy chương và 1 7 huy chương cịn lại. Những ngày cịn lại được tiếp tục và tương tự như vậy. Ngày sau cùng cịn lại n huy chương để phát. Hỏi cĩ tất cả cĩ bao nhiêu huy chương và đã phát trong bao nhiêu ngày. Lời giải: Gọi ak là số huy chương cịn lại trước ngày thứ k, suy ra a1 = m và ta cĩ: 19 ak+1 = ak – k - 1 7 (ak – k) = k6 6ka -7 7 (Do ngày thứ k phát đi k huy chương và 1 7 huy chương cịn lại). Giải hệ thức truy hồi này ta được: k 1 k 6 a (m 36) 6k 42 7 −   = − − +    . Theo giả thiết ta cĩ an = n = n 1 n 16 7(m 36) 6n 42 m 36 7(n 6) 7 6 − −     − − + ⇒ − = −        Vì m – 36 ∈
và (6, 7) = 1, 6n-1 > n – 6 nên n – 6 = 0 n 6 m 36.⇔ = ⇒ = Vậy cĩ 36 huy chương được phát trong 6 ngày. 3.1.2. Ứng dụng giải hệ thức truy hồi là một hệ biểu thức tuyến tính thuần nhất cấp một Xét hệ: 1 1 n 1 n n n 1 n n a , a pa qb b ra sb b + + = α = β  = +  = + , với α , β , p, q, r, s là các hằng số thực. Giải hệ trên là đi xác định số hạng tổng quát của các dãy số (an) và (bn) thỏa mãn hệ thức truy hồi đĩ. Bằng cách biến đổi đưa về giải hệ thức truy hồi tuyến tính thuần nhất cấp hai. Muốn vậy ta thay n bởi n + 1 vào phương trình thứ hai của hệ trên ta cĩ: n 2 n 1 n 1 n 1 n n n 1 n n 1 na pa qb pa q(ra sb ) pa qra s(a pa )+ + + + + += + = + + = + + − Suy ra n 2 n 1 na (p s)a (qr ps)a+ += + + − Mặt khác từ hệ trên ta lại cĩ 2 1 1a pa qb= + = p qα + β Vậy ta cĩ hệ thức truy hồi tuyến tính thuần nhất cấp hai là n 2 n 1 n 1 2a (p s)a (qr ps)a , a , a p q + += + + − = α = α + β Mà ta đã biết cách giải. Từ đĩ ta tìm được an , thế vào hệ trên và thu được bn. 3.1.3. Ứng dụng tìm số hạng của một số dãy số đặc biệt 3.1.3.1. Dạng 1 Cho dãy số ( )nx xác định bởi nn 1 n px q x rx s + + = + , trong đĩ: x0 = a cho trước và p, q, r, s là các hằng số. Tìm số hạng tổng quát nx . Giả sử yn và zn là nghiệm của hệ: n 1 n n n 1 n n y py qz z ry sz + + = +  = + , y0 = a, z0 = 1. Khi đĩ nn n y x z = là nghiệm của hệ thức truy hồi đã cho. Thật vậy, 00 0 y x z = = a a 1 = đúng. Ta lại cĩ: n n 1 n n nn n 1 nn 1 n n n n yp q y py qz px qz x yz ry sz rx s r s z + + + + + + = = = = + ++ đúng. 20 3.1.3.2. Dạng 2 Cho dãy số ( )nu xác định bởi 1 2u , u = α = β và n 1 nn 1 n 1 n u .u u au bu − + − = + (1) Tìm số hạng tổng quát nu . Biến đổi ( ) n 1 n n 1 n 1 n n 1 n n 1 1 au bu 1 1 11 a. b. u u .u u u u − + − + − + ⇒ = ⇔ = + Đặt n n 1 v u = ta cĩ: n 1 n n 1v av bv 0+ −− − = (Đây là hệ thức truy hồi tuyến tính thuần nhất hệ số hằng). 3.1.3.3. Dạng 3 Cho dãy số (un) xác định như sau: 2n n 1 n 1u a.u bu c , n 2− −= + + ∀ ≥ (2) và 2, b 1. 1 u a= α − = Tìm số hạng tổng quát nu . Ta cĩ: (2) ⇔ (un – aun-1)2 = b 2n 1u − + c 2 2n n n 1 n 1u 2au u u c 0− −⇔ − + − = (3) Thay n bởi n – 1 ta cĩ: 2 2n 2 n 1 n 2 n 1u 2au u u c 0− − − −− + − = (4) Từ (3) và (4) ta cĩ un và un-2 là 2 nghiệm của phương trình: 2 2 n 1 n 1t 2au .t u c 0− −− + − = . Áp dụng định lý Viet, ta cĩ: un + un-2 = 2a.un-1. Từ đĩ suy ra un. 3.1.3.4. Dạng 4 Tìm dãy số (un) xác định như sau: n 1n 2 n 1 u u a c.u b , n 2 − − = ∀ ≥ + + (5) Với điều kiện: 1u = α , 2 b 1 > 0, a > 0, a α − = Ta cĩ (5) 2 n n 1 n 1 1 a b c u u u − − ⇔ = + + và đặt n n 1 x u = ta được: 2 n n 1 n 1x a.x b.x c− −= + + đây là bài tốn dạng 3, nên ta tìm được xn, từ đĩ suy ra un. 3.2. MỘT SỐ ỨNG DỤNG CỦA PHƯƠNG PHÁP SONG ÁNH Dùng song ánh để thiết lập hệ thức truy hồi, dựa trên ý tưởng: Nếu tồn tại một song ánh từ tập A đến tập B thì số phần tử của A và B sẽ bằng nhau. Từ đĩ ứng dụng vào giải một số bài tốn như: Tính tổng tổ hợp, chứng minh đẳng thức tổ hợp ... là các dạng tốn đặc trưng của phương pháp song ánh. Phần này chúng ta đi tìm hiểu các bài tốn thuộc các dạng đặc trưng đĩ. 3.2.1. Dùng song ánh xây dựng hệ thức truy hồi và chứng minh hai tập bằng nhau áp dụng vào giải một số bài tốn tổ hợp Bài tốn 3.15. Cho số nguyên dương n, tìm số tập con khác rỗng của tập S = {1, 2, ..., n} sao cho trong mỗi tập con khơng chứa hai số nguyên liên tiếp nào. Lời giải: Đặt Sn = {M ⊂ S | M khơng chứa 2 số nguyên liên tiếp nào} 21 Pn = 1 2 n i i i 1{(a , a , ..., a ) | a {0, 1} 1, n a , a ) (1, 1), 1, n 1} i = ; ( i = +∈ ∀ ≠ ∀ − • Xét ánh xạ f: 1 2 n M (a ,a ,...,a ) n n f: S P → a sao cho i i a 1 a 0 khi i M khi i M = ∈  = ∉ Dễ dàng kiểm tra được rằng f là song ánh nên |Sn| = |Pn|, n 1∀ ≥ • Xét ánh xạ g: 1 2 n 1 n 1 n 1 2 n 1 2 n 2 n 2 n (a ,a ,...,a ) P 0(a ,a ,...,a ) (a ,a ,...,a ) P 1 n n-1 n-2 g: P P P n 3 khi a khi a − − − − → ∪ ∀ ≥ ∈ =  ∈ = a Dễ dàng kiểm tra được rằng g là song ánh, Pn và Pn-1 là rời nhau nên |Pn| = |Pn-1| + |Pn-2| , n 3∀ ≥ suy ra |Sn| = |Sn-1| + |Sn-2| , n 3∀ ≥ Vì |S1| = 2 ; |S2| = 3 nên |Sn| = |Fn+2| n 1∀ ≥ với {Fn} là dãy Fibonacci. Ta cĩ Fn = n n 1 1 5 1 5 2 25     + −  −          suy ra |Sn| = n 2 n 2 1 1 5 1 5 2 25 + +    + −  −          . Mà tập nS∅ ⊄ nên số tập con cần tìm bằng n 2 n 2 1 1 5 1 5 2 25 + +    + −  −          - 1. Bài tốn 3.17. (VMO 1996) Cho n, k, m *∈
thỏa mãn điều kiện 1 1. Hỏi cĩ bao nhiêu chỉnh hợp khơng lặp chập k: (a1, a2, ..., ak) của n số nguyên dương đầu tiên mà mỗi chỉnh hợp đĩ đều thỏa mãn ít nhất một trong hai điều kiện: (1) { }i, j 1,2,...,k sao cho i aj (2) { } ii 1,2,...,k i sao cho a∃ ∈ − khơng chia hết cho m Lời giải: Đặt A là tập gồm các chỉnh hợp chập k của n lấy từ tập {1, 2, ..., n}. Ta cĩ: |A| = knA . A* là tập gồm các chỉnh hợp thỏa mãn giả thiết. B = { }1 2 k 1 2 k i(a ,a ,...,a ) A | a a ... a i) m 1, k , (a i = ∈ < < < − ∀M Dễ thấy A* = A\B. • Xét ánh xạ f: 1 2 k 1 2 k B' (a ,a ,...,a ) (a 1 m,a 2 2m,...,a k km) f: B → − + − + − +a Khi đĩ f là song ánh từ B đến B’ 22 với B’ = { }{ }1 2 k 1 2 k i i(b ,b ,...,b ) | b b ... b 1,2,...,n k km , m 1, k , b b i = < < < ∈ − + ∀M Do đĩ |B| = |B’| = kn k k m C − +   . (Vì B’ là tập các bộ gồm k phần tử khơng phân biệt thứ tự lấy từ tập các số nguyên dương khơng lớn hơn n k km− + và chia hết cho m nên số phần tử của tập B’ là |B’| = k k kn k km n k n kk k m m m C C C − + − −     + +           = = ). Vậy |A*| = |A| - |B| = knA - kn k k m C − +   . 3.2.2. Tính tổng tổ hợp và chứng minh đẳng thức tổ hợp Một ứng dụng khác của phương pháp song ánh là dùng để tính tổng các phần tử của một tập hợp nào đĩ. Cĩ thể xem như ý tưởng này đã được đề xuất ngay trong bài tốn quen thuộc: “Tính tổng 1 + 2 + ... + n”, với cách giải quyết tuyệt vời mà tương truyền là của Gauxơ. Ta cĩ thể diễn đạt lại cách tính đĩ như sau: Với mọi i S∈ ={1, 2, …, n}, xét ánh xạ f xác định như sau: f(i) = n + 1 – i. Rõ ràng f là một song ánh từ S vào S. Do đĩ: i S i S i S n(n 1)2 i (i f (i)) S .(n 1) n(n 1) i 2∈ ∈ ∈ + = + = + = + ⇒ =∑ ∑ ∑ Bài tốn 3.18. (VMO 2002) Cho tập S gồm tất cả các số nguyên thuộc [1, n] *(n )∈
. T là tập tất cả các tập con khác rỗng của S. Với mỗi X ∈ T, kí hiệu m(X) là trung bình cộng tất cả các phần tử thuộc X. Tính m = X T m(X) T ∈ ∑ . Lời giải: Xét ánh xạ f: { } T T X f (X) n 1 x | x X f: → = + − ∈a Dễ thấy f là song ánh nên X T X T m(X) m(f (X)) n 1 , X T m(X) m(f (X)) ∈ ∈ + = + ∀ ∈   =  ∑ ∑ Suy ra: [ ] X T X T 2 m(X) m(X) m(f (X)) T (n 1) ∈ ∈ ⇒ = + = +∑ ∑ Vậy: m = X T m(X) T ∈ ∑ = n 1 2 + . Bài tốn 3.19. (Olympic 30.4.2000) Hãy tính trung bình cộng tất cả các số N gồm 2002 chữ số thỏa mãn N M 99 và các chữ số của N thuộc {1, 2, 3, 4, 5, 6, 7, 8}. Lời giải: Gọi M là tập các số N thỏa mãn điều kiện đề bài. Xây dựng ánh xạ f như sau: Nếu N = 1 2 2002a a ...a thì f(N) = 1 2 2002b b ...b , với bi = 9 – ai , i 1,2002∀ = 23 Do N + f(N) = { 2002 99...9 cs 9 99M nên f : M → M là song ánh. (kí hiêu: cs là “chữ số”) Từ đĩ ta cĩ: { { 2002 2002N M N M N M 12 N (N f (N)) | M | 99...9 N | M | 99...9 2 cs 9 cs 9 = ∈ ∈ ∈ = + ⇒ =∑ ∑ ∑ Vậy trung bình cộng các số N là: { 2002N M 1 1N 99...9| M | 2 cs 9∈ =∑ = 200210 1 2 − Nhận xét 3.2: Cũng từ việc so sánh lực lượng các tập hợp, phương pháp song ánh là một cơng cụ đắc lực để xây dựng và chứng minh các cơng thức tổ hợp. Thơng thường người ta xây dựng một song ánh đi từ một tập vào chính nĩ, và ý tưởng cơ bản ở đây cĩ thể phát biểu như sau: “Khi đếm số phần tử của một tập hợp bằng nhiều cách thì các kết quả đếm thu được phải bằng nhau, cho dù với các cách đếm khác nhau ta thu được các biểu thức rất khác nhau”. Ta đi xét các bài tốn sau: Bài tốn 3.23. (Vơ địch Trung Quốc – 1994) Chứng minh rằng: n k n k k n2 n 2n 1n k k 0 2 C C C , n −    +  +− = = ∀ ∈∑
Lời giải: Ta chọn ra n số khơng lặp từ 2n+1 số, khi đĩ số cách chọn bằng n2n 1C + . Mặt khác, ta cĩ thể chọn chọn ra n số từ 2n + 1 số bằng cách khác như sau: Trước hết, từ 2n+1 số, ta chia ra n cặp và cịn lại một số gọi là a khơng thuộc n cặp đĩ. Sau đĩ ta thực hiện liên tiếp hai bước chọn như sau: Bước 1: Ta chọn ra k cặp từ n cặp ấy rồi từ mỗi cặp chọn ra một số. Trường hợp này cĩ tất cả k knC .2 cách chọn. Bước 2: Chọn n k 2 −     cặp trong n - k cặp cịn lại, ngồi ra, số a sẽ được chọn nếu n - k lẻ và khơng được chọn nếu n – k chẵn. Ở bước 1 cĩ 2k knC cách chọn và bước 2 cĩ n k 2 n kC −     − cách chọn và ta chọn được tổng cộng n số, trong đĩ k chạy từ 0 đến n. Vậy theo nhận xét 3.2 suy ra điều phải chứng minh. 3.3. MỘT SỐ ỨNG DỤNG CỦA HÀM SINH 3.3.1. Ứng dụng hàm sinh vào bài tốn tìm dãy số 3.3.1.1. Phương pháp • Để tìm dãy số {an}. Ta xét hàm sinh sinh bởi dãy {an} là F(x) = nn n 0 a x ≥ ∑ . • Dựa vào đặc điểm của dãy {an} và hệ thức truy hồi ta tìm hàm F(x). • Khai triển F(x) theo lũy thừa x (Khai triển Taylor), ta tìm được an với mọi n. 24 3.3.1.2. Bài tập ứng dụng Bài tốn 3.26. (Dãy Fibonacci) Tìm dãy số Fibonacci thỏa mãn điều kiện: n 2 n 1 n 0 1 F F F F 0,F 1 + += +  = = Lời giải: Xét hàm sinh F(x) sinh bởi dãy {Fn} tức là: F(x) = F0 + F1x + F2x2 + ... + Fn+2xn+2 + ... Áp dụng tính chất của hàm sinh: Nếu {an} ↔F(x) thì {an+h} ↔ 2 3 h 1 0 1 2 3 h 1 h F(x) a a x a x a x ... a x , x h − − − − − − − − ∈
Ta suy ra: {Fn+2}↔ 0 12 F(x) F F .x x − − = 2 F(x) x x − và {Fn+1}↔ 0F(x) F F(x) x x − = Vì n 2 n 1 nF F F+ += + nên 2 F(x) x x − = F(x) x + F(x) hay n n n 2 n 0 x 1 1 1 1 1 5 1 5F(x) ( ) x 2 21 x x 5 1 5 1 5 51 x 1 x 2 2 ∞ =     + − = = + = −     − − + −     − − ∑ Vậy Fn = n n 1 1 5 1 5 2 25     + −  −          . Bài tốn 3.31. Trên mặt phẳng kẻ n đường thẳng sao cho khơng cĩ 3 đường nào đồng qui và khơng cĩ 2 đường nào song song. Hỏi mặt phẳng được chia làm mấy phần? Gọi pn là số lớn nhất các phần mặt phẳng cĩ thể cĩ trên mặt phẳng được chia bởi n đường thẳng thỏa mãn điều kiện bài tốn. Nhận xét 3.5: Ví dụ này đã gặp ở phần trước và ta đã lập được cơng thức truy hồi cho pn là pn = pn-1 + n với p1 = 2, p0 = 1 và đã tìm được cơng thức tường minh cho pn bằng 2 cách. Bây giờ ta đi tìm cơng thức hiện của pn dưới cách nhìn từ hàm sinh. Lời giải: Hàm sinh cho dãy p1, p2, ... là p(x) = ii i 0 p x ∞ = ∑ = 2 0 1 2p p x p x ...+ + + (1) Nhân 2 vế của (1) với x ta cĩ x.p(x) = i 1 2 3i 0 1 2 i 0 p x xp p x p x ... ∞ + = = + + +∑ (2) Lấy (1) trừ (2) vế theo vế ta cĩ: p(x) - xp(x) = p0 + (p1 - p0)x + (p2 - p1)x2 + ... (3) mặt khác ta cĩ p0 = 1, pn – pn-1 = n, do vậy ta thay vào (3) ta cĩ (1 - x).p(x) = 1 + x + 2x2 + 3x3 + ... = 1 + x(1 + 2x + 3x2 + ...) = 1 + x. 2 1 (1 x)− 25 Suy ra: p(x) = 3 1 1 x. 1 x (1 x) +− − , khai triển lũy thừa vế phải ta được: p(x) = n 2 m n 2 m 1m 2 m 2 n 0 m 0 n 0 m 0 x x. C .x x C .x ∞ ∞ ∞ ∞ + + + = = = = + = +∑ ∑ ∑ ∑ = n 2 n n 2 n n 1 n 1 n 0 n 1 n 0 n 0 x C .x x C .x ∞ ∞ ∞ ∞ + + = = = = + = +∑ ∑ ∑ ∑ Suy ra hệ số của xn là pn = 1 + 2n 1C + = 2n(n 1) n n 21 2 2 + + + + = 3.3.2. Tính tổng tổ hợp và chứng minh đẳng thức tổ hợp 3.3.2.1. Phương pháp: Để tính tổng m m S(n) h (n)=∑ ta xét hàm sinh: n n m n n m F(x) = S(n).x = ( h (n)).x∑ ∑ ∑ (*) Sau đĩ sử dụng phương pháp đổi tổng để tính vế phải của (*) rồi đồng nhất thức hai vế ta thu được S(n). 3.3.2.2. Bài tập ứng dụng Bài tốn 3.32. Tính tổng sau: n k k m n k k m ( 1) C C = −∑ Lời giải: Đặt S(m) = n k k m n k k m ( 1) C C = −∑ Xét hàm sinh: F(x) = m m S(m).x∑ = n k k m m k k m m n k n k m 0 k m k n m k ( ( 1) C C ).x ( 1) C . C x ∞ = = ≤ ≤ − = −∑ ∑ ∑ ∑ = k k k n n k k k n n n n n n k n k n ( 1) C .(1 x) ( 1) ( 1) C .(1 x) ( 1) ( 1 1 x) ( 1) x− ≤ ≤ − + = − − + = − − + + = −∑ ∑ Đồng nhất thức ta cĩ: n(-1) khi m = nS(m) 0 khi m < n  =   Bài tốn 3.34. Hãy tính tổng sau: f(n) = n 2k n k n k k 0 C 2 −+ = ∑ Lời giải: Gọi F(x) là hàm sinh của dãy {f(n)}. Ta cĩ F(x) = n n 0 f (n)x ≥ ∑ suy ra: F(x) n n n 2k n k n k 2k n n k k 2k n k n k n k n k n 0 k 0 k 0 n 0 k 0 n 0 C 2 .x 2 . C 2 x 2 .(2x) . C (2x)− − − − ++ + + ≥ = = ≥ = ≥ = = =∑∑ ∑ ∑ ∑ ∑ n k k 2k n k n k 2k 1 (n k) 1 k 0 n k 0 2 .(2x) .(2x) C (2x)− − − −+ + − − = − ≥ =∑ ∑ = n k k 2k 1 k 0 12 .(2x) . (1 2x) − + = − ∑ 26 k 2 k 0 2 1 x 1 1 . x1 2x 1 2x(1 2x) 1 (1 2x) ≥   = =  − − −  − − ∑ = 1 2x (1 4x)(1 x) − − − n n 2n 1 n n 0 n 0 n 0 2 1 1 12 (4x) x (2 1)x 3(1 4x) 3(1 x) 3 3 + ≥ ≥ ≥   = + = + = +  − −   ∑ ∑ ∑ = n n 0 f (n)x . ≥ ∑ Vậy: f(n) = 2n 12 1 3 + + (n ≥ 0). KẾT LUẬN Luận văn đã trình bày một cách cĩ hệ thống tổng quan về lý thuyết tổ hợp. Cũng như đã chọn những ví dụ phù hợp và khá phong phú để làm rõ phần lý thuyết đã trình bày. Đặc biệt ở chương hai, Chúng tơi đã đi nghiên cứu, chứng minh một cách chi tiết các định lý tổng quát về nguyên lý bù trừ, hệ thức truy hồi cũng như lý thuyết về hàm sinh. Trên cơ sở đĩ xây dựng một hệ thống phương pháp giải các dạng tốn tổ hợp liên quan ứng dụng phần lý thuyết đã nêu ra. Đặc biệt luận văn cịn đề xuất một phương pháp giải bài tốn đếm tổ hợp nâng cao ứng dụng một phương pháp khá đặc sắc đĩ là phương pháp song ánh. Ở chương ba, chúng tơi đã nghiên cứu và đưa ra một số dạng tốn ứng dụng đa dạng cho những lý thuyết đã được trình bày trong chương hai. Đồng thời luận văn đã nêu lên được mối quan hệ giữa hệ thức truy hồi và hàm sinh. Kết quả của luận văn nhằm nâng cao chất lượng dạy và học tốn tổ hợp nĩi riêng và tốn rời rạc nĩi chung, nhằm phát triển tư duy tốn học cho học sinh phổ thơng và đặc biệt là học sinh chuyên tốn cĩ một tư liệu để tham khảo bổ ích, bởi vì tổ hợp được xem là mơn học khĩ cho học sinh ở cấp học này. Cuối cùng, chúng tơi xin được nêu lên một số vấn đề cĩ thể được mở rộng nghiên cứu tiếp theo trong tương lai đĩ là: (1) Lý thuyết về hệ thức truy hồi tuyến tính bậc k bất kì với hệ số biến thiên cho đến nay vẫn chưa hồn chỉnh, cũng như lý thuyết về các dạng hệ thức truy hồi khác. (2) Ứng dụng hàm sinh và hệ thức truy hồi để giải các bài tốn liên quan đến độ phức tạp của thuật tốn cũng như giải các bài tốn trong lĩnh vực tin học. (3) Ứng dụng của hàm sinh để giải các bài tốn rất hay gặp trong các kỳ thi vơ địch tốn đĩ là bài tốn phân hoạch tập hợp và phân hoạch số nguyên.