Tóm tắt luận văn Thạc sĩ Khoa học: Số các ánh xạ không phân rã được trên tập hữu hạn

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG

NGUYỄN VĂN TIẾN

SỐ CÁC ÁNH XẠ KHÔNG PHÂN RÃ

ĐƯỢC TRÊN TẬP HỮU HẠN

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 2011

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: TS. Nguyễn An Khương

Phản biện 1: TS. Lê Hải Trung Phản biện 2: PGS. TS. Nguyễn Gia Định

Luận văn sẽ đượ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 28 tháng 5 năm 2011.

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ổ hợp là một lĩnh vực quan trọng của toán học nói chung và toán rời rạc nói riêng. Các bài toán tổ hợp có nội dung phong phú, được nghiên cứu và ứng dụng rộng rãi trong thực tế đời sống và trên nhiều lĩnh vực khác nhau, đặc biệt là xác suất thống kê.

Hiện nay, kiến thức cơ bản về tổ hợp đã được đưa vào chương trình giảng dạy ở lớp 11. Trong những kì thi tuyển sinh đại học, 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 và cao đẳng thì các bài toán tổ hợp hay được đề cập và thường thuộc loại khó. Đối với những bài toán tổ hợp phức tạp việc áp dụng các kiến thức cơ bản để giải sẽ gặp nhiều khó khăn, nên cần có những phương pháp sắc bén hơn.

Chính vì những lí do trên, chúng tôi chọn đề tài "Số ánh xạ không phân rã được trên tập hữu hạn"nhằm nghiên cứu về số các ánh xạ trên các tập hữu hạn thỏa mãn tính chất mà chúng tôi gọi là "không phân rã được".

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

Mục đích của đề tài là đề xuất thêm phương pháp chứng minh mới, hoàn toàn bằng sơ cấp để tính số ánh xạ không phân rã được trên tập hữu hạn.

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

Đối tượng nghiên cứu là số ánh xạ không phân rã được. Phạm vi nghiên cứu là số ánh xạ không phân rã được trên tập hữu hạn.

2

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

Đọc hiểu và sử lý tài liệu tham khảo đồng thời làm việc theo sự hướng

dẫn của người hướng dẫn khoa học.

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

Hệ thống hóa các phương pháp tìm số ánh xạ không phân rã được trên

tập hữu hạn.

Đưa ra cách chứng minh mới cho việc tìm số ánh xạ không phân rã được

trên tập hữu hạn.

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

Luận văn được chia làm bốn chương. Chương 1: Kiến thức chuẩn bị. Trong phần này chúng tôi giới thiệu những kiến thức và các kết quả cơ bản về các quy tắc đếm, sử dụng quy tắc song ánh, phân hoạch tổ hợp để giải quyết các bài toán tổ hợp, đồng thời nêu khái niệm về xích và độ dài của xích.

Chương 2: Các số tổ hợp cơ bản. Chương này chúng tôi nhắc lại các số tổ hợp cơ bản, đó là các số Hoán vị, Chỉnh hợp, Tổ hợp, số Stirling loại một, số Stirling loại hai và số Bell cùng với số các ánh xạ đặc biệt trên tập hữu hạn.

Chương 3: Dãy nhị thức. Trong chương này luận văn giới thiệu sơ lược về dãy nhị thức Pn(t)n≥0. Chương 4: Ánh xạ không phân rã được. Đây là chương cơ bản và quan trọng nhất của luận văn chúng tôi đưa ra một số khái niệm mới như ánh xạ không phân rã được từ tập [n] vào chính nó. Đặc biệt chúng tôi đưa ra cách chứng minh mới để tìm số ánh xạ không phân rã được trên tập hữu hạn.

3

Chương 1

KIẾN THỨC CHUẨN BỊ

1.1.1 Quy tắc cộng

1.1 Quy tắc cộng, quy tắc nhân

Nếu có m1 cách chọn đối tượng a1, m2 cách chọn đối tượng a2, ..., mn cách chọn đối tượng an, trong đó cách chọn đối tượng ai (1 ≤ i ≤ n) không phụ thuộc vào bất kì cách chọn đối tượng aj nào (1 ≤ j ≤ n, i (cid:54)= j) thì

n(cid:80)

sẽ có

k=1

n(cid:80)

mk cách chọn đối tượng a1, hoặc a2, ..., hoặc an.

Để vận dụng có hiệu quả, ta chuyển qui tắc này sang dạng sau: Cho n tập hợp Ak (1 ≤ k ≤ n) với |Ak| = mk và ∀i, j(1 ≤ i, j ≤ n)Ai ∩ Aj = ∅, khi i (cid:54)= j. Khi đó số cách chọn a1, hoặc a2, ..., hoặc an sẽ n(cid:83)

n(cid:83)

bằng số cách chọn các phần tử a ∈

k=1

k=1

k=1

1.1.2 Quy tắc nhân

|Ak|. Ak| = Ak và |

