ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TỐN

KHĨA LUẬN TỐT NGHIỆP
Đề tài: LÝ THUYẾT TỔ HỢP TRONG CHƯƠNG

TRÌNH TỐN BẬC TRUNG HỌC

GIẢNG VIÊN HƯỚNG DẪN
SINH VIÊN THỰC HIỆN
CHUYÊN NGÀNH
LỚP
NIÊN KHĨA

: TS. Cao Văn Ni
: Nguyễn Thị Bảo Nhung
: Cử nhân Toán ứng dụng
: 11CTUD2
: 2011-2015

ĐÀ NẴNG, NĂM 2015
1


MỤC LỤC
LỜI CẢM ƠN ............................................................................................................3
MỞ ĐẦU ....................................................................................................................4
1. Lý do chọn đề tài ..............................................................................................4
2. Mục tiêu nghiên cứu của đề tài.........................................................................4
3. Đối tượng và phạm vi nghiêm cứu ...................................................................4

4. Phương pháp nghiên cứu ..................................................................................4
5. Bố cục khóa luận ..............................................................................................5
CHƯƠNG 1 ...............................................................................................................6
CÁC PHƯƠNG PHÁP ĐẾM CƠ BẢN ....................................................................6
1.1. NGUYÊN LÝ CỘNG VÀ NGUYÊN LÝ NHÂN ...........................................6
1.1.1. Nguyên lý cộng ..........................................................................................6
1.1.2. Nguyên lý nhân ..........................................................................................6
1.2. TỔ HỢP ............................................................................................................7
1.3. CÁC TÍNH CHẤT CỦA HỆ SỐ TỔ HỢP (HAY HỆ SỐ NHỊ THỨC) .........9
1.4. SONG ÁNH ....................................................................................................14
1.5. PHÉP ĐỆ QUY ..............................................................................................16
1.6. CÁC BÀI TOÁN ỨNG DỤNG .....................................................................19
CHƯƠNG 2 .............................................................................................................23
CÁC PHƯƠNG PHÁP ĐẾM DÙNG NGUYÊN LÝ BAO HÀM – LOẠI TRỪ,
NGUYÊN LÝ FUBINI VÀ HÀM SINH ................................................................23
2.1. NGUYÊN LÝ BAO HÀM – LOẠI TRỪ ......................................................23
2.2. PHÉP TÍNH THEO HAI CÁCH: NGUYÊN LÝ FUBINI ............................25
2.3. HÀM SINH.....................................................................................................28
2.4. CÁC BÀI TOÁN ỨNG DỤNG .....................................................................32
KẾT LUẬN ..............................................................................................................35
TÀI LIỆU THAM KHẢO .......................................................................................36

2


LỜI CẢM ƠN
Lời đầu tiên em xin tỏ lòng biết ơn sâu sắc đến các thầy cô giáo đã tận tụy,
nhiệt tình truyền đạt kiến thức trong những năm em học tập tại trường Đại học Sư
phạm Đà Nẵng. Vốn kiến thức được tiếp thu trong q trình học khơng chỉ là nền
tảng cho q trình nghiên cứu khóa luận mà cịn là hành trang q báo để em bước

vào đời một cách vững chắc và tự tin.
Em xin chân thành cảm ơn thầy Cao Văn Nuôi đã trực tiếp hướng dẫn, giúp
đỡ em trong suốt quá trình triển khai, nghiên cứu và hoàn thành đề tài: “Lý thuyết tổ
hợp trong chương trình tốn bậc trung học”.
Cuối cùng em xin chúc tồn các thầy cơ giáo thật nhiều sức khỏe, nhiệt huyết
và thành cơng trong sự nghiệp cao q.
Một lần nữa em xin chân thành cảm ơn!

Sinh viên thực hiện

Nguyễn Thị Bảo Nhung

3


MỞ ĐẦU
Lý do chọn đề tài
Tư duy về tổ hợp ra đời rất sớm. Ở Trung Quốc, vào thời nhà Chu người
ta đã biết đến những hình vng thần bí. Nhà triết học cổ Hy Lạp Kxenokrat,
sống ở thế kỷ thứ 4 trước cơng ngun đã biết cách tính số các từ khác nhau lập
từ một bảng cái cho trước. Nhà tốn học Pithagore và các học trị của ơng đã
phát hện ra nhiều tính chất kỳ lạ của các số. Một kết quả nổi tiếng của trường
phái này là kết quả mà ngày nay chúng ta gọi là định lý Pithagore.
1.

Tuy nhiên, một thời gian dài sau đó, tổ hợp chỉ phát triển một cách riêng
lẻ, chưa hình thành được hệ thống lý luận cơ sở khoa học, phương pháp nghiên
cứu đặc thù. Và tổ hợp chỉ thực sự trở thành một ngành toán học rời rạc vào
đầu thế kỷ 17 bằng một loạt các cơng trình nghiên cứu nghiêm túc của nhà toán
học xuất sắc như Pascal, Fermat, Leibnitz, Euler, … Mặc dù vậy, tổ hợp vẫn là

lĩnh vực mờ nhạt và ít được chú ý tới trong khoảng thời gian hơn hai thế kỷ.
Trong những năm gần đây lý thuyết tổ hợp đã phát triển một cách mạnh
mẽ và đóng góp váo sự phát triển tốn học rời rạc, tối ưu rời rạc cũng như trong
hình học tổ hợp. Tơi cảm thấy thích thú phần tốn học này với những ứng dụng
cụ thể của nó nên chọn đề tài tốt nghiệp của mình là: “Lý thuyết tổ hợp trong
chương trình tốn bậc trung học”.
2.
Mục tiêu nghiên cứu của đề tài
Nghiên cứu đề tài này, tôi muốn cung cấp thêm tài liệu về lý thuyết tổ hợp xác
suất và hy vọng rằng khóa luận có thể được sử dụng như một tài liệu tham khảo
bổ ích cho học sinh và những người quan tâm đến xác suất.
3.
Đối tượng và phạm vi nghiêm cứu
Đối tượng nghiên cứu: nghiên cứu các định nghĩa, tính chất, chứng minh tính
chất và giải một số bài toán ứng dụng.
Phạm vi nghiên cứu: nghiên cứu từ các tài liệu, các giáo trình về tổ hợp của các
tác giả liên quan.
4.
Phương pháp nghiên cứu
Tham khảo một số tài liệu sách về tổ hợp nhằm làm sáng tỏ một số vấn đề trong
tính chất và định nghĩa nhằm làm rõ để đi chứng minh.
4


5.
Bố cục khóa luận
Chương I: Các phương pháp đếm cơ bản
1.1
Nguyên lý cộng và nguyên lý nhân
1.2

Tổ hợp
1.3
Các tính chất của hệ số tổ hợp
1.4
Song ánh
1.5
Phép đệ quy
1.6
Các bài toán ứng dụng
Chương II: Các phương pháp đếm dùng nguyên lý bao hàm – loại trừ, nguyên
lý Fubini và hàm sinh
2.1
2.2
2.3
2.4

Nguyên lý bao hàm – loại trừ
Phép tính theo hai cách: nguyên lý Fubini
Hàm sinh
Các bài toán ứng dụng

5


CHƯƠNG 1
CÁC PHƯƠNG PHÁP ĐẾM CƠ BẢN

1.1.

NGUYÊN LÝ CỘNG VÀ NGUN LÝ NHÂN


