Bài tập Toán rời rạc - Bài 14

Toán rời rạc: Hàm sinh Bài tập 14 1 Ứng dụng của đa thức trong tổ hợp 1. Xét hai đa thức a(x) = a0 + a1x + a2x 2 + · · ·+ anxn b(x) = b0 + b1x + b2x 2 + · · ·+ bmxm Hãy viết ra công thức tính hệ số của x k trong tích a(x)b(x) với 0≤ k ≤ n+m. 2. Biểu diễn số nghiệm nguyên của các phương trình sau như hệ số của số mũ x thích hợp trong tích các đa thức: (a) e1 + e2 + e3 + e4 + e5 = r, 0≤ ei ≤ 4 (b) e1 + e2 + e3 + e4 = r, 0< ei < 4 (c) e1 + e2 + e3 + e4 = r, 2≤ ei ≤ 8, e1 chẵn, e2 lẻ (d) e1 + e2 + e3 + e4 = r, 0≤ ei (e) e1 + e2 + e3 + e4 = r, 0< ei, e2, e4 lẻ, e4 ≤ 3 (f) e1 + e2 + e3 + e4 = r, −3≤ ei ≤ 3 3. Một quán cà phê có bán ba loại bánh: táo, mứt, và kem. Có bao nhiêu cách mua 12 chiếc bánh sao cho mỗi loại có ít nhất hai chiếc và số bánh táo không vượt quá ba? Hãy biểu diễn số này như hệ số của số mũ x thích hợp trong tích các đa thức thích hợp. 4. Có bao nhiêu cách để phát hết 10 quả bóng giống nhau cho 2 cậu bé và 2 cô bé sao cho mỗi cậu bé được ít nhất một quả và mỗi cô bé được ít nhất hai quả? Hãy biểu diễn số này như hệ số của số mũ x thích hợp trong tích các đa thức thích hợp. 5. Tính tổng ∑n i=0(−1)n n i
n n−i
. 6. Tìm hệ số của x10 y5 trong (19x + 4y)15. 2 Hàm sinh 1. Hãy tìm công thức đóng cho hàm sinh của các dãy sau và sau đó kiểm tra lại kết quả dùng Wolfram|Alpha: (a) 〈 0, 0, 0, 0, −6, 6, −6, 6, −6, 6, · · · 〉 (b) 〈1,0,1,0, 1,0, · · · 〉 (c) 〈1,2,1,4, 1,8, · · · 〉 (d) 〈1,1,0,1, 1,0, 1,1, 0, · · · 〉 (e) (bình phương hoàn hảo) 〈02, 12, 22, 32, · · · 〉= 〈0, 1, 4, 9, · · · 〉. 2. (a) Chứng minh rằng nếu 〈g0, g1, g2, . . . 〉 ↔ G(x) thì 〈g0, g0 + g1, g0 + g1 + g2, . . . 〉 ↔ 11− x G(x). (b) Dùng kết quả trên hãy tìm ∑n k=1 k 2. (c) Dùng kết quả trên hãy tìm ∑n k=1 k 3. (d) Với n và m là các số tự nhiên, hãy tính ∑n k=1(−1) n k
. (e) Có vẻ như với phương pháp này ta có thể tính mọi tổng, nhưng thực tế không đơn giản như vậy! Chuyên gì xảy ra nếu bạn dùng phương pháp này để tính tổng ∑n k=1 1/k? 3. Dãy r0, r1, r2, · · · được định nghĩa một cách đệ quy bởi luật sau: r0 = r1 = 0 và rn = 7rn−1 + 4rn−2 + (n+ 1), với n ≥ 2. Hãy biểu diễn hàm sinh của dãy này như thương của hai đa thức hoặc tích của các đa thức. Bạn không cần tìm dạng tường minh cho rn 4. Xét A(x) = ∑∞ n=0 anx n. Ta có thể kiểm tra được rằng an = A(n)(0) n! , với A(n) là đạo hàm cấp n của A. Hãy dùng kết quả trên (thay vì luật tích) để chứng minh rằng 1 (1− x)k = ∞∑ n=0  n+ k− 1 k− 1 ‹ xn. 3 Tính hệ số của hàm sinh 1. Hãy tính (a) [x15](x2 + x3 + x4 + x5 + · · · )4. (b) [x50](x7 + x8 + x9 + x10 · · · )6. (c) [x5](1− 2x)−2. (d) [x4] 3 p 1+ x . (e) [x3] (2+ x)3/2/(1− x)
. (f) [x4] (2+ 3x)5 p (1− x)
(g) [x3] 1− x + 2x2
9. 2. (a) Chứng minh rằng với mọi k ∈ N, hàm sinh cho dãy các số nguyên dạng mũ k là thương của hai đa thức theo x . Có nghĩa rằng, với mọi k ∈ N có đa thức Rk(x) và Sk(x) sao cho [xn]  Rk(x) Sk(x) ‹ = nk Gợi ý: Để ý rằng đạo hàm của thương hai đa thức cũng là thương của hai đa thức. Ta không cần phải chỉ rõ tường minh Rk(x) và Sk(x) để chứng minh điều này. (b) Chứng minh rằng nếu f (n) là một hàm trên các số nguyên không âm định nghĩa đệ quy dưới dạng f (n) = f (n− 1) + b f (n− 2) + c f (n− 3) + p(n)αn với a, b, c,α ∈ C và p là một đa thức với hệ số phức, vậy hàm sinh cho dãy f (0), f (1), f (2), . . . sẽ là thương của hai đa thức theo x , và vậy có một biểu thức dạng tường minh cho f (n). Gợi ý: Xét Rk(x) Sk(x) 3. (a) Xét S(n) = x2 + x (1− x)3 . Hệ số xn trong hàm sinh trên là gì? (b) Giải thích xem tại sao S(x)/(1− x) là hàm sinh cho các tổng của các bình phương. Có nghĩa rằng hệ số của xn trong chuỗi S(x)/(1− x) là∑nk=1 k2. (c) Dùng phần trước, hãy chứng minh rằng n∑ k=1 k2 = n(n+ 1)(2n+ 1) 6 . 4 Đếm dùng hàm sinh 1. Đặt gn là số cách trả lại n đồng chỉ dùng các tờ một đồng, các tờ hai đồng, và/hoặc các tờ năm đồng. (a) Hãy viết ra hàm sinh cho dãy 〈 g0, g1, g2, · · · 〉. (b) Dùng kết quả của câu 1a, hãy tìm công thức cho gn. 2. Các ngày phải đi học trong năm tới có thể đánh số 1,2, · · · , 300. Tôi muốn trốn học càng nhiều càng tốt. • Những ngày chẵn, tôi nói "bị ốm". • Những ngày là bội của 3, tôi nói "bị tắc đường". • Những ngày là bội của 5, tôi kiên quyết không ra khỏi chăn ấm. Cuối cùng thì có bao nhiêu ngày tôi trốn học trong năm tới? 3. Sơn đang lên kế hoạch cho một chuyến đi xa bằng tàu biển, và anh ta cần quyết định xem nên mang gì theo. • Anh chắc chắn phải mang mỳ tôm, được đóng 6 gói một. • Anh và hai người bạn không biết nên ăn mặc lịch sự hay thoải mái. Vậy nên hoặc anh mang 0 đôi tông, hoặc anh mang 3 đôi. • Do không có nhiều chỗ trong vali để khăn tắm, nên anh mang nhiều nhất 2 chiếc. • Có lẽ sẽ dừng ở nhiều bãi biển đẹp và đông người, anh quyết định mang ít nhất 1 quần bơi. (a) Xét gn là số cách khác nhau để Sơn mang n đồ vật (gói mỳ, đôi tông, khăn tắm, quần bơi) theo. Hãy biểu diễn hàm sinh G(x) = ∑∞ n=0 gnx n dưới dạng thương của hai đa thức. (b) Tìm công thức tường minh cho số cách Sơn mang đúng n đồ vật. 4. Bạn đang muốn mua một bó hoa. Bạn tìm thấy một cửa hàng trên mạng bó hoa từ hoa ly, hoa hồng, và hoa tulip, và bán theo ràng buộc sau • chỉ có nhiều nhất ba bông hoa ly, • phải có một số lẻ hoa tulip, • số lượng hoa hông tuỳ ý. Ví dụ: một bó gồm 3 bông tulip, không có bông ly nào, và 5 bông hồng thoả mãn ràng buộc trên. Xét fn là số bó hoa gồm n bông hoa thoả mãn rằng buộc này. Hãy biểu diễn hàm sinh F(n) tương ứng với dãy 〈 f0, f1, f2, · · · 〉 theo thương của hai đa thức (hoặc tích của các đa thức). Bạn không cần đơn giản biểu thức này. 5 Số Fibonacci 1. Có bao nhiêu xâu nhị phân độ dài n mà không chứa hai số 0 liên tiếp? 2. Hãy tìm số các tập con (kể cả tập rỗng) của tập {1,2, · · · ,n} mà không chứa hai số nguyên dương liên tiếp. 3. Tìm công thức tường minh cho các dãy được định nghĩa một cách đệ quy như sau: (a) a0 = 2, a1 = 3, an+2 = 3an − 2an+1 (b) a0 = 0, a1 = 1, an+2 = 4an+1 − 4an (c) a0 = 1, an+1 = 2an + 3. 4. Giải các hệ thức truy hồi (a) an = an−1 + an−2 + · · ·+ a1 + a0 với điều kiện ban đầu a0 = 1. (b) an = an−1 + an−3 + an−4 + · · ·+ a1 + a0 (n≥ 3) với a0 = a1 = a2 = 1. 5. Giải hệ thức truy hồi an−2 = p an+1an với điều kiện ban đầu a0 = 2, a1 = 8. 6 Số Catalan 1. Cho bàn cờ n× n như sau: Xét đường đi ngắn nhất từ góc A tới góc B đi qua các cạnh (mỗi đường qua 2n cạnh). (a) Có bao nhiêu đường như vậy? (b) Chứng minh rằng số đường không xuống dưới đường chéo chính là số Catalan Cn. 2. Hãy tìm cách chứng minh số cách đặt dấu ngoặc là số Catalan mà không dùng hàm sinh. 3. Có 2n người đứng đợi mua vé xem phim. Mỗi vé giá 5 đồng. Mọi người đều muốn mua vé; trong đó n người đều chỉ có một tờ 10 đồng và n khác người đều chỉ có một tờ 5 đồng. Ban đầu người bán vé không có đồng nào. (a) Có bao nhiêu cách xếp hàng cho 2n người này sao cho người bán vé luôn trả được 5 đồng cho những người chỉ có tờ 10 đồng. (b) Hãy tính xác suất để người bán vé có thể trả tiền được cho mọi người khi họ đứng xếp hàng một cách ngẫu nhiên. 4. Có bao nhiêu dãy gồm n số nguyên a1 ≤ a2 ≤ · · · ≤ an thỏa mãn ai ≤ i? Ví dụ, có 5 dãy độ dài 3: 111 112 113 122 123 5. Có bao nhiêu dãy số nguyên a1, a2, . . . , an thỏa mãn a1 = 0 và 0≤ ai+1 ≤ ai + 1? Ví dụ, 000 001 010 011 012