Mục lục
1 Một số kỹ năng giải bài toán đếm 3
1.1 Sử dụng các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Quy tắc cộng, quy tắc nhân . . . . . . . . . . . . . . . . . 3
1.1.2 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Phép tương ứng 1- 1 . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.1 Mô tả phần tử đếm . . . . . . . . . . . . . . . . . . . . . . 17
1.2.2 Mã hóa 0, 1 phần tử đếm . . . . . . . . . . . . . . . . . . 19
1.2.3 Phương pháp đánh số . . . . . . . . . . . . . . . . . . . . 24
1.3 Một số phương pháp giải nâng cao của bài toán đếm . . . . . . . 26
1.3.1 Nguyên lí bao gồm và loại trừ . . . . . . . . . . . . . . . . 26
1.3.2 Phương pháp truy hồi . . . . . . . . . . . . . . . . . . . . 30
2 Một số dạng bài toán tổ hợp liên quan đến bài toán đếm 34
2.1 Nguyên lí bất biến . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.1 Phát hiện đại lượng bất biến trong bài toán . . . . . . . 34
2.1.2 Giải toán bằng đại lượng bất biến . . . . . . . . . . . . . 39
2.1.3 Bất biến đơn điệu . . . . . . . . . . . . . . . . . . . . . . . 41
2.1.4 Một số bài toán nâng cao . . . . . . . . . . . . . . . . . . 44
2.2 Phân hoạch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2.1 Chứng minh không tồn tại phân hoạch thỏa mãn tính
chất (G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2.2 Chứng minh có tồn tại phân hoạch thỏa mãn tính chất
(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.2.3 Xây dựng phân hoạch tính chất (G) . . . . . . . . . . . . 49
2.2.4 Phân hoạch cân bằng . . . . . . . . . . . . . . . . . . . . . 52
2.2.5 Một số bài toán minh họa . . . . . . . . . . . . . . . . . . 53
2.3 Nguyên lí Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . 55
TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . 57
1

trong suốt quá trình tôi thực hiện luận văn này.
Tôi cũng xin gửi lời cảm ơn tới các thầy, cô giáo của trường Đại học Khoa
học Tự nhiên – Đại học Quốc gia Hà Nội đã hết lòng đào tạo, dạy dỗ giúp đỡ
tôi trong suốt thời gian tôi học tập tại trường.
Mặc dù vây, do năng lực cá nhân còn hạn chế cũng như thời gian hạn hẹp
luận văn không tránh khỏi những thiếu sót cả về mặt nội dung và hình thức,
rất mong sự đóng góp ý kiến của các thầy cô và các bạn.
2
Chương 1
Một số kỹ năng giải bài toán đếm
Bài toán đếm là một nội dung cơ bản không chỉ dành cho các bài toán
thi đại học mà còn rất cần thiết khi giải các bài toán tổ hợp khó trong
các kỳ thi học sinh giỏi. Một đặc điểm rất đặc thù của nội dung này là
khi giải toán, học sinh thường nhận được các đáp số khác nhau vì những
sai sót mà bản thân không nhận ra. Chính vì vậy xây dựng các kỹ năng
giải là thực sự cần thiết và nội dung của phần này là trình bày các kỹ
năng này.
1.1 Sử dụng các khái niệm cơ bản
1.1.1 Quy tắc cộng, quy tắc nhân
Quy tắc cộng.
Nội dung quy tắc: Nếu có m
1
cách chọn đối tượng a
1
, m
2
cách chọn
đối tượng a
2
, , m

1
cách chọn
đối tượng a
1
và với mỗi cách chọn a
1
có m
2
cách chọn đối tượng a
2
, sau
đó với mỗi cách chọn a
1
, a
2
có m
3
cách chọn đối tượng a
3
, Cuối cùng
với mỗi cách chọn a
1
, a
2
, a
3
, , a
n−1
có m
n

cách chọn các chữ số b, c,
d.
Trường hợp 2: a = 1. Có 4 cách chọn a ( vì a = 0).
- Nếu b = 1 thì có 1 cách chọn b và có A
2
4
cách chọn c, d;
- Nếu c = 1 thì có 1 cách chọn c và có A
2
4
cách chọn b, d;
- Nếu d = 1 thì có 1 cách chọn d và có A
2
4
cách chọn b, c;
Vậy theo quy tắc cộng có thể lập được 1.A
3
5
+ 4.A
2
4
+ 4.A
2
4
+ 4.A
2
4
= 204
(số).
Bài 2. Từ thành phố A đến thành phố B có 3 con đường, từ thành


d

, mà
4
abcd + a

b

c

d

= 11110
Khi đó, ta có đẳng thức:
(a+a

).1000+(b+b

).100+(c+c

).10+d+d

= 10.1000+10.100+10.10+1.10
Từ đó, ta có các đẳng thức
a + a

= b + b

= c + c

d

gồm 4
chữ số không trùng nhau thuộc tập {1, 2, 3, 4, 5, 6, 7, 8, 9}
Vậy tổng tất cả các số dạng trên là :
1
2
.9.8.7.6.11110 = 16798320
Bài 4. Một con ngựa trên bàn cờ vua 8x8. Hỏi có bao cách di chuyển con
ngựa trên bàn cờ.
Bài giải
Các ô của bàn cờ có thể đặt theo quy tắc a
ij
(i=1 8 ,j=1 8)
a
11
có 2 cách di chuyển.
a
12
có 3 cách di chuyển.
a
13
, a
14
, a
22
có 4 cách di chuyển.
a
23
, a

Lấy một quân domino bất kỳ nó thuộc một trong 2 loại:
Loại 1 (7 quân): (0,0), (1,1), ,(6,6).
Loại 2 (21 quân): có số chấm 2 đầu khác nhau.
- Nếu quân domino chọn ra là loại 1 (sẽ có 7 cách chon) sẽ được nối với 6
quân khác. Ví dụ như (1,1) sẽ được nối với (1,0), (1,2), (1,3),(1,4),(1,5),(1,6).
Vậy số cặp nối được trong trường hợp này là:
n
1
= 7.6 = 42.
- Nếu quân domino chọn ra là loại 2 (sẽ có 21 cách chọn), sẽ được nối với
12 quân khác. Ví dụ (2,3) sẽ được nối với (2,0), (2,1), (2,4), (2,2), (2,5),
(2,6),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6).
Vậy số cặp nối đươc trong trường hợp này là n
2
= 21.12 = 252
Theo quy tắc cộng thì số cách nối đươc là 252+42=294 (kể cả thứ tự).
Vì thứ tự giữa 2 đầu của quân domini được xác định, và mỗi cặp 2 quân
domino nối được đến 2 lần, ta suy ra số cặp nối được là n =
294
2
= 147.
1.1.2 Hoán vị
Hoán vị không lặp
Định nghĩa: Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi cách sắp
xếp n phần tử này theo một thứ tự nào đó (mỗi phần tử có mặt đúng
một lần) được gọi là một hoán vị của n phần tử đã cho. Kí hiệu số hoán
vị của n phần tử bằng P
n
Ta có công thức
P

2
.5! = 60.
Bài 9 Có bao nhiêu cách xếp 5 người đàn ông, 5 người đàn bà xung
quanh một bàn tròn 10 ghế sao cho không có 2 người đàn ông hoặc 2
người đàn bà nào ngồi cạnh nhau.
Bài giải
Lấy 1 ghế bất kỳ.
Nếu xếp 1 người đàn ông thì ghế tiếp theo là của đàn bà Số cách
xếp 5 đàn ông vào vị trí có sẵn là 5!, số cách xếp 5 đàn bàn vào vị trí là
5!. Số cách xếp theo vị trí này là 5!5!.
Nếu xếp 1 người đàn bà thì số cách xếp tương tự bằng 5!5!.
Đáp số:: 2.(5!)
2
.
Hoán vị có lặp
Định nghĩa: Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần
được gọi là hoán vị có lặp.
Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i
(1 ≤ i ≤ k) xuất hiện n
i
lần được kí hiệu là P (n
1
, n
2
, , n
k
) và được
tính bằng công thức
P (n
1

5
a
6
a
7
a
8
a
9
. Khi đó, mỗi số x tương ứng với
một hoán vị lặp của chín phần tử a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
, a
8
, a
9
.
Số các hoán vị khác nhau của chín phần tử a

Tương tụ đổi chỗ hai trong ba phần tử a
4
, a
6
, a
9
cho nhau vẫn chỉ cho
số x.
Như vậy, khi thực hiện 2! hoán vị a
2
, a
8
và 3! hoán vị a
4
, a
6
, a
9
, ta chỉ
được một số cần tìm x.
Vậy số các số có thể lập được là
S =
9!
2!3!
= 30240
Bài 11. Với sáu chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số chia
hết cho 5 gồm 11 chữ số, trong đó chữ số 1 có mặt 4 lần, chữ số 2 có mặt
3 lần, chữ số 3 có mặt 2 lần chữ số 4 có mặt 1 lần và tổng số lần xuất
hiện của chữ số 0 và chữ số 5 là 1.
Bài giải

a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
9
a
10
của x bằng số hoán vị lặp của 10 phần tử thuộc
4 loại chữ số: 1, 2, 3, 4 với 1 xuất hiện 4 lần, 2 xuất hiện 3 lần, 3 xuất
hiện 2 lần và 4 xuất hiện 1 lần sẽ bằng P(1, 2, 3, 4) . Ngoài ra a
11
lại có
thể nhận 0 hoặc 5 nên có thể lập được
2.P (1, 2, 3, 4) = 2.
10!
1!2!3!4!
= 25200

=
4!
2!
= 4.3 = 12.
Đáp số: n = n
1
− n
2
= 48
Ta xét một ví dụ đơn giản sau:
Xét tập A = {a, b}, ta lập tập B = {a, a, b, b, b}. Khi đó B = (A, α)
,α(a) = 2, a xuất hiện 2 lần, α(b) = 3 gọi là tập bội số lần xuất hiện α.
Khi đó, số cách xếp thành một hàng ngang của B bằng:
P (2, 5) =
5!
2!3!
.
Mở rộng, xét tập A = {x
1
, x
2
, , x
n
} gồm n phần tử riêng biệt.
Xét tập bội B trong đó x
i
xuất hiện α(x
i
) = α
i

Số hoán vị vòng quanh của n phần tử khác nhau (Q
n
) được tính bằng
công thức
Q
n
= (n − 1)!
Sau đây ta xét một số bài toán minh họa
9
Bài 14. Một hội nghị bàn tròn có năm nước tham gia. Anh có 3 đại biểu,
Pháp có 5 đại biểu, Đức có 2 đại biểu, Nhật có 3 đại biểu, Mỹ có 4 đại
biểu. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho mọi đại biểu sao cho
hai người cùng quốc tịch đều ngồi cạnh nhau.
Bài giải
Đầu tiên ta sắp xếp khu vực cho đại biểu từng nước. Ta mời phái đoàn
nào đó ngồi vào chỗ trước. Khi đó, bốn phái đoàn còn lại có 4! cách sắp
xếp.
Đối với mỗi cách sắp xếp các phái đoàn lại có: 3! cách sắp xếp đại biểu
trong nội bộ phái đoàn Anh; 5! cách sắp xếp đại biểu trong nội bộ phái
đoàn Pháp; 2! cách sắp xếp đại biểu trong nội bộ phái đoàn Đức; 3! cách
sắp xếp đại biểu trong nội bộ phái đoàn Nhật; 4! cách sắp xếp đại biểu
trong nội bộ phái đoàn Mỹ.
Bởi vậy, số cách sắp xếp chỗ ngồi cho tất cả các đại biểu để những
người cùng quốc tịch ngồi cạnh nhau sẽ bằng
4!3!5!2!3!4! = 4976640
Bài 15. Có bao nhiêu cách sắp xếp 5 nam A
1
, A
2
, A

kể B
1
, khi đó B
1
có thể xếp vào giữa A
2
, B
2
, giữa B
2
, A
4
, giữa A
4
, B
3
,
giữa A
5
, B
3
, giữa A
3
, A
5
. Như vậy có 7 −2 = 5 cách sắp xếp B
1
Vậy có
6!.5 = 720 cách sắp xếp.
c) Trước hết ta xếp 5 nam ngồi xung quanh bàn tròn. Số cách sắp xếp

Có n-1 cách lấy ra phần tử thứ 2

Có n-k+1 cách chọn ra phần tử thứ k
Theo quy tắc nhân, số hoán vị của k phần tử bằng n(n-1) (n-k+1)
(đpcm).
Sau đây ta xét một số bài toán minh họa:
Bài 16. Từ các chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số tự
nhiên mà trong mỗi số này các chữ số khác nhau?
Bài giải
Ta xét các trường hợp sau:
Trường hợp 1: Lập số có 1 chữ số có 6 số;
Trường hợp 2: Lập số có 2 chữ số có 5.5 = 25 số;
Trường hợp 3: Lập số có 3 chữ số có 5.A
2
5
= 100 số;
Trường hợp 4: Lập số có 4 chữ số có 5.A
3
5
= 300 số;
Trường hợp 5: Lập số có 5 chữ số có 5.A
4
5
= 600 số;
Trường hợp 6: Lập số có 6 chữ số có 5.A
5
5
= 600 số;
Vậy số các số tự nhiên có thể lập là 6+25+100+300+600+600 = 1631
Bài 17. Một cuộc khiêu vũ có 10 nam và 6 nữ tham gia. Đạo diễn

Có 5 cách chọn 1 người làm thư ký.
Có 4 cách chọn 1 người làm thủ quỹ.
Theo quy tắc nhân, số cách chọn bằng n=7.6.5.4=840.
Bài 19
Chọ tập A={0, 1, 2, 3, 4, 5}.Hỏi có bao nhiêu số gồm 4 chữ số phân biệt
lập được từ các chữ số của A. Hỏi có bao nhiêu số chẵn gồm 4 chữ số
phân biệt lập được từ các chữ số của A.
Bài giải
Đáp số n
1
= 5.A
3
5
= 300.
Ta chia tất cả các số chẵn thành 2 loại:
Loại 1: Số 0 đứng cuối cùng.
Loại 2: Số 2 hoặc số 4 đứng cuối cùng.
Số các số gồm 4 chữ số phân biệt mà số 0 đứng cuối bằng |S
1
| = A
3
5
=60.
Số các số mà số 2 hoặc 4 đứng cuối cùng (theo quy tắc nhân) bằng
|S
2
| = 4.4.3.2 = 96.
Đáp số n
2
= |S

các phần tử của tập X, mà mỗi phần tử có thể lặp lại nhiều lần và được
sắp xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập k
của n phần tử thuộc tập X.
Số chỉnh hợp lặp chập k của n phần tử kí hiệu là A
k
n
bằng số ánh xạ từ
tập k phần tử đến tập n phần tử và bằng n
k
, tức
A
k
n
= n
k
Sau đây ta xét một số bài toán minh họa:
Bài 21.Từ bốn chữ số 1, 2, 3, 5 có thể lập được bao nhiêu số chẵn gồm
4 chữ số?
Bài giải
Gọi số cần lập có dạng x = abcd. Vì x là số chẵn nên d = 2
Mỗi cách chọn bộ ba chữ số a, b, c là một chỉnh hợp lặp chập 3 của 4
phần tử 1, 2, 3, 5.
Vậy số các số chẵn có thể lập được bằng A
3
4
= 4
3
= 64.
Bài 22.Có thể lập được bao nhiêu biển số xe với hai chữ cái đầu thuộc
tập {A, B, C, D, E}, tiếp theo là một số nguyên dương gồm năm chữ số

Số tổ hợp chập k (0 ≤ k ≤ n) của n phần tử được kí hiệu là C
k
n
và
được tính theo công thức
C
k
n
=
n(n −1)(n − k + 1)
k!
=
n!
k!(n −k)!
Sau đây ta xét một số bài toán minh họa:
Bài 23. Có bao nhiêu cách chia một lớp 40 học sinh thành 4 tổ, sao cho
mỗi tổ có đúng 10 học sinh.
Bài giải
Đầu tiên lập tổ 1 bằng cách chọn tùy ý 10 học sinh trong 40 học sinh của
lớp. Số cách chọn bằng số các tổ hợp chập 10 của 40, bằng
C
10
40
=
40!
10!30!
Tổ 2 có thể chọn 10 em tùy ý trong 30 em còn lại, số cách chọn bằng số
các tổ hợp chập 10 của 30, bằng
C
10

40!
(10!)
4
Bài 24. Một lớp học sinh có 40 em gồm 25 nam và 15 nữ. Giáo viên chủ
nhiệm định chọn một ban cán sự gồm 4 người. Hỏi có bao nhiêu cách
chọn nếu:
a) Số nam hoặc nữ trong ban là tùy ý?
b) Ban cán sự có 1 nam và 3 nữ ?
c) Ban cán sự có 2 nam và 2 nữ?
d) Ban cán sự có ít nhất 1 nam?
e) Ban cán sự có ít nhất 1 nam và một nữ?
14
Bài giải
a) Nếu số nam (nữ) là tùy ý, thì số cách chọn là số các tổ hợp chập 4 của
40 phần tử, bằng
C
4
40
=
40!
4!36!
= 91390 (cách)
b) Nếu trong ban cán sự có 1 nam và 3 nữ, thì số cách chọn 1 nam trong
25 nam là C
1
25
còn số cách chọn 3 nữ trong số 15 nữ là C
3
15
. Vậy số cách

