tailieunhanh - 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,. . | 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 .