ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THỊ MINH PHƯƠNG

MỘT SỐ NGUYÊN LÝ VÀ KỸ THUẬT
ĐỂ GIẢI CÁC BÀI TOÁN TỔ HỢP

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên - 2017


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THỊ MINH PHƯƠNG

MỘT SỐ NGUYÊN LÝ VÀ KỸ THUẬT
ĐỂ GIẢI CÁC BÀI TOÁN TỔ HỢP

LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số:

60 46 01 13

NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TSKH. Đặng Hùng Thắng

Thái Nguyên - 2017

Định lý nhị thức . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.2

Các đồng nhất thức tổ hợp . . . . . . . . . . . . . . . . . . . .

6

1.1.3

Tam giác Pascal . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.1.4

Đồng nhất thức Chu Shih-Chieh . . . . . . . . . . . . . . . . .

13

1.1.5

Một số tính chất của hệ số nhị thức . . . . . . . . . . . . . . . .

19

Hệ số đa thức và tính chất . . . . . . . . . . . . . . . . . . . . . . . . .


Nguyên lý bao hàm – loại trừ . . . . . . . . . . . . . . . . . . . . . . .

40

2.3

Hàm sinh và quan hệ truy hồi . . . . . . . . . . . . . . . . . . . . . . .

44

2.3.1

Các hàm sinh thông thường . . . . . . . . . . . . . . . . . . .

44

2.3.2

Phân hoạch nguyên . . . . . . . . . . . . . . . . . . . . . . . .

54

Các bài toán áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

2.4
Kết luận

73

bậc của đa thức P(x)

a ≡ b (mod p)

a đồng dư với b theo modulo p

gcd(a, b)

ước chung lớn nhất của hai số nguyên a và b

a|b

a là ước của b

a b

a không phải là ước của b

x
m

∑ ai
i=1
m

∏ bi

phần nguyên của x
ký hiệu tổng a1 + a2 + · · · + am
ký hiệu tích b1 b2 · · · bm

giải) các bài tập nâng cao về tổ hợp và sáng tác ra những bài toán tổ hợp mới.
Tác giả cố gắng phấn đấu để bản luận văn sẽ cung cấp thêm một tài liệu tham
khảo tốt về tổ hợp cho học sinh phổ thông, đặc biệt là dành cho các em học sinh
có năng khiếu môn toán. Tác giả hy vọng luận văn sẽ đáp ứng được phần nào lòng
yêu thích khám phá toán học của các em học sinh đồng thời cũng là một tài liệu
hữu ích để các bạn đồng nghiệp cùng tham khảo. Ngoài ra thông qua việc viết luận
văn, tác giả có cơ hội mở rộng nâng cao hiểu biết về toán sơ cấp nói chung và tổ
hợp nói riêng, nâng cao kỹ năng các giải các bài toán tổ hợp, phục vụ tốt cho việc
giảng dạy môn toán ở trường phổ thông.
Nội dung của luận văn được trình bày trong hai chương:
Chương 1. Hệ số nhị thức và hệ số đa thức. Trong chương này chúng tôi trình
bày định lí về hệ số của nhị thức, hệ số của đa thức. Các tính chất của hệ số nhị


4
thức và hệ số của đa thức và một số ví dụ vận dụng trong giải các bài toán tổ hợp
Chương 2. Nguyên lý Dirrichlet và Nguyên lý bao hàm – loại trừ và hàm
sinh. Trong chương này chúng tôi trình bày các nguyên lý cơ bản, như nguyên lý
Dirichlet, nguyên lý bao hàm – loại trừ và hàm sinh. Một số ví dụ và bài toán áp
dụng các nguyên lý trên.
Trong thời gian học tập và hoàn thành luận văn, tôi đã nhận được sự hướng dẫn
của GS. TSKH. Đặng Hùng Thắng (Trường ĐHKHTN - ĐHQG Hà Nội). Tác giả
xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy, người đã đặt vấn đề
nghiên cứu, dành nhiều thời gian hướng dẫn và giải đáp những thắc mắc của tác
giả trong suốt quá trình làm luận văn.
Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học – Đại
học Thái Nguyên, Ban Chủ nhiệm Khoa Toán–Tin, cùng các giảng viên đã tham
gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu.
Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến gia đình vì
những động viên và chia sẻ những khó khăn để tác giả hoàn thành tốt luận văn này.

xyn−1 +
y
0
1
n−1
n
n
n n−r r
x y.
=∑
r
r=0

(x + y)n =

Chứng minh thứ nhất - Quy nạp toán học. Với n = 0, kết quả là tầm thường như
là (x + y)0 = 1 =

0
0

x0 y0 . Giả sử nó xảy ra khi n = k với một số nguyên k ≥ 0 nào

đó, đó là
k

(x + y)k =

∑


k k+1−r r k k k−r r+1
x
y ∑
x y
r
r=0 r

k k+1
k k
k k−1 2
k
x +
x y+
x y +···+
xyk
0
1
2
k


6
+

k k
k k−1 2
k
k k+1
x y+
x y +···+

x +
x y+···+
xyk +
y ,
0
1
k
k+1

đây là điều ta cần. Phép chứng minh hoàn thành bởi nguyên lý quy nạp toán học.

Chứng minh thứ hai - Phương pháp tổ hợp. Đủ để chứng minh rằng hệ số của xn−r yr
trong khai triển của (x + y)n là

n
r

.

Để khai triển tích
(x + y)n = (x + y)(x + y) · · · (x + y),
n

ta chọn một trong hai x hoặc y từ mỗi nhân tử (x + y) và sau đó nhân chúng với
nhau. Như vậy, để tạo thành xn−r yr , trước hết ta chọn r trong n nhân tử (x + y) và
sau đó chọn “y” từ r nhân tử đã chọn (và tất nhiên chọn “x” từ phần còn lại (n − r)
nhân tử). Bước đầu tiên có thể được thực hiện theo
là một cách. Do đó, số cách để tạo thành xn−r yr là

1.1.2

r
0
1
n

(1.1)


7
Chứng minh thứ nhất. Cho x = y = 1 trong Định lý 1.1.1, ta có được ngay
n

∑

r=0

n
= (1 + 1)n = 2n .
r

Và điều này kết thúc phép chứng minh.
Chứng minh thứ hai. Cho X là một tập hợp có n phần tử và P(X) là tập hợp tất
cả các tập hợp con của X. Ta sẽ đếm lực lượng |P(X)| theo hai cách.
Với mỗi r = 0, 1, . . . , n, số tập con có r phần tử của X là

n
r

theo định nghĩa.


n
= 0,
−
+
− · · · + (−1)n
n
0
1
2
n
n
n
+
+···+
+··· =
0
2
2k
n
n
n
=
+
+···+
+ · · · = 2n−1 .
1
3
2k + 1
=


n
n
n
n
n
=
+2
+3
+···+n
= n · 2n−1 .
r
1
2
3
n

(1.4)


8
Chứng minh thứ nhất. Cho x = 1 Định lý 1.1.1 cho ta
n

(1 + y)n =

∑

r=0

n r

n n−1
=
r
r r−1
có thể được viết lại thành
r

với điều kiện là r ≥ 1

n
n−1
=n
.
r
r−1

Do đó
n

n
n
n−1
n
n−1
∑ r r = ∑ n r−1 = n ∑ r−1
r=1
r=1
r=1
n−1


n

r=1


Luận văn đầy đủ ở file: Luận văn full