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

NGUYỄN XUÂN TRỌNG

ỨNG DỤNG SỐ STIRLING VÀO
GIẢI TOÁN TỔ HỢP

Chuyên ngành : Phương pháp tố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 hồ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. HỒNG QUANG TUYẾN

Phản biện 2: TS. CAO VĂN NI

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 26 tháng 5 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
Có thể nói tư duy tổ hợp ra đời rất sớm. Vào thời nhà Chu, người
ta đã biết đến các hình vẽ có liên quan đến những hình vng thần bí.
Thời cổ Hy Lạp, nhà triết học Kxenokrat, sống ở thế kỉ 4 trước cơng
ngun, đã biết tính số các từ khác nhau lập từ bảng chữ cái cho trước.
Nhà toán học Pytago và các học trị của ơng đã tìm ra nhiều con số có
tính chất đặc biệt. Việc tìm ra các con số như vậy địi hỏi phải có một
nghệ thuật tổ hợp nhất định . Tuy nhiên, có thể nói rằng, lý thuyết tổ hợp
được hình thành như một ngành tốn học mới vào khoảng thế kỉ 17 bằng
một loạt các cơng trình nghiêm túc của các nhà tốn học xuất sắc như
Pascal, Fermat, Leibnitz, Euler,…Mặc dù vậy, trong suốt hai thế kỉ rưỡi,
tổ hợp khơng có vai trị nhiều trong nghiên cứu tự nhiên. Đến nay, với sự
hỗ trợ đắc lực của máy tính, tổ hợp đã chuyển sang lĩnh vực tốn ứng
dụng với sự phát triển mạnh mẽ, có nhiều kết quả có ích cho con người .
Nhận thức được vai trò của lý thuyết tổ hợp trong đời sống hiện
đại. Tổ hợp đã được đưa vào giảng dạy ở chương trình học phổ thơng,
đại học, sau đại học và nó là một bộ mơn tương đối khó đối với học sinh,
sinh viên vì khái niệm trừu tượng và nhiều dạng tốn rất khó nhưng thời
lượng dành cho mơn này còn hạn chế nhất là bậc trung học phổ thơng.
Trong nhiều kì 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, cao đẳng các bài toán
liên quan đến tổ hợp hay được đề cập và thường thuộc loại rất khó nên
học sinh đa số cịn lúng túng khi giải quyết những bài toán loại này.



2

Chính vì các lý do nêu trên, tơi quyết định chọn đề tài “ ỨNG
DỤNG SỐ STIRLING VÀO GIẢI TOÁN TỔ HỢP ” để 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 đích nghiên cứu
Nghiên cứu về các số Stirling và ứng dụng của số Stirling để giải
các bài toán về tổ hợp.
3. Nhiệm vụ nghiên cứu
- Tìm hiểu về lý thuyết tổ hợp, đặc biệt là số Stirling
- Tìm hiểu và xây dựng các ứng dụng của các số Stirling để
giải các bài toán về tổ hợp.
4. Đối tượng và phạm vi nghiên cứu
- Đối tượng nghiên cứu là các số Stirling.
- Phạm vi nghiên cứu là số Stirling và ứng dụng ứng dụng của số
Stirling để giải các bài toán về tổ hợp.
5. Phương pháp nghiên cứu
- Nghiên cứu lý thuyết thông qua việc sưu tầm các loại tài liệu như
sách, báo, tạp chí, mạng internet, thầy cơ, bạn bè. Trình bày một cách có
hệ thống các nội dung lý thuyết đã nghiên cứu và tìm hiểu. Mỗi nội dung
phải chứng minh cụ thể, rõ ràng và lấy ví dụ minh họa xác thực, dễ hiểu.
- Phân loại và hệ thống các dạng toán. Tìm ra các phương pháp
đặc trưng để giải mỗi dạng toán cụ thể.


