Các nguyên lý và kỹ thuật cơ bản trong tổ hợp.

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

TRẦN ĐỨC VINH

CÁC NGUYÊN LÝ VÀ KỸ THUẬT

CƠ BẢN TRONG TỔ HỢP

Chuyên ngành: Phương pháp toán sơ cấp

Mãsố: 60.46.01.13

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2015

Công trình được hoàn thành tại

ĐẠI HỌC ĐÀ NẴNG

Người hướng dẫn khoa học: TS. NGUYỄN DUY THÁI SƠN

Phản biện 1: TS. LÊ HOÀNG TRÍ

Phản biện 2: TS. PHẠM HỮU KHÁNH

Luận văn được bảo vệ tại Hội đồng chấm Luận văn tốt

nghiệp thạc sĩ khoa học họp tại Đại học Đà Nẵng vào ngày

19 tháng 12 năm 2015.

Có thể tìm Luận văn tại:

- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng

- Thư viện trường Đại học sư phạm, Đại học Đà Nẵng

1

MỞ ĐẦU

1. Lý do chọn đề tài

Trong những năm qua, Tổ hợp đã trở thành một phần

căn bản trong các giáo trình cho học sinh và sinh viên các

trường THPT và đại học trên thế giới. Các nguyên lý và kỹ

thuật trong Tổ hợp ngày càng có nhiều ứng dụng trong nhiều

lĩnh vực khác, đặc biệt là trong khoa học máy tính và lý thuyết

toán tử. Các bài toán trong Tổ hợp không chỉ thách thức các

nhà nghiên cứu mà còn xuất hiện rất thường xuyên trong các

cuộc thi Toán học, đặc biệt là kỳ thi Olympic Toán học quốc

tế (IMO).

Tuy nhiên, hiện nay tài liệu tiếng Việt về Tổ hợp chưa

nhiều. Trên thực tế, giáo viên THPT ở nước ta chưa được đào

tạo bài bản, chuyên sâu về tổ hợp. Sinh viên và học sinh Việt

Nam thường tỏ ra lúng túng trước các bài toán Tổ hợp. Trong

luận văn này, tôi sẽ cố gắng tìm hiểu các nguyên lý và kỹ thuật

(từ cơ bản đến nâng cao) thường dùng khi giải các bài toán về

Tổ hợp. Bản thân là một giáo viên phổ thông, tôi hi vọng sẽ

khám phá được nhiều điều thú vị khi rèn luyện các kỹ năng Tổ

hợp. Mong rằng luận văn này - sau khi được hoàn thành - sẽ

cung cấp thêm một tài liệu về Tổ hợp đáp ứng được phần nào

2

lòng yêu thích Toán học của học sinh, phục vụ cho công tác

bồi dưỡng học sinh giỏi. Đồng thời đây cũng là một tài liệu để

mọi người quan tâm đến Tổ hợp tham khảo.

Với những lý do trên, dưới sự hướng dẫn của TS.

Nguyễn Duy Thái Sơn, tôi chọn “Các nguyên lý và kỹ thuật cơ

bản trong Tổ hợp” làm đề tài nghiên cứu cho luận văn Thạc sĩ

của mình.

2. Mục đích và nhiệm vụ nghiên cứu

Tôi mong muốn tìm kiếm được nhiều tài liệu từ các

nguồn khác nhau, nghiên cứu kỹ càng các tài liệu đó, cố gắng

lĩnh hội đầy đủ các kiến thức về Tổ hợp liên quan đến đề tài.

Từ đó, trình bày các kiến thức này trong luận văn theo một thể

khép kín.

Trong luận văn này, tôi cũng cố gắng tìm tòi lời giải

cho các bài toán (theo mức độ từ dễ đến khó) thu thập được từ

nhiều nguồn khác nhau, đặc biệt là từ những kỳ thi Olympic

Toán học và tôi hy vọng luận văn có thể được sử dụng như

một tài liệu tham khảo bổ ích cho học sinh, sinh viên và giáo

viên.

3

3. Đối tượng và phạm vi nghiên cứu

3.1. Đối tượng nghiên cứu: Các nguyên lý và kỹ thuật

trong Tổ hợp.

3.2. Phạm vi nghiên cứu: Các kiến thức về Tổ hợp được

