CHƯƠNG 2
CÁC PHƯƠNG PHÁP ĐẾM
VÀ NGUYÊN LÝ DIRICHLET

Các phần học trong chương 2

Các nguyên lý đếm cơ bản.

Khái niệm về hoán vị, chỉnh hợp, tổ
hợp.

Nhị thức Newton.

Nguyên lý Dirichlet.

Hệ thức truy hồi.

Quan hệ chia để trị

Nguyên lý bù trừ.

1.Các nguyên lý đếm cơ bản
1.1 Nguyên lý cộng

Cho A là một tập hữu hạn các phần tử, ta
ký hiệu N(A) là số lượng các phần tử của
A.

Nguyên lý cộng: Cho A
1


1.Các nguyên lý đếm cơ bản
1.1 Nguyên lý cộng

Ví dụ: Một sinh viên có thể chọn bài thực hành
máy tính trong ba danh sách tương ứng có 23, 15
và 19 bài. Có bao nhiêu cách chọn bài thực hành?

Giải:

Có 23 cách chọn bài thực hành từ ds thứ
nhất.

Có 15 cách chọn bài thực hành từ ds thứ hai.

Có 23 cách chọn bài thực hành từ ds thứ ba.

Vậy có 23 + 15 + 19 cách chọn bài thực
hành.

1.Các nguyên lý đếm cơ bản
1.2 Nguyên lý nhân

Nguyên lý nhân: Cho A
1
, A
2
, ..., A
n
là

2. K/n về hoán vị, chỉnh hợp, tổ hợp
2.1 Chỉnh hợp lặp

Chỉnh hợp lặp chập k của 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 phần tử
có thể lấy lặp lại.

Công thức tính:
kk
n
nA
=
Ví dụ: Tập A = {1,2,3,4,5} các bộ (1,1,2);
(1,2,1); (2,3,5) và (2,3,2) là chỉnh hợp lặp
chập 3 của 5 phần tử.

2. K/n về hoán vị, chỉnh hợp, tổ hợp
2.2 Chỉnh hợp không lặp

Chỉnh hợp không lặp chập k từ n phần tử
là một cách sắp xếp có thứ tự k phần tử
của n phần tử, mỗi phần tử không được
lấy lặp lại.

Công thức tính:
)!(
!
kn
n

không phân biệt thứ tự k phần tử lấy từ
tập n phần tử đã cho, mỗi phần tử
không được lấy lặp lại.

Công thức tính:
!)!(
!
kkn
n
C
k
n
−
=
Ví dụ: Có bao nhiêu cách tuyển 5 trong số
10 cầu thủ cầu lông để đi thi đấu?
Giải: Đó chính là số tổ hợp chập 5 của 10
phần tử:
252
!5!5
!10
5
10
==C

2. K/n về hoán vị, chỉnh hợp, tổ hợp
2.5. Tổ hợp lặp

Tổ hợp lặp chập k từ n phần tử là một bộ
gồm k phần tử không phân biệt thứ tự,

=
+ =
∑

Ví dụ: triển khai biểu thức (x+y)
4
4322344
44
4
33
4
222
4
31
4
40
4
4
464)(
)(
yxyyxyxxyx
yCxyCyxCyxCxCyx
++++=+
++++=+

4. Nguyên lý Dirichlet
4.1. Mở đầu

Giả sử có một đàn chim bồ câu có 5 con bay
vào chuồng.