3


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 các số Stirling vào giải
toán tổ hợp phù hợp với chuyên ngành Phương pháp toán sơ cấp.
- Sau khi cho phép bảo vệ, được sự góp ý của các thầy cơ trong hội
đồng, luận văn có thể dùng làm tài liệu tham khảo cho sinh viên, giáo
viên, học sinh phổ thông và những ai quan tâm đến lĩnh vực này.
- 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 của luận văn
Ngồi phần mở đầu và kết luận, luận văn được chia thành ba
chương :
Chương 1: Cơ sở lý thuyết
Trong chương này tơi trình bày các định nghĩa, tính chất, ví dụ về
nguyên lý cộng, nguyên lý nhân, các cấu hình tổ hợp cơ bản và nâng
cao, phân hoạch tổ hợp thứ tự và không thứ tự, công thức nhị thức
Newton.
Chương 2: Số Stirling loại 1 và loại 2
Trong chương này tôi trình bày các định nghĩa, tính chất của số
Stirling loại 1 và loại 2 .
Chương 3: Ứng dụng của số Stirling giải các bài tốn tổ hợp.
Trong chương này tơi trình bày một số ứng dụng của các số
Stirling để giải các bài toán tổ hợp.


4

CHƯƠNG 1

CƠ SỞ LÝ THUYẾT
1.1 NGUYÊN LÝ CỘNG VÀ NGUYÊN LÝ NHÂN
1.1.1 Nguyên lý cộng
Định nghĩa 1.1. Giả sử {X1, X2,...,Xn} là một phân hoạch của tập S. Khi
đó
S  X1  X 2  ...  X n

.

1.1.2 Nguyên lý nhân
Định nghĩa 1.2. 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ể được thực hiện theo n1 cách, bước 2 có thể được thực hiện
theo n2 cách, ..., bước k có thể thực hiện theo nk cách. Khi đó số cấu hình
tổ hợp là :
n1n2...nk .
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.3. 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.
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 Xk, 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) = nk.


5

1.2.2 Chỉnh hợp không lặp
Định nghĩa 1.4. 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 thành phần đã cho.
Các thành phần không được lặp lại.
Kí hiệu A(n,k) và A(n,k ) =

n!
.
(n - k )!

1.2.3 Hoán vị
Định nghĩa 1.5. 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ử đó .
Hố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. Ta có số hốn vị kí hiệu là P(n), P(n) = n!.
1.2.4 Tổ hợp
Định nghĩa 1.6. 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.
Kí hiệu C(n,k) là số tổ hợp chập k của n phần tử ta có:
C  n,k  =

n!
.
k!  n - k  !

1.3 CÁC CẤU HÌNH TỔ HỢP MỞ RỘNG
1.3.1 Hoán vị lặp
Định nghĩa 1.7. Hoán vị lặp là hốn vị trong đó mỗi phần tử được ấn
định một số lần lặp lại cho trước.



6

Định lí 1.1. Số hốn vị lặp của n phần tử khác nhau, trong đó phần tử thứ
nhất lặp n1 lần, phần tử thứ 2 lặp n2 lần, …, phần tử thứ k lặp nk lần là
P(n; n1 , n2 ,..., nk ) 

n!
,
n1 !n2 !...nk !

với n1  n2  ...  nk  n .
1.3.2 Tổ hợp lặp
Định nghĩa 1.8. Tổ hợp lặp chập k từ n phần tử 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ả sử 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–1,k).
1.3.3 Phân hoạch thứ tự tổ hợp
Định nghĩa 1.9. 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 S1 , S2 ,..., Sk  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 n1, n2,…,nk thỏa mãn n1+ n2 +…+ nk = r. Số
các phân hoạch thứ tự tổ hợp chập r của X có dạng S1 , S2 ,..., Sk  có
S1  n1 , S2  n2 ,…, Sk  nk được ký hiệu là C(n ; n1, n2,…,nk).

Định lí 1.3.
C  n; n1 , n2 , , nk  


n!
= P  n;n1 ,n2 ,...,nk ,n - r  .
n1!n2!...nk!  n - r !

C(n;n1,n2,…,nk) được gọi là hệ số đa thức.


7

1.3.4 Phân hoạch không thứ tự
Định nghĩa 1.10. Cho X là tập 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 bao 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.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à
C ( n; n1 ,..., n1 , n2 ,...n2 , nk ,..., nk )
n!

.
p
p1 ! p2 !... pk !
p1 !( n1 !) p2 !( n2 !) p ... pk !( nk !) p
1

