Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Chương 3: Bài toán đếm trình bày giới thiệu bài toán, nguyên lý bù trừ, hệ thức truy hồi, hàm sinh và bài toán đếm, định nghĩa hàm sinh, bài tập,. . | Chương 3 – Bài toán đếm 3.1. Giới thiệu bài toán 3.2. Nguyên lý bù trừ 3.3. Hệ thức truy hồi 3.4. Hàm sinh và bài toán đếm 3.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ức Ví 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 2 Định nghĩa hàm sinh Ví 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 đếm Ví 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 <8 Lờ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 <8 hn có hàm sinh: Cần tìm h29 Hàm sinh và bài toán đếm Ví 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 4 Lờ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 4 hn có hàm sinh: Cần tìm h29 Hàm sinh và bài toán đếm Ví 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ồi Ví 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ồi Ta có: Hàm sinh và công thức truy hồi Ví 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ồi Ta có: Bài tập Sử 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ập 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ư | Chương 3 – Bài toán đếm 3.1. Giới thiệu bài toán 3.2. Nguyên lý bù trừ 3.3. Hệ thức truy hồi 3.4. Hàm sinh và bài toán đếm 3.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ức Ví 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 2 Định nghĩa hàm sinh Ví 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 đếm Ví 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 <8 Lờ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 <8 hn có hàm sinh: Cần tìm h29 Hàm sinh và bài toán đếm Ví 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 4 Lờ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 4 hn có hàm sinh: Cần tìm
