tailieunhanh - Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 2 - Nguyễn Anh Thi

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 / .

• Toán học
• Bài giảng Toán học tổ hợp và cấu trúc rời rạc
• Toán học tổ hợp
• Cấu trúc rời rạc
• Phương pháp đếm dùng hàm sinh
• Định nghĩa hàm sinh
• Hệ số hàm sinh
• Tổ hợp cơ bản
• Khai triển luỹ thừa của đa thức
• Các bài toán về đường đi
• Đồ thị Hamilton
• Đồ thị Euler
• Đại cương về đồ thị
• Biểu diễn đồ thị
• Đẳng cấu đồ thị
• Một số kỹ thuật đếm
• Sử dụng sơ đồ Ven
• Nguyên lý bù trừ
• Cây khung ngắn nhất
• Cây có gốc
• Toán học rời rạc
• Tổ hợp căn bản
• Tổ hợp lặp
• Khai triển lũy thừa
• Khai triển đa thức
• Bài giảng Toán học tổ hợp
• Bài toán về đường đi
• Tìm đường đi ngắn nhất
• Hàm sinh mũ
• Kỹ thuật đếm
• Phép duyệt cây