TOÁN HỌC TỔ HỢP
Chương 4
TỔ HỢP CƠ BẢN
Đại học Khoa Học Tự nhiên Tp. Hồ Chí Minh
Chương 4. Tổ hợp cơ bản LVL c
❖
2020 1/39
Nội dung
Chương 4. TỔ HỢP CƠ BẢN
4. Các nguyên lý đếm cơ bản
4. Tổ hợp
4. Tổ hợp lặp
Chương 4. Tổ hợp cơ bản LVL c
❖
2020 2/39
4.1. Các nguyên lý đếm cơ bản
1Nguyên lý cộng
2Nguyên lý nhân
3Nguyên lý Dirichlet
Chương 4. Tổ hợp cơ bản LVL c
❖
2020 3/39
4.1.1. Nguyên lý cộng
Giả sử ta muốn thực hiện việc Xbằng cách chọn một trong kphương
pháp T1, T2, . . . , Tkkhác nhau. Với mỗi phương pháp Ti(1 ≤i≤k)ta
có nicách thực hiện việc X. Như vậy số cách thực hiện việc Xlà
n1+n2+· · · +nk.
Ví dụ. Một sinh viên 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 lần lượt là 23, 15 và 19. Hỏi sinh viên
có bao nhiêu cách chọn đề 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, . . . , Aklà các tập hữu hạn đôi một rời nhau thì
|A1∪A2∪. . . ∪Ak|=|A1|+|A2|+. . . +|Ak|.
Chương 4. Tổ hợp cơ bản LVL c
❖
2020 4/39
4.1.2. Nguyên lý nhân
Giả sử muốn thực hiện thủ tục Xta phải thực hiện kviệc X1, X2,
...,Xkliên tiếp nhau. Nếu mỗi việc Xi(1 ≤i≤k)có nicách thực
hiện thì số cách thực hiện thủ tục Xlà
n1×n2×... ×nk
Ví dụ.
Hỏi có nhiêu cách đi từ Ađến C?
Đáp án. 3×2 = 6 cách.
Chương 4. Tổ hợp cơ bản LVL c
❖
2020 5/39