Lời cảm ơn
Tôi xin bày tỏ lòng biết ơn sâu sắc đến GS.TSKH Hà Huy Khoái, đã
định hướng chọn đề tài và nhiệt tình hướng dẫn để tôi có thể hoàn thành
luận văn này.

Tôi cũng xin bày tỏ lòng biết ơn chân thành tới Phòng Sau đại học, các
thầy cô giáo giảng dạy chuyên ngành Phương pháp Toán sơ cấp, trường
Đại học Thăng Long đã giúp đỡ tôi trong suốt quá trình học tập tại trường.

Nhân dịp này tôi cũng xin gửi lời cảm ơn đến gia đình, bạn bè đã cổ vũ,
động viên để tôi hoàn thành luận văn này.
Hà Nội, tháng 4 năm 2016
Tác giả

Lê Thị Thọ


Lời cam đoan
Tôi xin cam đoan, dưới sự chỉ bảo và hướng dẫn của GS.TSKH Hà Huy
Khoái, luận văn chuyên ngành Toán Đại số với đề tài:”Phương pháp quy
nạp trong các bài toán tổ hợp” được hoàn thành bởi sự nhận thức và
tìm hiểu của bản thân tác giả.
Trong quá trình nghiên cứu và thực hiện luận văn, tác giả đã kế thừa
những kết quả của các nhà khoa học với sự trân trọng và biết ơn.
Hà Nội, tháng 4 năm 2016
Tác giả

Lê Thị Thọ

Thang Long University Libraty



1.5

Một số đồng nhất thức . . . . . . . . . . . . . . . . . . . . 19

2 QUY NẠP VÀ CÁC BÀI TOÁN TỔ HỢP

22

2.1

Số tập con . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2

Dãy số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3

Số tập con có thứ tự

2.4

Số tập con có kích thước cho trước . . . . . . . . . . . . . . 26

2.5

Bao hàm - Loại trừ . . . . . . . . . . . . . . . . . . . . . . 29

2.6


2.7.2

Công thức trong tam giác Pascal . . . . . . . . . . . 51

Kết luận

55

Tài liệu tham khảo

56

3

Thang Long University Libraty


MỞ ĐẦU
1. Lý do chọn đề tài
Học sinh ở các trường THPT hầu như chưa được học cơ bản về tổ hợp.
Không chỉ quan trọng đối với kỳ thi học sinh giỏi, mà tổ hợp là một phần
không thể thiếu cho những ai muốn tiếp tục học tập, nghiên cứu và làm
việc có hiệu quả trong những ngành như Toán học, Tin học, Kỹ thuật, hay
đơn giản chỉ là để trau dồi tư duy logic, điều mà ai cũng cần trong cuộc
sống. Trong những cố gắng nâng cao trình độ về tổ hợp cho học sinh, một
việc làm quan trọng là cung cấp cho giáo viên và học sinh những tài liệu
tốt về môn này. Yêu cầu đặt ra là tài liệu đó phải trình bầy những kiến
thức cơ bản nhất theo cách tự nhiên, bản chất và dễ hiểu nhất, để học
sinh cảm thấy tổ hợp không quá khó. Khi có những kiến thức cơ bản và


Bây giờ ta tìm hiểu các công cụ quan trọng nhất trong toán rời rạc. Ta
bắt đầu bằng câu hỏi:
Cộng n số lẻ đầu tiên lại ta thu được số bằng bao nhiêu?
Có lẽ cách tốt nhất là ta thử tìm câu trả lời bằng thực nghiệm. Thử với
các giá trị n nhỏ, thì thứ ta tìm được là:

1=1
1+3=4
1+3+5=9
1 + 3 + 5 + 7 = 16
1 + 3 + 5 + 7 + 9 = 25
1 + 3 + 5 + 7 + 9 + 11 = 36
1 + 3 + 5 + 7 + 9 + 11 + 13 = 49

7

Thang Long University Libraty


1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64
1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 = 81
1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 = 100
Dễ dàng nhận thấy ta thu được các số chính phương; thật ra, dường như
từ các ví dụ trên ta có tổng của n số lẻ đầu tiên là n2 . Ta đã thấy điều
này với 10 giá trị n đầu tiên; liệu ta có chắc chắn điều này đúng với mọi
giá trị? Vâng, tôi muốn nói rằng chúng ta có thể chắc chắn, nhưng trong
toán học thì tin rằng "chắc chắn đúng" chưa đủ. Làm thế nào chúng ta có
thể chứng minh khẳng định trên?
Xét tổng với số n tổng quát. Số lẻ thứ n là 2n − 1, nên ta thử chứng

Điều đó là đủ để kết luận rằng khẳng đúng với mọi n. Ta đã thấy nó
đúng với n = 1; nên theo trên, nó cũng đúng với n = 2 (ta đã thấy điều
này bằng tích toán trực tiếp, nhưng việc đó không thực sự cần thiết: nó
được suy ra trừ trường hợp n = 1). Theo cách tương tự, tính đúng đắn
của khẳng định với n = 2 kéo theo nó cũng đúng với n = 3, và đến lượt
nó lại kéo theo tính đúng đắn với n = 4, v.v.. Nếu ta lặp lại điều này đủ
nhiều, ta thu được tính đúng đắn với giá trị n bất kỳ. Do đó khẳng định
trên là đúng với mọi giá trị n.
Kỹ thuật chứng minh này được gọi là quy nạp (hoặc đôi khi gọi là quy
nạp toán học, để phân biệt với khái niệm trong triết học). Nó được tóm
tắt lại như sau.
Giả sử rằng ta muốn chứng minh một tính chất của các số nguyên dương.
Giả sử thêm ta có thể chứng minh hai điều:
(a) số 1 có tính chất đó, và
(b) bất cứ khi nào n − 1 có tính chất đó thì n cũng có tính chất đó
(n > 1).

Nguyên lý quy nạp nói rằng nếu (a) và (b) đúng, thì mọi số tự nhiên có
tính chất như vậy.
Điều này chính là những gì ta làm ở trên. Ta đã chỉ ra “tổng” của số lẻ
đầu tiên là 12 , và tiếp theo ta chỉ ra nếu tổng của n − 1 số lẻ đầu tiên là

(n − 1)2 , thì tổng của n số lẻ đầu tiên là n2 , với mọi số nguyên n > 1.

Do đó, theo Nguyên lý quy nạp ta có thể kết luận rằng với mọi số nguyên
dương n, tổng của n số lẻ đầu tiên là n2 .

Thông thường, cách tốt nhất để thử tiến hành chứng minh bằng phương
pháp quy nạp là như sau. Đầu tiên ta chứng minh phát biểu đúng với n = 1.
(Việc này đôi khi được gọi là trường hợp cơ sở.) Tiếp theo ta thử chứng

Bài toán 1.1.1. Chứng minh bằng quy nạp và không bằng quy nạp rằng

n(n + 1) luôn là số chẵn với mọi số nguyên dương n.
Bài toán 1.1.2. Chứng minh bằng quy nạp rằng tổng của n số nguyên
dương đầu tiên là n(n + 1)/2.
Bài toán 1.1.3. Nhận xét rằng n(n + 1)/2 là số cái bắt tay giữa n + 1
người. Giả sử rằng tất cả mọi người chỉ đếm số bắt tay với người nhiều
tuổi hơn mình (khá là lố bịch, phải không?). Ai là người có số bắt tay
nhiều nhất? Có bao nhiêu người có 6 cái bắt tay? (Chúng ta giả sử rằng
không có hai người nào bằng tuổi).
10


Dựa vào kết quả của bài tập 1.1.2 chứng minh các kết quả của bạn.
Chúng ta thường dùng chữ “v.v.”: để miêu tả một số lập luận mà phải
lặp n lần mới thu được kết quả ta cần, nhưng sau khi lập luận một hoặc
hai lần, ta nói “v.v.” thay vì tiếp lục lặp lại. Không có gì là sai ở đây, nếu
lập luận đủ đơn giản thì ta có một cách trực quan thấy những chỗ mà
phép lặp bắt đầu. Nhưng sẽ tốt hơn nếu có thể dùng một số công cụ thay
vì “v.v.” trong trường hợp mà kết quả của phép lặp không quá rõ ràng.
Cách chính xác để làm điều này là dùng phép quy nạp. Giả sử ta chứng
minh công thức tính số tập con của một tập n phần tử (đáp án là 2n ).
Nguyên lý quy nạp cho ta biết ta phải kiểm tra khẳng định đúng với

n = 0. Việc này là rõ ràng. Tiếp theo, ta giả sử rằng n > 0 và khẳng định
đúng với các tập có n − 1 phần tử. Xét tập S có n phần tử, và cố định

một phần tử bất kỳ a ∈ S. Ta muốn đếm số tập con của S. Ta chia chúng

thành hai lớp: lớp chứa a và lớp không chứa a. Ta đếm chúng một cách

Ta bắt đầu với các câu hỏi đơn giản hơn. Số nào lớn hơn, n hay
Với n = 2, 3, 4 giá trị

n
2

n
2

?

