Bài giảng Toán học tổ hợp - Chương 5: Phương pháp đếm dùng hàm sinh cung cấp cho người học những kiến thức 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; Bài toán đệ quy. Mời các bạn cùng tham khảo! | 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 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ø m m 2 m A x 1 x x xm 1 x m 1 2 m 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 soá 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á vieân bi maøu xanh ñöôïc choïn e2 laø soá vieân bi maøu traéng e3 laø soá vieân bi maøu ñoû vaø e4 laø soá vieân bi maøu vaøng. Nguyeãn Anh Thi ÑH KHTN Tp HCM Baøi giaûng Toaùn toå hôïp 5 54 Ñònh nghóa haøm sinh Ñònh nghóa haøm sinh Ta xaây döïng moät tích cuûa caùc nhaân töû ña thöùc sao cho sau khi nhaân caùc ña thöùc ñoù laïi vôùi nhau ta ñöôïc taát caû caùc haïng töû coù daïng xe1 xe2 xe3 xe4 trong ñoù 0 ei 3. Nhö vaäy ta caàn 4 nhaân töû vaø moãi nhaân töû baèng 1 x x2 x3 bao goàm taát caû caùc luõy thöøa nhoû hôn hay baèng 3 cuûa x. Ta ñöôïc haøm sinh caàn tìm laø 1 x x2 x3 4 1 4x 10x2 20x3 31x4 40x5 44x6 31x8 40x7 20x9 10x10 4x11 x12 . Nguyeãn Anh Thi ÑH KHTN Tp HCM Baøi giaûng Toaùn toå hôïp 6 54 Ñònh nghóa haøm sinh Ñònh nghóa haøm sinh Ví duï Tìm haøm sinh .
