Một số bài toán tổ hợp sơ cấp liên quan đến vấn đề sắp xếp và phân hoạch trên tập hữu hạn

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

TRƯỜNG ĐẠI HỌC QUY NHƠN

——————————————

NGUYỄN THỊ QUÀ

MỘT SỐ BÀI TOÁN TỔ HỢP SƠ CẤP

LIÊN QUAN ĐẾN VẤN ĐỀ SẮP XẾP VÀ

PHÂN HOẠCH TRÊN TẬP HỮU HẠN

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

Bình Định - 2022

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

TRƯỜNG ĐẠI HỌC QUY NHƠN

——————————————

NGUYỄN THỊ QUÀ

MỘT SỐ BÀI TOÁN TỔ HỢP SƠ CẤP

LIÊN QUAN ĐẾN VẤN ĐỀ SẮP XẾP VÀ

PHÂN HOẠCH TRÊN TẬP HỮU HẠN

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

Mã số: 8460113

Khóa: 23 (2020 - 2022)

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

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

PGS.TSKH. HUỲNH VĂN NGÃI

Bình Định - 2022

LỜI CAM ĐOAN

Luận văn này được hoàn thành tại Trường Đại học Quy Nhơn. Tác giả

xin cam đoan rằng nội dung trình bày trong luận văn là trung thực và không

trùng lặp với các đề tài khác tính đến thời điểm hiện tại. Đề tài “Một số bài

toán tổ hợp sơ cấp liên quan đến vấn đề sắp xếp và phân hoạch

trên tập hữu hạn” là kết quả nghiên cứu của tác giả dưới sự hướng dẫn

khoa học của PGS.TSKH. Huỳnh Văn Ngãi. Tác giả cũng xin cam đoan rằng

các kết quả được trình bày trong luận văn được tham khảo và trích dẫn từ

các tài liệu đảm bảo tính rõ ràng và chính xác.

Bình Định, ngày 25 tháng 7 năm 2022

Tác giả

Nguyễn Thị Quà

MỤC LỤC

LỜI CAM ĐOAN

MỤC LỤC

DANH MỤC KÝ HIỆU

LỜI MỞ ĐẦU 1

Chương 1 CÁC SỐ TỔ HỢP CƠ BẢN VÀ HÀM SINH 4

1.1 Các nguyên tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . 4

1.1.1 Nguyên tắc cộng . . . . . . . . . . . . . . . . . . . . . 4

1.1.2 Nguyên tắc nhân . . . . . . . . . . . . . . . . . . . . . 5

1.1.3 Nguyên tắc bù trừ . . . . . . . . . . . . . . . . . . . . 6

1.2 Các cấu hình tổ hợp cơ bản . . . . . . . . . . . . . . . . . . . 7

1.2.1 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.2 Hoán vị lặp . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.3 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.4 Chỉnh hợp lặp . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.6 Tổ hợp lặp . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2.7 Nhị thức Newton . . . . . . . . . . . . . . . . . . . . . 9

1.3 Hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3.1 Hệ số nhị thức tổng quát . . . . . . . . . . . . . . . . . 10

1.3.2 Chuỗi luỹ thừa hình thức . . . . . . . . . . . . . . . . 11

1.3.3 Hàm sinh thường . . . . . . . . . . . . . . . . . . . . . 13

1.3.4 Áp dụng hàm sinh vào hệ thức truy hồi . . . . . . . . . 15

Chương 2 SỐ STIRLING LOẠI HAI VÀ SỐ CATALAN 22

2.1 Số Stirling loại hai . . . . . . . . . . . . . . . . . . . . . . . . 22

2.1.1 Một số định nghĩa và tính chất cơ bản . . . . . . . . . 22

2.1.2 Một số bài tập áp dụng liên quan đến số Stirling loại hai 27

2.2 Số Catalan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.2.1 Một số định nghĩa và tính chất cơ bản . . . . . . . . . 35

2.2.2 Một số bài tập áp dụng liên quan đến số Catalan . . . 41

Chương 3 BÀI TOÁN CHIA KẸO EULER VÀ PHÂN HOẠCH

SỐ NGUYÊN 48

3.1 Bài toán chia kẹo Euler . . . . . . . . . . . . . . . . . . . . . . 48

3.1.1 Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.1.2 Một số bài toán mở rộng của bài toán chia kẹo Euler . 50

3.2 Phân hoạch của số nguyên . . . . . . . . . . . . . . . . . . . . 61

3.2.1 Một số định nghĩa và tính chất cơ bản . . . . . . . . . 61

3.2.2 Một số bài tập áp dụng liên quan đến phân hoạch của

số nguyên . . . . . . . . . . . . . . . . . . . . . . . . . 85

Chương 4 MỘT SỐ BÀI TOÁN SƠ CẤP LIÊN QUAN 90

4.1 Một số bài toán sơ cấp liên quan đến bài toán chia kẹo Euler . 90

4.2 Một số bài toán sơ cấp liên quan khác . . . . . . . . . . . . . 102

Kết luận 112

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

DANH MỤC KÝ HIỆU

N : Tập các số tự nhiên.

N

˚

: Tập các số tự nhiên khác 0.

Z : Tập các số nguyên.

R : Tập các số thực.

R

` : Tập các số thực không âm.

|A| : Số phần tử của tập hợp A.

rns : Tập hợp t1, 2, ¨ ¨ ¨ , nu.

x P A : phần tử x thuộc tập hợp A.

x R A : phần tử x không thuộc tập hợp A.

A Ă B : Tập hợp A con tập hợp B.

A X B : Tập hợp A giao với tập hợp B.

A Y B : Tập hợp A hợp với tập hợp B.

AzB : Tập hợp A hiệu tập hợp B.

řn

i“1

ai

: a1 ` a2 ` ¨ ¨ ¨ ` an.

ř

ně0

an : a0 ` a1 ` `a2 ` ¨ ¨ ¨ .

LỜI MỞ ĐẦU

Lý thuyết tổ hợp được hình thành như một ngành toán học vào khoảng

thế kỷ XVII bằng một loạt các công trình nổi tiếng của các nhà Toán học lỗi

lạc như Pascal, Fermat, Leibniz, ... Đặc biệt vào khoảng cuối thế kỷ XX, với

sự xuất hiện của máy tính, lý thuyết tổ hợp phát triển ngày càng mạnh mẽ,

và ngày nay, nó đã trở thành một phần quan trọng của toán học nói chung

và toán học rời rạc nói riêng. Nó không chỉ có nội dung phong phú, đa dạng,

mà còn có nhiều ứng dụng trong các lĩnh vực khác của toán học như: đại số,

lý thuyết xác suất, lý thuyết ergodic (ergodic theory), hình học.., cũng như

các ngành khoa học ứng dụng khác như: khoa học máy tính, vật lý thống kê

và nhiều ứng dụng trong thực tế đời sống.

Những bài toán tổ hợp liên quan đến vấn đề sắp xếp, phân hoạch tập hợp

đóng vai trò quan trọng trong lý thuyết tổ hợp nói chung, và trong tổ hợp

sơ cấp trong chương trình toán phổ thông nói riêng. Đặc biệt, trong những

năm gần đây, các bài toán tổ hợp liên quan đến vấn đề sắp xếp, phân hoạch

tập hợp cũng thường xuyên xuất hiện trong các kỳ thi chọc sinh giỏi Toán

quốc gia và quốc tế. Có rất nhiều những kết quả lý thuyết sâu sắc cũng như

những ứng dụng đã đạt được trong vài chục năm gần đây. Riêng trong toán

tổ hợp sơ cấp, mặc dù có nhiều tài liệu tổ hợp dành cho chương trình phổ

thông, tuy nhiên gần như chưa có (ít nhất ở Việt Nam) một tài liệu có hệ

thống về các vấn đề liên quan đến bài toán phân hoạch trên tập hữu hạn.

Vì vậy, với sự hướng dẫn khoa học của thầy PGS.TSKH. Huỳnh Văn

Ngãi, tôi đã chọn đề tài “Một số bài toán tổ hợp sơ cấp liên quan

đến vấn đề sắp xếp và phân hoạch trên tập hữu hạn” cho luận văn

thạc sĩ của mình.

Mục tiêu của Luận văn là tập trung giải quyết một số bài toán tổ hơp sơ

1

2

cấp liên quan đến vấn đế sắp xếp và phân hoạch trên các tập hữu hạn như:

các bài toán về các số Stirling, số Catalan, bài toán chia kẹo Euler, bài toán

phân hoạch số nguyên,...

Ngoài phần Mở đầu, Kết luận, Tài liệu tham khảo, nội dung của Luận

văn được chia làm bốn chương.

‚ Chương 1: Trình bày một số kiến thức cơ bản về các số tổ hợp cơ bản

và hàm sinh, nhằm sử dụng cho các chương tiếp theo.

‚ Chương 2: Trình bày một số kiến thức cơ bản của các số Stirling, số

Catalan và một số ứng dụng của chúng.

‚ Chương 3: Trình bày bài toán chia kẹo Euler, một số bài toán mở rộng

của bài toán chia kẹo Euler và một số kiến thức cơ bản về phân hoạch của

số nguyên cũng như các ứng dụng của nó.

‚ Chương 4: Sưu tầm và hệ thống một số bài toán tổ hợp sơ cấp trong

các đề thi học sinh giỏi Toán quốc tế, quốc gia, các đề ôn và thi chọn đội

tuyển học sinh giỏi các tỉnh, thành phố liên quan đến bài toán sắp xếp và

phân hoạch trên các tập hữu hạn.

Luận văn được hoàn thành dưới sự hướng dẫn khoa học của thầy PGS.

TSKH. Huỳnh Văn Ngãi, Khoa Toán và Thống kê, Trường Đại học Quy

Nhơn. Nhân dịp này, tôi xin được bày tỏ sự kính trọng và lòng biết ơn sâu

sắc đến Thầy, đã tận tình giúp đỡ và truyền đạt những kiến thức cũng như

những kinh nghiệm quý báu trong suốt quá trình học tập và nghiên cứu,

thực hiện Luận văn, để tôi có thể hoàn thành Luận văn một cách tốt nhất.

Tôi cũng xin gửi lời cảm ơn đến Ban giám hiệu nhà trường, Phòng Đào

tạo Sau Đại học, Khoa Toán và Thống kê, cùng quý thầy cô đã giảng dạy

lớp cao học, chuyên ngành Phương pháp Toán sơ cấp K23, Trường Đại học

Quy Nhơn, đã tạo điều kiện thuận lợi cho tôi trong suốt quá trình học tập

và nghiên cứu, thực hiện đề tài.

Tôi cũng xin được gửi lời cảm ơn đến Lãnh đạo Sở Giáo dục và Đào

tạo Phú Yên, Ban giám hiệu nhà trường, cùng quý thầy cô, đồng nghiệp

trường THCS & THPT Nguyễn Khuyến và các bạn lớp cao học, chuyên

ngành Phương pháp Toán sơ cấp K23, đã nhiệt tình giúp đỡ và tạo điều kiện

3

thuận lợi cho tôi trong suốt quá trình học tập và nghiên cứu, thực hiện đề

tài.

Cuối cùng, tôi xin chân thành cảm ơn gia đình và những người thân, bạn

bè của tôi, đã động viên và hỗ trợ tinh thần rất tốt cho tôi trong suốt thời

gian học tập và nghiên cứu, thực hiện đề tài.

Mặc dù luận văn được thực hiện với sự nổ lực và cố gắng hết sức của bản

thân nhưng do điều kiện thời gian có hạn, trình độ kiến thức và kinh nghiệm

nghiên cứu còn hạn chế nên Luận văn cũng khó tránh khỏi những thiếu sót.

Tôi rất mong nhận được sự góp ý của quý thầy, cô để luận văn được hoàn

