Một số phương pháp và kỹ thuật đếm cơ bản trong lý thuyết tổ hợp và áp dụng

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

- - - - - - - - - - - - - - - - - -

Lê Quang Việt

MỘT SỐ PHƯƠNG PHÁP VÀ KỸ

THUẬT ĐẾM CƠ BẢN TRONG LÝ

THUYẾT TỔ HỢP VÀ ÁP DỤNG

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ố: 60460113

Người hướng dẫn khoa học

GS. TSKH. NGUYỄN VĂN MẬU

THÁI NGUYÊN - NĂM 2013

Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/

1 .

Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/

2

Mục lục

Mở đầu 4

Lời cảm ơn 5

1 Các quy tắc đếm cơ bản trong tổ hợp 6

1.1 Một số kiến thức cơ bản của tổ hợp . . . . . . . . . . . . . . 6

1.1.1 Tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.2 Công thức tính lực lượng của tập hợp . . . . . . . . . 7

1.1.3 Công thức bao hàm và loại trừ . . . . . . . . . . . . . 9

1.2 Hai quy tắc cơ bản của phép đếm . . . . . . . . . . . . . . . 10

1.2.1 Quy tắc cộng . . . . . . . . . . . . . . . . . . . . . . 10

1.2.2 Quy tắc nhân . . . . . . . . . . . . . . . . . . . . . 12

1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.3.1 Hoán vị không lặp . . . . . . . . . . . . . . . . . . . . 14

1.3.2 Hoán vị có lặp . . . . . . . . . . . . . . . . . . . . . . 16

1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.4.1 Chỉnh hợp không lặp . . . . . . . . . . . . . . . . . . 17

1.4.2 Chỉnh hợp có lặp . . . . . . . . . . . . . . . . . . . . 19

1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.5.1 Tổ hợp không lặp . . . . . . . . . . . . . . . . . . . . 20

1.5.2 Tổ hợp có lặp . . . . . . . . . . . . . . . . . . . . . . 21

1.5.3 Khai triển lũy thừa của nhị thức . . . . . . . . . . . . 22

1.5.4 Tính số phần tử của một tập hợp các tập hợp . . . . . 23

2 Các phương pháp đếm sử dụng hàm sinh 27

2.1 Chuỗi lũy thừa hình thức . . . . . . . . . . . . . . . . . . . . 27

2.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 27

2.1.2 Các phép toán trên C

N . . . . . . . . . . . . . . . . . 28

2.2 Phương pháp đếm bằng hàm sinh thông thường . . . . . . . . 30

Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/

3

2.2.1 Định nghĩa hàm sinh thường . . . . . . . . . . . . . 30

2.2.2 Sử dụng hàm sinh thường để giải các bài toán đếm . 33

2.3 Phương pháp đếm bằng hàm sinh mũ . . . . . . . . . . . . . 37

2.3.1 Định nghĩa hàm sinh mũ . . . . . . . . . . . . . . . 37

2.3.2 Sử dụng hàm sinh mũ để giải các bài toán đếm . . . 37

3 Phương pháp đếm bằng các công thức nghịch đảo 40

3.1 Công thức nghịch đảo các đồng nhất thức tổ hợp . . . . . . . 43

3.2 Công thức nghịch đảo nhị thức . . . . . . . . . . . . . . . . . 44

3.3 Công thức nghịch đảo Stirling . . . . . . . . . . . . . . . . . 45

3.4 Công thức sàng . . . . . . . . . . . . . . . . . . . . . . . . . 46

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . 51

Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/

4

Mở đầu

Trong lý thuyết tổ hợp các phép đếm luôn chiếm một phần vô cùng quan

trọng và có ứng dụng vô cùng đa dạng. Các phương pháp đếm số lượng phần

tử của một tập hợp đóng vai trò quan trọng trong một số môn khoa học,

đặc biệt là Tin học và Toán học ứng dụng. Đối với chương trình toán phổ

thông các phương pháp đếm luôn là chuyên đề quan trọng và hết sức cần

thiết trong việc bồi dưỡng học sinh giỏi Toán ở bậc học phổ thông, đồng thời

các ứng dụng đa dạng của nó cũng luôn đem lại sự hấp dẫn đối với nhiều đối

tượng học sinh và giáo viên khi nghiên cứu vấn đề này.

Mục tiêu của Luận văn " Một số phương pháp và kĩ thuật đếm cơ bản trong

lý thuyết tổ hợp và áp dụng" nhằm trình bày một số phép đếm cơ bản nhất

và những ứng dụng của nó nhằm tạo ra được một đề tài phù hợp cho việc

giảng dạy, bồi dưỡng học sinh trung học phổ thông.

Luận văn bao gồm phần mở đầu, kết luận, tài liệu tham khảo và 3 Chương.

Chương 1 trình bày tóm tắt một số kiến thức cơ bản của tổ hợp và các quy

tắc cơ bản của phép đếm. Trong chương này cũng trình bày một số ví dụ và

các bài toán về tính lực lượng tập hợp, bài toán về khai triển nhị thức.

Chương 2 trình bày các phương pháp đếm bằng hàm sinh thông thường và

phương pháp đếm bằng hàm sinh mũ cùng các ví dụ áp dụng.

Chương 3 trình bày các phương pháp đếm bằng các công thức nghịch đảo

các đồng nhất thức tổ hợp bao gồm công thức nghịch đảo nhị thức, nghịch

đảo Stirling, công thức sàng và các ví dụ áp dụng.

Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/