Cho n đối tượng a1, a2, ..., an. Nếu có m1 cách chọn đối tượng a1 và ứng với mỗi cách chọn a1 ta có m2 cách chọn đối tượng a2, sau đó với mỗi cách chọn a1, a2 ta có m3 cách chọn đối tượng a3, ... Cuối cùng với mỗi cách chọn a1, a2, ..., an−1 ta có mn cách chọn đối tượng an.

Vậy sẽ có m1.m2.....mn−1.mn cách chọn các đối tượng a1, rồi a2,..., rồi

an.

Chú ý 1. Để vận dụng có hiệu quả, ta chuyển quy tắc nhân sang dạng sau:

4

Giả sử có n tập hợp Ak (1 ≤ k ≤ n) với |Ak| = mk. Khi đó, Số cách chọn (S) bộ gồm n phần tử (a1, a2, ..., an) với ai ∈ Ai(1 ≤ i ≤ n) sẽ là:

n (cid:89)

k=1

S = |A1.A2.....An| = m1.m2.....mn = mk

1.2 Nguyên lý bù trừ

Định lý 1.1. [4] Cho n≥2 tập hợp hữu hạn A1, ..., An. Khi đó ta có :

n (cid:88)

|A1 ∪ A2 ∪ ... ∪ An| =

i=1

1≤i

1≤i

(cid:88) (cid:88) |Ai| − |Ai ∩ Ak| + |Ai ∩ Aj ∩ Ak|

+... + (−1)k+1|Ai1 ∩ Ai2... ∩ Aik|

1≤i1

(∗)

1.3 Quy tắc song ánh

Định lý 1.2. [4] Cho hai tập hợp A, B hữu hạn Nếu có một đơn ánh f: A −→ B thì |A| ≤ |B|. Nếu có một toàn ánh f: A −→ B thì |A| ≥ |B|. Nếu có một song ánh f: A −→ B thì |A| = |B|.

1.4 Độ dài của xích

Chú ý 2. Mỗi song ánh từ tập N = {1, 2, ..., n} vào chính nó được gọi là một phép thế trên n phần tử. Gọi Sn là tập hợp tất cả các phép thế trên n phần tử. Nếu α, β ∈ Sn thì ánh xạ hợp thành αβ xác định bởi công thức: αβ(i) = α(β(i)), (1 ≤ i ≤ n) cũng là một song ánh từ tập N = {1, 2, ..., n} vào chính nó, tức αβ ∈ Sn

5

Định nghĩa 1.1. [3] Giả sử x1, ..., xk là các phần tử đôi một khác nhau trong {1, 2, ..., n}. Ta kí hiệu bởi (x1, x2, ..., xk) phép thế giữ nguyên các phần tử khác x1, x2, ..., xk và tác động trên x1, ..., xk như sau:

x1 (cid:55)→ x2, x2 (cid:55)→ x3, ..., xk−1 (cid:55)→ xk, xk (cid:55)→ x1.

Nó được gọi là một xích với độ dài k trên tập nền {x1, x2, ..., xk}. Với (x1, ..., xk) được gọi là một xích của phép thế α ∈ Sn nếu α tác động giống như (x1, ..., xk) trên các phần tử x1, x2, ..., xk (α có thể tác động không tầm thường trên các phần tử x1, ..., xk).

Định lý 1.3. [3] Mọi phép thế α ∈ Sn đều là tích của tất cả các xích khác nhau của nó. Các tập nền của các xích này là các tập con rời nhau của tập {1, 2, ..., n}.

Nhận xét 1.1. Khi viết một phép thế của Sn như là tích của các xích rời rạc, tức là xích với tập nền rời nhau, thì thứ tự của các xích ở trong tích là không quan trọng.

6

Chương 2

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

2.1.1 Chỉnh hợp lặp

2.1 Cấu hình tổ hợp

Định nghĩa 2.1. Cho tập hữu hạn X gồm n phần tử. Mỗi dãy có độ dài k các phần tử của tập X, mà mỗi phần tử có thể lặp lại nhiều lần và được sắp xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập k của n phần tử thuộc tập X.

Định lý 2.1. [4] Số chỉnh hợp lặp chập k của n phần tử, kí hiệu là n, thì Ak Ak

n = nk

2.1.2 Hoán vị

Định nghĩa 2.2. Cho một tập hợp gồm n (n ≥ 1) phần tử . Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó ( mỗi phần tử có mặt đúng một lần) được gọi là một hoán vị của n phần tử đã cho.

Định lý 2.2. [4] Kí hiệu số hoán vị của n phần tử là Pn thì Pn = n!

2.1.3 Hoán vị lặp

Định nghĩa 2.3. Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị lặp.

Định lý 2.3. [4] Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i (1 ≤ i ≤ k) xuất hiện ni lần được kí hiệu là P (n1, n2, ..., nk)

7

và được tính bằng công thức:

2.1.4 Tổ hợp lặp

P (n1, n2, ..., nk) = , n = n1 + n2 + ... + nk. n! n1!n2!...nk!

Định nghĩa 2.4. Cho tập hợp A = {a1, a2, ..., an}. Một tổ hợp lặp chập m (m không nhất thiết phải nhỏ hơn n ) của n phần tử thuộc A là một bộ gồm m phần tử, mà mỗi phần tử này là một trong những phần tử của A.

