TRƯỜNG ĐẠI HỌC QUẢNG BÌNH
KHOA KHOA HỌC TỰ NHIÊN

NGUYỄN THỊ THANH THẢO

MỘT SỐ PHƯƠNG PHÁP GIẢI CÁC BÀI TOÁN ĐẠI SỐ
TỔ HỢP TRONG CHƯƠNG TRÌNH THPT

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

NGÀNH: SƯ PHẠM TOÁN HỌC
Hệ đào tạo: Chính quy
Khóa học: 2014 - 2018

Người hướng dẫn: ThS. TRẦN MẠNH HÙNG

QUẢNG BÌNH, NĂM 2018



Lời cảm ơn
Trước tiên, tôi muốn gửi lời cảm ơn và tri ân sâu sắc đến thầy Trần Mạnh
Hùng - người đã tận tình chỉ bảo và hướng dẫn cho tôi trong suốt quá trình
thực hiện khóa luận tốt nghiệp.
Tôi cũng xin chân thành cảm ơn tất cả các thầy cô Trường Đại học Quảng
Bình, đặc biệt là các thầy cô trong khoa Khoa học tự nhiên đã dạy dỗ, tạo điều
kiện cho tôi trong suốt những năm tháng ngồi trên giảng đường đại học. Chính
những điều đó đã giúp tôi học được rất nhiều điều bổ ích không những trong
chuyên ngành của mình mà trong cả cuộc sống.
Cuối cùng, tôi muốn gửi lời cảm ơn đến gia đình, các anh chị khóa trước,
tập thể lớp ĐHSP Toán K56, bạn bè xung quanh và những người đã động viên,


1.4 Hoán vị, chỉnh hợp, tổ hợp . . . . . . . . . . . . . . . . . . . . .

9

1.4.1 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.4.2 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.4.3 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.5 Chỉnh hợp lặp, hoán vị lặp, tổ hợp lặp . . . . . . . . . . . . . .

11

1.5.1 Chỉnh hợp lặp . . . . . . . . . . . . . . . . . . . . . . . .

11

1.5.2 Hoán vị lặp . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.5.3 Tổ hợp lặp . . . . . . . . . . . . . . . . . . . . . . . . . .



2.1 Phương pháp đếm trực tiếp . . . . . . . . . . . . . . . . . . . .

14

2.2 Phương pháp đếm loại trừ . . . . . . . . . . . . . . . . . . . . .

17

2.3 Phương pháp tạo vách ngăn . . . . . . . . . . . . . . . . . . . .

19

2.4 Phương pháp "dán" phần tử . . . . . . . . . . . . . . . . . . . .

21

2.5 Phương pháp thêm bớt . . . . . . . . . . . . . . . . . . . . . . .

22

2.6 Phương pháp liệt kê các trường hợp . . . . . . . . . . . . . . . .

26

2.7 Phương pháp song ánh . . . . . . . . . . . . . . . . . . . . . . .

29



43

3.5 Phương pháp sử dụng bất đẳng thức Cauchy, Bunhiacopski để
chứng minh các đẳng thức tổ hợp . . . . . . . . . . . . . . . . .
Chương 4 Một số dạng toán khác và các ví dụ minh họa
4.1 Chứng minh một số bài toán chia hết . . . . . . . . . . . . . . .

46
49
49

4.2 Giải phương trình, hệ phương trình, bất phương trình, hệ bất
phương trình tổ hợp . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Tìm hệ số, số hạng trong khai triển nhị thức Newton

52

. . . . . .

61

4.4 Tính tổng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

2


KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

tới tận năm 1977, Appel và Haken mới quy được bài toán qui màu bản đồ
về việc xem xét trên 1900 cấu hình tổ hợp,. . . . Từ chỗ chỉ nghiên cứu các
trò chơi, bài toán về kinh tế xã hội,. . . tổ hợp đã trở thành ngành toán học
phát triển mạnh mẽ, có nhiều ứng dụng trong nhiều lĩnh vực khác nhau.
Hơn nữa, tổ hợp cũng là một dạng toán nằm trong chương trình THPT
và có cấu trúc trong các đề thi THPT Quốc gia và cũng là một mảng toán
khó, nhưng lại có ứng dụng nhiều trong cuộc sống hằng ngày.
Hiện nay, đa số học sinh đều gặp khó khăn trong việc giải các bài tập

4


có liên quan đến toán tổ hợp. Đặc biệt, đội ngũ học sinh giỏi khi tham gia
các kì thi cấp tỉnh, cấp quốc gia gặp nhiều lúng túng trong việc giải những
bài toán dạng này.
Với lí do trên, tôi đã tìm hiểu và đã chọn nghiên cứu đề tài :"Một số
phương pháp giải các bài toán đại số tổ hợp trong chương trình THPT".
Nhằm cung cấp cho học sinh một hệ thống phương pháp giải các bài toán
tổ hợp từ đó nâng cao khả năng giải toán và tư duy cho học sinh.
2. Mục đính nghiên cứu
Nghiên cứu và trình bày một cách có hệ thống về các khái niệm, các
phương pháp giải một số bài toán tổ hợp để ứng dụng vào việc giải toán.
3. Đối tượng nghiên cứu và phạm vi nghiên cứu
Đối tượng nghiên cứu chính của khóa luận là phân loại, đưa ra các
phương pháp toán giải các bài toán đại số tổ hợp.
4. Phương pháp nghiên cứu
Phương pháp nghiên cứu lí luận: Đọc và nghiên cứu các tài liệu, giáo
trình về các vấn đề cần nghiên cứu như: phương pháp đếm, phương pháp
giải các bài toán chứng minh đẳng thức,. . .
Phương pháp lấy ý kiến chuyên gia: Các ý kiến của giảng viên hướng

Định nghĩa 1.1.1.
i) Tập hữu hạn
Một tập hợp S được gọi là hữu hạn và có n phần tử nếu tồn tại một song
ánh f : S −→ { 1, 2, ..., n} (với { 1, 2, ..., n} ⊂ N).
Số n được gọi là lực lượng của tập hợp S. Kí hiệu | S |= n.
ii) Tập vô hạn
Nếu tập S không là tập hữu hạn thì ta nói tập S vô hạn.
Tập hợp tương đương: Các tập hợp tương đương, còn được gọi là tập hợp
đẳng lực, là các tập hợp mà giữa các phần tử của chúng có thể thiết lập quan
hệ tương đương, tức quan hệ tương ứng một-một (song ánh).
Nhận xét 1.1.1. Hai tập hợp có cùng lực lượng khi và chỉ khi tồn tại một
song ánh từ tập hợp này vào tập hợp kia.

1.2

Quy tắc cộng

Định nghĩa 1.2.1. Giả sử một công việc có thể thực hiện theo một trong k
phương án A1 , A2 , . . . , Ak .
Có n1 cách thực hiện phương án A1
7


Có n2 cách thực hiện phương án A2
...
Có nk cách thực hiện phương án Ak
Khi đó, công việc có thể được thực hiện bởi n1 + n2 + . . . + nk cách.

• Quy tắc cộng được phát biểu dưới dạng tập hợp
Nếu tập hợp hữu hạn A là hợp của n tập đôi một rời nhau A1 , A2 , . . . , An

Công đoạn nk , có thể thực hiện theo Ak cách
Khi đó, công việc có thể được thực hiện bởi n1 n2 . . . nk cách.

• Quy tắc nhân được phát biểu dưới dạng tập hợp
Nếu A1 , A2 , . . . , An là các tập hợp hữu hạn bất kì và A1 × A2 × ... × An
là tích Descartes của n tập hợp đó thì:
8


| A1 × A2 × . . . × An |=| A1 | × | A2 | × . . . × | An |
Nhận xét 1.3.1. Từ định nghĩa của quy tắc cộng và quy tắc nhân trên, ta
thấy rằng:

• Nếu bỏ một giai đoạn nào đó mà không thể hoàn thành được công việc
thì ta sử dụng quy tắc nhân.

• Nếu bỏ một giai đoạn nào đó mà vẫn có thể hoàn thành được công việc
thì ta sử dụng quy tắc cộng.
Như vậy, với nhận xét này, ta đã thấy được sự khác nhau căn bản giữa hai quy
tắc này.

1.4

Hoán vị, chỉnh hợp, tổ hợp

1.4.1

Hoán vị

