Tài liệu Luận văn thạc sĩ phân hoạch và hàm sinh

.PDF

118

nhattuvisu Báo vi phạm

Tải xuống 84

Mô tả:

I HÅC THI NGUYN TR×ÍNG I HÅC KHOA HÅC NGUYN THÀ HU LINH PHN HOCH V HM SINH LUN VN THC Sß TON HÅC Th¡i Nguy¶n - 2014 I HÅC THI NGUYN TR×ÍNG I HÅC KHOA HÅC NGUYN THÀ HU LINH PHN HOCH V HM SINH Chuy¶n ng nh: PH×ÌNG PHP TON SÌ CP M¢ sè: 60.46.01.13 LUN VN THC Sß TON HÅC Ng÷íi h÷îng d¨n khoa hå PGS.TS. M VN NH Th¡i Nguy¶n - 2014 1 Mö lö Líi nâi u 1 Ki¸n thù hu©n bà 1.1. 1.2. 1.3. 1.4. 1.5. 1.6. Quan h» t÷ìng ÷ìng . . . . . . . . . . . . Tê hñp suy rëng . . . . . . . . . . . . . . . Khai triºn a thù . . . . . . . . . . . . . Cæng thù huyºn êi ng÷ñ . . . . . . . . Nguy¶n lþ Bò-Trø . . . . . . . . . . . . . . Chuéi ly thøa h¼nh thù . . . . . . . . . . 1.6.1. V nh ¡ huéi ly thøa h¼nh thù 1.6.2. ành lþ Fi htenholz v· hëi tö . . . 2 Ph¥n ho¤ h tªp hñp húu h¤n 2.1. Ph÷ìng ph¡p ph¥n ho¤ h tªp hñp . 2.2. D¢y sè Stirling . . . . . . . . . . . 2.2.1. C¡ sè Stirling lo¤i hai . . . 2.2.2. C¡ sè Stirling lo¤i mët . . 2.3. Mët v i k¸t qu£ v· sè Bell . . . . . 2.3.1. Kh¡i ni»m sè Bell . . . . . . 2.3.2. Sè Bell â i·u ki»n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4 4 5 7 11 14 17 17 19 20 20 24 25 31 34 34 37 3 Ph¥n ho¤ h sè nguy¶n d÷ìng 41 K¸t luªn T i li»u tham kh£o 62 63 3.1. Ph¥n ho¤ h sè nguy¶n d÷ìng . . . . . . . . . . . . . . . . 3.2. Ph÷ìng ph¡p h m sinh õa Euler . . . . . . . . . . . . . . 3.3. H m sinh th÷íng õa sè Stirling v sè ph¥n ho¤ h . . . . . 41 56 59 2 Líi nâi u B i to¡n ph¥n ho¤ h tªp hñp v ph¥n ho¤ h sè nguy¶n d÷ìng ¢ ÷ñ bi¸t ¸n tø r§t l¥u v ng y nay nâ â vai trá quan trång khæng h¿ trong l¾nh vü to¡n hå m nâ án ÷ñ ¡p döng trong nhi·u ng nh khoa hå kh¡ nh÷ Vªt Lþ, àa Lþ, ... Vªy th¸ n o l ph¥n ho¤ h tªp hñp v th¸ n o l ph¥n ho¤ h sè nguy¶n d÷ìng. Leibniz l ng÷íi u ti¶n quan t¥m ¸n b i to¡n ph¥n ho¤ h sè tü nhi¶n. V o n«m 1674, trong mët bù th÷ gûi J.Bernoulli, æng ¢ häi v· ¡ h hia mët sè nguy¶n khæng ¥m. Nâi theo thuªt ngú hi»n ¤i, Leibniz ¢ °t ¥u häi u ti¶n v· sè ph¥n ho¤ h õa mët sè tü nhi¶n. Æng ¢ ÷a ra mët v i v½ dö ö thº d÷îi ¥y: (1) Sè 2 â hai ph¥n ho¤ h 2 = 2 = 1 + 1, (2) Sè 3 â ba ph¥n ho¤ h 3 = 3 = 2 + 1 = 1 + 1 + 1, (3) Sè 4 â n«m ph¥n ho¤ h 4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1. Nhi·u b i to¡n sè hå hay tê hñp s³ trð n¶n d¹ gi£i hìn khi sû döng ph÷ìng ph¡p ph¥n ho¤ h tªp hñp. Ph¥n ho¤ h tªp hñp ng ÷ñ ¡p döng r§t nhi·u trong l¾nh vü to¡n sì §p, ° bi»t l trong ¡ b i to¡n thi hå sinh giäi. Luªn v«n Ph¥n ho¤ h v h m sinh nh¬m h» thèng l¤i ¡ ki¸n thù ì b£n v· ph¥n ho¤ h tªp hñp v ph¥n ho¤ h sè nguy¶n d÷ìng. Luªn v«n ÷ñ hia ra l m ba h÷ìng Ch÷ìng 1 - Ki¸n thù hu©n bà. Ch÷ìng n y tr¼nh b y ¡ v§n · v·: Quan h» t÷ìng ÷ìng, tê hñp suy rëng, khai triºn a thù , æng thù huyºn êi ng÷ñ , nguy¶n lþ Bò-trø, huéi ly thøa h¼nh thù . Ch÷ìng 2 - Ph¥n ho¤ h tªp hñp húu h¤n. Tr¼nh b y v· ph÷ìng ph¡p ph¥n ho¤ h tªp hñp, d¢y sè Stirling v mët v i k¸t qu£ v· sè Bell. Ch÷ìng 3 - Tr¼nh b y ¡ kh¡i ni»m ì b£n, mët sè ành lþ, h» qu£, m»nh · v· ph¥n ho¤ h sè nguy¶n d÷ìng. Ph÷ìng ph¡p h m sinh õa Eler. 3 H m sinh th÷íng õa sè Stirling v sè ph¥n ho¤ h. º ho n th nh luªn v«n n y, tr÷î h¸t t¡ gi£ xin ÷ñ gûi líi £m ìn s¥u s tîi PGS. TS. m V«n Nh¿ ¢ d nh thíi gian h÷îng d¨n, h¿ b£o tªn t¼nh gióp ï trong suèt qu¡ tr¼nh x¥y düng · t i ng nh÷ ho n thi»n luªn v«n. Ti¸p theo, t¡ gi£ ng xin gûi líi £m ìn h¥n th nh tîi ¡ thy æ ¢ å , kiºm tra, ¡nh gi¡ v ho nhúng þ ki¸n quþ b¡u º luªn v«n ÷ñ y õ hìn, phong phó hìn. Qua ¥y, t¡ gi£ ng xin ÷ñ gûi líi £m ìn tîi Ban gi¡m hi»u, pháng o t¤o, Khoa To¡n - Tin Tr÷íng ¤i hå Khoa hå - ¤i hå Th¡i Nguy¶n v ¡ b¤n çng nghi»p ¢ t¤o i·u ki»n thuªn lñi trong suèt qu¡ tr¼nh hå tªp t¤i tr÷íng. T¡ gi£ r§t mong nhªn ÷ñ sü âng gâp þ ki¸n õa ¡ thy æ v ¡ b¤n çng nghi»p º luªn v«n ÷ñ ho n thi»n hìn. T¡ gi£ xin h¥n th nh £m ìn! Th¡i Nguy¶n, th¡ng 9 n«m 2014 T¡ Gi£ Nguy¹n Thà Hu» Linh 4 Ch÷ìng 1 Ki¸n thù hu©n bà 1.1. Quan h» t÷ìng ÷ìng Gi£ thi¸t tªp X 6= ∅. T½ h · ¡ X × X ÷ñ ành ngh¾a nh÷ d÷îi ¥y: X × X = {(x, y)|x, y ∈ X}. ành ngh¾a 1.1. Tªp on S õa X × X ÷ñ gåi l mët quan h» hai ngæi trong X. N¸u (x, y) ∈ S th¼ ta nâi x â quan h» S vîi y v vi¸t xSy. ành ngh¾a 1.2. Gi£ thi¸t X 6= ∅ v S 6= ∅ l mët quan h» hai ngæi trong X. Quan h» S ÷ñ gåi l mët quan h» t÷ìng ÷ìng trong X n¸u nâ thäa m¢n ba i·u ki»n sau ¥y: (i) (Ph£n x¤) Vîi måi x ∈ X â xSx. (ii) (èi xùng) Vîi måi x, y ∈ X, n¸u â xSy th¼ ng â ySx. (iii) (B u) Vîi måi x, y, z ∈ X, n¸u â xSy v ySz th¼ ng â xSz. Khi S l mët quan h» t÷ìng ÷ìng trong X th¼ ta th÷íng kþ hi»u ∼ thay ho S. °t C(x) = {y ∈ X|y ∼ x} v gåi nâ l mët lîp t÷ìng ÷ìng vîi x l m ¤i di»n. D¹ d ng h¿ ra ¡ t½nh h§t sau: T½nh h§t 1.1. Gi£ sû ∼ l quan h» t÷ìng ÷ìng trong X 6= ∅. Khi â (i) Vîi måi x ∈ X â x ∈ C(x). (ii) Vîi måi y, z ∈ C(x) â y ∼ z v y, z ∼ x. (iii) Vîi måi x, y ∈ X, â ho° C(x) ∩ C(y) = ∅ ho° C(x) = C(y). (iv) Tªp th÷ìng X/ ∼ l tªp ¡ lîp t÷ìng ÷ìng khæng giao nhau. 5 1.2. Tê hñp suy rëng ành ngh¾a 1.3. Méi ¡ h sp x¸p â thù tü k phn tû m ¡ phn tû â thº l°p l¤i õa tªp T gçm n phn tû kh¡ nhau ÷ñ gåi l mët h¿nh hñp l°p hªp k õa tªp n phn tû. Kþ hi»u sè ¡ h¿nh hñp l°p hªp k õa tªp gçm n phn tû kh¡ nhau l Akn. K¸t qu£ sau ¥y l hiºn nhi¶n. M»nh · 1.1. Sè ¡ h¿nh hñp l°p hªp k õa mët tªp gçm n phn tû kh¡ nhau l k A n = nk . ành ngh¾a 1.4. Méi ¡ h l§y k phn tû m ¡ phn tû â thº l°p l¤i õa mët tªp n phn tû ÷ñ gåi l mët tê hñp l°p hay tê hñp suy rëng hªp k õa tªp n phn tû. Kþ hi»u sèk t§t £ ¡ tê hñp l°p hªp k õa mët tªp gçm n phn tû kh¡ nhau l Cn. Ta â k¸t qu£ sau ¥y. M»nh · 1.2. Sè ¡ ho¡n và l°p õa n phn tû, trong â â n nh÷ nhau thuë lo¤i 1, n2 phn tû nh÷ nhau thuë lo¤i 2,..., nh÷ nhau thuë lo¤i s, s³ óng b¬ng n! · n1 !n2 ! . . . ns ! 1 phn tû ns phn tû Chùng minh. Kþ hi»u ¡ phn tû l a , a , . . . , a , trong â a xu§t hi»n 1 2 s 1 ln, a2 xu§t hi»n n2 ln,..., as xu§t hi»n ns ln. n1 phn tû b¬ng nhau a1 ÷ñ kþ hi»u qua a11, . . . , a1n ; n2 phn tû b¬ng nhau a2 ÷ñ kþ hi»u qua a21 , . . . , a2n ; . . . ; ns phn tû b¬ng nhau as ÷ñ kþ hi»u qua as1 , . . . , asn . Vîi n = n1 + n2 + · · · + ns phn tû aij ta â n! ho¡n và. Khi è ành ¡ ai1 , . . . , ain , i 6= 1, án n1 phn tû b¬ng nhau a11 , . . . , a1n ho¡n và vîi nhau ta ng h¿ ÷ñ mët ho¡n và. Trong tr÷íng hñp n y, thü t¸ méi phn tû ¢ ÷ñ t½nh n1! ln. T÷ìng tü x²t ¡ tr÷íng hñp kh¡ . V¼ ¡ tr÷íng hñp l ë lªp vîi nhau n¶n theo quy t nh¥n ta th§y méi ho¡n và thü t¸ ¢ ÷ñ t½nh n1! . . . ns! ln. Vªy sè ho¡n và n t½nh b¬ng n !n n! · !...n ! n1 1 s 2 1 i 1 2 s M»nh · 1.3. Kþ hi»u T l sè ¡ h ph¥n hia n ç vªt kh¡ nhau v o trong k hëp kh¡ nhau sao ho â Khi â n! T = · n1 !n2 ! . . . nk ! ni vªt ÷ñ °t v o hëp thù i vîi i = 1, 2, . . . , k. Chùng minh. Ta â C ¡ h hån n vªt tø n vªt °t v o hëp thù nh§t, n1 n 1 6 ti¸p theo â Cnn−n ¡ h hån n2 vªt tø n − n1 vªt °t v o hëp thù hai,..., èi òng l Cnn−n −···−n ¡ h hån nk vªt tø n − n1 − · · · − nk−1 vªt °t v o hëp thù k. V¼ ¡ tr÷íng hñp hån ð tr¶n l ë lªp vîi nhau n¶n theo quy t nh¥n ta th§y T = Cnn Cnn−n . . . Cnn−n −···−n . Nh÷ vªy hóng ta nhªn ÷ñ k¸t qu£ T = Cnn Cnn−n . . . Cnn−n −···−n . Bi¸n êi 2 1 k 1 k−1 1 2 k 1 1 2 1 k−1 k 1 1 k−1 n! (n − n1 )! (n − n1 − · · · − nk−1 )! · ··· n1 !(n − n1 )! n2 !(n − n1 − n2 )! nk !0! n! · = n1 !n2 ! . . . nk ! T = Tâm l¤i T = n !n n! · !...n ! 1 2 k V½ dö 1.1. Gi£ sû m v k l nhúng sè nguy¶n d÷ìng v °t n = mk. Kþ l sè ¡ h ph¥n hia n ç vªt kh¡ nhau x¸p v o sao ho méi hëp hùa óng m vªt. Khi â hi»u T T = n! · k!(m!)k k hëp gièng nhau B i gi£i. Ta oi k hëp l kh¡ nhau. Khi â sè ¡ h ph¥n hia l T = n! n! · = m!m! . . . m! (m!)k Do k hëp gièng nhau n¶n méi ¡ h ph¥n hia n! ¢ xu§t hi»n k! ln. Vªy thü t¸ sè ¡ h ph¥n hia l T = k!(m!) · k V½ dö 1.2. Gi£ sû â s lo¤i hëp gçm m 1 hi¸ lo¤i thù nh§t, m2 hi¸ lo¤i ms hi¸ lo¤i thù s, trong â nhúng hi¸ òng lo¤i gièng h»t nhau. Câ n = m1 n1 + m2 n2 + · · · + ms ns ç vªt x¸p h¸t v o ¡ hëp sao ho méi hëp thuë lo¤i thù i hùa óng ni vªt. Kþ hi»u T l sè ¡ h ph¥n hia n ç vªt kh¡ nhau x¸p v o s lo¤i hëp gçm m1 + m2 + · · · + ms hi¸ thù hai,..., â. Khi â T = (m1 n1 + m2 n2 + · · · + ms ns )! · m1 !m2 ! . . . ms !(n1!)m1 (n2 !)m2 · · · (ns!)ms B i gi£i. Tr÷î ti¶n ta hia n vªt th nh s phn sao ho phn thù i â mi ni vªt. Khi â sè ¡ h ph¥n hia l T = n! · (m1 n1 )!(m1 n2 )! . . . (ms ns)! 7 em phn thù i l mini vªt x¸p v o mi hëp gièng h»t nhau. Khi â sè ¡ h ph¥n hia l Ti = m(m!(nin!)i)!m · Do ¡ h hia ð méi phn l ë lªp vîi nhau i i n¶n t§t £ sè ¡ ¡ h ph¥n hia kh¡ nhau l T = S.T1.T2 . . . Ts hay i T = (ms ns )! (m1 n1 )! n! · · · , · (m1 n1 )!(m1 n2 )! . . . (ms ns )! m1 !(n1 !)m1 ms !(ns!)ms ho° vi¸t gån l¤i T = (m1 n1 + m2 n2 + · · · + ms ns )! · m1 !m2 ! . . . ms !(n1!)m1 (n2 !)m2 · · · (ns!)ms 1.3. Khai triºn a thù ành ngh¾a h» sè tê hñp a ìn thù d÷îi ¥y nh÷ mët sü têng qu¡t ho tê hñp v khai triºn Nhà thù Newton. ành ngh¾a 1.5. Vîi sè nguy¶n d÷ìng n v k, sè n r1 , r2 , . . . , rk ! = n! , r1 !r2 ! . . . rk ! trong â ¡ ri ∈ N v r1 + r2 + · · · + rk = n, ÷ñ gåi l mët h» sè tê hñp a ìn thù . Mët v i k¸t qu£ sau ¥y ÷ñ suy trü ti¸p tø ành ngh¾a. M»nh · 1.4. n r1 , r2 , . . . , rk ! = n r1 ! ! ! n − r1 n − r1 − r2 − · · · − rk−1 ··· . r2 rk M»nh · 1.5. n r1 , r2 , . . . , rk = n−1 n−1 n−1 , +· · ·+ + r1 , r2 , . . . , rk − 1 r1 , r2 − 1, . . . , rk r1 − 1, r2 , . . . , rk trong â t§t £ ¡ ri r1 + r2 + · · · + rk = n. triºn a ìn thù bª n. nguy¶n d÷ìng v ành lþ sau ¥y án ÷ñ gåi l khai 8 ành l½ 1.1. Cæng thù khai triºn ho (x (x1 + x2 + · · · + xk )n = X r1 +···+rk =n 1 + x2 + · · · + xk )n ! n xr11 xr22 . . . xrkk , r1 , r2 , . . . , rk r1 , . . . , rk ∈ N trong â têng l§y theo t§t £ ¡ nh÷ sau vîi r1 + · · · + rr = n. Chùng minh. Ta hùng minh k¸t qu£ b¬ng ph÷ìng ph¡p qui n¤p theo Vîi n = 1 æng thù hiºn nhi¶n óng. Gi£ sû æng thù óng vîi n. Ta h¿ ra nâ óng vîi n + 1. Thªt vªy, ta â: n. (x1 + · · · + xk )n+1 =(x1 + · · · + xk )n (x1 + · · · + xk ) X n! = xr11 xr22 . . . xrkk (x1 + · · · + xk ) r !r ! . . . rk ! r1 +r2 +···+rr =n 1 2 = X [ r1∗ +···+rk∗ =n+1 + ··· + Tø â suy ra n! n! + (r1∗ − 1)!r2∗ · · · rk∗ ! r1∗ !(r2∗ − 1)! · · · rk∗ ! n! rk∗ r1∗ ] x . . . x . 1 k r1∗ ! . . . (rk∗ − 1)! (x1 + · · · + xk )n+1 = hay (x1 + · · · + xk )n+1 = n!(n + 1) r1∗ rk∗ x · · · x k r∗ ! · · · rk∗ ! 1 r ∗ +···+r ∗ =n+1 1 1 X k (n + 1)! r1∗ rk∗ x . . . x , 1 k ∗ ∗ r ! · · · r ! k r ∗ +···+r ∗ =n+1 1 1 X k trong â têng l§y theo r1∗, · · · , rk∗ ∈ N vîi P ri∗ = n + 1. Vªy ta suy ra æng i=1 thù óng vîi n + 1. Tâm l¤i, æng thù óng vîi måi n. k V½ dö 1.3. Vîi b§t ký sè nguy¶n d÷ìng k luæn â çng nh§t thù kn = X r1 +···+rk =n trong â têng l§y theo t§t £ ¡ B i gi£i. Ta â k n ! n , r1 , r2 , . . . , rk r1 , . . . , rk ∈ N = (1 + 1 + · · · + 1)n = vîi P r1 + · · · + rr = n. r1 +···+rk =n n r1 , r2 , . . . , rk ! theo 9 ành lþ 1.1. Chó þ 1.1. Khi k = 2 ta nhªn ÷ñ çng nh§t thù Newton (x1 + x2 )n = X r1 +r2 =n ! n xr11 xr22 . r1 , r2 Tø â ta suy ra ÷ñ çng nh§t thù Vandermonde ! m 0 ! ! n m + k 1 ! ! n m + ··· + k−1 k n 0 ! = ! m+n . k Bê · 1.1. Sè nghi»m nguy¶n khæng ¥m õa ph÷ìng tr¼nh x +· · ·+x ! 1 k =n n+k−1 . k−1 b¬ng Chùng minh. Kþ hi»u sè nghi»m nguy¶n khæng ¥m õa ph÷ìng tr¼nh l Nk (n). Ta â N1(n) = 1. T½nh N2(n), tù l t½nh sè nghi»m nguy¶n khæng ¥m õa ph÷ìng tr¼nh x1 + x2 = n. Ph÷ìng tr¼nh n y â ¡ nghi»m (0, n), (1, n − 1), ..., (n, 0) n¶n N2 (n) = n + 1 = ! n+1 . 1 º t½nh N3(n) ta x²t ph÷ìng tr¼nh x1 + x2 + x3 = n. Cho x3 = 0, 1, 2, ..., n, ta â N3 (n) = N2 (n) + N2(n − 1) + · · ·+ N2 (2) + N2(1) + N2(0) = (n + 1) + · · ·+ 1. Vªy N3(n) = n¤p. Hiºn nhi¶n ! n+2 . 2 Ta hùng minh Nk (n) = n+k−1 k−1 ! b¬ng qui Nk (n) = Nk−1 (n) + Nk−1 (n − 1) + Nk−1 (n − 2) + · · · + Nk−1 (0). Do â Nk (n) = ! ! n+k−2 n+k−3 k−2 + + ··· + k−2 k−2 k−2 ! = ! n+k−1 . k−1 10 H» qu£ 1.1. Sè ¡ sè h¤ng trong khai ! triºn (x ìn thù bª n n+k−1 . k−1 óng b¬ng 1 + x2 + · · · + xk )n hay sè Chùng minh. Sè ¡ sè h¤ng trong khai triºn (x + x + · · · + x ) óng 1 2 k n b¬ng sè ìn thù kh¡ nhau xr1 xr2 . . . xrk xu§t hi»n trong khai triºn. Sè â óng b¬ng sè nghi»m nguy¶n! khæng ¥m õa ph÷ìng tr¼nh r1 + · · · + rk = n. Vªy sè â b¬ng n +k −k −1 1 theo Bê · 1.1. 1 2 k Sû döng k¸t qu£ n y v o vi» x²t h¿nh hñp vîi tn sè l°p. Mët phn tû xi õa mët d¢y k phn tû ho tr÷î x1 x2 . . . xk ÷ñ gåi l â tn sè l°p ri n¸u nâ xu§t hi»n trong d¢y óng ri ln. Kþ hi»u T (r1, r2, . . . , rk) l sè ¡ d¢y â l°p (r1, r2, . . . , rk ) vîi ë d i õa d¢y l r1 + r2 + · · · + rk = n ¡ phn tû õa mët tªp A = {x1, x2, . . . , xk} vîi k phn tû ho tr÷î sao ho trong méi d¢y ph£i â phn tû thù i xu§t hi»n óng ri ln. M»nh · 1.6. Tªp A vîi k phn tû ho tr÷î . Sè ¡ d¢y k phn tû â l°p (r1 , r2, . . . , rk ) vîi ë d i õa d¢y l r1 + r2 + · · · + rk = n l ! n . r1 , r2 , . . . , rk T (r1 , r2 , . . . , rk ) = Chùng minh. Sè d¢y k phn tû â l°p (r , r , . . . , r ) vîi ë d i õa d¢y 1 2 h½nh l h» sè õa ìn thù triºn (x1 + x2 + · · · + xk )n. Vªy T (r1, r2, . . . , rk) = r1 + r2 + · · · + rk = n k r1 r2 x1 x2 . . . xrkk trong ! n . r1 , r2 , . . . , rk khai V½ dö 1.4. Gi£ sû â b£ng hú §u t¤o h¿ vîi 3 hú ¡i a, b, c. T¼m sè ¡ tø bao gçm n hú m trong â â hùa mët sè h®n hú ¡i a. B i gi£i. N¸u trong hú â 2r hú ¡i a th¼ ta â thº °t theo C ¡ h; 2r n án trong n − 2r và tr½ án l¤i ta â 2n−2r ¡ h °t ho b v c. Tâm l¤i â n n−2r C2r ¡ h. T§t £ s³ l P C2rn 2n−2r . Tø n 2 r=0 n n (1 + x) + (1 − x) = 2 n X r=0 2r C2r n x 11 ta suy ra n X C2r n r=0 2 n−2r 1 3n + 1 1 2n · (1 + )n + (1 − )n = = 2 2 2 2 1.4. Cæng thù huyºn êi ng÷ñ B¥y gií ta sû döng kþ hi»u h¼nh thù º hùng minh æng thù huyºn êi ng÷ñ v· têng qua tê hñp d÷îi ¥y: ành l½ 1.2. Gi£ sû f (k) v g(k) l nhúng h m sè hå thäa m¢n f (n) = n P k=0 Ckn g(k) vîi måi n ∈ N. Khi â ta â g(n) = n X k=0 (−1)k Ckn f (n − k). Chùng minh. Vi¸t mët ¡ h h¼nh thù f (k) v g(k) qua f v g . Khi k k â f n = P Ckn gk hay f n = (g + 1)n óng vîi ∀ n ∈ N. Vªy n k=0 (f + x)n = (g + 1 + x)n , ∀ x. Nhî sau khi khai triºn ð hai v¸ s³ vi¸t fk v gk thay ho nhúng f k v g k . n Cho x = −1 â gn = (f − 1)n hay g(n) = P (−1)k Ckn f (n − k). k=0 V½ dö 1.5. Cho d¢y Fibona i F Chùng minh r¬ng B i gi£i. Vîi n X 0 = F1 = 1, Fn+1 = Fn + Fn−1 , n > 1. ! n (−1)j Fn = (F2j − 1). j j=1 √ √ 1+ 5 1− 5 , x2 = x1 = â biºu di¹n 2 2 1 Fn = √ (xn+1 − xn+1 2 1 ). 5 12 Khi â n X n ! n 1 X n ! Fj = √ (xj+1 − xj+1 2 1 ) j 5 j=0 j 1 = √ [x2(1 + x2 )n − x1 (1 + x1 )n ] 5 1 2n = √ [x2x2n 2 − x1 x1 ], 5 j=0 v¼ 1 + x2 = x22, 1 + x1 = x21. Vªy n X n ! 1 Fj = √ (x22n+1 − x12n+1 ) = F2n . j 5 j=0 Theo ành lþ 1.2, ta nhªn ÷ñ Fn = n X (−1)j j=0 ! n g(j) = j vîi f (j) = Fj , g(n) = F2n. V¼ F0 = 1 = − Fn = n X n X (−1)j j=1 ! n F2j j (−1)j j=0 n P (−1)j j=1 n j ! n¶n ! n (F2j − 1). j V½ dö 1.6. X²t d¢y sè Lu as L n > 1. Khi â ta â (ii) L2n = (iii) Ln = j=0 n P j=1 ! n Lj . j (−1)j = 2, L1 = 1 v √ √ 1+ 5 1− 5 , x2 = · x1 = 2 2 (i) Ln = xn1 + xn2 vîi n P 0 ! n (L2j − 2). j Ln+2 = Ln+1 + Ln vîi 13 B i √gi£i. B¬ng ph÷ìng ph¡p qui n¤p theo n, vîi 1+ 5 ta â biºu di¹n Ln = xn2 + xn1 v ta â (i). 2 (ii) V¼ 1 + x2 = x22, 1 + x1 = x21 n¶n â bi¸n êi n X n j=0 j ! n X n Lj = j=0 x2n 2 = j ! √ 1− 5 , x2 = x1 = 2 (xj2 + xj1 ) = (1 + x2 )n + (1 + x1 )n + x2n 1 = L2n . ! n Vªy â æng thù L2n = Lj . j j=0 (iii) Theo ành lþ 1.2, nhªn ÷ñ n P Ln = n X (−1)j j=0 ! ! n X n n g(j) = (−1)j L2j j j j=0 vîi f (j) = Lj , g(n) = L2n. V¼ L0 = 2 = −2 (−1)j j=1 d ng suy ra ÷ñ æng thù n P Ln = n X (−1)j j=1 n j ! n¶n hóng ta d¹ ! n (L2j − 2). j V½ dö 1.7. Cho d¢y Dn = n X (−1)k k=0 ! n (n − k)! k ! vîi n > 1. Chùng minh r¬ng n! = 1 + ! n X n k=2 B i gi£i. Ta â (−1)nDn = n X k=0 (−1)n−k k Dk ! vîi måi n > 2. n ! X n n (n − k)! = (−1)k k! n−k k k=0 14 vîi n > 1. °t fk = (−1)kDk v gk = (−1)kk!. Khi â f (n) = n X n k=0 Theo ành lþ 1.2, ta nhªn ÷ñ gn = n X (−1)n−k k=0 hay (−1)nn! = k ! ! gk . ! n X n n fk = (−1)n Dk k k k=0 n X k=0 (−1)n ! n Dk . k V¼ D0 = 1 theo quy ÷î v D1 = 0 n¶n n! = 1 + n P k=2 (−1)n ! n Dk . k 1.5. Nguy¶n lþ Bò-Trø Khi x²t b i to¡n tê hñp, ta th÷íng ph£i ¸m xem â bao nhi¶u §u h¼nh â thº t¤o ra vîi nhúng y¶u u °t tr÷î . Nâi hung, º ¸m ¡ §u h¼nh ¢ ho ng÷íi ta t¼m ¡ h ÷a ¡ §u h¼nh v· lo¤i quen thuë qua vi» ph¥n ra th nh ¡ lîp º ¡p döng nguy¶n lþ ëng d÷îi ¥y: Card (A ∪ B) = Card (A) + Card (B) − Card (A ∩ B). Têng qu¡t nguy¶n lþ ëng ta â Nguy¶n lþ Bò-Trø. C¡i khâ õa vi» vªn döng nguy¶n lþ Bò-Trø l vi» ph¥n lîp nh÷ th¸ n o º d¹ d ng â ÷ñ ¡ sè ¸m. Kþ hi»u lü l÷ñng õa tªp A gçm mët sè húu h¤n ¡ phn tû qua |A|. Gi£ sû A1, . . . , An l nhúng tªp on õa tªp A. C¡ sè sk ÷ñ x¡ ành 15 qua s0 = |A| s1 = |A1 | + |A2 | + · · · + |An | s2 = |A1 ∩ A2 | + |A1 ∩ A3 | + · · · + |An−1 ∩ An | ··· sk = ··· X 16i1 2 gi£ thi¸t k¸t luªn óng ho n − 1 tªp. °t A = S Ai. Theo i=1 æng thù (1) ta â n [ Ai = |A ∪ An | = |A| + |An | − |A ∩ An |. i=1 Sû döng gi£ thi¸t qui n¤p ho |A| v |A ∩ An| ta â æng thù . 16 V½ dö 1.8. Câ bao nhi¶u sè tü nhi¶n n ∈ [1, 2005] m khæng hia h¸t ho mët sè n o trong ¡ sè 2,3,11,13. B i gi£i. Kþ hi»u A = {1, 2, . . . , 2005} v A l tªp on õa A gçm t§t i 2005 = 1002, |A3| = 2 2005 2005 2005 = 668, |A11| = = 182 v |A13 | = = 154; ta l¤i â 3 11 13 2005 2005 2005 |A2 ∩A3 | = = 334, |A2 ∩A11 | = = 91, |A2 ∩A13 | = = 6 22 26 2005 2005 = 60, |A3 ∩ A13 | = = 51, |A11 ∩ A13 | = 77, |A3 ∩ A11 | = 33 39 2005 2005 = 14. T½nh |A2 ∩ A3 ∩ A11 | = = 30, |A2 ∩ A3 ∩ A13 | = 143 66 2005 2005 2005 = 25, |A2 ∩ A11 ∩ A13 | = = 7, |A3 ∩ A11 ∩ A13 | = = 4, 78 429 286 2005 |A2 ∩ A3 ∩ A11 ∩ A13 | = = 2. Sè T ¡ sè thuë A khæng hia h¸t 858 ho 2, 3, 11, 13 l £ ¡ sè nguy¶n d÷ìng hia h¸t ho i. Ta â |A2| = T = |A| − |A2 ∪ A3 ∪ A11 ∪ A13 | = 2005 − (1002 + 668 + 182 + 154) + + (334 + 91 + 77 + 60 + 51 + 14) − (30 + 25 + 7 + 4) + 2 = 562. Vªy T = 562. V½ dö 1.9. N¸u sè nguy¶n d÷ìng n > 1 â sü ph¥n ti¶u hu©n th nh t½ h t½ h n= pα1 1 pα2 2 . . . pαs s th¼ h m Euler l sè t§t £ ¡ sè nguy¶n ϕ(n) = n k ∈ {1, 2, . . . , n} s Q i=1 1 , trong pi (k, n) = 1. 1− sao ho Chùng minh. Vîi méi 1 6 i 6 s ta ành ngh¾a tªp A â ϕ(n) = {pi , 2pi, . . . , npi} . Khi â ¡ Ai l nhúng tªp on õa tªp T = {1, 2, . . . , n} v |Ai| = pn · Vîi i méi °p i, j, i 6= j, tªpn Ai ∩ Aj bao gçm t§t £ ¡ sè thuë T l bëi õa · T÷ìng tü t½nh lü l÷ñng õa ¡ tªp giao kh¡ . pi pj v |Ai ∩ Aj | = pi pj i 17 Theo nguy¶n lþ Bò-Trø, ành lþ 1.3, ta â n [ ϕ(n) = n − Ai i=1 s X n X n n − p pp ppp i=1 i 16i - Xem thêm -