Một số dạng bài toán đếm ở phổ thông và phương pháp giải

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

ĐẠI HỌC ĐÀ NẴNG

LÊ THỊ HƯỜNG

MỘT SỐ DẠNG BÀI TOÁN ĐẾM

Ở PHỔ THÔNG VÀ PHƯƠNG PHÁP GIẢI

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

Mã số: 60.46.40

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

Đà Nẵng - Năm 2013

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: PGS.TSKH. TRẦN QUỐC CHIẾN

Phản biện 1: TS. NGUYỄN NGỌC CHÂU

Phản biện 2: TS. HOÀNG QUANG TUYẾN

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 25 tháng 5

năm 2013.

* Có thể tìm hiểu 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:

Lí thuyết tổ hợp là một phần quan trọng của Toán học rời rạc

chuyên nghiên cứu sự phân bố các phần tử vào các tập hợp, nó được

hình thành như một nghành toán học mới vào khoảng thế kỉ 17 bằng

một loạt các công trình nghiên cứu nghiêm túc của các nhà Toán học

xuất sắc như Pascal, Fermat, Leibnitz, Euler.... Thông thường các

phần tử này là hữu hạn và việc phân bố chúng phải thỏa mãn những

điều kiện nhất định nào đó, tùy theo yêu cầu của bài Toán cần nghiên

cứu. Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp. Với các

cấu hình tổ hợp thường có các dạng bài toán tồn tại, bài toán đếm,

bài toán liệt kê, bài toán tối ưu. Để trả lời cho những câu hỏi: Có bao

nhiêu cấu hình tổ hợp thuộc dạng đang xét? Chứng minh sự tồn tại

hoặc không tồn tại của một cấu hình tổ hợp nào đó...

Bài toán đếm là một trong những bài toán lý thú của tổ hợp,

đồng thời nó cũng là một minh chứng rõ ràng cho việc ứng dụng của

môn Toán đối với thực tiễn cuộc sống (như các bài về số cách sắp

xếp đối tượng trên hàng ngang hay vòng tròn, đếm số đường đi...).

Song chúng lại không đòi hỏi người giải nhiều về vốn kiến thức và

kỹ năng tính toán, chúng chủ yếu đòi hỏi sự chặt chẽ trong việc xét

các khả năng, sự sáng tạo trong việc đưa ra một mô hình cụ thể, sự

linh hoạt trong việc vận dụng các phương pháp và sự khéo léo trong

việc gỡ rối các tình huống, vấn đề... bởi không phải trong trường hợp

nào áp dụng trực tiếp các quy tắc đếm cơ bản và các đối tượng tổ hợp

cũng đem lại kết quả mong muốn. Với những bài toán như vậy cần

những phương pháp nâng cao hơn như phương pháp sử dụng ánh xạ,

nguyên lý bù trừ, phương pháp phân hoạch tập hợp, phương pháp

quỹ đạo, đa thức quân xe, phương pháp thiết lập hệ truy hồi, phương

2

pháp thêm bớt, phương pháp quan hệ đệ quy, sử dụng số phức,

phương pháp hàm sinh...

Với mong muốn tìm hiểu và hệ thống hóa một số dạng toán

xoay quanh bài toán đếm mà không đi sâu vào lí thuyết của vấn đề

này, nhằm cung cấp một tài liệu nhỏ về bài toán tổ hợp cho học sinh

phổ thông. Qua đó, phục vụ công tác giảng dạy sau này. Chính vì lí

do trên tôi chọn đề tài “Một số dạng bài toán đếm ở phổ thông và

phương pháp giải”.

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

2.1. Đối tượng nghiên cứu:

Một số nguyên lý: Nguyên lý cộng, nguyên lý nhân, nguyên lý

bù trừ, công thức truy hồi.

Phương pháp đếm: sử dụng ánh xạ, sử dụng hàm sinh, truy

hồi, nguyên lý bù trừ, đa thức quân xe.

2.2. Phạm vi nghiên cứu:

Một số cấu hình tổ hợp thuộc chuyên nghành phương pháp

Toán sơ cấp và đặc biệt ứng dụng trong chương trình toán phổ thông

và toán học dành cho học sinh giỏi các đội tuyển Olympic.

3. Mục đích nghiên cứu:

- Hệ thống và phân loại một số dạng bài toán đếm theo từng

phương pháp giải

