Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản
Nguyên lý cộng
Giả sử ta phải thực hiện một công việc bằng cách chọn một trong k sự chọn lựa các phương pháp khác nhau T1, T2, ., Tk. Để thực hiện Ti (1 ≤ i ≤ k) ta có ni cách. Vậy ta số cách thực hiện công việc trên là
n1 + n2 + · · · + nk.
Ví dụ. Một sinh viên có thể chọn một đề tài từ một trong 3 danh sách các đề tài. Số đề tài trong các danh sách đề tài lần lượt là 23, 15, 19.
Hỏi sinh viên có bao nhiêu cách chọn một đề tài?
Đáp án. 23 + 15 + 19 = 57 cách.
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 1 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 1](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-1_7RJA8AaqH3.jpg)
Trang 1
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 2 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 2](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-2_aJduAeQbg9.jpg)
Trang 2
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 3 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 3](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-3_PsnNlRfM7H.jpg)
Trang 3
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 4 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 4](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-4_ZqvLjMYFEx.jpg)
Trang 4
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 5 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 5](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-5_xen4eIV2Vs.jpg)
Trang 5
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 6 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 6](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-6_m7ool1tZLd.jpg)
Trang 6
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 7 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 7](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-7_wIIk5cCtbE.jpg)
Trang 7
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 8 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 8](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-8_MxYPFgYxzU.jpg)
Trang 8
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 9 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 9](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-9_m0VfmQNp9X.jpg)
Trang 9
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 10 Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản trang 10](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5665/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban-trang-10_0hYI8TABHd.jpg)
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản
![Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản](https://s1.ebooks.com.vn/yetwygzggocsqsc5/thumb/2024/01/13/bai-giang-toan-to-hop-chuong-1-to-hop-co-ban_Bn5MhwDOPE.jpg)
Bài giảng Toán tổ hợp Đại học Khoa học Tự nhiên, Tp HCM 2017 Bài giảng Toán tổ hợp 2017 1/40 Nội dung chương 1 Nội dung Chương 1. Tổ hợp cơ bản 1. Nguyên lý đếm cơ bản 2. Tổ hợp 3. Tổ hợp lặp 4. Khai triển lũy thừa của đa thức Bài giảng Toán tổ hợp 2017 2/40 Các nguyên lý đếm cơ bản Nội dung Các nguyên lý đếm cơ bản 1 Nguyên lý cộng 2 Nguyên lý nhân 3 Nguyên lý Derichlet Bài giảng Toán tổ hợp 2017 3/40 Các nguyên lý đếm cơ bản Nguyên lý cộng Nguyên lý cộng Giả sử ta phải thực hiện một công việc bằng cách chọn một trong k sự chọn lựa các phương pháp khác nhau T1, T2, ..., Tk. Để thực hiện Ti (1 ≤ i ≤ k) ta có ni cách. Vậy ta số cách thực hiện công việc trên là n1+ n2+ · · ·+ nk. Ví dụ. Một sinh viên có thể chọn một đề tài từ một trong 3 danh sách các đề tài. Số đề tài trong các danh sách đề tài lần lượt là 23, 15, 19. Hỏi sinh viên có bao nhiêu cách chọn một đề tài? Đáp án. 23 + 15 + 19 = 57 cách. Nhận xét. Quy tắc cộng có thể phát biểu dưới dạng của ngôn ngữ tập hợp: Nếu A1, A2, . . . , Ak là các tập hợp đôi một rời nhau, khi đó |A1 ∪A2 ∪ . . .∪Ak| = |A1|+ |A2|+ . . .+ |Ak|. Bài giảng Toán tổ hợp 2017 4/40 Các nguyên lý đếm cơ bản Nguyên lý nhân Nguyên lý nhân Giả sử một thủ tục bao gồm k công việc kế tiếp nhau T1, T2, . . . , Tk. Nếu công việc T1 có thể được thực hiện theo n1 cách, và sau khi chọn cách thực hiện cho T1 ta có n2 cách thực hiện T2, v.v. . . cho đến cuối cùng, sau khi chọn cách thực hiện các công việc T1, T2, ..., Tk−1 ta có nk cách thực hiện Tk. Vậy ta có cách để thực hiện thủ tục này là: n1× n2× ...× nk Ví dụ. Hỏi có nhiêu cách đi từ A đến C? Đáp án. 3× 2 = 6 cách. Bài giảng Toán tổ hợp 2017 5/40 Các nguyên lý đếm cơ bản Nguyên lý nhân Nguyên lý nhân Nhận xét. Quy tắc nhân có thể phát biểu dưới dạng của ngôn ngữ tập hợp: Nếu A1, A2, . . . , Ak là các tập hữu hạn, khi đó |A1×A2× . . .×Ak| = |A1| × |A2| × . . .× |Ak|. Ví dụ. Có bao nhiêu chuỗi bit có độ dài 8? Giải. Mỗi bit có thể chọn 1 trong 2 cách: 0 hoặc 1. Theo nguyên lý nhân ta có số lượng chuỗi là 28 = 256. Ví dụ. Cho tập A gồm 6 phần tử và tập B gồm 10 phần tử. Hỏi a) Có bao nhiêu ánh xạ từ A vào B? b) Có bao nhiêu đơn ánh từ A vào B? Bài giảng Toán tổ hợp 2017 6/40 Các nguyên lý đếm cơ bản Nguyên lý nhân Nguyên lý nhân Giải. a) Với mỗi phần tử x của A ta có 10 cách chọn ảnh của x (vì B có 10 phần tử). Theo nguyên lý nhân, ta có 106 ánh xạ. b) Giải sử A = {x1, x2, . . . , x6}. Ta chia bài toán thành 6 bước: Bước 1. Chọn ảnh của x1 có 10 cách. Bước 2. Chọn ảnh của x2 có 10− 1 = 9 cách. ................ Bước 6. Chọn ảnh của x6 có 10− 5 = 5 cách. Vậy số đơn ánh là: 10× 9× 8× 7× 6× 5 = 151200. Bài giảng Toán tổ hợp 2017 7/40 Các nguyên lý đếm cơ bản Nguyên lý Derichlet Nguyên lý Derichlet (chuồng bồ câu) Ví dụ. Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày. Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên. Định nghĩa. Giá trị trần của x, ký hiệu là dxe, là số nguyên nhỏ nhất mà lớn hơn hay bằng x. Ví dụ. d2.1e = 3; d1.9e = 2; d4e = 4; d−1.1e = −1. d−2.9e = −2; d−4e = −4. Nguyên lý Derichlet Nếu có n đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất ⌈n k ⌉ đồ vật. Bài giảng Toán tổ hợp 2017 8/40 Các nguyên lý đếm cơ bản Nguyên lý Derichlet Chứng minh. Giả sử mọi hộp đều chứa ít hơn ⌈n k ⌉ vật. Khi đó tổng số đồ vật nhỏ hơn hoặc bằng k (⌈n k ⌉ − 1 ) < k (n k ) = n. Điều này mâu thuẩn với giả thiết là có n đồ vật cần xếp. Ví dụ. Trong 100 người thì có ít nhất ⌈ 100 12 ⌉ = 9 cùng tháng sinh. Ví dụ. Trong một lớp học phải có ít nhất bao nhiêu học sinh để cho có ít nhất 6 học sinh có cùng thứ bậc học tập, biết rằng có 5 loại thứ bậc A,B,C,D và E? Giải. Gọi số học sinh của lớp là N . Theo nguyên lý Derichlet ta có dN5 e = 6. Khi đó 25 < N ≤ 30. Do đó ta có thể chọn N = 26. Vậy lớp phải có ít nhất 26 học sinh. Bài giảng Toán tổ hợp 2017 9/40 Các nguyên lý đếm cơ bản Nguyên lý Derichlet Ví dụ. Chứng minh rằng trong 10 số tự nhiên bất kỳ có thể chọn hai số có hiệu chia hết cho 9. Giải. Khi chia 10 số bất kỳ cho 9 ta sẽ có mỗi số có một số dư trong 9 số dư: 0, 1, 2, . . . , 7, 8. Do đó theo nguyên lý Dirichlet phải tồn tại ít nhất hai số có cùng số dư. Hiệu của hai số đó sẽ chia hết cho 9. Ví dụ. Cho tập X = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ chứa hai phần tử có tổng bằng 10. Giải. Ta lập các hộp như sau: {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. Do A có 6 phần tử nên khi sắp xếp 6 phần tử đó sẽ có hộp có 2 phần tử. Rõ ràng tổng 2 phần tử này bằng 10. Bài giảng Toán tổ hợp 2017 10/40 Tổ hợp Nội dung Tổ hợp 1 Hoán vị 2 Chỉnh hợp 3 Tổ hợp Bài giảng Toán tổ hợp 2017 11/40 Tổ hợp Hoán vị Hoán vị Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Ví dụ. Cho A = {1, 2, 3}. Khi đó A có các hoán vị sau: 123, 132, 2 ... abcdefgh gồm 8 chữ số hệ thập phân a, b, c, d, e, f, g, h thỏa các điều kiện a lẻ, b = 4, g > 6, h chia hết cho 3 và c, d, e, f tùy ý ? Đáp án. 5× 1× 104 × 3× 4. Bài giảng Toán tổ hợp 2017 19/40 Tổ hợp Tổ hợp Ví dụ. Từ 9 sinh viên nam và 8 sinh viên nữ, ta muốn chọn ra một đội gồm 10 người sao cho trong đội đó có ít nhất 4 nam và 4 nữ. Hỏi có bao nhiêu cách chọn? Đáp án. C49 × C68 + C59 × C58 + C69 × C48 Ví dụ. Có bao nhiêu cách sắp 7 nam và 6 nữ thành 1 hàng dọc mà nam và nữ đứng xen kẽ ? Có bao nhiêu cách sắp 6 nam và 6 nữ thành 1 hàng dọc mà nam và nữ đứng xen kẽ ? Có bao nhiêu cách sắp 6 nam và 6 nữ thành 1 hàng dọc mà 6 nam đứng gần nhau ? Có bao nhiêu cách sắp 7 nam và 6 nữ thành 1 hàng dọc mà 7 nam đứng gần nhau và 6 nữ đứng gần nhau ? Đáp án. 7!× 6! 6!× 6! + 6!× 6! 6!× 7× 6! 2!× 7!× 6! Bài giảng Toán tổ hợp 2017 20/40 Tổ hợp Tổ hợp Ví dụ. Từ 9 sinh viên nam và 8 sinh viên nữ, ta muốn chọn ra một đội gồm 10 người sao cho trong đội đó có ít nhất 4 nam và 4 nữ. Hỏi có bao nhiêu cách chọn? Đáp án. C49 × C68 + C59 × C58 + C69 × C48 Ví dụ. Có bao nhiêu cách sắp 7 nam và 6 nữ thành 1 hàng dọc mà nam và nữ đứng xen kẽ ? Có bao nhiêu cách sắp 6 nam và 6 nữ thành 1 hàng dọc mà nam và nữ đứng xen kẽ ? Có bao nhiêu cách sắp 6 nam và 6 nữ thành 1 hàng dọc mà 6 nam đứng gần nhau ? Có bao nhiêu cách sắp 7 nam và 6 nữ thành 1 hàng dọc mà 7 nam đứng gần nhau và 6 nữ đứng gần nhau ? Đáp án. 7!× 6! 6!× 6! + 6!× 6! 6!× 7× 6! 2!× 7!× 6! Bài giảng Toán tổ hợp 2017 20/40 Tổ hợp Tổ hợp Ví dụ. Từ 9 sinh viên nam và 8 sinh viên nữ, ta muốn chọn ra một đội gồm 10 người sao cho trong đội đó có ít nhất 4 nam và 4 nữ. Hỏi có bao nhiêu cách chọn? Đáp án. C49 × C68 + C59 × C58 + C69 × C48 Ví dụ. Có bao nhiêu cách sắp 7 nam và 6 nữ thành 1 hàng dọc mà nam và nữ đứng xen kẽ ? Có bao nhiêu cách sắp 6 nam và 6 nữ thành 1 hàng dọc mà nam và nữ đứng xen kẽ ? Có bao nhiêu cách sắp 6 nam và 6 nữ thành 1 hàng dọc mà 6 nam đứng gần nhau ? Có bao nhiêu cách sắp 7 nam và 6 nữ thành 1 hàng dọc mà 7 nam đứng gần nhau và 6 nữ đứng gần nhau ? Đáp án. 7!× 6! 6!× 6! + 6!× 6! 6!× 7× 6! 2!× 7!× 6! Bài giảng Toán tổ hợp 2017 20/40 Tổ hợp Tổ hợp Ví dụ. Cho S = {1, 2, . . . , 9, 10}. a) Có bao nhiêu tập hợp con ? b) Có bao nhiêu tập hợp con mà mỗi tập có đúng 5 phần tử ? c) Có bao nhiêu tập hợp con mà mỗi tập có không quá 4 phần tử ? Đáp án. a) 210 b) C510 c) C 0 10 + C 1 10 + C 2 10 + C 3 10 + C 4 10 Ví dụ. Từ 9 nam và 11 nữ, ta muốn chọn ra một đội văn nghệ gồm 10 người sao cho số nam và số nữ trong đội chênh lệch nhau không quá 2. Hỏi có tất cả bao nhiêu cách chọn đội? Đáp án. C49 × C611 + C59 × C511 + C69 × C411 Bài giảng Toán tổ hợp 2017 21/40 Tổ hợp Tổ hợp Ví dụ. Cho S = {1, 2, . . . , 9, 10}. a) Có bao nhiêu tập hợp con ? b) Có bao nhiêu tập hợp con mà mỗi tập có đúng 5 phần tử ? c) Có bao nhiêu tập hợp con mà mỗi tập có không quá 4 phần tử ? Đáp án. a) 210 b) C510 c) C 0 10 + C 1 10 + C 2 10 + C 3 10 + C 4 10 Ví dụ. Từ 9 nam và 11 nữ, ta muốn chọn ra một đội văn nghệ gồm 10 người sao cho số nam và số nữ trong đội chênh lệch nhau không quá 2. Hỏi có tất cả bao nhiêu cách chọn đội? Đáp án. C49 × C611 + C59 × C511 + C69 × C411 Bài giảng Toán tổ hợp 2017 21/40 Tổ hợp Tổ hợp Ví dụ. Cho S = {1, 2, . . . , 9, 10}. a) Có bao nhiêu tập hợp con ? b) Có bao nhiêu tập hợp con mà mỗi tập có đúng 5 phần tử ? c) Có bao nhiêu tập hợp con mà mỗi tập có không quá 4 phần tử ? Đáp án. a) 210 b) C510 c) C 0 10 + C 1 10 + C 2 10 + C 3 10 + C 4 10 Ví dụ. Từ 9 nam và 11 nữ, ta muốn chọn ra một đội văn nghệ gồm 10 người sao cho số nam và số nữ trong đội chênh lệch nhau không quá 2. Hỏi có tất cả bao nhiêu cách chọn đội? Đáp án. C49 × C611 + C59 × C511 + C69 × C411 Bài giảng Toán tổ hợp 2017 21/40 Tổ hợp Tổ hợp Ví dụ. Từ các chữ số 1, 2, 3, 4, 5, 6, 7 và 8, ta có thể tạo ra - Bao nhiêu số tự nhiên có 4 chữ số khác nhau? - Bao nhiêu số tự nhiên có 3 chữ số khác nhau trong đó có chữ số 5? Đáp án. A48 A 3 8 −A37 Ví dụ. Có 3 luật sư, 4 bác sĩ và 5 kỹ sư xếp thành một hàng dọc sao cho các đồng nghiệp phải đứng cạnh nhau. Hỏi có tất cả bao nhiêu cách xếp? Nếu yêu cầu thêm các luật sư không đứng ở đầu hàng thì có tất cả bao nhiêu cách xếp ? Đáp án. 3!× 3!× 4!× 5! 2× 2!× 3!× 4!× 5! Bài giảng Toán tổ hợp 2017 22/40 Tổ hợp Tổ hợp Ví dụ. Từ các chữ số 1, 2, 3, 4, 5, 6, 7 và 8, ta có thể tạo ra - Bao nhiêu số tự nhiên có 4 chữ số khác nhau? - Bao nhiêu số tự nhiên có 3 chữ số khác nhau trong đó có chữ số 5? Đáp án. A48 A 3 8 −A37 Ví dụ. Có 3 luật sư, 4 bác sĩ và 5 kỹ sư xếp thành một hàng dọc sao cho các đồng nghiệp phải đứng cạnh nhau. Hỏi có tất cả bao nhiêu cách xếp? Nếu yêu cầu thêm các luật sư không đứng ở đầu hàng thì có tất cả bao nhiêu cách xếp ? Đáp án. 3!× 3!× 4!× 5! 2× 2!× 3!× 4!× 5! Bài giảng Toán tổ hợp 2017 22/40 Tổ hợp Tổ hợp Ví dụ. Từ các chữ số 1, 2, 3, 4, 5, 6, 7 và 8, ta có thể tạo ra - Bao nhiêu số tự nhiên có 4 chữ số khác nhau? - Bao nhiêu số tự nhiên có 3 chữ số khác nhau trong đó có chữ số 5? Đáp án. A48 A 3 8 −A37 Ví dụ. Có 3 luật sư, 4 bác sĩ và 5 kỹ sư xếp thành một hàng dọc sao cho các đồng nghiệp phải đứng cạnh nhau. Hỏi có tất cả bao nhiêu cách xếp? Nếu yêu cầu thêm các luật sư không đứng ở đầu hàng thì có tất cả bao nhiêu cách xếp ? Đáp án. 3!× 3!× 4!× 5! 2× 2!× 3!× 4!× 5! Bài giảng Toán tổ hợp 2017 22/40 Hoán vị lặp, tổ hợp lặp Nội dung Tổ hợp lặp 1 Hoán vị lặp 2 Chỉnh hợp lặp 3 Tổ hợp lặp 4 Khai triển lũy thừa của đa thức Bài giảng Toán tổ hợp 2017 23/40 Hoán vị lặp, tổ hợp lặp Hoán vị lặp Hoán vị lặp Ví dụ. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ AAABB? Đáp án. 10 Ví dụ. Có thể nhận được bao nhiêu chuỗi kí tự khác khác nhau bằng cách sắp xếp lại các chữ cái của từ SUCCESS? Giải. Chuổi SUCCESS này chứa 3 chữ S, 2 chữ C, 1 chữ U và 1 chữ E. Để xác định số chuỗi khác nhau có thể tạo ra được ta nhận thấy có - C37 cách chọn 3 chổ cho 3 chữ S, còn lại 4 chổ trống. - Có C24 cách chọn 2 chổ cho 2 chữ C, còn lại 2 chổ trống. - Có thể đặt chữ U bằng C12 cách và C 1 1 cách đặt chữ E vào chuỗi. Theo nguyên lý nhân, số các chuỗi khác nhau có thể tạo được là: Bài giảng Toán tổ hợp 2017 24/40 Hoán vị lặp, tổ hợp lặp Hoán vị lặp C37 × C24 × C12 × C11 = 7! 4!× 3! × 4! 2!× 2! × 2! 1!× 1! × 1! 1!× 0! = 7! 3!× 2!× 1!× 1! = 420. Định nghĩa. Cho n đối tượng trong đó có ni đối tượng loại i (1 < i ≤ k) giống hệt nhau, nghĩa là n1 + n2 + · · ·+ nk = n. Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một hoán vị lặp của n. Định lý. Số hoán vị lăp của n trong trường hợp trên là n! n1!× n2!× · · · × nk! Bài giảng Toán tổ hợp 2017 25/40 Hoán vị lặp, tổ hợp lặp Hoán vị lặp Chứng minh. Để xác định số hoán vị trước tiên chúng ta nhận thấy Có Cn1n cách giữ n1 chỗ cho n1 phần tử loại 1, còn lại n− n1 chỗ trống. Sau đó có Cn2n−n1 cách đặt n2 phần tử loại 2 vào hoán vị, còn lại n−n1 − n2 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 vị. Cuối cùng có Cnkn−n1−···−nk−1 cách đặt nk phần tử loại k vào hoán vị. Theo nguyên lý nhân tất cả các hoán vị có thể là: Cn1n × Cn2n−n1 × · · · × Cnkn−n1−···−nk−1 = n! n1!× n2!× . . .× nk! . Ví dụ. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ ATAHATAT? Bài giảng Toán tổ hợp 2017 26/40 Hoán vị lặp, tổ hợp lặp Hoán vị lặp Giải. Trong từ ATAHATAT có 4 chữ A, 3 chữ T và 1 chữ H. Do đó số chuỗi có được là 8! 4!× 3!× 1! = 280 Ví dụ.(tự làm) Từ các chữ số 1, 2, 3 lập được bao nhiêu số tự nhiên có đúng 5 chữ số 1, 2 chữ số 2 và 3 chữ số 3. Hướng dẫn. Số tự nhiên đó có 10 chữ số, trong đó có đúng 5 chữ số 1, 2 chữ số 2 và 3 chữ số 3. Do đó ta sẽ lập được 10! 5!× 2!× 3! = 2520 số Bài giảng Toán tổ hợp 2017 27/40 Hoán vị lặp, tổ hợp lặp Chỉnh hợp lặp Chỉnh hợp lặp Ví dụ. Từ bảng chữ cái tiếng Anh, có thể lặp được bao nhiêu chuỗi có độ dài 5? Đáp án. 265 Định nghĩa. Cho A là tập hợp gồm n phần tử. Chỉnh hợp lặp chập k của n phần tử là một bộ sắp thứ tự k phần tử của A, các phần tử có thể lấy lặp lại. Định lý. Số chỉnh hợp lặp chập k của n phần tử là nk. Chứng minh. Giả sử A = {a1, a2, . . . , an}. Mỗi chỉnh hợp lặp chặp k của n là bộ thứ tự gồm k phần tử x1x2 . . . xk. Ta có, mỗi xi có n cách chọn. Áp dụng nguyên lý nhân, ta có số chỉnh hợp lặp chặp k của n là nk. Bài giảng Toán tổ hợp 2017 28/40 Hoán vị lặp, tổ hợp lặp Tổ hợp lặp Tổ hợp lặp Ví dụ. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn? Đáp án. An có 6 cách chọn là AA, AB, AC, BB, BC, CC. Định nghĩa. Mỗi cách chọn ra k vật từ n loại vật khác nhau (trong đó mỗi loại vật có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp chập k của n. Số các tổ hợp lặp chập k của n được ký hiệu là Kkn Định lý. Số các tổ hợp lặp chập k của n là Kkn = C k n+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 “|” và k ngôi sao “ ∗ ”. Ta dùng n− 1 thanh đứng để phân cách các ngăn. Bài giảng Toán tổ hợp 2017 29/40 Hoán vị lặp, tổ hợp lặp Tổ hợp lặp 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 tổ hợp. Chẳng hạn, tổ hợp lặp chập 6 của 4 phần tử được biểu thị bởi: ∗ ∗ | ∗ | | ∗ ∗ ∗ mô tả 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ứ 3 và 3 phần tử thứ tư của tập hợp. Mỗi dãy n− 1 thanh và k ngôi sao ứng với chuỗi có độ dài n+ k− 1. Do đó số các dãy n− 1 thanh đứng và k ngôi sao chính là số tổ hợp chập k từ tập n+ k − 1 phần tử. Đó là điều cần chứng minh. Hệ quả. Số nghiệm nguyên không âm (x1, x2, . . . , xn) (xi ∈ Z, xi ≥ 0) của phương trình x1 + x2 + . . .+ xn = k là Kkn = C k n+k−1. Ví dụ. Tìm số nhiệm nguyên không âm của phương trình x1 + x2 + x3 = 10. Bài giảng Toán tổ hợp 2017 30/40 Hoán vị lặp, tổ hợp lặp Tổ hợp lặp Giải. Số nghiệm nguyên không âm của phương trình là: K103 = C 10 12 . Ví dụ. Tìm số nghiệm nguyên của phương trình x1 + x2 + x3 + x4 = 20 (∗) thỏa điều kiện x1 ≥ 4;x2 > 2;x3 > 5;x4 ≥ −2 Giải. Ta viết điều kiện đã cho thành x1 ≥ 4;x2 ≥ 3;x3 ≥ 6;x4 ≥ −2. Đặt y1 = x1 − 4; y2 = x2 − 3; y3 = x3 − 6; y4 = x4 + 2. Khi đó yi ≥ 0 (1 ≤ i ≤ 4). Phương trình (∗) trở thành y1 + y2 + y3 + y4 = 9 (∗∗) Ta có số nghiệm của phương trình (∗) bằng số nghiệm của phương trình (∗∗). Do đó số nghiệm của phương trình (∗) là K94 = C912. Bài giảng Toán tổ hợp 2017 31/40 Hoán vị lặp, tổ hợp lặp Tổ hợp lặp Ví dụ. Tìm số nghiệm nguyên không âm của phương trình x1 + x2 + x3 + x4 = 20 thỏa điều kiện x1 ≤ 3;x2 ≥ 2;x3 > 4. (∗) Giải. Ta viết điều kiện đã cho thành 0 ≤ x1 ≤ 3;x2 ≥ 2;x3 ≥ 5;x4 ≥ 0. Xét các điều kiện sau: x1 ≥ 0; x2 ≥ 2; x3 ≥ 5; x4 ≥ 0 (∗∗) x1 > 3; x2 ≥ 2; x3 ≥ 5; x4 ≥ 0 (∗ ∗ ∗) Gọi p, q, r lần lượt là các số nghiệm nguyên không âm của phương trình thỏa các điều kiện (∗), (∗∗), (∗ ∗ ∗). Ta có p = q− r. Bài giảng Toán tổ hợp 2017 32/40 Hoán vị lặp, tổ hợp lặp Tổ hợp lặp Trước hết ta tìm q. Đặt y1 = x1; y2 = x2 − 2; y3 = x3 − 5; y4 = x4 Phương trình (1) trở thành y1 + y2 + y3 + y4 = 13 (2) Số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện (**) bằng số nghiệm nguyên không âm của phương trình (2) Số nghiệm đó là K134 = C 13 4+13−1 = C1316 . Vậy q = C1316 . Lý luận tương tự ta có r = K94 = C 9 4+9−1 = C912. Như vậy p = q − r = C1316 − C912 = 560− 220 = 340. Vậy số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện (∗) là 340. Bài giảng Toán tổ hợp 2017 33/40 Hoán vị lặp, tổ hợp lặp Tổ hợp lặp Hệ quả. Số cách chia k vật đồng chất nhau vào n hộp phân biệt cũng chính bằng số tổ hợp lặp chập k của n. Ví dụ. Tìm số cách chia 15 viên bi giống nhau cho 4 đứa trẻ. Đáp án. K154 = C 15 18 . Ví dụ. Tìm số nghiêm nguyên không âm của bất phương trình sau: x1 + x2 + x3 ≤ 11. Giải. Đặt x4 = 11− (x1 + x2 + x3). Khi đó x4 ≥ 0 và bất phương trình đã cho tương đương với phương trình x1 + x2 + x3 + x4 = 11 với x1, x2, x3, x4 là các số nguyên không âm. Do đó số nghiệm của bất phương trình là: K114 = C 11 14 = 364. Bài giảng Toán tổ hợp 2017 34/40 Hoán vị lặp, tổ hợp lặp Tổ hợp lặp Ví dụ. Tìm số nghiệm nguyên của bất phương trình x+ y + z ≤ 20, biết x ≥ 1, y ≥ 2, z ≥ 3. Ví dụ. Tìm số nghiệm nguyên của bất phương trình x+ y + z ≤ 15 thỏa điều kiện 2 ≤ x ≤ 6, y ≥ 2, z ≥ 3. Ví dụ. Tìm số nghiệm nguyên của phương trình x+ y + z + t = 16 thỏa điều kiện 2 ≤ x ≤ 5, y ≥ 1, z ≥ 2, t ≥ 3. Ví dụ. Có bao nhiêu cách chia 18 viên bi giống nhau cho 4 đứa trẻ sao cho mỗi đứa trẻ đều có bi và đứa lớn nhất được ít nhất 6 viên bi. Bài giảng Toán tổ hợp 2017 35/40 Hoán vị lặp, tổ hợp lặp Khai triển lũy thừa của đa thức Khai triển lũy thừa của đa thức Định lý. Cho x, y là biến và n là số tự nhiên. Khi đó (x+ y)n = n∑ k=0 Cknx n−kyk = C0nx n + C1nx n−1y + · · ·+ Cn−1n xyn−1 + Cnnyn. Chứng minh. Ta có (x+ y)n = (x+ y)(x+ y) . . . (x+ y). Các số hạng trong khai triển của (x+ y)n sẽ có dạng xn−kyk với k = 0, 1, . . . , n. Để nhận được số hạng xn−kyk ta chọn x từ n− k tổng (x+ y) và có Cn−kn cách chọn như vậy, khi đó y được chọn từ k tổng còn lại (chỉ có một cách duy nhất). Đó đó hệ số của xn−kyk là Cn−kn Bài giảng Toán tổ hợp 2017 36/40 Hoán vị lặp, tổ hợp lặp Khai triển lũy thừa của đa thức Hệ quả. Lần lượt cho x = y = 1 và x = 1, y = −1 vào khai triển trên ta có (i) n∑ k=0 Ckn =C 0 n + C 1 n + C 2 n + . . .+ C n n = 2 n (ii) n∑ k=0 (−1)kCkn =C0n − C1n + C2n + . . .+ (−1)nCnn = 0 Ví dụ. Khai triển (x+ y)4 Giải. (x+ y)4 = 4∑ k=0 Ck4x 4−kyk = C04x 4 + C14x 3y + C24x 2y2 + C34xy 3 + C44y 4. = x4 + 4x3y + 6x2y2 + 4xy3 + y4. Ví dụ. Khai triển (2x− 3y)5 Bài giảng Toán tổ hợp 2017 37/40 Hoán vị lặp, tổ hợp lặp Khai triển lũy thừa của đa thức Ví dụ. Tìm hệ số của x12y13 trong khai triển (2x− 3y)25? Giải. Dựa vào Định lý, ta có [ 2x+ (−3y) ]25 = 25∑ k=0 Ck25(2x) 25−k(−3y)k. Do đó hệ số của x12y13 có được khi k = 13. Suy ra hệ số cần tìm là: C1325 2 12(−3)13 = −33959763545702400. Bài giảng Toán tổ hợp 2017 38/40 Hoán vị lặp, tổ hợp lặp Khai triển lũy thừa của đa thức Định lý. Cho x1, x2, . . . , xm là các biến và n là số nguyên dương. Khi đó (x1 + x2 + · · ·+ xm)n = ∑ k1+k2+···+km=n n! k1! k2! . . . km! xk11 x k2 2 . . . x km m Ví dụ. Tìm hệ số của x3y5z trong khai triển (x+ 2y − 3z + t)9 Giải. Áp dụng Định lý trên, ta có số hạng chứa x3y5z là 9! 3! 5! 1! 0! x3(2y)5(−3z)1t0 = −48384x3y5z. Vây hệ số của x3y5z là −48384. Bài giảng Toán tổ hợp 2017 39/40 Hoán vị lặp, tổ hợp lặp Khai triển lũy thừa của đa thức Ví dụ. Cho khai triển của (−x+ y − 2z + t)10 a) Tìm hệ số của x5y4t. b) Có bao nhiêu số hạng khác nhau trong phép khai triển trên? Hướng dẫn. b) Mỗi số hạng có dạng Mxaybzctd. Suy ra các số hạng khác nhau của khai triển là số nghiệm của phương trình a+ b+ c+ d = 10, với a, b, c, d là các số nguyên không âm. Đáp án. K104 = C 10 13 . Bài giảng Toán tổ hợp 2017 40/40
File đính kèm:
bai_giang_toan_to_hop_chuong_1_to_hop_co_ban.pdf