Bài giảng Nhập môn lý thuyết tổng hợp: Chương 2 - Nguyễn Anh Thi

Bài giảng Nhập môn lý thuyết tổng hợp Chương 2 Tổ hợp tính Toán trinh bày các nội dung bài học như sau: Các bài Toán đếm; Định lý nhị thức; Phân hoạch; Chu trình trong hoán vị; Nguyên lý bù trừ; Hàm sinh,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn lý thuyết tổng hợp: Chương 2 - Nguyễn Anh ThiBaøi giaûng Nhaäp moân Lyù Thuyeát Toå HôïpNguyeãn Anh ThiÑH KHTN, Tp HCM2017Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp20171 / 99Chöông 2TOÅ HÔÏP TÍNH TOAÙNNguyeãn Anh Thi ( ÑH KHTN, Tp HCM)Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp20172 / 99Noäi dungNoäi dung123456Caùc baøi toaùn ñeámCaùc nguyeân lyùGiaûi tích toå hôïpHoaùn vò laëp, toå hôïp laëpÑònh lyù nhò thöùcPhaân hoaïchPhaân hoaïch taäp hôïpPhaân hoaïch soá nguyeânChu trình trong hoaùn vòNguyeân lyù buø tröøHaøm sinhÑònh nghóa haøm sinhHeä soá haøm sinhPhaân hoaïchHaøm sinh muõPhöông phaùp toångBaøi toaùn ñeä quyNguyeãn Anh Thi ( ÑH KHTN, Tp HCM)Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp20173 / 99Caùc baøi toaùn ñeámCaù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 haibieän phaùp khaùc nhau (theo nghóa laø caùch thöïc hieän bieän phaùp thöù nhaátluoâ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átcoù 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 Alaø 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änphaù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ânbi 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ôïp20174 / 99Caùc baøi toaùn ñeámCaù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àmhai 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ù ncaù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ãiböôù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 Achöù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ïnlaø 5.3 = 15.Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp20175 / 99