tailieunhanh - Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 2 - Lê Văn Luyện

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" trình bày các định nghĩa, hệ số hàm sinh, sự phân loại, hàm sinh mũ, phương pháp tổng, hệ thức đệ quy. nội dung chi tiết. | Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 2 - Lê Văn Luyện 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 lvluyen@ FB: Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh lvluyen@ Chương 2. Phương pháp đếm dùng hàm sinh 09/2016 1/42 Nội dung Chương 2. PHƯƠNG PHÁP ĐẾM DÙNG HÀM SINH 1. Định nghĩa 2. Hệ số hàm sinh 3. Sự phân hoạch 4. Hàm sinh mũ 5. Phương pháp tổng 6. Hệ thức đệ quy lvluyen@ Chương 2. Phương pháp đếm dùng hàm sinh 09/2016 2/42 . Định nghĩa hàm sinh Định nghĩa. Cho {ar }r≥0 là một dãy các số thực. Khi đó chuỗi lũy thừa hình thức X G(x) = a0 + a1 x + a2 x2 + · · · + ar xr + · · · = ar xr r≥0 được gọi là hàm sinh của dãy {ar }r≥0 . Ví dụ. Hàm sinh của dãy 1, 1, 1, 1, 1, 1 là G(x) = 1 + x + x2 + x3 + x4 + x5 Ví dụ. Xét tập hợp X với n phần tử, gọi ar là số tập con có r phần tử n n của X. Khi đó ar = với là tổ hợp chập r của n phần tử r r Ta được hàm sinh của dãy số thực {ar }r≥0 là n n 2 n G(x) = 1 + x+ x + ··· + xn = (1 + x)n 1 2 n lvluyen@ Chương 2. Phương pháp đếm dùng hàm sinh 09/2016 3/42 Ví dụ. Tìm hàm sinh của dãy {ar }r≥0 , 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. Giải. Để tìm ar , ta đưa bài toán về bài toán tìm số nghiệm nguyên của phương trình e1 + e2 + e3 + e4 = r với 0 ≤ ei ≤ 3. Ở đây e1 , e2 , e3 , e4 tương ứng là số viên bi màu xanh, trắng, đỏ và vàng. Đề tìm hàm sinh của {ar }r≥0 ta xây dựng các nhân tử đa thức sao cho sau khi nhân các đa thức đó lại với nhau ta được tất cả các hạng tử có dạng xe1 xe2 xe3 xe4 , trong đó 0 ≤ ei ≤ 3 và e1 + e2 + e3 + e4 = r. Như vậy ta cần 4 nhân tử, và mỗi .