Bài giảng "Toán tổ hợp - Chương 2: Phương pháp đếm dùng hàm sinh" trình bày đị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, bài toán đệ quy,. nội dung chi tiết. | Baøi giaûng Toaùn toå hôïp Nguyeãn Anh Thi ÑH KHTN, Tp HCM Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Toaùn toå hôïp 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 toå hôïp 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 toå hôïp 3 / 54 Ñònh nghóa haøm sinh Ñònh nghóa haøm sinh Ñònh nghóa Cho {anP }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ø n n n 2 x + ··· + ··· + xn = (1 + x)n A(x) = 1 + x+ 1 2 n Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Toaùn toå hôïp 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 toå hôïp 5 / .