1
25
.C
3
15
cách chọn;
2 nam và 2 nữ có C
2
25
.C
2
15
cách chọn;
3 nam và 1 nữ có C
3
25
.C
1
15
cách chọn;
4 nam và không nữ có C
4
25
cách chọn;
Vậy có C
1
25
.C
3
15

+ C
4
25
) = 77375 (cách)
Bài 25. Cho 6 điểm trên mặt phẳng sao cho không có 3 điểm nào thẳng
hàng. Hỏi có bao nhiêu đường thẳng đi qua 2 điểm trong 6 điểm này.
Bài giải
Theo giả thiết, từ một cặp 2 điểm xác định duy nhất một đường thẳng.
Vậy số đường thẳng bằng số cặp 2 điểm từ 6 điểm: n = C
2
6
= 15.
Bài 26. Từ 7 học sinh nam, 4 học sinh nữ. Hỏi có bao nhiêu cách chọn
một đội bóng chuyền cho 6 em sao cho trong đội có ít nhất 2 nữ.
Bài giải
Ký hiệu S
2
là tập các đội bóng có 2 nữ, S
3
là tập các đội bóng có 3 nữ,
S
4
là các đội bóng có 4 nữ.
Có C
2
4
cách chọn 2 nữ, C
4
7
cách chọn 4 nam. Suy ra, |S

