Tài liệu Luận văn phép phân hoạch tập hợp và một số ứng dụng trong toán sơ cấp

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN VĂN DIỄN PHÉP PHÂN HOẠCH TẬP HOWPJVAF MỘT SỐ ỨNG DỤNG TRONG TOÁN SƠ CẤP THÁI NGUYÊN 2015 Môc lôc Muc luc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Lêi nãi ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1 PhÐp ph©n ho¹ch tËp hîp 5 1.1 PhÐp ph©n hoach tËp hîp vµ quan hÖ t−¬ng ®−¬ng . . . . . 5 1.2 Sè Bell vµ sè Stirling lo¹i hai . . . . . . . . . . . . . . . . 10 1.3 Mét sè c«ng thøc tÝnh hµm ph©n ho¹ch tËp hîp . . . . . . 18 2 Mét sè øng dông trong to¸n s¬ cÊp 22 2.1 Ph©n ho¹ch ch½n, lÎ vµ øng dông trong to¸n s¬ cÊp . . . . 22 2.2 Mét sè øng dông gi¶i to¸n tæ hîp vµ h×nh häc s¬ cÊp . . . 27 2.3 Ph©n hoach sè vµ øng dông trong to¸n s¬ cÊp . . . . . . . 32 KÕt luËn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Tµi liÖu tham kh¶o . . . . . . . . . . . . . . . . . . . . . . . . 39 1 2 Lêi c¶m ¬n Tr−íc hÕt, t«i xin göi lêi biÕt ¬n ch©n thµnh vµ s©u s¾c nhÊt ®Õn PGS.TS Lª ThÞ Thanh Nhµn ®· gióp t«i hoµn thµnh b¶n luËn v¨n nµy. Khi b¾t ®Çu nhËn ®Ò tµi thùc sù t«i c¶m nhËn ®Ò tµi mang nhiÒu néi dung míi mÎ. H¬n n÷a víi vèn kiÕn thøc Ýt ái cïng víi kinh nghiÖm lµm ®Ò tµi lín kh«ng nhiÒu nªn t«i ch−a thùc sù tù tin ®Ó tiÕp cËn ®Ò tµi. MÆc dï rÊt bËn rén trong c«ng viÖc nh−ng C« vÉn dµnh nhiÒu thêi gian vµ t©m huyÕt trong viÖc h−íng dÉn, ®éng viªn khuyÕn khÝch t«i trong suèt thêi gian t«i thùc hiÖn ®Ò tµi. Trong qu¸ tr×nh tiÕp cËn ®Ò tµi ®Õn qu¸ tr×nh hoµn thiÖn luËn v¨n C« lu©n tËn t×nh chØ b¶o vµ t¹o ®iÒu kiÖn tèt nhÊt cho t«i. Cho ®Õn b©y giê luËn v¨n th¹c sÜ cña t«i ®· ®−îc hoµn thµnh, xin c¶m ¬n C« ®· ®«n ®èc nh¾c nhë vµ gióp ®ì t«i hÕt m×nh. T«i xin tr©n träng c¶m ¬n Ban Gi¸m hiÖu, Khoa to¸n-Tin vµ phßng §µo t¹o cña tr−êng §¹i häc Khoa häc-§¹i häc Th¸i Nguyªn. T«i xin tr©n träng c¶m ¬n c¸c ThÇy, C« ®· tËn t×nh truyÒn ®¹t nh÷ng kiÕn thøc quÝ b¸u còng nh− t¹o mäi ®iÒu kiÖn thuËn lîi nhÊt ®Ó t«i hoµn thµnh luËn v¨n nµy. Cuèi cïng, t«i xin ch©n thµnh bµy tá lßng biÕt ¬n ®Õn gia ®×nh, b¹n bÌ, nh÷ng ng−êi ®· kh«ng ngõng ®éng viªn, hç trî t¹o mäi ®iÒu kiÖn cho t«i. V× n¨ng lùc b¶n th©n còng nh− thêi gian cßn h¹n chÕ, luËn v¨n ch¾c ch¾n kh«ng thÓ tr¸nh khái nh÷ng sai sãt. T¸c gi¶ rÊt mong nhËn ®−îc sù ®ãng gãp ý kiÕn nhËn xÐt cña ThÇy, C« ®Ó b¶n luËn v¨n ®−îc hoµn thiÖn h¬n. Nam §Þnh, ngµy 15, th¸ng 4, n¨m 2015 Häc viªn NguyÔn V¨n DiÔn 3 Lêi nãi ®Çu LÝ thuyÕt ph©n ho¹ch tËp hîp cã mét lÞch sö l©u dµi (®−îc quan t©m tõ ThÕ kØ 19), cho ®Õn nay ®©y vÉn lµ mét chñ ®Ò nghiªn cøu rÊt hÊp dÉn vµ thêi sù. LÝ thuyÕt ph©n ho¹ch tËp hîp ®ãng vai trß quan träng trong nhiÒu lÜnh vùc kh¸c nhau cña to¸n häc nh− Tæ hîp, LÝ thuyÕt Lie, LÝ thuyÕt biÓu diÔn, To¸n vËt lÝ, LÝ thuyÕt c¸c hµm ®Æc biÖt . . . . V× tÇm quan träng cña nã trong nh÷ng øng dông kh¸c nhau, c¸c nhµ to¸n häc ®· nç lùc t×m c«ng thøc tÝnh sè ph©n ho¹ch mét tËp hîp. Mét trong sè nh÷ng c«ng thøc tÝnh sè ph©n ho¹ch ®Çu tiªn thuéc vÒ Bell trong mét bµi b¸o trªn t¹p chÝ næi tiÕng Annals of Mathematics n¨m 1934 vµ tiÕp tôc ph¸t triÓn trong mét bµi b¸o kh¸c trªn Annals of Mathematics c«ng bè n¨m 1938. Sè phÐp ph©n ho¹ch trªn mét tËp hîp n phÇn tö ®−îc gäi lµ sè Bell thø n ®Ó ghi nhËn ®ãng gãp to lín cña nhµ to¸n häc tªn tuæi Eric Temple Bell (1883-1960), sè nµy ®−îc kÝ hiÖu lµ Bn . NhiÒu c«ng thøc kh¸c ®Ó tÝnh sè ph©n ho¹ch tËp hîp n phÇn tö nh− c«ng thøc ®−îc ®−a ra bëi G. C. Rota trong bµi b¸o “The Number of Partitions of a Set” trªn Amer. Math. Monthly n¨m 1964, c«ng thøc cña W. F. Lunnon, P. Pleasants, M. N. Stephens trong bµi b¸o “Arithmetic Properties of Bell Numbers to a Composite Modulus” trªn Acta Arith. n¨m 1979, . . . . Ngµy nay viÖc nghiªn cøu sè Bell vÉn rÊt ®−îc quan t©m, thÓ hiÖn trong c«ng tr×nh n¨m 2013 cña E. D. Knuth tæng kÕt 2000 n¨m vÒ to¸n Tæ hîp (xem [K]), cña D. Berend vµ T. Tassa n¨m 2010 (xem [BT]), cña D. Callan n¨m 2006 (xem [Ca]), . . .. Môc ®Ých cña luËn v¨n lµ nghiªn cøu lÝ thuyÕt ph©n ho¹ch tËp hîp, mét sè c«ng thøc tÝnh sè Bell Bn vµ øng dông ®Ó gi¶i mét sè d¹ng to¸n s¬ cÊp, ®Æc biÖt lµ to¸n tæ hîp. LuËn v¨n gåm 2 ch−¬ng. Trong Ch−¬ng 1, tr−íc hÕt chóng t«i tr×nh bµy 4 kh¸i niÖm phÐp ph©n ho¹ch tËp hîp, chØ ra sù liªn quan chÆt chÏ gi÷a phÐp ph©n ho¹ch tËp hîp vµ quan hÖ t−¬ng ®−¬ng trªn cïng mét tËp hîp. TiÕt 1.2 dµnh ®Ó chøng minh mét sè c«ng thøc tÝnh sè ph©n ho¹ch, sè Stirling lo¹i 2 vµ ®−a ra mét sè c«ng thøc truy håi ®Ó tÝnh sè Bell. Ch−¬ng nµy còng giíi thiÖu vÒ tam gi¸c Bell, ®ã lµ thµnh qu¶ cña viÖc tÝnh to¸n dùa trªn c¸c c«ng thøc cã ®−îc. Trong Ch−¬ng 2, chóng t«i tr×nh bµy mét sè øng dông cña lÝ thuyÕt ph©n ho¹ch trong viÖc gi¶i mét sè d¹ng to¸n s¬ cÊp, ®Æc biÖt lµ ®èi víi nh÷ng bµi to¸n trong ®¹i sè tæ hîp hay h×nh häc s¬ cÊp. Chóng t«i còng ®−a ra lêi gi¶i mét sè bµi to¸n liªn quan ®Õn nghiÖm cña ph−¬ng tr×nh, tÝnh x¸c suÊt cña biÕn cè hay bµi to¸n ph©n ho¹ch cña tËp hîp sè, ®Æc biÖt lµ nh÷ng bµi to¸n ph©n ho¹ch ®a gi¸c thµnh nh÷ng tam gi¸c trong h×nh häc s¬ cÊp. Ch−¬ng 1 PhÐp ph©n ho¹ch tËp hîp Môc tiªu cña Ch−¬ng 1 lµ tr×nh bµy kh¸i niÖm ph©n ho¹ch tËp hîp, mèi quan hÖ gi÷a ph©n ho¹ch tËp hîp vµ quan hÖ t−¬ng ®−¬ng, tÝnh chÊt c¬ së cña sè Bell vµ chøng minh mét sè c«ng thøc tÝnh sè Bell, tøc lµ c«ng thøc tÝnh hµm ph©n ho¹ch tËp hîp. 1.1 PhÐp ph©n hoach tËp hîp vµ quan hÖ t−¬ng ®−¬ng Trong suèt tiÕt nµy lu«n gi¶ thiÕt X lµ mét tËp hîp kh¸c rçng. Môc tiªu cña tiÕt nµy lµ giíi thiÖu kh¸i niÖm phÐp ph©n ho¹ch tËp hîp vµ mèi liªn hÖ gi÷a c¸c phÐp ph©n ho¹ch cña tËp X víi c¸c quan hÖ t−¬ng ®−¬ng trªn tËp X. 1.1.1 §Þnh nghÜa. Ta gäi mét phÐp ph©n ho¹ch tËp X (hay mét sù chia líp trªn X) lµ mét c¸ch chia X thµnh mét hä c¸c tËp con kh¸c rçng {Xi}i∈I S sao cho Xi ∩ Xj = ∅ víi mäi i, j ∈ I, i 6= j vµ X = Xi. NÕu {Xi}i∈I lµ i∈I mét ph©n ho¹ch tËp X th× mçi tËp con Xi ®−îc gäi lµ mét khèi cña ph©n ho¹ch; nÕu I gåm k phÇn tö th× ta nãi ph©n ho¹ch ®ã gåm k khèi. 1.1.2 VÝ dô. (i) NÕu X = {a} th× X cã ®óng mét ph©n ho¹ch, ®ã lµ ph©n ho¹ch thµnh mét khèi X. 5 6 (ii) NÕu X = {a, b} th× X cã hai ph©n ho¹ch, ph©n ho¹ch thø nhÊt thµnh mét khèi X; ph©n ho¹ch thø hai gåm hai khèi {a}, {b}. (iii) NÕu X = {a, b, c} th× cã 5 phÐp ph©n ho¹ch tËp X, ®ã lµ {{a}, {b}, {c}}; {{a, b}, {c}}; {{a, c}, {b}}; {{b, c}, {a}}; {{a, b, c}}, trong ®ã cã mét ph©n ho¹ch thµnh 1 khèi, ba ph©n ho¹ch thµnh 2 khèi, vµ mét ph©n ho¹ch thµnh 3 khèi. (iv) NÕu X = {a, b, c, d} th× cã 15 phÐp ph©n ho¹ch tËp X, ®ã lµ {{a, d}, {b}, {c}}; {{a, b}, {c}, {d}}; {{a, c}, {b}, {d}} {{b, c}, {a}, {d}}; {{b, d}, {a}, {c}}; {{c, d}, {a}, {b}} {{a, b, c}, {d}}; {{a, b, d}, {c}}; {{a, c, d}, {b}} {{b, c, d}, {a}}; {{a, b}, {c, d}}; {{a, c}, {b, d}} {{a, d}, {b, c}; {a, b, c, d}; {abcd}. Cô thÓ: TËp hîp gåm 4 phÇn tö cã 1 ph©n ho¹ch thµnh 1 khèi lµ {abcd} TËp hîp gåm 4 phÇn tö cã 1 ph©n ho¹ch thµnh 4 khèi lµ {a, b, c, d} TËp hîp gåm 4 phÇn tö cã 7 ph©n ho¹ch thµnh 2 khèi lµ {{a, b, c}, {d}}; {{a, b, d}, {c}}; {{a, c, d}, {b}}; {{b, c, d}, {a}}; {{a, b}, {c, d}}; {{a, c}, {b, d}}; {{a, d}, {b, c}} TËp hîp gåm 4 phÇn tö cã 6 ph©n ho¹ch thµnh 3 khèi lµ {{a, d}, {b}, {c}}; {{a, b}, {c}, {d}}; {{a, c}, {b}, {d}}; {{b, c}, {a}, {d}}; {{b, d}, {a}, {c}}; {{c, d}, {a}, {b}} 1.1.3 VÝ dô. Chó ý r»ng ph©n ho¹ch kh«ng phô thuéc vµo thø tù cña c¸c khèi. Ch¼ng h¹n, trong VÝ dô 1.1.2(iii) víi X = {a, b, c}, phÐp ph©n ho¹ch {{a}, {b}, {c}} vµ {{b}, {a}, {c}} lµ nh− nhau; phÐp ph©n ho¹ch {{a, c}, {b}} vµ {{b}, {a, c}} lµ nh− nhau. 7 Thùc tÕ, cã nhiÒu bµi to¸n ®−îc quy vÒ bµi to¸n ph©n ho¹ch tËp hîp nh− c¸c bµi to¸n vÒ x¸c xuÊt thèng kª, vÒ tæ hîp ®å thÞ, . . . . 1.1.4 VÝ dô. Cho Ω lµ kh«ng gian mÉu cña mét phÐp thö nµo ®ã. Khi ®ã hÖ biÕn cè gåm n biÕn cè A1, A2 , A3 , . . . , An ®−îc gäi lµ 1 ph©n ho¹ch cña kh«ng gian mÉu Ω nÕu Ai ∩ Aj = ∅, víi mäi i, j = 1, 2, 3 . . . n vµ A1 ∪ A2 ∪ A3 ∪ . . . ∪ An = Ω. HÖ biÕn cè trªn cßn ®−îc gäi lµ hÖ ®Çy ®ñ vµ ®«i mét xung kh¾c víi nhau. Khi ®ã víi B lµ mét biÕn cè bÊt k× trong phÐp thö, ta cã c«ng thøc ®Çy ®ñ vµ c«ng thøc Bayes nh− sau: (i) P (B) = P (A1)P (B/A1 ) + P (A2 )P (B/A2) + . . . + P (An)P (B/An ) P (Ai)P (B/Ai) . (ii) P (Ai/B) = P (B) TiÕp theo, chóng ta tr×nh bµy mèi quan hÖ gi÷a c¸c phÐp ph©n ho¹ch tËp X víi c¸c quan hÖ t−¬ng ®−¬ng trªn X. Nh¾c l¹i r»ng mét tËp con kh¸c rçng cña tÝch Descartes X × X ®−îc gäi lµ mét quan hÖ (hai ng«i) trªn X. Ta th−êng kÝ hiÖu c¸c quan hÖ b»ng c¸c ch÷ R, S, T, Ω, . . . hoÆc c¸c kÝ hiÖu ∼, 6, ≥, . . .. Cho Ω lµ mét quan hÖ hai ng«i trªn X. NÕu (a, b) ∈ Ω th× ta viÕt lµ aΩb vµ ta nãi a quan hÖ víi b (theo quan hÖ Ω). D−íi ®©y lµ mét sè tÝnh chÊt quan träng mµ mét quan hÖ Ω cã thÓ cã (i) Ph¶n x¹: aΩa víi mäi a ∈ X. (ii) §èi xøng: NÕu aΩb th× bΩa víi mäi a, b ∈ X. (iii) Ph¶n ®èi xøng: NÕu aΩb vµ bΩa th× a = b víi mäi a, b ∈ X. (iv) B¾c cÇu: NÕu aΩb vµ bΩc th× aΩc víi mäi a, b, c ∈ X. Ch¼ng h¹n, víi X = {1, 2, 3, 4}, quan hÖ chia hÕt Ω = {(a, b) ∈ X × X | a lµ −íc cña b} cã c¸c tÝnh chÊt ph¶n x¹, ph¶n ®èi xøng vµ b¾c cÇu. Ta còng viÕt quan hÖ chia hÕt nµy b»ng c¸ch chØ ra mét thuéc tÝnh ®Æc tr−ng nh− sau: aΩb nÕu vµ chØ nÕu a lµ −íc cña b víi mäi a, b ∈ X. Ta còng cã thÓ viÕt quan hÖ 8 nµy b»ng c¸ch liÖt kª nh− sau Ω = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}. 1.1.5 §Þnh nghÜa. Mét quan hÖ trªn X ®−îc gäi lµ quan hÖ t−¬ng ®−¬ng nÕu nã ph¶n x¹, ®èi xøng vµ b¾c cÇu. Theo truyÒn thèng, quan hÖ t−¬ng ®−¬ng th−êng ®−îc kÝ hiÖu bëi ∼ . Gi¶ sö ∼ lµ quan hÖ t−¬ng ®−¬ng trªn X. Víi mçi a ∈ X, ta gäi líp t−¬ng ®−¬ng cña a, kÝ hiÖu bëi cl(a) (hay a, hoÆc [a]) lµ tËp c¸c phÇn tö cña X quan hÖ víi a, tøc lµ cl(a) = {b ∈ X | b ∼ a}. TËp c¸c líp t−¬ng ®−¬ng ®−îc gäi lµ tËp th−¬ng cña X theo quan hÖ t−¬ng ®−¬ng ∼ vµ ®−îc kÝ hiÖu bëi X/ ∼ . Nh− vËy X/ ∼ = {cl(a) | a ∈ X}. Chó ý r»ng a ∼ b khi vµ chØ khi cl(a) = cl(b) víi mäi a, b ∈ X. ThËt vËy, gi¶ sö a ∼ b. Cho x ∈ cl(a), tøc lµ x ∼ a. Do ∼ cã tÝnh b¾c cÇu nªn x ∼ b. V× thÕ x ∈ cl(b). Do ®ã cl(a) ⊆ cl(b). T−¬ng tù, cl(b) ⊆ cl(a). Ng−îc l¹i, gi¶ sö cl(a) = cl(b). Do ∼ cã tÝnh ph¶n x¹ nªn a ∈ cl(a). V× thÕ a ∈ cl(b), tøc lµ a ∼ b. 1.1.6 VÝ dô. Cho m ≥ 1 lµ mét sè tù nhiªn. Ta ®Þnh nghÜa quan hÖ ≡ (mod m) trªn Z nh− sau: víi mäi a, b ∈ Z, a ≡ b (mod m) khi vµ chØ khi a − b lµ béi cña m. Quan hÖ nµy ®−îc gäi lµ quan hÖ ®ång d− theo m«®un m. Quan hÖ nµy lµ ph¶n x¹, ®èi xøng vµ b¾c cÇu vµ kh«ng ph¶n xøng. Do ®ã nã lµ quan hÖ t−¬ng ®−¬ng trªn Z. NÕu a ≡ b (mod m) th× ta ®äc lµ a ®ång d− víi b theo m«®un m. Víi mçi a ∈ Z, líp t−¬ng ®−¬ng cña a th−êng ®−îc kÝ hiÖu bëi a vµ gäi lµ líp thÆng d− theo m«®un m víi 9 ®¹i diÖn lµ a. TËp th−¬ng cña Z theo quan hÖ nµy ®−îc kÝ hiÖu bëi Zm vµ ®−îc gäi lµ tËp c¸c líp thÆng d− theo m«®un m hay tËp c¸c sè nguyªn mo®unl« m. Cho a ∈ Z. ViÕt a = mq + r víi 0 6 r 6 m − 1. Khi ®ã a − r lµ béi cña m, tøc lµ a ≡ r (mod m). Suy ra a = r. H¬n n÷a, nÕu r 6= s lµ c¸c sè tù nhiªn sao cho r, s 6 m − 1 th× r − s kh«ng lµ béi cña m. Do ®ã r 6= s. VËy tËp th−¬ng Zm gåm ®óng m phÇn tö, ®ã lµ 0, 1, . . . , m − 1. 1.1.7 MÖnh ®Ò. Cho ∼ lµ quan hÖ t−¬ng ®−¬ng trªn X. Khi ®ã. (i) cl(a) 6= ∅ víi mäi a ∈ X; S (ii) X = cl(a); a∈X (iii) NÕu cl(a) 6= cl(b) th× cl(a) ∩ cl(b) = ∅ víi mäi a, b ∈ X. Chøng minh. (i), (ii). Víi mçi a ∈ X, do tÝnh ph¶n x¹ nªn ta lu«n cã S a ∼ a. V× thÕ a ∈ cl(a). Do ®ã cl(a) 6= ∅ vµ X = cl(a). a∈X (iii). Gi¶ sö cl(a) ∩ cl(b) 6= ∅. Chän c ∈ cl(a) ∩ cl(b). Ta cã a ∼ c vµ c ∼ b. Gi¶ sö x ∈ cl(a). Khi ®ã x ∼ a. Do tÝnh chÊt b¾c cÇu ta cã x ∼ b. V× thÕ x ∈ cl(b). Suy ra cl(a) ⊆ cl(b). T−¬ng tù, cl(a) ⊇ cl(b). Do ®ã cl(a) = cl(b). §Þnh lÝ sau ®©y lµ kÕt qu¶ chÝnh cña tiÕt nµy, cho ta mèi quan hÖ gi÷a c¸c phÐp ph©n ho¹ch víi c¸c quan hÖ t−¬ng ®−¬ng. 1.1.8 §Þnh lý. NÕu ∼ lµ mét quan hÖ t−¬ng ®−¬ng trªn X th× tËp c¸c líp t−¬ng ®−¬ng X/ ∼ = {cl(a) | a ∈ X} lµ mét ph©n ho¹ch cña X. Ng−îc l¹i, nÕu {Xi}i∈I lµ mét phÐp ph©n hoach tËp X th× tån t¹i duy nhÊt mét quan hÖ t−¬ng ®−¬ng trªn X sao cho mçi Xi lµ mét líp t−¬ng ®−¬ng. Chøng minh. Gi¶ sö ∼ lµ mét quan hÖ t−¬ng ®−¬ng trªn X. Theo MÖnh ®Ò 1.1.7, tËp X/ ∼ c¸c líp t−¬ng ®−¬ng cña X theo quan hÖ t−¬ng ®−¬ng ∼ lµm thµnh mét phÐp ph©n ho¹ch trªn X. Ng−îc l¹i, gi¶ sö {Xi}i∈I lµ 10 mét ph©n ho¹ch tËp X. §Þnh nghÜa quan hÖ Ω trªn X nh− sau: víi mäi a, b ∈ X, aΩb khi vµ chØ khi tån t¹i i ∈ I ®Ó a, b ∈ Xi. DÔ thÊy Ω lµ quan hÖ t−¬ng ®−¬ng vµ mçi Xi lµ mét líp t−¬ng ®−¬ng. Gi¶ sö S lµ quan hÖ t−¬ng ®−¬ng trªn X còng cã tÝnh chÊt mçi Xi lµ mét líp t−¬ng ®−¬ng. Cho (a, b) ∈ Ω. Khi ®ã tån t¹i i ∈ I ®Ó a, b ∈ Xi. Theo gi¶ thiÕt vÒ S, tån t¹i c ∈ X sao cho Xi = cl(c)S , trong ®ã ta kÝ hiÖu cl(c)S lµ líp t−¬ng ®−¬ng cña phÇn tö c theo quan hÖ t−¬ng ®−¬ng S. Do a, b ∈ Xi = cl(c)S nªn aSc vµ bSc. Do tÝnh ®èi xøng cña S ta cã aSc vµ cSb. V× S b¾c cÇu nªn aSb, hay (a, b) ∈ S. VËy Ω ⊆ S. Cho (a, b) ∈ S. Khi ®ã ∃i ∈ I ®Ó cl(a)S = Xi. V× aSb nªn b ∈ cl(a)S = Xi, vµ v× aSa nªn a ∈ cl(a)S = Xi. Suy ra a, b ∈ Xi. Do ®ã aΩb hay (a, b) ∈ Ω. VËy Ω = S. 1.1.9 HÖ qu¶. Gi¶ sö X lµ tËp h÷u h¹n. Khi ®ã sè ph©n ho¹ch tËp X chÝnh lµ sè quan hÖ t−¬ng ®−¬ng trªn X. Chøng minh. Theo §Þnh lÝ 1.1.8, ¸nh x¹ cho øng mçi quan hÖ t−¬ng ®−¬ng Ω trªn X víi phÐp ph©n ho¹ch gåm c¸c líp t−¬ng ®−¬ng cña X theo Ω, lµ mét song ¸nh. 1.2 Sè Bell vµ sè Stirling lo¹i hai 1.2.1 §Þnh nghÜa. Sè phÐp ph©n ho¹ch tËp hîp n phÇn tö ®−îc gäi lµ sè Bell thø n vµ ®−îc kÝ hiÖu lµ Bn . Theo §Þnh lÝ 1.1.8, sè Bell thø n chÝnh lµ sè quan hÖ t−¬ng ®−¬ng trªn tËp n phÇn tö. Ta quy −íc sè Bell thø 0 lµ 1, tøc lµ B0 = 1. Theo VÝ dô 1.1.2, c¸c sè Bell thø 1, 2, 3, 4 lÇn l−ît lµ B1 = 1, B2 = 2, B3 = 5, B4 = 15. Mét sè sè Bell ®Çu tiªn trong d·y c¸c sè Bell lµ B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 203, B7 = 877, B8 = 4140, B9 = 21147, B10 = 115975. 11 §Ó tÝnh sè Bell, tøc lµ sè ph©n ho¹ch tËp hîp X gåm n phÇn tö, chóng ta cÇn tÝnh sè ph©n hoach tËp X thµnh k khèi víi k = 1, . . . , n. C¸c sè nµy ®−îc gäi lµ sè Stirling läai hai. 1.2.2 §Þnh nghÜa. Cho X lµ tËp cã n phÇn tö. Sè ph©n ho¹ch tËp X thµnh k khèi ®−îc gäi lµ sè Stirling lo¹i hai vµ ®−îc kÝ hiÖu lµ S(n, k). 1.2.3 VÝ dô. B»ng ph−¬ng ph¸p liÖt kª ta t×m ®−îc sè ph©n ho¹ch tËp hîp gåm 4 phÇn tö thµnh 3 khèi lµ S(4, 3). Sè ph©n ho¹ch tËp hîp gåm 5 phÇn tö thµnh 4 khèi lµ S(5, 4) = 10. §Æc biÖt, sè ph©n ho¹ch cña tËp hîp rçng thµnh 0 khèi lµ 1, sè ph©n ho¹ch tËp hîp kh¸c rçng thµnh 1 khèi lu«n b»ng 1. Sau nµy ta x©y dùng ®−îc sè ph©n ho¹ch thµnh k khèi cña tËp hîp gåm n phÇn tö bÊt k×, ch¼ng h¹n S(10, 4) = 34105, S(10, 5) = 42525. C¸c sè Stirling lo¹i hai xuÊt hiÖn nhiÒu trong c¸c bµi to¸n tæ hîp vµ cã øng dông trong To¸n thèng kª. Ng−êi ta cã thÓ sö dông phÇn mÒm Maple ®Ó tÝnh c¸c sè Stirling lo¹i hai. Sè Stirling lo¹i hai d−îc ®Æt theo tªn cña nhµ to¸n häc James Stirling (1692-1770), ng−êi ®· giíi thiÖu vµ nghiªn cøu kh¸i niÖm nµy vµo ThÕ kØ 18. Chó ý r»ng nÕu {X1 , . . . , Xk } lµ mét ph©n ho¹ch cña tËp X thµnh k khèi th× 1 6 k 6 n, trong ®ã n > 0 lµ sè phÇn tö cña X. V× thÕ ta cã c«ng thøc tÝnh sè Bell th«ng qua sè Stirling lo¹i hai nh− sau. 1.2.4 Bæ ®Ò. Bn = S(n, 1) + . . . + S(n, n − 1) + S(n, n). 1.2.5 VÝ dô. §Ó tÝnh B5 , theo Bæ ®Ò 1.2.4 ta cÇn tÝnh S(5, k) víi k = 1, 2, 3, 4, 5. Ta cã S(5, 1) = 1, S(5, 2) = 15, S(5, 3) = 25, S(5, 4) = 10, S(5, 5) = 1. Do ®ã B5 = S(5, 0) + S(5, 1) + S(5, 2) + S(5, 3) + S(5, 4) + S(5, 5) = 52. 12 Tõ Bæ ®Ò 1.2.4 ta thÊy r»ng c¸c sè Stirling lo¹i hai rÊt quan träng trong viÖc tÝnh to¸n sè Bell. Do ®ã trong phÇn tiÕp theo cña tiÕt nµy chóng ta nghiªn cøu mét sè tÝnh chÊt vÒ sè Stirling lo¹i hai. KÕt qu¶ sau ®©y cho ta mét sè c«ng thøc tÝnh sè Stirling lo¹i hai. Víi n! k ∈ {0, 1, . . . , n}, ta ®Æt Cnk = . Ta gäi Cnk lµ hÖ sè nhÞ thøc thø k!(n − k)! k øng víi n hay sè tæ hîp chËp k cña n phÇn tö. 1.2.6 §Þnh lý. Cho n, k lµ c¸c sè tù nhiªn víi k 6 n. Khi ®ã k 1P (i) S(n, k) = (−1)k−iin Cki . k! i=0 n! P 1 (ii) S(n, k) = . k! i1 +...+ik =n i1 ! . . . ik ! n P (iii) S(n + 1, k) = kn−r S(r, k − 1). r=k−1 Chøng minh. Gi¶ sö cã bé sè (i1, i2 , . . . , ik ) sao cho k P ij = n víi ik ≥ 1. j=1 Ta sÏ x¸c ®Þnh sè c¸ch ph©n ho¹ch tËp X thµnh k tËp con kh«ng rçng sao cho sè phÇn tö cña c¸c tËp lµ ij víi j ∈ {1, 2, . . . , k}. Sè c¸ch chän i1 tõ tËp hîp n phÇn tö cña tËp X lµ Cni1 . Víi mçi c¸ch chän i1 phÇn tö th× i2 cã Cn−i c¸ch chän i2 phÇn tö. Víi mçi c¸ch chän i1 phÇn tö vµ i2 phÇn 1 i3 tö th× cã Cn−i c¸ch chän i3 phÇn tö. Tæng qu¸t víi mçi c¸ch chän i1 1 −i2 ik phÇn tö vµ . . . ik−1 phÇn tö th× cã Cn−i c¸ch chän ik phÇn tö. H¬n 1 −i2 −...−ik n÷a, c¸c tËp con cña ph©n ho¹ch kh«ng ph©n biÖt thø tù, tøc lµ bé sè sau kh«ng ph©n biÖt thø tù (i1 , i2 , . . . , ik ). Do ®ã sè c¸ch ph©n ho¹ch tËp hîp X thµnh k tËp con kh«ng rçng sao cho sè phÇn tö cña c¸c tËp lµ ij víi 1 1 n! i2 ik j ∈ {1, 2, . . . , k} b»ng Cni1 Cn−i . . .C hay hay n−i −i −...−i 1 1 2 k k! k! i1 !i2 !. . .ik ! n! 1 . Sè c¸ch ph©n ho¹ch tËp hîp X thµnh k tËp con kh«ng rçng k! i1 !i2 !. . .ik ! P n! 1 n! P 1 lµ S(n, k) = ( ) hay S(n, k) = . k! i1 +...+ik =n i1 ! . . . ik ! i1 +...+ik =n k! i1 ! . . . ik ! 13 1.2.7 VÝ dô. Gi¶ sö ta cÇn t×m S(5, 3). Sö dông §Þnh lÝ 1.2.6(i) ta cã S(5, 3) = 1 [(−1)3 05 C30 + (−1)2 15 C31 + (−1)0 35 C33 = 25. 3! Gi¶ sö ta cÇn t×m S(6, 4). Sö dông §Þnh lÝ 1.2.6(i) ta cã 1 [(−1)4 06 C40 4! + (−1)3 16 C41 + (−1)2 26 C42 + (−1)36 C43 + (−1)0 46 C44 ] = 65. S(6, 4) = Chóng ta còng cã thÓ sö dông §Þnh lÝ 1.2.6 (ii) ®Ó tÝnh S(6, 4). B»ng c¸ch sö dông §Þnh lÝ 1.2.6 (iii) ta ®−îc 5 X S(6, 4) = 45−r S(r, 3) = 42 S(3, 3) + 4S(4, 3) + S(5, 3) r=3 = 16 + 24 + 25 = 60 hoÆc 6 X S(7, 4) = 46−r S(r, 3) = 43 S(3, 3) + 42 S(4, 3) + 4S(5, 3) + S(6, 3) r=3 = 64 + 96 + 100 + 90 = 350. (1.1) (1.2) C«ng thøc tÝnh sè Sirling lo¹i 2 b»ng c¸ch trùc tiÕp nh− trong §Þnh lÝ 1.2.6(i) víi sè n gÆp kh¸ nhiÒu khã kh¨n khi sè tù nhiªn n lín dÇn lªn. MÖnh ®Ò sau ®©y sÏ gióp ta kh¾c phôc ®−îc mét phÇn nh÷ng khã kh¨n ®ã. 1.2.8 MÖnh ®Ò. Cho n, k lµ c¸c sè tù nhiªn víi 2 6 k 6 n. Khi ®ã S(n + 1, k) = kS(n, k) + S(n, k − 1). Chøng minh. XÐt tËp hîp bÊt k× cã n + 1 phÇn tö, ch¼ng h¹n A = {x1 , x2 , x3 , . . . , xn+1 }. 14 Theo ®Þnh nghÜa S(n + 1, k) lµ sè ph©n ho¹ch tËp hîp A thµnh k khèi. MÆt kh¸c ta cã thÓ chia tËp B tÊt c¶ c¸c ph©n ho¹ch trªn thµnh 2 tËp con rêi nhau nh− sau: B1 gåm tÊt c¶ c¸c ph©n ho¹ch cña tËp hîp A thµnh k khèi trong ®ã cã mét khèi lµ {xn+1 }, cßn B2 gåm tÊt c¶ c¸c ph©n ho¹ch cña tËp hîp A thµnh k khèi trong ®ã kh«ng cã khèi nµo lµ {xn+1 }. Khi ®ã mçi ph©n ho¹ch thuéc B1 sÏ chia tËp hîp {x1 , x2 , x3 , . . . , xn } thµnh k − 1 khèi vµ cã S(n, k − 1) c¸ch chia nh− thÕ. Do ®ã lùc l−îng cña B1 lµ S(n, k − 1). NÕu {xn+1 } kh«ng lµ mét khèi th× xn+1 sÏ n»m trong mét khèi víi Ýt nhÊt mét phÇn tö kh¸c cña A. V× cã S(n, k) c¸ch ph©n ho¹ch tËp hîp {x1 , x2 , x3 , . . . , xn } thµnh k khèi nªn ta cã tÊt c¶ kS(n, k) c¸ch ph©n ho¹ch cña tËp hîp A thµnh k khèi, trong ®ã kh«ng cã khèi nµo lµ xn+1 . Do ®ã lùc l−îng cña B2 lµ kS(n, k). Theo qui t¾c céng, ta cã: S(n + 1, k) = kS(n, k) + S(n, k − 1). 1.2.9 VÝ dô. Ch¼ng h¹n khi ®· biÕt S(5, 3) = 25, S(5, 4) = 10 th× cã thÓ tÝnh ®−îc S(6, 4) b»ng c«ng thøc sau ®©y S(6, 4) = 4S(5, 4) + S(5, 3) = 40 + 25 = 65. Nh− vËy, víi c«ng thøc truy håi trªn cã −u ®iÓm rÊt lín so víi c«ng thøc tÝnh sè Sirling lo¹i 2 b»ng c¸ch trùc tiÕp nh− trong §Þnh lÝ 1.2.6(i) víi sè n lín. PhÇn cuèi cña tiÕt nµy tr×nh bµy mét c«ng thøc tæng qu¸t ®Ó tÝnh sè Stirling lo¹i hai cña mét tËp hîp gåm n phÇn tö víi ph©n ho¹ch thµnh k khèi, ch¼ng h¹n k = 2, 3, 4, 5, n − 1, n − 2. 1.2.10 MÖnh ®Ò. Ta cã c¸c ®¼ng thøc sau (i) S(n, 2) = 2n−1 − 1, n ≥ 2; 3n − 3.2n + 3 (ii) S(n, 3) = , n ≥ 3; 6 15 4n − 4.3n + 6.2n − 4 (iii) S(n, 4) = , n ≥ 4; 24 5n−1 − 4n + 2.3n − 2n+1 + 1 , n ≥ 5; (iv) S(n, 5) = 24 (v) S(n, n − 1) = Cn2 , n ≥ 2; (vi) S(n, n − 2) = Cn3 + 3Cn4 , n ≥ 4. Chøng minh. Ta sÏ chøng minh c¸c ®¼ng thøc trªn b»ng ph−¬ng ph¸p qui n¹p ®ång thêi kÕt hîp víi c«ng thøc truy håi S(n + 1, k) = kS(n, k) + S(n, k − 1). (i) Khi n = 2, ta cã S(n, 2)=S(2, 2) = 1 vµ 2n−1 − 1 = 2 − 1 = 1, do ®ã ®¼ng thøc ®óng víi n = 2. Gi¶ sö ®¼ng thøc ®óng víi n = k ≥ 2, tøc lµ S(k, 2) = 2k−1 − 1. Ta cÇn chøng minh ®¼ng thøc ®óng víi n = k + 1. Ta cã S(k + 1, 2) = 2S(k, 2) + S(k, 1) = 2S(k, 2) + 1 = (2k−1 − 1)2 + 1 = 2k − 1. Ngoµi ra c«ng thøc trªn cßn cã thÓ lÝ gi¶i nh− sau: Mçi c¸ch ph©n ho¹ch tËp hîp X gåm n phÇn tö thµnh 2 tËp con A vµ B th× 2 tËp con ®ã lµ bï cña nhau, tøc lµ A = X B. Mµ cã 2n cÆp (A, B) cã thø tù, bao gåm c¶ hai cÆp (A, ∅), (∅, B). Nh− vËy, nÕu kh«ng tÝnh hai cÆp nµy th× cã 2n − 2 cÆp bï nhau cã thø tù. V× trong ph©n ho¹ch ta kh«ng xÐt thø tù cña c¸c 2n − 2 cÆp nªn sè cÆp kh«ng cã thø tù lµ = 2n−1 − 1. 2 (ii) Khi n = 3, ta cã S(n, 3) = S(3, 3) = 1 vµ 3n − 3.2n + 3 33 − 3.23 + 3 = = 1. 6 6 Do ®ã ®¼ng thøc ®óng víi n = 3. Gi¶ sö ®¼ng thøc ®óng víi n = k ≥ 3, 3k − 3.2k + 3 tøc lµ S(k, 3) = . Ta cÇn chøng minh ®¼ng thøc ®óng víi 6 16 n = k + 1. ThËt vËy, ta cã 3k − 3.2k + 3 + 2k−1 − 1 S(k + 1, 3) = 3S(k, 3) + S(k, 2) = 3 6 k 3 − 2.2k + 1 . = 2 (iii) Khi n = 4, ta cã S(n, 4) = S(4, 4) = 1 vµ 4n − 4.3n + 6.2n − 4 44 − 4.34 + 6.24 − 4 = = 1. 24 24 Do ®ã ®¼ng thøc ®óng víi n = 4. Gi¶ sö ®¼ng thøc ®óng víi n = k ≥ 4, 4k − 4.3k + 6.2k − 4 tøc lµ S(k, 4) = . Ta cÇn chøng minh ®¼ng thøc ®óng 24 víi n = k + 1. ThËt vËy, ta cã S(k + 1, 4) = 4S(k, 4) + S(k, 3). Theo kÕt 3k − 3.2k + 3 qu¶ (ii) ë trªn ta cã S(k, 3) = . Suy ra 6 4k − 4.3k + 6.2k − 4 3k − 3.2k + 3 + 24 6 k+1 k+1 k+1 4 − 4.3 + 6.2 −4 = . 24 S(k + 1, 4) = 4 (iv) Khi n = 5, ta cã: S(n, 5) = S(5, 5) = 1 vµ 5n−1 − 4n + 2.3n − 2n+1 + 1 54 − 45 + 2.35 − 26 + 1 = = 1. 24 24 V× thÕ ®¼ng thøc ®óng víi n = 5. Gi¶ sö ®¼ng thøc ®óng víi n = k ≥ 5, tøc lµ 5k−1 − 4k + 2.3k − 2k+1 + 1 . 24 Ta cÇn chøng minh ®¼ng thøc ®óng víi n = k + 1. ThËt vËy, ta cã S(k + S(k, 5) = 1, 5) = 5S(k, 5) + S(k, 4). Theo kÕt qu¶ (iii) ë trªn ta cã 4k − 4.3k + 6.2k − 4 S(k, 4) = . 24 17 V× thÕ 5k−1 − 4k + 2.3k − 2k+1 + 1 4k − 4.3k + 62k − 4 + S(k + 1, 5) = 5 24 24 k k+1 k+1 k+2 + 2.3 −2 +1 5 −4 = . 24 (v) Khi n = 2, ta cã S(2, 1) = C22 = 1, do ®ã ®¼ng thøc ®óng víi n = 2. Gi¶ sö ®¼ng thøc ®óng víi n = k, tøc lµ S(k, k − 1) = Ck2 , k ≥ 2, k ∈ N . Ta cÇn chøng minh ®¼ng thøc ®óng víi n = k + 1. ThËt vËy, ta cã 2 S(k + 1, k) = kS(k, k) + S(k, k − 1) = k + Ck2 = Ck+1 . (vi) Khi n = 4, ta cã S(4, 2) = 7, C43 + 3C44 = 7 nªn ®¼ng thøc ®· cho ®óng víi n = 4. Gi¶ sö ®¼ng thøc ®· cho ®óng víi n = k, tøc lµ S(k, k − 2) = Ck3 + 3Ck4, k ≥ 4, k ∈ N . Ta cÇn chøng minh ®¼ng thøc ®óng víi n = k + 1. ThËt vËy, ta cã S(k + 1, k − 1) = (k − 1)S(k, k − 1) + S(k, k − 2) 3 4 = (k − 1)Ck2 + Ck3 + 3Ck4 = Ck+1 + 3Ck+1 . 1.2.11 VÝ dô. Theo c«ng thøc trong mÖnh ®Ò trªn ta cã 38 − 3.28 + 3 = 966; 6 410 − 4.310 + 6.210 − 4 S(10, 4) = = 34105. 24 S(8, 3) = Nh− vËy c¸c c«ng thøc trong mÖnh ®Ò trªn mang hiÖu øng kh¸ m¹nh gióp ta cã thÓ tra cøu sè ph©n ho¹ch cña tËp hîp gåm n phÇn tö thµnh k khèi víi nh÷ng gi¸ trÞ cña k ®Æc biÖt ë trªn. 18 1.3 Mét sè c«ng thøc tÝnh hµm ph©n ho¹ch tËp hîp Hµm ph©n ho¹ch tËp hîp lµ hµm biÕn nguyªn víi gi¸ trÞ nguyªn ®−îc cho bëi c«ng thøc f (n) = Bn víi mäi n ∈ N. Môc tiªu cña tiÕt nµy lµ chøng minh chi tiÕt mét sè c«ng thøc tÝnh hµm ph©n ho¹ch tËp hîp, tøc lµ tÝnh sè Bell Bn , ®ång thêi ®−a ra tam gi¸c Pascal tÝnh hµm ph©n ho¹ch tËp hîp. 1.3.1 MÖnh ®Ò. Ta cã c«ng thøc truy håi sau ®©y. Bn+1 n X = Cnk Bk = Cn0 B0 + Cn1 B1 + Cn2 B2 + . . . + Cnk Bk + . . . + Cnn Bn . k=0 Chøng minh. Ta x©y dùng phiÕm hµm tuyÕn tÝnh L : R[x] → R x¸c ®Þnh bëi (x)k = Akx = x(x − 1) . . . (x − k + 1) → L((x)k ) = 1 víi n P mäi k = 0, 1, 2 . . .. Ta chøng minh ®−îc xn = S(n, k)Akx . Do ®ã L(xn ) = n P S(n, k)L((x)k ) = n P k=0 S(n, k) = Bn . Ta cã r=0 k=0 (x)n+1 = x(x − 1) . . . (x − n) = x(x − 1)n . Suy ra L((x)n+1 ) = L((x)n) = L(x(x − 1)n ). Do ®ã L(p(x)) = L((x)n) = L(xP (x − 1)) víi mäi P (x). B©y giê ta cho P (x) = (x + 1)n , ta ®−îc L((x + 1)n ) = L(xn+1 ), hay n X Cnk L(xk ) = Bn+1 . k=0 Nh− vËy, n P Cnk Bk = Bn+1 . k=0 1.3.2 VÝ dô. B5 = C40 B0 + C41 B1 + C42 B2 + C43 B3 + C44 B4 = 1 + 4 + 12 + 20 + 15 = 52 B10 = C90 B0 + C91 B1 + C92 B2 + C93 B3 + C94 B4 + C95 B5 + C96 B6 + C97 B7 + C98 B8 + C99 B9 = 1 + 9 + 72 + 420 + 1890 + 6552 + 17052 + 31572 + 37260 + 21147 = 115975 19 Sau ®©y ta sÏ ®−a ra tam gi¸c Bell ®Ó tÝnh sè ph©n ho¹ch cña tËp hîp gåm n phÇn tö víi n nhËn nh÷ng gi¸ trÞ ®Çu tiªn lµ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. §©y lµ kÕt qu¶ tæng hîp cña nh÷ng ®Þnh lÝ, mÖnh ®Ò ë trªn. Tr−íc hÕt ta m« t¶ c¸ch x©y dùng tam gi¸c Bell qua chó ý sau ®©y. 1.3.3 Chó ý. C¸c sè Bell cã thÓ tÝnh dÔ dµng b»ng c¸ch x©y dùng tam gi¸c Bell, cßn ®−îc gäi lµ d·y Aitken hoÆc tam gi¸c Pierce. Ta cã thÓ m« t¶ c¸ch x©y dùng tam gi¸c Bell nh− sau: B¾t ®Çu víi sè 1 vµ ®Æt sè nµy trªn dßng thø nhÊt. T¹o mét dßng míi b»ng c¸ch lÊy phÇn tö bªn ph¶i cña dßng ngay trªn nã lµm phÇn tö ®Çu tiªn bªn tr¸i cña dßng míi. LÇn l−ît c¸c sè tiÕp theo cña dßng míi b»ng c¸ch lÊy tæng phÇn tö bªn tr¸i nã víi phÇn tö ®øng cïng cét phÇn tö Êy ë dßng tr−íc nã. TiÕp tôc b−íc ba cho ®Õn khi sè phÇn tö cña dßng míi nhiÒu h¬n sè phÇn tö cña dßng trªn mét phÇn tö. Sè n»m phÝa ph¶i mçi dßng lµ sè Bell cho mçi dßng. Cô thÓ tam gi¸c Bell còng cã qui luËt thiÕt lËp cô thÓ, cã nÐt t−¬ng tù nh− qui luËt thiÕt lËp tam gi¸c Pascal cña c¸c sè tæ hîp. Hµng ®Çu tiªn lµ ch÷ sè 1, ®©y lµ sè Bell ®Çu tiªn. Víi mäi i ≥ 1 hµng thø i + 1 ®−îc ®iÒn theo nguyªn t¾c sau ®©y: Ch÷ sè cuèi cïng cña hµng thø i ®−îc ®Æt lªn ®Çu hµng thø i + 1. Víi mäi j > 1 sè thø j cña hµng i + 1 lµ tæng cña sè thø j − 1 cña hµng i + 1 vµ sè thø j − 1 cña hµng i. Sè cuèi cïng cña hµng i + 1 lµ sè Bell cña hµng ®ã.