Chương 2: Tổ hợp

Nội dung tài liệu trình bày hoán vị; tổ hợp; nguyên lý bù trừ; công thức đệ qui và hàm sinh; nguyên lý các lồng chim bồ câu. Để hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung tài liệu.
Nội dung trích xuất từ tài liệu:
Chương 2: Tổ hợpNội dung2.1. Hoán vị2.2. Tổ hợp (Combination)2.3. Nguyên lý bù trừChương 22.4. Công thức đệ qui và hàm sinhTỔ HỢP2.5. Số Stirling(Combinatorics)Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội2.6. Nguyên lý các lồng chim bồ câuChap02-1Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nộiChương 2. Lý thuyết tổ hợpChap02-22.1 Hoán vị2.1. Hoánn vị••••2.2. Tổổ hợp (Combination)(C2.3. Nguyên lý bù trừ2.4. Công thức đệ qui và hàm sinh2.1.1. Chỉnh hợp lặp chập m (m-permutation with repetition)2.1.2. Chỉnh hợp không lặp chập m (m-permutation)2.1.3. Hoán vị (permutation)2.1.4. Liệt kê hoán vị2.5. Số Stirling2.6. Nguyên lý các lồng chim bồ câuToán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nộiChap02-3Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nộiChap02-42.1.1. Hoán vị lặp (Chỉnh hợp lặp)Chỉnh hợp lặp• Giả sử X là tập n phần tử.• Định nghĩa. Ta gọi chỉnh hợp lặp chập m từ n phần tử củaX là bộ có thứ tự gồm m thành phần, mỗi thành phần đều làphần tử của X.• Chú ý: Trong tài liệu tiếng Anh, thuật ngữ m-permutationwith repetition được dùng để chỉ chỉnh hợp lặp chập m. Vìthế có tài liệu dịch là hoán vị lặp.• Ký hiệu số lượng chỉnh hợp lặp chập m từ n phần tử là Anm• Theo định nghĩa, một chỉnh hợp lặp chập m từ n phần tửcủa X có thể biểu diễn bởi(a1, a2, ..., am), ai Î X, i = 1, 2, ..., m.Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nộiChap02-5Chỉnh hợp lặpToán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nộiChap02-62.1.2. Chỉnh hợp không lặp• Ví dụ 3. Cần phải phân bố 100 sinh viên vào 4 nhómthực tập ACCESS, FOXPRO, EXCEL, LOTUS. Mỗisinh viên phải tham gia vào đúng một nhóm và mỗinhóm có thể nhận một số lượng không hạn chế sinhviên• Giải: 4100 hay 1004 ?• Mỗi cách phân bố cần tìm có thể biểu diễn bởi bộ cóthứ tự gồm 100 thành phần (b1, ..., b100) trong đó bi Î{A, F, E, L} là nhóm thực tập của sinh viên thứ i. Từđó suy ra số cách phân bố cần đếm là 4100.Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội• Dễ thấy tập tất cả các chỉnh hợp lặp chập m từ n phần tử của X chính làXm. Vì vậy, theo nguyên lý nhân ta có• Định lý. Anm = nm.• Ví dụ 1. Tính số ánh xạ từ tập m phần tử U = {u1, u2, ..., um} vào tập nphần tử V.• Giải: Mỗi ánh xạ f cần đếm được xác định bởi bộ ảnh (f(u1), f(u2), ...,f(um)), trong đó f(ui) Î V, i=1, 2, ..., m. Từ đó nhận được số cần tìm lànm.• Ví dụ 2. Tính số dãy nhị phân độ dài n.• Giải: Mỗi dãy nhị phân độ dài n là một bộ gồm n thành phần, trong đómỗi thành phần chỉ nhận một trong hai giá trị (1 hoặc 0). Từ đó suy rasố các dãy nhị phân độ dài n là 2n.• Do mỗi tập con của tập n phần tử tương ứng với một vectơ đặc trưng làmột xâu nhị phân độ dài n, nên ta có• Hệ quả: Số lượng tập con của tập n phần tử là 2n.Chap02-7• Định nghĩa. Ta gọi chỉnh hợp không lặp chập m (m-permutation)từ n phần tử của X là bộ có thứ tự gồm m thành phần, mỗi thànhphần đều là phần tử của X, các thành phần khác nhau từng đôi.• Ký hiệu số lượng chỉnh hợp không lặp chập m từ n phần tử làP(n,m). Rõ ràng, để tồn tại chỉnh hợp không lặp, thì m £ n.• Theo định nghĩa, một chỉnh hợp không lặp chập m từ n phần tửcủa X có thể biểu diễn bởi(a1, a2, ..., am), ai Î X, i = 1, 2, ..., m, ai ¹ aj, i ¹ j.• Việc đếm số lượng chỉnh hợp không lặp chập m từ n phần tử cóthể thực hiện theo nguyên lý nhân. Ta có• Định lý.n!P(n, m) = n(n - 1)...(n - m + 1) =(n - m)!Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nộiChap02-8Chỉnh hợp không lặpChỉnh hợp không lặp• VÝ dô 1. TÝnh sè đơn ¸nh tõ tËp m phÇn tö U = {u1, u2, ..., um}vµo tËp n phÇn tö V.• Gi¶i: Mçi đơn ¸nh f cÇn ®Õm ®îc x¸c ®Þnh bëi bé ¶nh (f(u1),f(u2), ..., f(um)), trong ®ã f(ui) Î V, i=1, 2, ..., m, f(ui)¹ f(uj), i¹ j.Tõ ®ã nhËn ®îc sè cÇn tìm lµ n(n-1)...(n-m+1).• Ví dụ 2. Có bao nhiêu cách xếp 4 học sinh vào ngồi sau một cáibàn có 10 chỗ ngồi với điều kiện không được phép ngồi lòng.• Giải. Đánh số các học sinh từ 1 đến 4, các chỗ ngồi từ 1 đến 10.Mỗi cách xếp học sinh cần đếm có thể biểu diễn bởi bộ có thứ tự(g1, g2, g3, g4), trong đó gi Î {1, 2, ..., 10} là chỗ ngồi của họcsinh i. Từ điều kiện đầu bài gi¹ gj, i¹ j; do đó mỗi cách xếp cầnđếm là một chỉnh hợp không lặp chập 4 từ 10. Vậy số cách xếpcần đếm là P(10,4) = 10.9.8.7 = 5040.Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nộiChap02-9ΏHọc sinh thứ nhất có 10 cách xếpΏTiếp đến học sinh thứ hai có thể xếp vào 1 trong 9 chỗ cònlại, ...• Theo nguyên lý nhân có 10.9.8.7 = 5040 cách xếpToán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nộiChap02-10Hoán vị2.1.3. Hoán vị• Định nghĩa. Ta gọi hoán vị từ n phần tử của X là bộ cóthứ tự gồm n thành phần, mỗi thành phần đều là phầntử của X, các thành phần khác nhau từng đôi.• Ký hiệu số lượng hoán vị từ n phần tử là P(n).• Theo định nghĩa, một hoán vị từ n phần tử của X có thểbiểu diễn bởi(a1, a2, ..., an), ai Î X, i = 1, 2, ..., n, ai ¹ aj, i ¹ j.• Rõ ràng P(n) = P(n,n). Vì vậy, ta có• Định lý.P(n) = P(n, n) = n ´ (n - 1) ´ ... ´ 2 ´1 = n!Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội• Chú ý: Để giải ví dụ 2 có thể lập luận trực tiếp theo nguyênlý nhân:• Ta lần lượt xếp các học sinh vào chỗ ngồi.Chap02-11• Ví dụ 1. 6 người đứng xếp thành một hàng ngangđể chụp ảnh. Hỏi có thể bố trí bao nhiêu kiểu?• Giải: Mỗi kiểu ảnh là một hoán vị của 6 người. Từđó nhận được số kiểu ảnh có thể bố trí là 6! = 720.• Ví dụ 2. Cần bố trí việc thực hiện n chương trìnhtrên một máy vi tính. Hỏi có bao nhiêu cách?• Giải: Đánh số các chương trình bởi 1, 2,..., n. Mỗicách bố trí việc thực hiện các chương trình trênmáy có thể biểu diễn bởi một hoán vị của 1, 2, ...,n. Từ đó suy ra số cách bố trí cần tìm là n!Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nộiChap02-12Hoán vị2.1.4. Liệt kê hoán vị• Ví dụ 3. Có bao nhiêu song ánh từ tập n phần t ...