BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG…………………….


Luận văn thạc sỹ

Mối liên hệ giữa các số phân hoạch, số tất
cả các phân hoạch chẵn , số tất cả các
phân hoạch lẻ

1
Mục lục
mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1 Kiến thức chuẩn bị 5
1.1 Các quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Một số bài toán đếm và kết quả tổ hợp cơ bản . . . . . . . . . . 10
1.2.1 Chỉnh hợp - hoán vị - tổ hợp . . . . . . . . . . . . . . . . 10

Hướng nghiên cứu của luận văn là giới thiệu về phương pháp dùng hàm
sinh, hàm sinh mũ để giải một số bài toán tổ hợp và giới thiệu về một công
thức sàng lọc số phần tử của một tập hữu hạn theo hướng các phần tử này
có mặt trong đúng chẵn (lẻ) tập con của tập đã cho mà ta gọi là công th ức
sàng. Từ tính hữu dụng của kỹ thuật hàm sinh và ý tưởng về việc sàng lọc
theo hướng chẵn (lẻ) của công thức sàng, trong luận văn chúng tôi đưa ra công
thức tính cho số phân hoạch chẵn (lẻ) của một tập hợp hữu hạn cho trước mà
nó sẽ được gọi là một biến thể của công thức sàng. Đặc biệt, mối liên hệ
giữa số tất cả các phân hoạch, số tất cả các phân hoạch chẵn, số tất
cả các phân hoạch lẻ (thành các tập con không rỗng) của một tập hữu hạn
là vấn đề mà chúng tôi rất quan tâm.
Luận văn gồm có ba chương, phần kết luận và tài liệu tham khảo.
Chương 1. Kiến thức chuẩn bị
Trong chương này, chúng tôi trình bày về một số quy tắc đếm, bài toán đếm
và một vài kết quả cơ bản về tổ hợp.
Chương 2. Hàm sinh và công thức sàng
Chương này gồm ba phần.
- Hàm sinh thường: Giới thiệu về hàm sinh thường và áp dụng vào giải một
4
vài bài toán tổ hợp điển hình.
- Hàm sinh mũ: Giới thiệu về hàm sinh mũ và áp dụng vào giải một vài bài
toán tổ hợp điển hình.
- Công thức sàng: Dùng công thức ngược cho các đồng nhất thức tổ hợp, kết
hợp với nguyên lý bù trù trừ để xây dựng công thức sàng.
Chương 3. Biến thể củ a công thức sàng
Trong chương này, chúng tôi đưa ra cách tính số tất cả các cách phân hoạch
một tập hợp hữu hạn thành các tập con không rỗng sao cho mỗi tập con có
một số chẵn (một số lẻ) phần tử bằng cách áp dụng kỹ thuật hàm sinh mũ kết
hợp với các phép biến đổi giải tích. Hơn nữa, chúng tôi cũng sẽ xác định các số
này bằng con đường sơ cấp hơn qua các công thức tính truy hồi. Mối liên hệ

, a
2
, . . . , a
m
}, |Y | = m.
Một ánh xạ ϕ từ X vào Y là một phép tương ứng, ký hiệu
ϕ =


1 2 ··· n
a
i
1
a
i
2
··· a
i
n


cho ứng mỗi phần tử j ∈ X với duy nhất một phần tử a
i
j
∈ Y, j = 1, n.
- Ánh xạ ϕ được gọi là một toàn ánh nếu mỗi a ∈ Y , tồn tại ít nhất một i ∈ X
sao cho a = ϕ(i).
Nếu tồn tại một toàn ánh từ X đến Y thì |X| ≥ |Y |.
- Ánh xạ ϕ được gọi là một đơn ánh nếu với mọi i, j ∈ X nếu i = j thì
ϕ(i) = ϕ(j).