4
| = 6.35 + 4.35 + 1.21 = 371
Bài 27. Có 12 nam, 15 nữ. Hỏi có bao nhiêu cách chọn ra 4 cặp nhảy
(mỗi cặp 1 nam, một nữ).
Bài giải
Mỗi cách chọn tương ứng với cách chọn ra 4 em nam xếp thành một hàng,
4 em nữ xếp thành một hàng. (Khi đó 2 em đứng thẳng hàng tạo thành
một cặp nhảy). Vậy số cách chọn bằng
n = C
4
12
.C
4
15
.4!.
Chú ý: Lấy 1 em nam (trong 4 em) có 4 cách chọn 1 em nữ. Lấy 1 em
nam trong 3 em còn lại có 3 cách chọn 1 em nữ trong 3 nữ còn lại. Lấy 1
em nam trong 2 em còn lại có 2 cách chọn 1 em nữ. Vậy số cách xếp cặp
cho 4 nam, 4 nữ bằng 4!
Tổ hợp lặp
Định nghĩa. Cho tập hợp A = {a
1
, a
2
, , a
n
}. Một tổ hợp lặp chập m
(m không nhất thiết phải nhỏ hơn n) của n phần tử thuộc A là một bộ
gồm m phần tử mà mỗi phần tử này là một trong những phần tử của A.
Ta sử dụng C