dùng để giảng dạy cho học sinh chuyên Toán ở các trường

THPT, các bài toán tổ hợp thường gặp trong các kỳ thi chọn

học sinh giỏi Toán trong nước và Quốc tế.

4. Phương pháp nghiên cứu

- Cơ bản sử dụng phương pháp nghiên cứu tài liệu

(sách, báo và các tài liệu trên internet có liên quan đến đề tài

của luận văn) để lĩnh hội, trau dồi kiến thức về Tổ hợp và tập

hợp các bài toán phục vụ cho yêu cầu của đề tài.

- Trao đổi, thảo luận với người hướng dẫn khoa học.

5. Giả thuyết khoa học

Xây dựng một giáo trình có tính hệ thống, khép kín và

có thể giảng dạy với thời lượng chấp nhận được cho học sinh

chuyên toán bậc trung học phổ thông và cho sinh viên toán tại

các trường đại học.

4

Xây dựng được một hệ thống các bài toán (cũ và mới)

với các mức độ khó dễ khác nhau.

6. Cấu trúc luận văn

Cấu trúc của luận văn gồm:

Phần mở đầu

Chương 1: Hoán vị, Chỉnh hợp và Tổ hợp

Chương 2: Hệ số nhị thức và hệ số đa thức

5

CHƯƠNG 1

HOÁN VỊ VÀ TỔ HỢP

1.1. Hai nguyên lý đếm cơ bản:

Trong cuộc sống hằng ngày, chúng ta thường phải liệt

kê “các sự kiện” như sắp xếp các đối tượng theo một cách nào

đó, phân chia các đối tượng theo một điều kiện nhất định, phân

phối các đối tượng theo một đặc điểm kỹ thuật, v.v… Ví dụ,

chúng ta có thể gặp phải bài toán đếm có dạng như sau:

“Có bao nhiêu cách sắp xếp 5 chàng trai và 3 cô gái trên một

hàng sao cho không có hai cô gái nào đứng cạnh nhau?”

“Có bao nhiêu cách chia một nhóm 10 người thành 3 nhóm

gồm một nhóm 4 người, một nhóm 3 người, một nhóm 2 người

và giữ lại một người?”

Đây là hai bài toán đếm rất đơn giản liên quan đến những gì

mà chúng ta gọi là “hoán vị” và “tổ hợp”. Trước khi chúng ta

giới thiệu trong ba phần tiếp theo của những gì gọi là hoán vị

và tổ hợp, chúng ta nêu hai nguyên tắc cơ bản trong tất cả các

bài toán đếm.

6

Nguyên lý cộng (Addition Principle (AP))

Giả sử có:

1 n cách thực hiện phương án 1 E ,

2 n cách thực hiện phương án 2 E ,



k n cách thực hiện phương án , Ek

trong đó k 1 . Nếu cách thực hiện mỗi phương án Ei

không phụ thuộc vào mọi cách thực hiện phương án Ej

(1 , , )    i j k i j thì số cách để thực hiện ít nhất một

trong các phương án 1 2 E E, , ,  hoặc Ek xảy ra là:

1 2

1

... .

k

k i

i

n n n n 

    

Sử dụng ngôn ngữ của lý thuyết tập hợp, ta có một dạng

tương đương của nguyên lý cộng như sau:

7

Cho 1 2 , ,..., A A Ak là k tập hữu hạn, với k 1 . Nếu k

tập này đôi một không giao nhau thì:

1 2

1 1

... .

k k

i k i

i i

A A A A A

 

      

Nguyên lý nhân (Multiplication Principle (MP))

Giả sử công việc E bao gồm r công đoạn

1 2 , ,. , .. , E E Er và:

Có 1 n cách thực hiện công đoạn 1 E ,

Có 2 n cách thực hiện công đoạn 2 E ,



Có r n cách thực hiện công đoạn . Er

Khi đó, số cách để thực hiện công việc E là:

1 2

1

... . r

r

i

i

n n n n 

   

8

Sử dụng ngôn ngữ của lý thuyết tập hợp, ta có một dạng

tương đương của nguyên lý nhân như sau:

Giả sử

  

1 2

1 2

1

...

, ,..., | , 1,2,...,

i

r

i

r

r i i

A A

a a

A A

a a A i r











 





