Bài giảng toán rời rạc - Chương 3: Bài toán đếm

Chương 3 – Bài toán đếm3.1. Giới thiệu bài toán3.2. Nguyên lý bù trừ3.3. Hệ thức truy hồi3.4. Hàm sinh và bài toán đếm3.5. Bài tậpĐịnh nghĩa hàm sinhĐịnh nghĩa: Hàm sinh g(x) của dãy số {hn | n = 0,1,2,} là đa thứcVí dụ 1:g1(x) là hàm sinh của dãy tổ hợp hk = C(m,k)g2(x) là hàm sinh của dãy hk = 1Định nghĩa hàm sinhVí dụ 2: Xét hàm sau: g(x) là hàm sinh của dãy hn (hệ số của số hạng xn ) hn là số nghiệm nguyên không âm của phương trình: Hàm sinh và bài toán đếmVí dụ 3: Phương trình: x1 + x2 + x3 + x4 = 29 có bao nhiêu nghiệm nguyên không âm thỏa mãn: x1 <3, x2 <8Lời giải:hn là số nghiệm nguyên không âm của phương trình x1 + x2 + x3 + x4 = n thỏa mãn: x1 <3, x2 <8hn có hàm sinh: Cần tìm h29 Hàm sinh và bài toán đếmVí dụ 4: Phương trình: x1 + x2 + x3 + x4 = 29 có bao nhiêu nghiệm nguyên không âm thỏa mãn: x1 <4, x2 chia hết cho 4Lời giải:hn là số nghiệm nguyên không âm của phương trình x1 + x2 + x3 + x4 = n thỏa mãn: x1 <4, x2 chia hết cho 4hn có hàm sinh: Cần tìm h29Hàm sinh và bài toán đếmVí dụ 5: Có bao nhiêu cách chọn ra n quả từ 4 loại quả: táo, chuối, cam, đào (mỗi loại đều có số lượng ít nhất là n) mà trong đó có số chẵn quả táo, số chuối chia hết cho 5, không quá 4 quả cam và không quá 1 quả đào?Lời giải:Gọi hn là số cách chọn thỏa mãn yêu cầu đề bài.Khi đó hàm sinh của dãy hn có dạng: Hàm sinh và công thức truy hồiVí dụ 6: Giải công thức truy hồi: Lời giải:Gọi g(x) là hàm sinh của dãy số thỏa mãn hệ thức truy hồiTa có:Hàm sinh và công thức truy hồiVí dụ 5: Giải công thức truy hồi:a0=1 , a1= 2 và an = 3an-1 - 2an-2 + 2 Lời giải:Gọi g(x) là hàm sinh của dãy số thỏa mãn hệ thức truy hồiTa có:Bài tậpSử dụng hàm sinh để giải các bài toán sau:Bài 1: BPT: x1 + x2 + x3 + x4 + x5 +x6 ≤n có bao nhiêu nghiệm nguyên không âm thỏa mãn: x3 ≤ 3 và x4 chia hết cho 4 dư 2. x2 < 2 và x5 lẻBài 2: Giải hệ thức truy hồi: Bài tậpBPT: x1 + x2 + x3 + x4 + x5 +x6 ≤n có bao nhiêu nghiệm nguyên không âm thỏa mãn: x3 ≤ 3 và x4 chia hết cho 4 dư 2. x2 < 2 và x5 lẻ