1.1.1. Ngun lý cộng
Giả sử có 𝑘 cơng việc 𝑇1 , 𝑇2 , … , 𝑇𝑘 . Các cơng việc này có thể làm tương
ứng bằng 𝑛1 , 𝑛2 , … , 𝑛𝑘 cách và giả sử không có hai việc nào có thể làm đồng
thời, khi đó số cách làm một trong 𝑘 việc đó là 𝑛1 + 𝑛2 + ⋯ + 𝑛𝑘 .
Nguyên lý cộng còn được phát biểu dưới dạng ngôn ngữ tập hợp như
sau: Nếu 𝐴1 , 𝐴2 , … , 𝐴𝑘 là các tập hữu hạn đôi một rời nhau, hay 𝐴𝑖 ∩ 𝐴𝑗 =
∅ (𝑖 ≠ 𝑗) thì |𝐴1 ∪ 𝐴2 ∪ … ∪ 𝐴𝑘 | = |𝐴1 | + |𝐴2 | + ⋯ + |𝐴𝑘 |, ở đây |𝐴𝑖 | là
số các phần tử của tập 𝐴𝑖 .
Ví dụ 1.1.1. Giả sử cần chọn hoặc một học sinh nam hoặc một học sinh
nữ tham gia cuộc họp. Hỏi có bao nhiêu cách để chọn nếu có 35 học sinh nam
và 42 học sinh nữ?
Giải:
Gọi cách chọn thứ nhất là học một học sinh nam từ tập 35 học sinh nam,
ta có 35 cách.
Gọi cách chọn thứ hai là chọn một học sinh nữ từ tập 42 học sinh nữ, ta
có 42 cách.
Vì tập học sinh nam và tập học sinh nữ là rời nhau nên theo nguyên lý
cộng, ta có số cách chọn nhân sự là 35 + 42 = 77 cách.
1.1.2. Nguyên lý nhân
Giả sử một nhiệm vụ nào đó được tách ra thành 𝑘 việc 𝑇1 , 𝑇2 , … , 𝑇𝑘 .
Nếu việc 𝑇𝑖 có thể làm bằng 𝑛𝑖 cách, sau khi các việc 𝑇1 , 𝑇2 , … , 𝑇𝑖−𝑘 đã được
làm (1≤ 𝑖 ≤ 𝑘) thì có 𝑛1 . 𝑛2 . … . 𝑛𝑘 cách thực hiện nhiệm vụ đã cho.

6


Quy tắc nhân cịn được phát biểu dưới dạng ngơn ngữ tập hợp như sau:
Nếu 𝐴1 , 𝐴2 , … , 𝐴𝑘 là các tập hữu hạn bất kỳ và nếu 𝐴1 × 𝐴2 ×. … × 𝐴𝑘 là tích
Descartees của các tập đó thì |𝐴1 × 𝐴2 × … × 𝐴𝑘 | = |𝐴1 ||𝐴2 | … |𝐴𝑘 |

Ví dụ 1.1.2. Có bao nhiêu xâu nhị phân có độ dài 8?
Giải:
Một xâu nhị phân có độ dài 8 gồm 8 bit, mỗi bit có hai cách chọn (hoặc
giá trị 0 hoặc giá trị 1). Theo quy tắc nhân ta có: 2.2.2.2.2.2.2.2 = 256 xâu bit
nhị phân có độ dài 8.

1.2.

TỔ HỢP

Chúng ta thường gặp một số bài toán yêu cầu phải đếm số tổ hợp, tức
là đếm số tập hợp các đối tượng không được sắp xếp thứ tự.
Định lý 1.2.1. Cho 𝑛 và 𝑘 là những số nguyên, với 𝑛 ≥ 𝑘 Số tổ hợp của
việc mỗi một lần lấy 𝑘 phần tử từ 𝑛 phần tử là

C𝑛k =

n(n-1)…(n-k+1)
n!
=
k!
k!(n-k)!

𝑛
Ký hiệu: 𝐶𝑛𝑘 hoặc C(n; k) hay ( )
𝑘
Chứng minh:
𝑛!

Có 𝑃𝑛𝑘 = (𝑛−𝑘)! cách chọn đối tượng 𝑘 theo thứ tự.

Có 𝑘! cách để sắp xếp phần tử được chọn, có nghĩa là, có 𝑘! cách để
chọn tổ hợp của 𝑘 phần tử giống nhau. Vì vậy mỗi tổ hợp được tính 𝑘! lần trong
𝑃𝑛𝑘 .
Do đó có

𝑛!
(𝑛−𝑘)!𝑘!

tổ hợp.

Trong một số tình huống, thứ tự của các phần tử bằng cách nào đó được
xác định trước, thì thứ tự của các đối tượng được chọn khơng cịn quan trọng.
Ví dụ 1.2.1. Một nhóm bạn học gồm có 7 bạn nam và 6 bạn nữ. Vào
cuối năm, cả nhóm quyết định chụp ảnh làm kỷ niệm. Cả nhóm muốn đứng
thành một hàng, những bạn nam thì đứng theo thứ tự giảm dần theo chiều cao
của họ (giả định rằng họ có chiều cao khác nhau) từ trái sang phải và những
7


bạn nữ thì đứng theo thứ tự tăng dần theo chiều cao của họ (giả định rằng họ
có chiều cao khác nhau) từ trái sang phải. Những bạn nam không cần phải đứng
cùng nhau, và các bạn nữ không cần phải đứng cùng nhau. Có bao nhiêu cách
để thực hiện công việc này?
Giải:
Xét 13 khoảng trống trong một hàng 𝑠1 , 𝑠2 , … , 𝑠13
Nếu 𝑠𝑖1 , 𝑠𝑖2 , … , 𝑠𝑖7 được chọn cho vị trí của các bạn nam, thì các bạn
nam được đứng ở vị trí này theo chiều cao của họ. Các bạn nữ sau đó cũng có
một cách duy nhất để đứng ở vị trí của mình. Do đó câu trả lời là
7
𝐶13

=

13!
7!6!

= 1716

Hệ quả 1.2.2. Cho 𝑛, 𝑘1 , 𝑘2 , … , 𝑘𝑚 là những số nguyên, với 𝑛 ≥ 𝑘1 +
𝑘2 + ⋯ + 𝑘𝑚 . Số tổ hợp của việc một lần lấy 𝑘1 , 𝑘2 , … , 𝑘𝑚 phần tử từ 𝑛 phần
tử, theo thứ tự là
𝑘 𝑘2 …𝑘𝑚 𝑘𝑚+1

𝐶𝑛 1

=

𝑛!
𝑘1 !𝑘2 !…𝑘𝑚 !𝑘𝑚+1 !

Với 𝑘𝑚+1 = 𝑛 − (𝑘1 + 𝑘2 + ⋯ + 𝑘𝑚 )
Chứng minh:
𝑘

Từ định lý 1.2.1. có 𝐶𝑛 1 cách để lấy 𝑘1 phần tử, có 𝑛 − 𝑘1 cách để lấy
các phần tử còn lại.
𝑘

2
Sử dụng định lý 1.2.1 một lần nữa, có 𝐶𝑛−𝑘
cách để lấy 𝑘2 phần tử.

1

Tương tự như vậy, chúng ta kết luận rằng số tổ hợp của một việc một
lần lấy 𝑘1 , 𝑘2 , … , 𝑘𝑚 phần tử từ 𝑛 phần tử, theo thứ tự là
𝑘

𝑘

𝑘

𝑘

𝑚
2
𝐶𝑛 1 𝐶𝑛−𝑘
𝐶 3
… 𝐶𝑛−𝑘
1 𝑛−𝑘1 −𝑘2
1 −𝑘2 −⋯−𝑘𝑚

=
=

𝑛!
𝑘1 !(𝑛−𝑘1

.
)!

(𝑛−𝑘1 )!

𝑘2 !(𝑛−𝑘1 −𝑘2

.
)!

(𝑛−𝑘1 −𝑘2 )!
𝑘3 !(𝑛−𝑘1 −𝑘2 −𝑘3

…
)!

(𝑛−𝑘1 −𝑘2 −⋯𝑘𝑚−1 )!
𝑘𝑚 !(𝑛−𝑘1 −𝑘2 −⋯−𝑘𝑚 )!

𝑛!
𝑘1 !𝑘2 !…𝑘𝑚 !𝑘𝑚+1 !

Ví dụ 1.2.2. Khoa toán tổ chức một cuộc họp. Sau 23 thành viên đàm
thoại, họ quyết định chia ra thành 8 nhóm, trong đó 5 nhóm có 3 thành viên và
8


2 nhóm có 4 thành viên để tiếp tục thảo luận. Hỏi có bao nhiêu cách để chia
được?
Giải:
23!

3,3,3,3,3,4,4
Ta có 𝐶23
= (3!)5(4!)2 cách chia nhóm.


1.3.

CÁC TÍNH CHẤT CỦA HỆ SỐ TỔ HỢP (HAY HỆ SỐ
NHỊ THỨC)

Cho 𝑛 là số nguyên dương. Nếu chúng ta sử dụng hai biến số đa thức
(𝑥 + 𝑦)𝑛 như:
(𝑥 + 𝑦)𝑛 = 𝑎0 𝑥 𝑛 + 𝑎1 𝑥 𝑛−1 𝑦 + 𝑎2 𝑥 𝑛−2 𝑦 2 + ⋯ + 𝑎𝑛−1 𝑥𝑦 𝑛−1 + 𝑎𝑛 𝑦 𝑛
với 0 ≤ 𝑘 ≤ 𝑛, 𝑎𝑘 là hệ số tổ hợp.
1
1

1

1

2

1

1

3

3

1

1


4

6

4

1

1

5

10

10

5

1

…

…

…

…

…


…

…

Định lý 1.3.1. Cho 𝑛 là số nguyên dương. Khi đó:
(𝑥 + 𝑦)𝑛 = 𝐶𝑛0 𝑥 𝑛 + 𝐶𝑛1 𝑥 𝑛−1 𝑦 + 𝐶𝑛2 𝑥 𝑛−2 𝑦 2 + ⋯ + 𝐶𝑛𝑛 𝑦 𝑛
Quy ước: 𝐶𝑛0 = 𝐶𝑛𝑛 =

𝑛!
𝑛!0!

=1

Hệ số tổ hợp cũng là những số hạng trong tam giác Pascal. Chính xác
hơn cho 𝑛 ≥ 0
𝐶𝑛0 , 𝐶𝑛1 , 𝐶𝑛2 , … , 𝐶𝑛𝑛−1 , 𝐶𝑛𝑛
là hạng thứ 𝑛 của tam giác.
Ví dụ 1.3.1. Bảng số xe gồm 8 chữ số, nó được gọi là chẵn nếu số các
số 0 trong nó là chẵn. Có bao nhiêu bảng số xe như vậy?
9


Giải:
Cho 0 ≤ 𝑘 ≤ 4, nếu có 2𝑘 các số 0 trong đó, thì có 8 − 2𝑘 chữ số khác
0, mỗi số có 9 cách chọn.
Có 𝐶82𝑘 cách để chọn 2𝑘 vị trí của những số 0, và 𝐶82𝑘 98−2𝑘 bảng số có
2𝑘 số 0.
Do đó câu trả lời là: 98 + 𝐶82 96 + 𝐶84 94 + 𝐶86 92 + 𝐶88
Định lý 1.3.2. Cho 𝑛 và 𝑘 là số nguyên dương với 𝑛 ≥ 𝑘, ta có các tính

chất của hệ số tổ hợp sau:
(1) 𝐶𝑛𝑘 = 𝐶𝑛𝑛−𝑘
𝑘+1
𝑘
(2) 𝐶𝑛𝑘+1 = 𝐶𝑛−1
+ 𝐶𝑛−1
𝑛−1

(3)

𝐶𝑛0

<

𝐶𝑛1

<

𝐶𝑛2

<⋯<

⌈
⌉
𝐶𝑛 2

𝑛

=


⌊ ⌋
𝐶𝑛2

𝑘−1
(4) 𝑘𝐶𝑛𝑘 = 𝑛𝐶𝑛−1

(5) 𝑘𝐶𝑛𝑘 = (𝑛 − 𝑘 + 1)𝐶𝑛𝑘−1
𝑘
𝑛+1
1
2
(6) 𝐶𝑛0 + 𝐶𝑛+1
+ 𝐶𝑛+2
+ ⋯ + 𝐶𝑛+𝑘
= 𝐶𝑛+𝑘+1
𝑛
𝑛+1
𝑛
𝑛
(7) 𝐶𝑛𝑛 + 𝐶𝑛+1
+ 𝐶𝑛+2
+ ⋯ + 𝐶𝑛+𝑘
= 𝐶𝑛+𝑘+1

(8) 𝐶𝑛0 + 𝐶𝑛1 + ⋯ + 𝐶𝑛𝑛 = 2𝑛
(9) 𝐶𝑛0 − 𝐶𝑛1 + 𝐶𝑛2 − ⋯ + (−1)𝑛 𝐶𝑛𝑛 = 0
(10) 𝐶𝑛1 + 2𝐶𝑛2 + 3𝐶𝑛3 + ⋯ + 𝑛𝐶𝑛𝑛 = 𝑛2𝑛−1
(11) 𝐶𝑛𝑘 chia hết cho 𝑛 nếu 𝑛 là số nguyên tố và 1 ≤ 𝑘 ≤ 𝑛 − 1
Chứng minh:
(1)


𝑛!

𝐶𝑛𝑛−𝑘 = (𝑛−𝑘)!(𝑛−𝑛+𝑘)! =

𝑛!
𝑘!(𝑛−𝑘)!

= 𝐶𝑛𝑘
10


(2)

(𝑛−1)!

(𝑛−1)!

𝑘+1
𝑘
𝐶𝑛−1
+ 𝐶𝑛−1
= (𝑘+1)!(𝑛−𝑘−2)! +

=

𝑘!(𝑛−𝑘−1)!

(𝑛−1)!(𝑛−𝑘−1)+(𝑛−1)!(𝑘+1)
(𝑘+1)!(𝑛−𝑘−1)!

𝑛!

= (𝑘+1)!(𝑛−𝑘−1)! = 𝐶𝑛𝑘+1
(3)

Nếu 𝑛 chẵn, ⌈
Nếu 𝑛 lẻ ⌈

Cho 0 ≤ 𝑘 ≤ ⌈

𝑛−1
2
𝐶𝑛𝑘

Do đó

𝐶𝑛𝑘+1

𝑛−1

𝑛

2

2

⌉=

𝑛−1


𝑛−1

2

2

⌉=

⌉ − 1, 2𝑘 ≤ 𝑛 − 2 hoặc 𝑘 + 1 ≤ 𝑛 − 𝑘 − 1.
=

(𝑘+1)!(𝑛−𝑘−1)!
𝑘!(𝑛−𝑘)!

=

𝑘+1
𝑛−𝑘

<1

Từ (1) ta có:
𝐶𝑛0 < 𝐶𝑛1 < ⋯ < 𝐶𝑛𝑚 = 𝐶𝑛𝑚+1 > 𝐶𝑛𝑚+2 > ⋯ > 𝐶𝑛𝑛
nếu 𝑛 lẻ và 𝑛 = 2𝑚 + 1 và
𝐶𝑛0 < 𝐶𝑛1 < ⋯ < 𝐶𝑛𝑚 > 𝐶𝑛𝑚+1 > ⋯ > 𝐶𝑛𝑛
nếu 𝑛 chẵn và 𝑛 = 2𝑚
𝑘.𝑛!

𝑛(𝑛−1)!


𝑘−1
= (𝑘−1)![(𝑛−1)−(𝑘−1)]! = 𝑛𝐶𝑛−1

(4)

𝑘𝐶𝑛𝑘 =

(5)

𝑘𝐶𝑛𝑘 =

(6)

0
Chú ý rằng 𝐶𝑛0 = 𝐶𝑛+1
. Kết quả này có được bằng cách sử dụng

𝑘!(𝑛−𝑘)!
𝑘.𝑛!
𝑘!(𝑛−𝑘)!

(𝑛−𝑘+1)𝑛!

= (𝑘−1)!(𝑛−𝑘+1)! = (𝑛 − 𝑘 + 1)𝐶𝑛𝑘−1

tính chất (2) nhiều lần.
(7) Kết quả này có được từ việc sử dụng (1) trong mỗi thành phần
của (6).
(8) Đặt 𝑥 = 𝑦 = 1 trong khai triển của (𝑥 + 𝑦)𝑛 cho kết quả cần
chứng minh.

(9) Đặt 𝑥 = 1 và 𝑦 = −1 trong khai triển của (𝑥 + 𝑦)𝑛 cho kết
quả cần chứng minh.
(10) Từ (4) và (8) ta có:
11


𝑘−1
𝑘
𝑛−1
∑𝑛𝑘=1 𝑘𝐶𝑛𝑘 = 𝑛 ∑𝑛𝑘=1 𝐶𝑛−1
= 𝑛 ∑𝑛−1
𝑘=0 𝐶𝑛−1 = 𝑛2