là 1, 3, 6, nên nó nhỏ hơn n với n = 2, bằng

nhau với n = 3 và lớn hơn với n = 4. Thật ra, n =

n
1



Bây giờ ta giải quyết vấn đề ước lượng số 100!, hay tổng quát hơn,

n! = 1 · 2 · · · n. Nhân tử 1 đầu tiên không ảnh hưởng gì, nhưng tất cả các

nhân tử khác đều ít nhất là 2, nên n! ≥ 2n−1 . Tương tự n! ≤ nn−1 , vì (bỏ
qua nhân tử 1) n! là tích của n − 1 nhân tử, mỗi trong số đó đều nhỏ hơn
12


n. (Vì tất cả trừ một trong số chúng nhỏ hơn n, nên tích nhỏ hơn nhiều.)
Do vậy ta biết rằng

2n−1 ≤ n! ≤ nn−1 .

(1.3)

Các cận này cách nhau khá xa, với n = 10, cận dưới là 29 = 512, trong
khi cận trên là 109 (một tỉ).
Dưới đây là một câu hỏi vẫn chưa được trả lời bằng các ước lượng trong
(1.3). Số nào lớn hơn, n! hay 2n ? Nói cách khác, tập với n phần tử có số
phép hoán vị nhiều hơn số tập con hay không? Với các giá trị n nhỏ, số tập
con thắng nhiều hơn: 21 = 2 > 1! = 1, 22 = 4 > 2! = 2, 23 = 8 > 3! = 6.
Nhưng từ đây thì lại đổi chiều: 24 = 16 < 4! = 24, 25 = 32 < 5! = 120.
Dễ thấy rằng khi n tăng, n! tăng nhanh hơn 2n : Nếu ta đi từ n tới n + 1,
thì 2n tăng với hệ số 2, trong khi n! tăng với hệ số n + 1.
Bài toán 1.2.2. Dùng phép quy nạp để chính xác hoá phát biểu trên và
chứng minh rằng n! > 2n nếu n ≥ 4.
Dưới đây là công thức đưa ra phép xấp xỉ rất tốt cho n!. Ta phát biểu
nó mà không chứng minh, vì chứng minh (mặc dù không hoàn toàn khó)
cần đến giải tích.


Ta quay trở lại câu hỏi: Số 100! có bao nhiêu chữ số? Theo công thức
Stirling ta biết rằng

100! ≈ (100/e)100 ·

√

200π.

Số chữ số của số này là logarit cơ số 10 của nó được làm tròn. Do đó ta có

lg(100!) ≈ 100 lg(100/e) + 1 + lg

√

2π = 157.969...

Nên số chữ số trong số 100! là vào khoảng 158 (thật ra đây là giá trị đúng).

1.3

Chứng minh các đồng nhất thức và bất đẳng
thức nhờ quy nạp toán học

Phương pháp quy nạp toán học cho phép chứng minh các đồng nhất
thức và bất đẳng thức mà một hoặc hai vế của chúng phụ thuộc số tự
nhiên n. Chẳng hạn, trước tiên có thể kiểm tra rằng đồng nhất thức cần
chứng minh đúng khi n = 1, sau đó viết đồng nhất thức khi n = k + 1
và n = k rồi trừ từng vế hai đồng nhất thức nhận được. Nếu làm như vậy

(1.3.1)


Khi n = 1, đồng nhất thức có dạng 1 −

1
2

=

1
2

đúng.

Bây giờ ta viết đồng nhất thức khi n = k và khi n = k + 1

1−

1
1
1
1
1
1
+ ... +
−
=
+
+ ... +

1
1
−
=
+
−
,
2k + 1 2(k + 1) 2k + 1 2k + 2 k + 1
hay là

2
1
=
.
2(k + 1) k + 1
đúng.
Điều đó có nghĩa là nếu (1.3.1.1) đúng thì (1.3.1.2) đúng, do đó theo quy
nạp toán học đồng nhất thức (1.3.1) đúng với mọi số tự nhiên n.
Hoàn toàn như vậy ta chứng minh được khẳng định sau đây, được gọi
là bất đẳng thức Bernoulli:
Bài toán 1.3.2.
Nếu x > −1 thì mọi số tự nhiên n bất đẳng thức sau đây nghiệm đúng:

(1 + x)n ≥ 1 + nx.

(1.3.2).

Chứng minh. Thật vậy, khi n = 1 ta có bất đẳng thức đúng

1+x≥1+x .