2

k


(trong tử số C(n; n1,..., n1, n2 ,...n2 , nk ,..., nk ) số n1 lặp lại p1 lần, n2 lặp lại p2
lần, …, nk lặp lại pk lần).
1.4 NGUYÊN LÝ BÙ TRỪ
Cho hai tập A, B. Theo ngun lý cộng ta có
Định lí 1.5
A B  A  B  A B

Cho tập X và n tập con X1, X 2 ,..., X n , bằng quy nạp ta có
Định lí 1.6
n

X 1  X 2  ...  X n   (1)k 1 X (n, k )
k 1

trong đó X (n, k ) 



1i1 ...ik  n

X i  X i  ...  X i .
1

2

k

Trong tổng X (n, k ) , bộ (i1, i2 ,..., ik ) lấy tất cả các tổ hợp chập k của n và
như vậy X (n, k ) là tổng của C(n,k) số hạng. Nói riêng ta có
X (n,1)  X 1  X 2  ...  X n



8

và

X (n, n)  X1  X 2  ...  X n .

Từ Định lí 1.6 và sử dụng tính chất
X 1  X 2  ...  X n  X 1  X 2  ...  X n
 X  X 1  X 2  ...  X n ,

ta nhận được công thức sau :
Định lí 1.7 (cơng thức Sieve)
n

X 1  X 2  ...  X n   (1)k X (n, k ) ,
k 0

trong đó

X (n,0)  X

và

X (n, k ) 



1i1 ...ik  n


X i  X i  ...  X i
1

2

k

, k  1,..., n .

1.5 NHỊ THỨC NEWTON
Định lí 1.8 (Cơng thức nhị thức Newton)
n

(a  b)   Cnk a nk b k  Cn0a n  Cn1a n1b  ...  Cnnb n .
n

k 0

Chú ý : Số hạng tổng quát thứ k+1 là: Tk 1  Cnk a nk bk  Cnk a k bnk .
Hệ số của số hạng thứ k+1 là giá trị không chứa biến.
Công thức tam giác Pascal : C(n,k) = C(n – 1,k – 1) + C(n – 1,k).
1.6 HÀM SINH THƯỜNG VÀ HÀM SINH MŨ
Cho dãy số thực (a0, a1, a2, …) và biến x.
Định nghĩa 1.11
Hàm sinh thường của dãy (a0, a1, a2, ...) là hàm
g(x) = a0 + a1x + a2x2 + ...
Hàm sinh mũ của dãy (a0, a1, a2, …) là hàm



9

g(x) = a0 + a1 x + a2 x + ... .
2

1!

2!

1.7 KHAI TRIỂN LŨY THỪA CỦA MỘT HÀM
Định lí 1.9. Cho hàm số f khả vi vô hạn lần trên R. Khi đó :
f ' ( x0 )
f '' ( x0 )
f ( x)  f ( x0 ) 
( x  x0 ) 
( x  x0 )2  ...
1!
2!


10

CHƯƠNG 2
SỐ STIRLING LOẠI I VÀ
SỐ STIRLING LOẠI II
2.1 SỐ STIRLING LOẠI I
Kí hiệu [x]0  1 và [x]n  x(x – 1)(x – 2)…(x – n+1) với n = 1,2,… [2.1]
Định nghĩa 2.1. Hệ số của xk trong [x]n được hiểu là số Stirling loại I,
kí hiệu s(n,k).
Ta có [x]n =


n

 s ( n, k ) x

k

,

[2.2]

k 0

Quy ước

s(n,0) = 0,

n  N *

s(0,k) = 0,

k  N *

s(n,k) = 0 nếu n > k và s(0,0) = 1.
Định lí 2.1. ([14]) Cho n, k  N * ta có :
s(n+1,k) = s(n,k – 1) – ns(n,k).

[2.3]

Hệ quả. Từ kết quả Định lý 2.1 ta nhận được tam giác các số Stirling

loại I như sau :
Bảng 2.1. Số Stirling loại I
n
0
1

s(n,0) s(n,1) s(n,2)
1
0
1

2

0

-1

1

3

0

2

-3

4
5
6

7
8

0
0
0
0
0

s(n,3)

s(n,4) s(n,5) s(n,6) s(n,7) s(n,8)

1

-6
11
-6
1
24
-50
35
-10
1
-120
274
-225
85
-15
720 -1764 1624 -735 175

-5040 13068 -13132 6769 -1960

1
-21
322

1
-28

1


11

2.2 SỐ STIRLING LOẠI I KHƠNG DẤU
Kí hiệu [x]0  1 và [x]n  x(x+1)(x+2)…(x+n – 1) với n = 1,2,…

[2.4]

Định nghĩa 2.2. Hệ số của xk trong [x]n được hiểu là số Stirling loại I
khơng dấu, kí hiệu s  n,k  .
Ta có [x]n =

n

 s  n,k  x

k

,


[2.5]

k 0

Quy ước

s   n,0  = 0 , n  N *
s   0 ,k  = 0 , k  N *
s  n,k  = 0 , nếu n > k và s   0,0  = 1.

Ngoài ra s  n,k  còn tượng trưng cho số cách xếp n đồ vật vào k chu
trình. Chu trình là một cách sắp xếp trên vịng trịn.
Ví dụ. Ta có 11 cách chia 4 phần tử thành 2 chu trình là :
[1,2,3][4] ; [1,2,4][3]; [1,3,4][2] ; [2,3,4][1] ; [1,3,2][4] ; [1,4,2][3] ;
[1,4,3][2] ; [2,3,4][1] ; [1,2][3,4] ; [1,3][2,4] ; [1,4][2,3] . Vậy s   4, 2  =
11 .
Mệnh đề 2.1. Cho n  N , k  Z ta có s  n,k  = |s(n,k)|.
Mệnh đề 2.2. ([14])
a) s  n,1 = (n – 1)! với n  N* .
b) s  n,n  = 1 với n  N .
n

c)


k 0

s  n,k  = n! với n  N .


Định lí 2.2. ([14]) Cho n, k  N * , ta có :
s  n + 1,k  = s  n,k - 1 + n s  n,k  .

[2.6]


12

Hệ quả. Từ kết quả trên ta nhận được tam giác các số Stirling loại I
không dấu như sau :
Bảng 2.2. Số Stirling loại I không dấu
n

s   n,0 

s  n,1

s   n,2 

s  n,3

s   n,4 

s  n,5

s   n,6 

s   n,7 

0


1

1

0

1

2

0

1

1

3

0

2

3

1

4

0


6

11

6

1

5

0

24

50

35

10

1

6

0

120

274


225

85

15

1

7

0

720

1764

1624

735

175

21

1

8

0


5040

13068 13132

6769

1960

322

28

s  n,8 

1

Định nghĩa 2.3. Số Harmonic
1
.
r
k 1 k
n

Cho n,r  N * . Số Harmonic kí hiệu là : H n( r ) với H n( r )  

Mệnh đề 2.3.Quan hệ giữa số Stirling loại I không dấu và số Harmonic :
s   n + 1, 2  = n!(1 

1

1
 ...  ) = n!Hn , n  N * .
2
n

Mệnh đề 2.4. Các tính chất trên hàng, cột và đường chéo của bảng số
stirling loại I không dấu.
a) Cho n là số tự nhiên. khi đó
n

 j.s  n, j  = s  n+1,2  , n  N .
*

j=0

b) Cho n và c là các số nguyên không âm. Khi đó


13

n

 C  j,c  .s  n, j  = s  n +1,c+1 .
j=0

c) Cho n và c là các số ngun khơng âm. Khi đó
n

s  n +1,c+1 = n n-k .s  k,c  , n, c  N .
k=0


d) Cho n và c là các số ngun khơng âm. Khi đó
c

s  n +c +1,c  =   n +k  .s  n +k,k  .
k=0

2.3 SỐ STIRLING LOẠI II
Định nghĩa 2.4
Cho tập X có n phần tử khác nhau, k  n và {X1, X2, … , Xk} là một phân
hoạch k khối của X. Số tất cả các phân hoạch k khối của tập lực lượng n gọi
là số Stirling loại II, kí hiệu S(n,k). Hiển nhiên S(n,0) = 0 và S(n,n) = 1.
S(n,k) > 0 với 1  k  n và S(n,k) = 0 nếu 1  n  k
Ta đặt S(0,0) = 1 và S(0,k) = 0 với k  1 .
Do đó ý nghĩa của số Stirling là số các quan hệ tương đương với k lớp
trên một tập hợp n phần tử. Đó cũng là số cách phân bố n quả cầu riêng
biệt vào k hộp khơng phân biệt (mà khơng tính thứ tự sắp xếp) sao cho
khơng có hộp nào rỗng.
Mệnh đề 2.5. Số tồn ánh từ tập n phần tử tới tập k phần tử bằng
k!S(n,k) .
Định lí 2.3. ([17]) Số Stirling có thể tính trực tiếp qua cơng thức sau:
S (n, k ) 
=

1
j
n
 1 C (k , j )  k  j 

k ! 0 j  k

1
k i
 1 C (k , i)i n

k ! 0i  k

[2.7]


14

Công thức trên vẫn đúng khi k > n (lúc đó S(n,k) = 0).
Định lí 2.4. ([14]) Cho n, k  N * . Ta có :
S(n + 1,k) = S(n,k – 1) + kS(n, k).

[2.8]

Hệ quả. Từ kết quả Định lý 2.4 và điều kiện S(n,1) = S(n,n) = 1, S(n,m)
= 0 với n < m, ta xây dựng được tam giác các số Stirling loại II như sau:
Bảng 2.3. Số Stirling loại II
n

S(n,0) S(n,1) S(n,2) S(n,3) S(n,4) S(n,5) S(n,6) S(n,7) S(n,8)

0

1

1


0

1

2

0

1

1

3

0

1

3

1

4

0

1

7


6

1

5

0

1

15

25

10

1

6

0

1

31

90

65


15

1

7

0

1

63

301

350

140

21

1

8

0

1

127


966

1701

1050

266

28

1

Định lí 2.5. ([14]) Cho n  N . Số Stirling loại II được cho bởi công thức
:
n

x n   S (n, k )[x ]k .

[2.9]

k 0

Quy ước

S(n,0) = 0 ,

n  N *

S(0,k) = 0 ,


k  N *

S(n,k) = 0, nếu n > k và S(0,0) = 1.
Định lí 2.6. ([14]) Với k , n  N , ta có S (n, m)   C (n  1, k )S (k , m  1) .
k


15

Định lí 2.7. ([14]) Với n  N * . Ta có :
a)

n

 x + y  = C  n,r  x
n

n-r

r=0

b)

 y

r

,

n


 x + y n = C  n,r  xn-r  y r .
r=0

Định lí 2.8 ([14])
a) C (i  j, i)s(n, i  j )   C (n, k )s(k , i )s(n  k , j ) .
k

b) C (i  j, i)S (n, i  j )   C (n, k )S (k , i)S (n  k , j ) .
k

Chứng minh
Mệnh đề 2.6 ([17]). Cho n và c là các số ngun khơng âm. Ta có
a)

n

S (n  1, c  1)   C (n, k )S (k , c)
k 0

b)

n

S (n  1, c  1)   (c  1)nk S (k , c)
k 0

c)

c


S (n  c  1, c)   kS (n  k , k ) .
k 0

2.4 QUAN HỆ GIỮA SỐ STIRLING LOẠI I VÀ SỐ STIRLING
LOẠI II
Định lí 2.9 ([14]). Cho n,m là các số tự nhiên . Khi đó :
m

 S (n, k )s(k , m)   ,

a)

nm

k n
m

 s(n, k )S (k , m)   ,

b)

nm

k n

1
0

với  mn  


khi m  n
khi m  n

.


16

2.5 HÀM SINH CỦA CÁC SỐ STIRLING
2.5.1 Hàm sinh của số Stirling loại II
Định lí 2.10 ([17])
tn 1 t
k (t )   S (n, k )  (e  1)k , k  0 ,
n! k !
n k

(tại n  k có thể thay thế bởi n  0), và ta có :
tn k
tn 
 ( t , u )   S ( n, k ) u  1  
S ( n , k )u k 



