Tổng Quát Và ứng Dụng Nguyên Lý Bù Trừ - Tài Liệu đại Học

Tài liệu đại học Toggle navigation

• Miễn phí (current)
• Danh mục
  • Khoa học kỹ thuật
  • Công nghệ thông tin
  • Kinh tế, Tài chính, Kế toán
  • Văn hóa, Xã hội
  • Ngoại ngữ
  • Văn học, Báo chí
  • Kiến trúc, xây dựng
  • Sư phạm
  • Khoa học Tự nhiên
  • Luật
  • Y Dược, Công nghệ thực phẩm
  • Nông Lâm Thủy sản
  • Ôn thi Đại học, THPT
  • Đại cương
  • Tài liệu khác
  • Luận văn tổng hợp
  • Nông Lâm
  • Nông nghiệp
  • Luận văn luận án
  • Văn mẫu
• Luận văn tổng hợp

1. Home
2. Luận văn tổng hợp
3. tổng quát và ứng dụng nguyên lý bù trừ

Trich dan tổng quát và ứng dụng nguyên lý bù trừ - Pdf 13

Đề tàiNGUYÊN LÝ BÙ TRỪ TỔNG QUÁT & ỨNG DỤNGNHÓM 8STT Họ tên Công việc (theo mục lục)Chữ ký Nhận xét củagiáo viên1 Lê Diêm HùngChương 1: Đại cương về tổ hợp2 Hồ Thị Mộng Điệp Chương 2: Lý thuyết bù trừ3 Đào Thị Anh Thư Chương 3: Ứng dụng4 Nguyễn Thị Phương AnhChương 3: Ứng dụng và báocáoMỤC LỤC1Chương 1. Đại cương về tổ hợp …………………………………………………31.1. Bài toán tổ hợp…………………………………… ……………………….31.2. Các cấu hình tổ hợp cơ bản…………………………………………………41.3. Các cấu hình tổ hợp mở rộng………………………… ………………… 4Chương 2. Nguyên lý bù trừ tổng quát……………………….…………………62.1. Nguyên lý bù trừ……………………………………… ………………… 62.2. Phân hoạch tập hợp, số sterling loại 2 và số bell………….……………… 62.3. Tổ hợp lặp tổng quát…………………………… …… …………………72.4. Nguyên lý bù trừ tổng quát……………………… ……………………… 7Chương 3. Ứng dụng của nguyên lý bù trừ……………….…………………….93.1. Bài toán đếm số sinh viên…………… ……… …………………………103.2. Bài toán đếm số nghiệm nguyên không âm nhỏ hơn một số của một phươngtrình………………………….…………………………………………….133.2.1. Bài toán 1……………… ………………….…………………………… 13 được mô tả bằng các quy tắc sắp xếp và A1, A2, …, An là các điềukiện ràng buộc lên mỗi sắp xếp theo sơ đồ S. Khi đó mỗi cách sắp xếp các phần tửcủa A1, A2, …, An thỏa mãn các điều kiện R1, R2, …, Rm gọi là một cấu hình tổhợp trên các tập A1, A2, …, An.Trong tổ hợp người ta thường gặp 4 dạng bài toán sau:Bài toán tồn tại1.3. Các cấu hình tổ hợp mở rộng1.3.1. Hoán vị lặpĐịnh nghĩa 1.6. Hoán vị lặp là hoán vị mà trong đó mỗi phần tử được ấnđịnh một số lần lặp lại cho trước.Định lý 1.5. Số hoán vị lặp của k phần tử khác nhau, trong đó phần tử thứ nhất lặpn1 lần, phần tử thứ 2 lặp n2 lần, …, phần tử thứ k lặp nk lần là!! !!), ,,(2121kknnnnnnnP =với n = n1 + n2 +… +nk4Định lý 1.6. Số cách phân phối n đồ vật khác nhau vào k hộp khác nhau sao cho2,…,nk thoả n1 + n2 +… +nk = r. Số các phân hoạch thứ tự tổ hợp chập r của X dạng {S1, S2,…,Sk}có |S1| = n1, |S2| = n2,…, |Sk| = nk được ký hiệu là C(n, npk = n. Một hệ thống các tập con của X gồm p1 tập có n1 phần tử, p2 tập có n2 phần tử, …, pk tập có nk phần tử gọi là phân hoạch không thứ tự của X.Định lý 1.9. Số phân hoạch không thứ tự của X với p1 tập có n1 phần tử, p2 tập có n2 phần tử, …, pk tập có nk,…,nk ) số n1 lặp lại p1 lần, số n2 lặp lại p2 lần, …,số nk lặp lại pk lần).5CHƯƠNG 2NGUYÊN LÝ BÙ TRỪ TỔNG QUÁT2.1. Nguyên lý bù trừĐơn giản Cho hai tập A,B. Có |A∪B|=|A|+|B|-|A∩B| (Công thức 1)Cho ba tập A,B,C. Có |A∪B∪C| = |A|+|B|+|C| -|A∩B|-|A∩C|-|B∩C| +|A∩B∩C|Định lý 2.1. (Nguyên lý bù trừ) Cho X1, X2,…, XnniiiiiikkXXX 12121| | (Công thức 2) Trong tổng X(n,k), bộ (i1,i2,…,ik) lấy tất cả các tổ hợp chập k của n và như vậyX(n,k) là tổng của C(n,k) số hạng.Hệ quả 2.1. (Công thức Sieve) ∑=−=∩∩∩nkknknXXXX021),()1(| |, B2, …, Bk ta thấy một phân bố như vậy sẽ sinh k! toàn ánh từ tập X vào tập { B1, B2, …, Bk}. Suy ra ∑=−−=krnrrkrkCknSk0)).(,()1(),(!nên ∑=−−=krnrrkrkCtử thứ i lặp lại không quá ki lần (i=1,2,…,n) với k1 + k2 + …+kn ≥ k là( )( )∑ ∑= ≤<<≤−+++−+−−+−+=nm niiiimnknmkiiiaaa , ,,21và n(kiiiaaa , ,,21)=|kiiiX, ,,21|Tiếp theo, ký hiệu s0 = |X|, sk = mkaaanmiiiiiikk, ,2,1,), ,,( 12121aaa , ,,21, xét tập kiiiX, ,,21.Trên tập kiiiX, ,,21 ta có (m – k) tính chất αj, j ϵ J = {1,2,…,m}\{i1, i2, …, ik}7Kí hiệu kiiie, ,,iiiX, ,,21| x thỏa tính chất αj },∀j ϵ JTheo công thức ∑=−=∩∩∩nkknknXXXX021),()1( Trong đó: X(n,0) = |X| Và nkXXXknXniiikiik, ,1 ),( 1JjjkmJjjjjJjjiiiJjjiiiaanaanannYYYYXYe−−⊂∈∈−⊂∈∈−+−+−=−+−∩+−==∑∑∑∑αααααααααααSuy ra { } 12 1, ,,1111 212111111121−−+−+++−=−+−+−==−++≤<<≤−≤<<≤ ⊂≤<<≤ ∈≤<<≤≤<<≤∑∑ ∑∑ ∑∑∑−αααααααααααĐịnh lý 2.3. fk = s = sk – C(k+1,1).sk+1 + C(k+2,2).sk+2 - … + (-1)m-kC(m,m-k).sm + sk+1 - C(k+1,1).sk+2 + C(k+2,2).sk+3 - … + (-1)m-k-1C(m-1,m-k-1).sm= sk – C(k,1).sk+1 + C(k+1,2).sk+2 - … + (-1)m-kC(m-1,m-k).siniiXXXXXX1111 ====−=⇒+= nên niinnjijiniiniiniiniiXXXXXXXXX1a. Hãy tính số sinh viên của khóa họcb. Tính số sinh viên chỉ học đúng 1, 2, 3 ngoại ngữc. Tính số sinh viên học ít nhất 1, 2, 3 ngoại ngữGiảiGọi N là tổng số sinh viên của khóa họcKhi đó, |X| = N Kí hiệu: XA là số sinh viên học A, XB là số sinh viên học B, XC là số sinh viên học C, XD là số sinh viên học DTa có tập X có 4 tập con XA, XB, XC, XDTrong đó, theo đề ta có|XA| = 12 ; |X|= 3| XA∩ XB∩XC| = 3; | XA∩ XB∩XD| = 2 ; | XB∩ XC∩XD| = 2 ; | XA∩ XC∩XD| = 3| XA∩ X∪XC∪XD |=> |X| = | ͞XA∩ ͞͞XB∩ ͞XC∩ ͞XD| + | XA∪ XB∪XC∪XD | = 71 + | XA∪ XB∪XC∪XD |(*)= X(4,1) - X(4,2) + X(4,3) - X(4,4)= s1 – s2 + s3 – s4(*) => |X| = 71 + s1 – s2 + s3 – s4Màs1 = X(4,1) = |XA| + |XB| + |XC| + |XD| = 12 + 20 + 20 + 8 = 60sA∩ XB∩XC|+ | XA∩ XB∩XD| + | XB∩ XC∩XD| + | XA∩XC∩XD| = 3 + 2 + 2 + 3 = 10s4 = X(4,4) = | XAm• Số sinh viên chỉ học đúng 1 ngoại ngữ k= 1e1 = s1 – C(1+1,1).s1+1 + C(1+2,2).s1+2 – C(1+3,3).s1+3= s1 – C(2,1).s2 + C(3,2).s3 – C(4,3).s4= 60 – C(2,1).39 + C(3,2).10 – C(4,3).2 = 4• Số sinh viên chỉ học đúng 2 ngoại ngữ k= 211e2 = s2 – C(2+1,1).s2+1k = sk – C(k,1).sk+1 + C(k+1,2).sk+2 - … + (-1)m-kC(m-1,m-k).sm• Số sinh viên học ít nhất 1ngoại ngữ k=1f1 = s1 – C(1,1).s1+1 + C(1+1,2).s1+2 – C(1+2,3).s1+3= s1 – C(1,1).s2 + C(2,2).s3 – C(3,3).s43 – C(3,1).s4 = 10 – C(3,1).2 = 43.2. Bài toán đếm số nghiệm nguyên không âm nhỏ hơn một số của mộtphương trình123.2.1. Bài toán 1: Phương trình x1 + x2 +x3 =11 có bao nhiêu nghiệm nguyên không âm thoả mãn x1 ≤ 3, x2 ≤ 4, x3 ≤ 6?Giải.Gọi A, A1, A2 và A3 3| = CR(3,4) = C(6,2) = 15, |A1∩A2| = CR(3,2) = C(4,2) = 6, |A1∩A3| = CR(3,0) = C(2,2) = 1, |A2∩A3| = 0 |A1∩A2∩A3| = 0 Vậy, theo nguyên lý bù trừ, số nghiệm nguyên không âm của phương trìnhtrên sao cho | ͞A1∩ ͞͞A2∩ ͞AA(3,2) + (-1)3-1A(3,3) = A(3,1) - A(3,2) + A(3,3) = s1 – s2 + s3 Mà13s1 = A(3,1) = |A1| + |A2| + |A3| = 36 + 28 + 15 = 79s2 = A(3,2) = |A1∩A2| + |A1 | = |A| - (s1 – s2 + s3 ) = 78 – (79 – 7 + 0 )= 63.2.1. Bài toán 2: Cho phương trình x1 + x2 + x3 + x4 = 29 có bao nhiêu nghiệm nguyên không âm thoả mãn x1 < 4, x2 < 13, x3 < 6, x4 < 11? Giải.Gọi A là tập tất cả các nghiệm nguyên không âm của phương trình Ai phần tử loại i với i = 1,2,3,4 trong đó có ít nhất 4 phần tử loại một. Vì thế, đầu tiên chọn 4 phần tử loại một rồi chọn thêm 25 phần tử nữa nên |A1| = CR(4,25) = C(25+4-1,4-1) = C(28,3) = 3276. Tương tự, ta có |A2| = CR(4,16)= C(19,3) = 969, |A3| = CR(4,23) = C(26,3)= 2600, |A4| = CR(4,18) = C(21,3)=133014Mặt khác, x1 + x2 ≥ 4 + 13 = 17 có nghĩa chọn 17 phần tử loại một và hai, chọn thêm 29 – 17 = 12 phần tử nữa nên ta có |A1∩A2| = CR(4,12)= C(15,3)= 455Tương tự ta có |A1∩A1∩A2∩A4| = CR(4,1)= C(4,3)= 4, |A2∩A3∩A4| =0, | A1∩ A3∩A4|= CR(4,8)=C(11,3) = 165, |A1∩A2∩A3∩A4| = 0Vậy, theo nguyên lý bù trừ, số nghiệm nguyên không âm của phương trình trênsao cho | ͞A11),4()1(kkkA= (-1)1-1A(4,1) + (-1)2-1A(4,2) + (-1)3-1A(4,3) + (-1)4-1A(4,4) = A(4,1) - A(4,2) + A(4,3) - A(4,4)= s1 – s2 + s3 – s4Màs1 = A(4,1) = |A1| + |A∩A4| = 455 + 1540 + 680 + 286 + 56 + 455 = 3472s3= A(4,3) = | A1∩ A2∩A3| + | A1∩ A2∩A4| + | A2∩ A3∩A4| + | A1∩ A3∩A44 | = |A| - (s1 – s2 + s3 – s4) 15= 4960 – (8175 – 3472 + 253 – 0)= 43.3. Ứng dụng nguyên lý bừ trừ tổng quát để tính hàm trọng lượngĐịnh nghĩa 3.2. Một hàm ω từ một tập X vào tập số thực được gọi là hàm trọnglượng của X. Nếu X là hữu hạn và A là một tập con của X thì trọng lượng của A, kíhiệu là ω(A), là tổng tất cả ω(x) với x ϵ A. Nếu ∏ là tập có m tính chất, Aj với j = 0,1,…,m là tập tất cả các phần tử trong Xthỏa mãn đúng j tính chất và Bj với j=1,2,…,m là tập tất cả các phần tử trong Xthỏa mãn ít nhất j tính chất. Với mỗi j, đặt Ej = ω(Aj) và Fj = ω(BmĐịnh lý 3.3. Với mọi j=1,…,mta có Fj = Sj – C(j,1).Sj+1+ C(j+1,1).Sj+2-…+ (-1)m-jC(m-1,m-j).Sm 16KẾT LUẬNTừ các ứng dụng của nguyên lý bù trừ ta có thể giải lớp các bàitoán. Bằng cách thay đổi các tập hợp, số lượng các phần tử của tập hợp và quan hệgiữa các phần tử ta có thể tạo ra nhiều bài toán khác nhau mà việc giải chúng giúpcho ta có thể củng cố và rèn luyện việc sử dụng linh hoạt các cấu hình tổ hợp cơbản và mở rộng.17TÀI LIỆU THAM KHẢO• Tiếng Việt[1] Trần Quốc Chiến (2005), Giáo trình lý thuyết tổ hợp. (Giáo trình cho học viên cao học Toán, ĐHĐN.)[2] Hà Văn Chương (2004), Tuyển chọn 351 bài toán giải tích tổ hợp, NXB Đại học quốc gia TP Hồ Chí Minh. [3] Vũ Đình Hoà (2003), Lý thuyết tổ hợp và các bài toán ứng dụng, NXB Giáo dục. [4] Nguyễn Ngọc Thu (2003), Hướng dẫn giải toán tổ hợp, NXB Đại học Tải File Word Nhờ tải bản gốc Tài liệu, ebook tham khảo khác

• nguyên lý bù trừ tổng quát và ướng dụng trong tổ hợp
• tổng quát và ứng dụng nguyên lý bù trừ
• Các bài toán tựa cân bằng tổng quát và ứng dụng
• Giáo trình hình thành phân đoạn ứng dụng nguyên lý thị trường phát triển ở trình độ cao p1
• Giáo trình hình thành phân đoạn ứng dụng nguyên lý thị trường phát triển ở trình độ cao p2 pot
• Giáo trình hình thành phân đoạn ứng dụng nguyên lý thị trường phát triển ở trình độ cao p3 doc
• Giáo trình hình thành phân đoạn ứng dụng nguyên lý thị trường phát triển ở trình độ cao p4 doc
• Giáo trình hình thành phân đoạn ứng dụng nguyên lý thị trường phát triển ở trình độ cao p5
• Giáo trình hình thành phân đoạn ứng dụng nguyên lý thị trường phát triển ở trình độ cao p6
• Giáo trình hình thành phân đoạn ứng dụng nguyên lý thị trường phát triển ở trình độ cao p7 potx
• Nghiên cứu những mâu thuẫn chủ yếu trong việc phát triển kinh tế hàng hoá nhiều thành phần ở nước ta hiện nay và giải pháp giải quyết những mâu thuẫn đó
• Các giải pháp cơ bản nhằm đẩy nhanh quá trình hình thành các công ty cổ phần ở nước ta, và để nâng cao vai trò của công ty cổ phần trong phát triển kinh tế Việt Nam thời gian tới
• Một số giải pháp thúc đẩy phát triển công nghệ chế biến nông sản trong sự nghiệp công nghiệp hóa, hiện đại hóa ở nước ta hiện nay
• Một số giải pháp cơ bản trong việc áp dụng chính sách kinh tế mới với công cuộc đổi mới ở Việt Nam
• Vai trò của nhà nước trong nền kinh tế
• Đề án Một số kiến nghị nhằm nâng cao hiệu quả phân phối sản phẩm bánh kẹo Kinh Đô
• Tích luỹ tư bản trong việc quản lí các doanh nghiệp thuộc các thành phần kinh tế ở nước ta
• Lý luận về tích luỹ tư bản và vận dụng vào thực tiễn của Việt Nam
• Đề án Một số luận cứ khoa học cho việc nâng cao hiệu quả đầu tư phát triển trong doanh nghiệp
• Sự vận dụng lý luận của Lê Nin về chủ nghĩa tư bản nhà nước ở Việt Nam

Hệ thống tự động tổng hợp link tải tài liệu, ebook miễn phí cho các bạn sinh viên tham khảo.

Học thêm

• Nhờ tải tài liệu
• Từ điển Nhật Việt online
• Từ điển Hàn Việt online
• Văn mẫu tuyển chọn
• Tài liệu Cao học
• Tài liệu tham khảo
• Truyện Tiếng Anh

Music ♫

Copyright: Tài liệu đại học ©

Top