Định nghĩa 1.4.1. Cho tập hợp A có n phần tử (n


n!
.
(n − k)!

(1.2)

n!
= 1.
(n − 0)!
Vậy công thức (1.2) đúng với mọi số nguyên k thỏa mãn 0 ≤ k ≤ n.

• Ta quy ước: 0! = 1 và A0n =

1.4.3

Tổ hợp

Định nghĩa 1.4.3. Cho tập hợp A có n phần tử (n

1) và số nguyên dương

k (1 ≤ k ≤ n). Một tổ hợp chập k của n phần tử của tập hợp A là một tập
con của A có k phần tử. Một tổ hợp chập k của A được kí hiệu là Ckn .
Công thức :

Ckn =

n(n − 1)(n − 2)...(n − k + 1) Akn
=



Nhận xét 1.4.1.

• Chỉnh hợp và tổ hợp liên hệ với nhau bởi công thức: Akn = k!Ckn
• Chỉnh hợp thì các phần tử được sắp xếp 1 cách có thứ tự, còn tổ hợp các
phần tử được sắp xếp mà không phân biệt thứ tự.

• Những bài toán mà kết quả phụ thuộc vào vị trí các phần tử ta dùng chỉnh
hợp. Ngược lại, dùng tổ hợp.

1.5

Chỉnh hợp lặp, hoán vị lặp, tổ hợp lặp

1.5.1

Chỉnh hợp lặp

Định nghĩa 1.5.1. Cho tập A có n phần tử và số nguyên k . Chỉnh hợp lặp
chập k của n phần tử của tập hợp A là một bộ sắp thứ tự gồm k phần tử,
trong đó mỗi phần tử có thể lặp lại nhiều lần.
Nhận xét 1.5.1.

• Số các chỉnh hợp lặp chập k của n phần tử là Akn = nk (theo quy tắc nhân)
• Chỉnh hợp có lặp là khi giữa các phần tử thì yếu tố thứ tự là cốt lõi, còn
yếu tố khác biệt không quan trọng.

1.5.2



• Số các tổ hợp lặp chập k của n phần tử là: Ckn = Ckn+k−1 = Cn−1
n+k−1
• Tổ hợp có lặp là khi một phần tử có thể xuất hiện nhiều lần và thứ tự của
các phần tử là không cần để ý.

1.6

Nhị thức Newton

1.6.1

Công thức nhị thức Newton

n−1
+ Cnn bn =
(a + b)n = C0n an + C1n an−1 b + ... + Cn−1
n ab

n

Ckn an−k bk

k=0

1.6.2

Các tính chất của công thức nhị thức (a + b)n

• Số các số hạng là n + 1.

+ ... + Cm
= Ckm+n .
n
m .Cn

Chú ý. Ta có khai triển:

(x + y + z)n =

1.7

n!
.xk .y m .z l
k!m!l!
k+m+l=n

Tam giác Pascal

Các hệ số của khai triển Newton của nhị thức (a + b)n có thể được sắp xếp
thành tam giác sau đây (gọi là tam giác Pascal).

1
1
1
1
1
1

1
2

Một số phương pháp giải các bài toán
tổ hợp đếm
Bài toán đếm là bài toán đặc trưng của các dạng toán về tổ hợp. Bài toán
đếm nhằm trả lời câu hỏi: Có bao nhiêu "cấu hình" thỏa mãn điều kiện đã cho.
Phương pháp đếm thường dựa vào một số nguyên lý cơ bản và một số kết quả
đếm của các cấu hình đơn giản.

2.1

Phương pháp đếm trực tiếp

Phương pháp này đòi hỏi phải nắm vững các quy tắc đếm: quy tắc nhân,
quy tắc cộng, các khái niệm, công thức của chỉnh hợp, tổ hợp, hoán vị, tổ hợp
có lặp, chỉnh hợp có lặp. Vận dụng một cách linh hoạt các quy tắc đó.
Chú ý.

• Cần phân biệt khi nào sử dụng quy tắc nhân khi nào sử dụng quy tắc cộng
thông qua Nhận xét 1.3.1.

• Liệt kê các trường hợp, ghép nhóm, xen nhóm,. . .
• Sử dụng chỉnh hợp, chỉnh hợp lặp, tổ hợp, tổ hợp lặp, hoán vị, hoán vị lặp
một cách thích hợp.
Ví dụ 2.1.1. Trong một trường, khối 11 có 280 học sinh nam và 325 học sinh
nữ. Hỏi có bao nhiêu cách chọn.

14


i) Một học sinh ở khối 11 đi dự dạ hội của học sinh thành phố.
ii) Hai học sinh trong đó có một học sinh nam và một học sinh nữ.

(cách chọn)
Theo quy tắc cộng ta có : 60 + 18 + 12 = 90 cách chọn 3 người thỏa yêu cầu
bài toán.
Ví dụ 2.1.4. Có 8 người trong thang máy của một ngôi nhà 6 tầng. Họ đi ra
theo 3 nhóm: 1 người, 3 người và 4 người. Hỏi có bao nhiêu cách thực hiện việc
đó, nếu ở mỗi tầng chỉ có một nhóm đi ra và thứ tự đi ra của các người trong
một nhóm không có ý nghĩa gì?
Giải
Để chia 8 người thành 3 nhóm với số lượng mỗi nhóm lần lượt là 1 người, 3
người và 4 người thì áp dụng công thức hoán vị lặp ta có:
8!
P8 =
1! × 3! × 4!
Sau đó, ta chọn 3 trong 6 tầng và phân phối các tầng ấy cho 3 nhóm khác
nhau ta được: C36 = 20(cách)
Vậy theo quy tắc nhân, số tất cả các cách thực hiện theo yêu cầu của bài
toán là: P8 × C36 = 5600 (cách)
Nhận xét 2.1.1. Phương pháp này dễ suy luận theo giả thiết của bài toán.
Tuy nhiên có hạn chế, đó là nếu tính trực tiếp mà phải xét quá nhiều trường
hợp dẫn đến nhầm lẫn và đôi khi không thể ra được kết quả.

