Nội . Hoán . Tổ hợp (Combination).. Nguyên lý bù trừChương . Công thức đệ qui và hàm sinhTỔ . Số Stirling(Combinatorics)Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà . 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ổ Hoán . vị•.•.•.•. hợp (Combination).(. Nguyên lý bù . Công thức đệ qui và hàm . Chỉnh hợp lặp chập m (m-permutation with repetition).. Chỉnh hợp không lặp chập m (m-permutation).. Hoán vị (permutation).. Liệt kê hoán . Số . 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à . 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ử là bộ có thứ tự gồm m thành phần, mỗi thành phần đều tử của X• Chú ý: Trong tài liệu tiếng Anh, thuật ngữ " repetition" được dùng để chỉ chỉnh hợp lặp chập m. 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 X có thể biểu diễn bởi.(a1, a2, ., am), ai Î X, i = 1, 2, ., 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à . 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 tập ACCESS, FOXPRO, EXCEL, LOTUS. viên phải tham gia vào đúng một nhóm và có thể nhận một số lượng không hạn chế .• 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ộ 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. suy ra số cách phân bố cần đếm là 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 . 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 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 • 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 thành phần chỉ nhận một trong hai giá trị (1 hoặc 0). Từ đó suy 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 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à • Đị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 đề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ử (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 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ử 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à 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 xc ®Þnh bëi bé nh (f(u1),.f(u2), ., f(um)), trong ®ã f(ui) Î V, i=1, 2, ., m, f(ui)¹ f(uj), i¹ jTõ ®ã 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ó 10 chỗ ngồi với điều kiện không được phép ngồi lòng• Giải. Đánh số
