Ứng dụng số stirling vào giải toán tổ hợp

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

ĐẠI HỌC ĐÀ NẴNG

NGUYỄN XUÂN TRỌNG

ỨNG DỤNG SỐ STIRLING VÀO

GIẢI TOÁN TỔ HỢP

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. HOÀNG QUANG TUYẾN

Phản biện 2: TS. CAO VĂN NUÔI

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 26 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

Có thể nói tư duy tổ hợp ra đời rất sớm. Vào thời nhà Chu, người

ta đã biết đến các hình vẽ có liên quan đến những hình vuông thần bí.

Thời cổ Hy Lạp, nhà triết học Kxenokrat, sống ở thế kỉ 4 trước công

nguyên, đã biết tính số các từ khác nhau lập từ bảng chữ cái cho trước.

Nhà toán học Pytago và các học trò của ông đã tìm ra nhiều con số có

tính chất đặc biệt. Việc tìm ra các con số như vậy đòi hỏi phải có một

nghệ thuật tổ hợp nhất định . Tuy nhiên, có thể nói rằng, lý thuyết tổ hợp

được hình thành như một ngà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êm túc của các nhà toán học xuất sắc như

Pascal, Fermat, Leibnitz, Euler,…Mặc dù vậy, trong suốt hai thế kỉ rưỡi,

tổ hợp không có vai trò nhiều trong nghiên cứu tự nhiên. Đến nay, với sự

hỗ trợ đắc lực của máy tính, tổ hợp đã chuyển sang lĩnh vực toán ứng

dụng với sự phát triển mạnh mẽ, có nhiều kết quả có ích cho con người .

Nhận thức được vai trò của lý thuyết tổ hợp trong đời sống hiện

đại. Tổ hợp đã được đưa vào giảng dạy ở chương trình học phổ thông,

đại học, sau đại học và nó là một bộ môn tương đối khó đối với học sinh,

sinh viên vì khái niệm trừu tượng và nhiều dạng toán rất khó nhưng thời

lượng dành cho môn này còn hạn chế nhất là bậc trung học phổ thông.

Trong nhiều kì thi học sinh giỏi quốc gia, thi Olympic toán quốc

tế, thi Olympic sinh viên giữa các trường đại học, cao đẳng các bài toán

liên quan đến tổ hợp hay được đề cập và thường thuộc loại rất khó nên

học sinh đa số còn lúng túng khi giải quyết những bài toán loại này.

2

Chính vì các lý do nêu trên, tôi quyết định chọn đề tài “ ỨNG

DỤNG SỐ STIRLING VÀO GIẢI TOÁN TỔ HỢP ” để tìm hiểu,

nghiên cứu nhằm phục vụ cho công tác giảng dạy của tôi nói chung và

luyện thi học sinh giỏi nói riêng sau này. Đồng thời đây cũng là một tài

liệu cho các đồng nghiệp, học sinh, sinh viên tham khảo.

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

Nghiên cứu về các số Stirling và ứng dụng của số Stirling để giải

các bài toán về tổ hợp.

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

- Tìm hiểu về lý thuyết tổ hợp, đặc biệt là số Stirling

- Tìm hiểu và xây dựng các ứng dụng của các số Stirling để

giải các bài toán về tổ hợp.

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

- Đối tượng nghiên cứu là các số Stirling.

- Phạm vi nghiên cứu là số Stirling và ứng dụng ứng dụng của số

Stirling để giải các bài toán về tổ hợp.

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

- Nghiên cứu lý thuyết thông qua việc sưu tầm các loại tài liệu như

sách, báo, tạp chí, mạng internet, thầy cô, bạn bè. Trình bày một cách có

hệ thống các nội dung lý thuyết đã nghiên cứu và tìm hiểu. Mỗi nội dung

phải chứng minh cụ thể, rõ ràng và lấy ví dụ minh họa xác thực, dễ hiểu.

- Phân loại và hệ thống các dạng toán. Tìm ra các phương pháp

đặc trưng để giải mỗi dạng toán cụ thể.

3

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

- Đề tài góp phần nghiên cứu ứng dụng của các số Stirling vào giải

toán tổ hợp phù hợp với chuyên ngành Phương pháp toán sơ cấp.

- Sau khi cho phép bảo vệ, được sự góp ý của các thầy cô trong hội

đồng, luận văn có thể dùng làm tài liệu tham khảo cho sinh viên, giáo

viên, học sinh phổ thông và những ai quan tâm đến lĩnh vực này.

- Thời gian nghiên cứu không nhiều nên có thể còn một số nội

dung hay mà luận văn chưa đề cập đến. Tôi sẽ tiếp tục nghiên cứu và bổ

sung thường xuyên để nội dung luận văn được phong phú, có thể dùng

làm tài liệu ôn thi học sinh giỏi ở bậc trung học phổ thông.

7. Cấu trúc của luận văn

Ngoài phần mở đầu và kết luận, luận văn được chia thành ba

chương :

Chương 1: Cơ sở lý thuyết

Trong chương này tôi trình bày các định nghĩa, tính chất, ví dụ về

nguyên lý cộng, nguyên lý nhân, các cấu hình tổ hợp cơ bản và nâng

cao, phân hoạch tổ hợp thứ tự và không thứ tự, công thức nhị thức

