›

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

pdf 26 trang yendo 4280
Download
Bạn đang xem 20 trang mẫu của tài liệu "Tóm tắt luận án Bài toán đếm nâng cao trong tổ hợp và ứng dụng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdftom_tat_luan_an_bai_toan_dem_nang_cao_trong_to_hop_va_ung_du.pdf

Nội dung text: Tóm tắt luận án Bài toán đếm nâng cao trong tổ hợp và ứng dụng

  1. 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. 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. 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. 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. 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 k k định b ởi cơng th ức sau: An = AR(n, k) = n . 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: x 1 + x2 + x3 + x4 = 11 với xi 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ĩ x 1 ph ần t ử lo ại 1, x 2 ph ần t ử lo ại 2, x 3 ph ần t ử lo ại 3, x 4 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 {S1 , S 2 , , S k }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 n1 , n 2 , , n k th ỏa n1 n 2 n k r. Số các phân ho ạch th ứ t ự t ổ h ợp ch ập r c ủa X d ạng {S1 , S 2 , , S k } cĩ
  6. 6 = = = S1122 n,S n, ,S kk n, được kí hi ệu là C(n; n1 ,n 2 , ,n k ) . 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 n1 ph ần t ử t ừ X cho S1, cĩ C( n, n 1 ) kh ả n ăng. − Bước 2: Ch ọn n2 ph ần t ử t ừ X\S1 cho S2 , cĩ C( n n,n1 2 ) kh ả n ăng. ∪ ∪ ∪ Bước k: Ch ọn nk ph ần t ử t ừ X\(S1 S 2 S k1− ) cho Sk , cĩ − − −− C( n n1 n 2 n k1k− ,n ) kh ả n ăng. Theo nguyên lý nhân suy ra: − − − −− C(n; n1 ,n 2 , ,n k ) = C( n,n 1).C( n n,n1 2 ) C( n n1 n 2 n k1k− ,n ) n! = =P(n;n ,n , , n ,n − r). − 1 2 k n1 !n 2 ! n k !(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 n! C(n;n ,n , ,n ) = =P(n;n ,n , n ,n − r); C(n;n ,n , ,n ) 1 2 k − 1 2 k 1 2 k n1 !n 2 ! n k !(n r)! đượ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à: 17! C(17;4,3,3,4,1) = = 8576568000. 4!3!3!4!1! 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 + ++ = n1 ,n 2 , ,n k và p1 ,p 2 , ,p k th ỏa np11 np 22 np kk n. Một h ệ th ống các t ập con c ủa X v ới p1 tập l ực l ượng n1 , p2 tập l ực l ượng n2 , , pk tập l ực l ượng nk 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 p1 tập l ực l ượng n1 , p2 tập l ực lượng n2 , , pk tập l ực l ượng nk là: C(n;n, ,n,n, ,n, ,n, ,n) n! 1 12 2 k k = p1 p 2 p k p1 !p 2 ! p k ! p11 !(n !) p 22 !(n !) p kk !(n !) Trong t ử s ố C(n; n1 , , n 12 , n , , n 2 , , n k , , n k ) số n1 l ặp l ại p1 l ần, n2 l ặp l ại p2 l ần, , nk l ặp l ại pk 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 n1 v ật, h ộp 2 ch ứa n2 v ật, , h ộp m ch ứa nm v ật: n1 n 2 n m n
  7. 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 n1 ph ần t ử t ừ n c ầu cho hộp 1, cĩ C( n,n 1) cách − Bước 2: Ch ọn n2 ph ần t ử t ừ n - n1 cho hộp 2, cĩ C( n n,n1 2 ) cách − − −− Bước m: Ch ọn nm ph ần t ử t ừ n n1 n 2 n m1− cho h ộp m, cĩ − − −− C( n n1 n 2 n m1m− ,n ) kh ả n ăng. Theo nguyên lý nhân suy ra số cách phân ph ối là: − − − −− n! C( n,n 1) .C( n n,n1 2 ) .C( n n1 n 2 n m1m− ,n ) = . n1 !n 2 ! n m ! 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 A 1, A 2, , A n ta cĩ định lý tổng quát sau: Định lý 2.1: Với n t ập h ợp A 1, , A n b ất k ỳ ta cĩ cơng th ức n ∪ ∪ A∩ A n-1 ∩ ∩ ∩ |A1 An| = ∑ Ai - ∑ |i j | + + (-1) |A 1 A2 An| (1) i=1 1i≤ < j ≤ n Hay ta cĩ th ể phát bi ểu cách khác nh ư sau: n-1 | A 1 ∪ A 2 ∪ ∪ A n| = N 1 − N 2 + N 3 − + ( −1) Nn trong đĩ N m (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à: N m = |A∩ A ∩ ∩ A | ∑ i1 i 2 i m ≤< << ≤ 1i1 i 2 i m n 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 A i là t ập h ợp các cách x ếp cĩ quân xe n ằm ở ơ (i, i). Ta c ần tìm |A 1∪ ∪A8|. Nh ưng d ễ dàng th ấy r ằng |A i| = 7!, |A i∩Aj| = 6! , , |A 1∩ ∩A8| = 1 nên t ừ định lý trên ta suy ra: 1 2 3 8 8! 8! 8! |A 1 ∪ ∪ A 8| = C .7! - C .6! + C .5! - - C .0! = 8!− + − − . 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! 1 1 1 8! – ( 8!− + − − ) = 8! ( − + + ) 2! 3! 8! 2! 3! 8! 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 A 1 = {k ∈ S: k chia h ết cho 2}, A 2 = {k ∈ S: k chia h ết cho 3}, A 3 = {k ∈ S: k chia h ết cho 5}, A 4 = {k ∈ S: k chia h ết cho 7}. ∪ ∪ ∪ Khi đĩ A1 A 2 A 3 A 4 là t ập các s ố chia h ết cho ít nh ất m ột trong các s ố 2, 3, 5, 7. 280  280  280  280 Ta cĩ: |A|== 140;|A| == 93;|A| == 56;|A| == 40 ; 12 2  3 3  5 4  7 280  280  280 |A∩= A| = 46;|A ∩= A| = 28;|A ∩= A| = 20; 122.3 13  2.5 14  2.7 280  280  280 |A∩= A| = 18;|A ∩= A| = 13;|A ∩= A| = 8; 2315 24  21 34  35 280  280 |AA∩∩= A| = 9;|AA ∩∩= A| = 6; 12330 124  42 280  280 |AA∩∩= A| = 4;|A ∩∩= A A| = 2; 13470 234  105 280  |A∩∩∩= A A A| = 1. 1 2 3 4 210  ∪ ∪ ∪ Do đĩ theo nguyên lý bù tr ừ ta cĩ | A1 A 2 A 3 A 4 | = 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ì a 1, a 2 ∈A mà a 1 ≠ a 2 thì f(a 1) ≠ f(a 2), tức là f(a 1) = f(a 2) ⇔ a1 = a 2. • Á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. 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 ử F k là t ập h ợp t ất c ả các b ộ (A 1, A 2, , A k), trong đĩ A i (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: Sk∑ | A 12 A A k | (1) ∈ (A12 ,A , ,A k ) F k 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 S k thơng qua vi ệc tính T(i, k) là s ố các b ộ: ∈ ∪ ∪∪ = (A 1, A 2, , A k) F, sao cho A1 A 2 A k i tuy nhiên v ới m ột cách nhìn khác nh ư sau: Với i ph ần t ử n 1, n 2, , n i thu ộc {1, 2, , n} ta đếm xem cĩ bao nhiêu b ộ ∪ ∪ ∪ (A 1, A 2, , A k) th ỏa mãn điều ki ện A1 A 2 A k = {n 1, n 2, , n i} (2), t ừ đĩ tính được T(i, k) và S k. Ta cho các ph ần t ử n 1, n 2, , n i “ đă ng ký” cĩ m ặt trong các t ập h ợp A i theo qui tắc: n ếu, ch ẳng h ạn n 1 đă ng kí cĩ m ặt trong A 1, A 2 và khơng cĩ m ặt trong các t ập cịn lại thì phi ếu đă ng kí c ủa n 1 được ghi là (1, 1, 0, 0, , 0), cịn n ếu n 1 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 A1 A 2 A k ). Với i phi ếu đă ng kí c ủa n 1, n 2, , n i ta l ập được 1 b ộ (A 1, A 2, , A k). D ễ th ấy rằng v ới hai b ộ phi ếu đă ng kí khác nhau, ta cĩ hai b ộ t ập h ợp (A 1, A 2, , A k) khác nhau và nh ư v ậy s ố b ộ (A 1, A 2, , A k) th ỏa mãn (2) b ằng s ố b ộ phi ếu đă ng kí h ợp l ệ. Vì phi ếu đă ng kí c ủa n p, p = 1, 2, , i g ồm k s ố 0 ho ặc 1 và ph ải cĩ ít nh ất m ột s ố 1 k nên n p cĩ 2 – 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 ả (2 k – 1) i b ộ phi ếu đă ng kí h ợp l ệ khác nhau. Cu ối cùng, chú i ý r ằng cĩ Cn cách ch ọn i ph ần t ử n1, n 2, , n i từ n ph ần t ử nên ta cĩ: n n i k− i =i k − i k k(n-1) T(i, k) = Cn (2 1) suy ra: Sk = ∑iT(i,k) ∑ iCn (2 1) = n(2 – 1).2 . i0= i0 = (nh ờ khai tri ển (1 + x) n và l ấy đạo hàm, cho x = 2 k – 1 và nhân hai v ế v ới 2 k – 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. 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 ố {a n} là cơng th ức bi ểu di ễn a n qua m ột hay nhi ều s ố h ạng đi tr ước c ủa nĩ, c ụ th ể là a 0, a 1, a 2, , an-1 v ới n ≥ n 0 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 = F n-1 + F n-2 v ới n ≥ 3 và F1 = F 2 = 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 s n 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ĩ s n-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. 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ĩ s n-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 s n-1 + 1 + s n-1 = 2.s n-1 + 1 phép chuy ển. V ậy ta cĩ cơng th ức truy h ồi c ủa dãy s ố s 0, s 1, s 2, là: sn = 2.s n-1 + 1 và s 1 = 1 (s 2 = 3, s 3 = 7). 2 2 Ta cĩ: sn = 2s n-1 + 1 = 2(2s n-2+1) + 1 = 2 .s n-2 + 2 + 1= 2 (2s n-3 +1)+2+1 3 2 n-1 n-2 n-3 = 2 sn-3 + 2 + 2 + 1= = 2 .s 1 + 2 + 2 + + 2 + 1 − 1− 2 n 1 = 2 n-1 + 2 n-2 + 2 n-3 + + 2 + 1 = 2. +=−++ 1 2 2n 1 = 2 n – 1. 1− 2 Ví d ụ 2.23. (Olympic Bungari, 1995) Cho s ố nguyên n ≥ 2. Hãy tìm s ố các hốn v ị (a 1, a 2, , a n) 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 a i > a i+1 . Lời gi ải: Gọi S n 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à a n = n là S n-1 (Bởi vì S n-1 là s ố các hốn v ị (a 1, a 2, , a n-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 a i > a i+1 ). Cịn s ố các i− 1 hốn v ị (a 1, a 2, , a n) th ỏa mãn điều ki ện bài tốn với a i = n (1 ≤ i ≤ n-1) là Cn− 1 . n− 1 n i− 1 = n-1 i1−= n1 − Do đĩ: S n = S n-1 + ∑Cn− 1 S n-1 +2 – 1. (Do ∑Cn− 1 2 ). i= 1 i= 1 n Hi ển nhiên: S 2 = 1, tươ ng t ự ví d ụ 2.22 ta sẽ cĩ: S n = 2 - 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: a n = c 1(n). an-1 + c 2(n). an-2 + + c k(n). an-k + f(n) (T) trong đĩ c 1(n), c 2(n), , c k(n) và f(n) là các hàm theo n và c k(n) ≠ 0 v ới ∀n • Với h ệ th ức truy h ồi (T) thì h ệ th ức truy h ồi sau an = c 1(n). an-1 + c 2(n). an-2 + + c k(n). an-k (T 0) đượ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 c i(n) = c i , i = 1, 2, , k , đều là các h ằng s ố, c k(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à (T 0) 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: a 0 = C 0, a 1 = C 1, a 2 = C 2, ∗ Ph ươ ng trình đặc tr ưng c ủa h ệ th ức truy h ồi (T 0) cĩ h ệ s ố h ằng: k k-1 k-2 r − c 1r − c 2r − − c k-1r – c k = 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 (T 0), 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 (T 0).
  12. 12 ∗ Các định lý sau ta xét các h ệ th ức truy h ồi (T) và (T 0) ở trên v ới h ệ s ố h ằng: Định lý 2.3: N ếu a 1, a 2, , a m là các nghi ệm c ủa (T 0) thì a = c 1a1 + c 2a2 + + c mam (v ới c 1, c 2, , c m là các h ằng s ố tùy ý) c ũng là nghi ệm c ủa h ệ th ức truy h ồi (T 0). Đị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ì r n, nr n, 2 n m-1 n 2 m-1 n n r , , n r là các nghi ệm c ủa (T 0), và khi đĩ (c 0+c 1n+c 2n + + c m-1n ) .r , (c 0, c1, , c m-1 là các h ằng s ố tùy ý) cũng là nghi ệm c ủa (T 0). Hệ qu ả 2.1: Nếu r 1, r 2, , r q t ươ ng ứng là các nghi ệm b ội m 1, m 2, , m q (m i ≥1, i = 1, 2, , q) c ủa ph ươ ng trình đặc tr ưng (1), thì nghi ệm t ổng quát c ủa (T 0) cĩ d ạng: an = a 1(n) + a 2(n) + + a q(n), trong đĩ: − 2 mi 1 n ai(n) = (C i,0 + nC i,1 + n Ci,2 + + n .C − ). r , ∀i = 1,2, ,q i,mi 1 i Với C i,j , j = 0, 1, 2, , m i-1 , là các h ằng s ố b ất k ỳ. Hệ qu ả 2.2: Cho c 1, c 2, , c k là các s ố th ực. Gi ả s ử r ằng ph ươ ng trình đặc tr ưng k k-1 k-2 r − c 1r − c 2r − − c k-1r – c k = 0 cĩ k nghi ệm phân bi ệt r 1, r 2, , r k (cĩ th ể ph ức). Khi đĩ dãy {a n} là nghi ệm c ủa h ệ th ức truy h ồi (T 0) thì nghi ệm đĩ cĩ d ạng n n n an = α1r1 + α2r2 + + αkrk , 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 a n = h n + g n Trong đĩ g n là m ột nghi ệm riêng nào đĩ c ủa (T) và h n là nghi ệm t ổng quát c ủa h ệ th ức truy h ồi tuy ến tính thu ần nh ất (T 0) ứ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.a n-1 + C2.a n-2 + + Ck.a n-k = f(n) (T) trong đĩ f(n) = P s(n) (là đa th ức b ậc s c ủa n) k k-1 k-2 Ph ươ ng trình đặc tr ưng c ủa (T) là: r + C1r + C2r + + 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 an = Q s(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) * m cĩ d ạng an = n .Q s(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 + C 1.a n-1 + C 2.a n-2 + + C k.a n-k = f(n) (T) n trong đĩ f(n) = P s(n). β (là đa th ức b ậc s c ủa n, và β là m ột h ằng s ố) k k-1 k-2 Ph ươ ng trình đặc tr ưng c ủa (T) là: r + C 1r + C 2r + + C k-1r + C k = 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 * β n (T) cĩ d ạng an = Q s(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 * m β n của (T) cĩ d ạng an = n .Qs(n). (trong đĩ Qs(n) là đa th ức cĩ b ậc s).
  13. 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: a n = C1.a n-1 + C2.a n-2 + + Ck.a n-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) = p 1(n) + p 2(n) + + p m(n) thì nghi ệm riêng c ủa (T) cĩ d ạng gn = f 1(n) + f 2(n) + + f m(n), trong đĩ f i(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.a n-1 + C2.a n-2 + + Ck.a n-k + f i(n), i= 1,m . n n Ví d ụ 2.33. Gi ải cơng th ức truy h ồi a n = 4a n-1 – 4a n-2 + n2 + 3 + 4 , n ≥ 2 (T) Lời gi ải: n n • Ph ươ ng trình thu ần nh ất t ươ ng ứng cĩ nghi ệm t ổng quát là h n = c 1.2 + c 2.n2 • Ta cĩ thành ph ần khơng thu ần nh ất là f(n) = n2 n + 3 n + 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: n n an = 4a n-1 – 4a n-2 + 4 ; a n = 4a n-1 – 4a n-2 + 3 ; a n = 4a n-1 – 4a n-2 + n2 * V ới h ệ th ức a n = 4a n-1 – 4a n-2 + 4 (T 1) n Ta cĩ thành ph ần khơng thu ần nh ất là f 1(n) = 4 = 4.1 và do 1 khơng là nghi ệm c ủa n ph ươ ng trình đặc tr ưng nên nghi ệm riêng c ủa (T 1) cĩ d ạng c.1 , thay vào (T 1) ta được c = 4. V ậy nghi ệm riêng c ủa (T 1) là 4. n * V ới h ệ th ức a n = 4a n-1 – 4a n-2 + 3 (T 2) n n Ta cĩ thành ph ần khơng thu ần nh ất là f 2(n) = 3 = 1.3 và 3 khơng là nghi ệm c ủa n ph ươ ng trình đặc tr ưng nên nghi ệm riêng c ủa (T 2) cĩ d ạng c.3 , thay vào (T 2) ta được c = 9. n Vậy nghi ệm riêng c ủa (T 2) là 9.3 . n * V ới h ệ th ức a n = 4a n-1 – 4a n-2 + n2 (T 3) n Ta cĩ thành ph ần khơng thu ần nh ất là f 3(n) = n.2 và 2 là nghi ệm b ội 2 c ủa ph ươ ng 2 n trình đặc tr ưng nên nghi ệm riêng c ủa (T 3) cĩ d ạng n (c 1n + c 2)2 , thay vào (T 3) ta cĩ: 2 n 2 n-1 2 n-2 n n (c 1n + c 2)2 = 4 ()n− 1 [c 1(n - 1) + c 2]2 - 4 ()n− 2 [c 1(n - 2) + c 2]2 + n2 chia c ả hai v ế cho 2 n-2 sau đĩ khai tri ển và cân b ằng h ệ s ố (c ủa đa th ức ẩn n) ta được: 1 1 2 1 1 n c1 = , c 2 = . V ậy nghi ệm riêng c ủa (T 3) là n ( n + )2 . 6 2 6 2 Từ ba tr ường h ợp trên suy ra nghi ệm riêng c ủa h ệ th ức truy h ồi (T) là n 2 1 1 n gn = 4 + 9.3 + n ( n + )2 . 6 2 n n n 2 1 1 n Vậy nghi ệm t ổng quát c ủa (T) là: an = c 1.2 + c 2.n2 +4 + 9.3 + n ( n + )2 . 6 2
  14. 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 n Cho dãy s ố {a n}. Chu ỗi l ũy th ừa hình th ức vơ h ạn F(x) = ∑ an x gọi là hàm sinh n ≥ 0 th ường sinh b ởi dãy s ố {a n}. Kí hi ệu: {a n} ↔F(x) hay {a n} ↔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); x 0∈(a, b). Khi f(n) (x) đĩ ta cĩ cơng th ức khai tri ển Taylor: f(x) = ∑ 0 xn . n≥ 0 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 αα− α− +  ( 1) ( k 1) > k k  , k 0 mở r ộng Cα được định ngh ĩa nh ư sau: Cα =  k! 1, k= 0 ∞ α k k • Cho x là s ố th ực v ới |x| < 1 và α là m ột s ố th ực. Lúc đĩ: (1+ x) = ∑ Cx.α k= 0 α αα−( 1) αα− ( 1) ( α−+ n 1) Tức là: (1+=+α+ x) 1 x x2 ++ xn + 2 n! 2.4.4. Tính ch ất của hàm sinh Cho {a n} ↔F(x) , {b n} ↔G(x) khi đĩ ta cĩ các tính ch ất sau: (1) {a n ± b n}↔F(x) ± G(x) (2) {ka n}↔kF(x) , ∀k∈R (3) {(n+1)a n+1 } ↔ F’(x) (4) {a n-an-1} ↔ (1-x)F(x) (5) {na n} ↔ xF’(x) −− −2 − 3 −− h1− F(x) a012 ax ax ax 3 a h1− x (6) {a n+h } ↔ , h ∈ N xh (7) {k.a n ± h.b n}↔k.F(x) + h.G(x) F(x) (8) {a 0+a 1+a 2+ +a n} ↔ 1− x n ↔ (9) {c n} = { ∑ ai b j } = { ∑ak b n− k } F(x).G(x) i+ j = n k= 0
  15. 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 (1) =++1 x x2 ++ x k + 1− x 1 (2) = 1 – x + x 2 – x 3 + 1+ x 1 (3) = 1 + ax + a 2x2 + a 3x3 + + a nxn + 1− ax n +1 + 22 ++ nn (4) (1 + x) = 1 Cxn Cx n Cx n ∞ 1 − n(n+ 1) n(n + 1)(n + 2) (5) = Cn 1 x k = 1++ nx x2 + x 3 + − n ∑ n+ k − 1 (1 x) k= 0 2 3! k x + + (6) =xk()1 +++=+ x x 2 x kk1k2 x + x + 1− x + 1− x k 1 (7) =+1 x + x2 + + x k 1− x 1 (8) =+1 x2 + x 4 + x 6 + 1− x 2 x (9) =x(1 ++++=++++ x246 x x ) x x 357 x x 1− x 2 1 (10) =+1 2x + 3x2 + + (n+1)x n + (1− x) 2 1+ x (11) =++1 3x 5x2 ++ (2n + 1)x n + (1− x) 2 x+ x 2 (12) =+x 4x2 + 9x 3 ++ nx 2n + (1− x) 3 x2 x 3 x n (13) ex =++ 1 x + ++ xn + 2! 3! n! x2 x 3 x n (14) −ln(1 −=++++ x) x xn + 2 3 n ∞ +n = kkk (15) (1 ax)∑ Cn a x n= 0 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 x n 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↔+ 01 ++ kk =+ k {Ck } C kk C x C k x (1 x)
  16. 16 n k n Nh ư v ậy h ệ s ố c ủa x trong (1 + x) là Ck b ằng s ố cách ch ọn n ph ần t ử phân 2 2 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 x là Cn , 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 x k+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 1 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à . (1− x) n 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 Cn+ k − 1 . Một cách ti ếp c ận khác, ta l ập lu ận nh ư sau: n 1 Với k > 0, ta cĩ {C+ − , n= 0, 1, 2, } ↔F(x) = n k 1 (1− x) k 1 1  k Th ậy v ậy, ta cĩ =   = ( 1 + x + x 2 + x 3 + )k (1− x) k 1− x  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 x n s ẽ b ằng s ố nghi ệm nguyên khơng âm c ủa ph ươ ng trình: n x1 + x 2 + + x k = n. Ta đã bi ết s ố nghi ệm c ủa ph ươ ng trình này b ằng: Cn+ k − 1 . Nh ư vậy h ệ s ố c ủa x n 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 + x 2 + x 3 + x4 + x 5)(1 + x + x 2)(1 + x + x 2 + x 3 ) Gi ả s ử xx1 ,x x 2 ,x x3 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 ≤ x 1 ≤ 5, 0 ≤ x 2 ≤ 2, 0 ≤ x 3 ≤ 3. Khi khai tri ển v ế ph ải n n các th ừa s ố này s ẽ cho ta s ố h ạng x , v ới n = x 1 + x 2 + x 3. Nh ư th ế h ệ s ố c ủa x trong F(x) s ẽ là số nghi ệm nguyên khơng âm c ủa ph ươ ng trình x 1 + x 2 + x 3 = n th ỏa mãn: 0 ≤ x 1 ≤ 5, 0 ≤ x 2 ≤ 2, 0 ≤ x 3 ≤ 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. 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 1 Nh ư th ế ta cĩ hàm sinh cho s ố cách ch ọn táo là A(x) = 1 + x 2 + x 4 + = . 1− x 2 1 Tươ ng t ự, hàm sinh cho s ố cách ch ọn chu ối là B(x) = 1 + x 5 + x 10 + = . 1− x 5 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 1− x 5 khơng th ể chọn h ơn 4 qu ả cam, vì th ế ta cĩ C(x) = 1 + x + x 2 + x 3 + x 4 = . 1− x 1− x 2 Và t ươ ng t ự, hàm sinh cho s ố cách ch ọn đào là D(x) = 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 1 11x1x−5 − 2 1 A(x).B(x).C(x).D(x)= . . . = =++++ 1 2x 3x2 4x 3 1x1x−2 − 51− x 1 − x (1x) − 2 1 Gần nh ư t ất c ả được gi ản ước v ới nhau! Ch ỉ cịn l ại mà ta đã tìm được chu ỗi (1− x) 2 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 + x 2 + x 3 + + x k = n Lời gi ải: Hàm sinh c ần tìm là: k k 2 4 6 k x  x f(x) = (x + x 3 + x 5 + x 7 + ) k = x( 1 + x + x + x + )  =   = .   1− x 2  (1− x2 ) k
  18. 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). bn− 1 n Cho dãy s ố (b n) xác định b ởi h ệ th ức sau: b 0 = 0, b n = +( − 1) , n ≥ 1 . 2004 2 Tính lim b n . n→+∞ 1 1 Lời gi ải: Ph ươ ng trình đặc tr ưng r - = 0 ⇔ r = 2004 2004 1  n Nghi ệm t ổng quát c ủa h ệ th ức truy h ồi thu ần nh ất t ươ ng ứng là bC.=   . n 1 2004  n * n f(n) = (-1) nên ch ọn bn = C 2.(-1) . Thay vào h ệ th ức truy h ồi ở đề bài ta được: 2004 * 2004 n C2 = ⇒ b = .(-1) . 2005 n 2005 n 1  2004 n ⇒ Cơng th ức t ổng quát c ủa dãy s ố c ần tìm là b n = C .   + .()−1 . 1 2004  2005 2004 2004 Đề cho b 0 = 0 ⇒ 0 = C + ⇒ C = − 1 2005 1 2005 Vậy cơng th ức t ổng quát c ủa dãy s ố c ần tìm là: n ()−n − − 2004 1  2004 − n − 2004 1 bn = .  + .()1 = − . 2005 2004  2005 2005.() 2004 n 1 2 2 nn  n n  2 ()−1 2004 − 1() − 1 (2004) − 1 2004  Suy ra lim b 2 = lim = lim  =   . →+∞ n →+∞n1− →+∞ n1 − n n2005.() 2004  n 2005.() 2004  2005  Bài tốn 3.7. (IMO 1967) Trong m ột cu ộc thi đấu th ể thao cĩ m huy ch ươ ng, được 1 phát trong n ngày thi đấu. Ngày th ứ nh ất, ng ười ta phát m ột huy ch ươ ng và s ố huy 7 1 ch ươ ng cịn l ại. Ngày th ứ hai, ng ười ta phát hai huy ch ươ ng và huy ch ươ ng cịn 7 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 a k là s ố huy ch ươ ng cịn l ại tr ước ngày th ứ k, suy ra a 1 = m và ta cĩ:
  19. 19 1 6 6k 1 ak+1 = ak – k - (a k – k) = a - (Do ngày th ứ k phát đi k huy ch ươ ng và huy 7 7k 7 7 − 6  k 1 ch ươ ng cịn l ại). Gi ải h ệ th ức truy h ồi này ta được: a=  (m36) −−+ 6k 42 . k 7  − − 6 n 1 7  n 1 Theo gi ả thi ết ta cĩ a n = n =   (m− 36) − 6n + 42⇒ m− 36 = 7(n − 6)   7  6  Vì m – 36 ∈ và (6, 7) = 1, 6 n-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 a=α , b =β  1 1 = + α β Xét hệ: an1+ pa n qb n , với , , p, q, r, s là các h ằng s ố th ực.  = + bn1+ ra n sb n Gi ải h ệ trên là đi xác định số h ạng t ổng quát c ủa các dãy s ố (a n) và (b n) 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ĩ: =+=++=++ − an2++++ pa n1 qb n1 pa n1 q(ra n sb) n pa n1 + qra n s(a n1 + pa) n =+ + − Suy ra an2+ (p s)a n1 + (qr ps)a n = + α + β Mặt khác t ừ h ệ trên ta l ại cĩ a2 pa 1 qb 1 = p q Vậy ta cĩ h ệ th ức truy h ồi tuy ến tính thu ần nh ất c ấp hai là =+ +− =α =α+β an2+ (p s)a n1 + (qr ps)a,a n1 ,a 2 p q Mà ta đã bi ết cách gi ải. T ừ đĩ ta tìm được a n , th ế vào h ệ trên và thu được b n. 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 px+ q Cho dãy s ố (x ) xác định b ởi x = n , trong đĩ: x = a cho tr ước và p, q, r, s n n+ 1 + 0 rxn s là các h ằng s ố. Tìm s ố h ạng t ổng quát xn . Gi ả s ử y n và z n là nghi ệm c ủa h ệ: y+ = py + qz  n1 n n , y = a, z = 1. = + 0 0 zn1+ ry n sz n = yn = y0 a = Khi đĩ xn là nghi ệm c ủa h ệ th ức truy h ồi đã cho. Th ật v ậy, x0 = a zn z0 1 y pn + q y py+ qzz px + q đúng. Ta l ại cĩ: x ==n1nn+ =n = n đúng. n+ 1 +y + zn1nn+ ry szrn + s rx n s zn
  20. 20 3.1.3.2. Dạng 2 u .u Cho dãy s ố (u ) xác định b ởi u=α , u =β và u = n− 1 n (1) n 1 2 n+ 1 + aun− 1 bu n Tìm s ố h ạng t ổng quát un . 1au+ bu 1 1 1 Bi ến đổi ()1⇒ =n− 1 n ⇔=+ a. b. un1+− u.u n1n u n1 + u n u n1 − = 1 − − = Đặt vn ta cĩ: vn1+ av n bv n1 − 0 ( Đây là h ệ th ức truy h ồi tuy ến tính thu ần un nh ất h ệ s ố h ằng). 3.1.3.3. Dạng 3 = +2 +∀≥ Cho dãy s ố (u n) xác định nh ư sau: un a.u n1− bu n1 − c , n 2 (2) u=α a 2 − = và 1 , b1. Tìm s ố h ạng t ổng quát un . ⇔ 2 2 ⇔−2 + 2 −= Ta cĩ: (2) (u n – au n-1) = b un− 1 + c un 2au nn1 u− u n1 − c 0 (3) 2− +−= 2 Thay n b ởi n – 1 ta cĩ: un2− 2auu n1n2 −− u n1 − c0 (4) Từ (3) và (4) ta cĩ u n và u n-2 là 2 nghi ệm c ủa ph ươ ng trình: 2− + 2 −= t 2aun1− .t u n1 − c 0 . Áp d ụng định lý Viet, ta cĩ: u n + u n-2 = 2a.u n-1. T ừ đĩ suy ra u n. 3.1.3.4. D ạng 4 =un− 1 ∀ ≥ Tìm dãy s ố (u n) xác định nh ư sau: un , n 2 (5) +2 + a c.un− 1 b = α α2 − = Với điều ki ện: u1 , > 0, a > 0, ab 1 ⇔1 = a ++ b = 1 Ta cĩ (5) c 2 và đặt xn ta được: un u n− 1 un− 1 un = +2 + xn a.x n1− b.x n1 − c đây là bài tốn d ạng 3, nên ta tìm được x n, từ đĩ suy ra u n. 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 S n = {M ⊂ S | M khơng ch ứa 2 s ố nguyên liên ti ếp nào}
  21. 21 ∈∀ ≠∀− Pn = {(a12 , a , , a ni ) | a {0, 1} i = 1, n; ( a ii1 , a+ ) (1, 1), i = 1, n 1} • Xét ánh x ạ f: f: Sn → P n a= 1 khi i ∈ M sao cho  i a = khi i ∉ M M (a,a, ,a)1 2 n ai 0 Dễ dàng ki ểm tra được r ằng f là song ánh nên |S n| = |P n|, ∀n ≥ 1 • Xét ánh x ạ g: g: Pn → P n-1 ∪ P n-2 ∀≥ n 3 (a,a, ,a− )∈ P − khi a = 0 (a ,a , ,a ) a  12 n1 n1 n 1 2 n ∈ = (a,a, ,a12 n2− ) P n2 − khi a n 1 Dễ dàng ki ểm tra được r ằng g là song ánh, P n và P n-1 là r ời nhau nên |P n| = |P n-1| + |P n-2| , ∀n ≥ 3 suy ra |S n| = |S n-1| + |S n-2| , ∀n ≥ 3 Vì |S 1| = 2 ; |S 2| = 3 nên |S n| = |F n+2 | ∀n ≥ 1 v ới {F n} là dãy Fibonacci. + n −  n  115 15  Ta cĩ F n =  −  suy ra 2 2  5     + + + n2 −  n2  115 15  |S n| =  −  . 2 2  5     n2+ n2 +  115+  15 −  Mà t ập ∅ ⊄ S nên s ố t ập con c ần tìm b ằng  −   - 1. n 2 2  5     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: (a 1, a 2, , a k) 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 a j ∃ ∈ − (2) i{ 1,2, ,k} sao cho a i i 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}. k Ta cĩ: |A| = An . A* là t ập g ồm các ch ỉnh h ợp th ỏa mãn gi ả thi ết. ∈ <<< −M ∀ B = { (a,a, ,a)12k A|a 12 a a ki , (a i) m i = 1,k } Dễ th ấy A* = A\B. • Xét ánh x ạ f: f: B → B' a −+ −+ −+ (a,a, ,a12k ) (a 1 1 m,a 2 2 2m, ,a k k km) Khi đĩ f là song ánh t ừ B đến B’
  22. 22 <<< ∈ −+M ∀ với B’ = { (b12k12 ,b , ,b ) | b b b ki , b{ 1,2, ,n k km} , b i m i = 1, k } k Do đĩ |B| = |B’| = Cn− k  . (Vì B’ là t ập các bộ g ồm k ph ần t ử khơng phân bi ệt th ứ +k m  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ố k= k = k ph ần t ử c ủa t ập B’ là |B’| = Cnkkm−+  C nk −  C nk − ). +k + k m  m  m * k k Vậy |A | = |A| - |B| = An - Cn− k  . +k m  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 đĩ: n(n+ 1) 2∑ i= ∑ (i + f(i)) = S.(n +=+ 1) n(n 1)⇒ ∑ i = i∈ S i ∈ S i∈ S 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à ∑ m(X) trung bình c ộng t ất c ả các ph ần t ử thu ộc X. Tính m = X∈ T . T Lời gi ải: Xét ánh x ạ f: f: T → T X a f(X)={} n +− 1 x|x ∈ X  + =+∀∈ m(X) m(f(X)) n 1, X T Dễ th ấy f là song ánh nên  m(X)= m(f(X))  ∑ ∑ XT∈ XT ∈ Suy ra: ⇒ 2∑ m(X)= ∑ [ m(X) + m(f(X))] =+ T(n 1) XT∈ XT ∈ ∑ m(X) n+ 1 Vậy: m = X∈ T = . T 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 = a1 a 2 a 2002 thì f(N) = b1 b 2 b 2002 , v ới b i = 9 – a i , i 1,2002
  23. 23 Do N + f(N) = 99 9{ M 99 nên f : M → M là song ánh. (kí hiêu: cs là “ch ữ s ố”) 2002 cs 9 1 Từ đĩ ta cĩ: 2∑ N = ∑ (N + f (N)) = | M | 99 9{ ⇒ ∑ N= | M | 99 9{ NMNM∈ ∈ 2002 cs 9N∈ M 2 2002 cs 9 1 1 102002 − 1 Vậy trung bình c ộng các s ố N là: ∑ N= 99 9{ = |M|N∈ M 2 2002 cs 9 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) −  n n k k k2  = n ∀ n ∈ + Ch ứng minh r ằng: ∑ 2CCnn− k C 2n1+ , k= 0 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 C2n+ 1 . 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 k k cĩ t ất c ả Cn .2 cách ch ọn. n− k  Bước 2: Chọn   c ặp trong n - k c ặp cịn l ại, ngồi ra, s ố a s ẽ được ch ọn n ếu 2  k k n - k l ẻ và khơng được ch ọn n ếu n – k ch ẵn. Ở b ước 1 cĩ 2 Cn cách ch ọn và b ước 2 n− k  2  cĩ Cn− k 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 • n Để tìm dãy s ố {a n}. Ta xét hàm sinh sinh b ởi dãy {a n} là F(x) = ∑an x . n≥ 0 • D ựa vào đặc điểm c ủa dãy {a n} 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 a n v ới m ọi n.
  24. 24 3.3.1.2. Bài t ập ứng d ụng Bài tốn 3.26. (Dãy Fibonacci) F+= F + + F Tìm dãy s ố Fibonacci th ỏa mãn điều ki ện:  n2 n1 n = = F0 0,F 1 1 Lời gi ải: Xét hàm sinh F(x) sinh b ởi dãy {F n} t ức là: 2 n+2 F(x) = F 0 + F 1x + F 2x + + F n+2 x + Áp d ụng tính ch ất c ủa hàm sinh: N ếu {a n} ↔F(x) thì −− −2 − 3 −− h1− F(x) a012 ax ax ax 3 a h1− x {a n+h } ↔ , h ∈ xh − − − − F(x) F0 F 1 .x F(x) x F(x) F 0 F(x) Ta suy ra: {F n+2 }↔ = và {F n+1 }↔ = x2 x2 x x F(x)− x F(x) Vì F+= F + + F nên = + F(x) hay n2 n1 n x2 x ∞ n n  x 11 1 11515+  −  F(x)== ( += )∑  −   x n 1xx−−2 515 + 15 − 5 2 2  1− x1 − x n= 0     2 2 + n −  n  115 15  Vậy F n =  −  . 2 2  5     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 p n 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 p n là p n = p n-1 + n với p 1 = 2, p 0 = 1 và đã tìm được cơng th ức t ường minh cho p n bằng 2 cách. Bây gi ờ ta đi tìm cơng th ức hi ện c ủa p n d ưới cách nhìn t ừ hàm sinh. Lời gi ải: ∞ i + +2 + Hàm sinh cho dãy p 1, p 2, là p(x) = ∑pi x = p0 p 1 x p 2 x (1) i= 0 ∞ i1+ = + 2 + 3 + Nhân 2 v ế c ủa (1) v ới x ta cĩ x.p(x) = ∑pxi xp 01 px px 2 (2) i= 0 Lấy (1) tr ừ (2) v ế theo v ế ta cĩ: 2 p(x) - xp(x) = p 0 + (p 1 - p 0)x + (p 2 - p1)x + (3) mặt khác ta cĩ p 0 = 1, p n – p n-1 = n, do v ậy ta thay vào (3) ta cĩ 1 (1 - x).p(x) = 1 + x + 2x 2 + 3x 3 + = 1 + x(1 + 2x + 3x 2 + ) = 1 + x. (1− x) 2
  25. 25 1 1 Suy ra: p(x) = + x. , khai tri ển l ũy th ừa v ế ph ải ta được: 1− x (1− x) 3 ∞ ∞ ∞∞ n+ 2m = n + 2m1+ p(x) = ∑x x. ∑ Cm2+ .x ∑∑ x C m2 + .x n0= m0 = n0 == m0 ∞∞ ∞∞ n+ 2n = n + 2n = ∑∑x Cn1+ .x ∑∑ x C n1 + .x n0== n1 n0 == n0 2 n 2 n(n+ 1) n + n + 2 Suy ra h ệ s ố c ủa x là p n = 1 + C + = 1 + = n 1 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 S(n)∑ hm (n) ta xét hàm sinh: m n n F(x) =∑ S(n).x = ∑ ( ∑ hm (n)).x (*) n n m 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 n − k k m Bài tốn 3.32. Tính t ổng sau: ∑ ( 1) Cn C k k= m n − k k m Lời gi ải: Đặt S(m) = ∑ ( 1) Cn C k k= m ∞ n m −kkmm = − kk mm Xét hàm sinh: F(x) = ∑S(m).x = ∑∑( (1)CC).xnk ∑ (1)C. nk ∑ Cx m m0km== kn ≤ mk ≤ −kk +=− k n − nkk− +=−−++=− k n n nn = ∑(1)C.(1n x) (1) ∑ (1) C.(1 n x) (1)(1 1 x) (1)x kn≤ kn ≤ (-1)n khi m = n Đồng nh ất th ức ta cĩ: S(m) =   0 khi m < n n 2k n− k Bài tốn 3.34. Hãy tính t ổng sau: f(n) = ∑Cn+ k 2 k= 0 Lời gi ải: Gọi F(x) là hàm sinh c ủa dãy {f(n)}. Ta cĩ F(x) = ∑f (n)x n suy ra: n≥ 0 n n n =2knkn−− = k 2knn = −− k k 2k nk + F(x) ∑∑Cnk+ 2 .x ∑∑ 2. C nk + 2x ∑ 2.(2x). ∑ C nk+ (2x) n0k0≥= k0n0 =≥ k0 = n0 ≥ n n −− − − − 1 = 2k .(2x) k .(2x) 2k C nk (2x) nk = 2k .(2x) k . ∑ ∑ 2k++ 1 (n − k) − 1 ∑ − 2k+ 1 k0= nk0 − ≥ k= 0 (1 2x)
  26. 26 k 1 x  1 1 1− 2x =  = . = −∑ − 2 − x − − 12xk≥ 0 (1 2x)  12x 1− (1 4x)(1 x) (1− 2x) 2 211  1 + =+=2 (4x)n += x n (2 2n1 + 1)x n = f(n)xn . − − ∑ ∑  ∑ ∑ 3(1 4x) 3(1 x) 3n0≥ n0 ≥  3 n0 ≥ n≥ 0 + 22n 1 + 1 Vậy: f(n) = (n ≥ 0). 3 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.