(11) Lưu ý rằng 𝐶𝑛𝑘 là một số nguyên. Cũng lưu ý rằng 𝑛 chia hết cho
𝑛!, tử số của 𝐶𝑛𝑘 . Nếu 𝑛 là số nguyên tố, 𝑛 là nguyên tố cùng nhau tới 𝑘! (𝑛 −
𝑘)!. Do đó 𝐶𝑛𝑘 chia hết cho 𝑛.

Hệ số tổ hợp 𝐶𝑛𝑘 có một ý nghĩa tổ hợp nếu 𝑛 và 𝑘 là các số nguyên với
0 < 𝑘 ≤ 𝑛. Trong định lý 1.3.1, ta mở rộng định nghĩa tới 𝑘 = 0. Và quy ước
𝐶00 = 1. Nếu 0 ≤ 𝑛 < 𝑘 hay 𝑘 < 0 ≤ 𝑛, ta không thể lấy 𝑘 phần tử từ 𝑛 phần
tử, vì vậy quy ước 𝐶𝑛𝑘 = 0.
0
𝐶11

Ví dụ 1.3.2. Tính

1

1
𝐶11


+

2

+

2
𝐶11

3

+⋯+

11
𝐶11

12

Giải:
Từ định lý 1.3.2 (4), cho 0 ≤ 𝑘 ≤ 11,
12

𝑘
𝐶11
𝑘+1

𝑘+1
𝐶12


=

𝑘
𝐶11

hay

𝑘+1

=

𝑘+1
𝐶12

12

Do đó tổng cần tính là:
1
12

𝑘+1
∑11
𝑘=0 𝐶12 =

1

1

𝑘
0

12
(∑12
𝑘=0 𝐶12 − 𝐶12 ) = 12 (2 − 1)
12

từ định lý 1.3.2 (8)
Ví dụ 1.3.3. Cho 𝑛 là số nguyên dương, chứng minh
∑𝑛𝑖=0

1
𝐶𝑛𝑖

=

𝑛+1

2𝑖

2

𝑖

∑𝑛+1
𝑖=1
𝑛+1

Giải:
Cho 𝑆𝑛 =

1

𝑛+1

∑𝑛𝑖=0

1
𝐶𝑛𝑖

=

1
𝑛+1

∑𝑛𝑖=0

Ta cần chứng minh: 2𝑛+1 𝑆𝑛 = ∑𝑛+1
𝑖=1

𝑖!(𝑛−𝑖)!
𝑛!

2𝑖
𝑖

Ta có: 𝑆1 = 1

12


Và 2𝑛+2 𝑆𝑛+1 − 2𝑛+1 𝑆𝑛 = ∑𝑛+2
𝑖=1


2

=
=
=
=

𝑛+2
2
𝑛+2
2
𝑛+2
2
𝑛+2
2
𝑛+2

+

+
+
+

1

1

𝑛+2
1


𝑛+2
1
𝑛+2
1
𝑛+2
1
𝑛+2

(∑𝑛𝑖=0 𝐶 𝑖

𝑛+1

Vậy ∑𝑛𝑖=0

1
𝐶𝑛𝑖

=

1

∑𝑛𝑖=0 (

𝑖
𝐶𝑛+1

+ ∑𝑛+1
𝑖=0
+


1
𝑖+1
𝐶𝑛+1

1
𝑖
𝐶𝑛+1

𝑛+2

)

)

∑𝑛𝑖=0

𝑖!(𝑛+1−𝑖)!+(𝑖+1)!(𝑛−𝑖)!

∑𝑛𝑖=0

𝑖!(𝑛−𝑖)!(𝑛+1−𝑖+𝑖+1)

∑𝑛𝑖=0

𝑖!(𝑛−𝑖)!

1

1


2

𝑛+2

1

∑𝑛+1
𝑖=1
𝑛+1

2 2

=

2𝑛+2

(𝑛+1)!

(𝑛+1)!

𝑛!

𝑛+2

𝑆𝑛+1 = 𝑆𝑛 +

=

𝑖


=

2

= 𝑆𝑛 +

1

𝑖

2𝑖

𝑛+2

+

= .

− ∑𝑛+1
𝑖=1

2

Hay 2𝑆𝑛+1 = 𝑆𝑛 +
Vậy 2𝑆𝑛+1 =

2𝑖

∑𝑛+1

𝑖=1
𝑛+2

2𝑖

1

2𝑖

1

2

∑𝑛+2
𝑖=1
𝑛+2

𝑖

2

𝑖

+

+

1
𝑛+2


1
𝑛+2

𝑖

𝑛+1

2𝑖

2

𝑖

∑𝑛+1
𝑖=1
𝑛+1

2𝑖

Ví dụ 1.3.4. (Vandermonde) Cho 𝑚, 𝑛 và 𝑘 là những số nguyên; với
𝑚, 𝑛 ≥ 0. Chứng minh:
𝑘
𝑖
𝐶𝑚+𝑛
= ∑𝑘𝑖=0 𝐶𝑚
𝐶𝑛𝑘−𝑖

Giải
Cho rằng có 𝑚 phòng ngủ nam và 𝑛 phòng ngủ nữ tại khách sạn A.
Chúng ta muốn chọn 𝑘 phòng một cách ngẫu nhiên để kiểm tra nguy cơ cháy

13


𝑘
nổ của phịng. Tất nhiên có 𝐶𝑚+𝑛
cách chọn.

Mặt khác, những cách chọn này có thể phân loại 𝑘 + 1 kiểu. Cho 0 ≤
𝑖 𝑘−𝑖
𝑖 ≤ 𝑘, kiểu thứ 𝑖 gồm 𝑖 phòng nam và 𝑘 − 𝑖 phòng nữ. Do đó có 𝐶𝑚
𝐶𝑛 cách
của kiểu thứ 𝑖. Tổng các số này từ 0 → 𝑘 cho đồng nhất thức muốn chứng minh.

1.4. SONG ÁNH
Phần này ta giới thiệu một kỹ năng cơ bản trong việc giải quyết vấn đề
của tổ hợp. Để đếm các phần tử của một tập nhất định, chúng ta thay thế chúng
với những tập hợp khác có cùng số các phần tử và các phần tử được đếm dễ
dàng hơn.
Định lý 1.4.1. Cho 𝐴 và 𝐵 là các tập hữu hạn, và 𝑓: 𝐴 → 𝐵. Nếu 𝑓 là
song ánh, thì 𝐴 và 𝐵 có cùng số phần tử.
Chứng minh:
Cho 𝐴 = {𝑎1 , 𝑎2 , … , 𝑎𝑛 } với 𝑛 nguyên dương.
Vì 𝑓 song ánh, 𝑓(𝑎1 ), 𝑓(𝑎2 ), … , 𝑓(𝑎𝑛 ) phân biệt.
Do đó 𝐵 có ít nhất 𝑛 phần tử.
𝑓 toàn ánh nên mỗi phần tử trong 𝐵 là ảnh của một phần tử trong 𝐴.
Do đó 𝐵 = {𝑓(𝑎1 ), 𝑓(𝑎2 ), … , 𝑓(𝑎𝑛 )}, tức 𝐴 và 𝐵 có cùng số phần tử.
Ví dụ 1.4.1. Cho 𝑛 là số nguyên dương với 𝑛 ≥ 2 và dãy 𝑆 được định
nghĩa 𝑆 = (1, 2, … , 𝑛). Một phân dãy của 𝑆 được gọi là dãy số học nếu nó có ít
nhất hai số hạng và là cấp số cộng. Dãy con số học được gọi là cực đại nếu cấp
số này không thể bao hàm các phần tử khác của 𝑆. Hãy xác định số của dãy con

số học cực đại.
Giải:
Trước hết ta xem xét trường hợp khi 𝑛 là chẵn
Giả thiết 𝑛 = 2𝑚 với 𝑚 nguyên dương
Cho 𝑎1 < 𝑎2 < ⋯ < 𝑎𝑘 là dãy con số học cực đại với số nguyên 𝑘 ≥ 2
thì 𝑎1 ≤ 𝑚.
14


Mặt khác, 𝑎1 ≥ 𝑚 + 1 và 𝑎2 − 𝑎1 ≤ 2𝑚 − (𝑚 + 1) = 𝑚 − 1 chúng ta
có thể thêm 2𝑎1 − 𝑎2 vào dãy con kéo dài, bởi vì 2𝑎1 − 𝑎2 = 𝑎1 −
(𝑎2 − 𝑎1 ) ≥ (𝑚 + 1) − (𝑚 − 1) = 2 phủ định của dãy con cực đại.
Cũng như thế chúng ta thấy rằng 𝑎2 ≥ 𝑚 + 1
Do đó, một dãy con số học cực đại có hai số hạng liên tiếp 𝑎𝑖 và 𝑎𝑖+1 với
1 ≤ 𝑎𝑖 ≤ 𝑚 < 𝑚 + 1 ≤ 𝑎𝑖+1 ≤ 𝑛.
Ta có ánh xạ dãy con đến cặp số hạng liên tiếp (𝑎𝑖 , 𝑎𝑖+1 )
Như vậy cặp số hạng liên tiếp xác định hiệu số chung của dãy. Dãy cực
đại có nghĩa là tồn bộ các số hạng khác duy nhất được xác định (dùng hiệu số
chung để mở rộng dãy sang trái và sang phải đến khi không thể mở rộng nữa
trong khoảng biến thiên giữa 𝑙 và 𝑛).
Do đó, dãy con được xác định bằng đơi này của số hạng liên tiếp, và
ánh xạ của chúng ta là ánh xạ một đến một, tức là song ánh.
Rõ ràng ta có 𝑚 giá trị có thể có cho 𝑎𝑖 và 𝑚 giá trị cho 𝑎𝑖+1 , tức có
𝑚 cặp số (𝑎𝑖 , 𝑎𝑖+1 ) và 𝑚2 dãy con số học cực đại.
2

Tương tự chúng ta có thể thấy rằng có 𝑚(𝑚 + 1) dãy con số học cực
đại nếu 𝑛 = 2𝑚 + 1 với 𝑚 nguyên dương.
𝑛2


Như vậy, chúng ta kết luận rằng có ⌊ ⌋ dãy con số học cực đại với 𝑛
4

cho bất kỳ.
Định lý 1.4.2. Cho 𝑚 và 𝑛 nguyên dương
𝑚−1
(1) Có 𝐶𝑛−1
𝑚- tập hợp {𝑥1 , 𝑥2 , … , 𝑥𝑛 } nghiệm nguyên dương thỏa
phương trình 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑚 = 𝑛.
𝑚−1
(2) Có 𝐶𝑛+𝑚−1
𝑚- tập hợp {𝑥1 , 𝑥2 , … , 𝑥𝑛 } nghiệm nguyên không âm
thỏa phương trình 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑚 = 𝑛.

Thực ra, cũng có song ánh giữa 𝑚- tập hợp trong Định lý 1.4.2 (1) và
(2). Một 𝑚- tập hợp (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) nguyên dương với 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑚 = 𝑛
có thể là ánh xạ duy nhất tới một 𝑚- tập hợp (𝑦1 , 𝑦2 , … , 𝑦𝑚 ) không âm với 𝑦1 +
𝑦2 + … + 𝑦𝑚 = 𝑛 − 𝑚 dưới phép song ánh (𝑦1 , 𝑦2 , … , 𝑦𝑚 ) = (𝑥1 − 1, 𝑥2 −
1, … , 𝑥𝑚 − 1).
15


Ví dụ 1.4.2. (AIME 2000) Có 8 chiếc nhẫn, tìm số cách đeo 5 chiếc
nhẫn trên 4 ngón tay trên một bàn tay (thứ tự của các nhẫn trên mỗi một ngón
tay là có nghĩa, khơng nhất thiết mỗi ngón tay chỉ đeo một chiếc nhẫn).
Giải:
Có 𝐶85 cách để chọn 5 từ 8 chiếc nhẫn.
Giả sử 𝑎, 𝑏, 𝑐, 𝑑 là số của nhẫn trên ngón tay, chúng ta cần tìm bộ gồm
4 số (𝑎, 𝑏, 𝑐, 𝑑) ngun khơng âm sao cho 𝑎 + 𝑏 + 𝑐 + 𝑑 = 5.
5−1

Từ định lý 1.4.2 (1) có 𝐶4+5−1
bộ bốn.

Đối với mỗi cách đeo của 5 chiếc nhẫn, có 5! cách để đeo. Do đó câu trả lời là:
𝐶85 𝐶84 5! = 470400

1.5.

PHÉP ĐỆ QUY

Trong thực tế, chúng ta có thể gặp rất nhiều đối tượng mà khó có thể
định nghĩa nó một cách tường minh, nhưng lại dễ dàng định nghĩa đối tượng
qua chính nó. Kỹ thuật định nghĩa đối tượng qua chính nó được gọi là kỹ thuật
đệ quy.
Giả sử chúng ta đưa ra một tập các đối tượng, 𝑆𝑛 liên quan đến một
tham số 𝑛. Để tìm số lượng phần tử trong 𝑆𝑛 , chúng ta có thể xem số này như
là một hàm của 𝑛, có nghĩa là, chúng ta viết |𝑆𝑛 | = 𝑓(𝑛). Chúng ta có thể tìm
thấy một cơng thức rõ ràng cho 𝑓(𝑛), theo 𝑛, thông qua mối quan hệ giữa 𝑓(𝑛)
và 𝑓(𝑛 − 1), … , 𝑓(1), 𝑓(0). Mối quan hệ như vậy được gọi là quan hệ đệ quy
(hoặc đệ quy).
Cho 𝑓 là một hàm nguyên không âm. Nếu 𝑎1 , 𝑎2 , … , 𝑎𝑘 là hằng số thực
với 𝑛, 𝑘 nguyên và 𝑛 ≥ 𝑘 thì
𝑓(𝑛) − 𝑎1 𝑓(𝑛 − 1) − 𝑎2 𝑓(𝑛 − 2) − ⋯ − 𝑎𝑘 𝑓(𝑛 − 𝑘) = 0 (*)
Hệ thức này được gọi là thừa số đệ quy thuần nhất bậc 𝑘.
𝑓(𝑛) − 𝑎1 𝑓(𝑛 − 1) − 𝑎2 𝑓(𝑛 − 2) − ⋯ − 𝑎𝑘 𝑓(𝑛 − 𝑘) = 𝑔(𝑛) (*’)
Hệ thức này được gọi là thừa số đệ quy không thuần nhất bậc 𝑘.
16


Phương trình: 𝑥 𝑘 − 𝑎1 𝑥 𝑘−1 − 𝑎2 𝑥 𝑘−2 − ⋯ − 𝑎𝑘 = 0 (**)

được gọi là phương trình đặc trưng của đệ quy (*).
Nghiệm của phương trình (**) được gọi là nghiệm đăc trưng của đệ quy
(*). Chúng ta có những định lý sau:
Định lý 1.5.1. Cho 𝑧 ≠ 0 là một số phức. 𝑓(𝑛) = 𝑧 𝑛 thỏa (*) khi và chỉ
khi 𝑧 thỏa (**), tức 𝑧 là một nghiệm đặc trưng của (*).
Chứng minh:
Chú ý rằng 𝑓(𝑛) = 𝑧 𝑛 thỏa (*) khi và chỉ khi
𝑧 𝑛−𝑘 (𝑧 𝑘 − 𝑎1 𝑧 𝑘−1 − 𝑎2 𝑧 𝑘−2 − ⋯ − 𝑎𝑘 ) = 0
tương đương với 𝑧 thỏa (**), bởi 𝑧 ≠ 0.
Vì đệ quy (*) tuyến tính nên chúng ta dễ dàng có kết quả sau.
Định lý 1.5.2. Nếu 𝑓1 (𝑛) và 𝑓2 (𝑛) thỏa đệ quy (*) thì cũng thỏa tồn bộ
tổ hợp của chúng, tức 𝑐1 𝑓1 (𝑛) + 𝑐2 𝑓2 (𝑛) thỏa (*) với 𝑐1 , 𝑐2 hằng số.
Định lý 1.5.3. Nếu đệ quy (*) có 𝑘 nghiệm phân biệt 𝑧1 , 𝑧2 , … , 𝑧𝑘 thì tất
cả các hàm 𝑓(𝑛) thỏa (*) là tổ hợp tuyến tính của 𝑧1𝑛 , 𝑧2𝑛 , … , 𝑧𝑘𝑛 , tức là
𝑓(𝑛) = 𝑐1 𝑧1𝑛 + 𝑐2 𝑧2𝑛 + ⋯ + 𝑐𝑘 𝑧𝑘𝑛
trong đó 𝑐1 , 𝑐2 , … , 𝑐𝑘 là hằng số.
Chứng minh:
Theo định lý 1.5.1 và 1.5.2 chúng ta biết rằng tổ hợp tuyến tính của
𝑧1𝑛 , 𝑧2𝑛 , … , 𝑧𝑘𝑛 thỏa (*)
Giả sử 𝑓(𝑛) thỏa (*) thì 𝑓(𝑛) được xác định bởi giá trị ban đầu
𝑓(0), 𝑓(1), … , 𝑓(𝑘 − 1). Xét hệ tuyến tính:
1
𝑧1
𝑧12
⋮
𝑘−1
[𝑧1

1 … 1
𝑐1

𝑓(0)
𝑧2 ⋯ 𝑧𝑘
𝑐2
𝑓(1)
2
2
…
𝑐
𝑧𝑘 . 3 = 𝑓(2)
𝑧2
⋱
⋮
⋮
⋮
⋮
𝑘−1 …
𝑘−1 [𝑐 ]
𝑧2
𝑧𝑘 ] 𝑘 [𝑓(𝑘 − 1)]
17


Hệ này được giải khi và chỉ khi định thức của ma trận đầu tiên khác 0.
Nhưng ma trận đầu tiên là ma trận Vandermonde có định thức bằng
∏ (𝑧𝑗 − 𝑧𝑖 )
1≤𝑖<𝑗≤𝑘

Giá trị này khác 0 khi và chỉ khi tất cả các nghiệm 𝑧1 , 𝑧2 , … , 𝑧𝑘 phân
biệt. Do đó chúng ta có thể tìm các số thực 𝑐1 , 𝑐2 , … , 𝑐𝑘 sao cho:
𝑓(𝑛) = 𝑐1 𝑧1𝑛 + 𝑐2 𝑧2𝑛 + ⋯ + 𝑐𝑘 𝑧𝑘𝑛 với 𝑛 = 0, 1, … , 𝑘 − 1

Vì vậy hàm 𝑐1 𝑧1𝑛 + 𝑐2 𝑧2𝑛 + ⋯ + 𝑐𝑘 𝑧𝑘𝑛 thỏa phép truy hồi đã cho và đúng
với 𝑓(𝑛) của 𝑘 giá trị ban đầu 𝑛 = 0, 1, … , 𝑘 − 1, tức là
𝑓(𝑛) = 𝑐1 𝑧1𝑛 + 𝑐2 𝑧2𝑛 + ⋯ + 𝑐𝑘 𝑧𝑘𝑛 với 𝑛 ≥ 0
Định lý 1.5.4. Nếu đệ quy (*) có 𝑚 nghiệm phân biệt 𝑧1 , 𝑧2 , … , 𝑧𝑚 như
vậy bội số của nghiệm 𝑧𝑖 trong (**) là 𝑒𝑖 , với 𝑖 = 1, … , 𝑘, khi đó tất cả các hàm
𝑓(𝑛) thỏa mãn (*) là đệ quy tuyến tính của
𝑧1𝑛 , 𝑛𝑧1𝑛 , … , 𝑛𝑒1 −1 𝑧1𝑛
𝑧2𝑛 , 𝑛𝑧2𝑛 , … , 𝑛𝑒2 −1 𝑧2𝑛
....................................
𝑛
𝑛
𝑛
𝑧𝑚
, 𝑛𝑧𝑚
, … , 𝑛𝑒𝑚 −1 𝑧𝑚

Định lý này có thể được chứng minh bằng cách sử dụng ma trận tổng
quát Vandermonde và kiến thức về đa thức. Vì nó khơng phải là điểm chính
của tài liệu này, chúng ta bỏ qua chứng minh của định lý 1.5.4.
Vì đệ quy (*) cũng là tuyến tính, chúng ta dễ dàng có những điều sau đây.
Định lý 1.5.5. Hàm 𝑓(𝑛) thỏa mãn hằng số đệ quy khơng thuần nhất
(*’) có thể được viết dưới dạng
𝑓(𝑛) = 𝑓1 (𝑛) + 𝑓2 (𝑛)
𝑓1 (𝑛) thỏa mãn hằng đệ quy thuần nhất (*), và 𝑓2 (𝑛) là một hàm cụ thể thỏa
(*’).

18


1.6.


CÁC BÀI TỐN ỨNG DỤNG

Ví dụ 1.6.1. Có 5 nhà toán học nam, 3 nhà toán học nữ và 4 nhà vật lý
nam. Lập một đồn cơng tác gồm 3 người có cả nam lẫn nữ, cả nhà tốn học và
vật lý học. Hỏi có bao nhiêu cách lập đồn cơng tác? (Đề tuyển sinh Cao đẳng
Cơ khí luyện kim năm 2005)
Giải:
Chỉ có 3 cách lập đồn cơng tác như sau:
Gồm 2 nhà vật lý nam, 1 nhà toán học nữ. Theo quy tắc nhân số cách
chọn: 𝐶42 . 𝐶31 = 18
Gồm 1 nhà vật lý nam, 2 nhà toán học nữ. Theo quy tắc nhân, số cách
chọn: 𝐶41 . 𝐶32 = 12
Gồm 1 nhà vật lý nam, 1 nhà toán học nữ, 1 nhà toán học nam. Theo
quy tắc nhân số cách chọn: 𝐶41 𝐶31 𝐶51 = 60
Vậy theo quy tắc cộng, số cách lập đồn cơng tác: 18 + 12 + 60 = 90
Ví dụ 1.6.2. Một đội thanh niên tình nguyện có 15 người gồm 12 nam
và 3 nữ. Hỏi có bao nhiêu cách phân cơng đội thanh niên đó về giúp đỡ 3 tỉnh
miền núi, sao cho mỗi tỉnh có 4 nam và 1 nữ? (Đề thi tuyển sinh Đại học khối
B năm 2005)
Giải:
Đầu tiên chọn 4 nam, 1 nữ cho tỉnh thứ nhất. Theo quy tắc nhân, số cách
chọn là
4
𝑛1 = 𝐶12
. 𝐶31 = 1485

Sau đó chọn 4 nam (trong 8 nam cịn lại) và 1 nữ (trong 2 nữ còn lại)
cho tỉnh thứ 2, theo quy tắc nhân ta có
𝑛2 = 𝐶84 . 𝐶21 = 140

(Dĩ nhiên còn lại ta chọn xong tỉnh thứ 3)
Vậy theo quy tắc nhân, số cách phân công theo yêu cầu là
𝑛 = 𝑛1 . 𝑛2 = 207900

19


