Đại số tổ hợp

ĐẠI SỐ TỔ HỢP 
 Gv: Nguyễn Hoàng Lâm (01666.34.94.73) 
1. CÁC PHÉP ĐẾM CƠ BẢN: 
a./ QUY TẮC CỘNG: Nếu một công việc có n phương án thực hiện, phương án 1 có k1 cách thực hiện, phương án 2 
có k2 cách thực hiện, phương án 3 có k3 cách thực hiên,.và phương án n có kn cách thực hiện thì tổng số cách thực 
hiện công việc là: 1 2 3 ..... nk k k k    
Vd: Từ TP A đến TP B có thể đi bằng xe hay thuyền, mỗi ngày có 5 chuyến xe và 4 chuyến thuyền. Hỏi mỗi ngày có bao nhiêu 
sự lựa chọn để đi từ TP A đến TP B. 
HD: Xe có 5 sự lựa chọn, thuyền có 4 sự lựa chọn nên có tất cả 9 sự lựa chọn. 
b./ QUY TẮC NHÂN: Nếu một công việc thực hiện theo n công đoạn, công đoạn 1 có k1 cách thực hiện, công đoạn 2 
có k2 cách thực hiện, công đoạn 3 có k3 cách thực hiên,.và công đoạn n có kn cách thực hiện thì tổng số cách thực 
hiện công việc là: 1 2 3. . ..... nk k k k 
Vd0: Có 2 phái đoàn, phái đoàn 1 có 9 người, phái đoàn 2 có 10 người. Hỏi có bao nhiêu cái bắt tay, biết rằng mỗi 
người của phái đoàn này phải bắt tay với mỗi người của phái đoàn kia. 
HD: Mỗi người phái đoàn 1 bắt tay với 10 người của phái đoàn 2 nên có tất cả 9.10 = 90 cái bắt tay. 
Vd1: (Bài 1/22/Tài liệu NHC): Từ TP 
: 3.2 6 cách
 có thê thuc hien theo 2 cách ó tâ ca 12 cách
: 2.3 6 cách
A B D
A D c t
A C D
  
    
từ A đến D. 
Vd2: (Bài 2) Lập ban quản lý có 3 công đoạn: chọn 1 trưởng ban, 1 phó ban, 1 thư ký. Chọn trưởng ban có 8 cách, 
1 phó ban có 7 cách và 1 thư ký có 6 cách, nên có tật cả 8.7.6 = 336 cách 
Vd 3: ( Bài 3) công việc gồm 2 công đoạn: công đoạn 1 là xếp nam: vị trí 1: có 5 cách, vị trí 2: có 4 cách, vị trí 3: 
có 3 cách, vị trí 4: có 2 cách, vị trí 5: có 1 cách. Vậy có 5.4.3.2.1 = 120 cách xếp nam Công đoạn 2: tương tự cũng 
có 120 cách xếp nữ. Đảo vị trí nam nữ có 2 cách. Vậy có tất cả 120.120.2 = 28800 cách. 
Vd4: Hai công đoạn. Công đoạn 1: Xếp 2 nữ ngồi vào vị trí 1 và 2: Có 3.2 cách. Công đoạn 2: xếp 4 bạn còn lại có 
4.3.2.1. Vậy có 3.2.4.3.2.1 = 144 cách. 
2. HOÁN VỊ ( là đổi vị trí các phần tử trong tập hợp): Cho tập hợp A có n phần tử. Với mỗi cách sắp xếp của n phần 
tử của tập A cho ta 1 hoán vị của tập A. Vậy có bao nhiêu hoán vị của tập A. 
Việc sắp xếp n phần tử vào n vị trí theo quy tắc nhân có: n.(n-1).(n-2)1 = n! cách. Vậy Pn = n! cách 
Vd: Có bao nhiêu cách sắp xếp 10 người vào 10 ghế thành 1 hàng. 
HD: Ghế 1 có 10 cách, ghế 2 có 9 cách, ghế 3 có 8 cách,.ghế 10 có 1 cách. Vậy có 10! = 3628800 cách 
3. CHỈNH HỢP: Tập A có n phần tử, rút ra k phần tử với 1 k n  rồi sắp xếp chúng theo 1 thứ tự ta có 1 chỉnh hợp 
chập k của n phần tử. Vậy có tất cả bao nhiêu chỉnh hợp chập k của n phần tử ? 
Việc sắp xếp n phần tử vào k vị trí có: n.(n-1).(n-2)..[n-(k-1)] = 
.( 1).( 2)....[ ( 1)].( )....1 !
( )....1 ( )!
n n n n k n k n
n k n k
    

 
Vậy chỉnh hợp chập k của n phần tử là: 
!
( )!
k
n
n
A
n k


Vd: Cho tập  1;3;5;6A  . Có bao nhiêu số có 2 chữ số, 3 chữ số khác nhau được tạo thành từ tập A. 
HD: Chọn ra 2 số từ tập A là chỉnh hợp chập 2 của 4 có 24 12A  cách, chọn ra 3 số từ tập A có 
3
4 24A  cách. 
 4. TỔ HỢP: Tổ hợp khác chỉnh hợp ở chỗ là không quan tâm đến vị trí sắp xếp các phần tử trong tập hợp. Vậy nếu có 
k
nA chỉnh hợp thì sẽ có k! hoán vị, suy ra số tổ hợp chập k của n phần tử là: 
!
! !( )!
k
k n
n
A n
C
k k n k
 

* Lưu ý: Hai chỉnh hợp khác nhau nếu: có ít nhất 1 phần tử khác nhau hay 1 vị trí sắp xếp khác nhau. 
 Hai tổ hợp khác nhau nếu có ít nhât 1 phần tử khác nhau. 
Vd: ( bài 5/22 tài liệu NHC): Chọn ra 3 nam đặt vào 3 vị trí cặp đôi có 310A ( có sự thay đổi vị trí ). Chọn ra 3 nữ đặt 
vào 3 vị trí 36C ( không quan tâm đến vị trí, vì sẽ trùng lặp nếu thay đổi vị trí ). Vậy có 
3 3
10 6 14400A C  
+ Lý luận theo quy tắc nhân: 2 công đoạn, công đoạn 1: chọn 3 nam và 3 nữ có 3 310 6C C cách, công đoạn 2 xếp 3 nam 
vào 3 vị trí và xếp 3 nữ vào 3 vị trí có 6 cách xếp 
u1
2
am1 u2 ó 3 cách, 2 ó 2 cá , Nam3: u3 ó 1 cách ó 3.2.1 6
u3
u3
N
Nu
N N c Nam c ch N c c
N
N

     

, vậy có 3 310 6 .6C C