Tổ hợp trong xác suất và ứng dụng

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

ĐẠI HỌC ĐÀ NẴNG

PHẠM ĐỨC KHANH

TỔ HỢP TRONG XÁC SUẤT VÀ ỨNG DỤNG

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. CAO VĂN NUÔI

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 14 tháng 12

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

Trong những năm qua xác suất thống kê đã 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ủa các trường

phổ thông và đại học. Đồng thời nó cũng được ứng dụng trong nhiều

lĩnh vực khác có nhiều kết quả có ích cho con người.

Trong khoa học kỹ thuật chúng ta thường gặp rất nhiều bài

toán liên quan tới xác suất. Có nhiều trường hợp chúng ta cần phải áp

dụng tổ hợp vào để giải xác suất. Bởi vậy chúng ta phải tìm các

phương pháp tổ hợp để áp dụng giải các bài toán xác suất. Cho đến

nay, xác suất có rất nhiều ưu điểm và ứng dụng của nó .

Đó là lý do tôi chọn để tài “Tổ hợp trong xác suất và ứng

dụng”. Để 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 tiêu nghiên cứu của đề tài

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 đó và để có thể trình bày

lại các kiến thức trong luận văn này theo một thể khép kín và hi 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 và giáo viên các trường trung học phổ thông và những

người quan tâm đến xác suất thống kê.

Trong chương 1 của luận văn này, tôi trình bày lý thuyết về

«Tổ Hợp ». Trong chương 2 tôi dự định nghiên cứu về « Xác Suất ».

Chương 3 tôi sẽ tìm hiểu về «Một Số Ứng Dụng Tổ Hợp Tính Xác

Suất ».

2

Nội dung trong từng chương dự kiến là cung cấp lý thuyết cơ

bản về nguyên lý chủ đề của chương, kỹ thuật áp dụng của các

nguyên lí đó và các bài tập ví dụ minh họa.

Công việc sẽ tốn không ít thời gian xây dựng các bài toán liên

quan trong từng chương, mục để thấy hết ý nghĩa của các nguyên lý

và kỹ thuật đó trong xác suất thống kê.

3. Phƣơng pháp nghiên cứu

Trong luận văn, các phương pháp sử dụng nằm trong các lĩnh

vực sau đây: Một số kiến thức của lý thuyết xác suất và thống kê

toán học và lý thuyết tổ hợp .

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

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

Nghiên cứu giải một số bài toán xác suất bằng tổ hợp.

4.2. Phạm vi nghiên cứu

Nghiên cứu từ các tài liệu, các giáo trình về xác suất thống kê

và giáo trình lý thuyết tổ hợp của các tác giả liên quan.

5. Đóng góp đề tài

Đề tài có ý nghĩa về mặt lý thuyết, có thể sử dụng như là tài

liệu tham khảo dành cho học sinh ,sinh viên và giáo viên giảng dạy

môn toán khối phổ thông trung học …

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 tổ hợp vào xác suất

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

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 luận văn

3

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 : Tổ hợp

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

về hai nguyên lý đếm cơ bản, các cấu hình tổ hợp cơ bản, cấu hình tổ

hợp mở rộng, nhị thức Newton.

Chƣơng 2 : Xác suất

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

về phép thử và sự kiện, xác suất của một biến cố, xác suất có điều

kiện và công thức nhân xác suất, công thức xác suất toàn phần và

công thức Bayes, tính độc lập giửa các biến cố, dãy n biến cố độc

lập, dãy các phép thử độc lập, công thức xác suất nhị thức.

Chƣơng 3 : Một số ứng dụng tổ hợp tính xác suất

Trong chương này tôi trình bày một số bài toán dùng tổ hợp

tính xác suất .

4

CHƢƠNG 1

TỔ HỢP

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

1.1.1.Nguyên lý nhân

Nguyên lý nhân. Giả sử một sự kiện

E

có thể được phân tích thành

r sự kiện, theo trình tự là

1 2 , ,..., E E Er

và giả sử có:

1 n cách để sự kiện

E1

xảy ra,