n để kí hiệu số tổ hợp lặp chập m của n

Định lý 2.4. Ta sử dụng C m phần tử. Khi đó:

n = C m

n+m−1

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

C m

Định nghĩa 2.5. Giả sử X là một tập hợp gồm n phần tử. Khi đó ta có phân hoạch của tập X thành k khối là một họ tùy ý π = {B1, B2, ..., Bk} mà B1 ∪ B2 ∪ ...Bk = X, Bi ∩ Bj = ∅ với mọi 1 ≤ i < j ≤ k và Bi (cid:54)= ∅ với mọi 1 ≤ i ≤ k. Các tập con B1, ..., Bk được gọi là các khối của phân hoạch π.

Định nghĩa 2.6. Giả sử X là một tập hợp gồm n phần tử khác nhau, r ≤ n và S ⊂ X có r phần tử. Một phân hoạch {S1, S2, ..., Sk} có thứ tự 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: n1 + n2 + ... + nk = r. Số các phân hoạch thứ tự tổ hợp chập r của X dạng {S1, S2, ..., Sk} có |S1| = n1, |S2| = n2, ..., |Sk| = nk được kí hiệu là C(n; n1, n2, ..., nk).

Định lý 2.5. [2]

= P (n1, n2, ..., nk, n − r). C(n; n1, n2, ..., nk) = n! n1!n2!...nk!(n − r)!

8

Định lý 2.6. [2] Số phân hoạch không thứ tự của tập X gồm: p1 tập có n1 phần tử, p2 tập có n2 phần tử, ..., pk tập có nk phần tử được tính theo công thức:

C(n; n1, ..., n1, n2, ..., n2, ..., nk, ..., nk) p1!p2!...pk!

. = n! p1!(n1!)p1p2!(n2!)p2...pk!(nk!)pk

(trong C(n; n1, ..., n1, n2, ..., n2, ..., nk, ..., nk) 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)

2.2 Các số Stirling loại một, số Stirling loại hai và số

2.2.1 Số Stirling loại một

Bell

Định nghĩa 2.7. Số song ánh trên tập n phần tử được tách thành k vòng xích được gọi là số Stirling loại một không dấu, kí hiệu là cn,k. Số sn,k = (−1)n−kcn,k. được gọi là số Stirling loại một. Từ định nghĩa ta rút ra được cn,k = 0, ∀k > n.

Định lý 2.7. [8] Với n là số nguyên không âm cố định, ta có:

n (cid:88)

k=0

x(n) = (2.1) cn,kxk

với x(n) = x(x + 1)...(x + n − 1), x(0) := 1.

Mệnh đề 2.1. Ta có:

n (cid:88)

k=0

sn,kxk = x(n).

vào Mệnh đề 2.1 và Định lí 2.7 ta được mệnh đề sau.

Thay x =

1≤k≤n

1 u Mệnh đề 2.2. [6] Ta có: (cid:88) a) sn,kun−k = (1 − u)(1 − 2u)...(1 − (n − 1)u).

9

1≤k≤n

(cid:88) b) cn,kun−k = (1 + u)(1 + 2u)...(1 + (n − 1)u).

Thay n bằng n + 1 và k bằng n + 1 − k vào Mệnh đề 2.2 b ta được:

1≤n+1−k≤n+1

(cid:88) cn+1,n+1−kuk = (1 + u)(1 + 2u)...(1 + nu),

hay

0≤k≤n

0≤k≤n

0≤i1≤i2≤...≤ik≤n

(cid:88) (cid:88) (cid:88) cn+1,n+1−kuk = i1i2...ikuk.

Đồng nhất hệ số của uk hai vế ta thu được hệ quả sau.

Hệ quả 2.2.1. [6] Với k = 1, 2, ..., n ta có:

0≤i1≤i2≤...≤ik≤n

(cid:88) cn+1,n+1−k = i1i2...ik.

Dựa vào các kết quả trên, chúng ta tính được số các Stirling loại một

2.2.2 Số Stirling loại hai và số Bell

sn,k với một số giá trị đầu tiên được nêu trong Bảng 2.1.

Định nghĩa 2.8 (7). Số tất cả các phân hoạch của tập hợp A gồm n phần tử thành k khối gọi là số Stirling loại hai, kí hiệu là Sn,k.

Ta qui ước S0,0 = 1, S0,k = 0 nếu k > 0 và Sn,0 = 0 nếu n > 0. Từ định nghĩa này ta dễ dàng nhận thấy Sn,k = 0 nếu k > n và

Sn,1 = Sn,n = 1.

Định lý 2.8. [9] Với n, k là các số nguyên dương và k ≤ n ta có:

Sn+1,k = kSn,k + Sn,k−1.

Chú ý 3. Từ Sn,1 = Sn,n = 1 và từ công thức truy hồi của Sn,k ta thấy Sn,k có những tính chất giống như đối với công thức tổ hợp C k n nên ta cũng xây dựng được tam giác để tìm giá trị Sn,k như sau:

S1,1 S2,1 S2,2

10

