Phương Pháp Hàm Sinh - Giải Toán Tổ Hợp (Chuyên Đề K57C)
Phương Pháp Hàm Sinh - Giải Toán Tổ Hợp (Chuyên Đề K57C)
Môn: Phân tích hoạt động kinh doanh 12 tài liệu
Trường: Đại học Bách Khoa Hà Nội 3.5 K tài liệu
Tác giả:
Preview text:
TRƯÍNG ĐẠI HỌC SƯ PHẠM HÀ NộI KHOA TOÁN-TIN
CHUYÊN ĐỀ ĐẠI SỐ SƠ CẤP
PHƯƠNG PHÁP SỬ DỤNG HÀM SINH
Giáo viȇn hmớng dấn: ThS. Đào Ngọc Minh
Nhóm sinh viȇn: Trương Thị Nhung Lăng Thúy Nga
Phạm Thị Lan Phương Mai Thị Ngoan Lớp: K57C HÀ NộI, 9/2010 Mṇc lṇc
1 Giďi thi»u về hàm sinh và các phép toán trên hàm sinh 2
1.1 Giới thi»u về hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Các phép toán trȇn hàm sinh . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Nhȃn với hằng số . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 C®ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 Dịch chuyễn sang phải . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 Dạo hàm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.5 Quy tắc xoắn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Sfi dṇng phương pháp hàm sinh trong giải toán 7
2.1 Dùng hàm sinh là da thác . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Dùng hàm sinh là các chuối lǔy thàa vȏ hạn . . . . . . . . . . . . . . . 8
2.2.1 Cơ sở lý thuyết . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Dǎy Fibonacci
. . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.3 Dếm bằng hàm sinh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Bài tªp 15 1
1 Giďi thi»u về hàm sinh và các phép toán trên hàm sinh
1.1 Giďi thi»u về hàm sinh
Hàm sinh là m®t trong nhǎng sáng tạo thần tình, bất ngờ, nhiều áng dụng của
toán rời rạc. Nói m®t cách nȏm na, hàm sinh chuyễn nhǎng bài toán về dǎy số thành
nhǎng bài toán về hàm số. Với diều này chúng ta có thễ dế dàng giải quyết dmợc m®t số bài toán.
Trong bài này, các dǎy số sě dmợc dễ trong dấu ngo°c <> dễ phȃn bi»t với các dối tmợng toán học khác. Đ$nh nghĩa :
Hàm sinh thường của dǎy số vȏ hạng (an)n≥0 là chuối lǔy thàa hình thác:
G(x) = a0 + a1x + a2xn + · · · + anxn + . . .
Ta gọi hàm sinh là chuối lǔy thàa hình thác bởi vì thȏng thmờng ta sě chỉ coi x là
m®t kí hi»u thay thế thay vì m®t số. Chỉ trong vài trmờng hợp, ta sě cho x nhªn các
giá trị thực, vì thế ta gần nhm khȏng dễ ý dến sự h®i tụ của các chuối. Có m®t số loại
hàm sinh khác nhau, trong bài này ta chỉ xét dến hàm sinh thmờng.
Trong bài này ta sě ký hi»u sự tmơng áng giǎa m®t dǎy số và hàm sinh bằng dấu "↔" nhm sau : 2 n
<a0, a1, a2, . . . , an, . . . > ↔ a0 + a1x + a2x + · · · + anx + . . .
Ví dụ, dmới dȃy là m®t số ví dụ và hàm sinh của chúng
<0, 0, 0, 0, . . . ,> ↔ 0 + 0.x + 0.x2 + 0.x3 + · · · = 0 2 3
<1, 0, 0, 0, . . . ,> ↔ 1 + 0.x + 0.x + 0.x + · · · = 1 2 3 2
<3, 2, 1, 0, . . . ,> ↔ 3 + 2.x + 1.x + 0.x + · · · = x + 2x + 3
Quy tắc ở dȃy rất dơn giản: Số hạng thá i của dǎy số (dánh số tà 0) là h» số của xi trong hàm sinh.
Nhắc lại cȏng thác tính tỗng của cấp số nhȃn lùi vȏ hạn là :
1 + z + z2 + ··· = 1 1 − z
Dẫng thác này khȏng dúng với |z| ≥ 1. Nhmng m®t lần nǎa ta khȏng quan tȃm dến
vấn dề h®i tụ. Cȏng thác này cho chúng ta cȏng thác tmờng minh cho hàm sinh của hàng loạt dǎy số : 2 3 1
< 1, 1, 1, 1, · · · >↔ 1 + x + x + x + · · · = 1 1 − x 2 3
< 1, −1, 1, −1, · · · >↔ 1 − x + x − x + · · · = 1 + x
< 1, a, a2, a3, · · · >↔ 1 + ax + a2.x2 + a3.x3 + · · · = 1 1 − ax
< 1, 0, 1, 0, · · · >↔ 1 + x2 + x4 + · · · = 1 1 − x2
Vªn dụng diều này, ta có bài toán :
Ví dṇ 1. Tìm công thúc tổng quát cho dãy (yn, n ≥ 0) với y0 = 1 và yn = a.yn−1 +
bn, ∀n ≥ 1. Giải Σ ∞ Xét G(x) = ynxn n=1 Khi dó : ∞ Σ
G(x) = y0 + ynxn n=0 ∞ Σ
= y0 + (ayn−1 + bn)xn n=1 ∞ ∞ Σ Σ = y0 + ayn−1xn + bnxn n=0 ∞ n=0 ∞ Σ Σ = ax
ynxn + y0 − 1 + bnxn n=0 n=0 1
= axG(x) + 1 − 1 + 1— bxdo(y0 = 1) 1
= axG(x) + 1−bx
Vªy G(x) = axG(x) + 1 1 − bx 1
⇔ G(x)(1 − ax) = 1— bx 1
⇔ G(x) = (1 − ax)(1 − bx) 1 b a ⇔ G(x) = ( )
b − a 1 − bx − 1 − ax b Mà
= b(1 + bx + b2x2 + . . . ) = Σ ∞ bn+1xn 1 − bx n=0 a
= a(1a + ax + a2x2 + . . . ) = Σ ∞ an+1xn 1 − ax n=0 ∞ n+1 n+1 Σ ⇒ b G(x) = − a n=0 b − a bn+1 − an+1
Vªy cȏng thác tỗng quát của yn là: yn = b − a , ∀n ≥ 0.
1.2 Các phép toán trên hàm sinh
Phép màu của hàm sinh nằm ở chố ta có thễ chuyễn các phép toán thực hi»n trȇn
dǎy số thành các phép toán thực hi»n trȇn hàm sinh tmơng áng của chúng. Tà dó ta
có thễ dế dàng thực hi»n các phép toán. 3
1.2.1 Nhân vďi hằng số
Quy tắc 1. Nếu < f0, f1, f2, f3, · · · >↔ F (x) thì < cf0, cf1, cf2, · · · >↔ cF (x) Chfíng minh: Ta có:
< cf0, cf1, cf3, · · · >↔ (cf0)x + (cf1) + (cf3)x3 + . . . = c(f0 + f1x + f2x2 + f3x3 + . . . ) = cF (x) 1
Ví dṇ 2. < 1, 0, 1, 0, · · · >↔ 1 — x2 2
< 2, 0, 2, 0, · · · >↔ 1 − x2
Ví dṇ 3. < 1, a, a2, a3, ··· >↔ 1 + ax + a2x2 + a3x3 = 1 = f(x) 1 − ax
Nhȃn hàm sinh trȇn với a ta dmợc: a
af(x) = 1−ax 2 2 3 3
⇔ af(x) = a(1 + ax + a x + a x + . . . )
= a + a2x + a3x2 + a4x3 + · · · ↔< a, a2, a3, a4, · · · > 1.2.2 Cộng
Quy tắc 2. C®ng hai hàm sinh tương úng với vi»c c®ng các số hạng của dãy số
theo đúng chỉ số. Nếu < f0, f1, f2, · · · >↔ F (x) và < g0, g1, g2, · · · >↔ G(x) thì <
f0 + g0, f1 + g1, f2 + g2, · · · >↔ F (x) + G(x). Chfíng minh: Ta có :
< f0 + g0, f1 + g1, f2 + g2, · · · > 2
— (f0 + g0) + (f1 + g1)x + (f2 + g2)x + . . .
= (f0 + f1x + f2x2 + . . . ) + (g0 + g1x + g2x2 + . . . )
= F (x) + G(x) 2
Ví dṇ 4. < 2, 0, 2, 0, · · · >↔ 1− x2 1
Thªt vªy < 1, 1, 1, 1, · · · >↔ 1 — x 1
và < 1, −1, 1, −1, · · · >↔ 1 +x 1 1 2
Áp dụng quy tắc c®ng ta có: < 2, 0, 2, 0, · · · >↔ 1 − x + 1+ x = 1− x2.
1.2.3 Dịch chuyển sang phải 1
Ta bắt dầu tà m®t dǎy số dơn giản và hàm sinh của nó: < 1, 1, 1, 1, · · · >↔ 1 — x.
Bȃy giờ ta dịch chuyễn sang phải bằng cách thȇm k số 0 vào dầu: xk
< 0, 0, 0, . . . , 0, 1, 1, 1, · · · >↔ xk + xk+1 + xk+2 + · · · = xk(1 + x + x2 + . . . ) = 1− x k
Nhm vªy thȇm k số 0 vào dầu dǎy số tmơng áng với vi»c hàm sinh nhȃn với x . Diều
này cǔng dúng trong trmờng hợp tỗng quát.
Quy tắc 3. Nếu < f0, f1, f2, · · · >↔ F (x) thì < 0, 0, . . . , 0, f0, f1, f2, · · · >↔ xkF (x) Chfíng minh:
< 0, 0, . . . , 0, f0, f1, f2, · · · >↔ f0xk + f1xk+1 + f2xk+2+ . . . = xk(f0 + f1x + f2x2 + . . . ) = xkF (x) 1.2.4 Đạo hàm
Diều gì sě xảy ra nếu ta lấy dạo hàm của hàm sinh? Chúng ta hǎy bắt dầu tà vi»c
lấy dạo hàm của m®t hàm sinh dǎ trở nȇn quen thu®c trong dǎy số toàn 1: d d 1
(1 + x + x2 + x3 + x4 + . . . ) = ( ) dx dx 1 − x
1 + 2x + 3x2 + 4x3 + · · · = 1 1 (1 − x)2
< 1, 2, 3, 4, · · · >↔ (1 − x)2
Ta tìm dmợc hàm sinh cho dǎy số < 1, 2, 3, 4, · · · >
Tỗng quát, vi»c lấy dạo hàm của hàm sinh có hai tác d®ng lȇn dǎy số tmơng áng:
Các số hạng dmợc nhȃn với chỉ số và toàn b® dǎy số dmợc dịch chuyễn sang trái 1 vị trí. dF Quy tắc 4. (x)
Nếu < f0, f1, f2, · · · >↔ F(x) thì < f1, 2f2, 3f3, · · · >↔ dx Chfíng minh: 2 d 2 3
< f 1, 2f 2,3f 3,· · · >↔ 1f + 22f x + 3 3fx + . . . = dx(f0 + f1x + f2x + f 3x +. . . ) dF (x) = dx
Quy tắc dạo hàm là m®t quy tắc rất hǎu hi»u. Trong thực tế, ta thmờng xuyȇn cần
dến m®t trong hai tác d®ng của phép dạo hàm, nhȃn số hạng với chỉ số và dịch chuyễn
sang trái. M®t cách diễn hình, ta chỉ muốn có m®t tác d®ng và tìm cách "vȏ hi»u hóa" tác d®ng còn lại.
Ví dṇ 5. Tìm hàm sinh cho dãy số < 0, 1, 4, 9, 16, · · · > 5 Giải
Ta có < 0, 1, 4, 9, 16, · · · >=< 0, 1.1, 2.2, 3.3, 4.4, · · · > 1
M°t khác < 1, 1, 1, · · · >↔ 1 − x = f(x) df(x) 1
dx =< 0, 1, 2, 3, 4, · · · >= (1 — x)2 x
Áp dụng quy tắc dịch chuyễn sang phải: < 0, 1, 2, 3, 4, · · · >↔ (1 − x)2 = g(x) dg 1 + x
Áp dụng quy tắc dạo hàm, ta dmợc: < 1.1, 2.2, 3.3, 4.4, · · · >↔ dx(x) = (1 — x3) 1 + x
hay < 1, 4, 9, 16, · · · >↔ (1− x)3
Vªy hàm sinh của dǎy số ban dầu tmơng áng là: < 0, 1, 4, 9, 16, · · · >↔ x(1 + x) (1 − x)3 1.2.5 Quy tắc xoắn Σ ∞ Σ n
Xét hàm G(x) = A(x).B(x) = aibn−i Σ n=0 i=0 n D°t dn =
aibn−i. Ta có hàm sinh cho dǎy {dn}∀n ≥ 0 chính là hàm G(x). Ta gọi i=0
quy tắc này là phép xoắn hay quy tắc xoắn.
Ví dṇ 6. Số Catalan
Số Catalan là số được xác đ$nh m®t cách truy hồi như sau: nΣ −1
d0 = d1 = 1, Cn = d0dn−1 + d1dn−2 + · · · + dn−1d0 =
didn−1−i∀n ≥ 1 i=0
Số Catalan có nhiều đ$nh nghĩa tổ hợp khác nhau, chẫng hạn, số Catalan là số các
cách nối 2n điểm trên đường tròn bằng n dây cung không cắt nhau, là số cây nh$ phân
có gốc có n + 1 lá, là số đường đi ngắn nhất trên lưới nguyên tù điểm (0, 0) đến điểm
(n, n) không vượt qua đường thẫng y = x,. . . Ngoài ra, trong quá trình tính cũng đưa ra
các đ$nh nghĩa về số Catalan: Là các cách tính tích các ánh xạ f0, f1, . . . , fn. Sau đây
là bài toán quan trọng về số Catalan.
Hãy tính số hạng tổng quát của dãy Catalan. Giải Σ n Ta có dn+1 =
didn−i∀n ≥ 1 i=0
Xét hàm sinh G(x) = Σ ∞ dnxn = 1 + Σ
∞ dnxn (vì d0 = 1) n=0 n=1 Σ ∞ Σ ∞ Σ n n
khi dó G(x) − 1 = dnxn = didn−ix n=1 n=1 i=0 √ 1
Theo quy tắc xoắn ta có: G(x) ± 1 − 4x
—1 = xG(x)2 ⇒ G(x) = 2x √ 1 1 vì G(x) − − 4x ≥ 0 ⇒ G(x) = 2x √ Σ ∞ Σ 1 ta có: 1 − 4x = f (n)(0) ∞ xn = 1 − 2
Cn−1 xn(theo khai triễn Taylor) 2n−2 n=0 n!
n=1 n Σ∞ 1 n−1 n 1 − (1 − 2
C2n−2x ) n ∞ 1 n=1 Σ
Dồng nhất hai vế ta dmợc: G(x) = = Cn xn 2x 1
n=0 n + 1 2n
Vªy số Catalan là: d = n n C n + 1 2n
Trȇn dȃy là m®t số phép toán trȇn hàm sinh. Sau dȃy chúng ta sě xét m®t số bài
toán cụ thễ sả dụng m®t vài hàm sinh thmờng g°p với m®t số phép toán tmơng áng.
2 Sfi dṇng phương pháp hàm sinh trong giải toán
2.1 Dùng hàm sinh là đa thfíc
Ví dṇ 7.r Cho m, n, r là các số tü nhiên với r ≤ m, n chúng minh rằng: Σ Cr = CkCr−k m+n n m k=0 Eiải
Xét f(x) = (1 + x)n và g(x) = (1 + x)m Σ n+m
Ta có f(x)g(x) = (1 + x)n+m = Cr r n+m x (1) r=0 Σ n Σ m
M¾t khác ta có: f(x) = Cknxk và g(x) = m Cj xj k=0 j=0 Σ n Σ m
⇒ f(x)g(x) = Cknx k m Cj xj k=0 j=0 Σ n Σ m nΣ +m Σ r k j k+j k r r = CnCmx = (
CnCm — kx ) (2) k=0 j=0 r=0 k=0 r r Σ r k r−k
Tù (1) và (2) đồng nhất hóa các h» số của x ta có: Cn+m = CnCm (đpcm) k=0
Ví dṇ 8. Tính :S = 12C1n+ 22C2 n+ 32C3 n+· · · + p2Cp n+ · · · + n2Cnn Giải
Xét f(x) = (1 + x)n = C0n+ C1nx + C2 nx2 + C3 n
x3 + · · · + Cnnxn
và g(x) = x(1 + x)n = C0nx + C1nx2 + C2nx3 + C3 n
x4 + · · · + Cnnxn+1
Ta có: f,(x) = n(1 + x)n−1 = C1 + 2C2x + 3C3x2 + · · · + nCnxn−1 n n n n , n−1 1 2 3 n ⇒ f (1) = n2
= Cn + 2Cn + 3Cn + · · · + nCn (1) Và có:
g,(x) = (1 + x)n + nx(1 + x)n−1 = C0n+ 2C1nx + 3C2 nx2 + 4C3 n
x3 + · · · + (n + 1)Cnnxn 7 ,,
⇒ g (x) = 2n(1 + x)n−1 + n(n − 1)x(1 + x)n−2
= 2C1 + 3.2C2x + 4.3C3x2 + · · · + (n + 1)nCnxn−1 n n n n ,,
⇒ g (1) = 2n2n−1 + n(n − 1)2n−2
= 2C1n + 3.2C2n+ 4.3C3n+ · · · + (n + 1)nCnn(2)
Lấy (1) trà (2) vế với vế ta có:
S = 2n2n−1 + n(n − 1)2n−2 − n2n−1 = n2n−1 + n(n − 1)2n−2.
2.2 Dùng hàm sinh là các chuỗi lũy thfia vô hạn
Dầu tiȇn chúng ta nhắc lại m®t số lý thuyết về chuối lǔy thàa vȏ hạn. Dȃy cǔng
chính là nhǎng cơ sở lý thuyết cho phmơng pháp này.
2.2.1 Cơ sď lj thuyết Σ
A = R[[x]] các chuối lǔy thàa hình thác trȇn trmờng thực R có dạng anxn là • n≥0
m®t vành với phép c®ng và nhȃn chuối thȏng thmờng : Σ Σ Σ anxn +
bnxn = (an + bn)xn n≥0 n≥0 n≥0 Σ Σ k anxn = kanxn, k ∈ R n≥0 n≥0 Σ Σ • anxn =
bnxn ⇔ an = bn n≥0 n≥0 Σ 1 1
Trong A, phần tả u = xn •
khả nghịch ⇔ a0 = 0 và = Σ / u anxn an n≥0 n≥0
Nhìn chung thì hàm sinh có rất nhiều áng dụng. Ð dȃy, chúng ta chỉ xét tới nhǎng
áng dụng thmờng g°p của hàm sinh. Trmớc tiȇn phải nói tới là dùng hàm sinh dễ giải
quyết các bài toán về dǎy số d» qui. Khi dǎ biết cȏng thác truy hồi của dǎy, ta có thễ
dùng hàm sinh dễ tính cȏng thác của số hạng tỗng quát của dǎy dó. 2.2.2 Dãy Fibonacci
Dǎy Fibonacci là dǎy số quen thu®c xác dịnh bởi cȏng thác truy hồi:
f0 = 0; f1 = 1; fn = fn−1 + fn−2, ∀n ≥ 2
Chúng ta sě thả dùng hàm sinh dễ tìm cȏng thác tmờng minh cho các số hạng của dǎy số dó. a) Tìm hàm sinh :
Khai triễn dǎy Fibonacci ta dmợc : f0 = 0 f1 = 1
f2 = f1 + f0
fn = fn−2 + fn−1 Giả sả Σ F(x) = fnxn n≥0 Σ
= f0 + f1x + fnxn n≥2 Σ = x + fnxn n≥2 Σ
= x + (fn−1 + fn−2)xn n≥2 Σ Σ = x + fn−1xn + fn−2xn n≥2 n≥2 Σ Σ = x + fn−1xn + fn−2xn n≥2 n≥2 Σ Σ = x + x fnxn + x2 fnxn n≥0 n≥0
= x + xF (x) + x2F (x) x
⇒ F (x) = 1 − x − x2 x
⇒< 0; 1; 2; 3; 5; 8; 13; · · · >↔ − 1 x −x2
Chúng ta thấy dǎy Fibonacci rất khó chịu nhmng hàm sinh của nó lại rất dơn giản.
b) Tìm cȏng thác tmờng minh của số hạng tỗng quát:
Nhm vªy chúng ta dǎ tìm hàm sinh của dǎy Fibonacci, cȏng vi»c tiếp theo là tìm
h» số tà hàm sinh. Có m®t vài cách tiếp cªn cho bài toán này, nhmng cách dơn
giản nhất là sả dụng phmơng pháp phȃn tích. Tà các hàm phȃn thác ta phȃn
tích thành các phȃn thác sơ cấp, tìm các h» số cho các phȃn thác sơ cấp. Tà dó
ta tìm dmợc các h» số cần tìm.
Cụ thễ vào bài toán với dǎy số Fibonacci, ta làm nhm sau:
– Phȃn tích mấu số ra thàa số: 9 √ √ x x 5 = trong dó a 1 + 5 = ; a = 1 − . 1 1 − x − x2 (1 − 2 2 2 1 a x)(1 − 2 a x)
– Tìm các hằng số A1 và A2 sao cho : x A = A1 + 2 ; 1 − x − x2 1 − a1x 1 − a2x
Ta có thễ làm diều này bằng phmơng pháp h» số bất dịnh và ta dế dàng tìm dmợc: 1 1 A 1 1 1 = = √ ; A2 = − = −√ . a1 — a2 5 a1 — a2 5 ⇒ F(x) = x 1 − x − x2 1 1 = √ ( 1 — a1 ) 5 a1 — a2 — a2 1 Σ Σ n n n n = √ ( a a 5 1 x — 2 x ) n≥0 n≥0 1 Σ n n n
= √5 (a1 − a2)x n≥0 Σ √ √ 1 1 + 5 1 − 5 n n n = √ (( 5 2 ) − ( ) )x . 2 n≥0
Dồng nhất h» số, ta dmợc : √ √ 1 1 + 5 1 − 5 n n fn = √ (( 5 2 ) − ( 2 ) )
Dȃy chính là cȏng thác tính số hạng tỗng quát của dǎy Fibonacci.
Tmơng tự nhm vªy, chúng ta cǔng có thễ dùng phmơng pháp hàm sinh dễ giải
nhiều bài toán về dǎy số khác.
2.2.3 Đếm bằng hàm sinh
Trong phần này chúng ta sě biết thȇm m®t áng d®c dáo của hàm sinh nǎa, dó là
hàm sinh có thễ sả dụng cho các bài toán dếm. Cụ thễ là bài toán về chọn các phần tả
tà m®t tªp hợp thȏng thmờng sě dấn tới hàm sinh. Khi hàm sinh dmợc áp dụng theo
cách này thì h» số của xn chính là số cách chọn n phần tả, tác là với an là h» số của Σ
xn, ∀n ≥ 2 thì hàm sinh của số cách chọn sě là F (x) = anxn. n≥0
Dễ hiễu rõ hơn ta di vào các dạng toán sau :
a) Bài toán chọn các phần tả phȃn bi»t
Tỗng quát: có bao nhiȇu cách chọn n phần tả phȃn bi»t tà tªp hợp k phần tả.
Bài toán này có thễ giải quyết dế dàng bằng cȏng thác tỗ hợp. Nhmng lần này
chúng ta sě sả dụng hàm sinh. Cụ thễ nhm sau:
Dầu tiȇn ta hǎy xét tªp hợp có m®t phần tả {a1}. Ta có : 1 cách chọn 0 phần tả 1 cách chọn 1 phần tả 0 cách chọn 2 phần tả trở lȇn
⇒ Hàm sinh cho số cách chọn n phần tả tà tªp {a1} là 1 + x.
Tmơng tự nhm vªy, hàm sinh cho số cách chọn n phần tả tà tªp {ai}(1 ≤ i ≤ k)
cǔng là 1 + x (khȏng phụ thu®c vào sự khác bi»t giǎa các ai ).
Bȃy giờ ta sě cháng minh: hàm sinh cho số cách chọn các phần tả tà hợp của hai
tªp hợp bằng tích các hàm sinh cho số cách chọn các phần tả tà mối tªp hợp(∗).
Tiȇp tục xét tªp 2 phần tả {a1, a2} ta có : 1 cách chọn 0 phần tả 2 cách chọn 1 phần tả 1 cách chọn 2 phần tả 0 cách chọn 3 phần tả trở lȇn
⇒ Hàm sinh cho số cách chọn n phần tả tà tªp {a1, a2} là :
1 + 2x + x2 = (1 + x)2 = (1 + x)(1 + x)
Tiếp tục áp dụng quy tắc này ta sě dmợc hàm sinh cho số cách chọn các phần tả tà tªp k phần tả :
(1 + x)(1 + x) . . . (1 + x) = (1 + x)k
Ta có :< C0k, C1k,C2k,. . . , Ck k,0, 0, · · · >↔ C0 + k, k
C1 + C2k+ · · · + Ckk = (1 + x)k
Nhm vªy h» số của xn trong (1 + x)k là Cnkvà bằng số cách chọn n phần tả phȃn bi»t tà tªp k phần tả. 11
b) Bài toán chọn các phần tả có l°p:
Dễ hiễu cách giải bài toán này trmớc tiȇn ta phải mở r®ng (∗) thành quy tắc xoắn:
Quy tắc xoắn: Gọi A(x) là hàm sinh cho cách chọn các phần tả tà tªp hợp A và
B(x) là hàm sinh cho cách chọn các phần tả tà tªp hợp B. Nếu A và B rời nhau
thì hàm sinh cho cách chọn các phần tả tà tªp A ∪ B là A(x)B(x).
Quy tắc này dúng cho cả trmờng hợp chọn các phần tả phȃn bi»t ,cǔng dúng cho
trmờng hợp chọn nhiều lần cùng m®t phần tả.
Ta có bài toán như sau:
Có 5 loại kẹo : kẹo sǎa, kẹo socola, kẹo chanh,kẹo dȃu và kẹo cà phȇ. Hỏi có bao
nhiȇu cách chọn 12 cái kẹo tà 5 loại kẹo này.
Bài toán dạng tỗng quát : có ba nhiȇu cách chọn k phần tả tà tªp hợp có n phần
tả, trong dó cho phép m®t phần tả có thễ dmợc chọn nhiều lần.
Ta sě giải bài toán dạng tỗng quát.
Chia tªp n phần tả thành hợp của n tªp Ai, 1 ≤ i ≤ n; mối tªp gồm duy nhất
m®t phần tả thu®c tªp n phần tả.
Với mối tªp Ai, ta có : 1 cách chọn 0 phần tả 1 cách chọn 1 phần tả 1 cách chọn 2 phần tả
⇒ Hàm sinh của cách chọn có l°p tà tªp Ai là: 1
< 1, 1, 1, 1, · · · >↔ 1 + x + x2 + x3 + · · · = 1−x
Áp dụng quy tắc xoắn:⇒ Hàm sinh của cách chọn (có l°p) các phần tả tà tªp hợp n phần tả sě là : 1 1 1 1 . . . = 1 − x 1 − x
1 − x (1 − x)n 1
Bȃy giờ ta cần tính h» số của xk trong (1— x)n 1
Dễ làm vi»c này, ta thiết lªp khai triễn Taylor của f(x) := (1 − x)n f'(0) f”(0) f(k)
f(x) = f(0) + x + x2 + · · · + 1! 2!
k! xk + . . . k
⇒H» số của x là: f(k) k k! = n C +k−1
Nhm vªy số cách chọn k phần tả có l°p tà tªp hợp có n phần tả là Ckn+k−1 .
Quay lại với bài toán ban dầu, số cách chọn 12 cái kẹo tà 5 loại kẹo rất dơn giản sě là C1216.
Các bạn có thễ dùng phmơng pháp khác dễ thả lại kết quả này.
Ví dṇ 9. Bài toán chọn quả (úng döng phương pháp đếm bằng hàm sinh). Có bao
nhiêu cách sắp m®t giỏ n trái cây thỏa mãn điều ki»n sau:
• Số táo phải chẫn.
• Số chuối phải chia hết cho 5.
• Chỉ có thể có nhiều nhất 4 quả cam.
• Chỉ có thể có nhiều nhất 1 quả đào.
Bài toán có nhǎng diều ki»n ràng bu®c rất phác tạp và ta có cảm giác nhm vi»c
giải bài toán là vȏ vọng. Nhmng hàm sinh lại cho ta m®t cách giải quyết nhanh gọn. Giải
Trmớc tiȇn ta di tìm hàm sinh cho cách chọn tàng loại quả: Chọn táo: 1 cách chọn 0 quả táo 0 cách chọn 1 quả táo 1 cách chọn 2 quả táo 0 cách chọn 3 quả táo 1
Nhm thế ta có hàm sinh A(x) = 1 + x2 + x4 + · · · = . 1 − x2
Tmơng tự ta tìm dmợc hàm sinh cho cách chọn chuối là:
B(x) = 1 + x5 + x10 + ··· = 1 1 − x5
Hàm sinh cho cách chọn cam và dào hơi khác m®t chút. Ta có : 13 1 cách chọn 0 quả cam 1 cách chọn 1 quả cam 1 cách chọn 2 quả cam 1 cách chọn 3 quả cam 1 cách chọn 4 quả cam 0 cách chọn 5 quả cam
⇒ Hàm sinh là C(x) = 1 + x + x 2 + x3 + x4 = 1 − x5 1 − x 1 − x2
Tmơng tự ta tìm dmợc hàm sinh cho cách chọn dào là D(x) = 1 + x = 1−x
Áp dụng quy tắc xoắn: ⇒ Hàm sinh cho cách chọn tà cả 4 loại quả là: 1
A(x)B(x)C(x)D(x) =
1 1 − x5 1 − x2 = 1 = 1 + 2x + 3x2 + 4x3
1 − x2 1 − x5 1 − x 1 − x (1 − x)2
Nhm vªy cách sắp giỏ trái cȃy gồm n trái dơn giản là n + 1 cách.
Ví dṇ 10. Bài toán nghi»m nguyên (Ví dö 3 sách giáo trình): Tính số nghi»m nguyên
không âm của phương trình:
x1 + x2 + · · · + xd = n Giải
Vì x1, x2, . . . , xd nguyȇn khȏng ȃm nȇn suy ra xi(1 ≤ i ≤ d) nhªn các giá trị 0, 1, 2, 3, . . . .
Ta tìm hàm sinh cho cách chọn mối xi(1 ≤ i ≤ d). Có 1 cách chọn giá trị 0 1 cách chọn giá trị 1 1 cách chọn giá trị 2 1 cách chọn giá trị 3 1
⇒ Hàm sinh cho cách chọn mối x 2
i là 1 + x + x + x3 + · · · = 1 — x. 1
Áp dụng quy tắc xoắn: ⇒ Hàm sinh cho cách chọn b® số (x1, x2, x3, . . . , xd) là (1 − x)d.
Gọi un là số nghi»m nguyȇn khȏng ȃm của phmơng trình x1 + x2 + · · · + xd = n.
Khi dó hàm sinh của dǎy với các số hạng dạng un chính là hàm sinh cho số cách chọn
b® số (x1, x2, x3, . . . , xd). 1 Σ Σ xk = = k Tác là
k+d−1 xk. u (1 − x)d k≥0 k C k≥0
Vªy un = Cnn+d−1 . 3 Bài tªp
Bài 1. Với n là số nguyȇn dmơng ,cháng minh rằng: 1 2 n−1 n n−1
• a)Cn + 2Cn + · · · + (n − 1)Cn
+ nCn = n2 . 2 3 n n−2
• b)2.1.Cn + 3.2.Cn + · · · + n(n − 1)Cn = n(n − 1)2 . r r r r+1 r n r n
• c)(−1) CrCn + (−1) Cr+1 + · · · + (−1) CnCn = 0. Giải Σ n
• a)Xét f(x) = (1 + x)n = Cknxk (1). k=0
Lấy dạo hàm hai vế ta dmợc Σ n
n(1 + x)n−1 = kCknx k−1(2). k=0
Thay x = 1 vào (2) ta có, Σ n n2n−1 = kCkn(dpcm) k=0
• b)Lȃý dạo hàm cấp hai của (1) và thay x = 1 vào biễu thác vàa nhªn dmợc ta
có dmợc diều cần cháng minh.
• c)Lấy dạo hàm cấp rtheo hai vế của (1) ta dmợc, Σ n
n(n − 1) . . . (n − r + 1)(1 + x)n−r =
k(k − 1) . . . (k − r + 1)Cknx k−r (4) Chia hai k=r
vế của (4) chor! ta dmợc: 1 Σ n n(n 1) . . . (n
r + 1)(1 + x)n−r = k(k − −
− 1) . . . (k − r + xk−r r! 1) r! k=r n Σ = k! Cknxk−r
k=r r!(k − r)! n Σ k = Crxk−r(5) k=r Σ n k r k
Thayx = −1 vào (5) ta dmợc: (−1) CkCn = 0 k=r 15
Bài 2. Với n là số nguyȇn dmơng, CMR: C2 + 2C3 + · · · + (n − 1)Cn > (n − 2)2n−1 n n n Giải
Với x ∈ R, n ∈ N, xét f(x) = (1 + x)n = C0n + C1nx + C2 nx2 + · · · + Cnn(1)
Thay x = 1 vào (1) ta dmợc: 2n = C0 + C1 + · · · + Cn−1 + Cn (2) n n n n
Lấy dạo hàm hai vế của (1) ta dmợc:
n(1 + x)n−1 = C1n+ 2C2nx2 + · · · + (n − 1) n
Cn−1xn−2 + nCnnxn−1 (3)
Thay x = 1 vào (3) ta dmợc: n2n−1 = C1 + 2C2 + · · · + (n − 1)Cn−1 + nCn (4) n n n n
Lấy (4) trà (2) vế với vế ta dmợc:
n2n−1 − 2n = −C0 + C2 + 2C3 + · · · + (n − 1)Cn n n n n 2 3 n ⇔ C n−1
n + 2cn + · · · + (n − 1)Cn = (n − 2)2
+ 1 > (n − 2)2n−1 ⇒dpcm
Bài 3. Rút gọn biễu thác sau: • Σ a)S = n Ck
k=0 (k + 1) n Σ n • b) k Cn 1+k k=0 Σ n — k Ck • c) ( 1) n 1+k k=0 Giải Σ n
• a) Xét hàm f(x) = (1 + x) n = Cknxk k=o Σ n
Suy ra xf(x) = x(1 + x)n = Cknx k+1 k=0
Lấy dạo hàm hai vế ta dmợc: Σ n
nx(1 + x)n−1 + (1 + x)n = (k + 1) n Ckxn (∗) k=0
Thay x = 1 vào (∗), ta có S = n2n−1 + 2n = (n + 2)2n−1
Tác là: S = (n + 2)2n−1 Σ n
• b)Xét f(x) = (1 + x)n = xk k=0
Lấy tích phȃn hai vế ta dmợc: ∫ ∫ n Σ n Σ n t tk+1Ckn (1 + x)n dx = Ck 0 0
ndx ⇒ (1+t)n+1−1 = k+1 (2) n+1 k=0 k=0
Thay t = 2 vào (2) ta dmợc: n 2n+1−1 Σ k Cn n+1 = k+1 k=0
• c)Thay t = −1 vào(2) ta dmợc: Σ n Σ n k+1 Ck −1 1
(−1)k+1Ck 1 (−1) n = n k+1 n+1 ⇒ n+1 = k+1 = n+1. k=0 k=0
Bài 4. Tính tỗng sau: Σ n C • 1)A = k n k k=0 Σ n k−1 Ck • 2)B = (−1) kn k=1 Giải Σ n Σ n n k k k k−1 (1+x)n−1
• 1)Ta xét f(x) = (1 + x) = Cnx ⇒ Cnx = x k=0 k=1 ∫ ∫ 1 Σ n k k−1 1 (1+x)n−1 Lấy tích phȃn hai vế: 0 C k=1 nx dx = 0 x dx ∫
D°t I = 1 (1+x)n−1dx n 0 x Σ n Ck Khi dó, In = n k k=1 ∫ ∫ Mà I −I
= 1 (1+x)k−(1+x)k−1dx nȇn ta có I −I
= 2k−1 và I = 1 0dx = 0 k k−1 0 x k k−1 Σ k 0 0 n Σ n Σ n 2k 1 Vªy In = I0 +
(Ik − Ik−1) = k — k k=1 k=1 k=1
Tà dó ta có ngay tỗng cần tìm. Σ n Σ n • 2)Ta có:
(−1)k Cknxk = (1 − x)n ⇒
(−1)k−1Cknx k−1 = 1−(1−x)n x k=0 k=1 ∫ Σ n
1 1−(1−x)n k−1 Ck
Lấy tích phȃn hai vế ta dmợc: In = 0 x dx = (—1) n k=1 k ∫ Mà I − I
= 1 (1−x)k−1−(1−x)k dx k k−1∫ 1 0 x I − I =
(1 − x)k−1dx = 1 và J = 0 k k−1 0 Σ k o n Σ n 1 Nȇn Jn = Jo +
(Jk — Jk−1) = k k=1 k=1 Σ n Vªy B = 1 k . k=1 1 1 1
Bài 5. Cho Sn = 1 + 2 + 3 + ··· + n, cháng minh rằng: ( 1 n−1 —1)n−1
Sn − CnSn−1 + C2 nSn−2 − · · · + (−1)n−1Cn S1 = n . Giải
Xét f(x) = (x − 1)n = xn − C1xn−1 + C2xn−2 − · · · + (−1)nCn. (1) n n n 1 2 n n
⇒ f(1) = 0 = 1 − C C
n + Cn − · · · + (−1) n (2)
Lấy (1) trà (2) vế với vế ta có:
(x − 1)n = xn − 1 − C1n(xn−1 − 1) + C2n(xn−2 − 1) − · · · + (−1)n−1Cn−1 n (x − 1)
chia hai vế cho x − 1 và lấy tích phȃn trȇn [0,1] ta dmợc: 17 (−1n)−1 ∫
= 1(x − 1)n−1dx ∫n 0 ∫ ∫
= 10(xn−1 +xn−2 +· · ·+1)dx−C1 1
n 0 (xn−2 +xn−3 +· · ·+1)dx+· · ·+(−1)n−1Cn−1 1 n 0 dx = Sn − n
C1Sn−1 + C2nSn−2 + (−1)n−1Cn−1 n S1 ⇒dpcm.
Bài 6. Thu gọn các biễu thác sau: Σ
Cd1Cd2 . . . Cdk n n n
d1+d2+···+dk=m≤n Giải Σ n n d d
Vấn xét da thác f(t) = (1 + t) =
Cni.t i(i = 1, 2, . . . , k) di=0 Σ kn kn j j
Khi dó, (f(t)) = Cknt j=0
Nhm vªy, số hạng bªc m ≤ n là: Cm tm. kn Σ n Σ n kn n n n d d d d
M°t khác (f(t)) = (1 + t) .(1 + t) . . . (1 + t) . = Cn1t 1 · · · Cnkt k. ` ˛¸ d x 1=o dk=0 kln
Nhȃn da thác m®t cách thȏng thmờng thì ta có số hạng bªc m = d1 + d2 + · · · + dk ≤ n Σ là:
Cd1 Cd2 . . . Cdk tm. n n n
d1+···+dk=m≤n
Tà dó ta rút ra h» thác sau: Σ Σ m d d d
Cn1Cn2 . . . Cnk = .
d1+···+dk=m≤n kn Σ
Bài 7. Dùng chuối f(x) =
x2k+1 dễ xȃy dựng hàm sinh cho số nghi»m nguyȇn lẻ k≥0
của phmơng trình x1 + x2 + · · · + xd = n (∗). Giải
Trong phmơng trình (∗) thì x1, x2, x3, . . . , xd có vai trò nhm nhau nȇn ta chỉ cần tìm
hàm sinh cho cách chọn m®t xi(1 ≤ i ≤ d) bất kì. Vì xi nguyȇn dmơng lẻ nȇn xi nhªn
các giá trị :1, 3, 5, 7, . . . .
Nhm vªy hàm sinh cho cách chọn m®t xi là : Σ
f(x) = x + x3 + x5 + · · · = x2k+1 k≥0 Σ x Ta có f(x) = x2k+1 = k≥0 1 − x2
Áp dụng quy tắc xoắn ta tìm dmợc hàm sinh cho cách chọn b® số (x1, x2, x3, . . . , xd) là xd (1 − x2)d
Bài 8. Xác dịnh dǎy số (un)n ≥ 0 biết u0 = u1 = 1 vàun = aun−1 + bun−2, ∀n ≥ 2
trong các trmờng hợp sau: (a, b) = (1, 2), (a, b) = (3, −4) textbfGiải Σ
Ta có hàm sinh của dǎy (un)n ≥ 0 là F(x) = unxn n≥0 Theo bài ra ta có Σ
F (x) = u0 + u1x + unxn n≥2 Σ
= 1 + x + (aun−1 + bun−2)xn n≥2 Σ Σ = 1 + x + a
un−1xn + b un−2xn n≥2 n≥2 Σ Σ
= 1 + x + ax( unxn − u0) + bx2 unxn n≥0 n≥0
= 1 + x + axF (x) − ax + bx2F(x)
F (x) = 1 − ax + x . ⇒ 1 − ax − bx2
• TH1:(a, b) = (1, 2) ta có: F (x) = 1 1 − x − 2x2 = 1
(1 + x)(1 − 2x) 1 2
= 3(1 + x) − 3(1 − 2x)
= 1 Σ(−1)nxn − 2 Σ 2nxn 3 3 n≥0 n≥0
Σ (−1)n − 2n = 3 xn. n≥0 (−1)n − 2n
Dồng nhất h» số ⇒ un = 3 , ∀n ≥ 2 1 − 2x
• TH2: (a, b) = (3,−4) Ta có F (x) = 1 − 3x + 4x2
Bài 9. Xác dịnh dǎy số (un)n ≥ 0 biết u0 = u1 = u2 = 1 vàun = aun−1 + bun−2 +
cun−3, ∀n ≥ 3 trong các trmờng hợp sau: (a, b, c) = (6, −11, 6), (a, b, c) = (5, 1, −5) Giải Σ Xét G(x) =
unxn(1) là hàm sinh của dǎy (un)n ≥ 0. n≥0 Σ
G(x) = u0 + u1x + u2x2 + unxn n≥3 Σ
= u0 + u1x + u2x2 + (aun−1 + bun−2 + cun−3)xn n≥3 Σ Σ Σ
= u0 + u1x + u2x2 + ax( unxn − u1x − u0) + bx2( unxn − u0) + cx3 unxn n≥0 n≥0 n≥0
= 1 + x + x2 + ax(G(x) − x − 1) + bx2(G(x) − 1) + cx3G(x) 19