2
.
Quy tắc cộng ([3], tr 27).
Nếu có m
1
cách chọn đối tượng x
1
, m
2
cách chọn đối tượng x
2
, . . . , m
n
cách chọn đối tượng x
n
và nếu cách chọn đối tượng x
i
không trùng với bất
kỳ cách chọn đối tượng x
j
nào (i = j, i, j = 1, n) thì có m
1
+ m
2
+ ···+ m
n
cách
chọn một trong các đối tượng đã cho.
Ta chứng minh quy tắc cộng trên cơ sở của lý thuyết tập hợp như sau.
Định lý 1.1. Cho n tập hợp hữu hạn X



n

i=1
X
i



=
n

i=1
|X
i
|. (1.1)
7
Chứng minh. Ta chứng minh quy nạp theo n với n ≥ 2.
Nếu n = 2 thì |X
1
∪ X
2
| = |X
1
| + |X
2
| −|X
1
∩ X

|. (1.2)
Thật vậy ta có
X
1
∪ X
2
∪ ··· ∪X
k
∪ X
k+1
= (X
1
∪ X
2
∪ ··· ∪X
k
) ∪X
k+1
.
Vì X
i
∩ X
j
= ∅, i = j; i, j = 1, 2, . . . , k, k + 1 nên
(X
1
∪ X
2
∪ ··· ∪X
k

k+1
|
= |X
1
∪ X
2
∪ ··· ∪X
k
| ∪|X
k+1
|
=
k

i=1
|X
i
| + |X
k+1
|.
=
k+1

i=1
|X
i
|.
Suy ra (1.2) được chứng minh.
Theo nguyên lý quy nạp toán họ c, quy tắc cộng là đúng với mọi n ∈ N, n ≥ 2.
Ví dụ 1.2. Từ các chữ số 1, 2, 3 có thể lập được bao nhiêu số khác nhau có

3
cách chọn đối tượng
x
3
,. . . , cuối cùng, với mỗi cách chọn x
1
, x
2
, . . . , x
n−1
như thế có m
n
cách chọn
đối tượng x
n
, thì có m
1
m
2
. . . m
n
cách chọn dãy các đối tượng "x
1
rồi x
2
rồi
x
3
rồi x
n

2
× ··· ×X
n
| =
n

i=1
m
i
. (1.3)
Chứng minh. Ta chứng minh (1.3) bằng phương pháp quy nạp theo n, n ≥ 2
như sau.
Với n = 2, ta có |X
1
| = m
1
, |X
2
| = m
2
. Giả sử X
1
= {a
1
, a
2
, . . . , a
m
1
} và

}.
Ta viết X
1
× X
2
dưới dạng bảng sau
(a
1
, b
1
) (a
1
, b
2
) ······ (a
1
, b
m
2
)
(a
2
, b
1
) (a
2
, b
2
) ······ (a
2

, b
m
2
)
Đặt E
i
= {(a
i
, b
1
), (a
i
, b
2
), . . . , (a
i
, b
m
2
) : 1 ≤ i ≤ m
1
} =⇒ |E
i
| = m
2
.
Ta có X
1
×X
2

i
| = m
1
m
2
.
Vậy công thức (1.3) đúng cho trường hợp n = 2.
Giả sử (1.3) đúng với trường hợp n = k, (k ≥ 2), tức là |X
1
×X
2
×···×X
k
| =
m
1
.m
2
. . . m
k
. Ta chứng minh (1.3) đúng cho trường hợp n = k + 1, có nghĩa là
|X
1
× X
2
× ··· ×X
k
× X
k+1
| = m

k
). Rõ ràng giữa tập hợp các bộ có
dạng (a
1
, a
2
, . . . , a
k
, a
k+1
) và tập hợp các cặp có dạng (α, a
k+1
) có tương ứng
1 − 1. Vậy có bao nhiêu bộ (a
1
, a
2
, . . . , a
k
, a
k+1
) thì có bấy nhiêu cặp (α, a
k+1
).
Nếu ta ký hiệu tập hợp tất cả các α là X, thì ta có thể nói rằng tập hợp
X
1
× X
2
× ··· × X

