Hàm sinh mũ và ứng dụng giải bài toán đếm trong tổ hợp

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

ĐẠI HỌC ĐÀ NẴNG

NGUYỄN THỊ DUYÊN

HÀM SINH MŨ VÀ ỨNG DỤNG

GIẢI BÀI TOÁN ĐẾM TRONG TỔ HỢP

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

Mã số : 60.46.01.13

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

Đà Nẵng – Năm 2015

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. Phan Đức Tuấn

Phản biện 2: GS.TSKH. Nguyễn Văn Mậu

Luận văn đã được bảo vệ trước 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 12 tháng 12 năm 2015.

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

Tư duy về toán rời rạc ra đời rất sớm. Tuy nhiên, cho đến

khoảng giữa thế kỉ XVII, lí thuyết toán rời rạc mới được hình thành

như một ngành toán học. Lí thuyết tổ hợp là một phần quan trọng của

toán 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. 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 đó. Mỗi cách

phân bố như vậy được gọi là một cấu hình tổ hợp. Một trong những

vấn đề đầu tiên của việc nghiên cứu tổ hợp là đếm (có thể liệt kê)

xem có bao nhiêu cấu hình được tạo ra với những quy tắc đã nêu?

Bài toán đếm có nội dung rất phong phú kể cả dạng phát biểu lẫn

cách giải. Một trong những phương pháp giải bài toán đếm phải kể

đến đó là ứng dụng hàm sinh để giải. Phương pháp này đã đưa bài

toán tổ hợp về bài toán sử dụng các tính chất của hàm số để giải.

Những điều này đã gây hứng thú cho tôi. Vì vậy mà tôi đã chọn nó

làm hướng nghiên cứu chính cho luận văn của mình với tên đề tài là:

Hàm sinh mũ và ứng dụng giải bài toán đếm trong tổ hợp.

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

Hàm sinh mũ và ứng dụng hàm sinh mũ giải một số bài toán

đếm trong tổ hợp.

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

Nghiên cứu hàm sinh mũ cùng các ứng dụng của nó. Thông

qua đó giúp chúng ta giải các bài toán đếm tổng quát cũng như

2

chứng minh được nhiều công thức mà có thể sử dụng vào giải các bài

toán đếm trong phạm vi cho phép.

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

Đọc, nghiên cứu hàm sinh mũ cùng các ứng dụng của nó.

Nêu phương pháp và giải các bài toán đếm bằng cách sử dụng hàm

sinh mũ.

5. Phương pháp và cách tiếp cận nghiên cứu

Phương pháp nghiên cứu là đi từ lí thuyết về hàm sinh mũ, từ

việc xây dựng phương pháp giải các bài toán đếm tổng quát.

6.Tính mới và sáng tạo

Thông qua các bài toán mang tính tổng quát, chúng ta có thể

đưa ra nhiều bài toán áp dụng rất hiệu quả.

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

Có thể sử dụng luận văn làm tài liệu tham khảo giúp giáo viên

tổng quát hóa hay cụ thể hóa một số bài toán trong lĩnh vực tổ hợp

đồng thời xây dựng được phương pháp giải chung cho từng dạng

toán đó.

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

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

dung của luận văn được chia làm ba chương:

Chương 1. Đại cương về tổ hợp

Chương 2. Hàm sinh mũ.

Chương 3. Ứng dụng hàm sinh mũ để giải các bài toán đếm

trong tổ hợp.

3

CHƯƠNG 1

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

Trong chương này, tác giả trình bày một số quy tắc đếm cơ bản

và các định nghĩa liên quan trong các bài toán đếm. Các kiến thức

trong chương 1 có thể xem tại các tài liệu [1], [3], [5], [7], [8].

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

1.1.1. Nguyên lí nhân

Nguyên lý nhân: 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ể thực hiện n1 cách, bước 2 có thể thực hiện

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

hợp là: 1 2 . . ... . k

n n n

1.1.2. Nguyên lí cộng

Nguyên lý cộng: Giả sử {X1 2 ; X X ;...; n} là một phân hoạch

của tập S. Khi đó : 1 2 ... n

S = X + X X + +

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.2.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 phần tử đã

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

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

4

Số tất cả các chỉnh hợp không lặp chập k của n phần tử là:

( ) ( ) ( )

( )

; . –1 .

!

1

!

A n k n n . – n k n

n k

º + =

-

=

1.2.3. Hoán vị

Định nghĩa 1.2.3: 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. Vậy số các hoán vị của n phần tử là:

P(n) = n.(n n - = 1).....2.1 !

1.2.4. Tổ hợp

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

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 ). . P k( )

Suy ra,

( )

!

( ; )

! !

n

C n k

k n 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.3.1: 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.

Định lí 1.3.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ử thứ hai lặp n2 lần,… , phần tử thứ

k lặp nk

lần là

5

1 2

1 2

!

( ; , ,..., )

! !... ! k

k

n

P n n n n

n n n

=

với 1 2 ... k

n = n + n n + + .

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

1, có n2 phần tử kiểu 2,… , có 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.3.2: 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.

Lập luận tương tự ví dụ 17, ta có định lí sau:

Định lý 1.3.2: Giả 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 – 1;n – 1) = + C(k n k – 1; )

1.3.3. Phân hoạch không thứ tự

Định nghĩa 1.3.4: Cho X là một tập gồm n phần tử khác nhau,

các số nguyên dương n1; n2; …, nk và p1,p2, …,pk thỏa n1.p1 + n2.p2 +

… + nk

.pk = n. Một hệ thống các tập con của X gồm p1 tập lực lượng

n1, p2 tập lực lượng n2, …, pk

tập lực lượng nk

gọi là phân hoạch

không thứ tự của X.

Định lý 1.3.4: Số phân hoạch không thứ tự của X với p1 tập lực

lượng n1, p2 tập lực lượng n2, …, pk

tập lực lượng nk

là

6

1 2

1 1 2 2

1 2 1 1 2 2

( ; ,..., , ,..., ,..., ,..., ) !

! !... ! !( !) !( !) ... !( !) k

k k

p p p

k k k

C n n n n n n n n

p p p p n p n p n

=

trong tử số, số n1 lặp lại p1 lần, số n2 lặp lại p2 lần, ..., số nk

lặp lại pk

lần.

1.4. PHÂN HOẠCH CỦA TẬP HỢP. SỐ STERLING LOẠI

HAI VÀ SỐ BELL

Định nghĩa 1.4.1: Cho X là một tập gồm n phần tử khác nhau.

1) Một phân hoạch của một tập hữu hạn X thành k phần (khối)

là một họ các tập con khác rỗng X1;X2; … ;Xk của X thỏa các tính

chất sau:

i) Hợp tất cả các tập hợp Xi

, i = 1,2,…k tạo thành tập hợp X,

tức là:

1 2 ... X » X » » = X X k

ii) Các tập hợp này đôi một giao nhau bằng tập hợp rỗng, tức là:

, Xi j « X = Æ " ¹i j

2) Số tất cả các phân hoạch thành k phần của một tập X có n

phần tử được gọi là số Sterling loại hai và được kí hiệu là Sn,k.

3) Số ,

0

n

n n k

k

B S

=

= Â được gọi là số Bell.

7

CHƯƠNG 2

HÀM SINH MŨ

Trong chương này, tác giả trình bày các nội dung về hàm

sinh mũ. Các kiến thức trong chương này có thể xem thêm tại các tài

liệu [1],[4],[6],[8],[9],[10].

2.1. CÁC ĐỊNH NGHĨA

Cho dãy số thực ( r )

r

a = <a0; a1; a2; ... > và biến x.

Định nghĩa 2.1.1

Hàm sinh mũ của dãy <a0; a1; a2; ... > là hàm

2

0 1 2

0

( ) ...

1! 2! !

n

n

n

x x x G x a a a a

n

•

=

= + + + = Â (2.1)

Chúng ta có thể định nghĩa hàm sinh mũ cho dãy số hữu hạn

a0; a1; a2; ... ;an như sau:

Định nghĩa 2.1.2

2

0 1 2

0

( ) ...

1! 2! ! !

n r n

n r

r

x x x x H x a a a a a

n r

=

= + + + + =Â (2.2)

là hàm sinh mũ cho dãy số hữu hạn a0; a1; a2; ... ;an .

Định nghĩa 2.1.3

Hàm sinh thường của dãy <a0; a1; a2; ... > là hàm

2 3

0 1 2 3

0

( ) ...

n

n

n

g x a a x a x a x a x

•

=

= + + + + = Â (2.3)

8

2.2. CÁC ĐỊNH LÝ

ß Định lý 2.2.1

i) Nếu G(x) là hàm sinh của dãy (ar)r

thì xG x'( ) là hàm sinh

của dãy( r )

r

ra .

ii) Nếu G(x) là hàm sinh mũ của dãy ( r )

r

a và H(x) là hàm

sinh mũ của dãy ( r )

r

b thì pG(x) + qH x( ) là hàm sinh mũ của dãy

( r r ) , , R r

pa + qb " Πp q .

iii) Nếu G(x) và H(x) lần lượt là hàm sinh mũ của dãy ( r )

r

a

và ( r )

r

b thì G(x) . H(x) là hàm sinh mũ của dãy tích chập nhị thức

( )

0

,

r

i r i

i r

C r i a b -

=

Ê ˆ Á ˜

Ë ¯ Â .

ß Định lý 2.2.2: Nếu G(x) là hàm sinh mũ của dãy (ar)r

thì

( ) (0) r

r

a G= , với mọi số nguyên dương r, trong đó ( ) (0) r G đạo hàm

cấp r của hàm G(x) tại x = 0.

2.3. CÁC TÍNH CHẤT CỦA HÀM SINH MŨ

Cho hai hàm sinh mũ

0 0

( ) ; ( )

! !

n n

n n

n n

x x G x a H x b

n n

• •

= =

= = Â Â

2.3.1. Các hàm sinh bằng nhau

Hai hàm sinh

0 0

( ) ; ( )

! !

n n

n n

n n

x x G x a H x b

n n

• •

= =

= = Â Â được gọi là

bằng nhau nếu an = bn với mọi n nguyên không âm.

như sau: