Một số nguyên lý và kỹ thuật để giải các bài toán tổ hợp

ĐẠ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

i

Mục lục

Danh sách kí hiệu ii

Mở đầu 3

Chương 1. Hệ số nhị thức và hệ số đa thức 5

1.1 Hệ số nhị thức và tính chất . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 Đị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

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

1.2.1 Hệ số đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.2.2 Định lý đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.3 Một số bài toán vận dụng . . . . . . . . . . . . . . . . . . . . . . . . . 28

Chương 2. Nguyên lý Dirrichlet, nguyên lý bao hàm – loại trừ, và hàm sinh 38

2.1 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.2 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

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

Kết luận 73

Tài liệu tham khảo 74

ii

Danh sách kí hiệu

Z tập hợp các số nguyên

N tập hợp các số tự nhiên

n! n giai thừa, được xác định bởi n! = 1 · 2 · 3···n

￾

n

r

hoặc C

r

n

số tổ hợp chập r của n phần tử

degP(x) 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

bxc phần nguyên của x

m

∑

i=1

ai ký hiệu tổng a1 +a2 +···+am

m

∏

i=1

bi ký hiệu tích b1b2 ···bm

P(X) tập tất cả các tập con của tập hợp X

|A| số phần tử của tập hợp

3

Mở đầu

Trong nhiều năm tổ hợp luôn là một chuyên đề lớn đối với các học viên chuyên

ngành toán sơ cấp. Các nguyên tắc và kĩ thuật cơ bản trong tổ hợp ngày càng có

nhiều ứng dụng trong các lĩnh vực khác, đặc biệt trong khoa học máy tính. Nhận

thức được vai trò của lý thuyết tổ hợp đối với đời sống hiện đại nên lý thuyết tổ

hợp đã được đưa vào chương trình học phổ thông và chiếm một phần trong các kì

thi toán quốc gia và quốc tế. Trong chương trình bậc đại học và cao học, học viên

chưa có điều kiện làm quen và nghiên cứu các nguyên lý và kĩ thuật trong đại số

tổ hợp hoặc có thì cũng không nhiều và không sâu. Mặt khác, ở nước ta tài liệu về

tổ hợp chưa nhiều.

Mục tiêu của đề tài luận văn là tìm hiểu một số nguyên lý và kỹ thuật để giải

các bài toán tổ hợp nâng cao như: Nguyên lý Dirrichlet và Nguyên lý bao hàm và

loại trừ, kỹ thuật sử dụng hệ số nhị thức, hệ số đa thức, quan hệ truy hồì và phương

pháp hàm sinh.

Về mặt ứng dụng, luận văn sẽ áp dụng lý thuyết để soi sáng những bài toán

tổ hợp ở phổ thông, phân loại và hệ thống hoá (theo dạng cũng như phương pháp

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.

Thái Nguyên, ngày 04 tháng 11 năm 2017

Tác giả luận văn

Nguyễn Thị Minh Phương

5

Chương 1

Hệ số nhị thức và hệ số đa thức

1.1 Hệ số nhị thức và tính chất

1.1.1 Định lý nhị thức

Trong phần này, chúng tôi trình bày về định lý nhị thức, các tính chất của hệ số nhị

thức và ứng dụng trong các bài toán tổ hợp. Chúng ta bắt đầu với dạng đơn giản

sau đây của Định lý nhị thức được phát hiện bởi Isaac Newton (1646-1727) năm

1676.

Định lí 1.1.1. Với mỗi số nguyên bất kỳ n ≥ 0, ta có

(x+y)

n =



n

0



x

n +



n

1



x

n−1

y+···+



n

n−1



xyn−1 +



n

n



y

n

=

n

∑

r=0



n

r



x

n−r

y

r

.

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

x

0

y

0

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

đó, đó là

(x+y)

k =

k

∑

r=0



k

r



x

k−r

y

r

.

Xét n = k +1. Quan sát thấy rằng

(x+y)

k+1 = (x+y)(x+y)

k

= (x+y)

k

∑

r=0



k

r



x

k−r

y

r

(bởi giả thiết quy nạp)

=

k

∑

r=0



k

r



x

k+1−r

y

r

k

∑

r=0



k

r



x

k−r

y

r+1

=



k

0



x

k+1 +



k

1



x

k

y+



k

2



x

k−1

y

2 +···+



k

k



xy