Chương 2: Tổ hợp

Nội dung<br /> 2.1. Hoán vị<br /> 2.2. Tổ hợp (Combination)<br /> 2.3. Nguyên lý bù trừ<br /> <br /> Chương 2<br /> <br /> 2.4. Công thức đệ qui và hàm sinh<br /> <br /> TỔ HỢP<br /> <br /> 2.5. Số Stirling<br /> <br /> (Combinatorics)<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> 2.6. Nguyên lý các lồng chim bồ câu<br /> <br /> Chap02-1<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chương 2. Lý thuyết tổ hợp<br /> <br /> Chap02-2<br /> <br /> 2.1 Hoán vị<br /> <br /> 2.1. Hoán<br /> n vị<br /> <br /> •<br /> •<br /> •<br /> •<br /> <br /> 2.2. Tổ<br /> ổ hợp (Combination)<br /> (C<br /> 2.3. Nguyên lý bù trừ<br /> 2.4. Công thức đệ qui và hàm sinh<br /> <br /> 2.1.1. Chỉnh hợp lặp chập m (m-permutation with repetition)<br /> 2.1.2. Chỉnh hợp không lặp chập m (m-permutation)<br /> 2.1.3. Hoán vị (permutation)<br /> 2.1.4. Liệt kê hoán vị<br /> <br /> 2.5. Số Stirling<br /> 2.6. Nguyên lý các lồng chim bồ câu<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-3<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-4<br /> <br /> 2.1.1. Hoán vị lặp (Chỉnh hợp lặp)<br /> <br /> Chỉnh hợp lặp<br /> <br /> • Giả sử X là tập n phần tử.<br /> • Định nghĩa. Ta gọi chỉnh hợp lặp chập m từ n phần tử của<br /> X là bộ có thứ tự gồm m thành phần, mỗi thành phần đều là<br /> phần tử của X.<br /> • Chú ý: Trong tài liệu tiếng Anh, thuật ngữ "m-permutation<br /> with repetition" được dùng để chỉ chỉnh hợp lặp chập m. Vì<br /> thế có tài liệu dịch là hoán vị lặp.<br /> • Ký hiệu số lượng chỉnh hợp lặp chập m từ n phần tử là Anm<br /> • Theo định nghĩa, một chỉnh hợp lặp chập m từ n phần tử<br /> của X có thể biểu diễn bởi<br /> (a1, a2, ..., am), ai Î X, i = 1, 2, ..., m.<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-5<br /> <br /> Chỉnh hợp lặp<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-6<br /> <br /> 2.1.2. Chỉnh hợp không lặp<br /> <br /> • Ví dụ 3. Cần phải phân bố 100 sinh viên vào 4 nhóm<br /> thực tập ACCESS, FOXPRO, EXCEL, LOTUS. Mỗi<br /> sinh viên phải tham gia vào đúng một nhóm và mỗi<br /> nhóm có thể nhận một số lượng không hạn chế sinh<br /> viên<br /> • Giải: 4100 hay 1004 ?<br /> • Mỗi cách phân bố cần tìm có thể biểu diễn bởi bộ có<br /> thứ tự gồm 100 thành phần (b1, ..., b100) trong đó bi Î<br /> {A, F, E, L} là nhóm thực tập của sinh viên thứ i. Từ<br /> đó suy ra số cách phân bố cần đếm là 4100.<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> • 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à<br /> Xm. Vì vậy, theo nguyên lý nhân ta có<br /> • Định lý. Anm = nm.<br /> • Ví dụ 1. Tính số ánh xạ từ tập m phần tử U = {u1, u2, ..., um} vào tập n<br /> phần tử V.<br /> • Giải: Mỗi ánh xạ f cần đếm được xác định bởi bộ ảnh (f(u1), f(u2), ...,<br /> f(um)), trong đó f(ui) Î V, i=1, 2, ..., m. Từ đó nhận được số cần tìm là<br /> nm.<br /> • Ví dụ 2. Tính số dãy nhị phân độ dài n.<br /> • Giải: Mỗi dãy nhị phân độ dài n là một bộ gồm n thành phần, trong đó<br /> mỗi thành phần chỉ nhận một trong hai giá trị (1 hoặc 0). Từ đó suy ra<br /> số các dãy nhị phân độ dài n là 2n.<br /> • 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à<br /> một xâu nhị phân độ dài n, nên ta có<br /> • Hệ quả: Số lượng tập con của tập n phần tử là 2n.<br /> <br /> Chap02-7<br /> <br /> • Định nghĩa. Ta gọi chỉnh hợp không lặp chập m (m-permutation)<br /> từ n phần tử của X là bộ có thứ tự gồm m thành phần, mỗi thành<br /> phần đều là phần tử của X, các thành phần khác nhau từng đôi.<br /> • Ký hiệu số lượng chỉnh hợp không lặp chập m từ n phần tử là<br /> P(n,m). Rõ ràng, để tồn tại chỉnh hợp không lặp, thì m £ n.<br /> • Theo định nghĩa, một chỉnh hợp không lặp chập m từ n phần tử<br /> của X có thể biểu diễn bởi<br /> (a1, a2, ..., am), ai Î X, i = 1, 2, ..., m, ai ¹ aj, i ¹ j.<br /> • Việc đếm số lượng chỉnh hợp không lặp chập m từ n phần tử có<br /> thể thực hiện theo nguyên lý nhân. Ta có<br /> • Định lý.<br /> n!<br /> P(n, m) = n(n - 1)...(n - m + 1) =<br /> (n - m)!<br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-8<br /> <br /> Chỉnh hợp không lặp<br /> <br /> Chỉnh hợp không lặp<br /> <br /> • VÝ dô 1. TÝnh sè đơn ¸nh tõ tËp m phÇn tö U = {u1, u2, ..., um}<br /> vµo tËp n phÇn tö V.<br /> • Gi¶i: Mçi đơn ¸nh f cÇn ®Õm ®îc x¸c ®Þnh bëi bé ¶nh (f(u1),<br /> f(u2), ..., f(um)), trong ®ã f(ui) Î V, i=1, 2, ..., m, f(ui)¹ f(uj), i¹ j.<br /> Tõ ®ã nhËn ®îc sè cÇn tìm lµ n(n-1)...(n-m+1).<br /> • Ví dụ 2. Có bao nhiêu cách xếp 4 học sinh vào ngồi sau một cái<br /> bàn có 10 chỗ ngồi với điều kiện không được phép ngồi lòng.<br /> • Giải. Đánh số các học sinh từ 1 đến 4, các chỗ ngồi từ 1 đến 10.<br /> Mỗi cách xếp học sinh cần đếm có thể biểu diễn bởi bộ có thứ tự<br /> (g1, g2, g3, g4), trong đó gi Î {1, 2, ..., 10} là chỗ ngồi của học<br /> sinh i. Từ điều kiện đầu bài gi¹ gj, i¹ j; do đó mỗi cách xếp cần<br /> đếm là một chỉnh hợp không lặp chập 4 từ 10. Vậy số cách xếp<br /> cần đếm là P(10,4) = 10.9.8.7 = 5040.<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-9<br /> <br /> ΏHọc sinh thứ nhất có 10 cách xếp<br /> ΏTiếp đến học sinh thứ hai có thể xếp vào 1 trong 9 chỗ còn<br /> lại, ...<br /> <br /> • Theo nguyên lý nhân có 10.9.8.7 = 5040 cách xếp<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-10<br /> <br /> Hoán vị<br /> <br /> 2.1.3. Hoán vị<br /> • Định nghĩa. Ta gọi hoán vị từ n phần tử của X là bộ có<br /> thứ tự gồm n thành phần, mỗi thành phần đều là phần<br /> tử của X, các thành phần khác nhau từng đôi.<br /> • Ký hiệu số lượng hoán vị từ n phần tử là P(n).<br /> • Theo định nghĩa, một hoán vị từ n phần tử của X có thể<br /> biểu diễn bởi<br /> (a1, a2, ..., an), ai Î X, i = 1, 2, ..., n, ai ¹ aj, i ¹ j.<br /> • Rõ ràng P(n) = P(n,n). Vì vậy, ta có<br /> • Định lý.<br /> <br /> P(n) = P(n, n) = n ´ (n - 1) ´ ... ´ 2 ´1 = n!<br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> • Chú ý: Để giải ví dụ 2 có thể lập luận trực tiếp theo nguyên<br /> lý nhân:<br /> • Ta lần lượt xếp các học sinh vào chỗ ngồi.<br /> <br /> Chap02-11<br /> <br /> • Ví dụ 1. 6 người đứng xếp thành một hàng ngang<br /> để chụp ảnh. Hỏi có thể bố trí bao nhiêu kiểu?<br /> • Giải: Mỗi kiểu ảnh là một hoán vị của 6 người. Từ<br /> đó nhận được số kiểu ảnh có thể bố trí là 6! = 720.<br /> • Ví dụ 2. Cần bố trí việc thực hiện n chương trình<br /> trên một máy vi tính. Hỏi có bao nhiêu cách?<br /> • Giải: Đánh số các chương trình bởi 1, 2,..., n. Mỗi<br /> cách bố trí việc thực hiện các chương trình trên<br /> máy có thể biểu diễn bởi một hoán vị của 1, 2, ...,<br /> n. Từ đó suy ra số cách bố trí cần tìm là n!<br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-12<br /> <br /> Hoán vị<br /> <br /> 2.1.4. Liệt kê hoán vị<br /> <br /> • Ví dụ 3. Có bao nhiêu song ánh từ tập n phần tử X<br /> vào chính nó?<br /> • Giải. Mỗi song ánh f cần đếm được xác định bởi<br /> bộ ảnh (f(u1), f(u2), ..., f(un)), trong đó f(ui) Î X,<br /> i=1, 2, ..., n, f(ui)¹ f(uj), i¹ j.<br /> •<br /> Từ đó nhận được số cần tìm là n!<br /> • Ví dụ 4. Có bao nhiêu cách bố trí n thợ thực hiện n<br /> việc sao cho mỗi thợ thực hiện một việc và mỗi<br /> việc do đúng một thợ thực hiện<br /> • Giải: n!<br /> <br /> • Xét hai phương pháp liệt kê:<br /> ΏCây liệt kê<br /> ΏThuật toán sinh hoán vị<br /> <br /> • Cây liệt kê. Ví dụ, liệt kê các hoán vị của {a, b, c}<br /> -<br /> <br /> Thành phần thứ 1<br /> <br /> b<br /> <br /> a<br /> <br /> Thành phần thứ 2<br /> Thành phần thứ 3<br /> <br /> b<br /> <br /> c<br /> <br /> c<br /> <br /> b<br /> <br /> (a,b,c) (a,c,b)<br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-13<br /> <br /> c<br /> (b,a,c)<br /> <br /> c<br /> a<br /> (b,c,a)<br /> <br /> a<br /> <br /> b<br /> <br /> b<br /> <br /> a<br /> <br /> (c,a,b)<br /> <br /> (c,b,a)<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-14<br /> <br /> Ví dụ<br /> <br /> Thuậ<br /> uậtt toá<br /> uậ<br /> oá<br /> án sinh<br /> h hoá<br /> oá<br /> án vị<br /> <br /> • Bµi to¸n ®Æt ra lµ: Cho X = {1, 2, ... , n}. H·y liÖt kª c¸c<br /> ho¸n vÞ tõ n phÇn tö cña X.<br /> • Mçi ho¸n vÞ tõ n phÇn tö cña X cã thÓ biÓu diÔn bëi bé cã<br /> thø tù gåm n thµnh phÇn a = (a1, a2, ... , an) tho¶ m·n<br /> ai Î X , i = 1, 2,..., n , ap ¹ aq, p ¹ q.<br /> <br /> • Tríc hÕt ta xÐt quan hÖ thø tù tõ ®iÓn trªn tËp c¸c ho¸n vÞ.<br /> • Ta nãi ho¸n vÞ a = (a1, a2,..., an) ®i tríc ho¸n vÞ a' = (a'1,<br /> a'2, ... , a'n) trong thø tù tõ ®iÓn vµ ký hiÖu lµ a p a', nÕu<br /> tìm ®îc chØ sè k (1 £ k £ n) sao cho:<br /> a1 = a'1 , a2 = a'2, ... , ak-1 = a'k-1, ak < a'k .<br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> a<br /> <br /> c<br /> <br /> Chap02-15<br /> <br /> • C¸c ho¸n vÞ tõ 3 phÇn tö cña X ={1, 2, 3} ®îc liÖt kª theo<br /> thø tù tõ ®iÓn nh sau:<br /> 1<br /> 2<br /> 3<br /> 1<br /> 3<br /> 2<br /> 2<br /> 1<br /> 3<br /> 2<br /> 3<br /> 1<br /> 3<br /> 1<br /> 2<br /> 3<br /> 2<br /> 1<br /> • Ho¸n vÞ ®Çu tiªn trong thø tù tõ ®iÓn lµ (1, 2, ... , n)<br /> • Ho¸n vÞ cuèi cïng lµ (n, n-1, ..., 1).<br /> • Ta cÇn t™m c¸ch tõ mét ho¸n vÞ ®ang cã a = (a1, a2, ... , an)<br /> nÕu cha ph¶i lµ ho¸n vÞ cuèi cïng, ®a ra ho¸n vÞ kÕ tiÕp.<br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-16<br /> <br /> Thuật toán sinh kế tiếp<br /> <br /> Ví dụ<br /> <br /> • Gi¶ sö a = (a1, a2, ... , an) lµ ho¸n vÞ cha ph¶i cuèi cïng,<br /> khi ®ã ho¸n vÞ kÕ tiÕp nã cã thÓ x©y dùng nhê thùc hiÖn c¸c<br /> biÕn ®æi sau:<br /> <br /> • Gi¶ sö ®ang cã ho¸n vÞ (3, 6, 2, 5, 4, 1), cÇn x©y dùng ho¸n<br /> vÞ kÕ tiÕp nã trong thø tù tõ ®iÓn.<br /> <br /> ΏTìm tõ ph¶i qua tr¸i ho¸n vÞ ®ang cã chØ sè j ®Çu tiªn<br /> tho¶ m·n aj < aj+1 (nãi c¸ch kh¸c: j lµ chØ sè lín nhÊt<br /> tho¶ m·n aj < aj+1);<br /> <br /> • Sè nhá nhÊt cßn lín h¬n a3 trong c¸c sè bªn ph¶i cña a3 lµ<br /> a5 = 4. Đæi chç a3 víi a5 ta thu ®îc (3, 6, 4, 5, 2, 1),<br /> <br /> ΏTìm ak lµ sè nhá nhÊt cßn lín h¬n aj trong c¸c sè ë bªn<br /> ph¶i aj ;<br /> <br /> • Ta cã chØ sè j = 3 (a3 =2 < a4 = 5).<br /> <br /> • Cuèi cïng, lËt ngîc thø tù ®o¹n a4 a5 a6 ta thu ®îc ho¸n vÞ<br /> kÕ tiÕp (3, 6, 4, 1, 2, 5).<br /> <br /> ΏĐổi chỗ aj víi ak ;<br /> ΏLËt ngîc ®o¹n tõ aj+1 ®Õn an .<br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-17<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chương 2. Lý thuyết tổ hợp<br /> <br /> Chap02-18<br /> <br /> 2.2. Tổ hợp<br /> •<br /> •<br /> •<br /> •<br /> <br /> 2.1. Hoán vị<br /> 2.2. Tổ hợ<br /> hợp<br /> ợp (Combination)<br /> (<br /> <br /> 2.3. Nguyên lý bù trừ<br /> <br /> 2.2.1. Tổ hợp<br /> 2.2.2. Tổ hợp lặp<br /> 2.2.3. Tính chất của hệ số tổ hợp<br /> 2.2.4. Liệt kê<br /> <br /> 2.4. Công thức đệ qui và hàm sinh<br /> <br /> 2.5. Số Stirling<br /> 2.6. Nguyên lý các lồng chim bồ câu<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-19<br /> <br /> Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội<br /> <br /> Chap02-20<br /> <br />