Đăng ký Đăng nhập
Trang chủ Các phương pháp đếm trong lý thuyết tổ hợp....

Tài liệu Các phương pháp đếm trong lý thuyết tổ hợp.

.DOCX
41
15
143

Mô tả:

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 -

Tài liệu liên quan