Ví dụ 1.6.3. (AIME 1989) Trên vịng trịn có 10 điểm. Có bao nhiêu đa
giác lồi khác nhau có ba cạnh hoặc nhiều hơn có thể được vẽ bằng cách sử dụng
một vài điểm (hay tất cả các điểm) trong 10 điểm được cho là các đỉnh (các đa
giác được gọi là khác nhau trừ phi chúng có chính xác cùng các đỉnh).
Giải:
Cho 3 ≤ 𝑘 ≤ 10, mỗi cách chọn 𝑘 điểm sẽ cho một đa giác với 𝑘 đỉnh.
𝑘
Vì 𝑘 điểm được chọn từ 10 trong 𝐶10
cách.
Câu trả lời là
3
10
4
𝐶10
+ 𝐶10
+ ⋯ + 𝐶10
0
10 )
0
1
1
2 )
= (𝐶10

+ 𝐶10
+ ⋯ + 𝐶10
− (𝐶10
+ 𝐶10
+ 𝐶10

= (1 + 1)10 − (1 + 10 + 45)
= 968
Ví dụ 1.6.4. Gieo 5 con xúc xắc cân đối, đồng chất. Tính xác suất để
tổng số chấm xuất hiện trong một lần gieo là 14?
Giải:
Gọi 𝑑1 , 𝑑2 , … , 𝑑5 là 5 con xúc xắc được gieo và cho 𝑥𝑖 là số chấm xuất
hiện của xúc xắc thứ 𝑑𝑖 . Mỗi 𝑥𝑖 có thể nhận một trong 6 giá trị. Do đó có 65
kết quả có thể có.
Cho 𝐴 là tập tất cả các kết quả có tổng số chấm là 14.
Ta cần tính

|𝐴|
65

Từ đó, ta cần tính tổng của 5 giá trị (𝑥1 , … , 𝑥5 ) tức 1 ≤ 𝑥𝑖 ≤ 6, và 𝑥1 + 𝑥2 +
⋯ + 𝑥5 = 14
5−1
4
Với 𝑥𝑖 ≤ 6, từ định lý 1.4.2 (1) ta có 𝐶14−1
= 𝐶13
= 715 kết quả

Một kết quả là sai nếu 𝑥𝑖 > 6 với 1 ≤ 𝑖 ≤ 5.
Cho 1 ≤ 𝑖 ≤ 5, tập 𝐵𝑖 là tập kết quả sai với 𝑥𝑖 > 6.

Rõ ràng 𝐵𝑖 và 𝐵𝑗 là khác nhau nếu 𝑖 ≠ 𝑗.
(Mặt khác, 𝑥1 + 𝑥2 + ⋯ + 𝑥5 > 6 + 6 + 1 + 1 + 1 = 15)
20


Theo tính đối xứng, ta cũng có |𝐵𝑖 | = |𝐵𝑗 |. Do đó có 5|𝐵𝑖 | kết quả sai.
Ánh xạ (𝑥1 , … , 𝑥5 ) ∈ 𝐵1 đến (𝑦1 , … , 𝑦5 ) với 𝑦1 = 𝑥1 − 6 và 𝑦𝑖 = 𝑥𝑖 (2 ≤ 𝑖 ≤
5)
Rõ ràng, ánh xạ là một song ánh giữa 𝐵1 và tập (𝑦1 , … , 𝑦5 ) với
𝑦1 + 𝑦2 + ⋯ + 𝑦5 = 8
5−1
Do đó, |𝐵1 | = 𝐶8−1
= 𝐶74 = 35

Và 5|𝐵1 | = 175
Vì vậy, |𝐴| = 715 − 175 = 540
Vậy xác suất cần tìm là
540
65

5

= 72

Ví dụ 1.6.5. (Trung Quốc 2002) Cho 𝑛 nguyên dương. Biểu diễn
∑(𝑎1 𝑎2 … 𝑎𝑛 )
Với tổng được lấy từ toàn bộ 𝑛 − số hạng của dãy số nguyên dương sao
cho 𝑎1 = 1 và 𝑎𝑖+1 ≤ 𝑎𝑖 + 1, trong đó 1 ≤ 𝑖 ≤ 𝑛 + 1.
Giải:
Cho 𝑓(𝑚, 𝑛) = ∑(𝑎1 𝑎2 … 𝑎𝑛 )

Với tổng được lấy từ toàn bộ 𝑛 – số hạng của dãy số nguyên dương sao
cho 𝑎1 = 1 và 𝑎𝑖+1 ≤ 𝑎𝑖 + 1, trong đó 1 ≤ 𝑖 ≤ 𝑛 + 1.
Tìm 𝑓(1, 𝑛). Nếu 𝑎1 = 𝑚 thì 1 ≤ 𝑎2 ≤ 𝑚 + 1. Do đó có phép đệ quy:
𝑓(𝑚, 𝑛 + 1) = 𝑚 ∑(𝑎2 𝑎3 … 𝑎𝑛+1 )
= 𝑚[𝑓(1, 𝑛) + 𝑓(2, 𝑛) + ⋯ + 𝑓(𝑚 + 1, 𝑛)]
Để tìm 𝑓(𝑚, 𝑛) chúng ta thấy rằng 𝑓(𝑚, 𝑛 + 1) và tổng riêng
𝑓(1, 𝑛) + 𝑓(2, 𝑛) + ⋯ + 𝑓(𝑚 + 1, 𝑛)
có thể viết dưới dạng tương tự.
Theo định lý 1.3.2 (5) và (7) ta có:
21


𝑛

(2𝑛 − 1)‼ = ∏(2𝑖 − 1)
𝑖=1
2𝑛−1
Chúng ta chứng minh rằng 𝑓(𝑚, 𝑛) = 𝐶𝑚+2𝑛−2
. (2𝑛 − 2)‼ bằng cách sử dụng
phép quy nạp trên 𝑛.

Trường hợp cơ bản thì đơn giản bởi vì 𝑓(𝑚, 1) = 𝑚
Giả thiết rằng 𝑓(𝑚, 𝑛) thỏa mãn đồng nhất thức ở trên với số nguyên dương
1 ≤ 𝑛 ≤ 𝑘.
Ta có:

𝑓(𝑚, 𝑘 + 1) = 𝑚[𝑓(1, 𝑘) + 𝑓(2, 𝑘) + ⋯ + 𝑓(𝑚 + 1, 𝑘)]
2𝑘−1
2𝑘−1
2𝑘−1

= 𝑚(2𝑘 − 1)‼ (𝐶2𝑘−1
+ 𝐶2𝑘
+ ⋯ + 𝐶𝑚+2𝑘−1
)
2𝑘
= 𝑚(2𝑘 − 1)‼ 𝐶2𝑘+𝑚
2𝑘+1
= (2𝑘 + 1)‼ 𝐶2𝑘+𝑚

Bởi định lý 1.3.2 (7) và (5)
Do đó, phép quy nạp được hồn thành. Do đó, câu trả lời là:
𝑓(1, 𝑛) = (2𝑛 − 1)‼

22


CHƯƠNG 2
CÁC PHƯƠNG PHÁP ĐẾM DÙNG
NGUYÊN LÝ BAO HÀM – LOẠI TRỪ, NGUYÊN LÝ
FUBINI VÀ HÀM SINH

2.1.

NGUYÊN LÝ BAO HÀM – LOẠI TRỪ

Cho 𝑛 là số nguyên dương lớn hơn 1. Ta muốn xác định số nguyên tố
trong tập hợp 𝑆 = {1, 2, … , 𝑛}, chú ý mỗi hợp phần trong 𝑆 có ít nhất một số
ngun tố nhỏ hơn hay bằng ⌊√𝑛⌋. Cho 𝑝1 = 2, 𝑝2 = 3, … , 𝑝𝑘 là dãy các số
nguyên tố nhỏ hơn hay bằng ⌊√𝑛⌋. Với mỗi 𝑝𝑖 trong dãy này ta gọi 𝐴𝑝𝑖 là tập
con của 𝑝𝑖 trong 𝐴. Khi đó số nguyên tố nhỏ hơn hay bằng 𝑛 là:

𝑛 + 𝑘 − 1 − |⋃𝑘𝑖=1 𝐴𝑝𝑖 |
Nói chung, ta có phương pháp sau, được gọi là nguyên lý Bao hàm –
loại trừ (hay cịn gọi là cơng thức Boole-Sylvester)
Định lý 2.1.1. Cho 𝐴1 , 𝐴2 , … , 𝐴𝑛 là họ các tập hữu hạn. Khi đó số các
phần tử của phép hợp 𝐴1 ∪ 𝐴2 ∪ … ∪ 𝐴𝑛 được xác định bởi
|⋃𝑛𝑖=1 𝐴𝑖 | = ∑𝐼⊆{1,…,𝑛}(−1)|𝐼|+1 |⋂𝑖∈𝐼 𝐴𝑖 | (*)
𝐼≠∅

Chứng minh:
Bằng quy nạp, cho 𝑛 = 2 chúng ta chứng minh
|𝐴1 ∪ 𝐴2 | = |𝐴1 | + |𝐴2 | − |𝐴1 ∩ 𝐴2 |
Thực tế, 𝐴1 ∪ 𝐴2 là hợp của những tập hợp không giao nhau 𝐴1 và 𝐴2 ∖
(𝐴1 ∩ 𝐴2 ), trong khi 𝐴2 là hợp của những tập hợp không giao nhau 𝐴2 ∖
(𝐴1 ∩ 𝐴2 ) và 𝐴1 ∩ 𝐴2 . Từ những đẳng thức:
|𝐴2 | = |𝐴2 ∖ (𝐴1 ∩ 𝐴2 )| + |𝐴1 ∩ 𝐴2 |
23


|𝐴1 ∪ 𝐴2 | = |𝐴1 | + |𝐴2 ∖ (𝐴1 ∩ 𝐴2 )|
chúng ta thu được những đẳng thức mong muốn
Giả sử khẳng định này đúng cho họ của 𝑛 − 1 tập hợp. Ta sẽ chứng minh nó
cho họ của 𝑛 tập hợp
𝑛−1
𝑛−1
|⋃𝑛𝑖=1 𝐴𝑖 | = |⋃𝑛−1
𝑖=1 𝐴𝑖 ∪ 𝐴𝑛 | = |⋃𝑖=1 𝐴𝑖 | + |𝐴𝑛 | − |(⋃𝑖=1 𝐴𝑖 ) ∩ 𝐴𝑛 |
𝑛−1
= |⋃𝑛−1
𝑖=1 𝐴𝑖 | + |𝐴𝑛 | − |⋃𝑖=1 (𝐴𝑖 ∩ 𝐴𝑛 )|


= ∑𝐼⊆{1,…,𝑛−1}(−1)|𝐼|+1 |⋂𝑖∈𝐼 𝐴𝑖 | + |𝐴𝑛 | − ∑𝐼⊆{1,…,𝑛−1}(−1)|𝐼|+1 |⋂𝑖∈𝐼(𝐴𝑖 ∩ 𝐴𝑛 )|
𝐼≠∅

𝐼≠∅

Bằng cách đặt thừa số chung, ta có cơng thức (*)
Định lý đảo của định lý 2.1.1 là
Định lý 2.1.2. Cho 𝐴1 , 𝐴2 , . . , 𝐴𝑛 là những tập hợp con của tập 𝑆. Và tập
𝐴̅𝑖 = 𝑆 − 𝐴𝑖 là phần bù của 𝐴𝑖 . Khi đó:
|⋂𝑛𝑖=1 𝐴̅𝑖 | = |𝑆| + ∑𝐼⊆{1,…,𝑛}(−1)|𝐼| |⋂𝑖∈𝐼 𝐴𝑖 |
𝐼≠∅

Dạng tổng quát của nguyên lý Bao hàm – Loại trừ:
Định lý 2.1.3. Cho 𝐴 là một tập hữu hạn và 𝑓 là một hàm từ 𝐴 đến các
số thực. Cho mỗi tập hợp con 𝐵 ⊆ 𝐴 thiết lập
𝑓(𝐵) = ∑𝑥∈𝐵 𝑓(𝑥)
trong đó 𝑓(∅) = 0. Nếu 𝐴 = ⋃𝑛𝑖=1 𝐴𝑖 thì
𝑓(𝐴) = ∑𝐼≠∅(−1)|𝐼|+1 𝑓(⋂𝑖∈𝐼 𝐴𝑖 )

(**)

Nếu 𝑓(𝑥) là hàm hằng tức 𝑓(𝑥) = 1 với mọi 𝑥 ∈ 𝐴 thì (**) trở thành (*).
Nhiều kết quả Lý thuyết số cơ bản có được bằng ứng dụng nguyên tắc
Bao hàm – loại trừ. Cho 𝑛 là số nguyên dương. Hàm Euler ∅(𝑛) được định
nghĩa là một số nguyên dương không lớn hơn 𝑛, tức là nguyên tố cùng nhau
đến 𝑛. Ta quy ước ∅(1) = 1
Nếu 𝑝 > 1 là một số nguyên tố, thì 1, 2, …, 𝑝 − 1 là số nguyên tố cùng
nhau đến 𝑝, do đó ∅(𝑝) = 𝑝 − 1. Nếu 𝑝 > 1 là số nguyên tố và 𝑟 ≥ 1, thì giá
trị của ∅(𝑝𝑟 ) bằng giới hạn của dãy
24



1, 2, 3, … , 𝑝, 𝑝 + 1, … , 2𝑝, … , 𝑝𝑟
không chia hết cho 𝑝. Số chia hết cho 𝑝 trong dãy là 𝑝, 2𝑝, 3𝑝, … , 𝑝𝑟 , do đó
1

∅(𝑝𝑟 ) = 𝑝𝑟 − 𝑝𝑟−1 = 𝑝𝑟 (1 − )
𝑝

Chú ý
(a)

lim

𝐷𝑛
𝑛!

= lim(1 −

1
1!

+

1

1

1


+ ⋯ + (−1)𝑛 ) =
2!
𝑛!
𝑒

Cơng thức đệ quy sau có thể được rút ra từ cơng thức trên bằng tính tốn
đơn giản
𝐷𝑛+1 = (𝑛 + 1)𝐷𝑛 + (−1)𝑛+1 = 𝑛𝐷𝑛 + (𝐷𝑛 − (−1)𝑛 ) = 𝑛(𝐷𝑛 + 𝐷𝑛−1 )
Chúng ta cũng có thể đạt được phép đệ quy ở trên trực tiếp bằng cách sử
dụng song ánh. Trong một sắp xếp của 𝑆, ta có hai lựa chọn:
(i)
𝜋(1) = 𝑘 và 𝜋(𝑘) = 1 với 1 ≤ 𝑘 ≤ 𝑛. Khi đó có 𝑛 − 1 giá trị
có thể có cho 𝑘 và mỗi 𝑘 có 𝐷𝑛−2 sắp xếp cho 𝑛 − 2 yếu tố cịn lại. Do đó có
(𝑛 − 1)𝐷𝑛−2 sắp xếp.
(ii) 𝜋(1) = 𝑘 và 𝜋(𝑘) = 𝑚 với 1 < 𝑘, 𝑚 ≤ 𝑛. Chú ý rằng 𝑘 ≠ 𝑚.
Khi đó có những phần tử 𝜋(2), 𝜋(3), … , 𝜋(𝑛) thường là một sắp xếp 𝜋(𝑖) của
2, … , 𝑘 − 1, 1, 𝑘 + 1, … , 𝑛 với 𝜋(1) = 𝑘. Mặt khác, có 𝑛 − 1 giá trị cụ thể cho
𝑘 và mỗi 𝑘 có 𝐷𝑛−1 sắp xếp. Do đó có (𝑛 − 1)𝐷𝑛−2 sắp xếp.
Do đó, 𝐷𝑛 = (𝑛 − 1)(𝐷𝑛−2 + 𝐷𝑛−1 ). Chú ý rằng 𝐷1 = 0 và 𝐷2 = 1.
Từ phép đệ quy này ta có thể có được công thức 𝐷𝑛 = 𝑛! ∑𝑛𝑘=0

(−1)𝑘
𝑘!

(b) Đồng nhất thức sau là đúng với Euler. Cho 𝑚, 𝑛 nguyên dương
với 𝑚 ≤ 𝑛. Khi đó
0 𝑛ế𝑢 𝑛 < 𝑚
𝑘 𝑘
𝑛
∑𝑚

𝑘=0(−1) 𝐶𝑚 (𝑚 − 𝑘) = {
𝑛! 𝑛ế𝑢 𝑛 = 𝑚

2.2.

PHÉP TÍNH THEO HAI CÁCH: NGUYÊN LÝ FUBINI

Cho đến nay, hầu hết những bài tốn được trình bày, bất kể mức độ khó
hay phức tạp, hẳn đã được giải với những tính tốn trực tiếp, tức là mỗi một bài
tốn có thể giải bằng cách đếm số phần tử (có lẽ qua phép đệ quy hay song
ánh). Trong phần này, để tìm 𝑥 là số các phần tử của 𝐴, ta sẽ tìm 𝑦 là số các
phần tử của 𝐵, để lập phương trình có chứa biến 𝑥, sau đó ta giải phương trình
25