n!
n ,k  0
n ,k 0 n ! 1k n
t


= eu ( e 1) .
Định lí 2.11 ([17])
uk
k :  S (n, k )u 
,
(1  u )(1  2u ).....(1  ku )
n k
n

k  1.

2.5.2 Hàm sinh của số Stirling loại I
Định lí 2.12 ([17])

  s(n, k )u   (1  t)

tn k
tn
(t , u )   s(n, k ) u  1  
n!
n , k 0
n 1 n!

và

k

u

1 k  n


tn 1
 k (t )   s(n, k )  log k (1  t) .
n! k !
n k

Định lí 2.13 ([17])
n (u) 

 s(n, k )u

n k

 (1  u)(1  2u)...(1  (n  1)u) ,

[2.14]

1k n

n (u) 

 s (n, k )u
'

1k n

n k

 (1  u)(1  2u)...(1  (n  1)u) .


[2.15]


17

CHƯƠNG 3
ỨNG DỤNG SỐ STIRLING VÀO
GIẢI TOÁN TỒ HỢP
3.1 MỘT SỐ BÀI TỐN ĐẾM
Bài tốn 3.1. Tìm số cách đặt n vật phân biệt vào m hộp phân biệt, nếu
kể đến thứ tự từ trái qua phải của các vật trong hộp biết rằng có thể cho
phép một số hộp để trống (chú ý rằng nếu m > n, ít nhất m – n hộp phải
bỏ trống).
Bài toán 3.2. Yêu cầu tương tự như Bài toán 3.1 tuy nhiên thêm điều
kiện m  n và những trường hợp để trống khơng được phép .
Bài tốn 3.3. Nếu m và n là các số nguyên dương. Chứng minh rằng
[m ]n
phương trình x1 + x2 + ... xm = n có đúng
nghiệm. Trong đó xk là
n!

các số ngun khơng âm (kết quả cũng đúng khi n = 0).
Bài toán 3.4. Cho trước 1, 2 ,..., m là các số nguyên không âm. Tìm số
nghiệm nguyên của phương trình x1 + x2 + ... + xm = n sao cho xi  i ,
với i = 1,...,m.
Bài toán 3.5. Giả sử A = {ai : i = 1,2,...,m} là một bảng chữ cái bao gồm
m chữ cái được sắp xếp thứ tự như sau : a1 < a2 < ... < am. Một từ

12 ...n tạo ra từ bảng chữ cái này được gọi là một từ tăng (có độ dài n)
nếu 1  2  ...  n .

Chứng minh số các từ tăng có độ dài n là C(n + m – 1,m – 1).
Bài toán 3.6. Sử dụng tổ hợp thiết lập công thức
n

 x = u  n,k  x
n

k=1

k

với u(n, k ) 

n!
C (n  1, k  1) .
k!

[3.1]


18

Bài tốn 3.7. Bài tốn tìm số các hàm tăng.
Một hàm f có tập xác định là N = { 1 ,  2 , . . . ,  n } và tập giá trị là M =
{ 1 , 2 ,...,  m }, f là một hàm tăng (từ N tới M) nếu f (i )  f ( j ) nếu

i   j .
Xác định số lượng hàm tăng trong định nghĩa trên.
Bài toán 3.8. Tìm số cách chọn ra r số nguyên phân biệt từ n số nguyên
dương đầu tiên sao cho trong sự lựa chọn đó khơng có chứa hai số