S3,2 S4,2 S5,2 S6,2 S3,3 S4,3 S5,3 S6,3 S4,4 S5,4 S6,4 S5,5 S6,5 S6,6

S3,1 S4,1 S5,1 S6,1 .................................................................................

Mệnh đề 2.3. Với n, k là các số nguyên dương và k ≤ n ta có:

k (cid:88)

k.jn.

j=1

(−1)k−jC j Sn,k = 1 k!

Định nghĩa 2.9. Số tất cả các phân hoạch của tập hợp A lực lượng n được gọi là số Bell thứ n. Kí hiệu Bn.

Từ định nghĩa 2.9 và định nghĩa 2.10, ta có:

n (cid:88)

k=0

Bn = Sn,k.

2.3 Số các ánh xạ đặc biệt trên tập hữu hạn

Mệnh đề 2.4. [9] Cho tập hợp N = {1, 2, ..., n} và tập hợp M = {1, 2, ..., m}. Khi đó số tất cả các ánh xạ f : N −→ M là mn.

Mệnh đề 2.5. [9] Cho tập hợp N = {1, 2, ..., n} và tập hợp M = {1, 2, ..., m}, với n ≤ m.

Khi đó số tất cả các đơn ánh f : N −→ M là m(m−1)...(m−n+1).

Nhận xét 2.1.

Ta thấy từ mệnh đề 2.5 trong trường hợp n = m thì chúng ta dễ dàng

suy ra được kết quả sau đây.

Mệnh đề 2.6. Cho tập hợp N = {1, 2, ..., n}.

Khi đó số tất cả các song ánh f : N −→ N là n!

Mệnh đề 2.7. [9] Cho tập hợp N = {1, 2, ..., n} .

Khi đó số tất cả các tập con k phần tử của tập N là C k n.

11

Chú ý 4. Ngoài những cách hiểu đã nói trên, chúng ta có thể lập luận như sau:

Số tất cả các đơn ánh f : N −→ M , với n ≤ m là n!C n

m, với C n

m là số

tất cả các tập con n phần tử của tập M .

Mệnh đề 2.8. [9] Cho tập hợp N = {1, 2, ..., n} và tập hợp M = {1, 2, ..., m}, với n ≥ m.

Khi đó số tất cả các toàn ánh f : N −→ M là Sn,m.m!

12

Chương 3

DÃY NHỊ THỨC

3.1 Khái niệm dãy nhị thức

Định nghĩa 3.1. [1] Một dãy các đa thức một biến thực Pn(t)n≥0 với deg(Pn(t))≤ n, n = 0, 1, 2,... được gọi là dãy nhị thức nếu:

nPk(u)Pn−k(t), n = 1, 2, ...,

k=0

i)P0(t) = 1, t ∈ R , n (cid:88) C k t, u ∈ R . ii)Pn(t + u) =

3.2 Dãy nhị thức sinh bởi một dãy số

Định lý 3.1. [1] Dãy các đa thức {Pn(t)}n≥0, t ∈ R là dãy nhị thức khi và chỉ khi tồn tại một dãy số thực {ak}k≥1 sao cho:

i) P0(t) = 1, ii) Pn(t) = n! (cid:80)n

k=1((cid:80)

k!, n = 1, 2, 3, ...

ai1 i1!

i2! ... aik ai2

ik! ) tk

ij=n

(i1,...,ik):

k (cid:80) j=1 ij≥1

Định nghĩa 3.2. [1]Cho trước dãy số thực {ak}k≥1. Giả sử rằng {Pn(t)}n≥0 là dãy các đa thức thoả mãn các điều kiện i), ii) trong định lí 3.1. Ta gọi {Pn(t)}n≥0 là dãy nhị thức sinh bởi dãy {ak}k≥1 đã cho. (cid:88)

n(cid:80)

...

Nếu đặt λn,k =

thì Pn(t) =

k=1

ij=n

(i1,...,ik):

k (cid:80) j=1 ij≥1

λn,ktk. n! k! ai1 i1! ai2 i2! aik ik!

13

Các số λn,k được gọi là các hệ số của dãy nhị thức. Ta sẽ tìm công thức truy hồi để tính các hệ số của dãy nhị thức theo dãy

số thực {ak}k≥1

Mệnh đề 3.1. Với λn,0 = 0, λn,1 = an ∀n ≥ 0, λ0,0 = 1, ta có:

n+1−k (cid:88)

nλn−j,k−1,

j=1

n = 1, 2, ..., k = 1, 2, ... λn,k = ajC j 1 k

3.3 Dãy nhị thức sinh bởi một hàm số

Cho hàm số f có khai triển thành chuỗi lũy thừa hội tụ trong miền [0, R)

với R > 0 nào đó như sau:

∞ (cid:88)

k=1

, f (0) = 0 f (x) = ak xk k!

Khi đó, dãy số {ak}k≥1 với ak = f (k)(0), k = 1, 2, ... sẽ xác định một dãy nhị thức, ta gọi dãy nhị thức này là dãy nhị thức sinh bởi hàm số f .

Dựa vào định lí 3.1 ta có mệnh đề sau.