Bài 29.Tiền giấy của Ngân hàng quốc gia Việt nam ban hành phổ
biến trên thị trường có 10 loại 200đ, 500đ, 1000đ, 2000đ, 5000đ, 10000đ,
20000đ, 50000đ, 100000đ, 500000đ. Hãy xác định số bộ khác nhau gồm
15 tờ giấy bạc của Ngân hàng quốc gia Việt Nam.
Bài giải
16
Mỗi bộ gồm 15 tờ giấy bạc thuộc không quá 10 loại, nên có những tờ
giấy bạc cùng loại. Mặt khác trong mỗi bộ không quan tâm đến thứ tự
sắp xếp, nên số bộ giấy bạc khác nhau gồm 15 tờ sẽ bằng số tổ hợp lặp
chập 15 của 10 (loại), bằng
C
15
10
= C
15
10+15−1
= C
15
24
=
24!
15!9!
= 1307504
1.2 Phép tương ứng 1- 1
Xét hai tập hữu hạn A, B. Khi đó có tồn tại một song ánh (phép tương
ứng 1- 1) f : A → B khi và chỉ khi |A|= |B|. Như vậy, nếu tồn tại song
ánh f thì ta có thể thay thế việc đếm các phần tử của tập A bởi các phần
tử của tập B. trong các bài toán cụ thể thì song ánh f có thể được mô tả
như các kỹ năng giải cụ thể rất hiệu quả như sau:
1.Mô tả phần tử đếm: Thay thế phần tử đếm bởi sự mô tả cụ thể