ngun liên tiếp.
Bài tốn 3.9. Tìm số cách chọn ra r số ngun phân biệt từ n số nguyên
dương đầu tiên sao cho khơng có hai số ngun liên tiếp nào xuất hiện
trong sự lựa chọn và sự lựa chọn khơng có đồng thời cả hai số 1 và n.
Bài tốn 3.10. Có bao nhiêu cách để làm nhiều bộ khác nhau của k chiếc
vòng đeo tay từ n hạt riêng biệt. Biết rằng một vịng đeo tay cần phải có
ít nhất một hạt?.
Bài tốn 3.11. Có bao nhiêu cách xếp n nam và m nữ ngồi vào k bàn
tròn giống hệt nhau mà mỗi bàn có ít nhất một nam và một nữ .
Bài tốn 3.12. Bài tốn tìm số các hốn vị của tập hữu hạn X có chu
trình cấp k.
Một hoán vị của tập hữu hạn X là một song ánh từ X tới X. Giả sử f
là một hoán vị của X và x là một phần tử thuộc X. Ta xây dựng phép đệ
quy như sau : f 1 ( x)  f ( x) , f 2 ( x)  f ( f 1 ( x)) , ... , f i ( x)  f ( f i1 ( x)) , ....
Do X là hữu hạn nên tồn tại một số nguyên dương r sao cho f r ( x)  x .
Khi đó dãy x, f 1 ( x), f 2 ( x)..., f r 1 ( x) được gọi là một chu trình cấp
r của hoán vị f . Hiển nhiên, mỗi hoán vị của X có thể biểu diễn bằng


19

hợp thành của k chu trình rời nhau. Trong đó k nhận giá trị thấp nhất là 1
và lớn nhất là bằng lực lượng của tập X. Ta đặt
Pn,k  {f : f là một hoán vị của X và f có đúng k chu trình}.

Tìm card( Pn,k ).
Bài tốn 3.13. Một thương hiệu nhất định của một sản phẩm cung cấp
một trong k(k>1) giải thưởng cho mỗi sản phẩm của họ với xác xuất
bằng nhau cho mỗi sản phẩm. Xác suất có ít nhất một giải thưởng khi họ
bán ra n sản phẩm là bao nhiêu ?.

Bài toán 3.14. Đếm số cách phân phối n vật phân biệt vào m hộp nếu
thỏa mãn :
a) m hộp giống nhau và mỗi hộp phải có ít nhất một vật.
b) m hộp giống nhau và cho phép có hộp trống.
c) Các hộp đều phân biệt và mỗi hộp phải có ít nhất một vật.
Bài toán 3.15. Chứng minh rằng
a) S(n,2 )= 2n-1 - 1.
b) S (n, n  1)  C(n,2) .
Bài tốn 3.16. Kí hiệu Si (n, k ) là số cách phân hoạch tập hợp gồm n
phần tử thành k tập con sao cho mỗi tập con chứa ít nhất i phần tử .
Chứng minh rằng
Si (n, k )  kSi (n  1, k )  C(n  1, i  1)Si (n  i, k 1) .

Bài toán 3.17. Tìm số các hàm từ tập X gồm n phần tử đến tập Y gồm m
phần tử sao cho những hàm này có miền giá trị đúng r phần tử .
Bài toán 3.18. Cho X  x1 , x2 ,..., xn  , Y   y1 , y2 ,..., yk  (n,k > 1). Tìm số
các tồn ánh f : A  B sao cho f ( xn )  yk .


20

3.2 THU GỌN SỐ STIRLING LOẠI II
Định nghĩa 3.1. Thu gọn số Stirling loại II, kí hiệu S d (n, k ) , là số cách
để phân hoạch các số nguyên 1, 2, ..., n thành k tập con không rỗng sao
cho tất cả các phần tử trong mỗi tập con cách nhau từng đôi một một
khoảng cách tối thiểu là d. Khi đó, với bất kì số ngun i và j trong một
tập con cho trước thì yêu cầu i  j  d .
Định nghĩa 3.2. Tô màu đỉnh của đơn đồ thị G là sự gán màu cho các
đỉnh của nó sao cho khơng có hai đỉnh kề được gán cùng một màu .
Sắc số của đồ thị, kí hiệu  (G) là số màu tối thiểu cần thiết để tô màu

đỉnh của đồ thị .
Một nhãn màu riêng của đồ thị là tập hợp các màu của các đỉnh của nó
thỏa mãn hai đỉnh kề có màu khác nhau. Đa thức sắc số của đồ thị, kí
hiệu là  (G, k ) là số nhãn màu riêng của đồ thị sử dụng k màu (hoặc ít
hơn). Đa thức sắc số chứa đồ thị G, kí hiệu  (G, k ) là số nhãn màu riêng
của V(G) mà sử dụng đúng k màu. Kí hiệu Pn là đường đi của đồ thị trên
n đỉnh.
Bài tốn 3.19. Tìm số nhãn màu riêng của Pn mà sử dụng đúng k màu.
Bài toán 3.20. Chứng minh rằng
S 2 (n, k )  S 2 (n 1, k 1)  (k 1)S 2 (n 1, k ), n, k  2.