. Áp dụng giả
thiết quy nạp ta có
|X ×X
k+1
| = |X||X
k+1
| = |X
1
× X
2
× ··· ×X
k
| ×|X
k+1
| = m
1
m
2
. . . m
k
m
k+1
.
Vậy |X
1
× X
2
× ··· ×X
k
× X

1
, a
2
có 3
cách chọn a
3
. Theo quy tắc nhân ta có 4.4.3 = 48 số cần lập.
1.2 Một số bài toán đếm và kết quả tổ hợp cơ
bản
1.2.1 Chỉnh hợp - hoán vị - tổ hợp
Định nghĩa 1.1. Cho tập hữu hạn X = {a
1
, a
2
, a
3
, , a
n
} và một số tự nhiên
k  n. Khi đó
(i) Bộ k phần tử (a
i1
, a
i2
, , a
ik
), a
ij
∈ X được gọi là bộ có thứ tự nếu
đổi vị trí các phần tử ta được bộ một bộ mới. Ngược lại, b ộ k phần tử

∈ X
được gọi là bộ có lặp.
Định nghĩa 1.2. Cho tập hợp X gồm m phần tử và số nguyên dương n với
1  n  m.
Một chỉnh hợp chập n của m phần tử đã cho là một bộ có thứ tự gồm n
phần tử khác nhau được chọn từ m phần tử của X.
Theo định nghĩa, ta thấy rằng số các chỉnh hợp chập n của X chính là số
các cách chọn ra n phần tử từ X theo cách chọn có thứ tự và không lặp. Số
này được ký hiệu A
n
m
hoặc (m)
n
và được tính như sau: Ta có m cách chọn phần
tử thứ nhất. Vì chọn không lặp nên ta có m −1 cách chọn phần tử thứ hai. Tiếp
tục lý luận đó ta có m −n + 1 cách chọn phần tử thứ n . Theo quy tắc nhân, số
các cách chọn là m(m −1) (m − n + 1).
11
Vậy ta có
A
n
m
= (m)
n
= m(m −1) (m −n + 1) =
m!
(m −n)!
(1.4)
Định nghĩa 1.3. Một chỉnh hợp lặp chập n của m phần tử đã cho là một bộ
có thứ tự gồm n phần tử được chọn từ m phần tử đã cho, trong đó mỗi phần


.
Ta có nhận xét rằng ứng với mỗi tổ hợp chập n của m phần tử, có thể
thành lập được n! chỉnh hợp chập n của m phần tử. Suy ra
C
n
m
=
1
n!
A
n
m
=
m!
n!(m −n)!
(1.5)
Nhận xét. Cho tập hữu hạn X có |X| = n. Khi đó số tập con có k phần tử
(0  k  n) của X sẽ là C
k
n
.
12
Định nghĩa 1.6. Một tổ hợp lặp chập n của m phần tử cho trước là một bộ
không có thứ tự gồm n phần tử lấy từ m phần tử đã cho, mỗi phần tử có thể
có mặt nhiều lần.
Từ định nghĩa ta có kết quả sau đây.
Mệnh đề 1.3. Số tất cả các tổ hợp lặp chập n của m phần tử cho trước là
C
n

m
. Khi đó mỗi tổ hợp lặp
[a
i1
, , a
ik+1
] , a
ij
∈ X, j = 1, k + 1 có thể viết duy nhất dưới dạng bộ n- thứ
tự (a
i1
, , a
ik+1
) trong đó a
ij
 a
