Giáo trình Toán rời rạc - Chương 2: Tổ hợp - Nguyễn Đức Nghĩa

Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chương 2 TỔ HỢP (Combinatorics) Chap02-1 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nội dung 2.1. Hoán vị 2.2. Tổ hợp (Combination) 2.3. Nguyên lý bù trừ 2.4. Công thức đệ qui và hàm sinh 2.5. Số Stirling 2.6. Nguyên lý các lồng chim bồ câu Chap02-2 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chương 2. Lý thuyết tổ hợp 2.1. Hoán vị 2.2. Tổ hợp (Combination) 2.3. Nguyên lý bù trừ 2.4. Công thức đệ qui và hàm sinh 2.5. Số Stirling 2.6. Nguyên lý các lồng chim bồ câu Chap02-3 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.1 Hoán vị • 2.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ị Chap02-4 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.1.1. Hoán vị 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ủa X 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-permutation with 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. Chap02-5 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chỉnh hợp lặp • 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 n phầ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 ra số 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-6 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chỉnh hợp lặp • Ví dụ 3. Cần phải phân bố 100 sinh viên vào 4 nhóm thực tập ACCESS, FOXPRO, EXCEL, LOTUS. Mỗi sinh viên phải tham gia vào đúng một nhóm và mỗi nhóm có thể nhận một số lượng không hạn chế sinh viê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. Chap02-7 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.1.2. Chỉnh hợp không lặp • Đị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ành phầ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ý. ! ( , ) ( 1)...( 1) ( )! n P n m n n n m n m = - - + = - Chap02-8 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chỉ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ái bà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ọc sinh 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ếp cần đếm là P(10,4) = 10.9.8.7 = 5040. Chap02-9 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chỉnh hợp không lặp • Chú ý: Để giải ví dụ 2 có thể lập luận trực tiếp theo nguyên lý nhân: • Ta lần lượt xếp các học sinh vào chỗ ngồi. Ώ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òn lại, ... • Theo nguyên lý nhân có 10.9.8.7 = 5040 cách xếp Chap02-10 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 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ần tử 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ý. ( ) ( , ) ( 1) ... 2 1 !P n P n n n n n= = ´ - ´ ´ ´ = Chap02-11 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Hoán vị • 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ình trê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ỗi cách bố trí việc thực hiện các chương trình trên má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! Chap02-12 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Hoán vị • Ví dụ 3. Có bao nhiêu song ánh từ tập n phần tử X vào chính nó? • Giải. Mỗi song ánh f cần đếm được xác định bởi bộ ảnh (f(u1), f(u2), ..., f(un)), trong đó f(ui) Î X, i=1, 2, ..., n, f(ui)¹ f(uj), i¹ j. • Từ đó nhận được số cần tìm là n! • Ví dụ 4. Có bao nhiêu cách bố trí n thợ thực hiện n việc sao cho mỗi thợ thực hiện một việc và mỗi việc do đúng một thợ thực hiện • Giải: n! Chap02-13 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội b 2.1.4. Liệt kê hoán vị • Xét hai phương pháp liệt kê: ΏCây liệt kê ΏThuật toán sinh hoán vị • Cây liệt kê. Ví dụ, liệt kê các hoán vị của {a, b, c} Chap02-14 a c cb c a c a b b c - a b a (a,b,c) (a,c,b) (b,a,c) (b,c,a) (c,a,b) (c,b,a) Thành phần thứ 1 Thành phần thứ 2 Thành phần thứ 3 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Thuật toán sinh hoán vị • Bµi to¸n ®Æt ra lµ: Cho X = {1, 2, ... , n}. H·y liÖt kª c¸c ho¸n vÞ tõ n phÇn tö cña X. • Mçi ho¸n vÞ tõ n phÇn tö cña X cã thÓ biÓu diÔn bëi bé cã thø tù gåm n thµnh phÇn a = (a1, a2, ... , an) tho¶ m·n ai Î X , i = 1, 2,..., n , ap ¹ aq, p ¹ q. • Tríc hÕt ta xÐt quan hÖ thø tù tõ ®iÓn trªn tËp c¸c ho¸n vÞ. • Ta nãi ho¸n vÞ a = (a1, a2,..., an) ®i tríc ho¸n vÞ a' = (a'1, a'2, ... , a'n) trong thø tù tõ ®iÓn vµ ký hiÖu lµ a p a', nÕu tìm ®îc chØ sè k (1 £ k £ n) sao cho: a1 = a'1 , a2 = a'2, ... , ak-1 = a'k-1, ak < a'k . Chap02-15 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • C¸c ho¸n vÞ tõ 3 phÇn tö cña X ={1, 2, 3} ®îc liÖt kª theo thø tù tõ ®iÓn nh sau: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 • Ho¸n vÞ ®Çu tiªn trong thø tù tõ ®iÓn lµ (1, 2, ... , n) • Ho¸n vÞ cuèi cïng lµ (n, n-1, ..., 1). • Ta cÇn t™m c¸ch tõ mét ho¸n vÞ ®ang cã a = (a1, a2, ... , an) nÕu cha ph¶i lµ ho¸n vÞ cuèi cïng, ®a ra ho¸n vÞ kÕ tiÕp. Chap02-16 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Thuật toán sinh kế tiếp • Gi¶ sö a = (a1, a2, ... , an) lµ ho¸n vÞ cha ph¶i cuèi cïng, khi ®ã ho¸n vÞ kÕ tiÕp nã cã thÓ x©y dùng nhê thùc hiÖn c¸c biÕn ®æi sau: ΏTìm tõ ph¶i qua tr¸i ho¸n vÞ ®ang cã chØ sè j ®Çu tiªn tho¶ m·n aj < aj+1 (nãi c¸ch kh¸c: j lµ chØ sè lín nhÊt tho¶ m·n aj < aj+1); ΏTìm ak lµ sè nhá nhÊt cßn lín h¬n aj trong c¸c sè ë bªn ph¶i aj ; ΏĐổi chỗ aj víi ak ; ΏLËt ngîc ®o¹n tõ aj+1 ®Õn an . Chap02-17 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • Gi¶ sö ®ang cã ho¸n vÞ (3, 6, 2, 5, 4, 1), cÇn x©y dùng ho¸n vÞ kÕ tiÕp nã trong thø tù tõ ®iÓn. • Ta cã chØ sè j = 3 (a3 =2 < a4 = 5). • Sè nhá nhÊt cßn lín h¬n a3 trong c¸c sè bªn ph¶i cña a3 lµ a5 = 4. Đæi chç a3 víi a5 ta thu ®îc (3, 6, 4, 5, 2, 1), • Cuèi cïng, lËt ngîc thø tù ®o¹n a4 a5 a6 ta thu ®îc ho¸n vÞ kÕ tiÕp (3, 6, 4, 1, 2, 5). Chap02-18 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chương 2. Lý thuyết tổ hợp 2.1. Hoán vị 2.2. Tổ hợp (Combination) 2.3. Nguyên lý bù trừ 2.4. Công thức đệ qui và hàm sinh 2.5. Số Stirling 2.6. Nguyên lý các lồng chim bồ câu Chap02-19 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.2. Tổ hợp • 2.2.1. Tổ hợp • 2.2.2. Tổ hợp lặp • 2.2.3. Tính chất của hệ số tổ hợp • 2.2.4. Liệt kê Chap02-20 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.2.1. Tổ hợp (m-combination) • Định nghĩa. Ta gọi tổ hợp chập m từ n phần tử của X là bộ không có thứ tự gồm m thành phần, mỗi thành phầ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 tổ hợp chập m từ n phần tử là Cnm (đôi khi ta sẽ sử dụng ký hiệu C(n,m)) • Theo định nghĩa, một tổ hợp chập m từ n phần tử của X có thể biểu diễn bởi bộ không có thứ tự {a1, a2, ..., am}, ai Î X, i = 1, 2, ..., m, ai ¹ aj, i ¹ j. • Với giả thiết X={1, 2,...,n}, một tổ hợp chập m từ n phần tử của X có thể biểu diễn bởi bộ có thứ tự (a1, a2, ..., am), ai Î X, i = 1, 2, ..., m, 1 £ a1 < a2 < ...<am £ n. Chap02-21 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Tổ hợp • Định lý. • C(n,m) được gọi là hệ số tổ hợp. • Chứng minh. Gọi Q là tập hợp tất cả các chỉnh hợp không lặp chập m của n phần tử. ΏPhân Q thành các lớp sao cho hai chỉnh hợp thuộc cùng một lớp chỉ khác nhau về thứ tự. ΏRõ ràng các lớp này tạo thành một phân hoạch của tập Q và mỗi lớp như thế là tương ứng với một tổ hợp chập m của n. Ώ Số chỉnh hợp trong mỗi lớp là bằng nhau và bằng m! (số hoán vị). ΏSố các lớp là bằng số tổ hợp chập m của n: C(n,m). C n m = n! m!(nÿm)! (co the ky hieu la C(n,m) hay n m ÿ ÿ ÿ ÿ ÿ ÷) Chap02-22 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Tổ hợp • Theo nguyên lý cộng, ta có |Q| = m! C(n,m) suy ra n(n-1)...(n-m+1) = m! C(n,m). • Từ đó nhận được • Định lý được chứng minh. • Khi nhËn xÐt r»ng, gi¸ trÞ cña phÐp chia trong công thức của định lý lµ mét sè nguyªn, ta nhËn ®îc mét kÕt qu¶ lý thó trong sè häc: TÝch cña k sè tù nhiªn liªn tiÕp bao giê còng chia hÕt cho k!. ( 1)( 2)...( 1) ! ! !( )! m n n n n n m n C m m n m - - - + = = - Chap02-23 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • VÝ dô 1. Cã n ®éi bãng thi ®Êu vßng trßn. Hái ph¶i tæ chøc bao nhiªu trËn ®Êu? • Gi¶i: Cø 2 ®éi thi ̀ cã mét trËn. Tõ ®ã suy ra sè trËn ®Êu sÏ b»ng sè c¸ch chän 2 ®éi tõ n ®éi, nghÜa lµ b»ng C(n,2) = n(n-1)/2. • VÝ dô 2. Hái cã bao nhiªu giao ®iÓm cña c¸c ®êng chÐo cña mét ®a gi¸c låi n (n ³ 4) ®Ønh n»m ë trong ®a gi¸c, nÕu biÕt r»ng kh«ng cã ba ®êng chÐo nµo ®ång quy t¹i ®iÓm ë trong ®a gi¸c? • Gi¶i: Cø 4 ®Ønh cña ®a gi¸c thi ̀ cã mét giao ®iÓm cña hai ®- êng chÐo n»m trong ®a gi¸c. Tõ ®ã suy ra sè giao ®iÓm cÇn ®Õm lµ C(n,4) = n(n-1)(n-2)(n-3)/24. Chap02-24 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.2.2. Tổ hợp lặp. Bài toán chia kẹo Xét bài toán: "Giả sử k và n là các số nguyên không âm. Hỏi phương trình sau đây có bao nhiêu nghiệm? Nội dung thực tế: Cần chia n cái kẹo cho k em bé B1, B2, ,Bk. Hỏi có bao nhiêu cách chia khác nhau? Chap02-25 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Bài toán chia kẹo • Cần thả n quả bóng giống nhau vào k phòng: Room1, Room2, , Roomk. Hỏi có bao nhiêu cách phân bổ khác nhau? • Nếu gọi tj là số lượng quả bóng thả vào Roomj, j = 1, 2, ..., n; thì vấn đề đặt ra dẫn về bài toán: Hỏi phương trình sau đây có bao nhiêu nghiệm nguyên không âm? Chap02-26 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội • Xét dãy n+k-1 hộp. Tô k-1 hộp nào đó bởi màu xám; các hộp xám này sẽ là vách ngăn: D1, D2, D(k-1). • Ví dụ: với n=16, k=6 • Thả n quả bóng vào n hộp còn lại, mỗi hộp 1 quả. Giải bài toán chia kẹo D1 D2 D3 D5D4 Chap02-27 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội • Ví dụ, với n=16, k=6 • Thả các quả bóng trước vách ngăn D1 vào Room1, các quả bóng giữa vách ngăn D1 và D2 vào Room2, vân vân, và cuối cùng các quả bóng sau D(k-1) vào Room(k). Giải bài toán chia kẹo Room1 Room2 Room3 Room4 Room5 Room6 D1 D2 D3 D5D4 Chap02-28 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội • Như vậy, rõ ràng tồn tại tương ứng 1-1 giữa một cách phân bổ các quả bóng và một cách chọn k-1 hộp trong số n+k-1 hộp làm vách ngăn. • Do có tất cả cách chọn k-1 hộp từ n+k-1 hộp, nên đó cũng chính là số cách phân bổ n quả bóng vào k phòng, cũng chính là số cách chia n cái kẹo cho k em bé và cũng chính là số nghiệm nguyên không âm của phương trình: t1 + t2 + . . . + tk = n. • Con số nói trên cũng được gọi là số tổ hợp lặp chập k từ n (k- combination with repetition from n elements). Giải bài toán chia kẹo 1 1 k n k C - + - Chap02-29 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội • Bài toán chia kẹo 2: Có bao nhiêu cách chia n cái kẹo cho k em bé mà trong đó mỗi em được ít nhất một cái? Hay tương đương: Hỏi phương trình sau đây : t1 + t2 + ... + tk = n. có bao nhiêu nghiệm nguyên dương? • Trước hết chia cho mỗi em 1 cái kẹo, n-k cái kẹo còn lại sẽ được chia cho k em bé. Bài toán dẫn về: Hỏi có bao nhiêu cách chia n-k cái kẹo cho k em bé. Sử dụng kết quả bài trước, ta có đáp số cần tìm là Giải bài toán chia kẹo 1 1 k n C - - Chap02-30 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.2.3. Tính chất của hệ số tổ hợp • Díi ®©y lµ mét vµi tÝnh chÊt cña c¸c hÖ sè tæ hîp: a) Đèi xøng C(n,m) = C(n,n-m) b) ĐiÒu kiÖn ®Çu C(n,0) = 1; C(n,n) = 1, n ³ 0 c) C«ng thøc ®Ö qui C(n,m) = C(n-1,m) + C(n-1, m-1), n > m > 0 • Điều kiện đầu suy trực tiếp từ định nghĩa của hệ số tổ hợp. C¸c tính chất còn lại có thể chứng minh nhờ sử dụng công thức trong định lý 4. Chap02-31 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Tam giác PASCAL • Tõ b) vµ c), ta cã thÓ tÝnh tÊt c¶ c¸c hÖ sè tæ hîp chØ b»ng phÐp céng. C¸c hÖ sè nµy ®îc tÝnh vµ viÕt lÇn lît theo tõng dßng (mçi dßng øng víi mét gi¸ trÞ n=0, 1, ...), trªn mçi dßng chóng ®îc tÝnh vµ viÕt lÇn lît theo tõng cét (mçi cét øng víi mét gi¸ trÞ m = 0, 1, ..., n) theo b¶ng tam gi¸c díi ®©y: B¶ng nµy ®îc gäi lµ tam gi¸c Pascal. m Chap02-32 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Tam giác PASCAL • Tam giác Pascal, n=8 Chap02-33 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Tam giác PASCAL • Mỗi số trong ô lục giác bằng tổng của hai số của hai ô chung cạnh ở phía trên nó Chap02-34 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Khai triển nhị thức • C¸c hÖ sè tæ hîp cã liªn quan chÆt chÏ víi viÖc khai triÓn luü thõa cña mét nhÞ thøc. ThËt vËy, trong tÝch (x+y)n = (x+y) (x+y) . . . (x+y) hÖ sè cña xm yn-m sÏ lµ sè c¸ch chän m nh©n tö (x + y) mµ tõ ®ã ta lÊy ra x vµ ®ång thêi trong n-m nh©n tö cßn l¹i ta lÊy ra y, nghÜa lµ 0 0 ... ...( ) = n n n m nm m n n n n n i i n i n i xx y y yC C x C C x y - - = = + + + ++ å C«ng thøc trên ®îc gäi lµ khai triÓn nhÞ thøc Newton vµ c¸c hÖ sè tæ hîp cßn ®îc gäi lµ c¸c hÖ sè nhÞ thøc. Chap02-35 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Tổng quát hóa • Định lý khai triển nhị thức có thể tổng quát cho trường hợp phải khai triển lũy thừa của tổng nhiều hơn hai số hạng. Khi khai triển (x+y+z)n, ta có n!/(i!´j!´k!) cách tạo ra số hạng chứa i thừa số là x, j thừa số là y và k thừa số là z. Vì thế số này chính là hệ số của số hạng xi yj zk trong khai triển đang xét. • Ví dụ: Xét khai triển (x+y+z)7. Hệ số của xy2z4 là số cách tạo ra số hạng dạng xyyzzzz. Số đó là bằng 7! / (1!™2!™4!) = 105. Chap02-36 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Multinomials Xét cách xây dựng dãy gồm n đối tượng từ k loại đối tượng sao cho trong đó có n1 đối tượng loại 1, n2 đối tượng loại 2,..., nk đối tượng loại k (n1++nk = n). Ký hiệu C(n; n1,...,nk) là số cách tạo dãy như vậy. Số này được gọi là hệ số bội thức (multinomial). Định lý. CM. Ta lần lượt chọn các đồ vật. Đồ vật loại 1 có C(n,n1) cách chọn. Sau khi đồ vật 1 đã chọn, đồ vật loại 2 có C(n-n1,n2) cách chọn, ..., cuối cùng đồ vật loại k có C(nk,nk) cách chọn. Theo nguyên lý nhân C(n; n1,...,nk) = C(n,n1)´C(n-n1,n2)´ ...´C(nk,nk), từ đó suy ra kết quả cần chứng minh. æ ö = =ç ÷ è ø 1 1 2 1 2 ! ( ; ,..., ) , ,..., ! !.... ! k k k n n C n n n n n n n n n Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Multinomials Khi k=2 ta có hệ số nhị thức C(n,n1). Có thể chứng minh bằng cách khác: Nếu các đối tượng là không phân biệt thì có n! cách. Chúng ta đã tính lặp lại n1!´´nk! lần, từ đó suy ra định lý. Ví dụ: Có bao nhiêu từ gồm 11chữ cái lấy từ 11 chữ cái của từ “MISSISSIPPI”? Giải: Trong từ “MISSISSIPPI” có tất cả có 1 chữ cái “M”, 4 chữ “I”, 4 chữ “S”, và 2 chữ “P”. Ta xét cách xếp vị trí cho các chữ cái này trong từ cần xây dựng. Có C(11,1) vị trí để xếp "M", tiếp đến có C(10,4) để xếp vị trí cho 4 chữ "I", 4 chữ "S" được xếp vào 6 vị trí còn lại bởi C(6,4) cách và cuối cùng có C(2,2) cách xếp 2 chữ "P". Theo nguyên lý nhân có: C(11,1)™C(10,4)™C(6,4)™C(2,2) = 11!/(1! 4! 4! 2!) = 34650. Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Tổ hợp • Trong c«ng thøc Niuton đặt y=1 ta có: (*) • RÊt nhiÒu ®¼ng thøc vÒ hÖ sè tæ hîp ®îc suy tõ (*). Ch¼ng h¹n, trong (*) chän x =1 ta ®îc: C(n,0) + C(n,1) + ...+ C(n,n) = 2n, tøc lµ nhËn ®îc kÕt qu¶ ®· biÕt: sè c¸c tËp con cña mét n-tËp b»ng 2n, cßn nÕu chän x = -1 ta ®îc: C(n,0) – C(n,1) + C(n,2) - ...+(-1)nC(n,n) = 0, tøc lµ sè c¸c tËp con ch½n (cã sè phÇn tö lµ sè ch½n) b»ng c¸c sè tËp con lÎ vµ b»ng 2n-1. • Nhiều tính chất của hệ số tổ hợp có thể thu được từ (*) bằng cách lấy đạo hàm hoặc tích phân theo x hai vế của đẳng thức này một số hữu hạn lần, sau đó gán cho x những giá trị cụ thể. 0 1 1 1...(1 ) n nn n n n n n nx xx C C C x C - -= + + + ++ Chap02-39 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.2.4. Liệt kê m-tập con • Bµi to¸n ®Æt ra lµ: Cho X = {1, 2, ... , n}. H·y liÖt kª c¸c tËp con m phÇn tö cña X. • Mçi tËp con m phÇn tö cña X cã thÓ biÓu diÔn bëi bé cã thø tù gåm m thµnh phÇn a = (a1, a2, ... , am) tho¶ m·n ai Î X , i = 1, 2,..., m ; a1 < a2 < ... < am • Xét hai phương pháp liệt kê tất cả m-tập con của X: ΏCây liệt kê ΏThuật toán sinh m-tập con Chap02-40 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2 2.2.4. Cây liệt kê m-tập con • Cây liệt kê. Ví dụ, liệt kê các tập con 3 phần tử của {1,...,5} Chap02-41 1 3 32 3 4 3 4 4 4 5 - 4 5 5 123 124 125 Thành phần thứ 1 Thành phần thứ 2 Thành phần thứ 3 54 5 5 134 135 145 234 235 245 345 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 42 Thuật toán sinh m-tập con • Mçi tËp con m phÇn tö cña X cã thÓ biÓu diÔn bëi bé cã thø tù gåm m thµnh phÇn a = (a1, a2, ... , am) tho¶ m·n ai Î X , i = 1, 2,..., m ; a1 < a2 < ... < am • Tríc hÕt ta ®a vµo quan hÖ thø tù tõ ®iÓn trên tập tất cả m- tập con của X : • Ta nãi tËp con a = (a1, a2,..., an) ®i tríc tËp con a' = (a'1, a'2, ... , a'n) trong thø tù tõ ®iÓn vµ ký hiÖu lµ a p a', nÕu tìm ®îc chØ sè k (1 £ k £ m) sao cho: a1 = a'1 , a2 = a'2, ... , ak-1 = a'k-1, ak < a'k . Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • C¸c tËp con 3 phÇn tö cña X = {1, 2, 3, 4, 5} ®îc liÖt kª theo thø tù tõ ®iÓn nh sau 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 Chap02-43 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Thuật toán sinh kế tiếp • TËp con ®Çu tiªn trong thø tù tõ ®iÓn lµ (1, 2, ... , m) • TËp con cuèi cïng lµ (n-m+1, n-m+2, ..., n). • Gi¶ sö a=(a1, a2, ... , am) lµ tËp con ®ang cã cha ph¶i cuèi cïng, khi ®ã tËp con kÕ tiÕp trong thø tù tõ ®iÓn cã thÓ x©y dùng b»ng c¸ch thùc hiÖn c¸c quy t¾c biÕn ®æi sau ®èi víi tËp ®ang cã: ΏTìm từ bên phải dãy a1, a2,..., am phÇn tö ai ¹ n-m+i, ΏThay ai bëi ai + 1; ΏThay aj bëi ai + j - i, víi j = i+1, i+2,..., m. Chap02-44 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • Ví dụ: n = 6, m = 4. Giả sử đang có tập con (1, 2, 5, 6), cần xây dựng tập con kế tiếp nó trong thứ tự từ điển. • 1 2 5 6 3 4 5 6 (tập con cuối cùng) • Ta có i=2, thay a2 = 3, và a3 = 4, a4 = 5, ta được tập con kế tiếp (1, 3, 4, 5). Chap02-45 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chương 2. Lý thuyết tổ hợp 2.1. Hoán vị 2.2. Tổ hợp (Combination) 2.3. Nguyên lý bù trừ 2.4. Công thức đệ qui và hàm sinh 2.5. Số Stirling 2.6. Nguyên lý các lồng chim bồ câu Chap02-46 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.3. Nguyên lý bù trừ (The inclusion-exclusion principle) 2.3.1. Phát biểu nguyên lý 2.3.2. Các ví dụ áp dụng Chap02-47 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.3.1. Phát biểu nguyên lý • Nguyên lý bù trừ trong trường hợp hai tập: |A È B| = |A| + |B| - |A Ç B| (1) Ví dụ: Giả sử A có 5 phần tử, B có 4 phần tử và có 2 phần tử thuộc vào cả A lẫn B. Khi đó số phần tử của hợp hai tập là 5+4-2 = 7, chứ không phải là 5+4 = 9. • CM: Chap02-48 A B U 1 lần 2 lần AÇB Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nguyên lý bù trừ • Mở rộng cho trường hợp 3 tập: Giả sử A, B, C là ba tập bất kỳ. Khi đó: |AÈB ÈC| = |(A ÈB)ÈC)| = |AÈB| + |C| - |(AÈB)ÇC| = |A| +|B| + |C| - |AÇB| - |(AÇC)È(BÇC)| = |A| +|B| + |C| - |AÇB| - |AÇC|- |BÇC)|+ |AÇBÇC)| Vậy |AÈBÈC| = |A| +|B| + |C| - |AÇB| - |AÇC|- |BÇC)|+ |AÇBÇC)| (2) Chap02-49 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nguyên lý bù trừ |AÈB ÈC| = |A| +|B| + |C| - |AÇB| - |AÇC|- |BÇC)|+ |AÇBÇC)| (2) Có thể chứng minh bằng lập luận trực tiếp: • Trong tổng của ba số hạng đầu tiên các phần tử chung của A và B được tính hai lần, vì vậy phải trừ bớt đi một lần. Tương tự như vậy đối với các phần tử chung của A và C và các phần tử chung của B và C. • Thế nhưng, trừ như vậy là hơi quá, bởi vì những phần tử chung của cả ba tập A, B và C chưa được tính đến trong tổng của 6 số hạng đầu tiên. Vì vậy phải cộng bù lại. Chap02-50 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ minh họa • Giả sử mỗi hình tròn có diện tích là 4. Giao của hai hình tròn có diện tích 2, Giao của cả ba hình tròn có diện tích 1. Hỏi tổng diện tích bị phủ bởi ba hình tròn là bao nhiêu? • A=4+4+4 – 2 -2 -2 + 1 = 12 – 6 + 1 = 7. Chap02-51 A C ÇA B ÇA C ÇB C Ç ÇA B C U dt = 2-1=1 dt = 1 dt = 4-3=1 | | | | | | | | | | | | | | | |È È = + + - Ç - Ç - Ç + Ç ÇA B C A B C A B B C C A A B C Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội • §Þnh lý. Gi¶ sö A1, A2, ... , Am lµ c¸c tËp h÷u h¹n. Khi ®ã trong ®ã (Nk lµ tæng sè phÇn tö cña tÊt c¶ c¸c tËp lµ giao cña k tËp lÊy tõ m tËp ®· cho, nãi riªng N1 = N(A1) + ... + N(Am), Nm = N(A1 Ç A2 Ç ... Ç Am) ). Nguyên lý bù trừ 1 2 1 21 ... ( ... ), 1,2,..., k k k i i i i i i m N N A A A k m £ < < < £ = Ç Ç Ç =å 1 1 2 1 2( ... ) ... ( 1) m m mN A A A N N N -È È È = - + + - Chap02-52 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nguyên lý bù trừ • Chøng minh. • Chó ý r»ng, sè c¸c giao cña k tËp lÊy tõ m tËp b»ng C(m,k), k=1,2,..., m. • §Ó chøng minh c«ng thøc cña nguyªn lý bï trõ, ta sÏ tÝnh xem mçi phÇn tö cña tËp A1 È A2 È . . . È Am ®îc ®Õm bao nhiªu lÇn trong vÕ ph¶i: • XÐt mét phÇn tö tuú ý a Î A1 È A2 È . . . È Am. Gi¶ sö a lµ phÇn tö cña k tËp trong sè m tËp ®· cho. Khi ®ã a ®îc ®Õm ë vÕ ph¶i cña c«ng thøc C(k,1) – C(k,2)+ ... + (-1)k-1C(k,k) lÇn. Do C(k,1) – C(k,2)+ ... + (-1)k-1C(k,k) = 1 – [C(k,0) – (C(k,1) – C(k,2)+ ... + (-1)k-1C(k,k))] = 1 – (1 – 1)k = 1 Tõ ®ã suy ra ®¼ng thøc cÇn chøng minh lµ ®óng Chap02-53 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nguyên lý bù trừ • B©y giê ta ®ång nhÊt tËp Ak víi tÝnh chÊt Ak cho trªn mét tËp X nµo ®ã vµ ®Õm xem cã bao nhiªu phÇn tö cña X kh«ng tho¶ m·n bÊt cø mét tÝnh chÊt Ak nµo c¶. • Gäi`N lµ sè cÇn ®Õm. Do A1 È A2 È . . . È Am lµ tËp tÊt c¶ c¸c phÇn tö cña X tho¶ m·n Ýt nhÊt mét trong sè m tÝnh chÊt ®· cho, nªn ta cã: `N = N(X ) N(A1 È A2 È . . . È Am) = N(X )  N1 + N2 -...+( 1) mNm trong ®ã Nk lµ tæng c¸c phÇn tö cña X tho¶ m·n k tÝnh chÊt lÊy tõ m tÝnh chÊt ®· cho. • C«ng thøc thu ®îc cho phÐp tÝnh`N qua c¸c Nk trong trêng hîp c¸c sè nµy dÔ tÝnh to¸n h¬n. Chap02-54 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Các ví dụ áp dụng • VÝ dô 1. Hái trong tËp X = {1, 2, ..., 10000} cã bao nhiªu sè kh«ng chia hÕt cho bÊt cø sè nµo trong c¸c sè 3, 4, 7? • Gi¶i. Gäi Ai ={ x Î X : x chia hÕt cho i} , i = 3, 4, 7. • Khi ®ã A3 È A4 È A7 lµ tËp c¸c sè trong X chia hÕt cho Ýt nhÊt mét trong 3 sè 3, 4, 7, suy ra sè lîng c¸c sè cÇn ®Õm sÏ lµ N(X) – N(A3 È A4 È A7) = 10000 – (N1– N2 + N3). • Ta cã N1 = N(A3) + N(A4) + N(A7) = [10000/3] + [10000/4] + [10000/7] = 3333 + 2500 + 1428 =7261, Chap02-55 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ N2 = N(A3 Ç A4) + N(A3 Ç A7) + N(A4 Ç A7) = [10000/(3´4)] + [10000/(3´7)] + [10000/(4´7)] = 833 + 476 + 357 = 1666, N3 = N(A3 Ç A4 Ç A7) = [10000/(3´4´7) ] = 119, ë ®©y ký hiÖu [ r ] ®Ó chØ sè nguyªn lín nhÊt kh«ng vît qu¸ r. • Tõ ®ã sè lîng c¸c sè cÇn ®Õm lµ 10000 - 7261 + 1666 - 119 = 4286. Chap02-56 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • VÝ dô 2. Cã bao nhiªu x©u nhÞ ph©n ®é dµi 10 hoÆc lµ b¾t ®Çu bëi 00 hoÆc lµ kÕt thóc bëi 11? • Gi¶i. Ta cã ΏSè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 lµ 28 = 256 ΏSè x©u nhÞ ph©n ®é dµi 10 kÕt thóc bëi 11 lµ 28 = 256. ΏSè x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi 00 vµ kÕt thóc bëi 11 lµ 26 = 64. • Theo nguyªn lý bï trõ suy ra sè x©u nhÞ ph©n hoÆc b¾t ®Çu bëi 00 hoÆc kÕt thóc bëi 11 lµ 256 + 256 - 64 = 448. Chap02-57 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 3 • Ví dụ 3. Đếm số nghiệm nguyên không âm của phương trình x1 + x2 + x3 = 11, thỏa mãn x1 £ 3, x2 £ 4, x3 £ 6. • Giải. Xét các tính chất P1: x1 > 3 ; P2: x2 > 4; P3: x3 > 6. • Lời giải cần đếm là lời giải không thỏa mãn bất cứ tính chất nào trong P1, P2, P3. Theo nguyên lý bù trừ số lượng lời giải cần đếm là bằng N – N1 + N2 – N3. • Ta cần tính các số N, N1 , N2 , N3. • Tổng số nghiệm nguyên không âm của phương trình là bằng N = C(3+11–1, 11) = 78. Chap02-58 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 3 • Để đếm số lời giải thỏa mãn tính chất x1 > 3 ta lập luận như sau: Đổi biến y1 = x1 - 4, số nghiệm nguyên không âm của phương trình x1 + x2 + x3 = 11 thỏa mãn tính chất x1 > 3 chính là bằng số nghiệm nguyên không âm của phương trình y1 + x2 + x3 = 11 – 4 = 7. Vậy N(P1) = C(3+7–1,7) = 36. • Tương tự như vậy ta có • Số lời giải thỏa mãn tính chất x2>4: N(P2) = C(3+6-1,6) = 28. • Số lời giải thỏa mãn tính chất x3>6: N(P3) = C(3+4-1,4) = 15. • Số lời giải thỏa mãn tính chất x1>3 và x2>4: N(P1ÇP2)=C(3+2-1,2)=6. • Số lời giải thỏa mãn tính chất x1>3 và x3>6: N(P1ÇP3)=C(3+0-1,0)=1. • Số lời giải thỏa mãn tính chất x2>4 và x3>6: N(P2ÇP3)=0. • Số lời giải thỏa mãn tính chất x1>3, x2>4 và x3>6: N(P1ÇP2ÇP3)=0. • Ta thu được số lượng lời giải thỏa mãn điều kiện đầu bài là 78 – 36 – 28 –15 + 6 + 1 + 0 – 0 = 6. Chap02-59 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Bài toán bỏ thư • Bµi to¸n bá th. Cã n l¸ th vµ n phong b× ghi s½n ®Þa chØ. Bá ngÉu nhiªn c¸c l¸ th vµo c¸c phong b×. Hái x¸c suÊt ®Ó x¶y ra kh«ng mét l¸ th nµo bá ®óng ®Þa chØ lµ bao nhiªu? • Gi¶i: §¸nh sè c¸c l¸ th tõ 1 ®Õn n, c¸c phong b× t¬ng øng víi chóng còng ®îc ®¸nh sè tõ 1 ®Õn n. Mçi c¸ch bá th vµo phong b× cã thÓ biÓu diÔn bëi bé cã thø tù (p1, p2, ..., pn), trong ®ã pi lµ phong b× bá l¸ thø thø i. Tõ ®ã suy ra tån t¹i t- ¬ng øng 1-1 gi÷a mét c¸ch bá th vµo phong b× víi mét ho¸n vÞ cña n sè. VËy cã tÊt c¶ n! c¸ch bá th. Chap02-60 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nguyên lý bù trừ: Bài toán bỏ thư • VÊn ®Ò cßn l¹i lµ ®Õm sè c¸ch bá th sao cho kh«ng cã l¸ th nµo ®óng ®Þa chØ. • Gäi X lµ tËp hîp tÊt c¶ c¸c c¸ch bá th vµ Ak lµ tÝnh chÊt l¸ th thø k bá ®óng ®Þa chØ. Khi ®ã, theo nguyªn lý bï trõ ta cã: `N = N(X )  N1 + N2  ...+( 1)nNn trong ®ã`N lµ sè cÇn t×m, N(X) = n!, cßn Nk lµ sè tÊt c¶ c¸c c¸ch bá th sao cho cã k l¸ th ®óng ®Þa chØ. Chap02-61 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nguyên lý bù trừ: Bài toán bỏ thư • Chó ý lµ nghÜa lµ, Nk lµ tæng theo mäi c¸ch lÊy k l¸ th tõ n l¸, víi mçi c¸ch lÊy k l¸ th, cã (n-k)! c¸ch bá trong ®ã k l¸ nµy ®óng ®Þa chØ, ta nhËn ®îc: Nk = C(n, k).(n-k)! = n! / k! • Do ®ã • VËy x¸c suÊt cÇn t×m lµ: N n n n = - + - + - ! ( ! ! ... ( ) ! )1 1 1 1 2 1 1 1 1 1 2 1 - + - + - ! ! ... ( ) ! n n 1 2 1 21 ... ( ... ), 1,2,..., k k k i i i i i i n N N A A A k n £ < < < £ = Ç Ç Ç =å Chap02-62 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nguyên lý bù trừ • Mét ®iÒu lý thó lµ x¸c suÊt nµy dÇn ®Õn e-1 (nghÜa lµ cßn lín h¬n 1/3) khi n kh¸ lín. Sè thu ®îc trong bµi to¸n trªn ®îc gäi lµ sè mÊt thø tù (number of derangements) vµ ®îc ký hiÖu lµ Dn. • Díi ®©y lµ mét vµi gi¸ trÞ cña Dn, cho ta thÊy Dn t¨ng nhanh nh thÕ nµo khi n t¨ng: Chap02-63 n 2 3 4 5 6 7 8 9 10 11 Dn 1 2 9 44 265 1854 14833 133496 1334961 4890741 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Số lượng toàn ánh A f B Không tồn tại điểm không có mũi tên đi vào Toàn ánh: Ánh xạ f từ A vào B là toàn ánh nếu với mỗi phần tử b thuộc B đều tìm được a thuộc A sao cho f(a)=b. Giả sử A={a1, a2, ..., am } và B={b1, b2, ..., bn }, m ³ n. Hỏi có bao nhiêu toàn ánh từ A vào B? Ta muốn tất cả bi đều thuộc miền giá trị của f. Gọi Pi là tính chất "bi không nằm trong miền giá trị của f ". Khi đó ta cần đếm số ánh xạ không có bất cứ tính chất nào trong số các tính chất P1,..., Pn. Ký hiệu: Pi = tập các ánh xạ từ A vào B có tính chất Pi , i=1, 2, ...,n. Chap02-64 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Số lượng toàn ánh • Theo nguyên lý bù trừ số lượng toàn ánh cần đếm là: N – N1 + N2 – ... +(–1)n Nn. • Ta có: ΏN - số ánh xạ từ m-tập A vào n-tập B: nm ΏDo N(Pi) - số ánh xạ không có bi trong miền giá trị, nên N(Pi) = (n-1) m, do đó N1 = C(n,1) (n-1)m ΏDo N(PiÇPj) - số ánh xạ không có bi và bj trong miền giá trị, nên N(PiÇPj) = (n-2)m , do đó N2 = C(n,2) (n-2)m. ΏTổng quát ta có dó đó Nk = C(n,k) (n - k)m. • Từ đó ta có số lượng toàn ánh là: nm – C(n,1)(n-1)m + C(n,2)(n-2)m – ...+ (-1)n-1C(n,n-1)1m. Chap02-65 1 2 ( ... ) ( ) k m i i i N P P P n kÇ Ç Ç = - 1 2 1 21 ... ( ... ), 1,2,..., k k k i i i i i i n N N P P P k n £ < < < £ = Ç Ç Ç =å Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Số lượng toàn ánh • Ta viết gọn công thức nm – C(n,1)(n-1)m + C(n,2)(n-2)m – ...+ (-1)n-1C(n,n-1)1m. dưới dạng sau đây: Chap02-66 1 2 0 1 1 0 1 2 1 1 ( 1) ( 2) ... ( 1) 1 ( 1) ( ( 0) ( 1) ( 2) ... ( 1) 1 ( 1) ) 0 m m m n n m n n n m m n k k m m n n m n n m n n n n n n k n C n C n C C C n k n C n C n C C - - - = - - - + - - + - = - - - + - - + - + = - - - å Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chương 2. Lý thuyết tổ hợp 2.1. Hoán vị 2.2. Tổ hợp (Combination) 2.3. Nguyên lý bù trừ 2.4. Công thức đệ qui và hàm sinh 2.5. Số Stirling 2.6. Nguyên lý các lồng chim bồ câu Chap02-67 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4 Công thức đệ qui và hàm sinh 2.4.1. Xây dựng công thức đệ qui 2.4.2. Giải công thức đệ qui 2.4.3. Hàm sinh và công thức đệ qui Chap02-68 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1. Xây dựng công thức đệ qui • Công thức đệ qui là công thức cho phép tính giá trị của các đại lượng theo từng bước, dựa vào các giá trị tính ở các bước trước và một số giá trị đầu. • Là một kỹ thuật quan trọng cho phép giải nhiều bài toán đếm Chap02-69 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Ví dụ 1. Công thức đệ qui cho C(n,k) - số lượng tập con k phần tử của tập n phần tử X. • Theo định nghĩa C(n,0) = 1 và C(n,n) = 1 (1) • Giả sử n > k > 0, ta xây dựng công thức đệ qui để tính C(n,k). Cố định một phần tử x Î X. Phân tập các tập con k phần tử của X ra thành 2 tập: ΏA – tập các tập con k phần tử có chứa x; ΏB – tập các tập con k phần tử không chứa x. • Rõ ràng A và B tạo thành phân hoạch của tập tất cả các tập con k phần tử của X. Chap02-70 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Rõ ràng A và B tạo thành phân hoạch của tập tất cả các tập con k phần tử của X. Do đó, theo nguyên lý cộng: C(n,k) = |A| + |B|. • Ta có: ΏDo mỗi tập con trong A có chứa x, nên k-1 phần tử còn lại của nó là một tập con k-1 phần tử của tập X \ {x}, suy ra |A| = C(n-1,k-1) ΏTương tự như vậy, |B| = C(n-1, k) • Vậy, C(n,k) = C(n-1, k-1) + C(n-1,k), n > k > 0 (2) Chap02-71 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Công thức đệ qui (2) cùng với điều kiện đầu (1) cho phép tính giá trị của C(n, k) với mọi giá trị của n và k. • Công thức đệ qui (2) cho phép viết hàm đệ qui sau đây để tính giá trị của C(n,k): function C(n,k: integer): longint; begin if (k=0) or (k=n) then C:=1 else C:= C(n-1,k-1) + C(n-1,k); end; Chap02-72 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Hàm vừa xây dựng không cho một cách tính hiệu quả. Thực vậy, nếu gọi C*(n,k) là số phép toán “gán giá trị” phải thực hiện bởi lệnh gọi hàm C(n,k), dễ thấy C*(n,0) =1; C*(n,n) = 1 C*(n,k) = C*(n-1, k-1) + C*(n-1,k)+1, n > k > 0 tức là C*(n,k) thoả mãn công thức đệ qui như hệ số tổ hợp C(n, k), do đó: C*(n,k) ~ n!/[k!(n-k)!] và giá trị này là rất lớn khi n lớn và k = n/2. • Dễ dàng xây dựng một hàm lặp để tính giá trị của C(n, k) một cách hiệu quả hơn. Chap02-73 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • VÝ dô 2. Trªn mÆt ph¼ng, kÎ n ®êng th¼ng sao cho kh«ng cã 2 ®êng nµo song song vµ 3 ®êng nµo ®ång quy. Hái mÆt ph¼ng ®îc chia thµnh mÊy phÇn ? • Gi¶i: Gäi sè phÇn mÆt ph¼ng ®îc chia bëi n ®êng th¼ng lµ Sn. Râ ràng S1 = 2, (3) • XÐt n > 1, ta tìm c«ng thøc ®Ö qui cho Sn. • Gi¶ sö ®· kÎ n-1 ®êng th¼ng, khi ®ã mÆt ph¼ng ®îc chia ra lµm Sn-1 phÇn. B©y giê kÎ thªm ®êng th¼ng thø n. Đêng th¼ng nµy c¾t n-1 ®êng th¼ng ®· vÏ t¹i n- 1 giao ®iÓm. C¸c giao ®iÓm nµy chia ®êng th¼ng thø n ra lµm n phÇn, mçi phÇn nh vËy sÏ chia mét phÇn nµo ®ã sinh bëi n-1 ®êng th¼ng vÏ tríc ®ã ra lµm hai phÇn. Tõ ®ã suy ra, sau khi vÏ ®êng th¼ng thø n sè phÇn tăng thªm lµ n. Tõ ®ã nhËn ®îc c«ng thøc ®Ö qui Sn = Sn-1 + n, n ³ 2 (4) Chap02-74 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội G41 G21 G32 2.4.1 Xây dựng công thức đệ qui l1 l2 l3 l4 G11 G22 G31 phần 1 phần 2 phần 3 phần 4 Chap02-75 G42 G12 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Để tìm công thức trực tiếp, ta cộng các hệ thức Sk = Sk-1 + k víi k = 2, ..., n. S1 = 2 S2 = S1 + 2 S3 = S2 + 3 ... Sn-1= Sn-2 + (n-1) Sn = Sn-1 + n Sn = 2 + 2 + 3 + ...+(n-1) + n = n(n+1)/2 + 1 = (n 2+n+2)/2 Chap02-76 Phương pháp thế: Sn = Sn-1+n = Sn-2+(n-1)+n = Sn-3 +(n-2)+(n-1) +n = .... = S1+2+3+....+(n-1)+n = 2+2+3+....+(n-1)+n Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Ví dụ 3. Xây dựng công thức đệ qui cho fn là số chỉnh hợp lặp chập n từ hai phần tử 0, 1 (cũng chính là xâu nhị phân độ dài n) không chứa hai số 0 liền nhau. • Giải. Ta có f1 = 2; f2 = 3 Giả sử n > 2. Phân tập các chỉnh hợp cần đếm ra thành 2 tập: ΏA – tập các chỉnh hợp cần đếm chứa 1 ở vị trí đầu tiên; ΏB – tập các chỉnh hợp cần đếm chứa 0 ở vị trí đầu tiên; • Rõ ràng A và B tạo thành phân hoạch của tập tất cả các chỉnh hợp cần đếm. Chap02-77 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Do đó, theo nguyên lý cộng: fn = |A| + |B|. • Ta có: ΏDo mỗi chỉnh hợp trong A chứa 1 ở vị trí đầu tiên, nên n-1 phần tử còn lại sẽ tạo thành một chỉnh hợp cần đếm độ dài n-1, suy ra |A| = fn-1 ΏDo mỗi chỉnh hợp trong B chứa 0 ở vị trí đầu tiên, nên vị trí thứ hai của nó phải là 1 còn n-2 phần tử còn lại sẽ tạo thành một chỉnh hợp cần đếm độ dài n-2, suy ra |B| = fn-2 • Vậy, ta thu được công thức đệ qui f1 = 2; f2 = 3; fn = fn-1 + fn-2, n > 2 (5) Chap02-78 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Ví dụ 4. Xây dựng công thức đệ qui cho Qn là số lượng cách phủ lưới ô vuông kích thước 2´n bằng các quân bài domino. • Giải. Ta có Q1 = 1; Q2 = 2 (xem hình vẽ) • Giả sử n > 2. Phân tập các cách phủ cần đếm ra thành 2 tập: ΏA – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi quân bài nằm đứng; ΏB – tập các cách phủ trong đó ô ở góc trên trái được phủ bởi quân bài nằm ngang. • Rõ ràng A và B tạo thành phân hoạch của tập tất cả các cách phủ cần đếm. Chap02-79 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Do đó, theo nguyên lý cộng: Qn = |A| + |B|. • Ta có: Ώ|A| = Qn-1 Ώ|B| = Qn-2 • Vậy, ta thu được công thức đệ qui Q1 = 1; Q2 = 2; Qn = Qn-1 + Qn-2, n > 2 (6) ... ... ... ... A B Chap02-80 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Ví dụ 5. (Bài toán tháp Hà nội). Trò chơi tháp Hà nội được trình bày như sau: “Có 3 cọc a, b, c. Trên cọc a có một chồng gồm n cái đĩa đường kính giảm dần từ dưới lên trên. Cần phải chuyển chồng đĩa từ cọc a sang cọc c tuân thủ qui tắc: mỗi lần chỉ chuyển 1 đĩa và chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn. Trong quá trình chuyển được phép dùng cọc b làm cọc trung gian”. • Bài toán đặt ra là: Tìm công thức đệ qui cho hn là số lần di chuyển đĩa ít nhất cần thực hiện để hoàn thành nhiệm vụ đặt ra trong trò chơi tháp Hà nội. Chap02-81 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Gi¶i: Râ rµng: h1 = 1. • Gi¶ sö n ≥ 2. ViÖc di chuyÓn ®Üa gåm c¸c bíc: (i) ChuyÓn n-1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm trung gian. Bíc nµy ®îc thùc hiÖn nhê gi¶ thiÕt quy n¹p. (ii) ChuyÓn 1 ®Üa (®Üa víi ®êng kÝnh lín nhÊt) tõ cäc a ®Õn cäc c. (iii) ChuyÓn n-1 ®Üa tõ cäc b ®Õn cäc c (sö dông cäc a lµm trung gian). Bíc nµy ®îc thùc hiÖn nhê gi¶ thiÕt quy n¹p. Chap02-82 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Bíc (i) vµ (iii) ®ßi hái gi¶i bµi to¸n th¸p Hµ néi víi n-1 ®Üa, vì vËy sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc hiÖn trong hai bíc nµy lµ 2hn-1. Do ®ã ta cã c«ng thøc ®Ö qui sau: hn = 2hn-1 + 1, n ≥ 2. • Sö dông c«ng thøc ®Ö qui vµ ®iÒu kiÖn ®Çu võa tìm ®îc ®èi víi hn ta cã thÓ dÔ dµng chøng minh b»ng qui n¹p lµ hn = 2 n– 1, n ≥ 1. Chap02-83 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1 Xây dựng công thức đệ qui • Ta có thể tìm được công thức trực tiếp cho hn bằng phương pháp thế: hn = 2 hn−1 + 1 = 2 (2 hn−2 + 1) + 1 = 2 2 hn−2 + 2 + 1 = 22(2 hn−3 + 1) + 2 + 1 = 2 3 hn−3 + 2 2 + 2 + 1 = 2n−1 h1 + 2 n−2 + + 2 + 1 = 2n−1 + 2n−2 + + 2 + 1 (do h1 = 1) = 2n − 1 Chap02-84 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Tháp Hà nội với n=5 Cọc c Cọc b Chap02-85 Chuyển vào cọc này Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.2. Hàm sinh (Generating Function) • Giả sử {hn | n = 0, 1, 2, ....} là một dãy số. Ta viết dãy này như là dãy vô hạn phần tử, tuy nhiên ta coi rằng nó bao gồm cả trường hợp dãy hữu hạn. Nếu h0, h1, ..., hm là dãy hữu hạn, thì ta sẽ biến nó thành dãy vô hạn bằng cách đặt hi = 0, i > m . • Định nghĩa. Hàm sinh g(x) của dãy số {hn | n = 0, 1, 2, ....} là chuỗi vô hạn g(x) = h0 + h1 x + h2 x 2 + ... = . • Như vậy hàm g(x) sinh ra dãy số đã cho như là dãy các hệ số của nó. • Nếu dãy là hữu hạn thì sẽ tìm được m sao cho hi = 0, i > m. Trong trường hợp này g(x) là một đa thức bậc m. Chap02-86 0 i i i h x ¥ = å Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • Ví dụ 1. Một trong những nguồn gốc dẫn đến định nghĩa hàm sinh chính là định lý về khai triển nhị thức: Hàm g(x) = (1 + x)m sinh ra dãy các hệ số tổ hợp {hk = C(m, k), k=0, 1,..., m}. Bởi vì • Ví dụ 2. Hàm g(x) = 1/(1-x) sinh ra dãy 1, 1, 1, ... • Dễ dàng chứng minh điều đó bằng cách thực hiện phép chia: 1/(1- x) = 1 + x + x2 + ... Chap02-87 k m k m xkmCx å = =+ 0 ),()1( Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 3 • Ví dụ 3. Với k > 0, hàm g(x) = 1/(1-x)k sinh ra dãy {C(n+k-1, n): n = 0, 1, 2, ...}. • Như vậy hệ số thứ n sẽ là số khả năng chọn n vật từ k loại đồ vật. • Chứng minh. Thực vậy, ta có 1/(1-x)k =[ 1/(1-x)]k = (1 + x + x2 + ...)k. • Nếu ta khai triển biểu thức này bằng cách thực hiện nhân phá ngoặc, thì số lần xuất hiện số hạng xn sẽ bằng số nghiệm nguyên không âm của phương trình t1 + t2 + ... + tk = n, mà như đã biết là bằng C(n+k-1, n). Chap02-88 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 3 • Ví dụ này có thể gợi ý cho ta cách giải nhiều bài toán đếm. Chẳng hạn xét hàm sinh g(x) = (1 + x + x2 + x3) (1 + x + x2) (1 + x + x2 + x3 + x4). • Giả sử xa, xb, xc tương ứng là các số hạng lấy từ các thừa số thứ nhất, hai, ba của vế phải, điều đó có nghĩa là 0 £ a £ 3, 0 £ b £ 2, 0 £ c £ 4. Khi khai triển vế phải, các thừa số này sẽ cho ta số hạng xn, với n = a + b + c. • Như vậy hệ số của xn trong g(x) sẽ là số nghiệm nguyên không âm của phương trình n=a + b + c thoả mãn 0 £ a £ 3, 0 £ b £ 2, 0 £ c £ 4. • Suy ra hệ số này cũng cho ta số cách chọn n bông hoa từ 3 bông cúc, 2 bông layơn và 4 bông hồng. Chap02-89 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 3 • Tất nhiên việc sử dụng hàm sinh để giải bài toán đếm sẽ đòi hỏi nhiều tính toán khi thực hiện phép nhân các đa thức, và không thích hợp cho việc tính tay. Tuy nhiên, việc đó lại có thể thực hiện nhanh chóng trên máy tính, và vì thế hàm sinh sẽ là một công cụ hữu hiệu để giải nhiều bài toán đếm trên máy tính. • Ta dẫn ra một số khai triển đại số rất hay sử dụng trong việc sử dụng hàm sinh: • xk/(1-x) = xk (1 + x + x2 + ...) = xk + xk+1 + xk+2 + ... • (1-xk+1)/(1-x) = 1 + x + x2 + ... + xk. • 1/(1-x2) = 1 + x2 + x4 + x6 + ... • x/(1-x2) = x(1 + x2 + x4 + x6 + ...) = x + x3 + x5 + x7 + ... Chap02-90 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 4 • Ví dụ 4. Có bao nhiêu cách chọn ra n quả từ 4 loại quả: táo, chuối, cam và đào (mỗi loại đều có số lượng ít ra là n) mà trong đó có một số chẵn quả táo, số lẻ quả chuối, không quá 4 quả cam và ít ra 2 quả đào? • Giải. Hàm sinh để giải bài toán này là (1+ x2+x4+x6+ ...) (x+x3+x5+x7+ ...) (1+x+x2+x3+x4) (x2+x3+x4+ ...) • Trong công thức trên có 4 thừa số để đếm số quả táo (các số mũ chẵn), chuối (số mũ lẻ), cam (chỉ có đến số mũ 4) và đào (số mũ bắt đầu từ 2). Hàm sinh sẽ là g(x) = [1/(1-x2)] [x/(1-x2)] [(1-x5)/(1-x)] [x2/(1-x)] = [x3(1-x5)]/[(1-x2)2(1-x)2]. • Câu trả lời là: Số cách cần đếm là hệ số thứ n trong khai triển g(x) dưới dạng chuỗi luỹ thừa. Tuy là chúng ta không có câu trả lời bằng số, nhưng sử dụng hàm xây dựng được ta có thể lập trình trên máy tính để đưa ra bảng đáp số cho các giá trị của n mong muốn. Chap02-91 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 5 • Ví dụ 5. Tìm hàm sinh cho hn là số cách chọn ra n quả từ 4 loại quả: táo, chuối, cam và đào (mỗi loại đều có số lượng ít ra là n) mà trong đó có một số chẵn quả táo, số lượng chuối chia hết cho 5, không quá 4 quả cam và không quá 1 quả đào? • Giải. Hàm sinh có dạng g(x)=(1+x2+x4+x6+...)(1+x5+x10+x15+...)(1+x+x2+x3+x4)(1+x) = [1/(1-x2)] [1/(1-x5)] [(1-x5)/(1-x)] (1+x) = [1/((1-x)(1 +x)] [1/(1-x)] (1+x) = 1/(1-x)2 • Từ đó ta có thể tìm công thức hiện cho lời giải, bởi vì, theo ví dụ 3, ta có . • Vậy hn = n + 1. Chap02-92 2 1 12 0 0 0 1 ( 1) (1 ) n n n n n n n n n n C x C x n x x ¥ ¥ ¥ + - + = = = = = = + - å å å Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Hàm sinh và công thức đệ qui • Hàm sinh có thể sử dụng để tìm công thức dưới dạng hiện cho số hạng tổng quát của dãy số {hn , n=0,1,2,...} xác định bởi công thức đệ qui. Nội dung của phương pháp có thể trình bày như sau: ΏXây dựng hàm sinh g(x) của dãy số này theo công thức g(x) = h0 + h1 x + h2 x 2 + ... = ΏTìm công thức giải tích cho hàm sinh g(x). (Sử dụng các tính chất của dãy số suy từ công thức đệ qui xác định nó). ΏTheo công thức tìm được, tìm khai triển hàm g(x) dưới dạng chuỗi luỹ thừa (chuỗi Maclaurin). ΏSo sánh hệ số ở các số hạng với cùng số mũ của x ta tìm được công thức cho hn. Chap02-93 ¥ = å 0 i i i h x Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Phép toán với hàm sinh • Trước hết ta đưa ra một số phép toán đối với hàm sinh. Giả sử là hai hàm sinh còn a là số thực, khi đó • Tích Côsi của hai hàm sinh g(x) và f(x): trong đó ck = a0 bk + a1 bk-1 + ... + ak b0 = . Chap02-94 0 0 ( ) , ( ) i i i i i i f x a x g x b x ¥ ¥ = = = =å å 0 0 ( ) ( ) ( ) , ( ) i i i i i i i f x g x a b x f x a xa a ¥ ¥ = = + = + =å å 0 ( ) ( ) i i i f x g x c x ¥ = =å 0 k i k i i a b - = å Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chuỗi Maclaurin • Từ giải tích ta biết rằng nếu chuỗi g(x) = hội tụ ở lân cận điểm 0 thì tổng g(x) luôn là hàm giải tích trong lân cận này và hk = g (k)(0)/k! , k = 0, 1, ... • Khi đó chuỗi chính là khai triển Maclaurin của hàm g(x). Như vậy có một tương ứng 1-1 giữa một hàm giải tích và một chuỗi hội tụ trong lân cận 0. • Trong việc áp dụng hàm sinh ta thường sử dụng công thức sau: mà trường hợp riêng của nó là 1/(1 - rx) = 1 + rx + r2 x2 + r3 x3 + .... Chap02-95 0 i i i h x ¥ = å 0 i i i h x ¥ = å 1 0 1 (1 ) k k k n kn k C r x rx ¥ + - = = - å Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Dãy số Fibonaci • Dãy số Fibonaci. Dãy số Fibonaci là dãy số được xác định bởi công thức đệ qui fn = fn-1 + fn-2, n ³ 2, f0 = 0, f1 = 1. • Ta sẽ tìm công thức cho số hạng tổng quát của dãy số nhờ phương pháp hàm sinh. • Xét hàm sinh . Ta có Chap02-96 0 ( ) n n n F x f x ¥ = =å Leonardo Pisano Fibonacci 1170 - 1250 0 1 0 2 0 1 1 2 2 1 2 0 1 0 0 2 ( ) ( ) ( ) ( ). n n n n n n n n n n n n n n n n F x f x f f x f x f f x f f x f f x f x f x x xF x x F x ¥ ¥ = = ¥ - - = ¥ ¥ + + = = = = + + = + + + = + + + = + + å å å å å Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội • Từ đó suy ra • Ta có (1- x - x2) = (1 - a x) (1 - b x), với • Viết lại F(x) dưới dạng • Từ đó tìm được • Do đó • Suy ra Chap02-97 2 ( ) . 1 x F x x x = - - a b + - = = 1 5 1 5 , . 2 2 ( ) , 1 1 A B F x x xa b = + - - 1 1 , . 5 5 A B= = - 0 1 1 1 1 ( ) ( ) . 1 15 5 n n n n F x x x x a b a b ¥ = é ù = - = -ê ú- -ë û å 1 1 1 5 1 5 ( ) , 0. 2 25 5 n n n n n f na b é ùæ ö æ ö+ -ê ú= - = - ³ç ÷ ç ÷ç ÷ ç ÷ê úè ø è øë û Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chương 2. Lý thuyết tổ hợp 2.1. Hoán vị 2.2. Tổ hợp (Combination) 2.3. Nguyên lý bù trừ 2.4. Công thức đệ qui và hàm sinh 2.5. Số Stirling 2.6. Nguyên lý các lồng chim bồ câu Chap02-98 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.5 Số Stirling • 2.5.1. Số Stirling • 2.5.2. Số Bell • 2.5.3. Số Catalan Chap02-99 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Có bao nhiêu ánh xạ? Cho các tập hữu hạn A = {a1,, am} và B = {b1,, bn}. Hỏi có bao nhiêu ánh xạ f: A ® B ? Như ta đã chứng minh: • Tổng số ánh xạ có thể: |B||A| = nm. • Số lượng đơn ánh: P(n,m) = n∙(n–1)∙∙∙(n–m+1) = n!/(n–m)!. • Số lượng song ánh là P(n,n) = n! nếu |A| = |B| = n. • Số lượng toàn ánh: với m ≥ n: Chap02-100 0 ( 1) ( ) n k n k m n k C n k - = - -å Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.5.1. Số Stirling loại 2 • Số lượng toàn ánh từ tập A = {a1,,am} vào tập B = {b1,,bn} liên quan đến một con số tổ hợp nổi tiếng đó là số Stirling loại 2 (Stirling Numbers of the 2nd Kind). • Định nghĩa. Số Stirling loại 2, ký hiệu bởi S2(m,n), là số cách phân hoạch tập m phần tử thành n tập con (m ³ n). • Ví dụ: Ta đếm số cách phân hoạch tập {1,2,3,4} ra thành 2 tập con. Ta có thể kể ra tất cả các cách phân hoạch như vậy: {{1,2,3},{4}}, {{1,2,4},{3}}, {{1,3,4},{2}}, {{2,3,4},{1}}, {{1,2},{3,4}}, {{1,3},{2,4}},{{1,4},{2,3}}. • Vậy S2(4,2)=7. Chap02-101 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội • Trong nhiều tài liệu, số Stirling còn được ký hiệu bởi Chap02-102 S m (n) hoac m n ÿ ÿ ÿ ÿ ÿ ÿ James Stirling 1692 – 1770 Scotland Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.5.1. Số Stirling loại 2 • Ta sẽ xây dựng công thức đệ qui để đếm số S2(m,n). • Ta có: ΏS2(0,0)=1. ΏNếu m > 0, thì S2(m,0) = 0, S2(m,1)=1, và S2(m,m)=1. Định lý. Với m, n > 1, S2(m,n) = S2(m–1,n–1) + n∙S2(m–1,n). Chứng minh. Ta cần đếm số cách phân hoạch tập m phần tử X = {x1, x2, , xm} ra thành n tập con. Chap02-103 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Công thức đệ qui • Tập các cách phân hoạch như vậy có thể phân hoạch thành 2 tập: A = Tập các cách phân hoạch X ra thành n tập con trong đó có một tập con là {xm}; B = Tập các cách phân hoạch X ra thành n tập con trong đó không có tập con nào là {xm} (tức là xm không đứng riêng một mình!). • Ta có: |A| = S2(m–1,n–1) . |B| = n∙S2(m–1,n), bởi vì có S2(m–1,n) cách phân hoạch X \{xm} ra thành n tập con và có n cách xếp xm vào một trong số các tập con này. • Từ đó S2(m,n)= |A| + |B| = S2(m–1,n–1) + n∙S2(m–1,n). Định lý được chứng minh. Chap02-104 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Công thức tính số Stirling Chap02-105 • Từ công thức đệ qui có thể chứng minh bằng qui nạp toán học công thức sau đây: • Nói chung để tính S2(m,n) người ta thường dùng công thức đệ qui, chứ không sử dụng công thức này. Điều này được giải thích tương tự như để tính hệ số tổ hợp người ta thường dùng tam giác Pascal. 2 0 1 ( , ) ( 1) ! - = = -å n n k k m n k S m n C k n Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Liên hệ giữa số lượng toàn ánh và số Stirling Chap02-106 • Ta xét mối liên hệ giữa số Stirling loại 2 với số lượng toàn ánh từ tập m phần tử A vào tập n phần tử B (ký hiệu là S'(m,n)). • Giả sử cho f là toàn ánh từ A vào B. Đặt Ai = {aÎA| f(a) = bi}, i = 1, 2, ..., n, Rõ ràng các tập A1, A2, ..., An tạo thành một phân hoạch của tập A. • Ngược lại, cho một phân hoạch của tập A ra thành n tập con A1, A2, ..., An và p(1), p(2), ...,p(n) là hoán vị của 1, 2, ..., n, thì ta có thể xây dựng được toàn ánh f từ A vào B theo qui tắc f(a) = bp(i) , aÎAp(i) , i = 1,2, ..., n, • Như vậy mỗi phân hoạch cho ta n! toàn ánh. Vì thế, số lượng toàn ánh từ tập m phần tử vào tập n phần tử là bằng n! nhân với số cách phân hoạch tập m phần tử ra thành n tập con, nghĩa là bằng n!S2(m,n) Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Liên hệ giữa số lượng toàn ánh và số Stirling Chap02-107 • Như vậy ta có đẳng thức cho mối liên hệ giữa số toàn ánh từ tập m phần tử vào tập n phần tử S'(m,n) và số Stirling loại 2 sau đây: S'(m,n) = n! S2(m,n) . • Do đó từ công thức đã chứng minh ở mục trước • Ngược lại, nếu coi công thức của S2(m,n) đã biết thì 2 0 0 1 '( , ) ( 1) ( ) ( , ) ( 1) ( ) != = = - - Þ = - -å å n n k k m k k m n n k k S m n C n k S m n C n k n 2 0 0 1 ( , ) ( 1) '( , ) ( 1) ! - - = = = - Þ = -å å n n n k k m n k k m n n k k S m n C k S m n C k n Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Bảng giá trị của số Stirling loại 2 Chap02-108 S2(n,k) 0 1 2 3 4 5 6 7 8 9 10 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 k n Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.5.2. Số Bell • Định nghĩa. Số Bell (Bell numbers) là số cách phân hoạch tập n phần tử ra thành các tập con khác rỗng. • Các phần tử đầu tiên của dãy số này là 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, ... • Ví dụ: Tập {1, 2, 3} có các cách phân hoạch sau đây: {{1}, {2}, {3}} , {{1, 2}, {3}}, {{1, 3}, {2}} , {{1}, {2, 3}}, {{1, 2, 3}}. • Số Bell thứ n được tính bởi công thức trong đó S2(n,k) là số Stirling loại 2. Chap02-109 2 1 ( , ) n k S n k = å Eric Temple Bell Born: 1883, Scotland Died: 1960, USA Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Số Bell • Tập {1, 2, 3} có 5 cách phân hoạch: • Tập {1, 2, 3, 4, 5} có 52 cách phân hoạch: Chap02-110 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.5.2. Số Catalan • Định nghĩa. Số Catalan thứ n, ký hiệu là Cn , là số cách đặt dấu ngoặc để tổ chức thực hiện việc tính tích của n+1 thừa số: P0..n = x0 x1 x2 ... xn. • Ví dụ: • Có 2 cách để tính P0..2 : x0*x1*x2 = (x0*(x1*x2)) = ((x0*x1)*x2) • Có 5 cách để tính P0..3: 1*2*3*4 = (1*(2*(3*4))) = (1*((2*3)*4)) = ((1*2)*(3*4)) = ((1*(2*3))* 4) = (((1*2)*3)*4) • Có 14 cách để tính P0..4 : 1*2*3*4*5 = (1 (2 (3 (4 5)))) = (1 (2 ((3 4) 5))) = (1 ((2 3) (4 5))) = (1 ((2 (3 4)) 5)) = (1 (((2 3) 4) 5)) = ((1 2) (3 (4 5))) = ((1 2) ((3 4) 5)) = ((1 (2 3)) (4 5)) = ((1 (2 (3 4))) 5) = ((1 ((2 3) 4)) 5) = (((1 2) 3) (4 5)) = (((1 2) (3 4)) 5) = (((1 (2 3)) 4) 5) = ((((1 2) 3) 4) 5) Chap02-111 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.5.2. Số Catalan • Ta xây dựng công thức đệ qui để tính Cn. • Rõ ràng C0 = 1 và C1 = 1. • Giả sử n > 1. Sau khi đặt dấu ngoặc phân tách đầu tiên, tích x0 x1 x2 ... xn được chia làm hai tích con. • Ví dụ: P0..4 = P0..2 P3..4 = (x0 x1 x2) (x3 x4) • Giả sử dấu ngoặc phân tách đầu tiên được đặt sau thừa số xk: P0..n = P0..k Pk+1..n = (x0 x1 x2 ... xk) (xk+1 xk+2 ... xn) • Khi đó ta có Ck cách tính P0..k , Cn-k-1 cách tính Pk+1..n , và do đó việc tính P0..n có thể thực hiện bởi Ck Cn-k-1 cách . Chap02-112 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.5.2. Số Catalan • Do dấu ngoặc phân tách đầu tiên có thể đặt vào sau bất cứ thừa số nào trong các thừa số x0, x1, ..., xn-1, suy ra tổng số cách tính P0..n là: Cn = C0 Cn-1 + C1Cn-2+ ... +Cn-1C0 . • Như vậy ta thu được công thức đệ qui: • Sử dụng công thức này có thể chứng minh công thức sau: Chap02-113 1 1 0 0 1 , 1, 1, 1 n n k n k k C C C n C C - - - = = > = = å 1 1 0 21 (2 )! , 0. 1 !( 1)! - - - = æ ö = = = ³ç ÷+ +è ø å n n k n k k n n C C C n nn n n Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.5.2. Số Catalan • Một số phần tử đầu tiên của dãy số Catalan: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, • Số Catalan là lời giải của rất nhiều bài toán tổ hợp. • Ta sẽ kể ra dưới đây một số bài toán như vậy. Chap02-114 E. C. Catalan 1814 -1894 Belgium Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Tam giác phân đa giác • Cn là số cách chia đa giác n+2 đỉnh ra thành các tam giác nhờ vẽ các đường chéo không cắt nhau ở trong đa giác: Chap02-115 C3 = 5 C2 = 2 C4 = 14 C5 = 42 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Đường đi trên lưới ô vuông • Cn là số lượng đường đi đơn điệu (tức là đường đi xuất phát từ vị trí góc dưới-phải kết thúc ở góc trên-trái và chỉ đi sang trái hoặc lên trên) độ dài 2n trên lưới ô vuông kích thước n´n không vượt lên trên đường chéo. Chap02-116 C5 = 42C4 = 14 C2 = 2 C3 = 5 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Cây nhị phân đầy đủ Cn là số lượng cây nhị phân đầy đủ không đẳng cấu có n đỉnh trong. Cây nhị phân có gốc được gọi là đầy đủ nếu mỗi đỉnh của nó hoặc là không có con hoặc có đúng hai con. Đỉnh trong (internal vertice) là đỉnh có con. Chap02-117 n = 2 n = 3 n = 4 n = 1 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội • Cn là số cây nhị phân đầy đủ với n + 1 lá. • Có C3 = 5 cây nhị phân đầy đủ với 4 lá: Cây nhị phân đầy đủ với n lá Chap02-118 n 2 3 4 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chương 2. Lý thuyết tổ hợp 2.1. Hoán vị 2.2. Tổ hợp (Combination) 2.3. Nguyên lý bù trừ 2.4. Công thức đệ qui và hàm sinh 2.5. Số Stirling 2.6. Nguyên lý các lồng chim bồ câu Chap02-119 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.6 Nguyên lý các lồng chim bồ câu (Pigeonhole Principle) 2.6.1. Phát biểu nguyên lý 2.6.2. Các ví dụ ứng dụng Chap02-120 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.6.1. Phát biểu nguyên lý Nếu xếp nhiều hơn n đối tượng vào n cái hộp thì bao giờ cũng tìm được ít nhất một cái hộp chứa ít ra là hai đối tượng. Chap02-121 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Pigeonhole Principle Chøng minh. Việc chứng minh nguyên lý trên chỉ là một lập luận phản chứng đơn giản. Giả sử ngược lại là không tìm được cái hộp nào chứa không ít hơn 2 đối tượng. Điều đó có nghĩa là mỗi cái hộp chứa không quá một đối tượng. Từ đó suy ra tổng số đối tượng xếp trong n cái hộp là không vượt quá n, trái với giả thiết là có nhiều hơn n đối tượng được xếp trong chúng. Chap02-122 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.6.1. Phát biểu nguyên lý • Lập luận trên đã được nhà toán học người Đức là Dirichlet vận dụng thành công vào việc giải quyết rất nhiều bài toán tồn tại tổ hợp. • Trong lập luận của Dirichlet, các đối tượng được xét là các quả táo còn các cái hộp được thay bởi các cái giỏ: “Nếu đem bỏ nhiều hơn n quả táo vào n cái giỏ thì bao giờ cũng tìm được ít nhất một cái giỏ chứa ít ra là 2 quả táo”. Chap02-123 Johann Peter Gustav Lejeune Dirichlet Born: 13 Feb 1805 Died: 5 May 1859 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.6.1. Phát biểu nguyên lý l Trong tài liệu tiếng Anh lập luận đó lại được trình bày trong ngôn ngữ của các con chim bồ câu: “Nếu đem nhốt nhiều hơn n con chim bồ câu vào n cái lồng thì bao giờ cũng tìm được ít nhất 1 cái lồng chứa ít ra là 2 con chim bồ câu”. Vì thế nguyên lý còn có tên gọi là “Nguyên lý về các lồng chim bồ câu”. l Trong ngôn ngữ của lý thuyết tập hợp, nguyên lý có thể phát biểu như sau: “Nếu tập X gồm nhiều hơn n phần tử được phân hoạch thành n tập con, thì bao giờ cũng tìm được một tập con trong phân hoạch đó có lực lượng ít ra là 2” Chap02-124 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • Ví dụ 1. Trong số 367 người bao giờ cũng tìm được hai người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau. • Ví dụ 2. Trong kỳ thi học sinh giỏi điểm bài thi được đánh giá bởi một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất phải có bao nhiêu học sinh dự thi để cho chắc chắn tìm được hai học sinh có kết quả thi như nhau? • Giải. Theo nguyên lý Dirichlet, số học sinh cần tìm là 102, vì ta có 101 kết quả điểm thi khác nhau. Chap02-125 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • Ví dụ 3. Trong số những người có mặt trên trái đất luôn tìm được hai người có hàm răng giống nhau. • Giải: Tất cả chỉ có 232 = 4 294 967 296 hàm răng khác nhau mà số người trên hành tinh chúng ta hiện nay đã vượt quá 5 tỷ. Chap02-126 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nguyên lý Dirichlet tổng quát Generalized Pigeonhole Principle • Khi số lượng quả táo bỏ vào k cái giỏ vượt quá số lượng cái giỏ nhiều lần thì rõ ràng khẳng định trong nguyên lý về sự tồn tại cái giỏ chứa ít ra là 2 quả táo là quá ít. Trong trường hợp như vậy ta sử dụng nguyên lý Dirichlet tổng quát sau đây: • “Nếu đem bỏ n quả táo vào k cái giỏ thì bao giờ cũng tìm được ít nhất một cái giỏ chứa ít ra là én/kù quả táo”. • Ở đây ký hiệu éaù gọi là phần nguyên già của số thực a, theo định nghĩa, là số nguyên nhỏ nhất còn lớn hơn hoặc bằng a. Chap02-127 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Nguyên lý Dirichlet tổng quát Generalized Pigeonhole Principle • Chứng minh nguyên lý tổng quát: • Giả sử khẳng định của nguyên lý là không đúng. Khi đó mỗi cái giỏ chứa không quá én/kù - 1 quả táo. Từ đó suy ra tổng số quả táo bỏ trong k cái giỏ không vượt quá k(én/kù - 1) < k((n/k+1) - 1)) = n. Mâu thuẫn thu được đã chứng minh nguyên lý. Chap02-128 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • Ví dụ 4. Trong 100 người có ít nhất 9 người sinh cùng một tháng. • Giải: Xếp những người cùng sinh một tháng vào một nhóm. Có 12 tháng tất cả. Vậy theo nguyên lý Dirichlet, tồn tại ít nhất một nhóm có không ít hơn é100/12ù = 9 người. • Ví dụ 5. Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là sáu người cùng nhận học bổng như nhau? • Giải: Số sinh viên ít nhất cần có để đảm bảo chắc chắn có 6 sinh viên cùng nhận học bổng như nhau là số nguyên nhỏ nhất n sao cho én/5ù = 6. Số nguyên nhỏ nhất đó là n = 5´5+1 = 26. Vậy 26 là số lượng sinh viên nhỏ nhất đảm bảo chắc chắn là có sáu sinh viên cùng hưởng một loại học bổng. Chap02-129 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ • Ví dụ 6. Hỏi ít nhất phải có bao nhiêu người có mặt trên trái đất để luôn tìm được ba người có hàm răng giống nhau? • Giải: Tất cả chỉ có 232 = 4 294 967 296 hàm răng khác nhau. Ta cần tìm số n nhỏ nhất để én/232ù = 3. • Từ đó số người cần tìm là 2´232 + 1 = 8 589 934 593. Chap02-130 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.6.2. Các ví dụ ứng dụng • Trong các ví dụ ứng dụng phức tạp hơn của nguyên lý Dirichlet, cái giỏ và quả táo cần phải được lựa chọn khôn khéo hơn rất nhiều. • Trong phần này ta sẽ xét một số ví dụ như vậy. Chap02-131 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 1 • Ví dụ 1. Trong một phòng họp bao giờ cũng tìm được hai người có số người quen trong số những người dự họp là bằng nhau. • Gi¶i: Gäi sè ngêi dù häp lµ n, khi ®ã sè ngêi quen cña mét ngêi nµo ®ã trong phßng häp chØ cã thÓ nhËn c¸c gi¸ trÞ tõ 0 ®Õn n-1. Râ rµng trong phßng kh«ng thÓ ®ång thêi cã ngêi cã sè ngêi quen lµ 0 (tøc lµ kh«ng quen ai c¶) vµ cã ngêi cã sè ngêi quen lµ n-1 (tøc lµ quen tÊt c¶). V× vËy, theo sè lîng ngêi quen ta chØ cã thÓ ph©n n ngêi ra thµnh n-1 nhãm. Theo nguyªn lý Dirichlet suy ra cã Ýt nhÊt mét nhãm ph¶i cã kh«ng Ýt h¬n hai ngêi, tøc lµ lu«n t×m ®îc Ýt ra lµ hai ngêi cã sè ngêi quen lµ b»ng nhau. Chap02-132 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 2 • Ví dụ 2. Trong một tháng gồm 30 ngày một đội bóng chuyền thi đấu mỗi ngày ít nhất một trận, nhưng không chơi quá 45 trận. Chứng minh rằng phải tìm được một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho trong giai đoạn đó đội chơi đúng 14 trận. • Gi¶i: Gi¶ sö aj lµ tæng sè trËn thi ®Êu cho ®Õn hÕt ngµy thø j cña ®éi. Khi ®ã a1, a2, ..., a30 lµ d·y t¨ng c¸c sè nguyªn d¬ng vµ ®ång thêi 1 £ aj £ 45. Suy ra d·y a1+14, a2+14, ..., a30+14 còng lµ d·y t¨ng c¸c sè nguyªn d¬ng vµ 15 £ aj +14 £ 59. Chap02-133 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 2 • Tất cả có 60 số nguyên dương a1, a2, ..., a30, a1+14, a2+14, ..., a30+14, trong đó tất cả đều nhỏ hơn hoặc bằng 59. • Vì vậy theo nguyên lý Dirichlet, hai trong số các số nguyên này phải là bằng nhau. Vì các số a1, ..., a30 là đôi một khác nhau và các số a1+14, ..., a30+14 cũng là đôi một khác nhau, nên suy ra phải tìm được chỉ số i và j sao cho j<i và ai = aj+14. • Điều đó có nghĩa là có đúng 14 trận đấu trong giai đoạn từ ngày j+1 đến hết ngày i. Chap02-134 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 3 • Ví dụ 3. Chứng minh rằng, trong số n+1 số nguyên dương, mỗi số không lớn hơn 2n, bao giờ cũng tìm được hai số sao cho số này chia hết cho số kia. • Gi¶i: Gäi c¸c sè ®· cho lµ a1, a2, . . . , an+1 . • ViÕt mçi mét sè aj trong n+1 sè trªn díi d¹ng: aj = 2 k(j)qj , j = 1, 2, ..., n+1 trong ®ã k(j) lµ nguyªn kh«ng ©m, qj lµ sè lÎ. Chap02-135 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 3 • Các số q1, q2, ..., qn+1 là các số nguyên lẻ, mỗi số không lớn hơn 2n. • Do trong đoạn từ 1 đến 2n chỉ có n số lẻ, nên từ nguyên lý Dirichlet suy ra là hai trong số các số q1, q2, ..., qn+1 là bằng nhau, tức là tìm được hai chỉ số i và j sao cho qi = qj = q. • Khi đó ai = 2 k(i)q, aj = 2 k(j)q. • Suy ra nếu k(i) < k(j) thì aj chia hết cho ai, còn nếu k(i) ³ k(j) thì ai chia hết cho aj. Chap02-136 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 4 • Ví dụ 4. Trên mặt phẳng cho 5 điểm có toạ độ nguyên Mi(xi, yi), i=1, 2, ..., 5. Chứng minh rằng luôn tìm được 2 điểm sao cho đoạn thẳng nối chúng, ngoài hai đầu mút, còn đi qua một điểm có toạ độ nguyên khác nữa. • Giải. Ta sẽ chứng minh: Luôn tìm được 2 điểm sao cho điểm giữa của đoạn thẳng nối chúng có toạ độ nguyên. Theo tính chẵn lẻ của hai toạ độ, 5 điểm đã cho có thể phân vào nhiều nhất là 4 nhóm: (Chẵn, Chẵn), (Chẵn, Lẻ), (Lẻ, Chẵn), (Lẻ, Lẻ). Chap02-137 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 4 • Từ đó theo nguyên lý Dirichlet phải tìm được một nhóm chứa ít ra là 2 điểm, chẳng hạn đó là Mi, Mj. Khi đó điểm giữa Gij của đoạn thẳng nối Mi và Mi có toạ độ Gij = ((xi+xj)/2, (yi+yj)/2). • Do xi và xj cũng như yi và yj có cùng tính chẵn lẻ nên các toạ độ của Gij là các số nguyên. Khẳng định của ví dụ được chứng minh. • Khẳng định của ví dụ có thể tổng quát cho không gian n- chiều: “Trong không gian n-chiều cho 2n + 1 điểm có toạ độ nguyên. Khi đó luôn tìm được 2 điểm sao cho đoạn thẳng nối chúng, ngoài hai đầu mút, còn đi qua một điểm có toạ độ nguyên khác nữa”. Chap02-138 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 5 Trước hết ta cần một số khái niệm. • Cho a1, a2, an là dãy số thực. • n được gọi là độ dài của dãy số đã cho. • Ta gọi dãy con của dãy đã cho là dãy có dạng ai1, ai2, , aim, trong đó 1 £ i1 < i2 < . . . < im £ n • Dãy số được gọi là tăng ngặt nếu mỗi số hạng đứng sau luôn lớn hơn số hạng đứng trước. Dãy số được gọi là giảm ngặt nếu mỗi số hạng đứng sau luôn nhỏ hơn số hạng đứng trước.. ΏVí dụ: Cho dãy số 1, 5, 6, 2, 3, 9. • 5, 6, 9 là dãy con tăng ngặt của dãy đã cho • 6, 3 là dãy con giảm ngặt của dãy đã cho Chap02-139 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 5 • Định lý: Mỗi dãy gồm n2+1 số phân biệt (nghĩa là các phần tử là khác nhau từng đôi) luôn chứa hoặc dãy con tăng ngặt độ dài n+1 hoặc dãy con giảm ngặt độ dài n+1. • Ví dụ: Dãy 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 gồm 10 = 32+1 số hạng phải chứa hoặc dãy con tăng ngặt độ dài 4 phần tử hoặc dãy con giảm ngặt độ dài 4 phần tử. 1, 4, 6, 12 1, 4, 6, 7 11, 9, 6, 5 Chap02-140 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 5 • Chứng minh: Giả sử a1, a2, , an2+1 là dãy gồm n2+1 số phân biệt. Gán cho mỗi số hạng ak của dãy số cặp có thứ tự (ik,dk), trong đó ik là độ dài của dãy con tăng dài nhất bắt đầu từ ak còn dk là độ dài của dãy con giảm dài nhất bắt đầu từ ak. • Ví dụ: 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 a2 = 11, (i2,d2) = (2,4) a4 = 1 , (i4,d4) =(4,1) • Bây giờ giả sử không tồn tại dãy tăng cũng như dãy giảm có độ dài n+1. Khi đó ik và dk là các số nguyên dương £ n, với k = 1, 2, ..., n2+1. Chap02-141 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 5 • Do 1 £ ik, dk £ n, nên theo qui tắc nhân có tất cả n2 cặp có thứ tự dạng (ik,dk) khác nhau. • Do ta có tất cả n2 + 1 cặp (ik,dk), nên theo nguyên lý Dirichlet, hai trong số chúng là trùng nhau. Tức là tồn tại hai số hạng as và at trong dãy đã cho với s < t sao cho is = it và ds = dt. • Ta sẽ chỉ ra điều này là không thể xảy ra. • Do các số hạng của dãy là phân biệt, nên hoặc là as at. Chap02-142 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Ví dụ 5 • Nếu as < at, khi đó do is = it , ta có thể xây dựng dãy con tăng độ dài it+1 bắt đầu từ as, bằng cách nối đuôi nó bởi dãy con tăng độ dài it, bắt đầu từ at. ... , as , ..., at , .... • Suy ra dãy con tăng dài nhất bắt đầu từ as có độ dài ít ra là it + 1, nghĩa là is > it. Mâu thuẫn với giả thiết is= it. • Tương tự như vậy, nếu as > at, ta có thể chỉ ra ds phải lớn hơn dt, và cũng đi đến mâu thuẫn. • Định lý được chứng minh. Chap02-143 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-144 Hết chương 2 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-145 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội 2.4.1. Xây dựng công thức đệ qui • Định nghĩa. Công thức đệ qui (recurence relation) cho dãy số {an} là công thức cho phép tính an thông qua một hoặc một vài số hạng đi trước nó trong dãy số (đó là các số hạng a0, a1,..., an-1) với mọi n ³ n0, trong đó n0 là số nguyên không âm. Một dãy số được gọi là nghiệm của công thức đệ qui nếu như các số hạng của nó thỏa mãn của công thức này. • Ví dụ: Xét công thức đệ qui an= 2an– 1 – an– 2 với n = 2,3,4,... ΏDãy số {an} với an = 3n là nghiệm của công thức này, vì ta có an= 2an– 1 – an– 2 = 2[3(n–1)] – 3(n–2) = 3n, với n ³ 2. ΏDãy số {an = 5} cũng là nghiệm, vì an= 2an – 1 – an – 2 =2*5– 5=5, với mọi n ³ 2. ΏDãy số {an = 2n} không là nghiệm, vì ta có a0= 1, a1=2, a2 = 4, nhưng a2 = 4 ¹ 2a1 – a0 = 2*2 – 1 = 3. Chap02-146 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Cây nhị phân • A binary tree is often defined recursively as either (a) being empty, or (b) consisting of a root node together with left and right subtrees, both of which are binary trees. It is this definition that is most useful from the point of view of data structures in computer science. From the mathematical point of view these objects are not trees. Changing (a) from "empty" to "a single vertex" gives a definition equivalent to that of ordered trees in which every node is either a leaf (no children) or has two children. These are sometimes called extended binary trees. In either case, they are usually parameterized by n, the number of applications of rule (b) that are used. • In the extended binary tree illustrated above there are 5 internal nodes (the brown circles, which correspond to applications of rule (b)) and 6 leaves (the blue squares, which correspond to applications of rule (a)). By removing the blue edges and the leaves you obtain the corresponding binary tree. Chap02-147 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-148 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội • Ordered Trees • An ordered tree is a rooted tree in which the relative order of subtrees matters. An ordered forest is an ordered collection of ordered trees. There is a one-to-one correspondence between ordered forests with n nodes and binary trees with n nodes. This correspondence is best explained using the well-formed parentheses strings with n left and n right parentheses. If the n left parentheses and n right parentheses are labelled 1 through n from left to right in the string, then there are n pairs of matching left/right pairs of parentheses. These pairs correspond to the nodes of the corresponding ordered forest. Listing the pairs in increasing order of the left parentheses corresponds to a preorder listing of the nodes of the forest and listing the pairs in increasing order of the right parentheses corresponds to a postorder listing of the nodes of the forest. Chap02-149