B® GIÁO DUC VÀ ĐÀO TAO
ĐAI HOC ĐÀ NANG
∗∗∗∗∗¤¤¤∗∗∗∗∗
Đ¾NG THUC ĐOAN
CÁC PHƯƠNG PHÁP ĐEM
TRONG LÝ THUYET TO
HeP
Chuyên ngành: Phương pháp Toán sơ cap
Mã so: 60.46.40
TÓM TAT LU¾N VĂN THAC SĨ KHOA HOC
Đà Nang - 2011
Công trình đưac hoàn thành tai
ĐAI HOC ĐÀ NANG
Ngưài hưáng dan khoa hoc: PGS.TS NGUYEN GIA бNH
Phán bi¾n 1:......................................................................
Phán bi¾n 2:......................................................................
Lu¾n văn se đưoc báo v¾ trưóc H®i đong cham Lu¾n văn tot nghi¾p thac sĩ
khoa hoc hop tai Đai hoc Đà Nang vào ngày .........tháng ............. năm ...............
Có the tìm hieu lu¾n văn tai:
− Trung tâm Thông tin - Hoc li¾u, Đai hoc Đà Nang
− Thư vi¾n trưòng Đai hoc Sư pham, Đai hoc Đà Nang
1
Mé ĐAU
1. Lý do chon đe tài
To hop là m®t lĩnh vuc toán hoc có tư duy ra đòi tn rat sóm.
Hi¾n nay, cùng vói su bùng no và th%nh hành cúa máy tính đi¾n tn,
to hop đã chuyen sang lĩnh vuc toán nng dnng và phát trien manh
me và đưoc áp dnng trong nhieu lĩnh vuc khác nhau: lý thuyet so,
hình hoc hñu han, bieu dien nhóm, đai so không giao hoán, quy
trình ngau nhiên, thong kê xác suat, quy hoach thuc nghi¾m,
v.v... Có bon bài toán to hop cơ bán là bài toán đem, bài toán li¾t
kê, bài toán toi ưu to hop, bài toán ton tai. Trong đó, bài toán đem
là bài toán cơ bán và quan trong nhat. Phương pháp đem đưoc coi
là nen táng cho hau như tat cá các phương pháp khác.
Xuat phát tn nhu cau phát trien cúa lý thuyet to hop, đ¤c bi¾t là
bài toán đem trong lĩnh vuc này, cùng vói nhñng nng dnng cúa
nó, tôi quyet đ%nh chon đe tài "Các phương pháp đem trong lý
thuyet to hop" đe tien hành nghiên cnu. Tôi, dưói su hưóng dan t¤n
tình cúa PGS. TS Nguyen Gia Đ%nh, hy vong tao đưoc m®t tài li¾u
tham kháo tot cho nhñng ngưòi muon tìm hieu ve lý thuyet to hop
và hy vong tìm ra đưoc m®t so ví dn minh hoa đ¤c sac và tính
chat mói nham góp phan làm phong phú thêm các ket quá trong
lĩnh vuc này.
2. Mnc đích nghiên cNu: Mnc tiêu cúa đe tài nham tao đieu ki¾n
cho bán thân có the khám phá và hieu đưoc các nng dnng cúa
phương pháp đem trong giái toán to hop và có the tao đưoc tài
li¾u tham kháo bo ích cho nhñng ngưòi muon tìm hieu ve lĩnh
vuc này.
3. Đoi tưang và pham vi nghiên cNu: Đoi tưong nghiên cnu cúa
đe tài là các phương pháp đem trong lý thuyet to hop và các nng
dnng cúa nó. Pham vi nghiên cnu là Lý thuyet to hop dành cho
chương trình pho thông và nâng cao.
4. Phương pháp nghiên cNu:
− Thu th¤p các bài báo khoa hoc, các giáo trình cúa các tác giá
nghiên
cnu liên quan đen Bài toán đem trong lý thuyet to hop.
2
− Tham gia các buoi seminar hang tuan đe trao đoi các ket quá
đang
nghiên cnu.
5. Ý nghĩa khoa hoc và thNc tien cúa đe tài:
− Tong quan các ket quá cúa các tác giá đã nghiên cnu liên quan
đen
Các phương pháp đem trong lý thuyet to hop.
− Chnng minh chi tiet và làm rõ m®t so m¾nh đe, cũng như đưa ra
m®t
so ví dn minh hoa đ¤c sac nham làm cho ngưòi đoc de dàng tiep c¤n
van đe đưoc đe c¤p.
6. Cau trúc cúa lu¾n văn:
− Trong Chương 1, tôi se trình bày chi tiet các nguyên lý đem cơ
bán,
nguyên lý Dirichlet, m®t so bài toán đem cơ bán và m®t vài ví dn
nng
dnng minh hoa.
− Trong Chương 2, tôi se đe c¤p tói chuoi lũy thna hình thnc, các
toán
tn trong CN, phép truy hoi trong CN, các phương pháp đem dùng
hàm
sinh: hàm sinh thông thưòng và hàm sinh mũ.
− Trong Chương 3, tôi se đe c¤p tói nguyên lý bù trn và phương
pháp
đem bang công thnc ngh%ch đáo. Ngoài ra còn đe c¤p đen m®t so ky
thu¤t như: tính tong bang tích phân hñu han, xác đ%nh h¾ thnc
trong các dãy so bang phiem hàm tuyen tính.
Chương 1
NGUYÊN LÝ ĐEM VÀ BÀI TOÁN ĐEM CƠ BÁN
1.1 Khái quát ve to hap
1.2 NhÑng nguyên lý đem cơ bán
Đ%nh nghĩa 1. Khi hai công vi¾c có the đưoc làm đong thòi, ta
không the dùng quy tac c®ng hay quy tac nhân đe tính so cách
thnc hi¾n nhi¾m vn gom cá hai vi¾c. Đe tính đúng so cách thnc
hi¾n nhi¾m vn này, ta c®ng so cách làm moi m®t trong hai vi¾c
roi trù đi so cách làm đong thòi cá hai vi¾c. Ta có the phát bieu
nguyên lý đem này bang ngôn ngu t¾p hop.
Cho k t¾p huu han A1, A2, ..., Ak, ta có:
| A1 ∪ A2 ∪ ... ∪ Ak |= N1 − N2 + N3 − · · · + (−1)k−1Nk,
trong đó
Nm =
.
|Ai1 ∩
1™i1 n.
M¾nh đe 4. So to hop l¾p ch¾p k cúa t¾p n phan tú là C k
.
n+k−1
Đ%nh nghĩa 5. Cho A là m®t t¾p huu han n phan tú, trong đó có
n1 phan tú như nhau thu®c loai 1, n2 phan tú như nhau thu®c
loai 2,..., nk phan tú như nhau thu®c loai k sao cho n1 + n2 + · ·
· + nk = n
và khi hoán v% các phan tú cùng loai không sinh ra cau hình to
hop mói. M®t hoán v% các phan tú cúa A đưoc goi là m®t hoán v
% l¾p theo tham so l¾p n1, n2, ..., nk.
M¾nh đe 5. So hoán v% l¾p cúa t¾p n phan tú theo tham so n1, n2,
..., nk
là
n!
.
n1 !
n2!...nk!
Ví dn 4. Phương trình x1 +x2 +x3 = 10 có bao nhiêu nghi¾m
nguyên không âm?
Moi nghi¾m cúa phương trình tương nng vói m®t cách chon 10
phan tn tn m®t t¤p có 3 loai, sao cho có x1 phan tn loai 1, x2 phan
tn loai 2 và x3 phan tn loai 3. Như v¤y, so nghi¾m nguyên không âm
cúa phương trình tương nng vói to hop l¤p ch¤p 10 cúa t¤p có 3
phan tn. V¤y so nghi¾m nguyên không âm cúa phương trình trên
là:
C 10
3+10−1
=
10
2
= C12 = C12
12.11
= 66.
1.2
Đ%nh nghĩa 6. So tat cá các phân hoach thành k khoi cúa
m®t t¾p hop n phan tú đưoc goi là so Stirling loai hai và đưoc ký
hi¾u là S(n, k). De thay rang S(n, k) = 0 neu k > n. Ta cũng
quy ưóc S(n, 0) = 0.
So Tn = S(n, 1) + S(n, 2) + ... + S(n, n) đưoc goi là so
Bell. Như v¾y, so Bell chính là so tat cá các phân hoach cúa t¾p
hop n phan tú.
Trong Chương 2, ta se tìm công thnc cho so Stirling loai hai:
S(n, k) =
1 ..
( 1)k−j
.
j n
−
C j . k!
k
k
j=0
M¾nh đe 6. S(n + 1, k) = kS(n, k) + S(n, k − 1).
Chương 2
PHƯƠNG PHÁP ĐEM DÙNG HÀM SINH
2.1 Chuoi lũy thNa hình thNc
Đ%nh nghĩa 7. Vói t¾p so tn nhiên N và t¾p hop so phúc C, ký
hi¾u
CN là t¾p hop tat cá các ánh xa tù N vào C. Moi phan tú a ∗ CN
có
the bieu dien dưói dang: a = a(x) = j=0 ajxj, trong đó, aj =
.∞
a(j)
vói moi j ∗ N và goi đó là chuoi lũy thùa hình thúc cúa a(x).
Giá sú a(x)
=
∞
.a
j
∞
j
x và b(x) .b
=
j
xj là hai chuoi lũy thùa
hình
j=0
j=0
thúc bat kỳ. Ta đ%nh nghĩa phép c®ng, phép nhân trong CN và
phép nhân vô hưóng m®t so z ∗ C vói phan tú cúa CN như sau:
∞ .
∞
. ∞
.
j
j
a(x) + b(x) =
a jx +
bjx = (aj + bj
)xj
j=0
∞
a(x)b(x) = (
. .
(
akb j
.
j=0
j=0
∞
. ∞ j
ajxj )( bjxj ) =
j=0
j=0
∞
za(x) = z(
j=0
.
−k)x
j
j=0 k=0
∞
.
ajx ) = (zaj )xj
j
j=0
CN là m®t không gian vectơ trên trưòng C vói phép c®ng và phép
nhân vô hưóng, CN là m®t vành giao hoán có đơn v% vói phan tn đơn
v%
.∞ j
0x . Và z[a(x)b(x)] = [za(x)]b(x) = a(x)
là 1(x) =
[zb(x)].
1+
j=1
Đ%nh lý 1. T¾p CN vói phép c®ng, phép nhân và phép nhân vô
hưóng l¾p thành m®t đai so giao hoán trên C
M¾nh đe 7. Chuoi a(x) ∗ CN là khá ngh%ch khi và chs khi a0 ƒ=
0.
Neu a(x) là phan tn khá ngh%ch trong CN thì phan tn ngh%ch đáo
cúa
nó se đưoc ký hi¾u là (a(x))−1 hay hay a−1(x). Vói moi a(x) ∗
1
N
a(x) C
ta đ%nh nghĩa
vói moi so nguyên dương n.
a0(x) = 1, an(x) = a(x)a(x) ·
· · a(x)
s
n¸l¸an
x
Neu a(x) là khá ngh%ch thì ta đ%nh nghĩa
a−n(x) = a−1(x)a−1(x) · · ·
vói moi so nguyên dương n.
a−1(x)
s
n¸l¸an
x
M¾nh đe 8. Vói moi z ∗ C và 0 ƒ= n, k ∗ N, ta có
.
1
zjxnj ;
(2)
= ∞
(1)
.
1
z jxnj.
j
=
∞
C
k+j−1
(1 −
1−
j=1
j=1
zxn)k
zxn
.∞
ajxj vói a0 = 1 và n là m®t so
M¾nh đe 9. Giá sú a(x)
nguyên
=
j=0
dương bat kỳ. Khi đó, ton tai duy nhat b(x)
=
∞
.
bj xj vói b0 = 1
sao
j=0
cho bn(x) = a(x).
∞
.
a j xj vói a0 = 1 và n là
m®t
M¾nh đe 10. Giá sú a(x)
=
j=0
so nguyên dương bat kỳ. Khi đó, (a−1(x))n = (an(x))−1 và do
đó
a−n(x) = (an(x))−1.
M¾nh đe 11. Giá sú a(x)
=
.
xj vói a0 = 1, m là m®t so
nguyên
a
∞ j
j=0
và n là m®t so nguyên dương bat kỳ. Khi đó, ton tai duy nhat m®t
.∞ j
bjx vói b0 = 1 sao cho bn(x) = am(x).
b(x)
j=0
=
Chuoi b(x) ton tai duy nhat trong M¾nh đe 11 đưoc ký hi¾u là
am/n(x).
Đ%nh nghĩa 8. Giá sú c1(x), c2(x), . . . , ck(x), . . . là m®t dãy các
phan
.∞
N
cjkxj và c0k = 0, k = 1, 2, .... Khi
tú cúa C vói ck(x)
đó,
=
j=0
dãy 1 + c1(x), 1 + c2(x), . . . , 1 + ck(x), . . . đưoc goi là khá
tích neu vói moi j
“ 0 ton tai so
nguyên dương N
= N (j) sao cho
vói
n
Q
j
moi n > N h¾ so cúa x
(1 + ck(x)) đeu bang nhau.
trong
Neu
k=1
c1(x), c2(x), . . . , ck(x), . . . là m®t dãy khá tích thì ta có the đ%nh
nghĩa
tích
∞
∞
Y
Y
(1 + ck(x)) =
s j x j ∗ CN
k=1
j=0
trong đó h¾ so sj cúa xj trong tích này chính là h¾ so cúa xj trong
tích
n
Y
(1 + ck(x)) vói n > N.
∞
.
k=1
ajk xj , k =
Dãy a1(x), a2(x), . . . , ak(x), . . . các phan tú
ak(x) =
j=0
1, 2, ... trong CN đưoc goi là khá tong neu vói moi so nguyên r “
0 ton tai so nguyên dương N = N (r) sao cho vói moi n > N
ta có a0n = a1n = ... = arn = 0. Neu dãy a1(x), a2(x), . . . ,
∞
∞
ak(x), . . . là khá
.
.
tong thì đoi vói dãy này, ta có the đ%nh nghĩa
s j x j,
tong
ak(x) =
j=0
k=1
ó đây sj = aj1 + aj2 + ... + ajN
.
.∞
Đ%nh nghĩa 9. Giá sú b(x)
bjxj ∗ CN vói b0 = 0, còn a(x) =
j=0
=
.
∞ aj
∗ CN là m®t phan tú bat kỳ. Khi đó,
.∞ (bj (x)) ∗ CN
xj
j=0
chuoi
ja
=0
j
đưoc goi là hop thành cúa a(x) vói b(x) và đưoc ký hi¾u là a(x)
◦ b(x).
2.2
Các toán tN trong CN
Đ%nh nghĩa 10.
N
N
Ánh xa D : C → C :
.a
∞
a(x) =
j
j=0
j
j
x ›→ D(a(x)) =
.
∞
(j +
b(x) =
N
j=0
1) aj+1x đưoc goi là toán tú đao hàm trong C . Ta cũng đ%nh nghĩa:
D0(a(x)) = a(x), Dn(a(x)) = D(Dn−1(a(x))), cho moi so
nguyên
dương n và S(a(x)) = a0.
M¾nh đe 12.
(1) D(a(x) + b(x)) = D(a(x)) + D(b(x)).
(2) D(a(x)b(x)) = D(a(x))b(x) + a(x)D(b(x)).
(3) D(an(x)) = nan−1(x)D(a(x)) cho moi n nguyên dương.
(4) Neu a(x) khá ngh%ch thì D(a−n(x)) = −na−n−1(x)D(a(x))
cho m
(5) Vói moi so huu tý s và moi a(x) ∗ CN thóa mãn
S(a(x)) = 1, ta có D(as(x)) = sas−1(x)D(a(x)).
(6)
Vói moi n ∗ N,
Dn(a(x)) =
.
(j+n)!
j
∞
j! aj+nx .
j=0
(7)
Vói moi a(x) ∗ CN, ta có
a(x) =
.
j
∞
S(Dj (a(x))) x ,
j!
j=0
(8) Neu a1(x), a2(x), ..., ak(x), ... là dãy khá tong,
.
thì D(
.
∞
ak (x))
=
k=1
(x)
∞ D(a
k ).
k=1
Tính chat (7) có the xem như là phân tích MacLaurin cúa a(x).
Đ%nh nghĩa 11. Ánh xa
∞
N
D∗ : CN → C. a(x) =
:
D∗(a(x)) =
.
∞
ajxj ›→
j=0
aj −1
j
j x
j=1
đưoc goi là toán tú tích phân trong
CN.
.∞
bjxj, và a(x) = 1 + b(x). Khi
Đ%nh nghĩa 12. Giá sú b(x)
đó
=
j=1
logarit L(a(x)) cúa a(x) đưoc xác đ%nh bang đang thúc
L(a(x)) = L(1 + b(x)) =
. ∞
(−1)k−1
k=1
k
bk(x).
M¾nh đe 13. Giá sú a(x), c(x) ∗ CN thóa mãn S(a(x)) = S(c(x))
=
1. Khi đó,
(1)D(L(a(x)) D(a(x
))
,
) =
a(x)
(2)L(a(x)c(x)) = L(a(x)) + L(c(x)),
(3) Vói moi so huu tý r, ta có L(ar(x)) = rL(a(x)),
(4) Neu L(a(x)) = L(b(x)), thì a(x) = b(x),
(5) Neu b(x) ∗ CN thóa mãn S(b(x)) = 0, thì vói moi so huu tý r
ta
có:
r
∞
(1 + b(x)) = 1 +
(x)
r
j=1
.
C jb j = r(r − 1)...(r j + 1)
.
vói
Cj
r
j!
Đ%nh nghĩa 13. Giá sú b(x)
=
.b
∞
j
xj. Khi đó, mũ E(b(x)) cúa
b(x)
j=1
đưoc xác đ%nh bang đang thúc
E(b(x)) =
1 j
b
j! (x)
∞
b0
.
vói (x) = 1.
j=0
M¾nh đe 14. Giá sú b(x), c(x) ∗ CN thóa mãn S(b(x)) =
S(c(x)) =
0. Khi đó:
(1) D(E(b(x))) = E(b(x))D(b(x));
(2) Neu E(b(x)) = E(c(x)) thì b(x) = c(x),
(3) L(E(b(x))) = b(x), E(L(1 + b(x))) = 1 + b(x),
(4) E(b(x) + c(x)) = E(b(x))E(c(x)).
.∞
Đ%nh nghĩa 14. Giá sú a(x)
ajxj vói a0 = 1 và r ∗ C là
=
m®t
j=0
so phúc bat kỳ. Khi đó, ta đ%nh nghĩa ar(x) là chuoi lũy thùa
hình thúc E(rL(a(x))).
M¾nh đe 15. Giá sú a(x) ∗ CN thóa mãn S(a(x)) = 1 và r, s
∗ C. Khi đó,
(1) ar(x)as(x) = ar+s(x);
(2) D(ar(x)) = rar−1(x)D(a(x));
(3) L(ar(x)) = rL(a(x));
(4) Neu b(x) ∗ CN thóa mãn S(b(x)) = 0, thì
.
∞
r
(1 + b(x)) = 1 +
C jb j
= r(r − 1)...(r j + 1)
.
(x)
vói
Cj
r
r
j!
j=1
Đ%nh nghĩa 15. Giá sú a(x) ∗ CN và S(a(x)) = 0, túc là
.
a(x) =
∞
j
j=1 a jx . Khi đó, ta đ%nh nghĩa
- Xem thêm -