thiện hơn.

Tôi xin chân thành cảm ơn!

Chương 1

CÁC SỐ TỔ HỢP CƠ BẢN VÀ

HÀM SINH

Trong chương này chúng tôi trình bày một số kiến thức cơ bản về các số

tổ hợp cơ bản như: Hoán vị, chỉnh hợp, tổ hợp, các nguyên tắc đếm... và các

kiến thức cơ bản về hàm sinh, nhằm sử dụng cho các chương tiếp theo. Các

kiến thức cơ bản trong chương này chủ yếu được tham khảo từ các tài liệu

[1],[2], [3], [7].

1.1 Các nguyên tắc đếm cơ bản

1.1.1 Nguyên tắc cộng

Định lý 1.1 ([1]). Nếu A1, A2, ..., An là các tập hợp hữu hạn, đôi một không

giao nhau thì

|A1 Y A2 Y ¨ ¨ ¨ Y An| “ |A1| ` |A2| ` ¨ ¨ ¨ ` |An| .

Nguyên tắc này trong chương trình phổ thông được phát biểu như sau:

Giả sử một công việc được thực hiện theo một trong n phương án A1, A2, ...,

An. Phương án A1 có m1 cách thực hiện, phương án A2 có m2 cách thực hiện

,..., phương án An có mn cách thực hiện. Khi đó công việc có thể được thực

hiện bởi m1 ` m2 ` ... ` mn cách.

4

5

Ví dụ 1.1. Trên giá sách của Nam có n1 quyển giáo khoa, n2 quyển sách

bài tập, n3 quyển truyện tranh, n4 quyển tiểu thuyết (tất cả đều khác nhau).

Hỏi Nam có bao nhiêu cách chọn một quyển sách để đọc?

Lời giải. Gọi A1, A2, A3, A4 lần lượt là tập hợp các sách giáo khoa, sách bài

tập, truyện tranh, tiểu thuyết. Khi đó ta có A1, A2, A3, A4 là các tập hữu

hạn, đôi một không giao nhau.

Theo nguyên tắc cộng, số cách Nam có thể chọn một quyển sách để đọc là

|A1 Y A2 Y A3 Y A4| “ |A1| ` |A2| ` |A3| ` |A4| “ n1 ` n2 ` n3 ` n4 (cách).

1.1.2 Nguyên tắc nhân

Định lý 1.2 ([1]). Cho X1, X2, ¨ ¨ ¨ , Xn là các tập hữu hạn. Khi đó số bộ giá

trị px1, x2, ¨ ¨ ¨ , xnq thoả mãn xi P Xi

, @i “ 1, 2, ¨ ¨ ¨ , n là |X1| . |X2| . ¨ ¨ ¨ . |Xn|.

Nguyên tắc này trong chương trình phổ thông được phát biểu như sau:

Giả sử một công việc được thực hiện bởi n công đoạn A1, A2, ..., An liên

tiếp nhau. Công đoạn A1 có thể được thực hiện theo m1 cách, công đoạn A2

có thể được thực hiện theo m2 cách,..., Công đoạn An có thể được thực hiện

theo mn cách. Khi đó công việc có thể được thực hiện theo m1.m2. ¨ ¨ ¨ .mn

cách.

Ví dụ 1.2. Có bao nhiêu số nguyên dương có k chữ số, với k nguyên dương?

Lời giải. Một số nguyên dương có k chữ số chính là một bộ giá trị px1, x2, . . . , xkq,

trong đó xi

là chữ số thứ i trong số nguyên của chúng ta cần tìm. Khi đó

x1 P t1, 2, ¨ ¨ ¨ , 9u và xi P t0, 1, 2, ¨ ¨ ¨ , 9u, với 2 ď i ď k. Do đó, |X1| “ 9 và

|Xi

| “ 10, với mọi 2 ď i ď k.

Vậy theo nguyên tắc nhân, số các số nguyên dương có k chữ số, với k

nguyên dương là 9.10k´1

(số).