Nội dung

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp Nguyeãn Anh Thi ÑH KHTN, Tp HCM 2017 Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 1 / 99 Chöông 2 TOÅ HÔÏP TÍNH TOAÙN Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 2 / 99 Noäi dung Noäi dung 1 2 3 4 5 6 Caùc baøi toaùn ñeám Caùc nguyeân lyù Giaûi tích toå hôïp Hoaùn vò laëp, toå hôïp laëp Ñònh lyù nhò thöùc Phaân hoaïch Phaân hoaïch taäp hôïp Phaân hoaïch soá nguyeân Chu trình trong hoaùn vò Nguyeân lyù buø tröø Haøm sinh Ñònh nghóa haøm sinh Heä soá haøm sinh Phaân hoaïch Haøm sinh muõ Phöông phaùp toång Baøi toaùn ñeä quy Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 3 / 99 Caùc baøi toaùn ñeám Caùc nguyeân lyù Caùc nguyeân lyù Nguyeân lyù coäng: Giaû söû ñeå laøm coâng vieäc A ta coù theå choïn moät trong hai bieän phaùp khaùc nhau (theo nghóa laø caùch thöïc hieän bieän phaùp thöù nhaát luoân luoân khaùc caùch thöïc hieän bieän phaùp thöù hai). Neáu bieän phaùp thöù nhaát coù m caùch, bieän phaùp thöù hai coù n caùch, thì ta coù soá caùch laøm coâng vieäc A laø m + n. Toång quaùt, giaû söû ñeå laøm coâng vieäc A ta coù theå choïn moät trong k bieän phaùp khaùc nhau, moãi bieän phaùp coù mi caùch laøm vôùi i = 1, 2, . . . , k, khi ñoù soá caùch laøm coâng vieäc A laø m1 + m2 + · · · + mk . Ví duï Ta choïn moät vieân bi baát kyø töø hai hoäp A vaø B. Bieát raèng hoäp A chöùa 5 vieân bi maøu ñoû, hoäp B chöùa 3 vieân bi maøu xanh. Vaäy soá caùch choïn laø 5 + 3 = 8. Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 4 / 99 Caùc baøi toaùn ñeám Caùc nguyeân lyù Caùc nguyeân lyù Nguyeân lyù nhaân: Giaû söû chuùng ta phaûi thöïc hieän moät coâng vieäc bao goàm hai coâng vieäc keá tieáp nhau. Ñeå thöïc hieän coâng vieäc thöù nhaát chung ta coù m caùch, vaø öùng vôùi moãi caùch choïn thöïc hieän coâng vieäc thöù nhaát ta coù n caùch thöïc hieän coâng vieäc thöù hai.Vaäy ta coù soá caùch thöïc hieän coâng vieäc ñoù laø m.n. Toång quaùt, Giaû söû moät coâng vieäc bao goàm k böôùc keá tieáp nhau, neáu moãi böôùc ta coù ni caùch laøm vôùi i = 1, 2, . . . , k. Vaäy ta coù n1 .n2 . . . . .nk caùch ñeå thöïc hieän coâng vieäc. Ví duï Ta choïn hai vieân bi maøu khaùc nhau töø hai hoäp A vaø B. Bieát raèng hoäp A chöùa 5 vieân bi maøu ñoû, hoäp B chöùa 3 vieân bi maøu xanh. Vaäy soá caùch choïn laø 5.3 = 15. Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 5 / 99 Caùc baøi toaùn ñeám Giaûi tích toå hôïp Giaûi tích toå hôïp Ñònh nghóa Cho taäp hôïp A coù n phaàn töû. Moãi caùch saép ñaët coù thöù töï n phaàn töû cuûa A ñöôïc goïi laø moät hoaùn vò coù n phaàn töû. Soá caùc hoaùn vò cuûa n phaàn töû kyù hieäu laø Pn , vaø Pn = n! = n.(n − 1).(n − 2)...2.1, quy öôùc 0! = 1. Ví duï Cho X laø taäp hôïp coù n phaàn töû thì soá song aùnh töø X vaøo X laø n! Cho A = {a, b, c}. Khi ñoù A coù caùc hoaùn vò sau: abc, acb, bac, bca, cab, cba. Cho X = {1, 2, 3, 4, 5}, hoûi coù bao nhieâu soá töï nhieân goàm 5 chöõ soá khaùc nhau ñöôïc taïo thaønh töø taäp X? Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 6 / 99 Caùc baøi toaùn ñeám Giaûi tích toå hôïp Giaûi tích toå hôïp Ñònh nghóa Cho A laø taäp hôïp goàm n phaàn töû. Moãi boä goàm k phaàn töû (1 ≤ k ≤ n) saép thöù töï cuûa taäp hôïp A ñöôïc goïi laø moät chænh hôïp chaäp k cuûa n phaàn töû. Soá n! caùc chænh hôïp chaäp k cuûa n, kyù hieäu laø Akn . Ta coù coâng thöùc Akn = (n−k)! Ví duï Cho X = {a, b, c}. Khi ñoù X coù caùc chænh hôïp chaäp 2 cuûa caùc phaàn töû cuûa X laø: ab, ac, bc, ba, ca, cb. Ví duï Coù bao nhieâu soá töï nhieân goàm 3 chöõ soá khaùc nhau ñöôïc taïo thaønh töø {1, 2, 3, 4, 5, 6} ? Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 7 / 99 Caùc baøi toaùn ñeám Giaûi tích toå hôïp Giaûi tích toå hôïp Ñònh nghóa Cho taäp hôïp A goàm n phaàn töû. Moãi taäp con goàm k phaàn töû cuûa A ñöôïc goïi laø moät toå hôïp chaäp k cuû a nphaàn töû. Soá caùc toå hôïp chaäp k cuûa n phaàn töû n . Ta coù coâng thöùc ñöôïc kyù hieäu laø Ckn hay k Ckn = n! k!(n − k)! Tính chaát Cn−k = Ckn n Ckn + Ck−1 = Ckn+1 n Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 8 / 99 Caùc baøi toaùn ñeám Giaûi tích toå hôïp Ví duï Cho X = {1, 2, 3, 4}. Toå hôïp chaäp 3 cuûa 4 phaàn töû cuûa X laø {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} Ví duï Moät lôùp coù 30 hoïc sinh, hoûi coù bao nhieâu caùch choïn 10 baïn. Soá caùch choïn laø toå hôïp chaäp 10 cuûa 30: C10 30 . Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 9 / 99 Caùc baøi toaùn ñeám Hoaùn vò laëp, toå hôïp laëp Hoaùn vò laëp, toå hôïp laëp Ñònh nghóa Cho n ñoái töôïng trong ñoù coù ni ñoái töôïng loaïi i gioáng heät nhau (i = 1, 2, . . . , k; n1 + n2 + · · · + nk = n). Moãi caùch saép xeáp coù thöù töï n ñoái töôïng ñaõ cho goïi laø moät hoaùn vò laëp cuûa n. Soá hoaùn vò cuûa n ñoái töôïng, trong ñoù coù n1 ñoái töôïng gioáng nhau thuoäc loaïi 1, n2 ñoái töôïng gioáng nhau thuoäc loaïi 2,. . . , nk ñoái töôïng gioáng nhau thuoäc loaïi k, laø n! n1 !n2 ! . . . nk ! Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 10 / 99