Bài giảng Chương 3: Bài toán đếm

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,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương 3: Bài toán đếmChươ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ức g ( x ) = h0 + h1 x + h2 x + ... = 2 i hi x i =0 m g1 ( x ) = ( 1 + x ) = m Cmk x k k =0• Ví dụ 1: 1 g2 ( x ) = = 1 + x + x 2 + ... 1− x – 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 sinh• Ví dụ 2: Xét hàm sau: k 1 �1 � � = ( 1 + x + x + ... ) k g( x) = =� 2 (1 − x ) k 1− x � � g(x) là hàm sinh của dãy hn (hệ số của sốhạng xn ) t1 + t2 + ... + tk = n hn là số nghiệm nguyên không âm củaphương trình: � hn = Rk n 1 = ( 1 + x + x + x + ... ) = 2 3 k n n R x(1 − x) k k n =0 1 = ( 1 + rx + r x + r x + ... ) = 2 2 3 3 k n n n R r x( 1 − rx ) k k n =0 k x = x ( 1 + x + x + x + ... ) = x + x + x + ... k 2 3 k k +1 k +21− x k +11− x = 1 + x + ... + x k 1− x 1 = 1 + x + x + .... k 2k1− x k x k +1 2 k +1 = x+x +x + ....1− x k 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 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 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. –g (Khi ( x ) = đó 1 + xhàm 2 sinh + x4 + )( của1 +dãy x 6 + .... x 5 + hn x10 +có ... dạng:)( 1 + x + x2 + x3 + x4 ( 1 + x ) ) 1 1 1 − x5 1 = (1+ x + x + ... ) 2 = ( 1 + x) = 2 ( ) 2 1− x 1− x 1− x 2 5 1 − x hn = R = C n n = ( n + 1) ! = n +1 2 n + 2 −1 n !1! Hàm sinh và công thức truy hồi• Ví dụ 6: Giải công thức truy hồi: an = 4 an − 2 a0 = 0; a1 = 1• 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 g ( x ) = a 0 + a1 x + a 2 x 2 + a 3 x 3 + ... – Ta có: = a0 + a1 x + 4a0 x 2 + 4a1 x 3 + ... ...