2 thỏ trong thang thứ ba, và ba con thỏ trong tháng thứ tư, vì con thỏ
đầu tiên sinh ra một con sau tháng thứ hai. Sau 4 tháng, con thỏ thứ hai
cũng sinh một con thỏ mới, nên hai con thỏ con được thêm vào. Điều này
có nghĩa người nông dân có 5 con thỏ sau tháng thứ 5.
Dễ dàng suy ra quy tắc tăng trưởng đàn thỏ với số tháng bất kỳ, nếu ta
chú ý rằng số thỏ mới sinh trong mỗi tháng chính bằng số thỏ ít nhất hai
tháng tuổi, tức là, những con đã có ở tháng trước. Nói cách khác, để tính
số thỏ trong tháng tiếp theo, ta phải cộng thêm số thỏ trong tháng trước
16


đó vào số thỏ trong tháng hiện tại. Việc này giúp ta dễ dàng tính lần lượt
số thỏ:

1, 1, 1 + 1 = 2, 2 + 1 = 3, 3 + 2 = 5, 5 + 3 = 8, 8 + 5 = 13, . . .
(Có vẻ Fibonacci không thực sự coi câu hỏi của ông như bài toán áp
dụng thực tế; ông làm việc với các con số, chú ý rằng việc này sinh ra các
con số mới đối với ông, nhưng lại có các tính chất thú vị, như ta sẽ thấy
về sau).
Để viết điều này thành công thức, ta ký hiệu Fn là số thỏ trong tháng
thứ n. Khi đó ta có, với n = 2, 3, 4, . . .,

Fn+1 = Fn + Fn−1 .

(1.4)

ta cũng biết rằng F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5. Để cho tiện, ta
ký hiệu F0 = 0; khi đó phương trình (1.4) vẫn đúng với n = 1, giống như
định nghĩa của các số này. Điều này có gì đó có vẻ không bình thường:
thay vì nói cho ta biết Fn là cái gì (theo công thức), ta chỉ đưa ra quy tắc

Câu hỏi này cũng tương tự như câu hỏi ta đã dùng để tính dãy số Fibonacci

Fn . Điều này có phải có nghĩa là Fn = Jn ? Tất nhiên là không rồi, như ta
thấy ở các giá trị ban đầu: Ví dụ, F3 = 2 nhưng J3 = 3. Tuy nhiên, dễ
thấy rằng tất cả những gì xảy ra là Jn bị di chuyển thành

Fn+1 .
Điều này đúng với n = 1, 2, và nên tất nhiên đúng với mọi n, vì các dãy

F2 , F3 , F4 , . . . và J1 , J2 , J3 , . . . được tính toán bằng quy tắc giống nhau từ
giá trị của hai phần tử ban đầu.
Bài toán 1.4.2. Bạn có n đô la để tiêu. Mỗi ngày bạn mua một viên kẹo
với giá 1 đô la hoặc một cây kem với giá 2 đô la. Hỏi bạn có bao nhiêu
cách tiêu chỗ tiền này?

18


1.5

Một số đồng nhất thức

Có rất nhiều công thức thú vì về dãy Fibonacci. Ví dụ, tổng của n số
Fibonacci đầu tiên bằng bao nhiêu? Ta có

0 = 0,
0 + 1 = 1,
0 + 1 + 1 = 2,
0 + 1 + 1 + 2 = 4,
0 + 1 + 1 + 2 + 3 = 7,

Bài toán 1.5.2. Chứng minh rằng F5n chia hết cho 5.
Bài toán 1.5.3. Chứng minh các công thức sau.
(a) F1 + F3 + F5 + . . . + F2n−1 = F2n .
(b) F0 − F1 + F2 − F3 + · · · − F2n−1 + F2n = F2n−1 − 1.
Bây giờ ta muốn phát biểu một công thức khó hơn:
2
= F2n−1 .
Fn2 + Fn−1

(1.5)

Dễ dàng kiểm tra được công thức này đúng với nhiều giá trị n, và ta có
thể thuyết phục rằng nó đúng, nhưng để chứng minh nó thì hơi khó hơn
một ít. Tại sao công thức này lại khó hơn các công thức trước. Bởi vì nếu
ta muốn chứng minh nó bằng quy nạp (ta không thực sự có cách nào khác
tại thời điểm này), thì ở vế phải ta chỉ có một số Fibonacci khác, và do
vậy ta không biết cách để áp dụng phép truy hồi ở đây.
Một cách để khắc phục điều này là tìm công thức tương tự cho F2n , và
chứng minh cả hai công thức bằng quy nạp. Với một chút may mắn (hay
trực quan sâu sắc?) bạn có thể giả thiết

Fn+1 Fn + Fn Fn−1 = F2n .

(1.6)

Một lần nữa dễ dàng thấy công thức này đúng với nhiều giá trị n, để

