Bài giảng Toán rời rạc - Bài 14: Hàm sinh - Trần Vĩnh Đức

Hàm sinh Trần Vĩnh Đức HUST Ngày 26 tháng 4 năm 2016 1 / 51 Nội dung Đếm và đa thức Định nghĩa hàm sinh Các phép toán trên hàm sinh Một bài toán đếm Ký hiệu hình thức I Có 2 quả táo, 3 quả mận, và 4 quả đào. I Ta ký hiệu T := “lấy một quả táo” M := “lấy một quả mận” D := “lấy một quả đào”: I Lấy 1 quả táo, 2 quả mận, và 3 quả đào: TMMDDD = TM2D3: I Lấy 1 quả táo, 1 quả mận, và 1 quả đào hoặc lấy 1 quả táo, 1 quả đào, và 2 quả mận”: TMD+ TMD2: 3 / 51 Câu hỏi Xâu sau đây biểu diễn những lựa chọn gì? TMD+ TMD2 + TM2D+ T2MD+ TM2D2 +


+ T2M3D4 = (T+ T2)(M+M2 +M3)(D+D2 +D3 +D4): Lời giải Đây như một chuỗi hình thức mô tả mọi khả năng chọn trong số 2 quả táo, 3 quả mận, và 4 quả đào, mỗi loại ít nhất một quả. 4 / 51 Bài tập Có bao nhiêu cách chọn 6 quả trong số 2 quả táo, 3 quả mận, và 4 quả đào, mỗi loại ít nhất một quả? Lời giải I Ta chỉ cần thay thế mỗi T;M;D bằng biến hình thức x trong chuỗi (T+ T2)(M+M2 +M3)(D+D2 +D3 +D4): I Vậy mọi số hạng có số mũ 6 ứng với số lần x6 xuất hiện. I Hệ số của x6 chính là số cách chọn 6 quả. 5 / 51 Đa thức và đếm I Khi thay thế T;M;D bằng x thì hệ số của xk chính là số cách chọn đúng k quả. I Ta có (x+ x2)(x+ x2 + x3)(x+ x2 + x3 + x4) = x3(1 + x)(1 + x+ x2)(1 + x+ x2 + x3) = x3(1 + 2x+ 2x2 + x3)(1 + x+ x2 + x3) = x3 + 3x4 + 5x5 + 6x6 + 5x7 + 3x8 + x9: I Vậy có 6 cách lựa chọn 6 quả, 5 cách chọn 7 quả : : : . 6 / 51 Câu hỏi I Giả sử một quả mận có 20 calo, một quả đào có 40 calo, và một quả táo có 60 calo. I Nếu ta thay thế T! x60; M! x40 D! x20 trong chuỗi hình thức (T+ T2)(M+M2 +M3)(D+D2 +D3 +D4): thì hệ số của xn là gì? 7 / 51 Lời giải I Ta thay thế T! x60; M! x40 D! x20 I Vậy thì hệ số của xn của đa thức là số cách chọn quả để có n calo. I Vì khi chọn TiMjDk ta được 60i+ 40j+ 20k calo. 8 / 51 Ví dụ I Từ đa thức (x60 + x120)(x40 + x80 + x120)(x20 + x40 + x60 + x80) = x120(1 + x20 + 2x40 + 3x60 + 3x80 + 4x100 + 3x120 + 3x140 + 2x160 + x180 + x200) = x120 + x140 + 2x160 + 3x180 + 3x200 + 4x220 + 3x240 + 3x260 + 2x280 + x300 + x320 I Ta thấy có 3 cách chọn quả để có 200 calo. 9 / 51 Bài tập I Biết rằng quả táo giá 60 đồng, quả mận giá 40 đồng, và đào giá 20 đồng. I Có bao nhiêu cách chọn các quả giá 200 đồng, có thể có loại quả không được chọn? 10 / 51 Bài tập Hãy tìm đa thức có hệ số xk là số nghiệm nguyên không âm của phương trình x1 + x2 + x3 = k: 11 / 51 Câu hỏi Ta có thể dùng kỹ thuật mô tả ở phần trước để lựa chọn các quả táo, đào và mận nhưng không hạn chế bao nhiêu quả cần lấy. T0M0D0 + TM0D0 +


+ TMD+ TMD2 +


+ TiMjDk +


12 / 51 Tính toán hình thức I Việc chọn không, một,: : : tới một số bất kỳ táo (mận, đào ) có thể biểu diễn một cách hình thức là T0 + T1 + T2 +


+ Ti +


M0 +M1 +M2 +


+Mj +


D0 +D1 +D2 +


+Dk +


I Việc chọn táo, đào, mận với số lượng tùy ý có thể viết dưới dạng tích T0 + T1 +



M0 +M1 +



D0 +D1 +



