Tài liệu Phương pháp xác suất trong toán trung học phổ thông

ĐẠI HỌC QUỐC GIA HÀ NỘI ĐẠI HỌC KHOA HOC TỰ NHIÊN ——————– NGUYỄN THỊ HỒNG PHƯƠNG PHÁP XÁC SUẤT TRONG TOÁN TRUNG HỌC PHỔ THÔNG LUẬN VĂN THẠC SĨ KHOA HỌC HÀ NỘI - 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI ĐẠI HỌC KHOA HOC TỰ NHIÊN ——————– NGUYỄN THỊ HỒNG PHƯƠNG PHÁP XÁC SUẤT TRONG TOÁN TRUNG HỌC PHỔ THÔNG Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60 46 01 13 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. LÊ ANH VINH HÀ NỘI - 2014 Mục lục Danh mục ký hiệu 1 Lời nói đầu 2 1 Phương pháp đếm 1.1 Hoán vị, chỉnh hợp, tổ hợp . . 1.1.1 Hoán vị . . . . . . . . . 1.1.2 Chỉnh hợp . . . . . . . 1.1.3 Tổ hợp . . . . . . . . . 1.2 Sự phân hoạch . . . . . . . . . 1.2.1 Sự phân hoạch một số nguyên không âm . . . 1.2.2 Phân hoạch tập hợp . 1.2.3 Phân hoạch số nguyên 1.3 Công thức Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . nguyên dương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . thành . . . . . . . . . . . . . . . . 2 Lý thuyết đồ thị cơ bản 2.1 Khái niệm cơ bản về đồ thị . . . . . . . . . . . 2.1.1 Định nghĩa đồ thị và phân loại đồ thị . 2.1.2 Đồ thị đẳng cấu . . . . . . . . . . . . . . 2.1.3 Biểu diễn đồ thị bằng ma trận . . . . . 2.1.4 Đồ thị con, đồ thị thành phần và đồ thị 2.2 Các yếu tố trong đồ thị vô hướng . . . . . . . . 2.2.1 Bậc của đỉnh trong đồ thị . . . . . . . . 2.2.2 Đường đi và chu trình . . . . . . . . . . 2.2.3 Tính liên thông . . . . . . . . . . . . . . 2.2.4 Một số loại đơn đồ thị vô hướng . . . . 2.3 Bài toán tô màu và các số Ramsey . . . . . . . i . . . . . . . . . . . . sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . tổng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . các số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 4 6 7 11 . . . . 11 12 14 18 . . . . . . . . . . . 26 26 26 27 28 29 30 30 30 31 31 39 MỤC LỤC 2.3.1 2.3.2 Lý thuyết Ramsey cho đồ thị hữu hạn . . . . . . . . . . . . 39 Lý thuyết Ramsey trong trường hợp tổng quát . . . . . . . 42 3 Xác suất và một số ứng dụng 3.1 Phép thử và biến cố . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Xác suất của biến cố . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Định nghĩa cổ điển của xác suất . . . . . . . . . . . . . . . 3.2.2 Định nghĩa thống kê về xác suất . . . . . . . . . . . . . . . 3.2.3 Định nghĩa hình học về xác suất . . . . . . . . . . . . . . . 3.3 Định lý cộng xác suất . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Định lý nhân xác suất . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Một số mở rộng của định lý cộng và định lý nhân xác suất . . . . 3.6 Biến ngẫu nhiên và kì vọng . . . . . . . . . . . . . . . . . . . . . . 3.6.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.2 Tính tuyến tính của kì vọng . . . . . . . . . . . . . . . . . . 3.7 Sử dụng xác suất chứng minh một số tính chất của các số Ramsey 3.8 Áp dụng xác suất và kì vọng vào một số bài toán thi học sinh giỏi 44 44 45 45 48 48 50 53 57 64 64 66 68 70 Kết luận 78 Tài liệu tham khảo 79 ii Danh mục ký hiệu |A| Số phần tử của A p(n) Số hoán vị của n phần tử phân biệt Cnk Số tổ hợp chập k của n phần tử Akn Số chỉnh hợp chập k của n phần tử S(n, k) Số cách phân hoạch tập n phần tử thành k phần B(n) Số cách phân hoạch tập n phần tử thành một số phần P (n) Số cách phân hoạch số n thành k phần D(n) Số xáo trộn của tập n phần tử P (A) Xác suất của biến cố A E(X) Kì vọng của biến ngẫu nhiên X 1 Lời nói đầu Xác suất là một phần mới đối với toán trung học phổ thông nói chung,Ứng dụng xác suất trong giải các bài toán Trung học phổ thông là nội dung còn khá mới mẻ, thú vị. Mặt khác xác suất không chỉ có ứng dụng trong toán học mà còn có nhiều ứng dụng trong một số môn học khác, trong ngành khoa học khác. Học và tìm hiểu về xác suất học sinh thấy toán học gần gũi, gắn liền với cuộc sống thực tế hơn, tạo hứng thú học tập cho học sinh. Bởi vậy tôi lựa chọn tìm hiểu “ Phương pháp xác suất trong toán trung học phổ thông” . Xác suất trong toán THPT với cơ sở chủ yếu là các bài toán đếm, với đối tượng học sinh khá giỏi, còn được tiếp cận với Lý thuyết đồ thị và các bài toán liên quan giữa lý thuyết đồ thị và tổ hợp xác suất. Với mục đích tìm hiểu về xác suất , cách tính xác suất, một số ứng dụng của xác suất trong các bài toán THPT. Nên trong Luận văn này, ngoài phần mở đầu và phần kết luận tôi trình bày ba chương Chương 1: Trình bày các quy tắc đếm cơ bản và mở rộng. Nhằm trang bị cho học sinh kiến thức cơ sở để sử dụng trong các bài toán đếm và bài toán xác suất. người học muốn học tốt xác suất cần phải có kiến thức tốt về tổ hợp đếm. Chương 2: Trình bày rất sơ lược về lý thuyết đồ thị, nhằm trang bị kiến thức cần thiết cho chương 3. Chương 3: Là chương trọng tâm, trong chương này tôi trình bày về khái niệm xác suất,tính chất, các quy tắc tính xác suất. Khái niệm về kỳ vọng, tính tuyến tính của kỳ vọng và áp dụng vào một số ví dụ.Trong chương này bước đầu tôi trình bày được cách sử dụng xác suất, kỳ vọng vào một số bài toán số học, tổ hợp, hình học tổ hợp. Luận văn này được hoàn thành với sự hướng dẫn tận tình của Thầy PGS.TS Lê Anh Vinh – Đại học Giáo Dục – Đại học Quốc gia Hà Nội. Từ đáy lòng mình em xin bày tỏ lòng biết ơn sâu sắc tới Thầy Lê Anh Vinh đối với sự quan 2 Lời nói đầu tâm, chỉ bảo tận tình của thầy. Em xin chân thành cảm ơn các thầy cô trong Trường Đại học Khoa học tự nhiên - Đại học Quốc gia Hà Nội, đã giúp đỡ em trong suốt quá trình theo học. Tôi cũng xin chân thành cảm ơn Ban Giám hiệu và các đồng nghiệp Trường THPT Nam Khoái Châu – Hưng Yên đã tạo điều kiện cho tôi hoàn thành kế hoạch học tập. Hà Nội, ngày 5 tháng 12 năm 2014 Tác giả Nguyễn Thị Hồng 3 Chương 1 Phương pháp đếm 1.1 Hoán vị, chỉnh hợp, tổ hợp Nội dung chính của chương 1 được tam khảo chủ yếu ở tài liệu số 8 của tác giả Miko’s Bo’na, “A walk through combinatorics – An introduction to enumeration anh graph theory”. Ngoài cơ sở lý thuyết chính trong tài liệu trên, hệ thống ví dụ minh họa được xây dựng trên cơ sở lý thuyết tương ứng. 1.1.1 Hoán vị Định nghĩa 1.1.1. Mỗi sự sắp xếp thứ tự của n đối tượng khác nhau thành hàng, mà mỗi đối tượng xuất hiện đúng một lần được gọi là một hoán vị của n đối tượng đó. Định lý 1.1.1. Số hoán vị của tập hợp A có n phần tử là p(n) = n!. Ví dụ 1.1.1. Một người trồng hoa có 5 cây hoa đỏ, 3 cây hoa vàng, 2 cây hoa trắng muốn trồng thành một hàng. Hỏi có bao nhiêu cách trồng? Lời giải. Ta xét hai trường hợp: • Trường hợp 1: Các cây hoa đôi một khác loại nhau. Khi đó số cách trồng là 10!. • Trường hợp 2: Các cây hoa cùng màu thuộc cùng một loại. Khi đó sự thay đổi vị trí của 5 cây hoa đỏ cho ta cùng một cách trồng, sự thay đổi vị trí của 3 cây hoa vàng cho ta cùng một cách trồng, sự thay đổi vị trí của 2 cây hoa trắng cho ta cùng một cách trồng. Nên số cách trồng 10 cây hoa đó là 10! . 5!2!3! 4 Chương 1. Phương pháp đếm Từ ví dụ trên ta thấy khi sắp xếp n đối tượng không đôi một phân biệt định lý 1.1.1 không còn đúng. Mở rộng định nghĩa hoán vị ta có định nghĩa hoán vị lặp như sau. Định nghĩa 1.1.2. Cho n, a1 , a2 , ..., ak là các số nguyên dương thỏa mãn a1 + a2 + ... + ak = n. Mỗi cách sắp xếp n đối tượng thành hàng trong đó có ai đối tượng loại i là một hoán vị lặp của n đối tượng đó. Khi đó ta có số hoán vị lặp được tính như sau. Định lý 1.1.2. Cho n, a1 , a2 , ..., ak là các số nguyên không âm thỏa mãn a1 + a2 + ... + ak = n, có ai đối tượng loại i, i = 1, k . Khi đó số hoán vị lặp của n đối tượng trên là n! . a1 !a2 !...ak ! (1.1) Ví dụ 1.1.2. Cho tập A = {1, 2, 3, 4, 5}. Có bao nhiêu số nguyên dương có 8 chữ số được lập từ A. Biết chữ số 2 xuất hiện 3 lần, chữ số 3 xuất hiện 2 lần. Lời giải. Ta coi mỗi số có 8 chữ số là một hoán vị lặp của 8 đối tượng, trong đó số 2 xuất hiện 3 lần, số 3 xuất hiện 2 lần, số các số thỏa mãn yêu cầu là: 40320 8! = = 3360 (số). 2!3! 2.6 Ví dụ 1.1.3. Cho 2n người, trong đó có n nam, n nữ. Hỏi a) Có bao nhiêu cách sắp xếp cho 2n người ngồi thành hàng sao cho nam nữ ngồi xen kẽ? b) Có bao nhiêu cách sắp xếp cho 2n người ngồi thành hàng sao cho nam ngồi liền nhau? c) Có bao nhiêu cách sắp xếp cho 2n người ngồi quanh một bàn tròn? d) Có bao nhiêu cách sắp xếp cho 2n người ngồi quanh một bàn tròn sao cho nam nữ ngồi xen kẽ? Lời giải. a) Ta xét hai trường hợp 5 Chương 1. Phương pháp đếm • Trường hợp 1: n nam ngồi ở các vị trí lẻ có n! cách. Với mỗi cách sắp xếp nam ta có n! cách sắp xếp n nữ vào các vị trí chẵn, nên ta có n!n! = (n!)2 cách sắp xếp nam vào vị trí lẻ, nữ vào vị trí chẵn. • Trường hơp 2: n nam ngồi vị trí chẵn, n nữ ngồi vị trí lẻ, vậy ta có (n!)2 cách sắp xếp. Vậy có 2(n!)2 cách sắp xếp nam nữ ngồi xen kẽ. b) Trước hết ta sắp xếp n nam vào n vị trí liền kề nhau trong 2n vị trí. Khi đó ta có n + 1 cách (tương ứng với người thứ 1 ngồi ở vị trí thứ 1 tới vị trí n + 1). Sau đó với mỗi cách chọn n vị trí liền kề đó có n! cách sắp xếp n nam. Với mỗi cách sắp xếp n nam lại có n! cách sắp xếp n nữ vào n chỗ còn lại nên có (n + 1)(n!)2 (cách). c) Ta cần chọn một người vào một vị trí bất kỳ trong bàn tròn để xác định số thứ tự của các chỗ ngồi, sau đó sắp xếp 2n − 1 người vào 2n − 1 vị trí có (2n − 1)! cách. Vậy số cách sắp xếp 2n người khác nhau vào 2n vị trí trong bàn tròn là (2n − 1)!. d) Lập luận tương tự ý a), ý c) ta có số cách sắp xếp là 2n!(n − 1)! cách. 1.1.2 Chỉnh hợp Định nghĩa 1.1.3. Cho tập hợp A có n phần tử n ∈ N∗ (phân biệt). Mỗi cách sắp thứ tự k (0 ≤ k ≤ n) phần tử của A sao cho không phần tử nào xuất hiện nhiều hơn một lần được gọi là chỉnh hợp chập k của n phần tử của A. Chú ý: Quy ước: 0! = 1. Định lý 1.1.3. Số chỉnh hợp chập k của n phần tử là Akn = n! . (n − k)! (1.2) Tương tự hoán vị lặp ta mở rộng định nghĩa chỉnh hợp lặp như sau. Định nghĩa 1.1.4. Cho tập hợp A có n (n ∈ N∗ ) phần tử phân biệt. Mỗi cách sắp thứ tự k phần tử của A, mà mỗi phần tử có thể xuất hiện nhiều hơn một 6 Chương 1. Phương pháp đếm lần được gọi là chỉnh hợp lặp chập k của n phần tử. (Nói cách khác mỗi chỉnh hợp lặp chập k của n phần tử là một hoán vị lặp của k phần tử), k ∈ N∗ , k có thể lớn hơn n. Định lý 1.1.4. Cho tập A có n, n ∈ N∗ phần tử (phân biệt) khi đó số chỉnh hợp lặp chập k phần tử của A là nk . Chứng minh. Với mỗi vị trí trong k vị trí sắp xếp có n cách để chọn một phần tử của A, khi đó k vị trí có n.n.n...n = nk cách chọn các phần tử của A vào k vị trí.  Ví dụ 1.1.4. Có bao nhiêu số tự nhiên có 7 chữ số đôi một khác nhau? Lời giải. • Xét tập A = {0, 1, 2, ..., 9}. Số các chỉnh hợp chập 7 của 10 phần tử của A là A710 . Số các chỉnh hợp chập 7 của 10 phần tử của A mà vị trí đầu bằng 0 là A69 . Nên số các số tự nhiên có 7 chữ số đôi một khác nhau là A710 − A610 = 604800 − 60480 = 544320. Ví dụ 1.1.5. Một người chơi trò đoán chữ. Có 18 ô chữ cần điền vào đó mỗi ô 1 chữ cái được lấy ra từ các chữ cái H, G, N, A, O, I, T ,C. Hỏi có bao nhiêu cách sắp xếp các chữ cái vào ô chữ cần tìm. Lời giải. Số cách sắp xếp các chữ cái trên vào 18 ô là số chỉnh hợp lặp chập 18 của 8 phần tử, nói cách khác mỗi vị trí có thể chọn một trong 8 chữ cái, nên có 188 cách sắp xếp các chữ vào 18 ô. 1.1.3 Tổ hợp Định nghĩa 1.1.5. Cho tập A có n, n ∈ N∗ phần tử mỗi tập con có k(k ∈ N, k ≤ n) phần tử của A được gọi là tổ hợp chập k của n phần tử. Định lý 1.1.5. Cho n, k là các số nguyên thỏa mãn n ∈ N∗ , k ∈ N, k ≤ n, số tổ hợp chập k của n phần tử là Cnk = n! . (n − k)!k! 7 (1.3) Chương 1. Phương pháp đếm Định lý 1.1.6. (Một số tính chất của tổ hợp) Cho n, k là các số nguyên thỏa mãn n ∈ N∗ , k ∈ N, k ≤ n. Khi đó 1)Cn0 = Cnn = 1; (1.4) 2)Cnk = Cnn−k ; (1.5) k+1 k 3)Cn−1 + Cn−1 = Cnk+1 . (1.6) Ví dụ 1.1.6. Cho tập A gồm n phần tử, hỏi a) Tập A có bao nhiêu tập con? b) Tập A có bao nhiêu tập con có số lẻ phần tử? Tập A có bao nhiêu tập con có số chẵn phần tử? Lời giải. a) Số tập con có k phần tử của A là Cnk , 0 ≤ k ≤ n. Số tập con của A là Cn0 + Cn1 + ... + Cnn = (1 + 1)n = 2n tập con. b) Ta xét hai trường hợp • Trường hợp 1: n là số chẵn, đặt n = 2k . Xét khai triển 2n−2 2n−1 2n 0 1 2 + C2n . 0 = (1 − 1)2n = C2n − C2n + C2n − ... + C2n − C2n 2n−1 0 2 2n 1 3 ⇔ C2n + C2n + ... + C2n = C2n + C2n + ... + C2n . (*) • Trường hợp 2: n là số lẻ, đặt n = 2k + 1. Xét khai triển 2k+1 0 1 2k 0 = (1 − 1)2k+1 = C2k+1 − C2k+1 + ... + C2k+1 − C2k+1 . 2k+1Ω 0 2 2k 1 3 tag∗∗ (1.7) ⇔ C2k+1 + C2k+1 + ... + C2k+1 = C2k+1 + C2k+1 + ... + C2k+1 Từ (*) và (**) ta suy ra số tập con có số lẻ phần tử bằng số tập con có số chẵn phần tử, theo câu a) tổng số tập con của A là 2n , suy ra số tập con có số lẻ phần tử bằng số tập con có số chẵn phần tử và bằng 2n−1 . 8 Chương 1. Phương pháp đếm Ví dụ 1.1.7. Có bao nhiêu cách chọn ra 11 sinh viên vào đội bóng đá, 5 sinh viên vào đội chơi cầu lông từ một lớp có 30 sinh viên nếu a) Không ai chơi được ở cả hai đội. b) Bất kỳ sinh viên nào cũng có thể chơi được ở cả hai đội. c) Nhiều nhất có một sinh viên có thể chơi cho cả hai đội. Lời giải. 11 cách chọn 11 sinh viên cho đội bóng đá. Sau đó, có C 5 cách chọn 5 a) Có C30 19 11 .C 5 (cách). sinh viên chơi cầu lông từ 19 sinh viên còn lại, nên có C30 19 11 cách chọn 11 sinh viên cho đội bóng đá. Để mỗi cầu thủ chơi cả bóng b) Có C30 5 cách chọn 5 sinh viên chơi cầu lông từ 11 sinh viên và cầu lông ta có C11 11 .C 5 (cách). của đội bóng. Nên có C30 11 c) Số cách chọn một người chơi được cả cầu lông và bóng đá là 30, tương tự ý a), b), số cách chọn sinh viên cho đội bóng đá và cầu lông sao cho có nhiều nhất một người chơi cho cả 2 đội là: 11 .C 5 + 30.C 10 .C 4 (cách). C30 9 29 19 Ví dụ 1.1.8. Một sinh viên y phải làm việc 5 ngày trong tháng 1 (có 31 ngày) với điều kiện không được làm việc liên tiếp 2 ngày trong bệnh viện. Có bao nhiêu cách chọn 5 ngày làm việc cho sinh viên này? Lời giải. Giả sử a1 , a2 , a3 , a4 , a5 (theo thứ tự tăng dần) là 5 ngày cần chọn. Khi đó 1 ≤ ai ≤ 31,i = 1, 5 và 1 ≤ a1 < a2 < a3 < a4 < a5 ≤ 31. Do sinh viên này không được làm việc 2 ngày liên tiếp nên ta chọn a1 , a2 , ..., a5 thỏa mãn 1 ≤ a1 < a2 − 1 < a3 − 2 < a4 − 3 < a5 − 4 ≤ 27. Hay chọn b1 , b2 , b3 , b4 , b5 thỏa mãn 1 ≤ b1 < b2 < b3 < b4 < b5 ≤ 27, 1 ≤ bi ≤ 27, i = 1, 5. 5 (cách). Tức là ta chọn ra 5 phần tử trong 27 phần tử, nên số cách chọn là C27 Ví dụ 1.1.9. Một sinh viên vật lý cần làm việc 5 ngày trong phòng thí nghiệm trong học kỳ cuối (có 105 ngày). Sau mỗi ngày trong phòng thí nghiệm sinh viên này cần ít nhất 6 ngày để xử lí số liệu. Sau lần cuối khi làm việc ở phòng thí nghiệm, sinh viên này cần 10 ngày để hoàn thành báo cáo, báo cáo phải được 9 Chương 1. Phương pháp đếm hoàn thành và nộp vào ngày cuối cùng của kì học. Có bao nhiêu cách chọn lịch làm việc cho sinh viên này. Lời giải. Giả sử a1 , a2 , a3 , a4 , a5 (theo thứ tự tăng dần) là 5 ngày làm việc của sinh viên trong phòng thí nghiệm, khi đó 1 ≤ ai ≤ 105, i = 1, 5. Ta cần chọn 5 ngày thỏa mãn: 1 ≤ a1 < a2 < a3 < a4 < a5 ≤ 105. Mặt khác, sau mỗi ngày làm việc sinh viên cần ít nhất 6 ngày xử lý số liệu nên các ngày phải thỏa mãn 1 ≤ a1 < a2 − 6 < a3 − 12 < a4 − 18 < a5 − 24 ≤ 105 − 24. Sau ngày cuối cùng sinh viên cần 10 ngày để hoàn thành và nộp báo cáo nên ta chọn 5 số b1 , b2 , b3 , b4 , b5 thỏa mãn 1 ≤ b1 < b2 < b3 < b4 < b5 ≤ 71. 5 (cách). Để chọn 5 phần tử từ 71 phần tử có C71 5 cách chọn 5 ngày làm việc cho sinh viên này. Vậy có C71 Khái quát hóa từ hai ví dụ trên ta có. Định lý 1.1.7. Cho tập A có n phần tử, các phần tử được sắp thứ tự từ 1 tới k . n, số chuỗi có k phần tử được sắp thứ tự của A là Cn+k−1 Chứng minh. Giả sử a1 , a2 , ..., ak là chuỗi cần tìm. Khi đó, a1 , a2 , ..., ak thỏa mãn 1 ≤ a1 ≤ a2 ≤ ... ≤ ak ≤ n ⇔ 1 ≤ a1 < a2 + 1 < a3 + 2 < ... < ak + k − 1 ≤ n + k − 1. Đặt: b1 = a1 , bi = ai + i − 1, i = 2, k. Ta chọn b1 , b2 , ..., bk thỏa mãn 1 ≤ b1 < b2 < ... < bk ≤ n + k − 1. k Vậy có Cn+k−1 cách chọn dãy bi , i = 1, k .  Ví dụ 1.1.10. Có bao nhiêu số tự nhiên có 4 chữ số, mỗi chữ số đứng sau lớn hơn hoặc bằng chữ số đứng trước. 10 Chương 1. Phương pháp đếm Lời giải. Giả sử số cần tìm là a1 a2 a3 a4 , khi đó các số ai , i = 1, 4 thỏa mãn. 1 ≤ a1 ≤ a2 ≤ a3 ≤ a4 ≤ 9 ⇔ 1 ≤ a1 < a2 + 1 < a3 + 2 < a4 + 3 ≤ 12 ⇔ 1 ≤ b1 < b2 < b3 < b4 ≤ 12, bi = ai + i − 1, i = 1, 4. 4 cách chọn b b b b tức là có C 4 số có 4 chữ số sao cho chữ số đứng Khi đó có C12 1 2 3 4 12 sau lớn hơn hoặc bằng chữ số đứng trước. 1.2 Sự phân hoạch Xét bài toán tổ hợp rất phổ biến "có bao nhiêu cách sắp xếp n quả bóng vào k chiếc hộp?" Để giải quyết bài toán này ta phải xét đầy đủ tất cả các trường hợp: Các quả bóng là giống nhau hay khác nhau, các chiếc hộp giống nhau hay khác nhau? Ta sẽ xem xét tất cả các trường hợp ở các phần dưới đây. 1.2.1 Sự phân hoạch một số nguyên dương thành tổng các số nguyên không âm Khi chia n quả bóng giống nhau vào k hộp khác nhau, thực chất ta thực hiện tách số nguyên dương n thành tổng của k số nguyên không âm thỏa mãn n = n1 + n2 + ... + nk với nk là số quả bóng ở hộp thứ k nào đó. Định nghĩa 1.2.1. Mỗi dãy a1 , a2 , ..., ak là các số nguyên không âm thỏa mãn a1 + a2 + ... + ak = n được gọi là một phân hoạch yếu của n thành k phần. Nếu ai > 0, i = 1, k thì a1 , a2 , ..., ak là một phân hoạch của n thành k phần. Định lý 1.2.1. Với ∀n ∈ N∗ , k ∈ N, k ≤ n. Số cách phân hoạch yếu n thành k k−1 . phần là Cn+k−1 Chứng minh. Giả sử ta cần bỏ n quả bóng giống nhau vào k hộp khác nhau. Để thực hiện việc này ta xếp n quả bóng thành hàng sau đó đặt k − 1 vách ngăn vào dãy các quả bóng vừa xếp để chia các quả bóng vào k hộp. Khi đó tổng các quả bóng và vách ngăn là n + k − 1. Mà ta cần chọn k − 1 vị trí cho k − 1 k−1 . Tức số cách phân tích n thành tổng k số vách ngăn nên số cách chọn là Cn+k−1 k−1 nguyên không âm là Cn+k−1 .  11 Chương 1. Phương pháp đếm Định lý 1.2.2. Với mọi k, n ∈ N∗ , k ≤ n, số các phân hoạch n thành k phần k−1 khác rỗng là Cn−1 . Chứng minh. Tương tự định lý 1.2.1 ta sắp n quả bóng thành hàng để đảm bảo không có hộp nào không có bóng, ta cần đặt k − 1 vách ngăn vào n − 1 vị k−1 k−1 trí giữa các quả bóng, sẽ có Cn−1 cách đặt. Tức là có Cn−1 cách phân hoạch số nguyên dương n thành tổng của k phần.  Hệ quả 1.2.1. ∀n ∈ N∗ , k ∈ N∗ , k ≤ n, số cách phân hoạch n thành k phần, mỗi phần ít nhất là 1 là 2n−1 . k−1 Chứng minh. Số cách phân tích n thành k phần, mỗi phần ít nhất là 1 là Cn−1 , k = 1, n, khi đó ta có số cách phân tích số nguyên dương n thành một số phần, mỗi phần ít nhất là 1 là n−1 0 1 Cn−1 + Cn−1 + ... + Cn−1 = 2n−1 .  Ví dụ 1.2.1. Trong một hộp có 40 cái kẹo như nhau, hỏi có bao nhiêu cách chia hộp kẹo cho k người nếu mỗi người có ít nhất một cái kẹo? a) k = 4. b) k tùy ý thỏa mãn k ≤ 40. Lời giải. 3 cách. a) Theo định lí 1.2.2 ta có số cách chia là C39 b) Theo hệ quả 1.2.1 ta có số cách chia là 239 cách. 1.2.2 Phân hoạch tập hợp Tiếp theo ta xét trường hợp n quả bóng khác nhau, k hộp giống nhau. Đây chính là bài toán phân chia tập có n phần tử thành k tập con. Định nghĩa 1.2.2. Số cách phân chia tập hợp có n phần tử thành k tập con khác ∅ được ký hiệu là S(n, k), số S(n, k) là số Stirling loại 2. Từ định nghĩa ta thấy nếu k > n thì S(n, k) = 0. Ta quy ước: S(0, 0) = 1. Ví dụ 1.2.2. Ta có S(4, 2) = 7. 12 Chương 1. Phương pháp đếm Lời giải. Thật vậy số cách chia tập A = {a1 , a2 , a3 , a4 } thành hai tập con khác ∅. Bao gồm chia thành + {a1 } và {a2 , a3 , a4 }; + {a2 } và {a1 , a3 , a4 }; + {a3 } và {a1 , a2 , a4 }; + {a4 } và {a1 , a2 , a3 }; + {a1 , a2 } và {a3 , a4 }; + {a1 , a3 } và {a2 , a4 }; + {a1 , a4 } và {a2 , a3 }. Ví dụ 1.2.3. Với ∀n ≥ 1 ta có S(n, 1) = S(n, n) = 1. Với ∀n ≥ 2 ta có S(n, n − 1) = Cn2 . Ở phần này ta chưa có một công thức cụ thể cho các số S(n, k), ta sẽ chứng minh ở phần sau. Tuy nhiên ta chứng minh được một số tính chất sau của các số S(n, k). Định lý 1.2.3. Cho n, k ∈ N∗ , k ≤ n. Khi đó S(n, k) = S(n − 1, k − 1) + k.S(n − 1, k). (1.8) Chứng minh. Giả sử ta đã thực hiện phân chia n − 1 quả bóng khác nhau vào k hộp giống nhau. Ta xét quả bóng thứ n, nếu quả bóng thứ n ở một hộp không có quả bóng nào, khi đó n − 1 quả trước đó được phân vào k − 1 hộp, mỗi hộp có ít nhất một quả nên số cách là S(n − 1, k − 1). Nếu quả bóng thứ n được cho vào một hộp đã có bóng, khi đó có k cách chọn hộp cho quả bóng thứ n, đồng thời đã có S(n − 1, k) cách chia n − 1 quả bóng trước đó vào k hộp. Vậy ta có: S(n, k) = S(n − 1, k − 1) + k.S(n − 1, k).  Nhận xét 1.2.1. Nếu n quả bóng khác nhau, k hộp khác nhau thì có k!S(n, k) cách phân chia n quả bóng vào k hộp. Định nghĩa 1.2.3. Số cách phân chia tập A có n phần tử thành k phần khác ∅, k = 0, n là B(n). Số B(n) được gọi là số Bell. n P Quy ước: B(0) = 1, B(n) = S(n, i). i=1 13 Chương 1. Phương pháp đếm Định lý 1.2.4. Với mọi số nguyên không âm n ta có B(n + 1) = n X Cni B(i). (1.9) i=1 Chứng minh. Ta có vế trái B(n + 1) là số các cách phân chia n + 1 phần tử phân biệt thành k phần khác ∅, k ≤ n + 1. Bây giờ ta xét riêng phần tử thứ n + 1, giả sử phần tử thứ n + 1 được chia vào một hộp có n − i + 1 phần tử. Khi đó có Cnn−i cách chọn n − i phần tử ở cùng hộp với phần tử n + 1, mà Cnn−i = Cni . Với mỗi cách chọn n − i + 1 phần tử đó có B(i) cách phân i phần tử còn lại vào một số hộp nên số cách phân chia n phần tử thành một số phần là n X Cni B(i) = B(n + i). i=1  Ví dụ 1.2.4. Một cơ quan có 10 người được cử đi công tác ở ba địa điểm khác nhau. Biết vai trò của mỗi người là như nhau hỏi có bao nhiêu cách cử ba đoàn công tác biết mỗi đoàn phải có ít nhất một người. Lời giải. Số cách chia 10 người thành ba nhóm mỗi nhóm ít nhất một người là S(10, 3). Do ba địa điểm công tác khác nhau nên số cách để phân công ba đoàn công tác là 3!S(10, 3). 1.2.3 Phân hoạch số nguyên Cuối cùng ta xét trường hợp n quả bóng giống nhau, k hộp giống nhau. Khi đó chỉ có một vấn đề là số lượng của các quả bóng bỏ vào hộp. Có nghĩa ta chỉ cần quan tâm đến việc phân tích một số nguyên dương thành tổng các số nguyên dương mà không cần quan tâm đến thứ tự của chúng. Bởi vậy, không mất tính tổng quát ta có thể giả sử các số hạng giảm dần hoặc tăng dần. Định nghĩa 1.2.4. Cho a1 ≥ a2 ≥ ... ≥ ak ≥ 1 là các số nguyên thỏa mãn: a1 + a2 + ... + an = n. Khi đó dãy (a1 , a2 , ..., ak ) là một phân hoạch của số nguyên n. Số phân hoạch của số nguyên n được kí hiệu là p(n). 14 Chương 1. Phương pháp đếm Ví dụ 1.2.5. Số 5 có 7 phân hoạch là: (5); (4, 1); (3, 2); (3, 1, 1); (2, 2, 1); (2, 1, 1, 1); (1, 1, 1, 1, 1), tức là p(5) = 7. Ta đi tìm hiểu một số tính chất của p(n) thông qua biểu diễn Ferrers của mỗi phân hoạch. Với mỗi phân hoạch của n = (a1 , a2 , ...ak ) ta có thể biểu diễn bằng tập n ô vuông bằng nhau như sau Ở dòng thứ i ta vẽ ai ô vuông, sao cho các ô vuông ở vị trí thứ 1 của dòng thẳng cột với nhau. Khi đó trong biểu diễn n = (a1 , a2 , ...ak ) có k dòng, dòng thứ k có ak ô vuông, với mỗi phân hoạch có duy nhất 1 biểu diễn của nó. Ví dụ 1.2.6. 7 có 1 phân hoạch (4,2,1) có biểu diễn Ferrers hình 1.1 Hình 1.1: Số 7 có một phân hoạch. Định nghĩa 1.2.5. Một biểu diễn Ferrers của phân hoạch p của n, khi ta lấy đối xứng qua đường chéo chính ta được một biểu diễn Ferrers của một phân hoạch q của n. Khi đó p và q là hai phân hoạch liên hợp. Nhận xét 1.2.2. Đường chéo chính ở đây là đường thẳng chứa đường chéo của các hình vuông ở hàng i và cột i. Định nghĩa 1.2.6. Một phân hoạch được gọi là tự liên hợp nếu phân hoạch liên hợp của nó là chính nó. Ví dụ 1.2.7. Hai phân hoạch (4, 2, 1) và (3, 2, 1, 1) là hai phân hoạch liên hợp của nhau (xem hình 1.2). 15 Chương 1. Phương pháp đếm Hình 1.2: Phân hoạch liên hợp. Các phân hoạch (4, 3, 2, 1), (5, 1, 1, 1) và (4, 2, 1, 1) là các phân hoạch tự liên hợp (xem hình 1.3). Hình 1.3: Các phân hoạch tự liên hợp. Định lý 1.2.5. Số phân hoạch của n thành nhiều nhất k phần bằng với số cách phân hoạch của n thành một số phần mà mỗi phần không quá k . Chứng minh. Trong biểu diễn của một phân hoạch p của n có nhiều nhất k phần thì số hàng không quá k . Trong biểu diễn một phân hoạch q của n mà mỗi phần không quá k thì số cột không quá k . Ta thiết lập một song ánh từ tập P các phân hoạch của n có nhiều nhất k phần, tới tập Q các phân hoạch của n mà mỗi phần không quá k . Cho tương ứng với mỗi p ∈ P với phân hoạch liên hợp q của p, q ∈ Q. Khi đó ta có số phần tử của P và Q bằng nhau. 16