ĐẠ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
ĐẠ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.
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.
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
P
n(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.Chương 1
KIẾN THỨC CHUẨN BỊ
1.1 Quy tắc cộng, quy tắc nhân
1.1.1 Quy tắc cộng
Nếu có
m
1 cách chọn đối tượnga
1,m
2 cách chọn đối tượnga
2, ...,m
n cách chọn đối tượnga
n, trong đó cách chọn đối tượnga
i(1 ≤ i ≤ n)
không phụ thuộc vào bất kì cách chọn đối tượnga
j nào(1 ≤ j ≤ n, i 6= j )
thì sẽ cón
P
k=1
m
k cách chọn đối tượnga
1, hoặca
2, ..., hoặca
n.
Để 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ợpA
k(1 ≤ k ≤ n)
với|A
k| = m
k và∀i, j (1 ≤ i, j ≤ n)A
i∩ A
j= ∅
, khii 6= j
. Khi đó số cách chọna
1, hoặca
2, ..., hoặca
n sẽ bằng số cách chọn các phần tửa ∈
n
S
k=1
A
k và|
n
S
k=1
A
k| =
n
P
k=1
|A
k|
.1.1.2 Quy tắc nhân
Cho
n
đối tượnga
1, a
2, ..., a
n. Nếu cóm
1 cách chọn đối tượnga
1 và ứng với mỗi cách chọna
1 ta cóm
2 cách chọn đối tượnga
2, sau đó với mỗi cách chọna
1, a
2 ta cóm
3 cách chọn đối tượnga
3, ... Cuối cùng với mỗi cách chọna
1, a
2, ..., a
n−1 ta cóm
n cách chọn đối tượnga
n.Vậy sẽ có
m
1.m
2...m
n−1.m
n cách chọn các đối tượnga
1, rồia
2,..., rồia
n.Chú ý 1. Để vận dụng có hiệu quả, ta chuyển quy tắc nhân sang dạng sau:
Giả sử có
n
tập hợpA
k(1 ≤ k ≤ n)
với|A
k| = m
k. Khi đó, Số cách chọn (S) bộ gồmn
phần tử(a
1, a
2, ..., a
n)
vớia
i∈ A
i(1 ≤ i ≤ n)
sẽ là:S = |A
1.A
2...A
n| = m
1.m
2...m
n=
n
Y
k=1
m
k1.2 Nguyên lý bù trừ
Định lý 1.1. [4] Cho
n≥2
tập hợp hữu hạnA
1, ..., A
n.
Khi đó ta có :|A
1∪ A
2∪ ... ∪ A
n| =
n
X
i=1
|A
i| −
X1≤i<k≤n
|A
i∩ A
k| +
X1≤i<j<k≤n
|A
i∩ A
j∩ A
k|
+... +
X1≤i1<i2<...<ik≤n
(−1)
k+1|A
i1∩ A
i2... ∩ A
ik|
+... + (−1)
n+1|A
1∩ A
2∩ ... ∩ A
n|. (∗) 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ênn
phần tử. GọiS
n là tập hợp tất cả các phép thế trên n phần tử. Nếuα, β ∈ S
n 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ậpN = {1, 2, ..., n}
vào chính nó, tứcαβ ∈ S
nĐịnh nghĩa 1.1. [3] Giả sử
x
1, ..., x
k là các phần tử đôi một khác nhau trong{1, 2, ..., n}
. Ta kí hiệu bởi(x
1, x
2, ..., x
k)
phép thế giữ nguyên các phần tử khácx
1, x
2, ..., x
k và tác động trênx
1, ..., x
k như sau:x
17→ x
2, x
27→ x
3, ..., x
k−17→ x
k, x
k7→ x
1.
Nó được gọi là một xích với độ dài
k
trên tập nền{x
1, x
2, ..., x
k}
. Với(x
1, ..., x
k)
được gọi là một xích của phép thếα ∈ S
n nếuα
tác động giống như(x
1, ..., x
k)
trên các phần tửx
1, x
2, ..., x
k (α
có thể tác động không tầm thường trên các phần tửx
1, ..., x
k)
.Định lý 1.3. [3] Mọi phép thế
α ∈ S
n đề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
S
n 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.Chương 2
CÁC SỐ TỔ HỢP CƠ BẢN
2.1 Cấu hình tổ hợp
2.1.1 Chỉnh hợp lặp
Định nghĩa 2.1. Cho tập hữu hạn
X
gồmn
phần tử. Mỗi dãy có độ dàik
các phần tử của tậpX
, 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ậpk
củan
phần tử thuộc tậpX
.Đị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àA
kn, thìA
kn= n
k2.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àP
n thìP
n= 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ộck
loại, mà các phần tử loạii (1 ≤ i ≤ k)
xuất hiệnn
i lần được kí hiệu làP (n
1, n
2, ..., n
k)
và được tính bằng công thức:
P (n
1, n
2, ..., n
k) = n!
n
1!n
2!...n
k! , n = n
1+ n
2+ ... + n
k.
2.1.4 Tổ hợp lặp
Định nghĩa 2.4. Cho tập hợp
A = {a
1, a
2, ..., a
n}
. Một tổ hợp lặp chậpm
(m
không nhất thiết phải nhỏ hơnn
) củan
phần tử thuộcA
là một bộ gồmm
phần tử, mà mỗi phần tử này là một trong những phần tử củaA
.Định lý 2.4. Ta sử dụng
C
nm để kí hiệu số tổ hợp lặp chậpm
củan
phần tử. Khi đó:C
nm= C
n+m−1m2.1.5 Phân hoạch thứ tự tổ hợp
Định nghĩa 2.5. Giả sử
X
là một tập hợp gồmn
phần tử. Khi đó ta có phân hoạch của tậpX
thànhk
khối là một họ tùy ýπ = {B
1, B
2, ..., B
k}
màB
1∪ B
2∪ ...B
k= X
,B
i∩ B
j= ∅
với mọi1 ≤ i < j ≤ k
vàB
i6= ∅
với mọi1 ≤ i ≤ k
. Các tập conB
1, ..., B
k đượ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ồmn
phần tử khác nhau,r ≤ n
vàS ⊂ X
cór
phần tử. Một phân hoạch{S
1, S
2, ..., S
k}
có thứ tựS
gọi là một phân hoạch thứ tự tổ hợp chậpr
củaX
. Nếur = n
thì gọi là phân hoạch thứ tự củaX
.Cho các số nguyên dương
n
1, n
2, ..., n
k thỏa:n
1+ n
2+ ... + n
k= r
. Số các phân hoạch thứ tự tổ hợp chậpr
củaX
dạng{S
1, S
2, ..., S
k}
có|S
1| = n
1, |S
2| = n
2, ..., |S
k| = n
k được kí hiệu làC (n; n
1, n
2, ..., n
k)
. Định lý 2.5. [2]C (n; n
1, n
2, ..., n
k) = n!
n
1!n
2!...n
k!(n − r)! = P (n
1, n
2, ..., n
k, n − r).
Định lý 2.6. [2] Số phân hoạch không thứ tự của tập
X
gồm:p
1 tập cón
1 phần tử,p
2 tập cón
2 phần tử, ...,p
k tập cón
k phần tử được tính theo công thức:C (n; n
1, ..., n
1, n
2, ..., n
2, ..., n
k, ..., n
k) p
1!p
2!...p
k!
= n!
p
1!(n
1!)
p1p
2!(n
2!)
p2...p
k!(n
k!)
pk.
(trong
C (n; n
1, ..., n
1, n
2, ..., n
2, ..., n
k, ..., n
k)
sốn
1 lặp lạip
1 lần, sốn
2 lặp lạip
2 lần, ..., sốn
k lặp lạip
k lần)2.2 Các số Stirling loại một, số Stirling loại hai và số Bell
2.2.1 Số Stirling loại một
Đị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àc
n,k.
Số
s
n,k= (−1)
n−kc
n,k.
được gọi là số Stirling loại một.Từ định nghĩa ta rút ra được
c
n,k= 0, ∀k > n
.Định lý 2.7. [8] Với
n
là số nguyên không âm cố định, ta có:x
(n)=
n
X
k=0
c
n,kx
k(2.1)
vớix
(n)= x(x + 1)...(x + n − 1), x
(0):= 1
.Mệnh đề 2.1. Ta có:
n
X
k=0
s
n,kx
k= x
(n).
Thay
x = 1
u
vào Mệnh đề 2.1 và Định lí 2.7 ta được mệnh đề sau.Mệnh đề 2.2. [6] Ta có:
a)
X1≤k≤n
s
n,ku
n−k= (1 − u)(1 − 2u)...(1 − (n − 1)u).
b)
X1≤k≤n
c
n,ku
n−k= (1 + u)(1 + 2u)...(1 + (n − 1)u).
Thay
n
bằngn + 1
vàk
bằngn + 1 − k
vào Mệnh đề 2.2 b ta được:X
1≤n+1−k≤n+1
c
n+1,n+1−ku
k= (1 + u)(1 + 2u)...(1 + nu),
hayX
0≤k≤n
c
n+1,n+1−ku
k=
X0≤k≤n
X
0≤i1≤i2≤...≤ik≤n
i
1i
2...i
ku
k.
Đồng nhất hệ số củau
k hai vế ta thu được hệ quả sau.Hệ quả 2.2.1. [6] Với
k = 1, 2, ..., n
ta có:c
n+1,n+1−k=
X0≤i1≤i2≤...≤ik≤n
i
1i
2...i
k.
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
s
n,k với một số giá trị đầu tiên được nêu trong Bảng 2.1.2.2.2 Số Stirling loại hai và số Bell
Định nghĩa 2.8 (7). Số tất cả các phân hoạch của tập hợp
A
gồmn
phần tử thànhk
khối gọi là số Stirling loại hai, kí hiệu làS
n,k.
Ta qui ước
S
0,0= 1, S
0,k= 0
nếuk > 0
vàS
n,0= 0
nếun > 0
.Từ định nghĩa này ta dễ dàng nhận thấy
S
n,k= 0
nếuk > n
vàS
n,1= S
n,n= 1
.Định lý 2.8. [9] Với
n, k
là các số nguyên dương vàk ≤ n
ta có:S
n+1,k= kS
n,k+ S
n,k−1.
Chú ý 3. Từ
S
n,1= S
n,n= 1
và từ công thức truy hồi củaS
n,k ta thấyS
n,k có những tính chất giống như đối với công thức tổ hợpC
nk nên ta cũng xây dựng được tam giác để tìm giá trịS
n,k như sau:S
1,1S
2,1S
2,2S
3,1S
3,2S
3,3S
4,1S
4,2S
4,3S
4,4S
5,1S
5,2S
5,3S
5,4S
5,5S
6,1S
6,2S
6,3S
6,4S
6,5S
6,6...
Mệnh đề 2.3. Với
n, k
là các số nguyên dương vàk ≤ n
ta có:S
n,k= 1 k!
k
X
j=1
(−1)
k−jC
kj.j
n.
Đị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ượngn
được gọi là số Bell thứn
. Kí hiệuB
n.Từ định nghĩa 2.9 và định nghĩa 2.10, ta có:
B
n=
n
X
k=0
S
n,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ợpM = {1, 2, ..., m}
. Khi đó số tất cả các ánh xạf : N −→ M
làm
n.Mệnh đề 2.5. [9] Cho tập hợp
N = {1, 2, ..., n}
và tập hợpM = {1, 2, ..., m}
, vớin ≤ 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ợpn = 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 ánhf : 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ậpN
làC
nk.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ớin ≤ m
làn!C
mn, vớiC
mn là số tất cả các tập conn
phần tử của tậpM
.Mệnh đề 2.8. [9] Cho tập hợp
N = {1, 2, ..., n}
và tập hợpM = {1, 2, ..., m}
, vớin ≥ m
.Khi đó số tất cả các toàn ánh
f : N −→ M
làS
n,m.m!
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
P
n(t)
n≥0 vớideg(P
n(t))≤ n
, n = 0, 1, 2,... được gọi là dãy nhị thức nếu:i)P
0(t) = 1, t ∈
R, ii)P
n(t + u) =
n
X
k=0
C
nkP
k(u)P
n−k(t), n = 1, 2, ..., t, u ∈
R.
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
{P
n(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{a
k}
k≥1 sao cho:i)
P
0(t) = 1,
ii)P
n(t) = n!
Pnk=1
(
P(i1,...,ik):
k
P j=1 ij≥1
ij=n ai1
i1! ai2
i2!
...
aiikk!
)
tk!k, n = 1, 2, 3, ...
Định nghĩa 3.2. [1]Cho trước dãy số thực
{a
k}
k≥1. Giả sử rằng{P
n(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{P
n(t)}
n≥0 là dãy nhị thức sinh bởi dãy{a
k}
k≥1 đã cho.Nếu đặt
λ
n,k= n!
k!
X
(i1,...,ik):
k
P j=1 ij≥1
ij=n
a
i1i
1!
a
i2i
2! ... a
iki
k!
thìP
n(t) =
n
P
k=1
λ
n,kt
k.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
{a
k}
k≥1Mệnh đề 3.1. Với
λ
n,0= 0, λ
n,1= a
n∀n ≥ 0, λ
0,0= 1,
ta có:λ
n,k= 1 k
n+1−k
X
j=1
a
jC
njλ
n−j,k−1, n = 1, 2, ..., k = 1, 2, ...
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ớiR > 0
nào đó như sau:f (x) =
∞
X
k=1
a
kx
kk! , f (0) = 0
Khi đó, dãy số
{a
k}
k≥1 vớia
k= 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ử
{P
n(t)}
n≥0 là dãy nhị thức sinh bởi hàm sốf
. Khi đó:∞
X
k=1
{P
n(t)} x
nn! = e
tf(x).
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
c
n,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ànhk
vòng xích độc lập trên tậpn
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ậpn
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ậpN = {1, 2, ..., n}
vào chính nó là:
α
n= (n − 1)!
n
X
k=0
n
n−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ậpN = {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ỗngK
,|K | = k, 1 ≤ k ≤ n
sao chof
−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 .Định nghĩa 4.3. Một ánh xạ
f
từ tậpN = {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ạchN = N
1∪ N
2∪ ... ∪ N
k, N
i6= ∅, N
i∩ N
j=
∅, i, j = 1, k i 6= j, k ≥ 2
sao cho tất cả các hạn chếf
i của f trên mỗi tập conN
i Như vậy ta có thể phân tích một ánh xạ f từ tậpN = {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
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
k
0∈ N
sao chof (k
0) = k
0.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ậpN = {1, 2, ..., n}
vào chính nó, thì ta có:α
n=
n
X
k=1
(k − 1)!
X(i1,...,il):
l
P j=1 ij≥1
ij=n−k
n!
k!
k
i1i
1!
i
i12i
2! ... i
il−1li
l! (∗)
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ử trongn
phần tử ta có số cách chọn làC
nk. Xét dãy các tập hợpI
1, I
2, ..., I
l ,(1 ≤ l ≤ n − k)
,|I
j| = i
j sao chol
P
j=1
i
j= n − k
. Rồi sau đó ta phân phốin − k
phần tử còn lại vàol
tập hợpI
1, I
2, ..., I
l.Ta có số cách phân phối
n − k
phần tử vào tậpI
1 làC
n−ki1 , số cách phân phốin − k − i
1 phần tử vào tậpI
2 làC
n−k−ii21,..., số cách phân phối
n − k − i
1− ... − i
l−1 phần tử vào tậpI
l làC
n−k−iil1−...−il−1.
Nên số cách phân phối
n − k
phần tử vàol
tập hợpI
1, I
2, ..., I
l làC
n−ki1C
n−k−ii2 1...C
n−k−iil 1−...−il−1.
Tiếp theo ta tạo ánh xạ từ tập
I
1 vào tậpK
cók
i1 cách, ánh xạ từ tậpI
2 vào tậpI
1 cói
1i2 cách,..., ánh xạ từ tậpI
l vào tậpI
l−1 cói
il−1l cách.Vậy ta có 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ó là:α
n=
n
X
k=1
C
nk(k − 1)!
X(i1,...,il):
l
P j=1 ij≥1
ij=n−k
C
n−ki1C
n−k−ii21
...C
n−k−iil1−...−il−1
.
Hay
α
n=
n
X
k=1
(k − 1)!
X(i1,...,il):
l
P j=1 ij≥1
ij=n−k
n!
k!
k
i1i
1!
i
i12i
2! ... i
il−1li
l! .
Đị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ậpN = {1, 2, ..., n}
vào chính nó khi đó ta có:α
n= (n − 1)!
n
X
k=0
n
n−k(n − k)! (1)
Chứng minh. Để chứng minh (1) trước hết ta cần chứng minh rằng X
(i1,...,il):
l
P j=1 ij≥1
ij=n−k
n!
k!
k
i1i
1!
i
i12i
2! ... i
il−1li
l! = C
n−1k−1n
n−k,
hay:
X
(i1,...,il):
l
P j=1 ij≥1
ij=n−k
(n − k)! k
i1i
1!
i
i12i
2! ... i
il−1li
l! = kn
n−k−1(2)
Ta chứng minh (2) bằng qui nạp theo n.
Ta có:
X
(i1,...,il):
l
P j=1 ij≥1
ij=n−k
(n − k)! k
i1i
1!
i
i12i
2! ... i
il−1li
l!
=
n−k
X
h=1
X
(i1,...,il):
l
P j=1 ij≥1 i1=h
ij=n−k
(n − k)! k
hh!
h
i2i
2! ... i
il−1li
l!
=
n−k
X
h=1
k
h(n − k)!
h!(n − k − h)!
X
(i1,...,il):
l
P j=2 ij≥1
ij=n−k−h
(n − k − h)! h
i2i
2!
i
i23i
3! ... i
il−1li
l! .
Mà:
X
(i1,...,il):
Pl
j=2 ij≥1
ij=n−k−h
(n − k − h)! h
i2i
2!
i
i23i
3! ... i
il−1li
l! = h(n − k)
n−k−h−1.
Do đó:
X
(i1,...,il):
l
P j=1 ij≥1
ij=n−k
(n − k)! k
i1i
1!
i
i12i
2! ... i
il−1li
l!
=
n−k
X
h=1
k
h(n − k)!
h!(n − k − h)! h(n − k)
n−k−h−1= k
n−k
X
h=1
(n − k − 1)!
(h − 1)![n − k − 1 − (h − 1)]! k
h−1(n − k)
n−k−h= k
n−k−1
X
h=0
(n − k − 1)!
h![n − k − 1 − h]! k
h(n − k)
n−k−h−1= k
n−k−1
X
h=0
C
n−k−1hk
h(n − k)
n−k−h−1= k[k + (n − k)]
n−k−1= k.n
n−k−1.
Nên:
X
(i1,...,il):
l
P j=1 ij≥1
ij=n−k
n!
k!
k
i1i
1!
i
i12i
2! ... i
il−1li
l! = C
n−1k−1n
n−k.
Thay kết quả này vào đẳng thức (*) ta được:
α
n=
n
X
k=1
(k − 1)!C
n−1k−1n
n−k.
α
n= (n − 1)!
n
X
k=0
n
n−k(n − k)! .
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ậpN = {1, 2, ..., n}
vào chính nó. Khi đó ta có:α
1= 1,
α
n+1= nα
n+ (n + 1)!
X(i1,...,ik):
k
P j=1 ij≥1
ij=n
1
i1i
1!
i
i12i
2! ... i
ik−1ki
k!
+n!
n−1
X
m=1
α
n−m(n − m − 1)!
X
(i1,...,il):
l
P j=1 ij≥1
ij=m
1
i1i
1!
i
i12i
2! ... i
il−1li
l!
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ậpN
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) 6= ∅
.Ta xét dãy liên tiếp các tập hợp:
f
−1(n + 1) ∩ N = I
1, f
−1(I
1) ∩ N = I
2,
...
f
−1(I
k−1) ∩ N = I
k,
với
|I
j| = i
j, j = 1, k, 1 ≤ k ≤ n,
và dễ thấy rằng dãy trên dừng tạik
khi và chỉ khiI
k+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ủaN
sao cho hạn chế củaf
trênS
là một ánh xạ không phân rã được từ tậpS
vào chính nó.Gọi số các khả năng của
f
thuộc loại này làa
n+1,1. Khi đó dãy các tậpI
1, I
2, ..., I
k với1 ≤ k ≤ n
thoảk
P
j=1
i
j= n
.Để 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ốin
phần tử của tậpN
vàok
tập hợpI
1, I
2, ..., I
k, cóC
ni1C
n−ii2 1...C
n−(iik1+...+ik−1) cách.
Tiếp theo ta tạo các ánh xạ từ tập
I
1 vào tập{n + 1}
có1
i1 cách, ánh xạ từ tậpI
2 vào tậpI
1 cói
i12 cách,..., ánh xạ từ tậpI
k vào tậpI
k−1 cói
ik−1k cách.Cuối cùng là xác định ảnh của phần tử
(n + 1)
có(n + 1)
cách.Do đó:
a
n+1,1= (n + 1)
X(i1,...,ik):
k
P j=1 ij≥1
ij=n
C
ni1C
n−ii2 1...C
n−(iik1+...+ik−1)
1
i1i
i12...i
ik−1k= (n + 1)!
X(i1,...,ik):
k
P j=1 ij≥1
ij=n
1
i1i
1!
i
i12i
2! ... i
ik−1ki
k! .
b) Tồn tại một tập con thật sự
S
củaN
sao cho hạn chế củaf
trênS
là một ánh xạ không phân rã được từ tậpS
vào chính nó.Gọi số các khả năng của
f
thuộc loại này làa
n+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ủaN
có giao khác rỗng. Giả sử tậpN \ S
gồmm
phần tử,1 ≤ m ≤ n − 1
.Khi đó, ta xét dãy các tập hợp
I
1, I
2, ..., I
l, 1 ≤ l ≤ m
vớik
P
j=1
i
j= n
Để 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:Phân phối
n
phần tử của tậpN
vàol
tập hợpI
1, I
2, ..., I
l, cóC
ni1C
n−ii2 1...
C
n−(iil1+...+il−1) cách.
Tiếp theo ta tạo các ánh xạ từ tập
I
1 vào tập{n + 1}
có1
i1 cách, ánh xạ từ tậpI
2 vào tậpI
1 cói
i12 cách,..., ánh xạ từ tậpI
l vào tậpI
l−1 cói
il−1l cách.Tạo các ánh xạ không phân rã được từ tập con thật sự
S
củaN
gồmn − 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 đó:
a
n+1,2=
n−1
X
m=1
X
(i1,...,il):
l
P j=1 ij≥1
ij=m
(n − m)C
ni1C
n−ii2 1...C
n−(iil1+...+il−1)
1
i1i
i12...i
il−1l= n!
n−1
X
m=1
α
n−m(n − m − 1)!
X
(i1,...,il):
l
P j=1 ij≥1
ij=m
1
i1i
1!
i
i12i
2! ... i
il−1li
l! .
Vậy ta có điều phải chứng minh.
Mệnh đề 4.2. Gọi
α
n,k , với1 ≤ k ≤ n
là số ánh xạ cók
thành phần không phân rã được từ tậpN = {1, 2, ..., n}
vào chính nó. Khi đó ta có:α
n,k= 1 k
n+1−k
X
j=1
C
njα
jα
n−j,k−1với
α
n,0= 0, α
0,0= 1, α
n,1= α
n, n ≥ 1, 1 ≤ k ≤ n
.Hệ quả 4.3.1. Hệ số
λ
n,k của dãy nhị thứcP
n(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ồmk
thành phần không phân rã được từ tậpN = {1, 2, ..., n}
vào chính nó, vớiλ
n,1= α
n.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 ánh xạ không phân rã được{α
k}
k≥1 khit = 1
. TứcP
n(1) =
n
P
k=1
α
n,k= n
n. 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= n
n−
n
P
k=2
α
n,k.
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ậpN = {1, 2, ..., n}
vào chính nó và cũng chính là hệ số của dãy nhị thức{P
n(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ủaf
thuộc một vòng xích duy nhất.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.