5
cách chọn 2 vị trí để đặt chữ số chẵn
(vì số 0 đứng đầu). Vậy số bộ có số 0 đứng đầu là C
2
5
.5
5
.
17
Đáp số: d = C
3
6
.5
6
− C
2
5
.5
5
= 281250.
Bài 2. Cho tập A = {1, 2, 3}. Có bao nhiêu số nguyên dương gồm 10
chữ số lập được từ tập A, trong đó chữ số 3 xuất hiện đúng 2 lần. Hỏi có
bao nhiêu số trong các số này chia hết cho 9.
Bài giải
Có C
2
10
cách chọn 2 vị trí trong 10 vị trí để đặt số 3. Tại mỗi vị trí trong 8
vị trí còn lại có 2 cách sắp xếp (1 hoặc 2). Vậy đáp số d = C
2

2!.2!
= 6
3. Có 1 cặp chữ số giống nhau, còn 2 chữ số còn lại là phân biệt. Có 2
cách chọn một cặp 2 chữ số giống nhau và C
2
3
cách chọn 2 chữ số phân
biệt từ 3 chữ số phân biệt còn lại. Suy ra d
3
= 2.C
2
3
.P (2, 1, 1) = 72
Đáp số: 24+6+72 =102.
Bài 4. Cho tập A = {1, 2, 3, 4, 5}. Hỏi có bao nhiêu số gồm 6 chữ số
của A trong đó có 3 số a, 2 số b và 1 số c, với a, b, c là các số đôi một
phâm biệt thuộc A.
Bài giải.
Có C
3
5
cách lấy 3 số phân biệt đôi một a, b, c của tập A. Có 3 cách chỉ
định số nào xuất hiện 3 lần, số nào xuất hiện 2 lần sẽ có 2 cách chỉ định,
hiển nhiên số còn lại xuất hiện 1 lần và ta có đáp số d = C
3
5
.3.2.
6!
3!2!
.

