Bài giảng Toán tổ hợp - Chương 2: Phương pháp đếm dùng hàm sinh - ĐH KHTN TP.HCM

Định lý (Công thức tích cho hàm sinh thông thường) Gọi an là số cách để xây dựng một cấu trúc nào đó trên tập n phần tử, và bn là số cách để xây dựng một cấu trúc khác trên tập n phần tử. Gọi Cn là số cách để chia [ng thành các đoạn S = {1,2,...,i} và T = {i+1, +2, ...,n}, (S và T có thể bằng rỗng), và xây dựng cấu trúc loại thứ nhất lên S, và cấu trúc loại thứ hai lên T. Gọi A(x), B(x), và C(x) là các hàm sinh tương ứng của các dãy {4n}, {4n}, và {n}. Thì A(x)B(x) = C(x). Ví dụ Một học kì ở một trường đại học có n ngày. Đầu mỗi học kỳ, có hiệu trưởng chia học kì đó ra làm 2 phần, k ngày đầu tiên sẽ dùng cho lý | thuyết, và n – k ngày còn lại sẽ được dùng cho thực hành (ở đâu 1 ≤ k ≤ n − 2). Trong đợt dạy lý thuyết sẽ có 1 ngày nghỉ, và trong đợt dạy thực hành sẽ có 2 ngày nghỉ. Hỏi có hiệu trưởng có bao nhiêu cách khác nhau để làm như vậy?