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. | 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@ http cautrucroirac FB cautrucroirac Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh https tailieudientucntt 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 đệ https tailieudientucntt 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 1https tailieudientucntt 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 nhân tử bằng 1 x x2 x3 bao gồm tất cả các lũy thừa nhỏ hơn hay bằng 3 của x. Ta được hàm sinh cần tìm là 1 x x2 x3 4 1 4x 10x2 20x3 31x4 40x5 44x6 31x8 40x7 20x9 https tailieudientucntt 10x10 4x11 x12 . lvluyen@ Chương 2. Phương pháp đếm dùng hàm sinh 09 2016 4 42 Ví dụ. Tìm hàm sinh của ar r 0