Mệnh đề 3.2. [1] Giả sử {Pn(t)}n≥0 là dãy nhị thức sinh bởi hàm số f . Khi đó:

∞ (cid:88)

k=1

= etf (x). {Pn(t)} xn n!

14

Chương 4

ÁNH XẠ KHÔNG PHÂN RÃ ĐƯỢC

4.1 Đặt vấn đề lịch sử

Có thể nói các vấn đề liên quan tới lý thuyết tổ hợp là một bộ phận quan trọng, hấp dẫn và lí thú của toán học. Các vấn đề này có nội dung phong phú và được ứng dụng nhiều trong thực tế đời sống. Trong toán sơ cấp tổ hợp cũng xuất hiện nhiều với mức độ khó khá cao. Khi giải quyết các bài toán tổ hợp người quan tâm sẽ cảm thấy rất hấp dẫn . Trong đó việc phân lớp các ánh xạ trên tập hữu hạn và đếm số ánh xạ trong mỗi lớp là một bài toán tổ hợp khó. Cho đến nay, các kết quả về số các toàn ánh, đơn ánh và song ánh trên tập hữu hạn được coi là các kết quả rất cơ bản.

Bài toán phân tích các song ánh trên tập hữu hạn thành các vòng xích độc lập đã được mở rộng lên thành việc xét bài toán tương tự cho ánh xạ tuỳ ý trên tập hữu hạn. Tuy kết quả này đã được các nhà toán học trước đây đưa ra (Leo Katz (1954) và Martin D. Kruskal (1954) ), nhưng đây là vấn đề hết sức thú vị trong tổ hợp nên chúng tôi xét thấy việc đưa thêm ra cách chứng minh mới cho kết quả này là vấn đề có ý nghĩa.

Việc mô tả số Stirling loại một không dấu cn,k về mặt thống kê theo nghĩa đếm số tất cả các song ánh được phân tích thành k vòng xích độc lập trên tập n phần tử có thể coi là rất đầy đủ và có mặt trong nhiều tài liệu cơ bản. Tuy nhiên các kết quả tương tự khi xét tập tất cả các ánh xạ trên tập n phần tử gặp nhiều khó khăn, mặc dù ta có thể mô tả về mặt cấu trúc thông qua công cụ đồ thị và mảnh tổ hợp. Chúng tôi giới thiệu một kết quả mới nhận được chỉ bằng phương pháp sơ cấp chúng tôi đã chứng minh được rằng số tất cả các ánh xạ f không phân rã được từ tập N = {1, 2, ..., n}

15

vào chính nó là:

n (cid:88)

k=0

αn = (n − 1)! nn−k (n − k)!

Việc chứng minh quy nạp cho đẳng thức này chính là phần mới và cũng

là phần cơ bản nhất của luận văn này.

4.2 Định nghĩa

Định nghĩa 4.1. Một ánh xạ f từ tập N = {1, 2, ..., n} vào chính nó được gọi là ánh xạ phân rã được nếu tồn tại một tập con thật sự và không rỗng K, |K| = k, 1 ≤ k ≤ n sao cho f −1(K) ⊂ K

Định nghĩa 4.2. Một ánh xạ f từ tập N = {1, 2, ..., n} vào chính nó được gọi là ánh xạ không phân rã được nếu nó không phải là ánh xạ phân rã được .

i, j = 1, k i (cid:54)= j,

Định nghĩa 4.3. Một ánh xạ f từ tập N = {1, 2, ..., n} vào chính nó được gọi là một ánh xạ có k thành phần không phân rã được nếu nó tồn tại một phân hoạch N = N1 ∪ N2 ∪ ... ∪ Nk, Ni (cid:54)= ∅, Ni ∩ Nj = k ≥ 2 sao cho tất cả các hạn chế fi của f ∅, trên mỗi tập con Ni Như vậy ta có thể phân tích một ánh xạ f từ tập N = {1, 2, ..., n} vào chính nó thành các thành phần không phân rã được tương tự như khi phân tích một song ánh từ tập N vào chính nó thành các vòng xích.

4.3 Chứng minh kết quả cơ bản

Kết quả cơ bản này đã được chứng minh trong bài báo ”Components under a random mapping function" của nhà toán học Martin D. Kruskal và bài báo "Probability of a random mapping function" của nhà toán học Leo Katz bằng công cụ toán tử và các lập luận tổ hợp cơ bản đã đưa ra cách chứng minh vào năm 1954. Ngoài hai cách chứng minh trên, ở đây tôi đưa ra hai phương pháp chứng minh hoàn toàn bằng sơ cấp, đó là phương pháp

16

quy nạp và thiết lập công thức truy hồi để tính số các ánh xạ không phân rã được trên tập hữu hạn.

4.3.1 Phương pháp quy nạp

Nhận xét 4.1. Một ánh xạ f từ tập N = {1, 2, ..., n} vào chính nó được gọi là ánh xạ không phân rã được nếu nó thoả mãn một trong các điều kiện sau đây: i) Tồn tại duy nhất k0 ∈ N sao cho f (k0) = k0. ii) Tồn tại một tập con K thật sự và không rỗng của N sao cho khi hạn chế của f trên K thì f là một hoán vị vòng quanh. iii) f là một hoán vị vòng quanh trên N.

