- BÁO CÁO THẢO LUẬNMôn học :Toán rời rạcChủ đề: Chỉnh hợp và tổ hợp suy rộng. - Các sinh viên: 1. - Nguyễn Xuân Trường 3 Lời mở đầu Lý thuyết tổ hợp là 1 phần quan trọng của toán rời rạc chuyên nghiên cứu sựphân bố các phần tử vào các tập hợp.Thông thường các phần tử này là hữu hạnvà việc phân bố chúng phải thỏa mãn những điều kiện nhất định nào đó tùy theoyêu cầu của bài toán cần nghiên cứu.Mỗi cách phân bố như thế gọi là một cấuhình tổ hợp.Chủ đề này đã được nghiên cứu vào thế kỉ 17,khi những câu hỏi về tổhợp được đưa ra trong các công trình nghiên cứu hay các trò chơi may rủi.Liệtkê,đếm các đối tượng có những tính chất nào đólaf một phần quan trọng của lýthuyết tổ hợp.Chúng ta cần phải đếm các đối tượng để giải nhiều bài toán khácnhau.Hơn nữa các kĩ thuật đếm được dùng rất nhiều khi tính xác suất của cácbiến cố hay trong đánh giá độ phức tạp của thuật toán. - Trong bài báo cáo này chúng tôi sẽ trình bày các nội dung cơ bản về chỉnh hợpvà tổ hợp suy rộng cùng với các vấn đề liên quan . - Cung cấp kiến thức cơ bản về hoán vị, tổ hợp và chỉnh hợp suy rộng • Minh họa thuật toán liệt kê các hoán vị của các kí tự trong một xâu cho trước. - Dù đã rất cố gắng nhưng với thời gian hạn chế chắc chắn báo cáo này vẫn cònrất nhiều thiếu sót, rất mong nhận được sự góp ý của thầy cô và các bạn.Nhóm các sinh viên Thanh, Tiến, Trọng, Phượng, Quyến, Trung, Trường xin cảmơn! 3 BÁO CÁO THẢO LUẬNMôn học :Toán rời rạcChủ đề: Chỉnh hợp và tổ hợp suy rộng Các sinh viên:8. - Tổ hợp. - Một số nội dung mở rộng. - 33 3 Nội dung1.Cơ sở của phép đếm1.1Quy tắc cộng Nếu một công việc có thể được thực hiện bằng một trong n cách loại trừlẫn nhau: k1, k2. - Trong đó để thực hiện theo cách ki lại có ti phươngán khác nhau (i=1..n). - Khi đó tổng số phương án để thực hiện công việc banđầu là: t1 + t2. - Ví dụ 1. - Hỏi có bao nhiêu cách chọn vị đại biểu này nếu như có 37 cán bộ và 63 sinh viên. - Giải: Gọi việc thứ nhất là chọn một cán bộ từ tập cán bộ ta có 37 cách. - Gọi việc thứ hai là chọn một sinh viên từ tập sinh viên ta có 63 cách. - Vì tập cán bộ và tập sinh viên là rời nhau, theo nguyên lý cộng ta có tổng số cách chọn vị đại biểu này là cách chọn. - Ví dụ 2. - Số vận động viên nam là 10 người. - Hỏi đoàn có bao nhiêu người. - Ví dụ 3. - giá trị của biến k sẽ bằng bao nhiêu sau khi thực hiện đoạn chương trình sau: k:= 0 for i1:= 1 to n1 do 3 k:=k+1 for i2:= 1 to n2 k:=k+1. - for im:= 1 to nm k:=k+1 Giải: Coi mỗi vòng for là một công việc, do đó ta có m công việc T1,T2. - Trong đó Ti thực hiện bởi ni cách (i= 1, 2. - Vì các vòng forkhông lồng nhau hay các công việc không thực hiện đồng thời nên theo nguyênlý cộng tổng tất cả các cách để hoàn thành T1, T2. - Việc thứ nhấtđược thực hiện bằng n1 cách, việc thứ hai được thực hiện bằng n2 cách sau khiviệc thứ nhất đã được làm, khi đó sẽ có n1.n2 cách thực hiện nhiệm vụ này. - Nguyên lý nhân có thể được phát biểu tổng quát bằng ngôn ngữ tập hợp như sau: Nếu A1, A2. - Am là những tập hợp hữu hạn, khi đó số phần tử của tích đềcác các tập này bằng tích số các phần tử của mỗi tập thành phần. - N(A)k Ví dụ 1. - Giá trị của k sẽ bằng bao nhiêu sau khi ta thực hiện đoạn chương trình sau: k:=0 for i1 = 1 to n1 for i2 = 1 to n2. - Khi đó, số lầnvòng lặp là số cách thực hiện công việc. - Số cách thực hiện công việc Tj là nj(j=1,2. - Người ta có thể ghi nhãn cho những chiếc ghế của một giảngđường bằng một chữ cái và sau đó là một số nguyên nhỏ hơn 100. - Bằng cáchnhư vậy hỏi có nhiều nhất bao nhiêu chiếc ghế có thể ghi nhãn khác nhau. - Vì kí tự gánnhãn đầu tiên là một chữ cái vậy có 26 cách chọn các chữ cái khác nhau để ghikí tự đầu tiên, tiếp theo sau là một số nguyên dương nhỏ hơn 100 do vậy có 100cách chọn các số nguyên để gán tiếp sau của một nhãn. - Có bao nhiêu xâu nhị phân có độ dài 7. - Giải: một xâu nhị phân có độ dài 7 gồm 7 bít, mỗi bít có hai cách chọn(hoặc giá trị 0 hoặc giá trị 1), theo qui tắc nhân ta có xâu bít nhị phân độ dài 7. - Ví dụ 4. - Có bao nhiêu hàm đơn ánh xác định từ một tập A có m phần tử nhận giá trị trên tậpB có n phần tử. - Giải: Trước tiên ta nhận thấy, nếu m >n thì tồn tại ít nhất hai phần tử khác nhau của A cùngnhận một giá trị trên B, như vậy với m>n thì số các hàm đơn ánh từ A→B là 0.Nếu mn Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một dãy n-1 thanhđứng và k ngôi sao.Ta dùng n-1 thanh đứng để phân cách các ngăn.Ngăn thứ ichứa thêm một ngôi sao mỗi lần khi phần tử thứ i của tập xuất hiện trong tậphợp.Chẳng hạn,tổ hợp lặp chập 6 của 4 phần tử được biểu thị bởi. - |***Mô tả tổ hợp chứa đúng hai phần tử thứ nhất,một phần tử thứ hai,không có phần tửthứ ba và 3 phần tử thứ tư của tập hợp Mỗi dãy n-1 thanh và k ngôi sao ứng với một xâu nhị phân độ dài n+k-1 với ksố 1.Do đó số các dãy n-1 thanh đứng và k ngôi sao chính là số tổ hợp chập k từtập n+k-1 phần tử.4.2.3 Các ví dụ:Ví dụ 1.Có bao nhiêu cách chọn 5 tờ giấy bạc từ một két đựng tiền gồm những tờ1000đ, 2000đ, 5000đ, 10.000đ, 20.000đ, 50.000đ, 100.000đ.Giả sử thứ tự mà cáctờ tiền được chọn là không quan trọng,các tợ tiền cùng loại là không phân biệt vàmỗi loại có ít nhất 5 tờ.Giải: Vì ta không kể tới thứ tự chọn tờ tiền và vì ta chọn đúng 5 lần,mỗi lần lấymột từ 1 trong 7 loại tiền nên mỗi cách chọn 5 tờ giấy bạc này chính là một tổ hợplặp chập 5 từ 7 phần tử.Do đó số cần tìm là C V í d ụ 2 . - “Tìm số nghiệm nguyên không âm của phương trình sau: x1 + x2 + x3 = 10”.Giải: Đối với bài toán này, nếu đặt x1 là số bánh được cho vào hộp 1, x2 là sốbánh được cho vào hộp 2 và x3 là số bánh được cho vào hộp 3 thì bài toán trêntrở thành “có bao nhiêu cách cho 10 cái bánh giống nhau vào trong 3 cái hộpkhác nhau” và kết quả cần tìm làVí dụ 3. - Hỏi có bao nhiêu cáchchia như vậy. - Các mở rộng về giai thừa: Khái niệm “giai thừa”: Trong toán học, giai thừa là một toán tử một ngôi trên tập hợp các sốtự nhiên. - Cho n là một số tự nhiên dương, "n giai thừa", kí hiệu n! làtích của n số tự nhiên dương đầu tiên: 3 n. - Định nghĩa đệ quyTa có thể định nghĩa đệ quy (quy nạp) n! như sau: 1. - (n + 1) với n> 0Các khái niệm tương tựa.Giai thừa nguyên tố (primorial) Giai thừa nguyên tố của số tự nhiên n≥2, ký hiệu n# là tích của tấtcác các số nguyên tố không vượt quá n.Ví dụ b. - Giai thừa kép Có thể coi n! là tích n phần tử đầu của cấp số cộng với phần tử đầubằng 1 và công sai bằng 1. - Mở rộng với công sai bằng 2 ta có: Giai thừa kép là tích n phần tử đầu của cấp số cộng với phần tửđầu 1 và công sai là 2.Ví dụ: 8. - Dãy các giai thừa kép đầu tiên là: n n Định nghĩa trên có thể mở rộng cho các số nguyên âm như sau:Các giai thừa kép nguyên âm lẻ đầu tiên với n là Một vài đẳng thức với giai thừa kép: 3 - n!=n!!(n-1. - Giai thừa bội Ta có thể tiếp tục mở rộng với các giai thừa bội ba (n!!!),bội bốn(n. - Tổng quát, giai thừa bội k ký hiệu là n!(k), được định nghĩa đệ quynhư sau:d. - Siêu giai thừa (superfactorial). - Siêu giai thừa là tích của n giai thừa đầu tiên. - sf(n n-2)!(n-1)!n!( Neil Sloane và Simon Plouffe đã định nghĩa siêu giai thừa (năm 1995)) Chẳng hạn, siêu giai thừa của 4 là Tổng quát 3 n-k+1 Sf(n. - 1n.2n-2.3n-2...(n-1)2.n1Các siêu giai thừa đầu tiên bắt đầu từ (n = 0) là . - Hệ số nhị thứcĐịnh lý 1: Cho n,k là các số nguyên dương, với n ≥k, khi đó: Ckn+1`= Ck-1n + Ckn (Hằng đẳng thức Pascal) Chứng minh: Giả sử T là một tập có n+1 phần tử, gọi a là một phần tửbất kỳ của T. - Khi đó Ckn+1 là số các tập con có k phần tử của tập T,hoặc là chứa phần tử a cùng với k-1 phần tử của S, hoặc là chứa k phần tửcủa S mà không chứa a. - Vì có Ck-1n tập con chứa k-1 phần tử của S và Ckn tậpcon chứa k phần tử của tập S. - Khai triển ta có hằngđẳng thức Pascal hay tam giác Pascal: C00 C01 C11 C02 C12 C22 C03 C13 C23 C33 C04 C14 C24 C34 C44 3 C05 C15 C25 C35 C45 C Hằng đẳng thức Pascal chỉ ra rằng khiu cộng hai hệ số nhị thức liền kềtrong tam giác sẽ nhận được hệ số nhị thức của hàng tiếp theo ở giữa. - kĐịnh lý 2: Cho n số nguyên dương, khi đó =2n nChứng minh: Một tập hợp n phần tử có tất cả 2n tập con khác nhau (1). - Mặt khác ta thấy, mỗi tập con có hoặc không có phần tử nào hoặc 1phần tử, hoặc 2 phần tử. - hoặc n phần tử. - Số tập con có 0 phần tử là Số tập con có 2 phần tử là 3. - Số tập con có n phần tử là k Do đó ta có tất cả n tập con của tập n phần tử. - Kết hợp với (1) tacó k n =2n Định lý 3: Cho x,y là hai biến và n là một số nguyên dương khi đó:(x+y)n= k n-k k x y n (n≥2) Chứng minh: Ta chứng minh hệ thức này bằng suy luận tổ hợp. - n Hệ quả: k Khi x=y=1 ta có = 2n n k Khi x=1, y=-1, ta có (-1)k= 0. - Toán rời rạc – Nguyễn Ngọc Trung – ĐH Sư Phạm TP HCM 5. - Toán rời rạc – Nguyễn Duy Phương – HV Bưu Chính Viễn Thông 6. - 3Lời kết thúcTuy được hoàn thiện trong thời gian ngắn nhưng báo đã trình bày chi tiết những nộidung cơ bản và mở rộng về lí thuyết tổ hợp cũng như các vấn đề về tổ hợp và chỉnhhợp suy rộng cùng với các ví dụ cụ thể cho mỗi nội dung cùng với đó là thuật toánđược viết bằng ngôn ngữ lập trình Pascal.Thân ái cảm ơn sự theo dõi và góp ý của thầy cô và các bạn Nhận xét của giáo viên phụ trách
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt