Đang chuẩn bị liên kết để tải về tài liệu:
Chap02Combinatorics4-1

Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG Tải xuống

Nội dung.2.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án.n vị•.•.•.•2.2. Tổ.ổ hợp (Combination).(C.2.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ố Stirling.2.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-4.2.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ủ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.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ó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.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 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-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à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ý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-8.Chỉ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 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á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ố