Tài liệu Một vài nguyên lý và bài toán tổ hợp

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ NGUYỄN NGỌC MAI MỘT VÀI NGUYÊN LÝ VÀ BÀI TOÁN TỔ HỢP LUẬN VĂN THẠC SỸ TOÁN HỌC HÀ NỘI- 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ NGUYỄN NGỌC MAI MỘT VÀI NGUYÊN LÝ VÀ BÀI TOÁN TỔ HỢP Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60460113 LUẬN VĂN THẠC SỸ TOÁN HỌC Người hướng dẫn khoa học PGS. TS. ĐÀM VĂN NHỈ HÀ NỘI- 2014 Mục lục Mở đầu 1 Kiến thức chuẩn bị 1.1 Nguyên lý quy nạp . . . 1.2 Hai quy tắc đếm cơ bản . 1.3 Hoán vị . . . . . . . . . 1.4 Chỉnh hợp . . . . . . . . 1.5 Tổ hợp . . . . . . . . . . 1.5.1 Tổ hợp . . . . . . 1.5.2 Ứng dụng trong số 1.6 Nhị thức Newton . . . . 1.7 Đồ thị cây . . . . . . . . 3 . . . . . . . . . . . . . . . . . . học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Một vài nguyên lý trong tổ hợp 2.1 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . 2.1.1 Nguyên lý Dirichlet . . . . . . . . . . . . . 2.1.2 Nguyên lý Dirichlet áp dụng trong hình học 2.2 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . 2.3 Nguyên lý cực hạn . . . . . . . . . . . . . . . . . . 2.4 Nguyên lý bất biến . . . . . . . . . . . . . . . . . 3 Một vài đồng nhất thức trong tổ hợp 3.1 Xây dựng đồng nhất thức qua hệ phương trình . 3.2 Xây dựng đồng nhất thức qua số phức . . . . . 3.3 Xây dựng đồng nhất thức qua hàm sinh . . . . . 3.3.1 Khái niệm hàm sinh . . . . . . . . . . . . 3.3.2 Một số đồng nhất thức liên quan đến hàm 3.3.3 Ứng dụng của hàm sinh . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 8 9 11 14 14 16 18 20 26 . . . 26 . . . 26 tổ hợp 31 . . . 34 . . . 42 . . . 51 . . . . . . . . . . . . sinh . . . . . . . . . . . . . . . . . 60 60 66 69 70 70 71 77 78 Lời cảm ơn Tôi xin được bày tỏ lòng kính trọng và biết ơn sâu sắc đến PGS.TS Đàm Văn Nhỉ. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắc mắc của tôi trong suốt quá trình tôi thực hiện đề tài. Tôi xin gửi lời cảm ơn chân thành tới các thầy cô Khoa Toán - Cơ - Tin học, Phòng Sau đại học - Trường Đại học Khoa học Tự nhiên- Đại học Quốc gia Hà Nội; các thầy cô đã tham gia giảng dạy khóa cao học 2011-2013. Cuối cùng, tôi xin chân thành cảm ơn gia đình và bạn bè đã luôn động viên tôi trong suốt quá trình học tập và thực hiện luận văn. 2 Mở đầu Tư duy về tổ hợp xuất hiện từ rất sớm trong lịch sử phát triển của nhân loại. Tuy nhiên, lý thuyết tổ hợp được xem hình thành như một ngành toán học vào khoảng thế kỷ 17 bằng một loạt các công trình nổi tiếng của các nhà toán học như Passcal, Fermat, Leibniz, Euler, . . . . Kể từ sau khi tin học ra đời, lý thuyết tổ hợp phát triển ngày càng mạnh mẽ. Các vấn đề liên quan đến lý thuyết tổ hợp là một bộ phận quan trọng, hấp dẫn và lí thú của toán học nói chung và của toán rời rạc nói riêng. Nó không chỉ có nội dung phong phú, đa dạng, mà còn có nhiều ứng dụng trong thực tế đời sống. Trong toán sơ cấp, tổ hợp cũng xuất hiện với nhiều bài toán hay với độ khó cao. Khi giải các bài toán tổ hợp, ta phải liệt kê, đếm các đối tượng theo các tính chất nào đó. Để làm được việc này, ngoài việc sử dụng hai quy tắc đếm cơ bản, các kiến thức về hoán vị, chỉnh hợp, tổ hợp, trong nhiều bài toán ta phải sử dụng một số nguyên lý khác trong tổ hợp. Vì vậy, để hiểu rõ và nắm bắt sâu hơn vể vấn đề này, tôi đã chọn đề tài Một vài nguyên lý và bài toán tổ hợp. Luận văn đã trình bày một số nguyên lý cơ bản trong tổ hợp và xây dựng một số bài toán áp dụng. Luận văn gồm phần mở đầu, ba chương, kết luận và danh mục tài liệu tham khảo. Chương 1 : Kiến thức chuẩn bị. Trong chương này, tác giả đã trình bày một số lý thuyết về nguyên lý quy nạp, hai quy tắc đếm cơ bản, hoán vị, chỉnh hợp, tổ hợp, nhị thức Newton và đồ thị cây. Chương 2 : Một vài nguyên lý trong tổ hợp. Chương 2 gồm 4 nội dung chính, trình bày bốn nguyên lý cơ bản trong tổ hợp và các ví dụ áp dụng các nguyên lý đó. Cụ thể là: Mục 2.1 trình bày nguyên lý thứ nhất: Nguyên lý Dirichlet. Nguyên lý này còn được gọi là nguyên lý lồng chim bồ câu. Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất có ngăn 3 có nhiều hơn 1 con chim. Phát triển dạng toán này, Piter Gustave Dirichlet đã đưa ra một nguyên lý chứng minh toán học đơn giản, được phát biểu như sau: "Nếu có N đồ vật được đặt vào k hộp thì tồn tại một hộp chứa ít nhất N  + 1 đồ vật." k Mục 2.2 trình bày Nguyên lý bù trừ. Khi hai công việc có thể làm đồng thời, chúng 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. Cộng số cách thực hiện mỗi việc sẽ dẫn đến sự trùng lặp, vì những cách làm cả hai công việc sẽ được tính hai lần. Để 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 công việc. Nguyên lý này được mở rộng cho trường hợp đếm số phần tử của hợp các tập hợp bất kì. Đó là Nguyên lý bù trừ. Nguyên lý thứ 3 là Nguyên lý cực hạn, được trình bày trong mục 2. 3. Nguyên lý này chỉ ra rằng tồn tại phần tử lớn nhất và phần tử nhỏ nhất của một tập hợp hữu hạn. Nguyên lý này có rất nhiều ứng dụng trong việc giải các bài toán tổ hợp, giải một số phương trình nghiệm nguyên, chứng minh các bất đẳng thức, . . . . Cuối cùng, mục 2. 4 trình bày nguyên lý thứ 4 là Nguyên lý bất biến. Trong mục này, tác giả đã trình bày hai mẫu bài toán tổng quát thường được giải bằng nguyên lý bất biến và đưa ra một ví dụ sử dụng nguyên lý bất biến. Chương 3. Một vài đồng nhất thức trong tổ hợp. Chương này trình bày một số ví dụ về xây dựng đồng nhất thức trong tổ hợp qua hệ phương trình, số phức và hàm sinh, . . . 4 Chương 1 Kiến thức chuẩn bị 1.1 Nguyên lý quy nạp Mệnh đề 1.1. [Nguyên lý thứ nhất]. Nếu mệnh đề P (n), phụ thuộc vào số tự nhiên n thỏa mãn: (i) P (α) đúng với một α ∈ N. (ii) P (n + 1) đúng khi P (n) đúng, ở đó n ≥ α, n ∈ N thì P (n) đúng với mọi số tự nhiên n ≥ α. Mệnh đề 1.2. [Nguyên lý thứ hai]. Nếu mệnh đề P (n), phụ thuộc vào số tự nhiên n thỏa mãn: (i) P (α) đúng với một α ∈ N. (ii) P (n + 1) đúng khi P (α), P (α + 1), ..., P (n) đúng, ở đó n ≥ α, n ∈ N, thì P (n) đúng với mọi số tự nhiên n ≥ α. Cách chứng minh một định lý hay một bài toán có sử dụng nguyên lý quy nạp được gọi là phép quy nạp hay phương pháp quy nạp toán học. Sau đây, ta sẽ xét một số ví dụ áp dụng hai nguyên lý này. Ví dụ 1.1. Chứng minh rằng, với số nguyên n ≥ 1 và số thực a > 0 ta luôn có đồng nhất thức n X n!an (−1)k Cnk = Qn . k=1 ak + 1 k=1 (1 + ka) Lời giải. Trước tiên, ta chứng minh bằng quy nạp theo n rằng Z 1 n!an (1 − xa )n dx = Qn . k=1 (1 + ka) 0 5 Thật vậy Với n = 1 ta có Z 1 0 a xa+1 1 1!a1 (1 − x )dx = x − = .  = a+1 0 a+1 1 + 1.a   a Suy ra khẳng định đúng với n = 1. Đặt Z 1 (1 − xa )n dx. In = 0 Giả sử n!an . k=1 (1 + ka) In = Qn Ta phải chứng minh (n + 1)!an+1 In+1 = Qn+1 . (1 + ka) k=1 Ta có Z 1 a n+1 (1 − x ) In+1 = 1 Z xa (1 − xa )n dx = (n + 1)a(In − In+! ). dx = (n + 1)a 0 0 Hay In+1 = (n + 1)a In . 1 + (n + 1)a Theo giả thiết quy nạp ta có (n + 1)!an+1 In+1 = Qn+1 . k=1 (1 + ka) Suy ra khẳng định trên đúng với n + 1. Vậy khẳng đinh trên đúng với mọi n ≥ 1. Từ đó suy ra n X (−1)k C k n k=0 ak + 1 = n X (−1) k=0 k Cnk Z 1 Z ak x dx = 0 0 1 n!an . k=1 (1 + ka) (1 − xa )n dx = Qn Ví dụ 1.2. Chứng minh rằng với số nguyên n > 0 ta có đồng nhất thức 1.2 + 2.22 + · · · + n.2n = (n − 1)2n+1 + 2. 6 Lời giải. Ta chứng minh bằng quy nạp theo n. + Với n = 1 ta có 1.2 = 2 = (1 − 1)21+1 + 2. Chứng tỏ kết luận đúng với n = 1. + Giả sử kết luận đúng với n ≥ 1. Khi đó 1.2 + 2.22 + · · · + n.2n = (n − 1)2n+1 + 2. + Ta phải chứng minh kết luận đúng với n + 1. Tức là 1.2 + 2.22 + · · · + n.2n + (n + 1)2(n+1) = n2n+2 + 2. Thật vậy, ta có 1.2 + 2.22 + · · · + n.2n + (n + 1)2(n+1) = (n − 1)2n+1 + 2 + (n + 1)2n+1 = n2n+2 + 2. Chứng tỏ kết luận đúng với n + 1. Vậy khẳng định đúng với mọi số nguyên n > 0. Ví dụ 1.3. Dãy (an ) được cho như sau: a0 = 1, a1 = 3, a2 = 6, a3 = 10, a4 = 15, a5 = 21, .... Xác định (an ) theo n và chứng minh bất đẳng thức T = 1− 1
1
1
1 1 1
1− 1− ... 1 − < + . 3 6 10 an 3 n Lời giải. Ta có a0 = 1, a1 = 3 = a0 + 1 + 1, a2 = 6 = a1 + 2 + 1, a3 = 10 = a2 + 3 + 1, a4 = 15 = a3 + 4 + 1, a5 = 21 = a4 + 5 + 1, ... Suy ra an = an−1 + n + 1. Điều này dễ dàng có được bằng chứng minh quy nạp. (n + 1)(n + 2) . 2 1 ak − 1 (k + 1)(k + 2) − 2 k(k + 3) Suy ra 1 − = = = . ak ak (k + 1)(k + 2) (k + 1)(k + 2) Vậy an = 1 + 2 + 3 + 4 + ... + n + n + 1 = Như vậy 1− 1 1
1
= 1− 1+ . ak k+1 k+2 7 Suy ra 1
1
1
1
1
1
1+ 1− 1+ ... 1 − 1+ 2 3 3 4 n+1 n+2
1 1
1
1
1 1
= 1 − 2 1 − 2 1 − 2 ... 1 − 1+ 2 2 3 4 5 (n + 1) (n + 2) 2 2 2 2 (n + 1) − 1
1
1 3 − 1
4 − 1
5 − 1
. . . 1 + = 2 32 42 52 (n + 1)2 (n + 2) 2 2 2 2 2.3.4 .5 . . . (n − 1) .n (n + 1)(n + 2)(n + 3) = 2.32 .42 .52 . . . (n − 1)2 .n2 (n + 1)2 (n + 2) n+3 n+3 1 1 = < = + . 3(n + 1) 3n 3 n T = 1− Vậy an = 1.2 1 1 (n + 1)(n + 2) và T < + . 2 3 n Hai quy tắc đếm cơ bản Chương trình toán phổ thông lớp 11 đã trang bị cho học sinh hai quy tắc đếm cơ bản, đó là quy tắc cộng và quy tắc nhân. Đây là hai công cụ quan trọng giúp học sinh giải được một số bài toán tổ hợp đơn giản. Quy tắc cộng được phát biểu như sau: Giả sử, một công việc có thể được thực hiện theo một trong k phương án A1 , A2 , . . . , Ak . Có n1 cách thực hiện phương án A1 , n2 cách thực hiện phương án A2 , . . . , nk cách thực hiện phương án Ak . Khi đó công việc có thể được thực hiện bởi n1 + n2 + · · · + nk cách. Bản chất của quy tắc cộng là công thức tính số phần tử của hợp n tập hợp hữu hạn đôi một không giao nhau. Cụ thể ta có: Cho A1 , A2 , . . . , Ak là các tập rời nhau. Khi đó         A1 ∪ A2 ∪ · · · ∪ Ak  = A1  + A2  + · · · + Ak . Khi một công việc được thực hiện bởi nhiều công đoạn liên tiếp, thì ta phải sử dụng quy tắc nhân. Quy tắc nhân cho nhiều công đoạn được phát biểu như sau: Giả sử một công việc nào đó bao gồm k công đoạn A1 , A2 , . . . , Ak . Công đoạn A1 có thể thực hiện theo n1 cách, công đoạn A2 có thể thực hiện theo n2 cách, . . . , công đoạn Ak có thể thực hiện theo nk cách. Khi đó công việc có thể thực hiện theo n1 n2 . . . nk cách. 8 Quy tắc nhân cũng có thể được phát biểu dưới dạng tập hợp như sau: Cho A1 , A2 , . . . , Ak là các tập hợp hữu hạn. Khi đó, số cách chọn một bộ gồm k phần tử (a1 , a2 , . . . , ak ), ai ∈ Ai , i = 1, 2, . . . , k là         A1 × A2 × · · · × Ak  = A1  × A2  × · · · × Ak . 1.3 Hoán vị Hoán vị thực chất chính là một cách sắp xếp nào đó các phần tử của một tập hợp. Khi các phần tử của tập hợp phân biệt và không được sử dụng lặp lại thì ta có hoán vị không lặp, gọi tắt là hoán vị. Hoán vị không lặp (hoán vị) được định nghĩa như sau: Định nghĩa 1.1. Cho tập A có n phần tử (n ≥ 1). Khi sắp xếp n phần tử này theo một thứ tự, ta được một hoán vị các phần tử của tập A (gọi tắt là một hoán vị của A). Kí hiệu: Số hoán vị của n phần tử là Pn . Để tính số hoán vị không lặp của một tập hợp gồm n phần tử, ta áp dụng định lý sau: Định lý 1.1. Số các hoán vị của tập có n phần tử là Pn = n! = n(n − 1) . . . 2.1. (1.1) Chứng minh. Giả sử, tập A có n phần tử. Việc sắp xếp thứ tự n phần tử của A là một công việc gồm n công đoạn: Công đoạn 1: Chọn phần tử để xếp vào vị trí thứ nhất. Trong công đoạn này, ta có thể chọn bất kì phần tử nào trong n phần tử của A nên có n cách thực hiện. Công đoạn 2: Chọn phần tử để xếp vào vị trí thứ 2. Sau khi thực hiện xong công đoạn thứ nhất, ở công đoạn thứ 2 ta có thể chọn bất kì phần tử nào trong n − 1 phần tử còn lại của A để xếp vào vị trí thứ 2 nên có n − 1 cách thực hiện. Công đoạn 3: Chọn phần tử xếp vào vị trí thứ 3. Lập luận tương tự, ở công đoạn 3 có n − 2 cách thực hiện. ... Công đoạn n: Chọn phần tử xếp vào vị trí thứ n. Sau khi thực hiện xong n − 1 công đoạn trên thì tập A chỉ còn 1 phần tử nên công đoạn thứ n có 1 cách 9 thực hiện. Theo quy tắc nhân, có tất cả n(n − 1)(n − 2) . . . 1 = n! cách sắp xếp thứ tự n phần tử của tập A . Tức là có Pn = n! hoán vị. Chú ý 1.1. Quy ước 0! = 1 nên công thức (1.1) đúng với n ≥ 0 Trong một số bài toán đếm, khi hoán vị n phần tử mà có các phần tử giống nhau hoặc được sử dụng lặp lại nhiều lần thì khi đếm số các hoán vị này cần thận trọng, tránh đếm chúng hơn một lần. Khi đó, công thức tính số hoán vị trên không sử dụng được. Ta phải sử dụng công thức tính số hoán vị lặp. Định nghĩa về hoán vị lặp được phát biểu như sau: Định nghĩa 1.2. Hoán vị mà trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị lặp. Định lý 1.2. Số hoán vị của n phần tử, trong đó có n1 phần tử giống nhau thuộc loại 1, n2 phần tử giống nhau thuộc loại 2, . . . , nk phần tử giống nhau thuộc loại k , là n! . n1 !n2 ! . . . nk ! (1.2) Chứng minh. Để xách định số hoán vị, trước tiên ta thấy có Cnn1 cách giữ n1 chỗ cho n1 phần tử loại 1, còn lại n − n1 chỗ trống. Sau đó, đặt n − 2 phần n2 tử loại 2 vào hoán vị. Có Cn−n cách đặt, còn lại n − n1 − n2 chỗ trống. Tiếp 1 tục, đặt các phần tử loại 3, loại 4, . . . , loại k − 1 vào hoán vị. Cuối cùng, có nk 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, có tất cả các hoán vị là nk n2 Cnn1 Cn−n . . . Cn−n = 1 1 −n2 −···−nk−1 = (n − n1 )! (n − n1 − · · · − nk−1 )! n! n! ... = . n1 !(n − n1 )! n2 !(n − n1 − n2 )! nk !0! n1 !n2 ! . . . nk ! Ví dụ 1.4. Một lớp có 100 sinh viên gồm 50 nam và 50 nữ. Giả sử 100 em xếp thành một hàng thẳng. Tính số cách xếp để có ít nhất có hai em cùng giới đứng cạnh nhau. Lời giải. Đánh số vị trí đứng từ 1 đến 100. Xếp 100 em vào 100 vị trí là một phép hoán vị của 100 phần tử. Tất cả có 100! cách xếp. Tính số cách xếp để không có hai người cùng giới đứng cạnh nhau: Lần đầu xếp các em nữ ở vị trí lẻ, các em nam đứng ở vị trí chẵn. Có 50!50! cách xếp. 10 Lần sau, xếp các em nữ ở vị trí chẵn, các em nam ở vị trí lẻ. Có 50!50! cách xếp. Vậy số cách xếp cần tính là 100! − 2.50!50!. Ví dụ 1.5. Giả sử các số a1 , a2 , . . . , an , . . . được định nghĩa như sau : a1 = 0, a2 = 1 và an+1 = (n + 1)an + (−1)n+1 , với mọi số nguyên n ≥ 1. Chứng minh rằng 1 1
1 1 1 an = P n − + − + · · · + (−1)n với n ≥ 1. P0 P1 P2 P3 Pn 1
1 − . Kết luận đúng với n = 1. P0 P1 1 1 1 1 Giả sử kết luận đúng với n, có nghĩa là an = Pn − + − + ··· + P0 P1 P2 P3 1
(−1)n với n ≥ 1. Pn Ta chứng minh khẳng định đúng với n + 1. Thật vậy: Lời giải. Với n = 1, ta có a1 = 0 = P1 an+1 = (n + 1)an + (−1)n+1 1 1 1 1 1
= (n + 1)Pn − + − + · · · + (−1)n + (−1)n+1 P0 P1 P2 P3 Pn
1 1 1 1 1 + (−1)n+1 = Pn+1 − + − + · · · + (−1)n P0 P1 P2 P3 Pn 1 1 1 1 1 1
= Pn+1 − + − + · · · + (−1)n + (−1)n+1 . P0 P1 P2 P3 Pn Pn+1 Do đó an = Pn 1 1 1 1 1
− + − + · · · + (−1)n với n ≥ 1. P0 P1 P2 P3 Pn Ví dụ 1.6. Giả sử m và k là những số nguyên dương và đặt n = mk . Kí hiệu T là số cách phân chia n đồ vật khác nhau xếp vào k hộp giống nhau sao cho mỗi hộp chứa đúng m đồ vật. Khi đó T = n! . k!(m!)k Lời giải. Ta coi k hộp là khác nhau. Khi đó số cách phân chia n đồ vật vào k hộp sao cho mỗi hộp chứa đúng m đồ vật là n! n! . Do k hộp = m!m!...m! (m!)k giống nhau nên mỗi cách phân chia xuất hiện k! lần. Vậy thực tế số cách phân chia là T = 1.4 n! . k!(m!)k Chỉnh hợp Trước tiên, ta có định nghĩa chỉnh hợp không lặp, gọi tắt là chỉnh hợp. 11 Định nghĩa 1.3. Cho tập A gồm n phần tử và số nguyên k , 1 ≤ k ≤ n. Khi lấy ra k phần tử của A và sắp xếp chúng theo một thứ tự, ta được một chỉnh hợp chập k của n phần tử của A, gọi tắt là một chỉnh hợp chập k của A. Kí hiệu: Số chỉnh hợp chập k của tập A có n phần tử là Akn . Định lý 1.3. Số các chỉnh hợp chập k của một tập có n phần tử ( 1 ≤ k ≤ n) là n! Akn = = n(n − 1) . . . (n − k + 1). (1.3) (n − k)! Chứng minh. Việc lập một chỉnh hợp chập k của một tập hợp có n phần tử được coi như một công việc gồm k công đoạn như sau: Công đoạn 1: Chọn phần tử xếp vào vị trí thứ nhất. Vì tập hợp có n phần tử nên công đoạn này có n cách thực hiện. Công đoạn 2: Chọn phần tử xếp vào vị trí thứ 2. Ở công đoạn 2, tập hợp chỉ còn n − 1 phần tử chưa chọn nên có n − 1 cách thực hiện. Công đoạn 3: Chọn phần tử xếp vào vị trí thứ 3. Ở công đoạn 3, tập hợp chỉ còn n − 2 phần tử chưa chọn nên có n − 2 cách thực hiện. ... Công đoạn k : Chọn phần tử xếp vào vị trí thứ k . Lập luận tương tự, ở công đoạn k, có n − k + 1 cách thực hiện. Theo quy tắc nhân, ta có n(n − 1) . . . (n − k + 1) cách thực hiện công việc. Hay có n(n − 1) . . . (n − k + 1) cách lập ra một chỉnh hợp chập k của n phần tử. Vậy Akn = n(n − 1) . . . (n − k + 1) = n! . (n − k)! Chú ý 1.2. Quy ước A0n = 1 nên công thức (1.3) đúng với 0 ≤ k ≤ n. Trong các bài toán đếm sử dụng chỉnh hợp không lặp, thì các phần tử được sử dụng nhiều nhất một lần. Nhưng trong thực tế, nhiều bài toán đếm, các phần tử có thể được sử dụng nhiều hơn một lần. Khi đó, áp dụng chỉnh hợp không lặp trong các bài toán đó không còn đúng nữa. Vì vậy, ta có khái niệm chỉnh hợp lặp. Định nghĩa 1.4. Cho tập hữu hạn A gồm n phần tử. Mỗi dãy có độ dài k các phần tử của A, mà mỗi phần tử có thể lặp lại nhiều lần và được xếp theo một thứ tự nhất định, được gọi là một chỉnh hợp lặp chập k của n phần tử của A. Kí hiệu: Số chỉnh hợp lặp chập k của n phần tử là Akn . 12 Định lý 1.4. Số chỉnh hợp lặp chập k của n phần tử là Akn = nk . (1.4) Chứng minh. Việc lập một chỉnh hợp lặp chập k của một tập hợp có n phần tử được coi như một công việc gồm k công đoạn: Công đoạn 1 là chọn phần tử vào vị trí thứ nhất, công đoạn 2 là chọn phần tử vào vị trí thứ 2, công đoạn 3 là chọn phần tử vào vị trí thứ 3, . . . , công đoạn k là chọn phần tử vào vị trí thứ k . Vì các phần tử có thể lặp lại nhiều lần nên ở mỗi công đoạn, ta đều có n cách chọn một phần tử từ tập hợp có n phần tử cho mỗi một trong k vị trí của chỉnh hợp. Theo quy tắc nhân, có n.n . . . n} = nk chỉnh hợp lặp chập k của n | {z k lần phần tử. Ví dụ 1.7. Một cuộc khiêu vũ có 10 nam và 8 nữ tham gia. Người ta chọn có thứ tự 3 nam và 3 nữ để ghép thành 3 cặp. Hỏi có bao nhiêu cách chọn? Lời giải. Chọn có thứ tự 3 nam trong số 10 nam là một chỉnh hợp chập 3 của 10. Số cách chọn là A310 = 720 cách chọn nam. Chọn có thứ tự 3 nữ trong số 8 nữ là một chỉnh hợp chập 3 của 8. Số cách chọn là A38 = 336 cách chọn nữ. Mỗi cách chọn nam lại tương ứng với tất cả các cách chọn nữ nên tất cả có số cách chọn là 720.336 = 241920 cách chọn. Ví dụ 1.8. Có thể lập được bao nhiêu biển số xe với hai chữ cái đầu thuộc tập {A, B, C, D, E}. Tiếp theo là một số nguyên dương gồm năm chữ số chia hết cho 5. Lời giải. Giả sử một biển số xe nào đó có dạng XY abcde. Vì X, Y có thể trùng nhau nên XY là chỉnh hợp lặp chập 2 của 5 phần tử A, B, C, D, E . Số cách chọn XY là A25 = 52 = 25. Do a 6= 0 nên a có 9 cách chọn. . Vì abcde..5 nên e = 0 hoặc e = 5. Suy ra e có 2 cách chọn. Do b, c, d có thể trùng nhau nên số cách chọn mỗi số bcd là chỉnh hợp lặp chập 3 của 10. Bởi vậy, số cách chọn số bcd là A310 = 103 = 1000. Vậy số biển số xe có thể lập được theo yêu cầu là 25.9.2.1000 = 450000. 13 1.5 Tổ hợp 1.5.1 Tổ hợp Định nghĩa 1.5. Cho tập A có n phần tử và số nguyên k với 1 ≤ k ≤ n. Mỗi tập con của A có k phần tử được gọi là một tổ hợp chập k của n phần tử của A , gọi tắt là một tổ hợp chập k của A. Kí hiệu: Số tổ hợp chập k của n phần tử là Cnk . Định lý 1.5. Số các tổ hợp chập k của một tập hợp có n phần tử, với 1 ≤ k ≤ n, là Cnk = Akn n! = . k! k!(n − k)! (1.5) Chứng minh. Giả sử, ta lập được một tổ hợp chập k của tập A có n phần tử. Mỗi cách sắp xếp thứ tự các phần tử của một tổ hợp chập k của A cho ta một chỉnh hợp chập k của A. Nói cách khác, mỗi hoán vị của một tổ hợp chập k của A cho ta một chỉnh hợp chập k của A. Vậy từ một tổ hợp chập k của A ta lập được k! chỉnh hợp chập k của A. Suy ra Akn = Cnk k! hay Cnk = Akn n! = . k! k!(n − k)! Chú ý 1.3. Ta quy ước Cn0 = 1 nên công thức (1.5) đúng với mọi số nguyên k thỏa mãn 0 ≤ k ≤ n. Hệ quả 1.1. Cho n và k là các số nguyên không âm sao cho k ≤ n . Khi đó Cnk = Cnn−k . Chứng minh. Theo định lý 1.5 ta có Cnk = và Cnn−k = n! k!(n − k)! n! n! = . (n − k)![n − (n − k)]! (n − k)!k! Suy ra Cnk = Cnn−k . 14 Định nghĩa 1.6. Cho tập A gồm n phần tử (n ≥ 1). Một tổ hợp lặp chập k của n phần tử của A (k không nhất thiết phải nhỏ hơn n) là một bộ gồm k phần tử, mà mỗi phần tử này có thể lặp lại của tập hợp A. Kí hiệu: Số tổ hợp lặp chập k của n phần tử là Cnk . Định lý 1.6. Số các tổ hợp lặp chập k của tập n phần tử là k Cnk = Cn+k−1 . (1.6) Chứng minh. Mỗi tổ hợp lặp chập k của n phần tử có thể biểu diễn bằng một dãy n − 1 thanh đứng và k ngôi sao. Ta dùng n − 1 thanh đứng để ngăn cách các ngăn. Ngăn thứ i chứa thêm một ngôi sao nếu phần tử thứ i của tập hợp xuất hiện trong tổ hợp. Ví dụ, tổ hợp lặp chập 6 của tập 4 phần tử được biểu thị bằng 3 thanh đứng và 6 ngôi sao. Dãy ∗ ∗ | ∗ | | ∗ ∗∗ biểu thị tổ hợp chứa đúng 2 phần tử thứ nhất, 1 phần tử thứ hai, không có phần tử thứ ba và 3 phần tử thứ tư của tập hợp. Như vậy, mỗi dãy n − 1 thanh đứng và k ngôi sao ứng với một tổ hợp lặp chập k của n phần tử. Vì mỗi dãy ứng với một cách chọn k vị trí cho k ngôi sao từ k n + k − 1 vị trí. Nên số các dãy như vậy là Cn+k−1 . k . Vậy số tổ hợp lặp chập k của tập n phần tử là Cn+k−1 Ví dụ 1.9. Một cửa hàng có 10 loại bánh khác nhau. Ngày Trung thu, cô giáo đi mua 30 chiếc bánh cho học sinh. Hỏi có bao nhiêu cách chọn mua 30 chiếc bánh đó. Lời giải. Mỗi cách chọn mua 30 chiếc bánh cho học sinh là một tổ hợp lặp 30 chập 30 của 10 phần tử. Khi đó, số cách mua 30 chiếc bánh đó là C30+10−1 = 30 C39 Ta có một số kết quả sau đây. Bổ đề 1.1. Số nghiệm nguyên không âm của phương trình x1 +x2 +· · ·+xk = n k−1 bằng Cn+k−1 . Chứng minh. Kí hiệu số nghiệm nguyên không âm của phương trình là Nk (n). Ta có N1 (n) = 1. Tính N2 (n), tức là tính số nghiệm nguyên không âm của phương trình x1 + x2 = n. Phương trình này có các nghiệm (0, n), (1, n − 1 . 1), . . . , (n, 0) nên N2 (n) = n + 1 = Cn+1 Để tính N3 (n) ta xét phương trình x1 +x2 +x3 = n. Cho x3 = 0, 1, 2, . . . , n, ta có 15 N3 (n) = N2 (n) + N2 (n − 1) + · · · + N2 (2) + N2 (1) + N2 (0) = (n + 1) + n + · · · + 2 +1 = (n + 1)(n + 2) 2 . = Cn+2 2 k−1 Ta chứng minh Nk (n) = Cn+k−1 bằng quy nạp. Ta có Nk (n) = Nk−1 (n) + Nk−1 (n − 1) + Nk−1 (n − 2) + · · · + Nk−1 (0) k−2 k−2 k−2 k−2 k−1 = Cn+k−2 + Cn+k−3 + Cn+k−4 + · · · + Ck−2 = Cn+k−1 . Hệ quả 1.2. Số nghiệm nguyên không âm của hệ bất phương trình dưới đây k−1 đúng bằng Cn−α 1 −α2 −···−αn +k−1   x 1 + x2 + · · · + x = n k  x1 ≥ α 1 , . . . , x ≥ α . k k Chứng minh. Đặt xi = yi + αi với i = 1, 2, . . . , k. Khi đó ta phải xác định nghiệm nguyên không âm của hệ bất phương trình   y1 + y2 + · · · + y = n − α1 − · · · − α k k  y1 ≥ 0, . . . , y ≥ 0. k k−1 Theo bổ đề 1.1, số nghiệm cần xác định đúng bằng Cn−α . 1 −α2 −···−αn +k−1 Nhận xét 1.1. Ta có thể sử dụng hệ phương trình nghiệm nguyên để chứng minh định lý 1.6: Giả sử ta lấy xi lần phần tử của tập A = {a1 , a2 , . . . , an }. Khi đó xi là số nguyên không âm. Mỗi tổ hợp lặp chập k của A tương ứng một một với một nghiệm nguyên không âm của phương trình x1 + x2 + · · · + xn = k . Theo bổ đề 1.1, số nghiệm nguyên không âm của phương trình này là n−1 k Cn+k−1 = Cn+k−1 . 1.5.2 Ứng dụng trong số học Bổ đề 1.2. Với số nguyên dương n, đặt f (x) = (1 + x)(2 + x) . . . (n + x). Giả sử f (x) = b0 + b1 x + b2 x2 + · · · + bn xn . Chứng minh rằng n−1−k n+1−k 2 bn−2 + · · · + Ck+2 bk+1 . (n − k)bk = Cn+1 bn + Cnn−k bn−1 + Cn−1 Chứng minh. Từ (1 + x)(2 + x) . . . (n + x) = b0 + b1 x + b2 x2 + · · · + bn xn ta suy ra (2 + x)(3 + x) . . . (n + 1 + x) = b0 + b1 (x + 1) + b2 (x + 1)2 + · · · + bn (x + 1)n . Ta có ngay bn = 1, bn−1 = 1 + 2 + 3 + · · · + n = 16 n(n + 1) và hệ thức (1 + x)(2 + 2 x) . . . (n + x)(n + 1 + x) = b0 (x + 1) + b1 (x + 1)2 + b2 (x + 1)3 + · · · + bn (x + 1)n+1 . Tức là (n + 1 + x)f (x) = (x + 1)f (x + 1). Suy ra (n+1+x)(b0 +b1 x+b2 x2 +· · ·+bn xn ) = b0 (x+1)+b1 (x+1)2 +b2 (x+1)3 +· · ·+bn (x+1)n+1 Như vậy:    bn = 1      2 b + C 1b 0  (n + 1)bn−1 + bn−2 = Cn+1 n n n−1 + Cn−1 bn−2      1 0 3 b + C 2b  (n + 1)bn−2 + bn−3 = Cn+1 n n n−1 + Cn−1 bn−2 + Cn−2 bn−3   ...    n−3 n−1   bn−2 + · · · + C31 b2 + C20 b1 (n + 1)b2 + b1 = Cn+1 bn + Cnn−2 bn−1 + Cn−1     n−2  n b + C n−1 b 1 0  (n + 1)b1 + b0 = Cn+1 n−1 + Cn−1 bn−2 + · · · + C2 b1 + C1 b0 n n      (n + 1)b0 = C n+1 bn + C n bn−1 + C n−1 bn−2 + · · · + C 2 b1 + C 1 b0 n 2 1 n+1 n−1   bn = 1      n(n + 1)   bn−1 =   2!    3 2    2bn−2 = Cn+1 + Cn bn−1 ...                 n−3 n−1 bn−2 + · · · + C42 b3 (n − 2)b2 = Cn+1 + Cnn−2 bn−1 + Cn−1 n−2 n (n − 1)b1 = Cn+1 + Cnn−1 bn−1 + Cn−1 bn−2 + · · · + C31 b2 n−1 n+1 nb0 = Cn+1 + Cnn bn−1 + Cn−1 bn−2 + · · · + C20 b1 n+1−k n−1−k 2 b Do vậy (n − k)bk = Cn+1 + Cnn−k bn−1 + Cn−1 bn−2 + · · · + Ck+2 k+1 . Hệ quả 1.3. [MO British 1974] Với số nguyên tố lẻ p, đặt f (x) = (1 + x)(2 + x) . . . (p − 1 + x). Giả sử f (x) = b0 + b1 x + b2 x2 + · · · + bp−1 xp−1 . Chứng minh rằng (i) p | bk với k = 1, 2, . . . , p − 2 và p |(b0 + 1). (ii) Với mọi số nguyên n ta có p | (n + 1)(n + 2) . . . (n + p − 1) − np−1 + 1. Từ đó suy ra p | (p − 1)! + 1 và p | np−1 − 1 khi (n, p) = 1. 17 Chứng minh:. (i) Qua các công thúc tính toán được ở trên ta có   bp−1 = 1      p(p − 1)   bp−2 =   2!   2b 3 = C + C2 b p−3 p−1 p−2 p   ···     p−2 p−3   (p − 2)b1 = Cpp−1 + Cp−1 bp−2 + Cp−2 bp−3 + · · · + C31 b2     (p − 1)b = C p + C p−1 b + C p−2 b + · · · + C 2b . 0 p p−1 p−2 p−2 p−3 2 1 Sử dụng quy nạp theo k có p | bk với k = 1, 2, . . . , p − 2. Từ hệ thức cuối cùng suy ra hệ thức pb0 = (b0 + 1) + bp−2 + bp−3 + · · · + b1 và như vậy b0 + 1 chia hết cho p. (ii) Vì p | bk với k = 1, 2, . . . , p − 2 và b0 + 1 chia hết cho p nên p | (n + 1)(n + 2) . . . (n + p − 1) − np−1 + 1 với mọi số nguyên n. Từ đó suy ra p | (p − 1)! + 1 và p | np−1 − 1 khi (n, p) = 1. Từ các kết quả trên ta suy ra các kết quả sau đây Định lý 1.7. Với số nguyên tố p và với mọi số tự nhiên n thỏa mãn (n, p) = 1, ta luôn có: (i) [Fermat] np−1 ≡ 1(modp). (ii) [Wilson] (p − 1)! + 1 ≡ 0(modp). (iii) Nếu số nguyên tố p có dạng 4k + 1 thì 1.6  p − 1
2 2 ! + 1 ≡ 0(modp). Nhị thức Newton Định lý 1.8. [Hằng đẳng thức Pascal] Cho n và k là các số nguyên dương với n ≥ k . Khi đó k (1.7) Cn+1 = Cnk−1 + Cnk . Chứng minh. Giả sử T là tập có n + 1 phần tử. Gọi a là một phần tử nào đó của T và S = T − {a}. k . Khi đó, các tập con này Ta có, số tập con có k phần tử của tập T là Cn+1 hoặc là chứa phần tử a cùng với k − 1 phần tử của S hoặc là chứa k phần tử của S và không chứa a. 18