.5.5
- Trường hợp 2 (3 số giống nhau là 3 số 0).
Có C
2
4
cách chọn 2 vị trí để viết thêm 2 số 0, có 5 cách chọn a ∈ A, a = 0,
5 cách chọn c ∈ A, c = 0 để đặt vào 2 vị trí còn lại, Vậy số bộ của trường
hợp này bằng d
3
= C
2
4
.5.5
Đáp số: d = d
1
− (d
2
+ d
3
) = 1250.
Bài 6. Tìm số các số nguyên có 4 chữ số được cấu tạo bởi đúng 2 chữ số
phân biệt.
Bài giải.
Có C
2
10
= 45 cách chọn 2 chữ số từ 10 chữ số. Tử 2 chữ số đó chúng ta có
thể tạo thành 2
4
số có 4 chữ số (tuy nhiên chúng ta phải trừ đi 2 trường

= 630 − 63 = 567.
1.2.2 Mã hóa 0, 1 phần tử đếm
Khi bài toán mà mỗi phần tử đếm là một quy tắc, một cách chọn,
một cách phân chia, một trò chơi thì người ta thường mô tả phần tử đếm
bằng một bộ số 0, 1 để phép đếm trở nên đơn giản hơn.
Sau đây ta xét một số bài toán minh họa:
Bài 7. Ở một cửa hiệu có 12 loại bưu thiếp, hỏi có bao nhiêu cách mua
8 bưu thiếp để gửi đến các địa chỉ khác nhau.
Bài giải
19
Ta viết n
1
số 1 nếu n
1
số thiếp loại 1 được mua (n
1
= 0 ta không viết số
nào), sau đó viết tiếp số 0.
Ta lại viết n
2
số 1 nếu n
2
số thiếp loại 2 được mua, sau đó viết tiếp
số 0.
Cứ tiếp tục như vậy, ta viết n
12
số 1 nếu n
12
số thiếp loại 12 được
mua.

Tiếp tục như vậy đến bước cuối cùng là viết x
6
số 1 nếu phát x
6
quả
bóng cho học sinh thứ 6.
Vậy số cách phát bằng số bộ gồm x
1
+ x
2
+ + x
6
= 9 số 1 và 5 số
0. Số bộ này bằng: P(9, 5) =
14!
9!5!
= C
5
14
Bài 9.Tìm số bộ 3 số (x, y, z) nguyên dương thỏa mãn đẳng thức x +
y + z = 1000.
Bài giải
Đặt u = x−1, v = y−1, t = z−1 ta thu được bài toán tương đương "Tìm
số bộ (u, v, t) nguyên không âm thỏa mãn đẳng thức u + v + t = 997".
Mỗi bộ số (u, v, t) tương ứng với một bộ gồm toàn số 0, 1 sau đây:
(11 1
  
u
, 0, 11 1
  

2, sau đó viết số 0.
Cứ tiếp tục vậy viết x
6
số 1 nếu phát x
6
bóng cho học sinh thứ 6.
Ta có x
1
+ x
2
+ + x
12
= 15.
Vậy một cách phát bằng một bộ gồm 15 số 1 và 5 số 0 theo một thứ
tự nào đó. Để có một bộ như vậy ta cần chọn 5 vị trí trong 20 vị trí để
viết số 0, còn lại viết số 1.
Vậy số cách phát bằng n
1
= C
5
20
.
2) Ta phát cho mỗi em một quả bóng và sau đó phát 9 quả bóng cho
6 em theo cách trên và thu được số cách phát bằng n
2
= C
5
14
Bài 11.Có bao nhiêu cách chia 7 thùng nho, 5 thùng táo như nhau
cho 3 học sinh (Hai cách chia là khác nhau nếu có ít nhất một học sinh

7
.
Theo quy tắc nhân số cách phát này là: n = n
1
.n
2
= C
2
9
.C
2
7
.
Bài 12.Với n ∈ N cố định, Tìm số nghiện phương trình
x
1
+ x
2
+ + x
k
= n.
1. Trên tập các số nguyên không âm.
2. Trên tập các số nguyên dương.
Bài giải
1. Mỗi nghiệm (x
1
, x
2
, , x
k

− 1(i = 1, 2, , k) và mỗi bộ (x
1
, x
2
, , x
k
) tương ứng
1-1 với bộ (y
1
, y
2
, , y
k
) thỏa mãn y
1
+ y
2
+ + y
k
= n −k với y
i
không
âm.
Giải tương tự phần (1) ta có đáp số n
2
= C
n−k
n−k+k−1
= C
n−k

Đáp số n
1
= C
4
16
2. Ta lấy mỗi loại 2 gói, và mua tiếp 2 gói theo cách trên sẽ tương ứng
với một bộ 2 số 1 và 4 số 0.
Đáp số n
2
= C
2
6
.
Bài 14.Có bao nhiêu cách bỏ 12 đồng xu (như nhau) vào 7 phong bì
có đánh số sao cho mỗi phong bì có ít nhất 1 đồng xu.
Bài giải
Ta bỏ vào mỗi phong bì một đồng xu, năm đồng xu còn lại bỏ vào 7
phong bì theo quy tắc sau:
Nếu bỏ x
1
đồng xu vào phong bì thứ 1 ta viết x
1
số 1, sau đó ta viết số
0. Tương tự viết x
7
số 1 nếu bỏ x
7
đồng xu vào phong bì số 7. Mỗi cách
tương ứng với một bộ gồm 5 số 1 (x
1

cách bỏ phiếu bằng C
4
34
22
Bài 16. Có bao nhiêu cách bỏ 2 quả bóng trắng, 7 bóng đen vào 9 lỗ
khác nhau sao cho:
1. Không có lỗ nào trống.
2. Có một vài lỗ trống.
Bài giải
1. Có C
2
9
cách chọn 2 trong 9 lỗ để bỏ bóng trắng, còn lại bỏ bóng đen.
Suy ra n
1
= C
2
9
.
2. Viết x
1
số 1 nếu bỏ x
1
quả bóng trắng vào lỗ thứ 1, sau đó viết 0. Tương
tự đến khi viết x
9
số 1 nếu bỏ x
9
quả bóng trắng vào lỗ thứ 9. Vậy mỗi
cách bỏ bóng trắng tương ứng 1-1 với mỗi bộ 2 số 1 (x

.
Bài 17. Tìm số bộ (x
1
, x
2
, x
3
) nguyên không ân thỏa mãn x
1
+x
2
+x
3
≤
1000.
Bài giải.
Mỗi bộ (x
1
, x
2
, x
3
) thỏa mãn x
1
+ x
2
+ x
3
≤ 1000 tương ứng 1-1 với bộ
(x

  
x
2
, 0, 11 1
  
x
3
, 0, 11 1
  
x
4
)
gồm 1000 số 1 và 3 số 0. Số bộ này bằng P (1000, 3) =
1003!
1000!3!
.
Bài 18. Xét bất phương trình x
1
+ x
2
+ x
3
+ x
4
≤ 9
1. Tìm số nghiệm nguyên không âm.
2. Tìm số nghiệm nguyên dương.
Bài giải
1. Số nghiệm khi x
1

= 1 bằng C
3
4
.
Tiếp tục như vậy, khi x
1
+ x
2
+ x
3
+ x
4
= 0 bằng C
3
3
.
Đáp số:
n = C
3
3
+ C
3
4
+ C
3
5
+ + C
3
12
= C

+ + C
9
12
=
= C
8
12
+ C
9
12
= C
9
13
2. Đặt y
i
= x
i
− 1, ta thu được
y
1
+ y
2
+ y
3
+ y
4
≤ 5.
Suy ra:
n
2

8
= C
5
9
1.2.3 Phương pháp đánh số
Để kỹ năng đếm hiệu quả, chính xác hơn với các bài toán phức tạp
chúng ta xây dựng phương pháp đánh số như sau: Đánh số các vị trí để
sắp xếp các thành phần của phần tử đếm theo thứ tự khi đó mỗi cách
chọn vị trí tương ứng với một bộ số nguyên dương thỏa mãn một tính
chất cụ thể theo yêu cầu của bài toán đếm.
Sau đây ta xét một số bài toán minh họa:
Bài 19. Một tổ có 7 học sinh nam, 3 học sinh nữ. Hỏi có bao nhiêu cách
xếp tổ thành một hàng ngang mà không có 2 học sinh nữ nào ngồi cạnh
nhau.
Bài giải
Ta đánh số các vị trí từ 1 đến 10. 3 vị trí không kề nhau tương ứng với
các số a < b < c thỏa mãn tính chất sau 3 ≤ a + 2 < b + 1 < c ≤ 10.
Để xác định a, b, c ta cần chọn ra 3 số phân biệt trong 8 số từ 3 đến
10. Vậy có C
3
8
cách chọn ra 3 vị trí trong 10 vị trí để xếp các em nữ.
Vậy số cách xếp bằng n = C
3
8
.3!.7!
Bài 20. Có bao nhiêu cách xếp 7 nam, 3 nữ ngồi xung quanh một bàn
tròn 10 ghế sao cho không có 2 em nữ nào ngồi cạnh nhau.
Bài giải
Ta lấy một chiếc ghế bất kỳ và xếp tiếp theo một chiếc.

Ta cần 7 vị trí để xếp các chữ số cho một số. Đánh số thứ tự các vị trí
từ 1 đến 7. Ta chọn ra 2 vị trí để viết số 0 tương ứng với 2 số a, b thỏa
mãn tính chất 4 ≤ a + 2 < b ≤ 7. (ta có a ≥ 2 vì số 0 không được đứng
đầu). Vậy số cách chọn 2 vị trí bằng số cách chọn 2 số phân biệt trong 4
số từ 4 đến 7. Số cách chọn bằng C
2
4
và tại các vị trí này ta viết số 0.
Còn 5 vị trí còn lại có 5! cách xếp các số 1,2,3,4,5.
Đáp số: n = C
2
4
.5!
Bài 22.Xét đa giác đều n đỉnh (n ≥ 12), hỏi có bao nhiêu tam giác
có 3 cạnh là 3 đường chéo. Hỏi có bao nhiêu tứ giác có 2 cạnh là cạnh đa
giác, 2 cạnh còn lại là 2 đường chéo.
Bài giải
- Xuất phát từ 1 đỉnh bất kỳ ta đánh số các đỉnh theo thứ tự A
1
, A
2
, , A
n
.
Ta cần chọn thêm 2 đỉnh ứng với các số a, b thỏa mãn 4 ≤ a + 1 < b ≤
n −1.
Suy ra số cách chọn 2 đỉnh bằng số cách lấy ra 2 số phân biệt từ n − 4
số (từ 4 đến n −1).
Suy ra số tam giác đỉnh A
1