Từ nhận xét trên ta thấy để xây dựng một ánh xạ không phân rã được trên tập hữu hạn N ta phải xây dựng một hoán vị vòng quanh trên tập K với |K| = k , K ⊂ N , (1 ≤ k ≤ n) và ánh xạ các phần tử còn lại sao cho liên kết với hoán vị vòng quanh đó.

Do vậy, ta có mệnh đề đếm số tất cả các ánh xạ không phân rã được từ

tập N = {1, 2, ..., n} vào chính nó như sau.

Mệnh đề 4.1. Gọi αn là số tất cả các ánh xạ không phân rã được từ tập N = {1, 2, ..., n} vào chính nó, thì ta có:

n (cid:88)

k=1

ij=n−k

(i1,...,il):

l (cid:80) j=1 ij≥1

(cid:88) ... (∗) (k − 1)! αn = n! k! ki1 i1! ii2 1 i2! iil l−1 il!

Chứng minh. Để đếm số tất cả các ánh xạ không phân rã được từ tập N = {1, 2, ..., n} vào chính nó ta tiến hành theo các bước sau đây.

Trước hết ta tạo một hoán vị vòng quanh trên tập K với |K| = k,

K ⊂ N , (1 ≤ k ≤ n) nên ta có số hoán vị là (k − 1)!.

Tiếp theo chọn k phần tử trong n phần tử ta có số cách chọn là C k n. Xét dãy các tập hợp I1, I2, ..., Il , (1 ≤ l ≤ n − k) , |Ij| = ij sao cho

17

l(cid:80)

j=1 hợp I1, I2, ..., Il.

ij = n − k. Rồi sau đó ta phân phối n − k phần tử còn lại vào l tập

Ta có số cách phân phối n − k phần tử vào tập I1 là C i1

n−k, số cách ,..., số cách phân phối

n−k−i1

.

phân phối n − k − i1 phần tử vào tập I2 là C i2 n − k − i1 − ... − il−1 phần tử vào tập Il là C il

n−k−i1−...−il−1

Nên số cách phân phối n − k phần tử vào l tập hợp I1, I2, ..., Il là n−kC i2

n−k−i1

n−k−i1−...−il−1 Tiếp theo ta tạo ánh xạ từ tập I1 vào tập K có ki1 cách, ánh xạ từ tập

i2 cách,..., ánh xạ từ tập Il vào tập Il−1 có iil

C i1 ...C il .

l−1 cách.

I2 vào tập I1 có i1

Vậy ta có số tất cả các ánh xạ không phân rã được từ tập N =

n (cid:88)

{1, 2, ..., n} vào chính nó là:

n(k − 1)!

n−kC i2

n−k−i1

n−k−i1−...−il−1

k=1

ij=n−k

(i1,...,il):

l (cid:80) j=1 ij≥1

(cid:88) C k C i1 ...C il . αn =

Hay

n (cid:88)

k=1

ij=n−k

(i1,...,il):

l (cid:80) j=1 ij≥1

(cid:88) ... . (k − 1)! αn = n! k! ki1 i1! ii2 1 i2! iil l−1 il!

Định lý 4.1. (Số ánh xạ không phân rã được) Gọi αn là số tất cả các ánh xạ không phân rã được từ tập N = {1, 2, ..., n} vào chính nó khi đó ta có:

n (cid:88)

k=0

(1) αn = (n − 1)! nn−k (n − k)!

18

Chứng minh. Để chứng minh (1) trước hết ta cần chứng minh rằng

n−1nn−k,

ij=n−k

(i1,...,il):

l (cid:80) j=1 ij≥1

(cid:88) ... = C k−1 n! k! ki1 i1! ii2 1 i2! iil l−1 il!

hay:

ij=n−k

(i1,...,il):

l (cid:80) j=1 ij≥1

(cid:88) ... = knn−k−1 (2) (n − k)! ki1 i1! ii2 1 i2! iil l−1 il!

Ta chứng minh (2) bằng qui nạp theo n. Ta có:

ij=n−k

(i1,...,il):

l (cid:80) j=1 ij≥1

n−k (cid:88)

(cid:88) ... (n − k)! ki1 i1! ii2 1 i2! iil l−1 il!

h=1

ij=n−k

(i1,...,il):

l (cid:80) j=1 ij≥1 i1=h

(cid:88) ... = (n − k)! kh h! hi2 i2! iil l−1 il!

n−k (cid:88)

h=1

ij=n−k−h

(i1,...,il):

l (cid:80) j=2 ij≥1

(cid:88) ... . (n − k − h)! = kh(n − k)! h!(n − k − h)! hi2 i2! ii3 2 i3! iil l−1 il!

Mà:

ij=n−k−h

(i1,...,il):

l (cid:80) j=2 ij≥1

(cid:88) ... (n − k − h)! = h(n − k)n−k−h−1. hi2 i2! ii3 2 i3! iil l−1 il!

19

Do đó:

ij=n−k

(i1,...,il):

