TAILIEUCHUNG - 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,.! | Bài giảng Toán học tổ hợp và Cấu trúc rời rạc Nguyễn Anh Thi ĐH KHTN, Tp HCM 2016 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 1 / 54 Chương 2 PHƯƠNG PHÁP ĐẾM DÙNG HÀM SINH Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 2 / 54 Nội dung Nội dung 1 Định nghĩa hàm sinh 2 Hệ số hàm sinh 3 Phân hoạch 4 Hàm sinh mũ 5 Phương pháp tổng 6 Bài toán đệ quy Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 3 / 54 Định nghĩa hàm sinh Định nghĩa hàm sinh Định nghĩa Cho {an }n≥0 là một dãy các số thực, thì chuỗi lũy thừa hình thức A(x) = n≥0 an xn được gọi là hàm sinh thông thường (hay hàm sinh) của dãy {an }n≥0 . Ví dụ Xét tập hợp X với m phần tử, gọi an là số tập con có n phần tử của X, m an = . n Ta được hàm sinh của dãy số thực {an }n≥0 là A(x) = 1 + n 1 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) x+ n 2 x2 + · · · + · · · + Bài giảng Toán học tổ hợp và Cấu trúc rời rạc n n xn = (1 + x)n 2016 4 / 54 Định nghĩa hàm sinh Định nghĩa hàm sinh Ví dụ Tìm hàm sinh của ar , với ar là số cách để chọn r viên bi từ 3 viên bi màu xanh, 3 viên bi màu trắng, 3 viên bi màu đỏ, và 3 viên bi màu vàng. Bài toán trên có thể đưa về bài toán tìm nghiệm nguyên của phương trình e1 + e2 + e3 + e4 = r với 0 ≤ ei ≤ 3. Ở đây e1 là số quả cầu màu xanh được chọn, e2 là số quả cầu màu trắng, e3 là số quả cầu màu đỏ, và e4 là số quả cầu màu vàng. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạ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