27/03/2008
1
HÀM SINH VÀ ỨNG DỤNG
Phạm Thế Bảo
Khoa Toán – Tin học
Trường Đại học Khoa học Tự nhiên Tp.HCM
•Bài toán: có 12 trái táo chia cho 03 bạnA,B,C.Theo
qui định: A lấyítnhất04trái,BvàClấyítnhất02trái,
C không lấy quá 05 trái. Vậy, có bao nhiêu cách chia?
Giới thiệu
Giải: gọia,b,clàsốtáo của các bạnA,B,Cđược
chia. Ta có: 12
4
2 (*)
abc
a
b
⎧++=
⎪
⎪
⎪≥
⎪
⎪
⎨
⎪
≥
⎪
Sốcách chia táo chính là sốnghiệmcủaphương trình (*)
52c
≥
⎪
⎪
⎪≥≥
⎪
⎩
Phạm Thế Bảo
27/03/2008
2
•Hay gọi G={a+b+c=12/ a≥4, b ≥2, 5≥c≥2}. Thì
|G|=số lời giải. Ta đặt H={xa+b+c/ a,b,c∈N, xa+b+c = x12,
a≥4, b ≥2, 5≥c ≥2} thì |G|= |H|Æcần tìm |H|Æchính
là hệ số của x12 trong phương trình
f(x)=(x
4
+x
5
+ )(x
2
+x
3
+ )(x
2
++x
5
)
f(x)=(x
+x
+
...
)(x
+x
+
...
)(x
+
...
+x
)
=
Khi k=12 thì a
k
chính là giá trị cần tìm Æmục tiêu
48
2
25
abc k
k
ak
b
c
xax
++
≤≤∞ =
≤≤∞
≤≤
=
∑∑
của bài toán là tìm khai tri
n của f(x).
Phạm Thế Bảo
•Xét chuỗi lũy thừa nếu
Chuỗi lũy thừa
0
n
vôùi a
n
n
n
az C
∞
=
∈
∑
•Cho dãy số {an}∞n=0. Hàm sinh của dãy này là
hỗi
0
()
n
n=0
hoäi tuï veà G(z) thì chuoãi hoäi tuï vaø
G(z)= a
n
k
nk
k
n
Sz az
z
=
∞
=∑
∑
∞
∑
c
h
u
ỗi
.
0
n
n
n
az
=
∑
Phạm Thế Bảo
27/03/2008
3
•Quay lại bài toán chia táo. Thay vì 4≤a≤∞ và
2≤b≤∞ ta cũng có thể viết 4≤a≤8 và 2≤b≤6.
Thì:
865
()
abc
f
⎛⎞⎛⎞⎛⎞
⎜⎟⎜⎟⎜⎟
∑∑∑
422
4 2342 2342 23
8 2342 23
2
54
88524
3
()
(1 ) (1 ) (1 )
(1 ) (1 )
11 1
(
1
)(
1
)
()
=
abc
abc
f
zzzz
zzzzzzzzzzzzzz
z zzzz zzz
zz
zzzz
===
=
⎜⎟⎜⎟⎜⎟
⎝⎠⎝⎠⎝⎠
= ++++ ++++ +++
= ++++ +++
⎛⎞⎛⎞
−−
=
−−
⎜⎟⎜⎟
⎝⎠⎝⎠
∑∑∑
3
()()
11
(
1
)
caàn xaùc ñònh heä soá c
zz z
⎜⎟⎜⎟
−− −
⎝⎠⎝⎠
⇒52 4
3
1
(1 ) (1 ) (1 )
4
uûa z trong zz
z
−−
−
Phạm Thế Bảo
Theo chuỗi lũy thừa ta có:
Nê t ó hệ ố ủ
4
thỗiàlà
2
3
34 2
11 ... ...
12
(1 )
k
k
zz z
k
z
⎛+⎞
⎛⎞ ⎛⎞ ⎛ ⎞
=+ + ++ +
⎜⎟
⎜⎟ ⎜⎟ ⎜ ⎟
−⎝⎠ ⎝⎠ ⎝ ⎠
⎝⎠
Nê
n
t
a c
ó
hệ
s
ố
c
ủ
a z
4
t
rong c
h
u
ỗi
n
à
y
là
Vậy có 14 cách giải bài toán chia táo.
66! 5*6
11114
44!2! 2
⎛⎞
=−= −= −=
⎜⎟
⎝⎠
Phạm Thế Bảo
27/03/2008
4
Tương tự cho bài toán:
Xét tập hợp {1,2, ...,15} có bao nhiêu tập
con có 04 phần tử mà không chứa 02 số liên
tiếp nhau. Vị trí các phền tử trong một tập con
không quan trọng, ví dụ: {4,7,9,12} và
{
9
,
12
,
4
,
7
}
là như nhau.
{, ,,}
Phạm Thế Bảo
Dùng hàm sinh giải hệ thức truy hồi
•Trong quá trình phân tích thuật toán, chúng ta
tì đđộ hứtủth ậtt á là ô
tì
m
đ
ược
độ
p
hứ
c
t
ạp c
ủ
a
th
u
ật
t
o
á
n
là
c
ô
ng
thức truy hồi.Ví dụ:
0
01
1
12
0
005
22 65 0 2
2
hay
n
nn n
nk
k
xaa
naa a n
xx
n
−
−−
=
===
+
−
+=∀≥
=+
∑
•Chúng ta sẽ dùng hàm sinh để tìm nghiệm (độ
phức tạp của thuật toán)
0
k
Phạm Thế Bảo
27/03/2008
5
Hàm sinh của dãy xác suất
•Xét biếnAcóthểlấy các giá trị0, 1, 2, ... Với
á
ấ
là
Với
≥
0
à
hì
1
∞
∑
x
á
csu
ấ
t
là
p0,p
1,p
2,...
Với
pi
≥
0
v
à
t
hì
hàm sinh củadãyxácsuất (phân bố)là
Ví
d
ét
th ật
tá
tì
ố
lớ
hất
t
0
1
k
k
p
=
=
∑
0
() k
k
k
Gz pz
∞
=
=∑
•
Ví
d
ụx
ét
th
u
ật
t
o
á
n
tì
ms
ố
lớ
nn
hất
t
rong
mảng (ví dụ3–phầnđánh giá bằng công cụ
toán họccơbản).
Phạm Thế Bảo
•Có thể thấy độ phức tạp là O(n). Vậy số lần
thực hiện α:
•
Tốithiểu:
0
Tối
thiểu:
0
•Tối đa: n-1
•Trung bình: ?
Nếu xét n=3, dữ liệu là một dãy số đôi một phân biệt
{a[0], a[1], a[0]} Æcó ? tổ hợp thứ tự
vớixácsuất ngang nhau là ?
6
1/6
với
xác
suất
ngang
nhau
là
?
1/6
Phạm Thế Bảo