›
›

Bài giảng Toán học tổ hợp và cấu trúc rời rạc - Chương 2: Phương pháp đếm dùng hàm sinh - Nguyễn Anh Thi

pdf 54 trang ngocly 3110
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán học tổ hợp và cấu trúc rời rạc - Chương 2: Phương pháp đếm dùng hàm sinh - Nguyễn Anh Thi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toan_hoc_to_hop_va_cau_truc_roi_rac_chuong_2_phuon.pdf

Nội dung text: Bài giảng Toán học tổ hợp và cấu trúc rời rạc - Chương 2: Phương pháp đếm dùng hàm sinh - Nguyễn Anh Thi

  1. Bài giảng Toán học tổ hợp và Cấu trúc rời rạc Nguyễn Anh Thi ĐH KHTN, Tp HCM 2016 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 1 / 54
  2. Chương 2 PHƯƠNG PHÁP ĐẾM DÙNG HÀM SINH Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 2 / 54
  3. Nội dung Nội dung 1 Định nghĩa hàm sinh 2 Hệ số hàm sinh 3 Phân hoạch 4 Hàm sinh mũ 5 Phương pháp tổng 6 Bài toán đệ quy Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 3 / 54
  4. Định nghĩa hàm sinh Định nghĩa hàm sinh Định nghĩa Cho {an}n≥0 là một dãy các số thực, thì chuỗi lũy thừa hình thức P n A(x) = n≥0 anx được gọi là hàm sinh thông thường (hay hàm sinh) của dãy {an}n≥0. Ví dụ Xét tập hợp X với m phần tử, gọi an là số tập con có n phần tử của X,  m  a = . n n Ta được hàm sinh của dãy số thực {an}n≥0 là  n   n   n  A(x) = 1 + x + x2 + ··· + ··· + xn = (1 + x)n 1 2 n Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 4 / 54
  5. Định nghĩa hàm sinh Định nghĩa hàm sinh Ví dụ Tìm hàm sinh của ar, với ar là số cách để chọn r viên bi từ 3 viên bi màu xanh, 3 viên bi màu trắng, 3 viên bi màu đỏ, và 3 viên bi màu vàng. Bài toán trên có thể đưa về bài toán tìm nghiệm nguyên của phương trình e1 + e2 + e3 + e4 = r với 0 ≤ ei ≤ 3. Ở đây e1 là số quả cầu màu xanh được chọn, e2 là số quả cầu màu trắng, e3 là số quả cầu màu đỏ, và e4 là số quả cầu màu vàng. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 5 / 54
  6. Định nghĩa hàm sinh Định nghĩa hàm sinh Ta xây dựng một tích của các nhân tử đa thức sao cho sau khi nhân các đa thức đó lại với nhau, ta được tất cả các hạng tử có dạng xe1 xe2 xe3 xe4 , trong đó 0 ≤ ei ≤ 3. Như vậy ta cần 4 nhân tử, và mỗi nhân tử bằng 1 + x + x2 + x3, bao gồm tất cả các lũy thừa nhỏ hơn hay bằng 3 của x. Ta được hàm sinh cần tìm là (1 + x + x2 + x3)4 =1 + 4x + 10x2 + 20x3 + 31x4 + 40x5 + 44x6+ + 31x8 + 40x7 + 20x9 + 10x10 + 4x11 + x12. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 6 / 54
  7. Định nghĩa hàm sinh Định nghĩa hàm sinh Ví dụ Tìm hàm sinh của {ar}r≥0, với ar là số cách để chọn r quả từ 6 quả lê, 5 quả cam, 3 quả chanh, 3 quả mận. Giải. Tương tự như ví dụ trên ar là nghiệm nguyên của phương trình e1 + e2 + e3 + e4 = r với 0 ≤ e1 ≤ 6, 0 ≤ e2 ≤ 5, 0 ≤ e3 ≤ 3, và 0 ≤ e4 ≤ 2. Để tìm hàm sinh ta xây dựng một tích của các nhân tử đa thức sao cho sau khi nhân các đa e1 e2 e3 e4 thức đó lại với nhau, ta được tất cả các hạng tử có dạng x1 x2 x3 x4 . Các nhân tử đa thức tương ứng là: 1 + x + x2 + x3 + x4 + x5 + x6, 1+x+x2+x3+x4+x5, 1+x+x2+x3, và 1+x+x2+x3. Vậy hàm sinh cần tìm là (1 + x + x2 + x3 + x4 + x5 + x6)(1 + x + x2 + x3 + x4 + x5)(1 + x + x2 + x3)2. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 7 / 54
  8. Định nghĩa hàm sinh Định nghĩa hàm sinh Ví dụ Tìm hàm sinh của {ar}r≥0, với ar là số cách chia r đồng xu vào 5 hộp với điều kiện: Số đồng xu ở hộp 1 và hộp 2 là số chẵn và không quá 10, và các hộp còn lại chứa 3 đến 5 đồng xu. Giải. ar là số nghiệm nguyên của phương trình e1 + e2 + e3 + e4 + e5 = r với e1, e2 chẵn, 0 ≤ e1, e2 ≤ 10, và 3 ≤ e3, e4, e5 ≤ 5. Để tìm hàm sinh ta xây dựng một tích của các nhân tử đa thức sao cho sau khi nhân các đa thức đó lại với nhau, ta được tất cả các hạng tử có e e e e e dạng x 1 x 2 x 3 x 4 x 5 . Ta được nhân tử đa thức tương ứng với e1 và e2 là 2 4 6 8 10 (1 + x + x + x + x + x ), và tương ứng với e3, e4, và e5 là (x3 + x4 + x5). Hàm sinh cần tìm là (1 + x2 + x4 + x6 + x8 + x10)2(x3 + x4 + x5)3 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 8 / 54
  9. Hệ số hàm sinh Hệ số hàm sinh Trong phần này, chúng ta sẽ sử dụng một số kỷ thuật để tính toán các hệ số trong hàm sinh. Phương pháp chủ yếu là đưa một hàm sinh phức tạp về hàm sinh kiểu nhị thức hoặc tích của các hàm sinh kiểu nhị thức. Ta cần sử dụng một số khai triển sau: Một số khai triển đa thức 1 − xm+1 (1) = 1 + x + x2 + x3 + ··· + xm 1 − x 1 (2) = 1 + x + x2 + ··· 1 − x  n   n   n   n  (3) (1 + x)n = 1 + x + x2 + ··· + xr + ··· + xn 1 2 r n  n   n   n  (4) (1 − xm)n = 1 − xm + x2m + ··· + (−1)k xkm + 1 2 k  n  ··· + (−1)n xnm n Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 9 / 54
  10. Hệ số hàm sinh Hệ số hàm sinh Một số khai triển đa thức 1 (5) = (1 − x)n  1 + n − 1   2 + n − 1   r + n − 1  1 + x + x2 + ··· + xr + ··· 1 2 r 2 (6) Nếu h(x) = f(x)g(x), với f(x) = a0 + a1x + a2x + ··· và 2 g(x) = b0 + b1x + b2x + ··· , thì h(x) = a0b0 + (a1b0 + a0b1)x + (a2b0 + 2 r a1b1 + a0b2)x + ··· + (arb0 + ar−1b1 + ar−2b2 + ··· + a0br)x + ··· Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 10 / 54
  11. Hệ số hàm sinh Hệ số hàm sinh Ví dụ Tìm hệ số của x16 trong (x2 + x3 + x4 + ··· )5? Giải. Ta có (x2 + x3 + x4 + ··· )5 = [x2(1 + x + x2 + ··· )]5 = x10(1 + x + x2 + ··· )5 1 = x10 (1 − x)5 Để tìm hệ số của x16 trong (x2 + x3 + x4 + ··· )5, ta tìm hệ số của x6 trong 1 . Theo khai triển trên ta được hệ số của x6 trong 1 là (1−x)5 (1−x)5  6 + 5 − 1  . 6 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 11 / 54
  12. Hệ số hàm sinh Hệ số hàm sinh Ví dụ Tìm số cách để lấy 15 đồng xu từ 20 người sao cho, trong 19 người đầu tiên ta có thể lấy ở mỗi người 0 đồng hoặc 1 đồng, và người thứ 20 ta có thể lấy 0 đồng, hoặc 1 đồng, hoặc 5 đồng? Giải. Bài toán trên tương đương với bài toán tìm nghiệm nguyên của phương trình x1 + x2 + ··· + x20 = 15 thỏa điều kiện xi = 0 hoặc 1 với i = 1, 2, , 19 và x20 = 0 hoặc 1, hoặc 5. Ta có được hàm sinh cho bài toán trên là (1 + x)19(1 + x + x5) Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 12 / 54
  13. Hệ số hàm sinh Hệ số hàm sinh Theo công thức khai triển ta có  19   19   19  (1 + x)19 = 1 + x + x2 + ··· + ··· + x19 1 2 19 19 5 r Đặt f(x) = (1 + x) và g(x) = 1 + x + x . Gọi ar là hệ số của x trong f(x),  19  và b là hệ số của xr trong g(x). Ta thấy a = , và r r r 15 b0 = b1 = b5 = 1, các bi khác bằng 0. Hệ số của x trong h(x) = f(x)g(x) được tính bởi (6) là, a15b0 + a14b1 + a13b2 + ··· + a0b15 Thu gọn ta được  19   19   19  a b +a b +a b = ×1+ ×1+ ×1 = 107882. 15 0 14 1 10 5 15 14 10 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 13 / 54
  14. Hệ số hàm sinh Hệ số hàm sinh Ví dụ Có bao nhiêu cách chia 25 viên bi vào 7 hộp với điều kiện hộp thứ nhất có không quá 10 viên, các hộp còn lại tùy ý. Giải. Hàm sinh của dãy {ar}r≥0 với ar là số cách chia r viên bi vào 7 hộp với điều kiện như đề bài là: (1 + x + + x10)(1 + x + x2 + +)6 ! !6 1 − x11 1 = 1 − x 1 − x !7 1 = (1 − x11) 1 − x Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 14 / 54
  15. Hệ số hàm sinh Hệ số hàm sinh Theo công thức (5) ta có !7 1  1 + 7 − 1   r + 7 − 1  = 1 + x + ··· + xr + ··· 1 − x 1 r !7 1 Đặt f(x) = 1 − x11 và g(x) = . Gọi a là hệ số của xr trong f(x), 1 − x r r và br là hệ số của x trong g(x). Ta thấy a0 = 1, a11 = −1, ai = 0 với  r + 7 − 1  i 6= 0, 11 và b = . r r Hệ số của x25 trong h(x) = f(x)g(x) được tính bởi (6) là, a0b25 + a1b24 + ··· + a25b0 Thu gọn ta được  25 + 7 − 1   14 + 7 − 1  a b + a b = 1 × + (−1) × = 697521 0 25 11 14 25 14 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 15 / 54
  16. Hệ số hàm sinh Hệ số hàm sinh Ví dụ Có bao nhiêu cách chọn 25 nón từ 6 loại nón, với điều kiện mỗi loại nón phải được chọn từ 1 đến 5 cái. Ví dụ Cho n là số nguyên dương. Chứng minh rằng: 2 2 2  n   n   n   2n  + + ··· + = 0 1 n n Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 16 / 54
  17. Hệ số hàm sinh Hệ số hàm sinh  2n  Giải. Ta có là hệ số của xn trong (1 + x)2n = (1 + x)n(1 + x)n. n n n r Đặt f(x) = (1 + x) , g(x) = (1 + x) và ar, br lần lượt là hệ số của x trong  n  f(x) và g(x). Ta có a = b = . Áp dụng công thức (6), ta có hệ số r r r xn trong f(x)g(x) là a0bn + a1bn−1 + ··· + anb0  n   n   n   n   n   n  = + + ··· + 0 n 1 n − 1 n 0 2 2 2  n   n   n  = + + ··· + . 0 1 n Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 17 / 54
  18. Phân hoạch Phân hoạch Định nghĩa Cho số nguyên dương n. Khi đó dãy (a1, a2, , ak) được gọi là một phân hoạch của n nếu 1 ≤ a1 ≤ a2 ≤ · · · ≤ ak ≤ n và a1 + a2 + ··· + ak = n. Ví dụ Số nguyên dương 5 có 7 phân hoạch là (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 4), (2, 3), và (5), trong đó 5 được gọi là một phân hoạch tầm thường của chính nó. Ví dụ Liệt kê tất cả các phân hoạch của 6. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 18 / 54
  19. Phân hoạch Phân hoạch Chúng ta xây dựng một hàm sinh cho ar, với ar là số lượng các phân hoạch của số nguyên r. Một phân hoạch của số nguyên r được mô tả bằng số lượng các số 1, 2, sao cho khi lấy tổng lại với nhau ta được r. Gọi ek là số các số nguyên k xuất hiện trong phân hoạch, ta có 1e1 + 2e2 + 3e3 + ··· + kek + ··· + rer = r Ta được hàm sinh cần tìm là g(x) = (1 + x + x2 + ··· + xn + ··· ) × (1 + x2 + x4 + ··· + x2n + ··· )× · · · × (1 + xk + x2k + ··· + xkn + ··· ) 1 Dễ dàng thấy được g(x) = (1 − x)(1 − x2)(1 − x3) (1 − xk) Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 19 / 54
  20. Phân hoạch Phân hoạch Ví dụ Tìm hàm sinh cho ar, với ar là số cách biểu diễn r như tổng của các số nguyên khác nhau. Tương tự như trên ta cũng gọi ek là số các số nguyên k xuất hiện trong phân hoạch của r, ta có 1e1 + 2e2 + 3e3 + ··· + kek + ··· + rer = r Do yêu cầu của bài toán các ei chỉ nhận giá trị là 0 hoặc 1. Ta được hàm sinh của ar là g(x) = (1 + x)(1 + x2)(1 + x3) Ví dụ Tìm hàm sinh cho ar, với ar là số cách chọn các đồng xu 1 đồng, 2 đồng, 5 đồng để được tổng là r đồng. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 20 / 54
  21. Phân hoạch Phân hoạch Ví dụ Chứng minh rằng mọi số nguyên dương đều được viết như là tổng duy nhất của các lũy thừa khác nhau của 2. Gọi ar là số cách để viết một số nguyên r thành tổng của các lũy thừa khác nhau của 2. Ta tìm hàm sinh cho ar. Tương tự như hàm sinh cho tổng các số nguyên khác nhau trong ví dụ trên, nhưng trong trường hợp này ta chỉ xét các số nguyên là lũy thừa của 2. Gọi ek là số các số nguyên 2k trong phân hoạch, thì ta có 2 k 1 + 2e1 + 2 e2 + ··· + 2 ek + ··· = r Hàm sinh của ar là k g(x) = (1 + x)(1 + x2)(1 + x4)(1 + x8) (1 + x2 ) Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 21 / 54
  22. Phân hoạch Phân hoạch Để chứng minh mọi số nguyên đều được viết dưới dạng tổng duy nhất của các lũy thừa khác nhau của 2, ta phải chứng minh hệ số của mỗi lũy thừa của x trong g(x) bằng 1. Nghĩa là chứng minh 1 g(x) = 1 + x + x2 + x3 + ··· = 1 − x Ta thấy (1 − x)g(x) = (1 − x)(1 + x)(1 + x2)(1 + x4) (1 + x2k) = (1 − x2)(1 + x2)(1 + x4) (1 + x2k) = (1 − x4)(1 + x4) (1 + x2k) = 1 Do đó g(x) = 1 + x + x2 + x3 + ··· . Vậy ta được điều cần chứng minh. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 22 / 54
  23. Hàm sinh mũ Hàm sinh mũ Trong phần này chúng ta sẽ nói về hàm sinh mũ và sử dụng chúng để giải quyết các bài toán liên quan đến sự sắp xếp có lặp lại. Ví dụ Tìm số các từ khác nhau có 4 ký tự được tạo thành từ các chữ a, b, c, và mỗi từ chứa ít nhất hai chữ a? Từ tập hợp các ký tự sau đây ta có thể sắp xếp để được các từ cần tìm: {a, a, a, a}, {a, a, a, b}, {a, a, a, c}, {a, a, b, b}, {a, a, b, c}, {a, a, c, c}. Dễ dàng thấy rằng số từ có thể có được là 4! 4! 4! 4! 4! 4! + + + + + 4!0!0! 3!1!0! 3!0!1! 2!2!0! 2!1!1! 2!0!2! Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 23 / 54
  24. Hàm sinh mũ Hàm sinh mũ Gọi e1, e2, e3 là số chữ a, b, c xuất hiện trong một từ. Thoạt nhìn, bài toán của chúng ta sẽ tương đương với bài toán tìm số nghiệm nguyên của phương trình e1 + e2 + e3 = 4 với e1 ≥ 2 , e2, e3 ≥ 0, và chúng ta có thể dùng hàm sinh thông thường để giải. Sự khác biệt ở đây nằm ở chỗ ứng với mỗi nghiệm nguyên của phương trình trên ta được số lượng các chữ cái mỗi loại, và ứng với số lượng các chữ cái đó ta có thể sắp xếp để cho ra nhiều từ khác nhau. Nghĩa là ứng với một nghiệm nguyên của phương trình trên cho ta 4! e1!e2!e3! từ có thể. Trong trường hợp này người ta đưa ra khái niệm hàm sinh mũ. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 24 / 54
  25. Hàm sinh mũ Hàm sinh mũ Định nghĩa Cho {ar}r≥0 là một dãy các số thực. Khi đó chuỗi lũy thừa hình thức x2 x3 xr E(x) = a + a x + a + a + ··· + a + ··· 0 1 2 2! 3 3! r r! được gọi là hàm sinh mũ của dãy {ar}r≥0. Chúng ta xây dựng hàm sinh mũ giống như cách xây dựng hàm sinh thông thường: một nhân tử đa thức cho mỗi đối tượng, mỗi nhân tử chứa tập hợp các lũy thừa của x. Tuy nhiên mỗi lũy thừa xr được chia cho r!. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 25 / 54
  26. Hàm sinh mũ Hàm sinh mũ Ví dụ Tìm hàm sinh mũ cho ar, số các bộ gồm k phần tử không lặp lại có sắp thứ tự từ n phần tử?, (ar là chỉnh hợp chập r của n phần tử. ) Do không có sự lặp lại, nên hàm sinh mũ cần tìm là (1 + x)n. Hệ số của xr   n r là . Hệ số của x là a = n!/(n − r)! r r! r n! Hay nói cách khác, ta có a = , do đó hàm sinh mũ là r (n − r)! n! x2 n! x3 n! xr E(x) = 1 + x + + + ··· + + ··· . (n − 2)! 2! (n − 3)! 3! (n − r)! r! Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 26 / 54
  27. Hàm sinh mũ Hàm sinh mũ Ví dụ Tìm hàm sinh mũ cho ar, với ar là số cách sắp xếp khác nhau của r vật thể được chọn ra từ 4 loại vật thể khác nhau, sao cho mỗi loại vật thể xuất hiện ít nhất 2 lần và không quá 5 lần? Gọi ei là số lượng loại vật thể thứ i, i = 1, 2, 3, 4, xuất hiện trong số r vật thể cần sắp xếp. Ta có e1 + e2 + e3 + e4 = r và 2 ≤ ei ≤ 5, với i = 1, 2, 3, 4. Nhân tử đa thức ứng với mỗi loại vật thể là x2 x3 x4 x5 + + + 2! 3! 4! 5! . Từ đó suy ra hàm sinh cần tìm là !4 x2 x3 x4 x5 + + + . 2! 3! 4! 5! Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 27 / 54
  28. Hàm sinh mũ Hàm sinh mũ Ví dụ Tìm hàm sinh mũ cho số cách xếp r người vào trong 3 căn phòng với ít nhất một người mỗi phòng? Dễ dàng thấy hàm sinh mũ cần tìm là 3  x2 x3 x4  x + + + + ··· . 2! 3! 4! Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 28 / 54
  29. Hàm sinh mũ Một khai triển cơ bản của hàm sinh mũ õ Ta có x2 x3 xr ex = 1 + x + + + ··· + + ··· 2! 3! r! Thay x bởi nx ta được n2x2 n3x3 nrxr enx = 1 + nx + + + ··· + + ··· . 2! 3! r! Ta cũng suy ra được là x2 x3 x4 + + + ··· = ex − 1 − x 2! 3! 4! Một số khai triển hữu ích thường gặp 1 x2 x4 x6 (ex + e−x) = 1 + + + + 2 2! 4! 6! 1 x3 x5 x7 (ex − e−x) = x + + + + ··· 2 3! 5! 7! Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 29 / 54
  30. Hàm sinh mũ Hàm sinh mũ Ta xem một số ứng dụng: Ví dụ Tìm số cách sắp xếp r đối tượng được chọn ra từ n loại đối tượng khác nhau? Ta dễ dàng thấy hàm sinh của nó là n  x2 x3  1 + x + + + ··· = (ex)n = enx 2! 3! xr Theo công thức khai triển trên ta dễ dàng thấy được hệ số của r! trong hàm sinh trên là nr (công thức chỉnh hợp lặp). Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 30 / 54
  31. Hàm sinh mũ Hàm sinh mũ Ví dụ Tìm số cách để chia 25 người vào trong 3 căn phòng với ít nhất một người mỗi phòng? 3  x2 x3  x 3 Ta dễ dàng thấy được hàm sinh mũ là x + 2! + 3! + ··· = (e − 1) để tìm hệ số của xr/r! ta khai triển biểu thức của ex, (ex − 1)3 = e3x − 3e2x + 3ex − 1 Thay vào ta được ∞ ∞ ∞ X xr X xr X xr e3x − 3e2x + 3ex − 1 = 3r − 3 2r + 3 − 1 r! r! r! r=0 r=0 r=0 Suy ra hệ số của x25/25! là 325 − (3 × 225) + 3. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 31 / 54
  32. Phương pháp tổng Phương pháp tổng Trong phần này ta chỉ ra cách xây dựng hàm sinh thông thường h(x) mà hệ số của xr phụ thuộc vào r. Ta có một số quy luật sau đây để xây dựng hàm sinh mới từ các hàm sinh P n P n P n đã có sẵn. Giả sử A(x) = anx , B(x) = bnx , C(x) = cnx . Nếu bn = dan, thì B(x) = dA(x) với mọi hằng số d. Nếu cn = an + bn, thì C(x) = A(x) + B(x). Pn Nếu cn = i=0 aibn−i, thì C(x) = A(x)B(x). k Nếu bn = an−k, ngoại trừ bi = 0 với i < k, thì B(x) = x A(x). 2 3 r Nếu g(x) = a0 + a1x + a2x + a3x + ··· + arx + ··· , lấy đạo hàm của g(x) d 2 r−1 ta được dx g(x) = a1 + 2a2x + 3a3x + ··· + rarx + ··· . Nhân hai vế cho x ta được  d  x g(x) = a x + 2a x2 + 3a x3 + ··· + ra xr + ··· dx 1 2 3 r Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 32 / 54
  33. Phương pháp tổng Phương pháp tổng Ví dụ 2 Xây dựng hàm sinh h(x) với hệ số ar = 2r . 1 2 3 Từ 1−x = 1 + x + x + x + ··· , ta được     d 1 1 1 2 2 3 3 r x dx 1−x = x (1−x)2 = x + x + x + ··· + rx + ··· Ta lặp lại quá trình trên với x ta được (1−x)2   d x x(1+x) 12 22 2 32 3 2 r Cuối cùng x dx (1−x)2 = (1−x)3 = x + x + x + ··· + r x + ··· nhân 2 vào hai vế của phương trình trên ta được 2x(1+x) 2 12 2 22 2 2 2 r h(x) = (1−x)3 = ( × )x + ( × )x + ··· + ( × r )x + ··· . Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 33 / 54
  34. Phương pháp tổng Phương pháp tổng Ví dụ Xây dựng hàm sinh h(x) với hệ số ar = (r + 1)r(r − 1). Ta có   1 + 4 − 1   2 + 4 − 1   3!(1 − x)−4 = 3! 1 + x + x2 + ··· 1 r Hệ số ar của khai triển trên là  r + 4 − 1  (r + 3)! a = 3! = 3! = (r + 3)(r + 2)(r + 1) r r r!3! Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 34 / 54
  35. Phương pháp tổng Phương pháp tổng Khi đó khai triển lũy thừa của 3!(1 − x)−4 là: 3! = (3 × 2 × 1) + (4 × 3 × 2)x + ··· + (r + 3)(r + 2)(r + 1)xr + ··· (1 − x)4 Nhân hai vế cho x2 ta được 3!x2 = (3 × 2 × 1)x2 + (4 × 3 × 2)x3 + ··· + (r + 1)r(r − 1)xr + ··· (1 − x)4 2 Vậy hàm sinh cần tìm là 3!x h(x) = (1−x)4 . −n Tổng quát, ta thấy (n − 1)!(1 − x) có hệ số ar là ar = (n − 1)!C(r + n − 1, r) = [r + (n − 1)][r + (n − 2)] ··· (n + 1) Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 35 / 54
  36. Phương pháp tổng Phương pháp tổng Định lý r ∗ Nếu h(x) là hàm sinh với ar là hệ số của x , thì h (x) = h(x)/(1 − x) là hàm sinh của tổng các ar, nghĩa là r ! ∗ 2 X r h (x) = a0 + (a0 + a1)x + (a0 + a1 + a2)x + ··· + ai x + ··· . i=0 Ví dụ Tính tổng 2 × 12 + 2 × 22 + 2 × 32 + ··· + 2n2. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 36 / 54
  37. Phương pháp tổng Phương pháp tổng 2 Hàm sinh h(x) cho ar = 2r là 2x(1 + x)/(1 − x)3 n Theo định lý trên, tổng cần tìm a1 + a2 + ··· + an là hệ số của x trong h∗(x) = h(x)/(1 − x) = 2x(1 + x)/(1 − x)4 = 2x(1 − x)−4 + 2x2(1 − x)−4 Hệ số của xn trong 2x(1 − x)−4 là hệ số của xn−1 trong 2(1 − x)−4, và hệ số của xn trong 2x2(1 − x)−4 là hệ số của xn−2 trong 2(1 − x)−4. Do đó tổng cần tìm bằng  (n − 1) + 4 − 1   (n − 2) + 4 − 1  2 + 2 (n − 1) (n − 2)  n + 2   n + 1  = 2 + 2 . 3 3 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 37 / 54
  38. Phương pháp tổng Phương pháp tổng Ví dụ Tính tổng 3 × 2 × 1 + 4 × 3 × 2 + ··· + (n + 1)n(n − 1). Hàm sinh h(x) cho ar = (r + 1)r(r − 1) là: h(x) = 6x2(1 − x)−4. Bởi định lý trên, tổng cần tìm là hệ số của xn trong h∗(x) = h(x)/(1 − x) = 6x2(1 − x)−5. Hệ số của xn trong h∗(x) bằng với hệ số của xn−2 trong 6(1 − x)−5, và bằng 6C((n − 2) + 5 − 1, n − 2) = 6C(n + 2, 4). Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 38 / 54
  39. Bài toán đệ quy Ứng dụng hàm sinh thông thường trong bài toán đệ quy Trong phần này, chúng ta sẽ trình bày một ứng dụng quan trọng của hàm sinh trong việc giải bài toán đệ quy, ta gọi G(x) là hàm sinh của dãy {an}n≥0 và tiến hành các bước sau: (1) Chuyển công thức đệ quy thành một phương trình của G(x), thường được thực hiện bằng cách nhân cả hai vế của phương trình đệ quy cho xn, hay xn+1, hay xn+k với một k nào đó, và lấy tổng trên tất cả các số nguyên không âm n. (2) Giải phương trình để tìm G(x). n (3) Tìm hệ số của x trong G(x), hệ số đó chính bằng an, và ta được một công thức tường minh cho an. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 39 / 54
  40. Bài toán đệ quy Ứng dụng hàm sinh thông thường trong bài toán đệ quy Ví dụ Một người gửi 1000 đô la vào trong một tài khoản tiết kiệm với lãi suất là 5 phần trăm một năm. Bắt đầu mỗi năm, người đó lại chuyển vào tài khoản đó 500 đô la nữa. Hỏi số tiền trong tài khoản tiết kiệm của người đó sau n năm là bao nhiêu? Gọi an là số dư trong tài khoản tiết kiệm sau n năm. Ta thấy a0 = 1000, P n an+1 = 1.05an + 500. Gọi G(x) = n≥0 anx là hàm sinh của dãy {an}n≥0. Bây giờ ta giải bài toán theo các bước như trên: (1) Nhân cả hai vế của hệ thức đệ quy với xn+1 và lấy tổng trên tất cả các số nguyên không âm n, ta được X n+1 X n+1 X n+1 an+1x = 1.05anx + 500x n≥0 n≥0 n≥0 500x Phương trình trên tương đương với: G(x) − a0 = 1.05xG(x) + 1−x Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 40 / 54
  41. Bài toán đệ quy Ứng dụng hàm sinh thông thường trong bài toán đệ quy (2)Do đó ta được 1000 500x G(x) = + 1 − 1.05x (1 − x)(1 − 1.05x) (3)Ta thấy 1000 X = 1000 · 1.05nxn 1 − 1.05x n≥0 do đó hệ số của xn trong biểu thức trên là 1000 · 1.05n. 500x P n P n n Xét thành phần thứ hai (1−x)(1−1.05x) = 500x. n≥0 x n≥0 1.05 x Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 41 / 54
  42. Bài toán đệ quy Ứng dụng hàm sinh thông thường trong bài toán đệ quy Trong tích trên xn−1 được tạo thành từ xi của tổng thứ nhất và 1.05n−1−ixn−1−i từ tổng thứ hai với 0 ≤ i ≤ n − 1. Do đó hệ số của xn 500x trong (1−x)(1−1.05x) là n−1 X 1.05n − 1 500 1.05i = 500 = 10000 · (1.05n − 1) 1.05 − 1 i=0 Ta được hệ số n n n an = 1000 · 1.05 + 10000 · (1.05 − 1) = 1.05 .11000 − 10000. Thử lại ta được kết quả đúng. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 42 / 54
  43. Bài toán đệ quy Ứng dụng hàm sinh thông thường trong bài toán đệ quy Ví dụ Cho hệ thức đệ quy an+1 = 4an − 100, và a0 = 50. Tìm công thức cho an. n 4n−1 Đáp án: an = 50 · 4 − 100 · 3 . Ví dụ Cho hệ thức đệ quy an+2 = 3an+1 − 2an, và a0 = 0, a1 = 1. Tìm công thức cho an. n Đáp án: an = 2 − 1. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 43 / 54
  44. Bài toán đệ quy Định lý 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 [n] thành các đoạn S = {1, 2, ··· , i} và T = {i + 1, i + 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 {an}, {bn}, và {cn}. 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 (ở đây 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? Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 44 / 54
  45. Bài toán đệ quy Ứng dụng hàm sinh thông thường trong bài toán đệ quy Nếu đợt dạy lý thuyết có k ngày thì ta sẽ có k cách để chọn ra một ngày  n − k  nghỉ, và nếu đợt dạy thực hành có n − k ngày thì có cách để 2 P k chọn ra 2 ngày nghỉ. Các hàm sinh tương ứng là A(x) = k≥1 kx , và  m  B(x) = P xm. Ta có P xi = 1 . m≥2 2 i≥0 1−x 2 Lấy đạo hàm ta được x và x Gọi là số cách để A(x) = (1−x)2 B(x) = (1−x)3 fn chia học kỳ ra hai phần và chọn ngày nghỉ, và gọi F(x) là hàm sinh của nó. Khi đó ta có A(x)B(x) = F(x). Do đó x3 X  n + 4  X  n + 1  F(x) = = x3 xn = xn (1 − x)5 4 4 n≥0 n≥3  n + 1  Từ đó suy ra f = . n 4 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 45 / 54
  46. Bài toán đệ quy Ứng dụng hàm sinh thông thường trong bài toán đệ quy Ví dụ Tương tự như ví dụ trên nhưng ở đây thay vì chọn ngày nghỉ, hiệu trưởng chọn ra một số ngày tự học trong cả hai phần của học kỳ. Hỏi có bao nhiêu cách khác nhau để hiệu trưởng làm như vậy? Gọi gn là số cách mà hiệu trưởng có thể chọn. Chia bài toán ra thành 2 phần. Gọi C(x) là hàm sinh cho số cách để chọn ra một tập các ngày tự học trong phần thứ nhất của học kỳ. Bởi vì một tập k phần tử sẽ có 2k tập P k k 1 con, ta có C(x) = k≥0 2 x = 1−2x . Ta thấy phần thứ hai cũng có hàm sinh giống như phần thứ nhất. Do đó hàm sinh cần tìm là  n + 2 − 1  F(x) = C(x)C(x) = 1 = P (2x)n = (1−2x)2 n≥0 n  n + 1  P (2x)n = P (n + 1)2nxn. Vậy ta được g = (n + 1)2n. n≥0 1 n≥0 n Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 46 / 54
  47. Bài toán đệ quy Ứng dụng hàm sinh thông thường trong bài toán đệ quy Ví dụ Tìm số cách để chia n ngày của một học kỳ ra thành ba phần. Trong đó, ở phần thứ nhất số ngày nghỉ được chọn tùy ý, ở phần thứ hai số ngày nghỉ là số lẻ, và ở phần thứ ba số ngày nghỉ là số chẵn. n−3 Đáp án: gn = 2 n(n + 3). Ví dụ Gọi p≤k(n) là số các phân hoạch của số nguyên n thành những phần có nhỏ hơn hay bằng k, chứng minh rằng ∞ k X Y 1 p (n)xn = ≤k 1 − xi n≥0 i=1 = (1 + x + x2 + x3 + ··· )(1 + x2 + x4 + x6 + ··· ) ··· (1 + xk + x2k + x3k + ··· ). Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 47 / 54
  48. Bài toán đệ quy Ứng dụng hàm sinh mũ trong bài toán đệ quy Tương tự như hàm sinh thông thường, gọi G(x) là hàm sinh mũ cho dãy {an}, ta thực hiện theo một số bước như sau: (1) Chuyển hệ thức đệ quy thành một phương trình trong G(x), thường được thực hiện bằng cách nhân cả hai vế của phương trình đệ quy cho xn/n!, hay xn+1/(n + 1)!, hay xn+k/(n + k)! với một k nào đó, và lấy tổng trên tất cả các số nguyên không âm n. (2) Giải G(x). n (3) Tìm hệ số của x /n! trong G(x), hệ số đó chính bằng an, và ta được một công thức tường minh cho an. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 48 / 54
  49. Bài toán đệ quy Ứng dụng hàm sinh mũ trong bài toán đệ quy Ví dụ Cho a0 = 1, và an+1 = (n + 1)(an − n + 1), nếu n ≥ 0. Tìm một công thức cho an. Chú ý Nếu chúng ta giải bài toán trên bằng cách dùng hàm sinh thông thường, thì sẽ gặp vấn đề lúc đưa ra kết quả. Dãy {an} tăng khá nhanh, và chúng ta không tìm được dạng hàm sinh thông thường tương ứng. Do đó bài toán trên sẽ được giải bằng hàm sinh mũ. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 49 / 54
  50. Bài toán đệ quy Ứng dụng hàm sinh mũ trong bài toán đệ quy P xn Gọi A(x) = n≥0 an n! là hàm sinh mũ của dãy {an}n≥0. Ta nhân cả hai xn+1 vế của hệ thức đệ quy với (n+1)! , và lấy tổng với mọi n ≥ 0, ta được X xn+1 X xn+1 X xn+1 a = a − (n − 1) n+1 (n + 1)! n n! n! n≥0 n≥0 n≥0 Ta thấy vế trái là A(x) − 1, hạng tử đầu tiên của vế phải là xA(x). Từ đó ta được phương trình trên tương đương với A(x) − 1 = xA(x) − x2ex + xex. 1 X X xn+1 A(x) = + xex = xn + 1 − x n! n≥0 n≥0 n P n n Hệ số của x /n! trong n≥0 x là n!, trong khi hệ số của x /n! trong P xn+1 n n≥0 n! là n. Vậy hệ số của x /n! trong A(x) là n! + n. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 50 / 54
  51. Bài toán đệ quy Ứng dụng hàm sinh mũ trong bài toán đệ quy Ví dụ Cho f0 = 0, và fn+1 = 2(n + 1)fn + (n + 1)! nếu n ≥ 0. Tìm một công thức cho fn. P xn Gọi F(x) = n≥0 fn n! là hàm sinh mũ của dãy {fn}. Nhân cả hai vế của hệ thức trên với xn+1/(n + 1)!, và lấy tổng với mọi n ≥ 0. Ta được P xn+1 P xn P n+1 n≥0 fn+1 (n+1)! = 2x n≥0 fn n! + n≥0 x Do f0 = 0 nên vế trái bằng F(x), hạng tử thứ nhất của vế phải bằng 2xF(x), và hạng tử thứ hai của vế phải bằng x/(1 − x). Do đó, ta có được x x F(x) = 2xF(x) + 1−x , hay F(x) = (1−x)(1−2x) Suy ra, X F(x) = (2n − 1)xn n≥0 n n Ta được hệ số của x /n! trong F(x) là fn = (2 − 1)n! Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 51 / 54
  52. Bài toán đệ quy Ứng dụng hàm sinh mũ trong bài toán đệ quy Bổ đề P xi P xk Gọi {ai} và {bk} là hai dãy, và gọi A(x) = i≥0 ai i! , và B(x) = k≥0 bk k!  n  là các hàm sinh của nó. Gọi c = Pn a b , và C(x) là hàm n i=0 i i n−i sinh của dãy {cn}. Thì A(x)B(x) = C(x) Hay nói cách khác, hệ số của xn/n! trong A(x)B(x) là  n  c = Pn a b . n i=0 i i n−i Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 52 / 54
  53. Bài toán đệ quy Ứng dụng hàm sinh mũ trong bài toán đệ quy Định lý (Công thức tích cho hàm sinh mũ) Gọi an là số cách để xây dựng một cấu trúc nào đó trên một tập hợ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 đoạn [n] thành những tập con rời nhau S và T, (S ∪ T = [n]), và xây dựng một cấu trúc trên S, và một cấu trúc thứ hai lên T. Gọi A(x),B(x), và C(x) là các hàm sinh mũ tương ứng của các dãy {an}, {bn}, và {cn}, thì A(x)B(x) = C(x). Ví dụ Một đội bóng có n cầu thủ. Huấn luyện viên chia đội bóng ra thành hai nhóm, và mỗi nhóm đứng thành một dòng. Các thành viên của nhóm thứ nhất mặt áo cam, áo trắng, hoặc áo xanh. Các thành viên của nhóm còn lại mặc áo đỏ. Hỏi có bao nhiêu cách để thực hiện các việc trên? Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 53 / 54
  54. Bài toán đệ quy Ứng dụng hàm sinh mũ trong bài toán đệ quy Giả sử huấn luyện viên chọn ra k người để tạo thành nhóm thứ nhất. Gọi ak là số cách để k người này có thể chọn áo cam, trắng, hoặc xanh, và k đứng thành một dòng. Thì ak = k!3 , hàm sinh mũ của dãy {ak} là P k xk 1 A(x) = k≥0 k!3 k! = 1−3x . Tương tự, giả sử có m người trong nhóm thứ hai. Gọi bm là số cách để m người này đứng thành một dòng, bm = m!, và hàm sinh mũ của dãy bm là P xm 1 B(x) = m≥0 m! m! = 1−x . Gọi cn là số cách để thực hiện tất cả những việc trên, và C(x) là hàm sinh mũ tương ứng của nó. Theo công thức trên ta có 1 1 1 P k k 1 P m C(x) = A(x)B(x) = 1−3x · 1−x . Do 1−3x = k≥0 3 x , và 1−x = m≥0 x , n n+1 ta có hệ số của x /n! trong C(x) là cn = n!(3 − 1)/2. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 54 / 54