- Chọn lọc, giới thiệu, tìm kiếm những ứng dụng của một số

nguyên lý đếm và phương pháp đếm gần gũi trong chương trình toán

phổ thông.

4. Nhiệm vụ nghiên cứu:

- Nghiên cứu một số phương pháp giải bài toán đếm trong lí

thuyết tổ hợp dựa trên phương pháp xây dựng ánh xạ, sử dụng hàm

sinh, công thức truy hồi, nguyên lý bù trừ, đa thức quân xe.

3

- Thực hành trên một số bài toán cụ thể trong chương trình

toán phổ thông, các đề thi đại học, thi học sinh giỏi toàn quốc,

olympic.

5. Giả thiết khoa học:

Việc khai thác các dạng bài toán đếm theo từng phương pháp

giải sẽ tạo cho học sinh biết nhận thức vấn đề, lựa chọn phương pháp

phù hợp với từng dạng bài toán cụ thể. Từ bài toán đếm đơn giản đến

bài toán trong các kỳ thi Olympic.

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

Đề tài này sử dụng các phương pháp nghiên cứu:

- Nghiên cứu tư liệu: Tạp chí toán học tuổi trẻ, các đề tài

nghiên cứu có liên quan.

- Tiếp cận lịch sử: sưu tầm, phân tích và tổng hợp tư liệu.

- Tiếp cận hệ thống.

- Thực nghiệm sư phạm ở trường phổ thông.

7. Ý nghĩa khoa học và thực tiễn đề tài:

- Hệ thống và phân loại một số dạng của bài toán đếm và

phương pháp giải quyết một số dạng bài toán khó ở phổ thông, góp

phần cho học sinh và giáo viên tiếp cận nhận dạng bài toán nhanh

chóng cùng phương pháp giải hợp lí.

- Đề tài trình bày logic, khoa học, rõ ràng và dễ hiểu.

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

Ngoài phần mở đầu, kết luận và tài liệu tham khảo trong luận

văn gồm có các chương như sau :

CHƯƠNG 1: ĐẠI CƯƠNG VỀ TỔ HỢP

CHƯƠNG 2: CÁC PHƯƠNG PHÁP ĐẾM NÂNG CAO

CHƯƠNG 3: ỨNG DỤNG

4

CHƯƠNG 1

ĐẠI CƯƠNG VỀ TỔ HỢP

1.1. TẬP HỢP

1.1.1. Các khái niệm cơ bản

• Định nghĩa

• Biểu diễn tập hợp

- Liệt kê các phần tử

- Chỉ ra tính chất đặc trưng

• Lực lượng tập hợp

• Quan hệ bao hàm

1.1.2. Phép toán tập hợp

• Phép hiệu

• Phần bù.

• Phép hợp

• Phép giao.

• Phân hoạch.

• Định lí.

- Luật kết hợp

- Luật giao hoán

- Luật phân bố

- Luật đối ngẫu De Morgan

1.1.3. Tích Đề-Các

 Định nghĩa

 Định lí

1.2. QUAN HỆ

1.2.1. Định nghĩa

 Ví dụ

1.2.2. Quan hệ tương đương và phân hoạch

5

 Ví dụ

 Định lí 1

 Định lí 2

1.2.3. Quan hệ thứ tự

 Định nghĩa.

 Kí hiệu

 Ví dụ

 Định lí 3

 Hệ quả

1.3. ÁNH XẠ

1.3.1. Định nghĩa

 Ví dụ 1

 Ví dụ 2

 Ví dụ 3

 Định lý 1

 Ví dụ

1.3.2. Các phép toán ánh xạ

 Định nghĩa

 Ví dụ

 Định lí 2

 Định lí 3

 Định lí 4

 Định lí 5

1.4. HỆ SỐ NHỊ THỨC

 Định nghĩa

 Các tính chất cơ bản

 Nhị thức Newton

1.5. HAI NGUYÊN LÝ ĐẾM CƠ BẢN

6

1.5.1. Nguyên lý cộng

 Ví dụ 1

 Ví dụ 2

1.5.2. Nguyên lý nhân

 Ví dụ 1

 Ví dụ 2

7

CHƯƠNG 2

CÁC PHƯƠNG PHÁP ĐẾM NÂNG CAO

2.1. PHƯƠNG PHÁP ĐẾM BẰNG SONG ÁNH

2.1.1 Quy tắc cộng

Mệnh đề 1

Cho A và B là hai tập hữu hạn.

Nếu A



B = Ø thì

A B

=

A

+

B .

Chứng minh

Mệnh đề 2

Nếu A1,A2,...,An là các tập hữu hạn đôi một rời nhau, tức là

Ai



Aj = Ø,



i,j



{1,2,3,...,n}, thì

│A1



A2

...

An │ = │ A1│+│A2│+│An│

2.1.2. Quy tắc nhân

Mệnh đề 1

Nếu A và B là hai tập hữu hạn thì,

AB

=

A

×

B .

Chứng minh

Mệnh đề 2

Nếu A1,A2,...,An là các tập hữu hạn bất kỳ và A1 ×A2 ×... ×An là tích

Đềcác của n tập hợp đó thì

│A1×A2×...×An │ = │ A1│×│A2│×...×│An│.

2.2. PHƯƠNG PHÁP ĐẾM BẰNG HÀM SINH

2.2.1 Giới thiệu về hàm sinh và các phép toán trên hàm

sinh

Cho dãy số thực (ar)r = (a0,a1,a2,…) và biến

Định nghĩa

- Hàm sinh (thường) của dãy (a0,a1,a2,…) là hàm

8

g(x) = a0 + a1x + a2x

2

+ a3x

3 …

- Hàm sinh mũ của dãy (a0,a1,a2,…) là hàm

g(x) = a0 + a1

1!

x

+ a2

2!

2

x

+ a3

3!

3

x …

Qui ước.

Qui tắc là: Số hạng thứ i của dãy số (đánh số từ 0) là hệ số của xi

trong hàm sinh.

Các phép toán trên hàm sinh

● Quy tắc 1. (Quy tắc nhân với hằng số)

Khi nhân hàm sinh với một hằng số thì trong dãy số tương ứng, các

số hạng sẽ được nhân với hằng số đó.

Nếu < f0, f1, f2, f3, …>  F(x) thì < cf0, cf1, cf2, cf3, …>  cF(x)

Chứng minh

Ví dụ

● Quy tắc 2. (Quy tắc cộng)

Cộng hai hàm sinh tương ứng với việc cộng các số hạng của dãy số

theo đúng chỉ số.

Nếu < f0, f1, f2, …>  F(x), <g0, g1, g2, …>  G(x)

thì < f0+g0, f1+g1, f2+g2, …>  F(x) + G(x)

Chứng minh

Ví dụ

● Quy tắc 3. (Quy tắc dịch chuyển phải)

Nếu < f0, f1, f2, …>  F(x) thì < 0, …, 0, f0, f1, f2, …>  x

k

.F(x)

(có k số 0)

Chứng minh

Ví dụ

● Quy tắc 4. (Quy tắc đạo hàm)

Nếu < f0, f1, f2, …>  F(x)

9

thì < f1, 2f2, 3f3, ..> 

dx

dF (x)

Chứng minh

Ví dụ 1

Ví dụ 2

● Quy tắc 5 (Quy tắc xoắn). Gọi A(x) là hàm sinh cho cách chọn

các phần tử từ tập hợp A và B(x) là hàm sinh cho cách chọn các phần

tử từ tập hợp B. Nếu A và B là rời nhau thì hàm sinh cho cách chọn

các phần tử từ A  B là A(x).B(x).

  













   

0 0 0

( ) , ( ) , ( ) ( ) . ( ) .

n

n

n

n

n

n

n

n

n A x a x B x b x C x A x B x c x

trong đó cn = a0bn + a1bn-1 + … + anb0

Ý tưởng chính để áp dụng giải bài toán đếm ở đây là: hàm sinh

cho số cách chọn các phần tử từ hợp của hai tập hợp bằng tích các

hàm sinh cho số cách chọn các phần tử từ mỗi tập hợp.

2.2.2 Đếm bằng hàm sinh thường và đếm bằng hàm sinh

mũ

a. Đếm bằng hàm sinh thường

a1. Số Fibonacci

a2. Hợp thành và phân hoạch của số nguyên dương

● Hợp thành

k

phần của số nguyên dương

Ví dụ

. ● Phân hoạch một số nguyên dương

r

Ví dụ

Định lí . Với mọi

r

và

n , p (r)

n q (r) 

n

.

Chứng minh

Ví dụ

b. Đếm bằng hàm sinh mũ