l (cid:80) j=1 ij≥1

n−k (cid:88)

(cid:88) ... (n − k)! ki1 i1! ii2 1 i2! iil l−1 il!

h=1

n−k (cid:88)

= h(n − k)n−k−h−1 kh(n − k)! h!(n − k − h)!

h=1

n−k−1 (cid:88)

kh−1(n − k)n−k−h = k (n − k − 1)! (h − 1)![n − k − 1 − (h − 1)]!

h=0

n−k−1 (cid:88)

kh(n − k)n−k−h−1 = k (n − k − 1)! h![n − k − 1 − h]!

n−k−1kh(n − k)n−k−h−1

h=0

C h = k

. = k[k + (n − k)]n−k−1 = k.nn−k−1

Nên:

n−1nn−k.

ij=n−k

(i1,...,il):

l (cid:80) j=1 ij≥1

(cid:88) ... = C k−1 n! k! ki1 i1! ii2 1 i2! iil l−1 il!

Thay kết quả này vào đẳng thức (*) ta được:

n (cid:88)

n−1nn−k.

k=1

n (cid:88)

(k − 1)!C k−1 αn =

k=0

. αn = (n − 1)! nn−k (n − k)!

20

4.3.2 Thiết lập công thức truy hồi

Định lý 4.2. [5] Gọi αn là số tất cả các ánh xạ không phân rã được từ tập N = {1, 2, ..., n} vào chính nó. Khi đó ta có:

α1 = 1,

ij=n

(i1,...,ik):

k (cid:80) j=1 ij≥1

(cid:88) ... αn+1 = nαn + (n + 1)! 1i1 i1! ii2 1 i2! iik k−1 ik!

n−1 (cid:88)

m=1

ij=m

(i1,...,il):

l (cid:80) j=1 ij≥1

(cid:88) ... +n! αn−m (n − m − 1)! 1i1 i1! ii2 1 i2! iil l−1 il!

Chứng minh. Với n = 1, ta dễ thấy rằng chỉ có đúng một ánh xạ không phân rã từ tập 1 vào chính nó.

Hay α1 = 1. Giả sử f là một ánh xạ không phân rã được từ tập N ∪ {n + 1} vào

chính nó. Ta đếm số các khả năng của f. Có hai trường hợp xảy ra:

1)Trường hợp 1: f −1(n + 1) = ∅. Vì có αn ánh xạ không phân rã được trên tập N và phần tử (n + 1) có

n cách cho ảnh nên

αn+1 = nαn.

2) Trường hợp 2: f −1(n + 1) (cid:54)= ∅. Ta xét dãy liên tiếp các tập hợp:

f −1(n + 1) ∩ N = I1,

f −1(I1) ∩ N = I2,

... f −1(Ik−1) ∩ N = Ik,

21

với |Ij| = ij, j = 1, k, 1 ≤ k ≤ n, và dễ thấy rằng dãy trên dừng tại k khi và chỉ khi Ik+1 = ∅. Ta có hai khả năng sau:

a) Không tồn tại một tập con thật sự S nào của N sao cho hạn chế của

f trên S là một ánh xạ không phân rã được từ tập S vào chính nó.

Gọi số các khả năng của f thuộc loại này là an+1,1.

k(cid:80)

ij = n.

Khi đó dãy các tập I1, I2, ..., Ik với 1 ≤ k ≤ n thoả

j=1

Để tạo một ánh xạ không phân rã được trên tập N ∪ {n + 1} vào chính nó, trước hết ta phân phối n phần tử của tập N vào k tập hợp I1, I2, ..., Ik, có C i1

n C i2

n−i1...C ik

n−(i1+...+ik−1) cách.

Tiếp theo ta tạo các ánh xạ từ tập I1 vào tập {n + 1} có 1i

1 cách, ánh

1 cách,..., ánh xạ từ tập Ik vào tập Ik−1 có iik

k−1

xạ từ tập I2 vào tập I1 có ii2 cách.

Cuối cùng là xác định ảnh của phần tử (n + 1) có (n + 1) cách. Do đó:

1 ...iik

n C i2

1ii2

k−1

n−i1...C ik

n−(i1+...+ik−1)1i

ij=n

(i1,...,ik):

k (cid:80) j=1 ij≥1

(cid:88) C i1 an+1,1 = (n + 1)

ij=n

(i1,...,ik):

k (cid:80) j=1 ij≥1

(cid:88) ... . = (n + 1)! 1i1 i1! ii2 1 i2! iik k−1 ik!

b) Tồn tại một tập con thật sự S của N sao cho hạn chế của f trên S

là một ánh xạ không phân rã được từ tập S vào chính nó. Gọi số các khả năng của f thuộc loại này là an+1,2. Dễ thấy rằng một ánh xạ không phân rã được từ tập N vào chính nó không thể được tạo nên từ hai ánh xạ không phân rã được trên hai tâp con thật sự của N có giao khác rỗng. Giả sử tập N \ S gồm m phần tử, 1 ≤ m ≤ n − 1.

k(cid:80)

Khi đó, ta xét dãy các tập hợp I1, I2, ..., Il, 1 ≤ l ≤ m với