: 13 / 51 Ví dụ Nếu thay thế T;M;D bởi x thì hệ số của xn trong tích của ba chuỗi vô hạn sau chính là số cách chọn đúng n quả. (1 + x+ x2 +


+ xi +


)3: 14 / 51 Nội dung Đếm và đa thức Định nghĩa hàm sinh Các phép toán trên hàm sinh Một bài toán đếm Định nghĩa Hàm sinh của dãy số hg0; g1; g2;


i là chuỗi vô hạn G(x) = g0 + g1x+ g2x2 +


: Ta sử dụng ký hiệu mũi tên hai phía để chỉ tương ứng giữa một dãy số và hàm sinh của nó như sau: hg0; g1; g2;


i ! g0 + g1x+ g2x2 +


: 16 / 51 Định nghĩa Ta ký hiệu [xn]G(x) là hệ số của xn trong hàm sinh G(x) = g0 + g1x+ g2x2 +


: Có nghĩa rằng [xn]G(x) = gn: 17 / 51 Ví dụ Dưới đây là một vài dãy số và hàm sinh của chúng: h0; 0; 0; 0;


i ! 0 + 0x+ 0x2 + 0x3 +


= 0 h1; 0; 0; 0;


i ! 1 + 0x+ 0x2 + 0x3 +


= 1 h3; 2; 1; 0;


i ! 3 + 2x+ 1x2 + 0x3 +


= 3 + 2x+ x2 18 / 51 Ví dụ I Hàm sinh cho dãy vô hạn h1; 1; 1;


i là chuỗi hình học G(x) := 1 + x+ x2 + x3 +


Ta có G(x) = 1 + x+ x2 + x3 +


+ xn +


xG(x) = 1 x x2 x3


xn


G(x) xG(x) = 1 I Vậy hàm sinh của dãy 1; 1; : : : là 1 1 x = G(x) := 1X n=0 xn: 19 / 51 Bài tập Hãy tìm công thức đóng cho hàm sinh của các dãy sau: 1. h 0; 0; 0; 0; 6; 6; 6; 6; 6; 6;


i 2. h1; 0; 1; 0; 1; 0;


i 3. h1; 1; 0; 1; 1; 0; 1; 1; 0;


i 20 / 51 Bài tập Chứng minh rằng hàm sinh của dãy h1; 2; 3;


i là 1 (1 x)2 : 21 / 51 Đạo hàm của chuỗi Lời giải I Lấy đạo hàm của chuỗi 1 + x+ x2 + x3 +


= 1 1 x ta được 1 + 2x+ 3x2 + 4x3 +


= 1 (1 x)2 I Đây chính là hàm sinh của dãy h1; 2; 3; 4;


i: 22 / 51 Dịch phải bằng cách nhân với x Xét hàm sinh G(x) = g0 + g1x+ g2x2 +


: Vậy thì xG(x) = 0 + g0x+ g1x2 + g2x3 +


Có nghĩa rằng [xn1]G(x) = [xn]xG(x): 23 / 51 Bài tập Tìm hàm sinh của dãy h0; 1; 2; 3; : : : i 24 / 51 Lời giải I Hàm sinh của dãy số h1; 2; 3;


i là G(x) = 1 (1 x)2 I Vậy thì xG(x) = x (1 x)2 = 0 + x+ 2x 2 + 3x3 +


: là hàm sinh của dãy h0; 1; 2; 3;


i. 25 / 51 Bài tập h1;1; 1;1;


i ! 1 x+ x2 x3 + x4


= 1 1 + x 26 / 51 Bài tập h1; a; a2; a3;


i ! 1+ax+a2x2+a3x3+


= 1 1 ax 27 / 51 Bài tập h1; 0; 1; 0; 1; 0;


i ! 1+x2+x4+x6+x8+


= 1 1 x2 28 / 51 Nội dung Đếm và đa thức Định nghĩa hàm sinh Các phép toán trên hàm sinh Một bài toán đếm Luật (nhân với hằng số) Nếu hf0; f1; f2;


i ! F(x); thì hcf0; cf1; cf2;


i ! c
F(x): 30 / 51 Ví dụ Ta biết rằng h1; 0; 1; 0; 1; 0;


i ! 1 + x2 + x4 + x6 + x8 +


= 1 1 x2 Nhân hàm sinh này với 2 ta được 2 1 x2 = 2 + 2x 2 + 2x4 + 2x6 +


sinh dãy h2; 0; 2; 0; 2; 0;


i 31 / 51 Luật (cộng) Nếu hf0; f1; f2;


i ! F(x); hg0; g1; g2;


i ! G(x); thì hf0 + g0; f1 + g1; f2 + g2;


i ! F(x) +G(x): 32 / 51 Ý tưởng của luật cộng hf0 + g0; f1 + g1; f2 + g2;


i ! 1X n=0 (fn + gn)xn = 1X n=0 fnxn ! + 1X n=0 gnxn ! = F(x) +G(x) 33 / 51 Ví dụ Xét hai hàm sinh: h1; 1; 1; 1;


i ! 1 1 x + h1;1; 1;1;


i ! 1 1 + x h2; 0; 2; 0;


i ! 1 1 x + 1 1 + x = 2 1 x2 34 / 51 Luật (dịch phải) Nếu hf0; f1; f2;


i ! F(x), vậy thì h0;


; 0| {z } k ; f0; f1; f2;


i ! xk
F(x): 35 / 51 Luật (đạo hàm) Nếu hf0; f1; f2;


i ! F(x) vậy thì hf1; 2f2; 3f3;


i ! F0(x): 36 / 51 Bài tập Hãy tìm hàm sinh cho dãy số bình phương hoàn hảo h0
0; 1
1; 2
2; 3
3;


i = h0; 1; 4; 9;


i: 37 / 51 Luật (tích) Nếu ha0; a1; a2;


i ! A(x) hb0; b1; b2;


i ! B(x); vậy thì hc0; c1; c2;


i ! A(x)
B(x); trong đó cn := a0bn + a1bn1 + a2bn2 +


+ anb0: 38 / 51 Luật tích b0x0 b1x1 b2x2 b3x3


a0x0 a0b0x0 a0b1x1 a0b2x2 a0b3x3


a1x1 a1b0x1 a1b1x2 a1b2x3


a2x2 a2b0x2 a2b1x3


a3x3 a3b0x3


...


39 / 51 Nội dung Đếm và đa thức Định nghĩa hàm sinh Các phép toán trên hàm sinh Một bài toán đếm Bài tập Có bao nhiêu cách để lấy n quả thỏa mãn ba yêu cầu sau đây? I Nhiều nhất 2 quả cam. I Số táo là tùy ý. I Số chuối phải chia hết cho 3. 41 / 51 Với n = 4 quả 1. 0 quả cam, 1 quả táo, 3 quả chuối 2. 0 quả cam, 4 quả táo, 0 quả chuối 3. 1 quả cam, 0 quả táo, 3 quả chuối 4. 1 quả cam, 3 quả táo, 0 quả chuối 5. 2 quả cam, 2 quả táo, 0 quả chuối 42 / 51 Nhiều nhất hai quả cam Hàm sinh cho dãy số hcki là “Số cách chọn k quả cam trong đó có nhiều nhất hai quả cam”: C(x) = 1X k=0 ckxk = 1 + x+ x2 = 1 x3 1 x : 43 / 51 Số táo tùy ý Hàm sinh cho dãy số htki là “Số cách chọn k quả táo”: T(x) = 1X k=0 tkxk = 1 + x+ x2 +


= 1 1 x : 44 / 51 Thay thế x bởi xk 1 1 x ! h1; 1; 1;


i 1 1 xk ! h1; 0; 0;


0| {z } k1 ; 1; 0; 0;


0| {z } k1 ; 1; 0;


i 45 / 51 Số chuối chia hết cho 3 Hàm sinh cho dãy số hbki là “Số cách chọn k quả chuối thỏa mãn số chuối chia hết cho 3”. B(x) ! h1; 0; 0; 1; 0; 0; 1; 0;


i B(x) = 1 1 x3 : 46 / 51 Câu hỏi Liệu ta có thể dùng các hàm sinh riêng để giải bài toán ban đầu? C(x) = 1 x 3 1 x (nhiều nhất hai cam) T(x) = 1 1 x (số táo tùy ý) B(x) = 1 1 x3 (số chuối chia hết cho 3) 47 / 51 Luật tích chập cho hàm sinh Hàm sinh cho số cách chọn từ hợp của các tập rời nhau là tích của các hàm sinh cho số cách chọn từ mỗi tập. 48 / 51 Tích các hàm sinh I Hàm sinh cho số cách chọn quả C(x)
T(x)
B(x) = 1 x 3 1 x
1 1 x
1 1 x3 = 1 (1 x)2 I Đây chính là hàm sinh cho dãy số h1; 2; 3;


i 49 / 51 Bài tập Có bao nhiêu cách để lấy n quả thỏa mãn ba yêu cầu sau đây? I Nhiều nhất 2 quả cam. I Số táo là tùy ý. I Số chuối phải chia hết cho 3. Lời giải Số cách chọn n quả chính là hệ số của xn trong F(x): [xn]  1 (1 x)2  = n+ 1: 50 / 51 Bài tập Có bao nhiêu cách chọn tám thanh kẹo gồm các thanh kẹo sôcôla hoặc kẹo cafe. 51 / 51