Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 2 Phương pháp đếm dùng hàm sinh do Nguyễn Anh Thi biên soạn với các nội dung chính như: Định nghĩa hàm sinh, hệ số hàm sinh, phân hoạch, hàm sinh mũ, phương pháp tổng,.! | Baøi giaûng Toaùn hoïc toå hôïp vaø Caáu truùc rôøi raïc Nguyeãn Anh Thi ÑH KHTN, Tp HCM 2016 Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Toaùn hoïc toå hôïp vaø Caáu truùc rôøi raïc 2016 1 / 54 Chöông 2 PHÖÔNG PHAÙP ÑEÁM DUØNG HAØM SINH Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Toaùn hoïc toå hôïp vaø Caáu truùc rôøi raïc 2016 2 / 54 Noäi dung Noäi dung 1 Ñònh nghóa haøm sinh 2 Heä soá haøm sinh 3 Phaân hoaïch 4 Haøm sinh muõ 5 Phöông phaùp toång 6 Baøi toaùn ñeä quy Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Toaùn hoïc toå hôïp vaø Caáu truùc rôøi raïc 2016 3 / 54 Ñònh nghóa haøm sinh Ñònh nghóa haøm sinh Ñònh nghóa Cho {an }n≥0 laø moät daõy caùc soá thöïc, thì chuoãi luõy thöøa hình thöùc A(x) = n≥0 an xn ñöôïc goïi laø haøm sinh thoâng thöôøng (hay haøm sinh) cuûa daõy {an }n≥0 . Ví duï Xeùt taäp hôïp X vôùi m phaàn töû, goïi an laø soá taäp con coù n phaàn töû cuûa X, m an = . n Ta ñöôïc haøm sinh cuûa daõy soá thöïc {an }n≥0 laø A(x) = 1 + n 1 Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) x+ n 2 x2 + · · · + · · · + Baøi giaûng Toaùn hoïc toå hôïp vaø Caáu truùc rôøi raïc n n xn = (1 + x)n 2016 4 / 54 Ñònh nghóa haøm sinh Ñònh nghóa haøm sinh Ví duï Tìm haøm sinh cuûa ar , vôùi ar laø soá caùch ñeå choïn r vieân bi töø 3 vieân bi maøu xanh, 3 vieân bi maøu traéng, 3 vieân bi maøu ñoû, vaø 3 vieân bi maøu vaøng. Baøi toaùn treân coù theå ñöa veà baøi toaùn tìm nghieäm nguyeân cuûa phöông trình e1 + e2 + e3 + e4 = r vôùi 0 ≤ ei ≤ 3. ÔÛ ñaây e1 laø soá quaû caàu maøu xanh ñöôïc choïn, e2 laø soá quaû caàu maøu traéng, e3 laø soá quaû caàu maøu ñoû, vaø e4 laø soá quaû caàu maøu vaøng. Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Toaùn hoïc toå hôïp vaø Caáu truùc rôøi raïc 2016 5 / .
