Chương IV
ĐẾM CÁC PHẦN TỬ
I) Các phương pháp đếm cơ bản
1. Mở đầu
Số serial của phiên bản Windows 98 của hãng MicroSoft gồm một dãy 25 chữ
số thập phân và chữ cái trong bộ mẫu tự tiếng Anh (không phân biệt hoa/ thường). Vậy
có bao nhiêu số serial khã dó dùng cho các bản copy của phiên bản đó? Có tất cả bao
nhiêu lời gọi đệ qui xảy ra khi thực hiện đoạn chương trình giải bài toán tháp Hà Nội
với kích thước dữ liệu đầu vào N? Tìm kiếm câu trả lời cho các câu hỏi tương tự như
vậy đều dẫn đến việc thực hiện các phép đếm. Khi số lượng thực hiện thao tác đếm với
số lượng cần phải đếm là rất lớn hoặc các cấu hình cần phải đếm thay đổi phức tạp thì
việc phát triễn các kỹ thuật đếm là rất cần thiết.
2. Các nguyên lý đếm cơ bản.
Các kỹ thuật đếm thường dựa trên nguyên tắc chia bài toán đếm thành các bài
toán nhỏ hơn có cấu hình quen thuộc mà việc đếm các phần tử trong cấu hình đó chỉ
cần dựa trên một số các nguyên lí đếm cơ bản. Dó nhiên bài toán đếm chỉ có nghóa khi
nó dẫn đến đáp số hữu hạn (mặc dù đáp số này có thể là một con số khổng lồ!). Vì vậy
mọi tập hợp X được xét sau đây đều mặc đònh là tập hữu hạn và N(X) để chỉ số phần tử
của X.
o Nguyên lí cộng:
Nếu A và B là hai tập hợp rời nhau thì N(A
∪
B)=N(A)+N(B).
Ví dụ:
Có bao nhiêu cách chọn một vận động viên từ danh sách 12 người của
Huyện Chợ Lách, danh sách 14 người của Huyện Châu Thành và danh sách 20
người của Huyện Ba Tri biết rằng không có vận động viên nào thi đấu cho hơn một
huyện?
Lời giải:
Rõ ràng các danh sách là các tập rời nhau và việc lựa chọn vận động viên
trên mỗi danh sách là độc lập với nhau. Vì vậy số cách lựa chọn vận động viên là:

i
khả
năng lựa chọn (
1 i k
≤ ≤
) thì số cấu hình tạo ra là tích số các
khả năng này. Nói cách khác: Nếu
(1 ),
i i
i i k a A∀ ≤ ≤ ∈
thì:
N(A
1
xA
2
x ...x A
k
) = N(A
1
).N(A
2
)...N(A
k
)
Ví dụ:
Có bao nhiêu cách chọn ba vận động viên thuộc ba huyện theo thứ tự từ
danh sách 12 người của Huyện Chợ Lách, danh sách 14 người của Huyện Châu
Thành và danh sách 20 người của Huyện Ba Tri biết rằng mỗi huyện được chọn
đúng một vận động viên?
Lời giải:

Xét đoạn mã chương trình viết bằng ngôn ngữ Pascal sau:
Var K,n1,n2,n3:word;
Begin
{.....}
42
K := 7; n1:=5; n2:=10; n3:=15;
For i:=1 to n1 do
For j:=1 to n2 do
For t:=1 to n3 do
K:=K+1;
writeln(‘K = ’,K);
{.....}
Cho biết kết xuất của dòng lệnh cuối cùng là gì?
Lời giải:
Ở đây ta có ba vòng lặp FOR lồng nhau. Trình biên dòch Pascalsẽ biên dòch
để với mỗi lần lặp của vòng lặp bên ngoài thì vòng lặp ngay bên trong nó được thực
hiện đầy đủ các lần lặp. Vậy mỗi lần lặp của ba vòng lặp lồng nhau đó tương ứng
với một cấu hình là bộ ba có thứ tự (i,j,t). Ở mỗi lần lặp K đều tăng lên một đơn vò.
Sau tất cả lần lặp K tăng lên đúng bằng số lần lặp. K được khởi tạo trước khi vào
vòng lặp bằng 7. Vì i vét qua tất cả n
1
giá trò khác nhau, j vét qua tất cả n
2
giá trò
khác nhau, t vét qua tất cả n
3
giá trò khác nhau nên số cấu hình được tạo ra cho bộ
(i,j,t) là n
1
.n

được đếm A và B là rời nhau. Nếu không có giả thiết đó thì buộc phải loại bớt các phần
tử trùng nhau của hai tập bò đếùm qua quá một lần:
N(A
∪
B)=N(A)+N(B)-N(A
∩
B)
43
Ví dụ: Có bao nhiêu xâu nhò phân độ dài 8 bit với 3 bit 111 đứng đầu hoặc 2 bit 00 đứng
cuối.
Lời giải:
Số xâu độ dài 8 bit với 3 bit 111 đứng đầu là: 2
5
= 32 (Áp dụng nguyên lí nhân đối với 5
bít cuối do chỉ còn 5 bit cuối là thay đổi).
Tương tự, số xâu độ dài 8 bit với 2 bit 00 đứng cuối là: 2
6
= 64 (do chỉ còn 6 bit đầu là
thay đổi).
Số xâu vừa có 3 bit đứng đầu 111, vừa có 2 bit đứng cuối 00 là: 2
3
= 8.
Vậy số xâu thỏa điều kiện đòi hỏi là: (32+64) - 8 = 88
Tổng quát hơn:
Giả sử A
1
,A
2
, ...,A
m

C

phần giao như vậy. Hay:
N
2
= N(A
1
∩
A
2
)+N(A
1
∩
A
3
)+...+N(A
i
∩
A
j
)+....
N
2
=
, 1
( )
m
i j
i j
i j

=N(A
1
∩
A
2
∩
A
3
∩
...
∩
A
m
)
Ta chấp nhận không chứng minh tính chất trên.
Ví dụ:
Trong tập X={1,2, ... , 10000} có bao nhiêu số không chia hết cho bất cứ số nào trong
ba số 3,4,7?
Lời giải:
Đặt A
i
là tập các số thuộc X mà chia hết cho i {i=3,4,7}.
44
Khi đó A
3
∪
A
4
∪
A

2
= N(A
3
∩
A
4
)+N(A
3
∩
A
7
)+N(A
4
∩
A
7
)
= (10000 div (3x4))+(10000 div (3x7))+(10000 div (4x7)) = 833+476+357 =1666
N
3
= N(A
3
∩
A
4
∩
A
7
)=(10000 div (3x4x7))=119.
Suy ra số các số thuộc X mà không chia hết cho số nào trong 3 số 3,4,7 là:

nào.
1
Người viết giả thiết rằng người đọc đã biết phát biểu của bài toán này. Và ở thời điểm đọc
phần này người đọc đã hiểu về lời gọi đệ qui trong một ngôn ngữ lập trình nào đó.
45