ih
khi i  h (tức là a
i1
 a
i2
 ···  a
ik+1
)
Ngược lại, với bộ n thứ tự như trên, ta xác định duy nhất một tổ hợp lặp
chập n của m phần tử đã cho. Nói cách khác ta đã xác định được một tương
ứng 1-1 giữa tập hợp gồm tất cả các tổ hợp lặp chập n của m phần tử với tập
hợp gồm tất cả các bộ (k + 1)-thứ tự như trên, tức là N(m, k + 1) chính là số
tất cả bộ (k + 1)-thứ tự (a
i


C
k+1
m+k+1−j
− C
k+1
m+k−j

= C
k+1
m+k
(1.6)
Theo nguyên lý quy nạp ta có điều cần chứng minh.
13
1.2.2 Phân hoạch của tập hợp. Số Stirling loại hai và số
Bell
Định nghĩa 1.7. 1) Một phân hoạch của một tập hữu hạn X thành k phần
là một họ các tập con khác rỗng X
1
, X
2
, . . . , X
k
của X thoả các tính chất sau
i) Hợp tất cả các tập hợp X
i
, i = 1, k tạo thành tập hợp X, tức là
X
1
∪ X

ii) Số Bell chính là số tất cả các phân hoạch của tập X có n phần tử.
Ví dụ 1.4. Phân hoạch của tập hợp {a, b, c, d} thành 3 phần có thể được biểu
thị như tập hợp:
{{a}, {b}, {c, d}}; {{a}, {b, d}, {c}}; {{a, d}, {b}, {c}}
{{a}, {b, c}, {d}}; {{a, c}, {b}, {d}}; {{a, b}, {c}, {d}}
hoặc viết đơn giản hơn
a|b|cd a|bd|c ad|b|c
a|bc|d ac|b|d ab|c|d
Như vậy S
4,3
= 6.
Ta cũng có S
4,0
= 0; S
4,0
= 0; S
4,1
= 1; S
4,2
= 7; S
4,4
= 1. Do đó B
4
= S
4,0
+ S
4,1
+
S
4,2

1
, x
2
, . . . , x
n−1
thành k −1 phần và có S
n−1,k−1
cách làm như vậy. Nếu {x
n
} không là một khối
thì x
n
phải được chứa trong một khối với ít nhất một phần tử khác của tập
hợp. Có S
n−1,k
cách phân hoạch {x
1
, x
2
, . . . , x
n−1
} thành k khối và x
n
có thể
nằm trong bất cứ một trong các khối này. Do đó có kS
n−1,k
cách mà trong đó
tập hợp ban đầu có thể phân hoạch thành k khối mà không có {x
n
} là một

1
S
2,1
S
2,2
1 1
S
3,1
S
3,2
S
3,3
1 3 1
S
4,1
S
4,2
S
4,3
S
4,4
1 7 6 1
S
5,1
S
5,2
S
5,3
S
5,4


(∗)
Chúng ta có thể rút gọn (∗) bằng cách khử hàng đầu tiên và viết f như một
dãy
f(1)f(2)f(3) ···f(n)
hay m
1
m
2
m
3
. . . m
n
, trong đó f(i) = m
i
∈ M.
Do đó, số các ánh xạ cần tính bằng số các dãy. Theo quy tắc nhân số các
dãy là
m.m.m . . . m
  
n
= m
n
.
Vậy ta có
Số tất cả các hàm f : N → M với |N| = n và |M | = m bằng |M|
|N|
= m
n
.

n,m
nên theo quy tắc nhân số toàn ánh
f : N −→ M bằng
m!S
n,m
.
Bây giờ ta có thể chứng minh một kết quả tổ hợp quan trọng sau đây.
17
Mệnh đề 1.5. ([4], tr 38).
m
n
=
n

k=1
S
n,k
(m)
k
.
Chứng minh. Giả sử N và M là các tập hợp với |N | = n, |M| = m. Chúng ta
hãy đếm tập hợp các ánh xạ f : N −→ M theo hai cách. Đầu tiên là những dãy
như trong 1.2.3 ta đượ c kết quả là m
n
. Thứ hai ta phân loại các ánh xạ theo
lực lượng ảnh của chúng. Số các ánh xạ có ảnh f (N) = K ⊂ M là số những
toàn ánh f : N −→ K, theo trong 1.2.5 bằng k!S
n,k
với |K| = k. Do đó số các
ánh xạ f : N −→ M với ảnh có lực lượng k bằng tích các k-tập hợp con K