Bài toán 3.21. Chứng minh rằng S 2 (n, k )  S (n 1, k 1), n, k  2 .
Bài toán 3.22. Chứng minh rằng
S d (n, k )  S d (n 1, k 1)  (k  d  1)S d (n, k 1), n  k  d .

Bài toán 3.23. Chứng minh rằng


21

S d (n, k )  S  n  d  1, k  d  1 , n  k  d

Như vậy, S1(n,k) = S(n,k).
3.3 SỐ BELL VÀ PHÂN HOẠCH TẬP HỢP
Định nghĩa 3.3. Số cách phân hoạch tập gồm n phần tử được gọi là số
Bell , kí hiệu Bn. Quy ước B0 = 1, ta có
n

Bn   S (n, k )


i)

k 1

n 1

ii) Bn   C (n  1, k )Bk
k 1

1 k
(1)r C (k , r )(k  r )n .

k 1 k ! r 0
n

iii) Bn  

Bài tốn 3.24. Kí hiệu B(n n  j ) là số cách phân hoạch một tập hợp
gồm n phần tử mà trong đó có ít nhất một tập con với n – j phần tử, j =
n n

n

1, 2, ...,   (   là phần nguyên của ). Khi đó với mọi n  2, ta có
2
2 2
C (n, j ) B j


B(n n  j )     n   

1  n n 
C
n
,
B


   2    n  2    2  , 2  
 2


 
1
0

trong đó  ( x, y )  

khi
khi

x y
x y

n
j  1,...,    1
2
,
n
j 
2


.

Áp dụng.
1. Tìm số cách phân hoạch một tập hợp gồm 5 phần tử mà trong đó có
đúng một tập con :
a) Có 4 phần tử.
b) Có 3 phần tử.


22

2. Tìm số cách phân hoạch một tập hợp gồm 4 phần tử mà trong đó có ít
nhất một tập con có 2 phần tử.
Bài tốn 3.25. Số cách phân hoạch tập n phần tử thành các tập con mà
tất cả các tập con đều có m phần tử, kí hiệu là Pm (n) . Chứng minh rằng
Pm (n) 

nếu m | n thì

1
n!
C (n; m, m,..., m) 
.
n
n
n
 m 

 m  !

 m  !(m!)

Bài toán 3.26. Số cách phân hoạch tập n phần tử thành các tập con sao
cho số các tập con có m phần tử đạt lớn nhất, kí hiệu là Pm' (n) .
  n 
 m  m  !
n




Chứng minh rằng Pm ' (n)  C  n, m   .     n  .B  n  .
nm 
 m 
m  n 

m
!(
m
!)
 m 

Bài toán 3.27. Cho m | n, kí hiệu Pm|n ,...,n (n) là số cách phân hoạch tập n
1

j

phần tử thành các tập con m phần tử sao cho trong j tập con đó có m
phần tử đặc biệt nào đó của tập hợp. Ở đây, tồn tại các số n1 , n2 ,..., n j phần
n

tử , j  1,2,..., ,
m

j

n
i 1

Pm|n ,...,n (n) 
1

j

.

i

 m . Chứng minh rằng

1
C  m; n1 ,..., n j .C  n  m; m  n1 ,..., m  n j , n  jm .
j!

 n  jm!
n  jm
 n  jm 
m

!m!
m




.

Áp dụng. Tìm số cách phân hoạch tập {1, 2, ..., 9} thành các tập con
gồm 3 phần tử :
a) Các phần tử tùy ý .


23

b) 3 phần tử 1, 2, 3 ở ba tập con khác nhau .
Bài tốn 3.28. Nếu m|n thì
n
m

Pm (n)  



j
j 1 

n1 ,..., n j | ni  n , ni 1
i 1






1
C  m; n1 ,..., n j .
j!

.C  n  m; m  n1 ,..., m  n j , n  jm .

 n  jm!
n  jm
 n  jm 
m
!
m
!


 m 

.