CHƯƠNG 1. CC KIN THC CƠ S
1.1. Các khái niệm cơ bản
1.2. Lý thuyết tổ hợp
1.3. Hai nguyên lý cơ bản
1.4. Lý thuyết số và các hệ đếm
1.5. Bài tập
LÝ THUYT TỔ HỢP
1. Khái niệm.
2. Chỉnh hợp lặp.
3. Chỉnh hợp không lặp.
4. Hoán vị.
5. Tổ hợp.
6. Tổ hợp lặp.
7. Hoán vị của tập hợp có các phần tử giống nhau.
8. Một số công thức tổ hợp.
9. Một số ví dụ.
KHI NIỆM
Lý thuyết tổ hợp nghiên cứu:
1. Các cấu hình tổ hợp,
2. Các phương pháp lựa chọn phần tử hoặc bộ các phần tử trong
tập hợp hữu hạn theo các cách khác nhau.
→ Là cơ sở để xây dựng thuật toán vét cạn, các thuật toán sinh
phần tử mới, các thuật toán lựa chọn phương án tối ưu, v v…
Một số bài toán:
1. Các bài toán đếm,
2. Các bài toán về sự tồn tại,
3. Các phương pháp biểu diễn các cấu hình tổ hợp…

CHỈNH HỢP LẶP
KN: Chỉnh hợp lặp chập k của tập n phần tử là một cách sắp
xếp có thứ tự k phần tử lấy từ tập gồm n phần tử đã cho, mỗi

tử của tập n phần tử, mỗi phần tử không được lấy lặp
lại.
KH: Số chỉnh hợp chập k của n phần tử:
)!(
!
)1) (2)(1.(
kn
n
knnnnP
k
n


CHỈNH HỢP KHÔNG LẶP
Ví dụ 4.
• Tập A = {1, 2, 3, 4, 5} các bộ (2, 3, 5); (2, 5, 3) là các chỉnh hợp
không lặp chập 3 từ 5 phần tử, còn các bộ (1, 1, 2) ; (1, 2, 1) ; và
(2, 3, 2) không phải là chỉnh hợp không lặp chập 3 từ 5 phần tử,
nhưng mặt khác đó lại là chỉnh hợp lặp chập 3 từ 5 phần tử.
Ví dụ 5.
• Có bao nhiêu số có 4 chữ số khác nhau được chọn từ các số sau B
= {1,3, 4, 5, 7, 6}?
• Giải: Số các số có 4 chữ số khác nhau được chọn từ tập B là số
chỉnh hợp chập 4 của 6:
• (số)
4
6
6! 6!
6.5.4.3 360
(6 4)! 2!

n
C
n k k


!!

( )! ! !( )!
k n k
nn
nn
CC
n k k k n k

  

TỔ HỢP
Ví dụ 7:
 Với tập A = {1, 2, 3, 4, 5} thì các bộ (1, 2, 3 ), (1, 2, 4) là các tổ
hợp chập 3 từ 5 phần tử, còn các bộ (1, 1, 2 ), (2, 3, 2 ) không
phải là tổ hợp chập 3 từ 5 phần tử đã cho. Theo định nghĩa
hai bộ (2, 3, 5 ), (3, 5, 2) chỉ được tính là một tổ hợp chập 3.
Ví dụ 8:
 Có 12 đội bóng tham dự giải chuyên nghiệp quốc gia, các đội
thi đấu vòng tròn một lượt. Hỏi có bao nhiêu trận đấu được tổ
chức ?
 Giải : Mỗi trận đấu là một cặp 2 đội được chọn từ 12 đội đã
cho, không kể đến thứ tự và phải khác nhau, vậy số trận đấu
là tổ hợp chập 2 từ 12 : 12!/(10!.2!) = 66 trận
TỔ HỢP LẶP

chọn 11 phần tử từ một tập có 3 loại, sao cho có x
1
phần tử loại 1, x
2

phần tử loại 2, x
3
phần tử loại 3 được chọn. Vì vậy số nghiệm bằng số
tổ hợp chập 11 từ tập gồm 3 phần tử. Theo công thức trên ta có
11 11 11 2
3 11 3 1 13 13
13.12
C 78
1.2
R C C

    
HON VỊ CỦA TẬP HỢP CÓ CC PHẦN TỬ GIỐNG NHAU
KN: Giả sử có n phần tử trong đó có n
1
phần tử giống nhau thuộc
loại 1, n
2
phần tử giống nhau thuộc loại 2, …, và n
k
phần tử giống
nhau thuộc loại k. Khi đó số cách sắp xếp n phần tử được tính
như sau:
 Số cách chọn n
1

)!(
)!(!
!k21k
1k1
212
1
11
n
nnn
n
nn
n
n
nnn
n
0n
nnn
nnnn
nn
nnn
n
CCC
k
1k1
2
1
1

kn
n
k
n
CC



1
1 k
n
k
n
k
n
CCC



C ) (
n
0i
i
n



inin
yxyx
1.

2
, …, a
n
, a
n+1
, …, a
n+m
}= 
1
 
2
, trong đó 
1
=
a
1
, a
2
, …, a
n
 và 
2
= a
n+1
, a
n+2
, …, a
n+m
, như vậy để chọn tập con có k
phần tử của  ta có thể chọn như sau:

n
k
n
1
m
1k
n
2k
m
2
n
1k
m
1
n
k
m
k
mn
CCCCCCCCCCC






BÀI TẬP
1. Cho n là số nguyên dương, chứng minh
1
k
n
kC
0
( 1) 0
n
k

kk
n
C



a.
b.
c.
BÀI TẬP
6. Có bao nhiêu cách chọn 8 đồng tiền xu từ hộp chứa 100
đồng một xu giống nhau và 80 đồng năm xu giống nhau?
7. Phương trình :
x
1
+ x
2
+ x
3
+ x
4

đầu bằng bít 1 và chứa thêm 3 bít 1 nữa, nó còn chứa tất cả
12 bít 0 và sau mỗi bít 1 có ít nhất hai bít 0?
10. Có bao nhiêu xâu khác nhau có thể lập được từ chữa cái
trong từ MISSISSIPPI, yêu cầu phải dùng tất cả các chữ?