TS. Trần Văn Hoài 2008-2009 Tổ hợp & Phép đếm (Combinatorics & Counting) Tổ hợp & Phép đếm (Combinatorics & Counting) Page 1 TS. Trần Văn Hoài 2008-2009 Lý thuyết tổ hợp Combinatorics là một ngành toán học nghiên cứu sự liệt kê, tổ hợp, và hoán vị của tập những phần tử những mối quan hệ toán học. (Concise Encyclopedia of Mathematics) Combinatorics bao gồm đếm • Đếm các đối tượng thỏa điều kiện (enumerative combinatorics) • Quyết định khi nào điều kiện thỏa, xây dựng và phân tích các đối tượng thỏa điều kiện (combinatorial designs and matroid theory) • Tìm lớn nhất, nhỏ nhất, tối ưu (combinatorial optimization) (en.wikipedia.org) Tổ hợp & Phép đếm (Combinatorics & Counting) Page 2 TS. Trần Văn Hoài 2008-2009 Ứng dụng của lý thuyết tổ hợp ➳ Lý thuyết độ phức tạp của thuật toán ➳ Lý thuyết tối ưu rời rạc ➳ Lý thuyết xác suất ➳ Vật lý thống kê ➳ Hình học Tổ hợp & Phép đếm (Combinatorics & Counting) Page 3 TS. Trần Văn Hoài 2008-2009 Những quy tắc đếm cơ bản Rất nhiều bài toán đếm có thể thực hiện chỉ dùng 2 quy tắc cơ bản: cộng (sum) và nhân (product). Có những quy tắc đếm nâng cao khác ➠ Liệt kê các khả năng thối một lượng tiền với một tập các loại tiền xác định ➠ Đếm bao nhiêu mật khẩu (password) có thể có với một chiều dài cho trước ➠ Đếm có bao nhiêu địa chỉ Internet Tổ hợp & Phép đếm (Combinatorics & Counting) Page 4 TS. Trần Văn Hoài 2008-2009 Bao nhiêu cách chọn ? Hấp dẫn Đảm đang Chọn ai đây?!?! Mà chỉ được 1 mà thôi :-( Tổ hợp & Phép đếm (Combinatorics & Counting) Page 5 TS. Trần Văn Hoài 2008-2009 Quy tắc cộng Ví dụ: Hoặc là 1 giảng viên của khoa KH&KT MT, hoặc là 1 sinh viên của khoa KH&KT MT sẽ là đại diện của trường. Như vậy nếu có 24 giảng viên, 310 sinh viên thì có bao nhiêu cách chọn lựa đại diện ? Lời giải: Chọn đại diện từ giảng viên thì có 24 cách, chọn đại diện từ sinh viên thì có 310 cách. Như vậy ta có 24+310=334 cách chọn đại diện. Tổ hợp & Phép đếm (Combinatorics & Counting) Page 6 TS. Trần Văn Hoài 2008-2009 Quy tắc cộng Ví dụ: Hoặc là 1 giảng viên của khoa KH&KT MT, hoặc là 1 sinh viên của khoa KH&KT MT sẽ là đại diện của trường. Như vậy nếu có 24 giảng viên, 310 sinh viên thì có bao nhiêu cách chọn lựa đại diện ? Lời giải: Chọn đại diện từ giảng viên thì có 24 cách, chọn đại diện từ sinh viên thì có 310 cách. Như vậy ta có 24+310=334 cách chọn đại diện. Giả thiết công việc 1 có thể làm bằng n1 cách, công việc 2 có thể làm bằng n2 cách. Nếu 2 công việc không thể làm đồng thời thì có n1 + n2 cách làm một trong 2 công việc. Tổ hợp & Phép đếm (Combinatorics & Counting) Page 7 TS. Trần Văn Hoài 2008-2009 Tổng quát hóa quy tắc cộng Tổng quát lên m công việc không thể làm đồng thời và số cách làm chúng tương ứng là nP 1 , n2 , . . . , nm . Số cách làm một trong m công việc là m i=1 ni . Ví dụ: Một sinh viên chọn đồ án môn học trong 5 nhóm: khoa học máy tính, cơ sở dữ liệu, công nghệ phần mềm, hệ thống & mạng máy tính, kỹ thuật máy tính. Mỗi nhóm có số lượng đề tài tương ứng là: 10, 15, 14, 16, 11. Có bao nhiêu cách chọn ? Lời giải: 10+15+14+16+11 = 66 cách Tổ hợp & Phép đếm (Combinatorics & Counting) Page 8 TS. Trần Văn Hoài 2008-2009 Góc nhìn tập hợp Giả thiết A1, A2 , . . . , Am là các tập hợp rời nhau (disjoint). Khi đó số cách để chọn một phần tử từ một trong các tập chính là |A1 ∪ A2 ∪ . . . ∪ Am| = |A1 | + |A2| + . . . + |Am | Tổ hợp & Phép đếm (Combinatorics & Counting) Page 9 TS. Trần Văn Hoài 2008-2009 Chọn nhà nào đây ? Mục tiêu Chọn nhà nào đây ?!?! Mà chỉ 1 nhà thôi :-( Tổ hợp & Phép đếm (Combinatorics & Counting) Page 10 TS. Trần Văn Hoài 2008-2009 Quy tắc nhân Ví dụ: Một trung tâm máy tính có 32 máy vi tính. Một máy có 12 cổng. Như vậy trung tâm có bao nhiêu cổng ? Lời giải: Quá trình gồm 2 bước 1. Chọn máy 2. Chọn cổng của máy được chọn Dễ thấy, số cách là 32 × 12 = 384 cổng. Giả sử một nhiệm vụ được tách làm 2 việc: việc 1 làm bằng n1 cách, việc 2 làm n2 cách khi việc 1 đã được làm. Khi đó sẽ có n1 ×n2 cách thực hiện nhiệm vụ này. Tổ hợp & Phép đếm (Combinatorics & Counting) Page 11 TS. Trần Văn Hoài 2008-2009 Tổng quát quy tắc nhân Giả thiết một nhiệm vụ có m công việc phải thực hiện T1, . . . , Tm. Nếu việc Ti có ni cách thực hiện. Khi đó ta có n1 × . . . × nm cách thực hiện nhiệm vụ. Ví dụ: Có bao nhiêu xâu nhị phân có độ dài 7 ? Lời giải: Mỗi bit có thể chọn 1 trong 2 cách: 0 và 1. Quy tắc nhân cho số lượng xâu là 27 = 128. Ví dụ: Có bao nhiêu hàm đơn ánh xác định trên tập hữu hạn A có m phần tử và nhận giá trị trên tập B có n phần tử ? Tổ hợp & Phép đếm (Combinatorics & Counting) Page 12 TS. Trần Văn Hoài 2008-2009 Phối hợp 2 quy tắc Ví dụ: Mật khẩu máy tính dài từ 6 → 8 ký tự. Mỗi ký tự có thể là số hoặc chữ hoa. Mỗi mật khẩu phải có ít nhất một chữ số. Có bao nhiêu mật khẩu ? Lời giải: Gọi P1 , P2 , P 3 là tổng số mật khẩu có chiều dài tương ứng là 6, 7, 8. Dùng quy tắc nhân để tính Pi ta có P6 = (10 + 26)6 − 266 P7 = (10 + 26)7 − 267 P8 = (10 + 26)8 − 268 Dùng quy tắc cộng ta có tổng số mật khẩu P = P6 + P7 + P8 = 366 + 367 + 368 − (266 + 267 + 268 ) Tổ hợp & Phép đếm (Combinatorics & Counting) Page 13 TS. Trần Văn Hoài 2008-2009 Quy tắc bù trừ Ví dụ: Có bao nhiêu chuỗi bit có độ dài 8 bit hoặc được bắt đầu bằng 1 hoặc kết thúc bằng 2 bit 00 ? Lời giải: • Số lượng chuỗi bit bắt đầu bằng 1 là 27 = 128 • Số lượng chuỗi bit kết thúc bằng 00 là 26 = 64 • Số lượng chuỗi bit bắt đầu bằng 1 và kết thúc bằng 00 là 25 = 32 Số lượng chuỗi bit thỏa đề bài là 128 + 64 − 32 = 160. Ví dụ: Có bao nhiêu chuỗi bit có độ dài 8 bit hoặc được bắt đầu bằng 01 hoặc được bắt đầu bằng 10 ? Tổ hợp & Phép đếm (Combinatorics & Counting) Page 14 TS. Trần Văn Hoài 2008-2009 Góc nhìn tập hợp Cho A1 và A2 là các tập hợp. T1 là công việc chọn 1 phần tử từ A1, T2 là công việc chọn 1 phần tử từ A2 . ☞ |A1 | cách làm T1, |A2 | cách làm T2 ☞ Số cách làm T1 hoặc T2 là |A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2| T1 và T2 có thể làm đồng thời Tổ hợp & Phép đếm (Combinatorics & Counting) Page 15 TS. Trần Văn Hoài 2008-2009 Giản đồ cây Giản đồ cây để giải bài Ví dụ: Có bao nhiêu chuỗi nhị phân dài 4 bit không có 2 số 1 liên tiếp ? toán đếm: 0 0 1 ☞ Nhánh: đại diện những 0 0 1 0 khả năng có thể có 0 1 0 1 1 ☞ Lá: là những kết quả 0 0 1 có thể có 1 0 Bit 1 Tổ hợp & Phép đếm (Combinatorics & Counting) 0 Bit 2 Bit 3 Bit 4 Page 16 TS. Trần Văn Hoài 2008-2009 Nguyên lý lồng chim bồ câu (Pigeonhole principle) Nếu có k + 1 hoặc nhiều hơn đồ vật được đặt vào trong k hộp thì có ít nhất một hộp chứa 2 hoặc nhiều hơn 2 đồ vật Ví dụ: Có 109 sinh viên và thang điểm có 110 bậc thì có ít nhất 2 sinh viên cùng điểm thi. Tổ hợp & Phép đếm (Combinatorics & Counting) Page 17 TS. Trần Văn Hoài 2008-2009 Nguyên lý Dirichlet tổng quát Nếu có N đồ vật được đặt vào trong k hộp, sẽ tồn tại một hộp chứa ít nhất ⌈N/k⌉ vật. Ví dụ: Trong 100 người có ít nhất ⌈100/12⌉ = 9 người cùng tháng sinh. Ví dụ: Xét 1 tháng 30 ngày. Một đội bóng chơi ít nhất 1 ngày 1 trận, nhưng cả tháng không quá 45 trận. Hãy chỉ ra rằng có những ngày liên tiếp đội bóng chơi tất cả 14 trận. Tổ hợp & Phép đếm (Combinatorics & Counting) Page 18 TS. Trần Văn Hoài 2008-2009 Hoán vị và chỉnh hợp Ví dụ: Bao nhiêu cách chọn 22 cầu thủ để tham dự đội tuyển bóng đá Việt Nam từ danh sách 30 cầu thủ đề cử ? Bao nhiêu cách chọn ra một danh sách có thứ tự 11 cầu thủ để thi đấu ? ☞ Hoán vị của 1 tập các đối tượng = 1 cách sắp xếp các đối tượng ☞ Một cách sắp xếp có thứ tự r phần tử của tập n phần tử được gọi là chỉnh hợp chập r của tập n phần tử n! P (n, r) = n(n − 1)(n − 2) . . . (n − r + 1) = (n − r)! Tổ hợp & Phép đếm (Combinatorics & Counting) Page 19 TS. Trần Văn Hoài 2008-2009 Ví dụ hoán vị và chỉnh hợp Ví dụ: Bao nhiêu cách chọn 22 cầu thủ để tham dự đội tuyển bóng đá Việt Nam từ danh sách 30 cầu thủ đề cử ? Bao nhiêu cách chọn ra một danh sách có thứ tự 11 cầu thủ để thi đấu ? Lời giải: Có P (22, 11) cách chọn danh sách có thứ tự 11 cầu thủ từ 22 cầu thủ trong đội. Ví dụ: Một thương nhân đi qua 6 tỉnh để buôn bán và chỉ qua một tỉnh một và chỉ một lần duy nhất mà thôi. Sau đó thương nhân quay về tỉnh xuất phát. Hỏi có bao nhiêu lộ trình ? Tổ hợp & Phép đếm (Combinatorics & Counting) Page 20 TS. Trần Văn Hoài 2008-2009 Tổ hợp Một tổ hợp chập r của một tập hợp với bản số n là một cách chọn không có thứ tự r phần tử của tập đã cho n! C(n, r) = r!(n − r)! Hệ quả dễ thấy C(n, r) = C(n, n − r) Ví dụ: Có C(30, 22) cách chọn ra 22 cầu thủ từ danh sách đề cử 30 cầu thủ. Tổ hợp & Phép đếm (Combinatorics & Counting) Page 21 TS. Trần Văn Hoài 2008-2009 Một số định lý Hằng đẳng thức Pascal C(n + 1, k) = C(n, k − 1) + C(n, k) Hằng đẳng thức Vandermonde C(m + n, r) = r X C(m, r − l)C(n, k) k=0 Định lý nhị thức (x + y)n = n X C(n, j)xn−j y j j=0 Tổ hợp & Phép đếm (Combinatorics & Counting) Page 22 TS. Trần Văn Hoài 2008-2009 Hoán vị có lặp Ví dụ: Từ bảng chữ cái tiếng Anh có thể tạo ra bao nhiêu chuỗi có độ dài n ? Lời giải: 26n (dùng quy tắc nhân) Có sự tương tự như chỉnh hợp (có thứ tự), nhưng cho phép sự lặp lại của các chữ cái. Số các chỉnh hợp lặp chập r từ tập n phần tử bằng nr Tổ hợp & Phép đếm (Combinatorics & Counting) Page 23 TS. Trần Văn Hoài 2008-2009 Tổ hợp lặp Ví dụ: Bao nhiêu cách bày mâm 5 quả nếu chỉ chọn các loại quả: dừa, đu đủ, xoài ? Lời giải: Liệt kê ra 21 trường hợp Số tổ hợp lặp chập r của n phần tử bằng C(n + r − 1, r) Tổ hợp & Phép đếm (Combinatorics & Counting) Page 24 TS. Trần Văn Hoài 2008-2009 Ví dụ: Phương trình x1 + x2 + x3 = 11 có bao nhiêu nghiệm nguyên không âm ? Lời giải: Mỗi nghiệm tương ứng với một cách chọn 11 phần tử của 1 tập có 3 loại sao cho có x1 phần tử loại 1, x2 phần tử loại 2, x3 phần tử loại 3. Suy ra số nghiệm là tổ hợp lặp chập 11 từ tập 3 phần tử C(3 + 11 − 1, 11) = C(13, 11) = 78 Tổ hợp & Phép đếm (Combinatorics & Counting) Page 25 TS. Trần Văn Hoài 2008-2009 Hoán vị có phần tử giống nhau Ví dụ: Có bao nhiêu chuỗi khác nhau bằng cách sắp xếp lại các chữ cái SUCCESS ? Lời giải: Không thể là hoán vị của 7 chữ cái vì có sự lặp lại. ➳ 3 chữ S, 2 chữ C, 1 chữ U, 1 chữ E ➳ Có C(7, 3) cách chọn chỗ cho 3 chữ cái S. Có C(4, 2) cách chọn chỗ cho 2 chữ cái C. Có C(2, 1) cách chọn chỗ cho 1 chữ U. Có C(1, 1) cách chọn chỗ cho 1 chữ E. Theo quy tắc nhân ta có số chuỗi là: 7!4!2!1! C(7, 3)C(4, 2)C(2, 1)C(1, 1) = 3!4!2!2!1!1!1!0! 7! = 3!2!1!1! = 420 Tổ hợp & Phép đếm (Combinatorics & Counting) Page 26 TS. Trần Văn Hoài 2008-2009 Hoán vị có phần tử giống nhau Tổng quát hóa n phần tử có n1 thuộc loại 1, ..., nk phần tử thuộc loại k. Số hoán vị là n! n1 ! . . . nk ! Tổ hợp & Phép đếm (Combinatorics & Counting) Page 27 TS. Trần Văn Hoài 2008-2009 Phân bổ đồ vật vào hộp n đồ vật khác nhau, bỏ vào trong k hộp sao cho có n1 vật trong hộp 1, ..., nk vật trong hộp nk . Số cách là n! n1 ! . . . nk ! Tổ hợp & Phép đếm (Combinatorics & Counting) Page 28