Newton.

Chương 2: Số Stirling loại 1 và loại 2

Trong chương này tôi trình bày các định nghĩa, tính chất của số

Stirling loại 1 và loại 2 .

Chương 3: Ứng dụng của số Stirling giải các bài toán tổ hợp.

Trong chương này tôi trình bày một số ứng dụng của các số

Stirling để giải các bài toán tổ hợp.

4

CHƯƠNG 1

CƠ SỞ LÝ THUYẾT

1.1 NGUYÊN LÝ CỘNG VÀ NGUYÊN LÝ NHÂN

1.1.1 Nguyên lý cộng

Định nghĩa 1.1. Giả sử {X1, X2,...,Xn} là một phân hoạch của tập S. Khi

đó

1 2 ... S X X X    

n

.

1.1.2 Nguyên lý nhân

Định nghĩa 1.2. Giả sử một cấu hình tổ hợp được xây dựng qua k bước,

bước 1 có thể được thực hiện theo n1 cách, bước 2 có thể được thực hiện

theo n2 cách, ..., bước k có thể thực hiện theo nk cách. Khi đó số cấu hình

tổ hợp là :

n1n2...nk .

1.2 CÁC CẤU HÌNH TỔ HỢP CƠ BẢN

1.2.1 Chỉnh hợp lặp

Định nghĩa 1.3. Một chỉnh hợp lặp chập k của n phần tử khác nhau là

một bộ có thứ tự gồm k thành phần lấy từ n thành phần đã cho. Các

thành phần có thể được lặp lại.

Một chỉnh hợp lặp chập k của n có thể xem như một phần tử của

tích Đê – các X

k

, với X là tập n phần tử. Như vậy số tất cả các chỉnh hợp

chập k của n là

AR(n, k) = n

k

.

5

1.2.2 Chỉnh hợp không lặp

Định nghĩa 1.4. Một chỉnh hợp không lặp chập k của n phần tử khác

nhau là một bộ có thứ tự gồm k thành phần lấy từ n thành phần đã cho.

Các thành phần không được lặp lại.

Kí hiệu A(n,k) và

!

( ) =

( )!

n

A n,k

n - k

.

1.2.3 Hoán vị

Định nghĩa 1.5. Một hoán vị của n phần tử khác nhau là một cách sắp

xếp thứ tự các phần tử đó .

Hoán vị có thể coi như trường hợp riêng của chỉnh hợp không lặp

chập k của n trong đó k = n. Ta có số hoán vị kí hiệu là P(n), P(n) = n!.

1.2.4 Tổ hợp

Định nghĩa 1.6. Một tổ hợp chập k của n phần tử khác nhau là một bộ

không kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử đã cho.

Nói cách khác ta có thể coi một tổ hợp chập k của n phần tử khác nhau là

một tập con có k phần tử từ n phần tử đã cho.

Kí hiệu C(n,k) là số tổ hợp chập k của n phần tử ta có:

 

 

!

! !

n

C n,k =

k n - k

.

1.3 CÁC CẤU HÌNH TỔ HỢP MỞ RỘNG

1.3.1 Hoán vị lặp

Định nghĩa 1.7. Hoán vị lặp là hoán vị trong đó mỗi phần tử được ấn

định một số lần lặp lại cho trước.

6

Định lí 1.1. Số hoán vị lặp của n phần tử khác nhau, trong đó phần tử thứ

nhất lặp n1 lần, phần tử thứ 2 lặp n2 lần, …, phần tử thứ k lặp nk lần là

1 2

1 2

!

( ; , ,..., ) ,

! !... ! k

k

n

P n n n n

n n n



với

1 2 ... n n n n    k

.

1.3.2 Tổ hợp lặp

Định nghĩa 1.8. Tổ hợp lặp chập k từ n phần tử là một nhóm không phân

biệt thứ tự gồm k phân tử trích từ n phần tử đã cho, trong đó các phần tử

có thể được lặp lại.

Định lí 1.2. Giả sử có n phần tử khác nhau. Khi đó số tổ hợp lặp chập k

từ n phần tử của X, kí hiệu CR(n,k) là

CR(n,k) = C(k+n–1,n–1) = C(k+n–1,k).

1.3.3 Phân hoạch thứ tự tổ hợp

Định nghĩa 1.9. Cho X là tập n phần tử khác nhau, r



n và

S X 

có r

phần tử . Một phân hoạch

S S S 1 2 , ,..., k

có thứ tự của S gọi là một phân

hoạch thứ tự tổ hợp chập r của X . Nếu r = n , thì gọi là phân hoạch thứ

tự của X.

Cho các số nguyên dương n1, n2,…,nk thỏa mãn n1+ n2 +…+ nk = r. Số

các phân hoạch thứ tự tổ hợp chập r của X có dạng

S S S 1 2 , ,..., k

có

1 1 S n  ,

2 2 S n  ,…,

k k S n 

được ký hiệu là C(n ; n1, n2,…,nk).

Định lí 1.3.

 

 

1 2 1 2  

1 2

!

C ; , , ,

! ! ! !

  k k

k

n

n n n n = P n;n ,n ,...,n ,n - r

n n ...n n - r

.

C(n;n1,n2,…,nk) được gọi là hệ số đa thức.