j=1

ij = n

22

Để tạo một ánh xạ không phân rã được trên tập N ∪ {n + 1} vào chính

nó ta tiến hành theo các bước sau:

n C i2

n−i1...

C il

Phân phối n phần tử của tập N vào l tập hợp I1, I2, ..., Il, có C i1 n−(i1+...+il−1) cách. Tiếp theo ta tạo các ánh xạ từ tập I1 vào tập {n + 1} có 1i

1 cách, ánh

1 cách,..., ánh xạ từ tập Il vào tập Il−1 có iil

l−1

xạ từ tập I2 vào tập I1 có ii2 cách.

Tạo các ánh xạ không phân rã được từ tập con thật sự S của N gồm

n − m phần tử vào chính nó, có αn−m cách.

Xác định ảnh của phần tử (n + 1), có (n − m) cách. Do đó:

n−1 (cid:88)

1 ...iil

1ii2

n C i2

l−1

n−i1...C il

n−(i1+...+il−1)1i

m=1

ij=m

(i1,...,il):

l (cid:80) j=1 ij≥1

(cid:88) (n − m)C i1 an+1,2 =

n−1 (cid:88)

m=1

ij=m

(i1,...,il):

l (cid:80) j=1 ij≥1

(cid:88) ... . = n! αn−m (n − m − 1)! 1i1 i1! ii2 1 i2! iil l−1 il!

Vậy ta có điều phải chứng minh.

Mệnh đề 4.2. Gọi αn,k , với 1 ≤ k ≤ n là số ánh xạ có k thành phần không phân rã được từ tập N = {1, 2, ..., n} vào chính nó. Khi đó ta có:

n+1−k (cid:88)

nαjαn−j,k−1

j=1

C j αn,k = 1 k

1 ≤ k ≤ n.

với αn,0 = 0, α0,0 = 1, αn,1 = αn, n ≥ 1,

Hệ quả 4.3.1. Hệ số λn,k của dãy nhị thức Pn(t), n = 0, 1, 2, ... sinh bởi dãy αk, k = 1, 2, ... các ánh xạ không phân rã được từ tập {1, 2, ..., k} vào chính nó chính là số ánh xạ gồm k thành phần không phân rã được từ tập N = {1, 2, ..., n} vào chính nó, với λn,1 = αn.

23

n(cid:80)

Nhận xét 4.2. Số tất cả các ánh xạ không phân rã được từ tập N = {1, 2, ..., n} vào chính nó chính là giá trị của dãy nhị thức sinh bởi dãy các αn,k = nn.

ánh xạ không phân rã được {αk}k≥1 khi t = 1. Tức Pn(1) =

k=1

n(cid:80)

αn,k.

Do đó với α1 = α1,1 = 1, chúng ta có thể tìm αn = αn,1 theo cách sau. Trước hết tìm αn,k, k = 2, 3, ..., n, sau đó tìm αn = nn −

k=2

Dựa vào các định lí, mệnh đề và hệ quả trên ta có thể tính truy hồi cho số ánh xạ gồm k thành phần không phân rã được αn,k, k = 1, 2, ..., n từ tập N = {1, 2, ..., n} vào chính nó và cũng chính là hệ số của dãy nhị thức {Pn(t)}n≥0 của dãy {αk}k≥1 các ánh xạ khôn phân rã được từ tập {1, 2, ..., k} vào chính nó.

Mệnh đề 4.3. Nếu f là ánh xạ không phân rã từ tập [n] vào chính nó thì tập hợp các ảnh cuối của f thuộc một vòng xích duy nhất.

24

KẾT LUẬN

Trong luận văn này, chúng tôi đã tập trung nghiên cứu một số vấn đề

sau đây:

1) Chúng tôi đã giới thiệu lại các khái niệm về ánh xạ, đơn ánh, toàn ánh và song ánh. Luận văn cũng nêu lại quy tắc đếm cơ bản và nguyên lý bù trừ tổng quát, cũng như quy tắc song ánh để giải các bài toán tổ hợp. Đồng thời luận văn cũng giới thiệu lại khái niệm về xích.

2) Luận văn giới thiệu lại các khái niệm về Hoán vị, Chỉnh hợp, Tổ hợp, số Stirling loại một, số Stirling loại một không dấu, số Stirling loại hai và số Bell. Đồng thời luận văn nêu lại cách tính số các ánh xạ, đơn ánh, toàn ánh và song ánh.

3) Chúng tôi trình bày sơ lược lại các kết quả đã có về dãy nhị thức. 4) Điều đáng lưu ý trong luận văn này là chúng tôi đã đưa ra một số khái niệm mới như ánh xạ phân rã được, ánh xạ không phân rã được trên tập hữu hạn. Đặc biệt việc đưa ra cách chứng minh quy nạp để tìm số ánh xạ không phân rã được từ tập [n] vào chính nó chính là phần mới và là cơ bản nhất của luận văn này.

Kết quả luận văn là cơ sở trong việc tiếp tục nghiên cứu để tìm ra công

thức truy hồi cho số tất cả các đồ thị liên thông có n đỉnh.