TAILIEUCHUNG - Bài giảng Toán học rời rạc và cấu trúc rời rạc: Chương 2 - Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh

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

• Toán học
• Toán học rời rạc
• Cấu trúc rời rạc
• Phương pháp đếm dùng hàm sinh
• Hệ số hàm sinh
• Hàm sinh mũ
• Bài giảng Toán học rời rạc
• Toán rời rạc
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc
• Câu hỏi Toán rời rạc
• Ôn thi Toán rời rạc
• Luyện thi Toán rời rạc
• Bài thi Toán rời rạc
• Hướng dẫn thi Toán rời rạc
• Câu hỏi thi Toán rời rạc
• Học phần Toán rời rạc 1
• Toán rời rạc 1
• Câu hỏi thi Toán rời rạc 1
• Ngân hàng câu hỏi Toán rời rạc 1
• Thi tự luận Toán rời rạc 1
• Hướng dẫn thi Toán rời rạc 1