Bài giảng Toán tổ hợp - Chương 2: Phương pháp đếm dùng hàm sinh
Baøi giaûng Toaùn toå hôïp
Nguyeãn Anh Thi
ÑH KHTN, Tp HCM
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
1 / 54
Chöông 2
PHÖÔNG PHAÙP ÑEÁM DUØNG HAØM
SINH
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
2 / 54
Noäi dung
Noäi dung
1
Ñònh nghóa haøm sinh
2
3
4
5
6
Heä soá haøm sinh
Phaân hoaïch
Haøm sinh muõ
Phöông phaùp toång
Baøi toaùn ñeä quy
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
3 / 54
Ñònh nghóa haøm sinh
Ñònh nghóa haøm sinh
Ñònh nghóa
Cho {an}n≥0 laø moät daõy caùc soá thöïc, thì chuoãi luõy thöøa hình thöùc
P
A(x) = n≥0 anxn ñöôïc goïi laø haøm sinh thoâng thöôøng (hay haøm sinh) cuûa
daõy {an}n≥0
.
Ví duï
Xeùt taäp hôïp X vôùi m phaàn töû, goïi an laø soá taäp con coù n phaàn töû cuûa X,
ꢀ
ꢁ
m
n
an =
.
Ta ñöôïc haøm sinh cuûa daõy soá thöïc {an}n≥0 laø
ꢀ
ꢁ
ꢀ
ꢁ
ꢀ
ꢁ
n
1
n
2
n
n
A(x) = 1 +
x +
x2 + · · · + · · · +
xn = (1 + x)n
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
4 / 54
Ñònh nghóa haøm sinh
Ñònh nghóa haøm sinh
Ví duï
Tìm haøm sinh cuûa ar, vôùi ar laø soá caùch ñeå choïn r vieân bi töø 3 vieân bi maøu
xanh, 3 vieân bi maøu traéng, 3 vieân bi maøu ñoû, vaø 3 vieân bi maøu vaøng.
Baøi toaùn treân coù theå ñöa veà baøi toaùn tìm nghieäm nguyeân cuûa phöông trình
e1 + e2 + e3 + e4 = r
vôùi 0 ≤ ei ≤ 3. ÔÛ ñaây e1 laø soá quaû caàu maøu xanh ñöôïc choïn, e2 laø soá quaû
caàu maøu traéng, e3 laø soá quaû caàu maøu ñoû, vaø e4 laø soá quaû caàu maøu vaøng.
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
5 / 54
Ñònh nghóa haøm sinh
Ñònh nghóa haøm sinh
Ta xaây döïng moät tích cuûa caùc nhaân töû ña thöùc sao cho sau khi nhaân caùc ña
thöùc ñoù laïi vôùi nhau, ta ñöôïc taát caû caùc haïng töû coù daïng xe1 xe2 xe3 xe4 , trong
ñoù 0 ≤ ei ≤ 3. Nhö vaäy ta caàn 4 nhaân töû, vaø moãi nhaân töû baèng
1 + x + x2 + x3, bao goàm taát caû caùc luõy thöøa nhoû hôn hay baèng 3 cuûa x. Ta
ñöôïc haøm sinh caàn tìm laø
(1 + x + x2 + x3)4 =1 + 4x + 10x2 + 20x3 + 31x4 + 40x5 + 44x6+
+ 31x8 + 40x7 + 20x9 + 10x10 + 4x11 + x12.
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
6 / 54
Ñònh nghóa haøm sinh
Ñònh nghóa haøm sinh
Ví duï
Tìm haøm sinh cuûa {ar}r≥0, vôùi ar laø soá caùch ñeå choïn r quaû töø 6 quaû leâ, 5
quaû cam, 3 quaû chanh, 3 quaû maän.
Giaûi. Töông töï nhö ví duï treân ar laø nghieäm nguyeân cuûa phöông trình
e1 + e2 + e3 + e4 = r
vôùi 0 ≤ e1 ≤ 6, 0 ≤ e2 ≤ 5, 0 ≤ e3 ≤ 3, vaø 0 ≤ e4 ≤ 3. Ñeå tìm haøm sinh
ta xaây döïng moät tích cuûa caùc nhaân töû ña thöùc sao cho sau khi nhaân caùc ña
thöùc ñoù laïi vôùi nhau, ta ñöôïc taát caû caùc haïng töû coù daïng xe11 xe22 x3e3 x4e4 . Caùc
nhaân töû ña thöùc töông öùng laø: 1 + x + x2 + x3 + x4 + x5 + x6,
1+x+x2+x3+x4+x5, 1+x+x2+x3, vaø 1+x+x2+x3. Vaäy haøm sinh caàn tìm laø
(1 + x + x2 + x3 + x4 + x5 + x6)(1 + x + x2 + x3 + x4 + x5)(1 + x + x2 + x3)2.
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
7 / 54
Ñònh nghóa haøm sinh
Ñònh nghóa haøm sinh
Ví duï
Tìm haøm sinh cuûa {ar}r≥0, vôùi ar laø soá caùch chia r ñoàng xu vaøo 5 hoäp vôùi
ñieàu kieän: Soá ñoàng xu ôû hoäp 1 vaø hoäp 2 laø soá chaün vaø khoâng quaù 10, vaø
caùc hoäp coøn laïi chöùa 3 ñeán 5 ñoàng xu.
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
8 / 54
Ñònh nghóa haøm sinh
Ñònh nghóa haøm sinh
Ví duï
Tìm haøm sinh cuûa {ar}r≥0, vôùi ar laø soá caùch chia r ñoàng xu vaøo 5 hoäp vôùi
ñieàu kieän: Soá ñoàng xu ôû hoäp 1 vaø hoäp 2 laø soá chaün vaø khoâng quaù 10, vaø
caùc hoäp coøn laïi chöùa 3 ñeán 5 ñoàng xu.
Giaûi. ar laø soá nghieäm nguyeân cuûa phöông trình
e1 + e2 + e3 + e4 + e5 = r
vôùi e1, e2 chaün, 0 ≤ e1, e2 ≤ 10, vaø 3 ≤ e3, e4, e5 ≤ 5.
Ñeå tìm haøm sinh ta xaây döïng moät tích cuûa caùc nhaân töû ña thöùc sao cho
sau khi nhaân caùc ña thöùc ñoù laïi vôùi nhau, ta ñöôïc taát caû caùc haïng töû coù
daïng xe1 xe2 xe3 xe4 xe5 . Ta ñöôïc nhaân töû ña thöùc töông öùng vôùi e1 vaø e2 laø
(1 + x2 + x4 + x6 + x8 + x10), vaø töông öùng vôùi e3, e4, vaø e5 laø
(x3 + x4 + x5). Haøm sinh caàn tìm laø
(1 + x2 + x4 + x6 + x8 + x10)2(x3 + x4 + x5)3
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
8 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Trong phaàn naøy, chuùng ta seõ söû duïng moät soá kyû thuaät ñeå tính toaùn caùc heä
soá trong haøm sinh. Phöông phaùp chuû yeáu laø ñöa moät haøm sinh phöùc taïp
veà haøm sinh kieåu nhò thöùc hoaëc tích cuûa caùc haøm sinh kieåu nhò thöùc. Ta
caàn söû duïng moät soá khai trieån sau:
Moät soá khai trieån ña thöùc
1 − xm+1
(1)
(2)
= 1 + x + x2 + x3 + · · · + xm
1 − x
1
= 1 + x + x2 + · · ·
1 − x
ꢀ
ꢁ
ꢀ
xm +
ꢁ
ꢀ
ꢁ
ꢀ
ꢁ
ꢁ
n
n
n
r
n
n
(3) (1 + x)n = 1 +
x +
x2 + · · · +
xr + · · · +
xn
1
2
ꢀ
ꢁ
ꢀ
ꢁ
ꢀ
n
n
n
k
(4) (1 − xm)n = 1 −
x2m + · · · + (−1)k
xkm
+
1
xnm
2
ꢀ
ꢁ
n
· · · + (−1)n
n
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
9 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Moät soá khai trieå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
(6) Neáu h(x) = f(x)g(x), vôùi f(x) = a0 + a1x + a2x2 + · · · vaø
g(x) = b0 + b1x + b2x2 + · · · , thì h(x) = a0b0 + (a1b0 + a0b1)x + (a2b0 +
a1b1 + a0b2)x2 + · · · + (arb0 + ar−1b1 + ar−2b2 + · · · + a0br)xr + · · ·
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
10 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Ví duï
Tìm heä soá cuûa x16 trong (x2 + x3 + x4 + · · · )5?
Giaûi. Ta coù
(x2 + x3 + x4 + · · · )5 = [x2(1 + x + x2 + · · · )]5
= x10(1 + x + x2 + · · · )5
1
= x10
(1 − x)5
Ñeå tìm heä soá cuûa x16 trong (x2 + x3 + x4 + · · · )5, ta tìm heä soá cuûa x6 trong
1
1
. Theo khai trieån treân ta ñöôïc heä soá cuûa x6 trong
laø
(1−x)5
(1−x)5
ꢀ
ꢁ
6 + 5 − 1
.
6
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
11 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Ví duï
Tìm soá caùch ñeå laáy 15 ñoàng xu töø 20 ngöôøi sao cho, trong 19 ngöôøi ñaàu
tieân ta coù theå laáy ôû moãi ngöôøi 0 ñoàng hoaëc 1 ñoàng, vaø ngöôøi thöù 20 ta coù
theå laáy 0 ñoàng, hoaëc 1 ñoàng, hoaëc 5 ñoàng?
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
12 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Ví duï
Tìm soá caùch ñeå laáy 15 ñoàng xu töø 20 ngöôøi sao cho, trong 19 ngöôøi ñaàu
tieân ta coù theå laáy ôû moãi ngöôøi 0 ñoàng hoaëc 1 ñoàng, vaø ngöôøi thöù 20 ta coù
theå laáy 0 ñoàng, hoaëc 1 ñoàng, hoaëc 5 ñoàng?
Giaûi. Baøi toaùn treân töông ñöông vôùi baøi toaùn tìm nghieäm nguyeân cuûa
phöông trình
x1 + x2 + · · · + x20 = 15
thoûa ñieàu kieän xi = 0 hoaëc 1 vôùi i = 1, 2, . . . , 19 vaø x20 = 0 hoaëc 1, hoaëc 5.
Ta coù ñöôïc haøm sinh cho baøi toaùn treân laø
(1 + x)19(1 + x + x5)
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
12 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Theo coâng thöùc khai trieån ta coù
ꢀ
ꢁ
ꢀ
ꢁ
ꢀ
ꢁ
19
1
19
2
19
19
(1 + x)19 = 1 +
x +
x2 + · · · + · · · +
x19
Ñaët f(x) = (1 + x)19 vaø g(x) = 1 + x + x5. Goïi ar laø heä soá cuûa xr trong f(x),
ꢀ
ꢁ
19
vaø br laø heä soá cuûa xr trong g(x). Ta thaáy ar =
, vaø
r
b0 = b1 = b5 = 1, caùc bi khaùc baèng 0. Heä soá cuûa x15 trong h(x) = f(x)g(x)
ñöôïc tính bôûi (6) laø,
a15b0 + a14b1 + a13b2 + · · · + a0b15
Thu goïn ta ñöôïc
ꢀ
ꢁ
ꢀ
ꢁ
ꢀ
ꢁ
19
15
19
14
19
10
a15b0 +a14b1 +a10b5 =
×1+
×1+
×1 = 107882.
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
13 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Ví duï
Coù bao nhieâu caùch chia 25 vieân bi vaøo 7 hoäp vôùi ñieàu kieän hoäp thöù nhaát coù
khoâng quaù 10 vieân, caùc hoäp coøn laïi tuøy yù.
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
14 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Ví duï
Coù bao nhieâu caùch chia 25 vieân bi vaøo 7 hoäp vôùi ñieàu kieän hoäp thöù nhaát coù
khoâng quaù 10 vieân, caùc hoäp coøn laïi tuøy yù.
Giaûi. Haøm sinh cuûa daõy {ar}r≥0 vôùi ar laø soá caùch chia r vieân bi vaøo 7 hoäp
vôùi ñieàu kieän nhö ñeà baøi laø:
(1 + x + . . . + x10)(1 + x + x2 + . . . +)6
!
!
6
1 − x11
1 − x
1
=
1 − x
!
7
1
= (1 − x11)
1 − x
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
14 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Theo coâng thöùc (5) ta coù
!
7
ꢀ
ꢁ
ꢀ
ꢁ
1
1 + 7 − 1
r + 7 − 1
= 1 +
x + · · · +
xr + · · ·
1
r
1 − x
!
7
1
Ñaët f(x) = 1 − x11 vaø g(x) =
. Goïi ar laø heä soá cuûa xr trong f(x),
1 − x
vaø br laø heä soá cuûa xr trong g(x). Ta thaáy a0 = 1, a11 = −1, ai = 0 vôùi
ꢀ
ꢁ
r + 7 − 1
i = 0, 11 vaø br =
.
r
Heä soá cuûa x25 trong h(x) = f(x)g(x) ñöôïc tính bôûi (6) laø,
a0b25 + a1b24 + · · · + a25b0
Thu goïn ta ñöôïc
ꢀ
ꢁ
ꢀ
ꢁ
25 + 7 − 1
14 + 7 − 1
a0b25 + a11b14 = 1 ×
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
+ (−1) ×
= 697521
25
14
Baøi giaûng Toaùn toå hôïp
15 / 54
Heä soá haøm sinh
Heä soá haøm sinh
Ví duï
Coù bao nhieâu caùch choïn 25 noùn töø 6 loaïi noùn, vôùi ñieàu kieän moãi loaïi noùn
phaûi ñöôïc choïn töø 1 ñeán 5 caùi.
Ví duï
Cho n laø soá nguyeân döông. Chöùng minh raèng:
ꢀ
ꢁ2
ꢀ
ꢁ2
ꢀ
ꢁ2
ꢀ
ꢁ
n
0
n
1
n
n
2n
n
+
+ · · · +
=
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
16 / 54
Heä soá haøm sinh
Heä soá haøm sinꢁh
ꢀ
2n
Giaûi. Ta coù
laø heä soá cuûa xn trong (1 + x)2n = (1 + x)n(1 + x)n.
n
Ñaët f(x) = (1 + x)n, g(x) = (1 + x)n vaø ar, br laàn löôït laø heä soá cuûa xr trong
ꢀ
ꢁ
n
r
f(x) vaø g(x). Ta coù ar = br =
xn trong f(x)g(x) laø
. AÙp duïng coâng thöùc (6), ta coù heä soá
a0bn + a1bn−1 + · · · + anb0
ꢀ
ꢀ
ꢁ ꢀ
ꢁ2
ꢁ
ꢀ
ꢁ ꢀ
ꢁ
ꢀ
ꢁ ꢀ
ꢁ
n
n
n
n
n
n
n
n
0
=
+
+ · · · +
0
1
n − 1
ꢀ
ꢁ2
ꢀ
ꢁ2
n
0
n
1
n
n
=
+
+ · · · +
.
Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)
Baøi giaûng Toaùn toå hôïp
17 / 54
Tải về để xem bản đầy đủ
58 trang
15/01/2024
6420
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán tổ hợp - Chương 2: Phương pháp đếm dùng hàm sinh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_to_hop_chuong_2_phuong_phap_dem_dung_ham_sinh.pdf