n,k
=
n!
k!

(i
1
,i
2
, ,i
k
):
k
j=1
i
j
=n
i
j
≥1

1
i
1
!
·
1
i
2
!

1
n
,
Với mỗi cách chọn i
1
phần tử thì có C
i
2
n−i
1
cách chọn i
2
phần tử;
Với mỗi cách chọn i
1
phần tử và i
2
phần tử thì có C
i
3
n−i
1
−i
2
cách chọn i
3
phần
tử;

Với mỗi cách chọn i

k!
· C
i
1
n
C
i
2
n−i
1
···C
n−i
1
−i
2
−···−i
k−1
=
1
k!
·
n!
i
1
!i
2
! ···i
k
!
=

i
1
!
·
1
i
2
!
···
1
i
k
!

=
n!
k!

(i
1
,i
2
, ,i
k
):
k
j=1
i
j
=n

k−j
C
j
k
.j
n
. Công thức này sẽ được chứng minh trong chương sau.
Mệnh đề sau đây cho ta công thức tính truy hồi cho số Bell.
Mệnh đề 1.7. ([6], tr 92).
B
n+1
=
n

k=0
C
k
n
B
k
, (B
0
= S
0,0
= 1) .
Chứng minh.
Xét hàm sốL : R [x] → R
(x)
k
→ L(x)

k=1
S
n,k
(x)
k
= 0 hay x
n
=
n

k=1
S
n,k
(x)
k
.
Suy ra L(x
n
) = L

n

k=1
S
n,k
(x)
k

=
n

n
, ta được L(x + 1)
n
= Lxx
n
= Lx
n+1
Trong đó L(x + 1)
n
= L
n

k=0
C
k
n
x
k
=
n

k=0
C
k
n
Lx
k
=
n


e

k≥0
k
n
n!
( Công thức Dobinski ).
Công thức này sẽ được chứng minh ở chương 2.
Áp dụng các công thức trên ta thu được bảng các số Bell như sau:
n 0 1 2 3 4 5 6 7 8
B
n
1 1 2 5 15 52 203 877 4140
20
Chương 2
Hàm sinh và công thức
sàng
Trong phần này chúng ta xem xét một phương pháp rất hữu hiệu trong
việc nghiên cứu những dãy số, bằng việc xem các số trong dãy số như là hệ số
trong một chuỗi lũy thừa hình thức. (Xem [4], [6], [9]).
2.1 Hàm sinh
Định nghĩa 2.1. ([9], tr 30). Nếu a
0
, a
1
, , a
n
, là dãy số thì G(t) = a
0
+ a

n
. Theo định
nghĩa, hàm sinh của dãy số hữu hạn trên sẽ là
G(t) = C
0
n
+ C
1
n
t + C
2
n
t
2
+ + C
n
n
t
n
.

21
Ví dụ 2.2. Số Fibonacci ([9], tr 31). Xét dãy Fibonacci {F
n
}
∞
n=0
, xác định bởi
công thức truy hồi
F

t + F
1
t
2
+ F
2
t
3
+ + F
n
t
n+1
+
t
2
G(t) = F
0
t
2
+ F
1
t
3
+ F
2
t
4
+ + F
n
t

)G(t) = t
Suy ra G(t) =
t
1 −t − t
2
Vế phải của đẳng thức trên có thể phân tích thành
1
√
5
1 −at
−
1
√
5
1 −bt
, trong đó
a =
1 +
√
5
2
và b =
1 −
√
5
2
Theo đó G(t) =
1
√
5

a −b
√
5
t
a
2
− b
2
√
5
+
a
3
− b
3
√
5
+ +
a
n
− b
n
√
5
t
n
+
Do đó ta thu được công thức cho số Fibonacci thứ n như sau:
F
n

