Giải tích tổ hợp
Nguyên lý nhân: Một công việc được chia làm k giai đoạn. Cón 1cách hoàn thành giai đoạn 1, Có n2 cách hoàn thành giai đoạn 2, . . . , Có nk cách hoàn thành giai đoạnk. Số cách thực hiện công việc
GIẢI TÍCH TỔ HỢP
1.1 Nguyên lý nhân: Một công việc được
chia làm k giai đoạn. Có n1 cách hoàn
thành giai đoạn 1, Có n2 cách hoàn thành
giai đoạn 2, . . . , Có nk cách hoàn thành
giai đoạn k. Số cách thực hiện công việc
n = n1.n2 ...nk
Ví dụ. Có tất cả bao nhiêu xâu nhị phân có
độ dài bằng 4?
1.2 Hoán vị: Cho A là tập hợp khác ∅ có
số phần tử là n. Một hoán vị của A là một
cách sặp xếp có thứ tự các phần tử của A.
Mệnh đề. Số hoán vị của tập A có n phần
tử bằng n!.
Ví dụ. Có bao nhiêu cách sắp 5 người vào
một bàn dài có 5 chỗ ngồi.
1.3 Chỉnh hợp. Cho A là tập hợp có n
phần tử. Một cách sắp xếp có thứ tự m
phần tử trong n phần tử của tập hợp A được
gọi là một chỉnh hợp chập m của n phần tử
Mệnh đề. Số chỉnh hợp châp m của n
phần tử là:
m n!
An =
(n - m)!
Ví dụ có bao nhiêu cách sắp xếp 5 cuốn
sách khác nhau vào kệ sách có 15 ô.
1.4 Chỉnh hợp lặp. Một bộ thứ tự gồm m
phần tử không nhất thiết khác nhau cùa 1
tập hợp A gồm n phần tử được gọi là một
chình hợp lặp chập m cùa n phần tử,
Mệnh đề. Số chỉnh hợp lặp chập m của n
phận từ bằmg:
An = n m .
m
Ví dụ. Cho A là tập có n phần tử tính số
tập con của nó
1.5 Tổ hợp. Một cách chọn m phần tử
trong một tập hợp gồm n phần tử được gọi
là một tổ hợp chập m cùa n phần tử.
Mệnh đề. Số tổ hợp chập m của n phần tử
bằng:
m n!
Cn =
m!(n - m)!
Ví dụ. Có bao nhiêu cách chia 12 cuốn
sách cho bốn học sinh mỗi em được 3 cuốn
1.6 Tổ hợp lặp: Một nhóm có m phần tử
không phân biệt thứ tự, có thể trùng nhau
được gọi là một tổ hợp lặp chập m của n
phần tử.
Mệnh đề. Số tổ hợp lặp chập m của n phần
tử bằng.
Cn = Cn+ m- 1 = Cn+ 1 - 1
m m n-
m
Định lý. Số cách chia m vật đồng chất
giống nhau vào n hộp khác nhau là
m
C n
Ví dụ 1. Có bao nhiêu cách chia 10 viên bi
giống nhau cho 5 đứa trẻ trong các trường
hợp sau:
a. Không có một hạn chế nào.
b. Đứa trẻ lớn nhất được ít nhất 2 viên bi.
Ví dụ 2. Có bao nhiêu cách chia 10 viên bi
khác nhau cho 5 đứa trẻ trong các trường
hợp sau:
a. Không có một hạn chế nào.
b. Đứa trẻ lớn nhất được ít nhất 2 viên bi.
1.7 Phân hoạch: Cho A là tập hợp có n
phần tử. Ký hiệu A = n.
Một sự phân chia tập A thành những tập
con A1 , A2 ,K , Ak khác rỗng sao cho:
k
A= U Ai ; Ai I
i= 1
A j = Æ(i ¹ j )
Được gọi là một phân hoạch của tâp A
thành k tập con.
Mệnh đề. Số phân hoạch khác nhau thành
k tập con của tập A là
n!
n1 !n2 !K nk !