2 n cách để sự kiện

E2

xảy ra,

...

r n cách để sự kiện

Er

xảy ra.

Khi đó, số cách để sự kiện

E

xảy ra là:

1 2

1

...

r

r i

i

n n n n

1.1.2.Nguyên lý cộng

Nguyên lý cộng. Giả sử có:

1 n cách để sự kiện

E1

xảy ra,

2 n cách để sự kiện

E2 xảy ra,

...

k n cách để sự kiện

Ek

xảy ra,

trong đó k > 1. Nếu các cách để xảy ra các sự kiện khác nhau nói

trên là từng đôi một rời nhau thì số cách để ít nhất một trong các sự

kiện E1, E2,..., hoặc Ek xảy ra là :

1 2

1

...

k

k i

i

n n n n

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

1.2.1. Chỉnh hợp lặp

5

Định nghĩa 1.1. 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.

Số các chỉnh hợp lặp. 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

.

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

Định nghĩa 1.2 . 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 phần tử đã cho

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

Số các chỉnh hợp không lặp. Số các chỉnh hợp không lặp chập k

của n phần tử kí hiệu :

k

A

n

. Ta xây dựng công thức tính

k

A

n

.

Một chỉnh hợp không lặp chập k của n phần tử có thể được xây dựng

qua k bước kế tiếp như sau :

Chọn các thành phần đầu : có n khả năng .

Chọn các thành phần thứ hai : có n – 1 khả năng .

…

Chọn các thành phần thứ k : có n – k + 1 khả năng .

Như vậy, theo nguyên lý nhân, số tất cả chỉnh hợp không lặp chập k

của n phần tử là :

!

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

( )!

n

A n k n n n k

n k

.

1.2.3.Hoán vị

Định nghĩa 1.1. 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ử đó .

6

Số các hoán vị. Gọi P(n) là số các hoán vị khác nhau có thể lập từ n

phần tử khác nhau. Ta có :

P(n) = n !

1.2.4. Tổ Hợp

Định nghĩa 1.3. 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 .

Số các tổ hợp. Gọi số tổ hợp chập k của n phần tử là C(n,k) ta có:

A(n,k) = C(n,k) . k!

Suy ra

!

( , )

!.( )!

n

C n k

k n k

.

Hệ quả 1.1. Tích k số tự nhiên liên tiếp chia hết cho k!.

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

1.3.1. Hoán vị lặp

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

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

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

tử thứ nhất lặp n1 lần, phần tử lặp 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

.... n n nk

7

Hệ quả1.2. Giả sử tập S có n phần tử, trong đó có n1 phần tử kiểu 1,

n2 phần tử kiểu 2,…, nk phần tử kiểu k. Khi đó số các hoán vị n phần

tử của S là:

1 2

1 2

!

( ; , ,..., )

! !... ! k

k

n

P n n n n

n n n

.

1.3.2. Tổ hợp lặp

Định nghĩa 1.5. Tổ hợp lặp chập k từ n phần tử khác nhau 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ải sử X 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 n C k n k ( , ) ( 1, 1) ( 1, ).

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

Định nghĩa 1.6. 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

1 2 , ,... k S S S

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

1 2 , ,... n n nk

thỏa

1 2 ... n n n r k

. Số các

phân hoạch thứ tự tổ hợp chập

r

của X dạng

1 2 , ,..., k S S S

có

1 S

=

1, 2 2 ,..., n S n S n k k

được kí hiệu là

1 2 ; , ,..., C n n n nk

. Một cấu

hình tổ hợp kiểu này được xây dựng trên các bước như sau :

Bước 1: chọn

1 n

phần tử từ X cho

1 S

, có

1 C n n,

khả năng

Bước 2: chọn

2 n

phần tử từ X\

1 S

cho

2 S

, có

1 2 C n n n,

khả năng

…

Bước k : chọn

k n

phần tử từ

1 2 1 | ( ... ) X S S Sk

cho

k S , có

1 2 1 ( ... , ) C n n n n n k k

khả năng.

Theo nguyên lí nhân suy ra: