Tài liệu Phương pháp quỹ đạo và ứng dụng vào giải một số bài toán tổ hợp dành cho học sinh khá giỏi

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- PHẠM THỊ QUỲNH PHƢƠNG PHƢƠNG PHÁP “QUỸ ĐẠO” VÀ ỨNG DỤNG VÀO GIẢI MỘT SỐ BÀI TOÁN TỔ HỢP DÀNH CHO HỌC SINH KHÁ GIỎI LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- PHẠM THỊ QUỲNH PHƢƠNG PHƢƠNG PHÁP “QUỸ ĐẠO” VÀ ỨNG DỤNG VÀO GIẢI MỘT SỐ BÀI TOÁN TỔ HỢP DÀNH CHO HỌC SINH KHÁ GIỎI Chuyên ngành: Phƣơng pháp Toán sơ cấp Mã số: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. Trịnh Thanh Hải THÁI NGUYÊN - 2019 i Mục lục Một số ký hiệu và chữ viết tắt iii Lời nói đầu iv Chương 1 Một số kiến thức chuẩn bị 1.1 Bài toán đếm trong toán tổ hợp . . . . . . . . . . . . . . . . . . 1.2 Một số nguyên lý, tính chất của toán tổ hợp thường được vận dụng vào giải bài toán đếm của toán tổ hợp . . . . . . . . . . . 1.3 Một số phương pháp giải bài toán đếm của toán tổ hợp trong phạm vi chương trình toán THPT . . . . . . . . . . . . . . . . . 1.3.1 Đếm trực tiếp . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Đếm theo vị trí . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Đếm loại trừ . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.4 Chọn tập con trước, sắp xếp sau . . . . . . . . . . . . . . 1.3.5 Đếm theo “vách ngăn” . . . . . . . . . . . . . . . . . . . 1.3.6 Sử dụng nguyên lý bù trừ . . . . . . . . . . . . . . . . . 1.3.7 Sử dụng tính chất của song ánh . . . . . . . . . . . . . . 1.3.8 Sử dụng hàm sinh . . . . . . . . . . . . . . . . . . . . . . 1 1 4 4 6 7 7 8 9 11 13 Chương 2 Vận dụng phương pháp “quỹ toán tổ hợp 2.1 Phương pháp “quỹ đạo” . . . . . . . 2.1.1 Quan niệm về “quỹ đạo” . . . 2.1.2 Một số tính chất về “quỹ đạo” 2.2 Một số vận dụng . . . . . . . . . . . 2.2.1 Bài toán sắp hàng . . . . . . 2.2.2 Bài toán bỏ phiếu . . . . . . . 2.2.3 Quy tắc Pascal . . . . . . . . 15 15 15 16 20 20 23 24 4 đạo” vào giải một số bài . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 2.3 2.2.4 Một số bài toán khác . . . . . . . . . . . . . . . . . . . . Ý nghĩa của khái niệm “quỹ đạo” và phương pháp “quỹ đạo” . . 25 31 Kết luận 36 Tài liệu tham khảo 37 iii Một số ký hiệu và chữ viết tắt N N∗ Z R MO IMO Tập hợp các số tự nhiên. Tập hợp các số tự nhiên khác 0. Tập hợp các số nguyên. Tập hợp các số thực. National Mathematical Olympiad. Internation Mathematical Olympiad. iv Lời nói đầu 1. Lý do chọn đề tài Toán tổ hợp là một bài toán khó, thường xuất hiện trong các kì thi học sinh giỏi cấp tỉnh, cấp quốc gia và quốc tế. Chính vì vậy toán tổ hợp luôn dành được sự quan tâm rất lớn từ các bạn học sinh, các thầy, cô giáo và các nhà toán học. Một trong các phương pháp có hiệu quả để giải một số bài toán tổ hợp là phương pháp “quỹ đạo”. Ý tưởng của phương pháp “quỹ đạo” là chỉ ra cách giải thích hình học để đưa ra lời giải cho bài toán tổ hợp, mà chủ yếu là các bài toán tổ hợp đếm các đường đi (hay số các “quỹ đạo”) theo một tính chất xác định nào đó (hay còn gọi là phương pháp quy các bài toán đếm về các bài toán đếm số đường đi trên lưới nguyên). Phương pháp “quỹ đạo” không chỉ ứng dụng được vào giải một số bài toán tổ hợp liên quan đến lưới nguyên mà còn có thể vận dụng được để đưa ra lời giải cho một số bài toán về dãy số. Mặt khác, với các bài toán tối ưu hóa quen thuộc trong kinh tế, kỹ thuật như: Tìm đường đi ngắn nhất, tìm chu trình đi tối ưu nhất... thì ngoài các phương pháp quen thuộc như quy hoạch động, thử sai quay lui... ta có thể vận dụng tư tưởng của phương pháp “quỹ đạo” để đưa ra các thuật toán “tốt” hơn. Xuất phát từ thực tế trên và với mục đích tích lũy thêm các kiến thức về cách giải bài toán đếm của toán tổ hợp với phương pháp “quỹ đạo” và vận dụng vào giải một số bài toán đếm trong các đề thi học sinh giỏi trong nước và quốc tế làm tư liệu cho công việc giảng dạy của bản thân, em đã lựa chọn hướng nghiên cứu vận dụng phương pháp “quỹ đạo” vào giải một số bài toán đếm. Luận văn tập trung vào hoàn thành các nhiệm vụ chính sau • Tìm hiểu về bài toán đếm của toán tổ hợp và các nguyên lý, tính chất của toán tổ hợp thường được vận dụng để đưa ra lời giải cho các bài toán đếm. • Ý tưởng toán học của phương pháp “quỹ đạo” trong việc tìm lời giải cho bài toán đếm của toán tổ hợp. v • Sưu tầm một số bài toán, đề thi về bài toán đếm của toán tổ hợp dành cho học sinh giỏi. • Đưa ra ý nghĩa của khái niệm “quỹ đạo” và phương pháp “quỹ đạo” thông qua thuật toán đường đi của con Robot. 2. Nội dung của đề tài luận văn Ngoài phần mở đầu, kết luận, tài liệu tham khảo, luận văn gồm 2 chương Chương 1. Một số kiến thức chuẩn bị 1.1. Bài toán đếm trong toán tổ hợp. 1.2. Một số nguyên lý, tính chất của toán tổ hợp thường được vận dụng vào giải bài toán đếm của toán tổ hợp. 1.3. Một số phương pháp giải bài toán đếm của toán tổ hợp trong phạm vi chương trình toán Trung học phổ thông. Chương 2. Vận dụng phương pháp “quỹ đạo” vào giải một số bài toán tổ hợp 2.1. Phương pháp “quỹ đạo”. 2.2. Một số vận dụng. 2.3. Ý nghĩa của khái niệm “quỹ đạo” và phương pháp “quỹ đạo”. Luận văn được hoàn thành dưới sự hướng dẫn tận tình, chu đáo của thầy PGS. TS Trịnh Thanh Hải, các thầy cô giáo trong khoa Toán - Tin, trường Đại học Khoa học cùng toàn thể các bạn trong lớp Cao học K11 đã tạo mọi điều kiện, nhiệt tình ủng hộ em trong suốt quá trình làm luận văn. Em xin bày tỏ lòng biết ơn chân thành, sâu sắc với tất cả những đóng góp quý báu của thầy cô và các bạn đặc biệt là thầy PGS. TS Trịnh Thanh Hải. Tuy đã có nhiều cố gắng trong quá trình làm luận văn, nhưng do thời gian và kiến thức còn hạn chế nên luận văn không tránh khỏi những thiếu sót. Kính mong nhận được sự góp ý của quý thầy, cô và các bạn. Em xin chân thành cảm ơn! Thái Nguyên, ngày 28 tháng 12 năm 2019 Tác giả luận văn Phạm Thị Quỳnh Phương 1 Chương 1 Một số kiến thức chuẩn bị 1.1 Bài toán đếm trong toán tổ hợp Trong toán tổ hợp, bài toán đếm là bài toán nhằm trả lời câu hỏi: “Có bao nhiêu cấu hình tổ hợp thuộc dạng đã cho?”. Phương pháp đếm thường dựa vào một số quy tắc, nguyên lý đếm và một số kết quả đếm cho các cấu hình tổ hợp đơn giản. Hai quy tắc đếm cơ bản là quy tắc cộng và quy tắc nhân. Hai quy tắc đếm cơ bản Định nghĩa 1.1.1. (a). Quy tắc cộng: Một công việc được hoàn thành bởi một trong hai hành động. Nếu hành động thứ nhất có m cách thực hiện, hành động thứ hai có n cách thực hiện không trùng với bất kì cách nào của hành động thứ nhất thì công việc đó có m + n cách thực hiện. (b). Quy tắc nhân: Một công việc được hoàn thành bởi hai hành động liên tiếp. Nếu có m cách thực hiện hành động thứ nhất và ứng với mỗi cách đó có n cách thực hiện hành động thứ hai thì có m.n cách hoàn thành công việc. Hoán vị Định nghĩa 1.1.2. Cho tập hợp A gồm n phần tử (n ≥ 1). Mỗi kết quả của sự sắp xếp thứ tự n phần tử của tập hợp A được gọi là một hoán vị của n phần tử đó. • Kí hiệu: Pn là số các hoán vị của n phần tử. • Số các hoán vị: Pn = n! = 1 · 2 · · · (n − 1) · n. 2 Chỉnh hợp Định nghĩa 1.1.3. Cho tập hợp A gồm n phần tử (n ≥ 1). Kết quả của việc lấy k phần tử khác nhau từ n phần tử của tập hợp A và sắp xếp chúng theo một thứ tự nào đó được gọi là một chỉnh hợp chập k của n phần tử đã cho. • Kí hiệu: Akn là số các chỉnh hợp chập k của n phần tử, 1 ≤ k ≤ n. n! • Số các chỉnh hợp: Akn = = n. (n − 1) · · · (n − k + 1) (với 1 ≤ k ≤ n). (n − k)! Nhận xét: Mỗi hoán vị của n phần tử cũng là một chỉnh hợp chập n của n phần tử đó nên Pn = Ann . Tổ hợp Định nghĩa 1.1.4. Giả sử tập A gồm n phần tử (n ≥ 1). Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho. • Kí hiệu: Cnk là số các tổ hợp chập k của n phần tử (0 ≤ k ≤ n). n! (với 1 ≤ k ≤ n). • Số các tổ hợp: Cnk = k! (n − k)! Nhận xét: (a). Cnk = Cnn−k (0 ≤ k ≤ n). k−1 k (b). (công thức Pascal): Cn−1 + Cn−1 = Cnk (1 ≤ k ≤ n). Chỉnh hợp lặp Định nghĩa 1.1.5. Cho tập A có m phần tử. Ta rút ra từ A một phần tử bất kỳ, kí hiệu nó là a1 rồi trả lại nó vào tập hợp A. Ta lại rút ra từ A một phần tử, kí hiệu nó là a2 (a2 có thể lại chính là phần tử thứ nhất) rồi trả lại nó vào tập hợp A. Tiếp tục thao tác này k lần (k không nhất thiết nhỏ hơn hoặc bằng m ), ta tìm được một dãy (a1 , a2 , · · · , ak ) gồm k phần tử (có thể trùng nhau) của A. Một dãy như thế gọi là một chỉnh hợp có lặp chập k của m phần tử đã cho. Tập hợp tất cả các chỉnh hợp có lặp chập k lập nên từ các phần tử của một tập hợp A có m phần tử chính là tập hợp các bộ (a1 , a2 , · · · , ak ) với ai ∈ A. Vậy đó là tích Đề-các A × A ×{z · · · × A} = Ak . | k lần Định lý 1.1.1. Số chỉnh hợp có lặp chập k của m phần tử, kí hiệu là Akm , được   tính theo công thức Akm = Ak  = mk . 3 Chứng minh. Rõ ràng có m cách chọn một phần tử từ tập m phần tử cho mỗi một trong k vị trí của chỉnh hợp khi cho phép lặp. Vì vậy theo quy tắc nhân, có mk chỉnh hợp lặp chập k từ tập có m phần tử. Hoán vị lặp Trong bài toán đếm, một số phần tử có thể giống nhau. Khi đó cần phải cẩn thận, tránh đếm chúng hơn một lần. Định lý 1.1.2. Số các hoán vị của n phần tử trong đó có n1 phần tử như nhau thuộc loại 1, có n2 phần tử như nhau thuộc loại 2, · · · và có nk phần tử như n! . nhau thuộc loại k bằng n1 !n2 ! · · · nk ! Chứng minh. Để xác định số hoán vị trước tiên chúng ta nhận thấy có Cnn1 cách giữ n1 số cho n1 phần tử loại 1, còn lại n − n1 chỗ trống. n2 Sau đó, có Cn−n cách đặt n2 phần tử loại 2 vào hoán vị, còn lại n − n1 − n2 1 chỗ trống. Tiếp tục đặt các phần tử loại 3, loại 4, . . . , loại k − 1 vào chỗ trống trong hoán nk vị. Cuối cùng có Cn−n cách đặt nk phần tử loại k vào hoán vị. 1 −n2 −···−nk−1 Theo quy tắc nhân tất cả các hoán vị có thể là: n2 nk Cnn1 .Cn−n · · · Cn−n = 1 1 −n2 −···−nk−1 n! . n1 !n2 ! · · · nk ! Tổ hợp lặp Một tổ hợp lặp chập k của một tập hợp là một cách chọn không có thứ tự k phần tử có thể lặp lại của tập đã cho. Như vậy một tổ hợp lặp kiểu này là một dãy không kể thứ tự gồm k thành phần lấy từ tập n phần tử. Do đó có thể là k > n. k Định lý 1.1.3. Số tổ hợp lặp chập k từ tập n phần tử bằng Cn+k−1 . Chứng minh. Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một dãy n − 1 thanh đứng để phân cách các ngăn. Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần tử thứ i của tập xuất hiện trong một tổ hợp. Mỗi dãy n − 1 thanh và k ngôi sao ứng với một tổ hợp lặp chập k của n phần tử. Do đó mỗi dãy ứng với một cách chọn k chỗ cho k ngôi sao từ n + k − 1 chỗ chứa n − 1 thanh và k ngôi sao. Đó là điều cần chứng minh. 4 p n−1 . Tổ hợp có lặp Chú ý. Số tổ hợp có lặp chập p của n là Cnp = Cn+p−1 = Cn+p−1 lại khi một phần tử có thể xuất hiện nhiều lần và thứ tự của các phần tử không cần để ý. 1.2 Một số nguyên lý, tính chất của toán tổ hợp thường được vận dụng vào giải bài toán đếm của toán tổ hợp • Nguyên lý cộng: Nếu A, B là các tập hợp không giao nhau thì |A ∪ B| = |A| + |B| . • Nguyên lý cộng mở rộng: Nếu tập hợp hữu hạn C là hợp của n tập đôi một rời nhau C1 , C2 , · · · , Cn thì |C| = |C1 | + |C2 | + · · · + |Cn | Định nghĩa 1.2.1. Tích Descartes của hai tập hợp A, B kí hiệu bởi A × B là tập hợp tất cả các cặp thứ tự (a, b) với a ∈ A, b ∈ B. • Nguyên lý nhân: Nếu A và B là hai tập hợp hữu hạn thì A × B cũng hữu hạn và ta có |A × B| = |A| . |B| . Định nghĩa về tích Descartes và nguyên lý nhân trên đây có thể mở rộng cho nhiều tập hợp. Nguyên lý nhân có thể phát biểu một cách khác như sau: Nếu một quá trình có thể được thực hiện qua hai công đoạn: công đoạn I có n1 cách thực hiện, công đoạn II (sau khi thực hiện I) có n2 cách thực hiện. Khi đó có n1 .n2 cách thực hiện quá trình đó. • Nguyên lý thêm bớt: Với hai tập hữu hạn A, B bất kỳ ta có |A ∪ B| = |A| + |B| − |A ∩ B| . 1.3 Một số phương pháp giải bài toán đếm của toán tổ hợp trong phạm vi chương trình toán THPT 1.3.1 Đếm trực tiếp • Ý tưởng Tùy theo bài toán chúng ta có thể chia trường hợp hay không chia trường hợp. Nội dung: Đếm các trường hợp thỏa mãn yêu cầu bài toán. • Ví dụ minh họa 5 Ví dụ 1.3.1. Cho tập A = {0, 1, 2, 3, 4, 5, 6, 7}. a) Có thể lập được bao nhiêu số tự nhiên có 5 chữ số khác nhau luôn có mặt chữ số 2. b) Có thể lập được bao nhiêu số tự nhiên lẻ có 5 chữ số khác nhau luôn có mặt chữ số 2. Lời giải a) Gọi số cần tìm là n = a1 a2 a3 a4 a5 . +Trường hợp 1 a1 = 2 có 1 cách chọn. a2 a3 a4 a5 có A47 cách chọn. Suy ra ta có A47 = 840 số. + Trường hợp 2 a2 = 2 có 1 cách chọn. a1 6= 0 và a1 6= 2 nên có 6 cách chọn. a3 a4 a5 có A36 số. Suy ra ta có 6.A36 = 720 số. Vì vai trò của 2 trong các vị trí a2 , a3 , a4 , a5 là giống nhau nên Số cần tìm là 840 + 720.4 = 3720 số. b) Gọi số cần tìm là n = a1 a2 a3 a4 a5 . +Trường hợp 1 a5 lẻ nên có 4 cách chọn. a2 = 2 có 1 cách chọn. a2 a3 a4 có A36 số. Suy ra ta có 4.A36 = 480 số. + Trường hợp 2 a5 lẻ nên có 4 cách chọn. a2 = 2 có 1 cách chọn. a1 6= 0, a1 6= 2, a1 6= a5 nên có 5 cách chọn. a3 a4 có A25 cách chọn. Suy ra ta có 4.5.A25 = 400 số. Vì vai trò của 2 trong các vị trí a2 , a3 , a4 là giống nhau nên Số cần tìm là 480 + 400.3 = 1680 số. 6 1.3.2 Đếm theo vị trí • Ý tưởng + Chọn vị trí cho số thứ nhất theo yêu cầu bài toán, suy ra số vị trí cho các số tiếp theo. + Sắp xếp các số còn lại. • Ví dụ minh họa Ví dụ 1.3.2. Từ các chữ số thuộc tập hợp S = {1; 2; 3; . . . ; 8; 9} có bao nhiêu số có chín chữ số khác nhau sao cho chữ số 1 đứng trước chữ số 2, chữ số 3 đứng trước chữ số 4 và chữ số 5 đứng trước chữ số 6? Lời giải Chọn 2 vị trí để xếp 2 chữ số 1, 2 (số 5 đứng trước 6): có C52 cách. 3 chữ số còn lại có 3! cách. Vậy có 3!.C92 · C72 · C52 = 45360 số. Ví dụ 1.3.3. Cho tập A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Có bao nhiêu số tự nhiên chẵn có 5 chữ số khác nhau sao cho a) Luôn có mặt chữ số 3. b) Luôn có mặt chữ số 4. Lời giải Gọi số cần tìm là n = a1 a2 a3 a4 a5 . a) + a5 có 4 cách chọn. + Chữ số 3 có 3 vị trí. + 3 chữ số còn lại có A38 cách sắp xếp. Vậy có 4.4.A38 = 5376 số. b) + Trường hợp 1: a5 = 4, khi đó A48 = 1680 số. + Trường hợp 2: a5 6= 4, khi đó a5 có 3 cách chọn. Chữ số 4 có 4 vị trí. 3 chữ số còn lại có A37 cách sắp xếp. Suy ra ra có 3.4.A37 = 2520 số. 7 1.3.3 Đếm loại trừ • Ý tưởng Nội dung: Đếm loại trừ theo hai bước + Bước 1: Đếm số phương án xảy ra bất kỳ ta có kết quả n1 . + Bước 2: Đếm số phương án xảy ra không thỏa mãn yêu cầu bài toán ta có kết quả n2 . + Bước 3: Số phương án đúng là: n = n1 − n2 . Chú ý: Khi phương pháp đếm trực tiếp có nhiều trường hợp quá chúng ta sử dụng phương pháp đếm loại trừ. • Ví dụ minh họa Ví dụ 1.3.4. Cho tập A = {1, 2, 3, 4, 5, 6, 7}. Có bao nhiêu số lẻ có 4 chữ số khác nhau sao cho chữ số 4 luôn có mặt một lần. Lời giải Gọi số cần tìm là n = a1 a2 a3 a4 . + Đếm các số lẻ có 4 chữ số khác nhau là: a4 có 4 cách chọn (a4 ∈ {1, 3, 5, 7}); 3 chữ số còn lại có A36 cách chọn, suy ra có 4.A36 số. + Đếm các số lẻ có 4 chữ số khác nhau mà không có mặt chữ số 4 là: a4 có 4 cách chọn (a4 ∈ {1, 3, 5, 7}); 3 chữ số còn lại có A35 cách chọn (số 4 không có), suy ra có 4.A35 số. Các số cần tìm là 4.A36 − 4.A35 = 240 số. 1.3.4 Chọn tập con trước, sắp xếp sau • Ý tưởng + Bước 1: Chọn ra trước cho đủ số lượng và thỏa mãn tính chất mà bài toán yêu cầu (Ví dụ như chọn tập con có k phần tử từ n phần tử ta có Cnk cách). + Bước 2: Sắp xếp. • Chú ý: Những bài toán có sự sắp xếp, cạnh nhau, có mặt. • Ví dụ minh họa Ví dụ 1.3.5. Cho tập A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Có bao nhiêu số tự nhiên có 5 chữ số khác nhau sao cho: a) Luôn có mặt hai chữ số 2, 3. b) Luôn có mặt hai chữ số 2, 3 và hai chữ số này luôn đứng kề nhau. Lời giải 8 a) + Lấy ra 5 số từ tập A: Số 2, 3 có 1 cách chọn, 3 số còn lại được lấy từ tập A\{2, 3} nên có C73 cách, suy ra có C73 cách lấy ra 5 số mà 2, 3 luôn có mặt. + Sắp xếp 2 . 3 . Sắp xếp 5 số vào 5 vị trí ta có 5! cách. Vậy ta có C73 .5! = 4200 số. b) + Lấy ra 5 số từ tập A: Số 2, 3 có 1 cách chọn, 3 số còn lại được lấy từ tập A\{2, 3} nên có C73 cách, suy ra có C73 cách lấy ra 5 số mà 2, 3 luôn có mặt. + Sắp xếp 2,3 . . . Sắp xếp số 2, 3 kề nhau ta xem là một số a có 2! cách, sắp xếp số a với 3 số còn lại có 4! cách, từ đó số cách sắp xếp 5 chữ số đã chọn như trên là 2!.4! cách. Vậy ta có C73 .2!.4! = 1680 số. 1.3.5 Đếm theo “vách ngăn” • Ý tưởng + Bước 1: Sắp xếp m đối tượng vào m vị trí sẽ tạo ra m + 1 vách ngăn. + Bước 2: Sắp xếp đối tượng khác theo yêu cầu bài toán từ m + 1 vách ngăn nói trên. • Nhận xét: 1. Hầu hết các bài toán tổ hợp đều sử dụng một trong các phương pháp trên để giải quyết, tuy nhiên sự linh hoạt của phương pháp tùy thuộc vào khả năng của từng học sinh. 2. Đối với bài toán mà tập ban đầu có số 0 ta xét các trường hợp xem số 0 là một số có nghĩa ta được kết quả n1 , xét trường hợp số 0 đứng đầu ta có kết quả n2 , kết quả cần tìm là n1 − n2 . • Ví dụ minh họa Ví dụ 1.3.6. Cần sắp xếp 2 thầy giáo và 6 học sinh vào một dãy ghế dài sao cho 2 thầy giáo không ngồi cạnh nhau. 9 Lời giải + Xếp 6 học sinh vào 6 vị trí ta có 6! cách xếp. + 6 học sinh sẽ tạo ra 7 vách ngăn, ta đặt 2 thầy giáo vào 7 vách ngăn ta có A27 cách xếp. Khi đó số cách sắp xếp là 6!A27 = 30240. 1.3.6 Sử dụng nguyên lý bù trừ • Nguyên lý bù trừ Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. Cho A1 , A2 là hai tập hữu hạn, khi đó |A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 | . Từ đó với ba tập hợp hữu hạn A1 , A2 , A3 , ta có: |A1 ∪ A2 ∪ A3 | = |A1 |+|A2 |+|A3 |−|A1 ∩ A2 |−|A2 ∩ A3 |−|A3 ∩ A1 |+|A1 ∩ A2 ∩ A3 |. Và bằng quy nạp, với k tập hữu hạn A1 , A2 , . . . , Ak ta có: |A1 ∪ A2 ∪ . . . ∪ Ak | = N1 − N2 + N3 − . . . + (−1)k−1 Nk , trong đó Nm (1 ≤ m ≤ k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho, nghĩa là Nm = X |Ai1 ∩ Ai2 ∩ . . . ∩ Aim | . 1≤i1 a2 > . . . > ai . Khi đó tổng đan dấu của một tập con trên bằng (a1 − a2 + a3 − . . .) + (n − a1 + a2 − a3 + . . .) = n. Có 2n tập con của A suy ra có 2n−1 cặp tập hợp con loại 1 và loại 2 theo định 13 nghĩa trên. Vậy tổng của tất cả các tổng đan dấu bằng S = 2n−1 · n. 1.3.8 Sử dụng hàm sinh • Ý tưởng Hàm sinh có thể được áp dụng trong các bài toán đếm. Nói riêng các bài toán chọn các phần tử từ một tập hợp thông thường sẽ dẫn đến các hàm sinh. Khi hàm sinh được áp dụng theo cách này, hệ số của Xn chính là số cách chọn n phần tử, tức là với an là hệ số của với mọi n lớn hơn hoặc bằng 2 thì hàm sinh P của số cách chọn sẽ là F (x) = n≥0 an xn . • Ví dụ minh họa Ví dụ 1.3.12. Có bao nhiêu cách chọn n phần tử phân biệt từ tập hợp k phần tử. Lời giải Bài toán này có thể giải quyết dễ dàng bằng công thức tổ hợp. Nhưng lần này chúng ta sẽ sử dụng hàm sinh. Cụ thể: Đầu tiên ta xét tập hợp có một phần tử {a1 }.Ta có: 1 cách chọn 0 phần tử. 1 cách chọn 1 phần tử. 0 cách chọn 2 phần tử trở lên. Suy ra hàm sinh cho số cách chọn n phần tử từ tập {a1 } là 1 + x. Tương tự như vậy, hàm sinh cho số cách chọn n phần tử từ tập {ai } (1 ≤ i ≤ k) cũng là 1 + x (không phụ thuộc vào sự khác biệt giữa các {ai }). Tiếp tục xét tập 2 phần tử {a1 , a2 } ta có 1 cách chọn 0 phần tử. 2 cách chọn 1 phần tử. 1 cách chọn 2 phần tử. 0 cách chọn 3 phần tử trở lên. Suy ra hàm sinh cho số cách chọn n phần tử từ tập {a1 , a2 } là 1 + 2x + x2 = (1 + x)2 = (1 + x)(1 + x) Tiếp tục áp dụng quy tắc này ta sẽ được hàm sinh cho số cách chọn các phần tử từ tập k phần tử. (1 + x)(1 + x) . . . (1 + x) = (1 + x)k .