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

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.