Bài giảng Toán rời rạc: Hàm sinh cung cấp cho người học những nội dung kiến thức như: Đế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. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết. | Hàm sinh Trần Vĩnh Đức HUST Ngày 26 tháng 4 năm 2016 https tailieudientucntt 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 https tailieudientucntt Ký hiệu hình thức Có 2 quả táo 3 quả mận và 4 quả đào. 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 . Lấy 1 quả táo 2 quả mận và 3 quả đào TMMDDD TM2 D3 . 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 . https tailieudientucntt 3 51 Câu hỏi Xâu sau đây biểu diễn những lựa chọn gì TMD TMD2 TM2 D T2 MD TM2 D2 T2 M3 D4 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ả. https tailieudientucntt 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 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 . Vậy mọi số hạng có số mũ 6 ứng với số lần x6 xuất hiện. Hệ số của x6 chính là số cách chọn 6 quả. https tailieudientucntt 5 51 Đa thức và đếm 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ả. 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 . Vậy có 6 cách lựa chọn 6 quả 5 cách chọn 7 quả . . . . https tailieudientucntt 6 51 Câu hỏ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. 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ì https tailieudientucntt 7 51 Lời giải Ta thay thế T x60 M x40 D x20 Vậy thì hệ số của xn của đa thức là số cách chọn quả để có n calo. Vì khi chọn Ti Mj Dk ta được 60i 40j 20k calo. https tailieudientucntt 8 51