20




= F2n−3 + F2n−2 = F2n−1 .
(áp dụng phép quy nạp cho số hạng đầu tiên và công thức (1.6) cho số
hạng thứ hai).
Đợi một chút! Thủ thuật ở đây là gì? Chúng ta sử dụng (1.6) trong
chứng minh (1.5), và sau đó (1.5) trong chứng minh (1.6)? Không sao, lập
luận là đúng. Nó chỉ là hai chứng minh quy nạp phải đi cùng một lúc. Nếu
chúng ta biết rằng cả (1.6) và (1.5) cùng đúng với giá trị nhất định của

n, sau đó ta chứng minh (1.5) cho các giá trị tiếp theo (nếu bạn nhìn vào
chứng minh, bạn có thể thấy nó chỉ sử dụng các giá trị n nhỏ hơn), và sau
đó sử dụng điều này và các giả thiết quy nạp một lần nữa để chứng minh
(1.6).
Thủ thuật này được gọi là quy nạp đồng thời, và nó là một phương pháp
hữu ích để làm cho phép quy nạp mạnh hơn.

21

Thang Long University Libraty


Chương 2
QUY NẠP VÀ CÁC BÀI TOÁN
TỔ HỢP
2.1

Số tập con

Ta quay lại với bài toán: Có tất cả bao nhiêu tập con của một tập có n
phần tử?


8

Dựa vào các giá trị trong bảng, ta thấy rằng số tập con là lũy thừa của

2: Nếu tập có n phần tử, thì kết quả là 2n , ít nhất là đúng với các ví dụ
nhỏ này.
22


Không khó để thấy rằng điều này luôn đúng. Giả sử bạn phải chọn một
tập con của một tập A có n phần tử; ta gọi các phần tử này là a1 , a2 , . . . , an .
Khi đó chúng ta có thể muốn hoặc không muốn bao gồm a1 , nói cách khác,
ta có thể đưa ra hai lựa chọn ở đây. Không quan trọng ta đã quyết định
như thế nào về a1 , ta có thể muốn hoặc không muốn bao gồm a2 trong
tập con này; điều này có nghĩa có hai lựa chọn, và do vậy tổng số cách ta
có thể chọn về a1 và a2 là 2 · 2 = 4. Bây giờ không quan trọng ta đã chọn

a1 và a2 , ta phải quyết định chọn a3 , và một lần nữa ta có hai cách. Mỗi
một trong hai cách này có thể kết hợp với 4 lựa chọn ta có thể đưa ra về

a1 và a2 , tạo ra 4 · 2 = 8 khả năng để quyết định về a1 , a2 và a3 .

Ta có thể tiếp tục như vậy: Không quan trọng về k phần tử đầu tiên,

ta có hai lựa chọn về số tiếp theo, và do vậy số khả năng nhân đôi mỗi lần
ta lấy một phần tử mới. Để quyết định về tất cả n phần tử của tập hợp,
ta có 2n khả năng.
Do đó ta suy ra định lý sau.
Định lý 2.1.1. Một tập với n phần tử có 2n tập con.

Số dữ liệu tất nhiên sẽ rất lớn. Trường thứ nhất có thể chứa 268 >

200.000.000.000 tên (phần lớn trong số chúng sẽ rất khó để phát âm và
khó có thể xảy ra, nhưng ta phải đếm tất cả số trường hợp). Trường thứ
hai có hai khả năng. Trường thứ 3 có thể được coi là 3 trường riêng biệt,
có tương ứng 12, 31, và 100 khả năng (một số tổ hợp của chúng sẽ không
bao giờ xảy ra, ví dụ 04-31-76 hay 02-29-13, nhưng ta bỏ qua điều này).
Trường cuối cùng có 13 khả năng.
Bây giờ ta xác định cách các trường này được kết hợp với nhau. Ta có
lặp lại lập luận như trên, theo thứ tự “3 cách chọn” được thay bằng “ 268
cách chọn”, “2 cách chọn”, “12 cách chọn”, “31 cách chọn”, “100 cách chọn”,
và “13 cách chọn”. Ta thu được kết quả là là 268 · 2 · 12 · 31 · 100 · 13 =

201, 977, 536, 857, 907, 200.

Ta có thể tổng quát hóa định lý 2.2.1 (chứng minh bao gồm lặp lại các
lập luận như trên).
Định lý 2.2.2. Giả sử ta muốn lập một chuỗi có độ dài n bằng một tập bất
kỳ có k1 ký hiệu làm phần tử đầu của chuỗi, một tập bất kỳ có k2 ký hiệu
24