c
n
, là số cách chèn n cặp ngoặc tròn vào tích x
1
x
2
···x
n+1
của n + 1 số sao cho
mỗi lần nhân chỉ có đúng hai thừa số. Chẳng hạn, ta có các cách chèn các cặp
ngoặc tròn vào tích x
1
x
2
x
3
x
4
như sau
(x
1
(x
2
(x
3
x
4
))), ((x
1
x

Như vậy, c
3
= 5. Ta cũng tính được c
1
= 1, c
2
= 2.
22
Ta định nghĩa c
0
= 1.
Ta có nhận xét rằng mỗi cách chèn n cặp ngoặc tròn vào tích x
1
x
2
···x
n+1
của n + 1 số chứa một cặp ngoặc ngoài cùng mà thực hiện phép nhân tích của
k + 1 số đầu x
1
x
2
···x
k+1
với tích của n −k số sau x
k+2
x
k+3
···x
n+1

+ c
2
c
n−3
+ ··· + c
n−1
c
0
=
n−1

k=0
c
k
c
n−k−1
.
Đây là hệ thức truy hồi không tuyến tính.
Ta sẽ tìm công thức tính c
n
qua n bằng cách xét hàm sinh của dãy {c
n
}
∞
n=0
.
Gọi G(t) = c
0
+ c
1

2
+ c
1
c
1
+ c
2
c
0
)t
2
+ ···
+ (c
0
c
n−1
+ c
1
c
n−2
+ ··· + c
n−1
c
0
)t
n−1
+ ···
= c
1
+ c

1 −4t
2t
và G(t) =
1 −
√
1 −4t
2t
Trong đó
√
1 −4t = (1 −4t)
1
2
= 1 +
(
1
2
)
1!
(−4t) +
(
1
2
)(−
1
2
)
2!
(−4t)
2
+

t
2
+
1.3
2
3
.3!
4
3
t
3
+ ··· +
1.3.5 (2n −3)
2
n
.n!
4
n
t
n
+ ···

= 1 +
2t
2!
+
1.3
3!
2
2

(n + 1)!
2
n
t
n
=
1.2.3.4.5 (2n −1)(2n)
(n + 1)!.n!.2
n
2
n
=
1.3.5.(2n −1)(2n)
(n + 1)!n!
2
n
t
n
=
(2n)!
(n + 1)!n!
=
1
n + 1
C
n
2n
.
Ta có tính một vài số đầu tiên bằng công thức trên:
c

5
C
4
8
= 14
c
5
=
1
6
C
5
10
= 42.

2.2 Hàm sinh mũ
Định nghĩa 2.2. ([9], tr 38). Hàm sinh mũ cho dãy số {a
n
}
∞
n=0
là chuỗi lũy
thừa hình thức f(t) = a
0
+ a
1
t
1!
+ ··· + a
n

+ ··· là hàm sinh mũ của
dãy các dãy các tập các vật (S([n])
∞
0
và T (t) = |T ([0])| + |T ([1])|
t
1!
+ |T ([2])|
t
2
2!
+
|T ([3])|
t
3
3!
+ ··· là hàm sinh mũ của dãy các tập các vật (T ([n])
∞
0
.
Ta định nghĩa ST ([n]) là tập bao gồm tất cả các cặp (σ, τ), trong đó σ là một
phần tử của tập S(K) với K là một tập con bất kỳ của [n], còn τ là một phần
tử của của tập T (K) với K = [n] \K. K hi dó,
|ST ([n])| =
n

k=0
C
k
n

Mặt khác,
S(t)T (t) = |S(∅)||T (∅)| +

|S(∅)||T ([1])|
1
0!
1
1!
+ |S([1])||T (∅)|
1
1!
1
0!

t
+

|S(∅)||T ([2])|
1
0!
1
2!
+ |S([1])||T ([1])|
1
1!
1
1!
+ |S([2])||T (∅)|
1
2!

1
(n −2)!
1
2!
+ |S([n − 1])||T ([1])|
1
(n −1)!
1
1!
+ |S([n])||T (∅)|
1
n!
1
0!

t
n
+ ···