16


2.2

Phương pháp đếm loại trừ

Cở sở của phương pháp này xuất phát từ Nguyên lý bù trừ: "Nếu B là một
tập con của tập hữu hạn A. Gọi CA (B) là phần bù của B trong A. Khi đó:

• Xét abcd có dạng aaax
Ta có: a có 9 cách chọn; x có 9 cách chọn

• Xét abcd có dạng xaaa
Ta có: x có 9 cách chọn; a có 8 cách chọn (trừ x và 0)
Suy ra số các số tự nhiên có 4 chữ số mà có một chữ số lặp lại đúng 3
lần có: 9.9.3 + 9.8 + 9 = 324 (cách chọn)
Vì vậy số các số thỏa mãn yêu cầu bài toán có : 9000 − 324 = 8676 (cách chọn).
Nhận xét 2.2.1. Phương pháp này khắc phục được những yếu điểm mà phương
pháp trực tiếp tỏ ra vướng mắc. Tuy nhiên, phương pháp này chỉ phát huy được
hiệu quả của nó khi mà ta tìm được bài toán đối của bài toán trực tiếp và số
các trường hợp là ít và ít hơn phương pháp trực tiếp.

2.3

Phương pháp tạo vách ngăn

Khi bài toán yêu cầu xếp hai hay nhiều phần tử không đứng cạnh nhau thì
ta có thể tạo ra các "vách ngăn" các phần tử này trước khi xếp chúng.
Nội dung: Đếm theo hai bước:
Bước 1: Sắp xếp m đối tượng vào m vị trí sẽ tạo ra m + 1 vách ngăn
Bước 2: Sắp xếp đối tượng khác theo yêu cầu bài toán từ m + 1 vách ngăn nói
trên.
Ví dụ 2.3.1. Có 6 học sinh và hai thầy giáo được xếp hàng ngang. Hỏi có bao
nhiêu cách xếp mà hai thầy giáo không đứng cạnh nhau.
Giải
19


Trước hết, xếp 6 học sinh thành một hàng ngang có: 6! cách

2.4

Phương pháp "dán" phần tử

Đây là phương pháp đối lập với phương pháp tạo "vách ngăn". Vì đối tượng
mà phương pháp này áp dụng lên là các bài tập yêu cầu xếp hai hay nhiều
phần tử đứng cạnh nhau trên cùng một hàng (cột).
Đối với phương pháp này, ta sẽ "dán" những phần tử đứng cạnh nhau thành
một phần tử đại diện thay thế cho các phần tử này.
Một số ví dụ cho phương pháp.
Ví dụ 2.4.1. Một nhóm có 4 học sinh lớp A, có 3 học sinh lớp B và 5 học sinh
lớp C. Hỏi có bao nhiêu cách sắp xếp các học sinh trên thành một hàng ngang
sao cho các học sinh lớp A đứng cạnh nhau và các học sinh lớp B cũng đứng
cạnh nhau.
Giải
Vì các học sinh lớp A đứng cạnh nhau. Nên ta "dán" các học sinh này lại
thành 1, gọi là học sinh a.
Vì các học sinh lớp B đứng cạnh nhau. Nên ta "dán" các học sinh này lại
thành 1, gọi là học sinh b.
Khi đó, ta xếp 7 học sinh (học sinh a, học sinh b, và 5 học sinh lớp C) thành
một hàng ngang, có 7! cách.
Sau đó, sắp xếp các học sinh trong lớp A, có 4! cách
Sau đó, sắp xếp các học sinh trong lớp B, có 3! cách
Do đó, số cách sắp xếp các học sinh trên thành một hàng ngang sao cho các
học sinh lớp A đứng cạnh nhau và các học sinh lớp B cũng đứng cạnh nhau là:

7! × 3! × 4! = 725760 cách.
21




Phương pháp thêm bớt

Phương pháp này là tổng quát hóa của Nguyên lý thêm bớt dạng tổng quát:
n

|A1 ∪ A2 ∪ ... ∪ An | =

n

|Ai |−
i=1

|Ai ∩ Ak | + ...
1 i k n

... + (−1)n−1 |A1 ∩ A2 ∩ ... ∩ An |
Xét các ví dụ để thấy rõ hơn về ý tưởng của phương pháp này.

22