ký hiệu của tích Đề-các của r tập hữu hạn 1 2 , ,..., . A A Ar

Khi đó:

1 1

1 2 ... . i i

i

r

r r

i

A A A A A  

      

Với tư cách là các mệnh đề toán học, cả nguyên lý (AP)

và (MP) đều thực sự rất ‘tầm thường’. Đây chính là lý do vì

sao sinh viên thường xem nhẹ chúng. Trên thực tế, cả hai

nguyên lý này đều đóng vai trò rất cơ bản trong việc giải quyết

các bài toán đếm. Để minh chứng cho điều đó, trong luận văn

này, các bài toán đếm cho dù có phức tạp đến đâu, ta cũng có

thể chia nhỏ chúng thành các bài toán đơn giản hơn, và từ đó

sử dụng hai nguyên lý này để giải quyết.

9

1.2. Hoán vị

Cho tập hợp A  a1 2 , ,..., a an  gồm n phần tử phân

biệt. Với 0 ,  r n một r-hoán vị của tập A là một cách sắp

xếp r phần tử bất kỳ của A trên một hàng. Khi r n  , một n￾hoán vị của tập A được gọi đơn giản là một hoán vị của A.

1.3. Hoán vị vòng tròn

Hoán vị được thảo luận trong mục 1.2 là số cách sắp

xếp các phần tử trên một hàng. Có những hoán vị đòi hỏi sắp

xếp các phần tử trên một đường tròn khép kín. Những hoán vị

như thế được gọi là hoán vị vòng tròn.

Xét bài toán sắp xếp 3 phần tử phân biệt a b c , , vào 3 vị trí

trên một vòng tròn. Giả sử 3 vị trí này được đánh số 1 , 2    và

3 như hình 1.3.1. Khi đó, 3 cách sắp xếp của a b c , , được chỉ ra

trong hình 1.3.1 có thể xem như là các hoán vị:

abc cab bca , ,

bca abc cab

b

a c

c

c b b a

a

(3) (2)

(1)

(3) (2)

(1) (1)

(3) (2)

Hình 1.3.1.

10

Trong trường hợp này, các “hoán vị vòng tròn” như

vậy được đồng nhất với hoán vị thông thường, và vì vậy

không có gì đáng bàn. Để có được một cái gì đó thú vị hơn,

chúng ta hãy bỏ việc đánh số các vị trí.

Nguyên lý Bù trừ

(Principle of Complementation (CP))

Nếu A là một tập con của tập hữu hạn U , thì

U A U A \ .  

1.4. Tổ hợp

Cho tập A gồm n phần tử phân biệt. Một tổ hợp của

tập A đơn giản là một tập con của tập A. Nói một cách chính

xác hơn, với 0  r n , một r-tổ hợp của tập A là một tập con

gồm r phần tử của tập A.

Sự khác nhau giữa hoán vị và tổ hợp của các phần tử là

gì? Một hoán vị là một sự sắp xếp các phần tử theo một thứ tự

nhất định, do đó sự sắp xếp các phần tử này là rất quan trọng.

Trong khi một tổ hợp thì chỉ là một tập hợp các phần tử, nên

sự sắp xếp các phần tử này là không quan trọng.

11

   

!

! ! !

n

r n r

n r

P n C

r n r r    

1.5. Nguyên lý đơn ánh và song ánh

Giả sử một nhóm gồm n sinh viên tham dự một bài giảng

trong giảng đường gồm 200 chổ ngồi. Với giả thiết không có bất

kỳ sinh viên nào ngồi hơn một chổ và cũng không có hai sinh viên

ngồi chung một chổ. Nếu biết rằng, mỗi sinh viên ngồi một chổ thì

chúng ta sẽ có n  200 . Hơn nữa, nếu giảng đường không còn chổ

trống, thì chúng ta chắc chắn rằng n  200 mà không cần đếm số

sinh viên. Đây là một ví dụ minh họa cho hai nguyên lý đơn giản

mà chúng ta sẽ nêu ra.

Nguyên lý đơn ánh (The Injection Principle (IP))

Cho A B, là hai tập hợp hữu hạn. Nếu có một đơn ánh

từ A vào B, thì:

A  B .

Nguyên lý song ánh (The bijection Principle (BP))

Cho A B, là hai tập hợp hữu hạn. Nếu có một song ánh