BỘ GIÁO DỤC VÀ ĐÀO TẠO
Công trình ñược hoàn thành tại
ĐẠI HỌC ĐÀ NẴNG
ĐẠI HỌC ĐÀ NẴNG (cid:1)(cid:1)(cid:2)(cid:3)(cid:3)
ĐẶNG THỊ NGUYỄN VIỆT
Người hướng dẫn khoa học: PGS . TSKH TRẦN QUỐC CHIẾN
SỐ STIRLING VÀ ỨNG DỤNG
Phản biện 1 :…………………………………………………
Phản biện 2 :………………………………………………….
Chuyên ngành : PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số : 60.46.40
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ĩ chuyên ngành Phương pháp Toán sơ cấp tại Đại học
Đà Nẵng vào ngày 02.tháng …12.năm…2012…..
TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC
Người hướng dẫn khoa học : PGS . TSKH TRẦN QUỐC CHIẾN
- Trung tâm Thông tin - Học liệu , Đại học Đà Nẵng
Có thể tìm hiểu luận văn tại :
- Thư viện truờng Đại học sư phạm , Đại học Đà Nẵng
Đà Nẵng - Năm 2012
Đối tượng : Số Stirling loại 1 và số Stirling loại 2 và các ứng
A. MỞ ĐẦU
dụng của nó . 1. LÝ DO CHỌN ĐỀ TÀI : Phạm vi nghiên cứu : Để thực hiện ñề tài này tôi sẽ tiến hành Năm 1730 , cuốn sách quan trọng nhất của James Sitirling
thu thập và nghiên cứu trên các bài báo toán học nổi tiếng , các (1692 – 1770 ) ñã ñược xuất bản , “ Methodus differentialis , cuốn sách ñề cập ñến số Stirling . sive Tractatus de Summatine et Interpolatione Serireum
4. PHƯƠNG PHÁP NGHIÊN CỨU Infinitarum ” . Trong cuốn sách này ông ñã chỉ ra cách tăng
Nghiên cứu trực tiếp từ các tài liệu của giáo viên hướng dẫn , nhanh ñộ hội tụ của một dãy số và các biến ñổi nói chung của
của các ñồng nghiệp cũng như từ các học viên trong lớp . các dãy số này với mục ñích tăng tốc ñộ hội tụ . Điều này
5. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ thường kéo theo sự biến ñổi của các giai thừa sang lũy thừa và
TÀI : ngược lại và ông ấy ñã viết lên bảng ñể thực hiện ý ñịnh này .
Việc sử dụng số Stirling loại một , số Stirling loại một không Những con số trong bảng ñược gọi là số Stirling . Có hai loại số
dấu và số Stirling loại hai sẽ giải ñược một số bài toán tổ hợp Stirling là số Stirling loại một và số Stirling loại hai.
và một số bài toán giải tích một cách ñơn giản hơn . Trong luận văn này chúng ta chủ yếu nghiên cứu về số Stirling
6. CẤU TRÚC CỦA LUẬN VĂN loại hai và các ứng dụng của nó vào các lĩnh vực khác nhau của Luận văn ñược cấu trúc bởi 3 chương . toán học . Số Stirling loại hai ñã xuất hiện trong nhiều bài toán
Chương 1 : Tổng quan về tổ hợp tổ hợp và có ứng dụng trong lý thuyết thống kê.
Chương này tôi giới thiệu sơ lược về lịch sử tổ hợp và nêu
2. MỤC ĐÍCH NGHIÊN CỨU ra các bài toán tổ hợp . Ngoài ra , còn giới thiệu các công cụ hỗ
Trên cơ sở nghiên cứu ñề tài , tôi muốn giới thiệu ñến ñộc giả trợ có liên quan ñến luận văn Chương 2 : Số Stirling
nguồn gốc và các ứng dụng của số Stirling . Từ ñó, ñộc giả có Chương này nêu ñầy ñủ một cách có hệ thống ñịnh nghĩa
thể hiểu hơn rõ hơn số Stirling , nắm bắt những ứng dụng của về số Stirling loại một , số Stirling loại một không dấu và số
nó ñể có thể vận dụng vào các bài toán . Mục ñích của luận văn Stirling loại hai . Các ñịnh lý , tính chất , hàm sinh của các số
này là nghiên cứu thêm các ứng dụng của số Stirling và áp dụng Stirling và quan hệ giữa chúng .
nó vào một số lĩnh vực khác của Toán học . Chương 3 : Ứng dụng của số Stirling
3. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU
Chương này có 2 phần : phần 1 ñưa ra các bài toán tổ
hợp trong ñó có ứng dụng số Stirling ñể giải và phần 2 là ứng
B. NỘI DUNG
dụng của số Stirling ñể giải các bài toán giải tích . Ngoài phần mở ñầu và kết luận , luận văn gồm có 3 chương
CHƯƠNG 1. TỔNG QUAN VỀ TỔ HỢP
1.1 NHỮNG NGUYÊN LÍ ĐẾM CƠ BẢN
1.1.1 Nguyên lí cộng
Giả sử có k công việc T1, T2, ..., Tk. Các việc này có thể làm
tương ứng bằng n1, n2, ..., nk cách và giả sử không có hai việc
nào có thể làm ñồng thời. Khi ñó số cách làm một trong k việc
ñó là n1+n2+ ... + nk.
Quy tắc cộng có thể phát biểu dưới dạng của ngôn ngữ tập hợp
như sau: Nếu A1, A2, ..., Ak là các tập hợp ñôi một rời nhau, khi
ñó số phần tử của hợp các tập hợp này bằng tổng số các phần tử
của các tập thành phần.
...¨ (1.1a) |A1 ¨ A2 ¨ Ak| = |A1| + |A2| + ... + |Ak|.
1.1.2 Nguyên lí nhân
Giả sử một nhiệm vụ nào ñó ñược tách ra thành k việc T1, T2,
..., Tk. Nếu việc Ti có thể làm bằng ni cách sau khi các việc T1,
T2, ... Ti-1 ñã ñược làm, khi ñó có n1.n2....nk cách thi hành nhiệm
vụ ñã cho.
1.1.3 Nguyên lí bù trừ
(1.1b) Cho A1, A2 là hai tập hữu hạn, khi ñó : A2| = |A1| + |A2| - |A1 ˙ |A1 ¨ A2|.
... ¨ (1.1d) và bằng quy nạp, với k tập hữu hạn A1, A2, ..., Ak ta có: |A1 ¨ ... + (- 1)k-1Nk Ak| = N1 - N2 + N3 - A2 ¨
=
(
)
P n,n ,n ,...,n 1
2
k
n! n !.n !....n ! 2 k
1
m £ k) là tổng phần tử của tất cả các giao m trong ñó Nm (1 £ . tập lấy từ k tập ñã cho, nghĩa là :
...
|
A i 2
A i m
1
˙∑ | A i 1 £<<< ... i k m
i 2
i 1
1.2.3 Chỉnh hợp lặp ˙ ˙ Nm = £ Định nghĩa 1.2.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 phần Định lý ( Công thức Sieve) : Nếu A1 , A2 ,…, Am là những
iA là ký hiệu phần bù của Ai
(
) m A A ... A =|X|-S +S -...+ -1 S m
m
1
1
2
2
tập con của một tập hữu hạn X . tử ñã cho . Các thành phần có thể lặp lại .Như vậy số tất cả các chỉnh hợp chập k của n là : AR(n,k) = nk trong tập X với i = 1 , 2,…, m thì : 1.2.4 Chỉnh hợp không lặp ˙ ˙ ˙ (1.1e) Định nghĩa 1.2.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ừ Trong ñó Sk là ký hiệu của tổng các lực lượng của tất cả những
n phần tử ñã cho . Các thành phần không ñược lặp lại . k- bộ giao nhau ñược tạo ra từ m tập hợp ở trên .
A A
i
j
˙∑
Số tất cả các chỉnh hợp không lặp của n phần tử : , … S1 = |A1| + |A2| + …+ |Am| ; S2 =
____ i,j=1,m j i
n! ) n-k !
„ A(n,k) = n(n-1)…(n-k+1) = ( Định lý : Với kí hiệu giống ñịnh lí trên 1.2.5 Tổ hợp |A1 ¨ A2 ¨ …¨ Am| = S1 – S2 + … + ( -1)m-1 Sm Định nghĩa 1.2.5 : 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
1.2 CÁC CẤU HÌNH TỔ HỢP CƠ BẢN
phần tử ñã cho . Nói cách khác ta có thể coi một tổ hợp chập k 1.2.1 Hoán vị của n phần tử khác nhau là một tập con có phần tử từ n phần tử Định nghĩa 1.2.1 : Một hoán vị của n phần tử khác nhau là một ñã cho . cách sắp xếp thứ tự các phần tử ñó . Kí hiệu : C(n,k) là số tổ hợp chập k của n phần tử ta có : 1.2.2 Hoán vị lặp
(
n! ) k! n-k !
Định nghĩa 1.2.2 : Hoán vị lặp là hoán vị trong ñó mỗi phần tử C(n,k) =
ñược ấn ñịnh một số lần lặp lại cho trước .
1.2.6 Tổ hợp lặp Từ ñó , ta ñược số hoán vị của n phần tử trong ñó có n1 phần tử
như nhau thuộc loại 1, n2 phần tử như nhau thuộc loại 2, ..., và
nk phần tử như nhau thuộc loại k, bằng :
Định nghĩa 1.2.6 : Tổ hợp chập k từ n phần tử là một nhóm
CHƯƠNG 2
không phân biệt thứ tự gồm k phân tử trích từ n phần tử ñã cho,
SỐ STIRLING
trong ñó các phần tử có thể lặp lại.
Giả sử X có n phần tử khác nhau . Khi ñó số tổ hợp lặp chập k
2.1 SỐ STIRLING LOẠI 1
từ n phần tử của X , ký hiệu CR(n,k) là :
CR(n,k) = C(n+k-1, n-1) = C(n+k-1, k)
N , k ˛ N . Số Stirling loại một kí 2.1.1 Định nghĩa Định nghĩa 2.1.1 : Cho n ˛ 1.2.7 Nhị thức Newton :
n
n
k
n
n-k
k
hiệu là s(n, k) ñược cho bởi công thức : Công thức nhị thức Newton
(
(
)
)
( ) s n,k x
a+b = C n,k a b
(2.1a)
∑
∑
[ ] x = n
k=0
k=0
N* Công thức tam giác Pascal : C(n,k) = C(n-1,k-1) + C(n-1,k)
1.2.8 Một số công cụ bổ sung : (2.1b) Với [x]n = x(x-1)(x-2)...(x-n+1) với n ˛ và [x]0 = 1 với n ˛ N* và [x]0 = 1
Định lý l.1 ( Khai triển lũy thừa của 1 hàm ) : Cho hàm f khả Quy ước : s(n,0) = 0 với " n˛ N*
vi vô hạn lần trên R . Khi ñó : s(0, k ) = 0 với " k˛ N*
(
(
)2
f(x) = f(x )+
+...
x-x
0
) x-x + 0
0
f'(x ) 0 1!
f''(x ) 0 2!
s(n, k) = 0 nếu k >n và s(0,0) = 1
n
Định nghĩa 1.2.7 ( Ma trận chuyển cơ sở ) Giả sử B = { e1, e2 2.1.2 Các ñịnh lý Định lí 2.1.1 : Cho n ˛ N , k ˛ N , ta có : , …, en} , B’ = { e’1, e’2 , …, e’n} là hai cơ sở của không gian s(n+1, k) = s(n, k-1) - n s(n,k) (2.1c) vectơ V . Ma trận của hệ vectơ B’ trong cơ sở B ñược gọi là ma Ví dụ 2.1.2 : Cho n ˛ N . Chứng minh :
e' = j
_____ t e , j = 1,n ij
i
∑
i=1
trận chuyển từ cơ sở B sang cơ sở B’ nếu : a) s(n,n) = 1
(n-1)! " n ˛
n
) ( s n,k =0
∑
k=0
b) s(n,1) = (-1)n-1 N* (1.1f) thì P = [ tij ] là ma trận chuyển từ cơ sở B sang B’ . c) s(n,n-1) = - C(n,2) Định nghĩa 1.2.8 ( Ma trận nghịch ñảo ) : Ma trận vuông A d) ñược gọi là khả nghịch nếu tồn tại ma trận cùng cấp B sao cho
Từ công thức (2.1c) ta có bảng số Stirling loại 1 như sau : AB = BA = I , với I là ma trận ñơn vị cùng cấp . Khi ñó , B gọi là ma trận nghịch ñảo của ma trận A , kí hiệu là A-1 . (1.1g)
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)
1
0
Bảng 2.1 : Bảng số Stirling loại 1
0
1
1
0
1
-1
2
[1,3,4][2] ; [234][1] ; [132][4];[142][3] ;[143][2];[234][1] ; [12][34]; [13][24];[14][23] . Định nghĩa 2.2.2 : Cho n ˛ N . Số Stirling loại một N , k ˛
0
1
-3
2
3
n
0
- 6
11
-6
1
4
k
không dấu kí hiệu là s’(n, k) ñược cho bởi công thức :
n x =
) ( s' n,k x
∑
0
35
-50
24
-10
1
5
k=0
0
274
-120
-225
85
-15
1
6
0
720
1624
-1764
-735
175
-21
1
7
(2.2a) [ ]
0
-5040
13068
-13132
6769
-1960
322
-28
1
8
N* và [x]0 = 1 (2.2b)
Với [x]n = x(x+1)(x+2)...(x+n-1) với n ˛ n˛ N* s’(n,0) = 0 với " Quy ước :
n
k
)
)
( s n,k
( ln 1+y
∑
y 1 = n! k!
n k
s’(0, k) = 0 với " k˛ N* Định lý 2.1.2 : Đẳng thức về hàm sinh lũy thừa cho số Stirling s’(n, k) = 0 nếu k >n và s’(0,0) = 1 loại 1 : 2.2.2 Các tính chất : (2.1d) Tính chất 2.2.1 : ‡
a) s’(n,1) = (n-1)! với n ˛ N* b) s’(n,n) =1 với n ˛ N
2.2 SỐ STIRLING LOẠI MỘT KHÔNG DẤU
n
) ( s' n,k =n!
∑
k =
0
2.2.1 Các ñịnh nghĩa c) với n ˛ 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)
n
Định nghĩa 2.2.1 : Giá trị tuyệt ñối của s(n,k) ñược gọi là số Từ các công thức trên ta xây dựng tam giác của số Stirling loại Stirling loại 1 không dấu và ñược kí hiệu là s’(n,k) với 1 không dấu s’(n,k) = | s(n,k)| . Bảng 2.2 : Bảng số Stirling loại 1 không dấu Ngoài ra s’(n,k) còn tượng trưng cho số cách xếp n ñồ vật vào k
1
0
0
1
1
xích .Xích là một cách sắp xếp trên vòng tròn . Hai xích là
0
1
1
2
giống nhau nếu có thể chặt xích ở vị trí nào ñó và căng ra ta thu
0
2
3
1
3
0
6
11
6
1
4
ñược 2 tập có thứ tự giống nhau . Với xích [A,B,C,D] ta có :
0
24
50
35
10
1
5
0
120
274
225
85
15
1
6
[A,B,C,D] = [B,C,D,A] = [C,D,A,B] = [D,A,B,C] nhưng xích
0
720
1764
1624
735
175
21
1
7
[A,B,C,D] lại khác với [A,B,D,C] hay [D,C,B,A]. Và ta có 11
8
0
5040
13068
13132
6769
1960
322
28
1
cách chia 4 phần tử thành 2 xích là : [1,2,3][4] ; [1,2,4][3] ;
Định nghĩa số Harmonic : Cho n ,r ˛ N*
2.3 SỐ STIRLING LOẠI 2
n
(r)
nH với
(r) H = n
1 ∑ r k
k=1
2.3.1 Định nghĩa Số Harmonic kí hiệu là : Định nghĩa 2.3.1 : Số phân hợp tập hợp n phần tử thành k khối
không rỗng , gọi là số Stirling loại 2 , kí hiệu S(n,k) .
Tính chất 2.2.2 :
Nói cách khác , số Stirling loại 2 là số cách phân phối n quả
Quan hệ giữa số Stirling loại 1 không dấu và số Harmonic :
bóng phân biệt vào k hộp giống nhau mà không có hộp nào
rỗng .
a) s’(n+1,2) = n!Hn
+....+
2 H -H n
(2) n
2 n
n! 2
n! 2
1 2 2
1 2 n
H - 1+
b) s’(n+1,3) = = 2.3.2 Các ñịnh lý
H -3H H +2H n
(2) n
3 n
(3) n
n! 6
bằng k!S(n,k)
Mệnh ñề 1 : Số toàn ánh từ tập hợp n phần tử vào tập k phần tử c) s’(n+1,4)=
k
i
n
)
(
)(
)
)
thức sau :
(2.3a)
( S n,k =
( -1 C k,i k-i
∑
Tính chất 2.2.3 : Các tính chất trên hàng, cột và ñường chéo Định lý 2.3.1 : Số Stirling loại 2 có thể tính trực tiếp qua công của bảng số Stirling loại 1 không dấu .
1 k!
i=0
n
a) Cho n là số tự nhiên . Khi ñó :
(2.2d)
j.s'(n,j)=s'(n+1,2)
∑
j=0
S(n + 1 ,k) = S(n, k-1) + k S(n, k)
(2.3b)
b) Cho n và c là các số nguyên không âm . Khi ñó :
Định lí 2.3.2 : Cho n và k là số tự nhiên . Ta có : " n ˛ N*
Định lý 2.3.3 : Cho n ˛
N . Số Stirling loại 2 ñược cho bởi
n
n
(
(
(
)
(2.2e)
(2.3c)
công thức :
) ) C j,c .s' n,j =s' n+1,c+1
∑
n x =
)[ ] ( S n,k x
∑
k
j=0
k=0
c) Cho n và c là các số nguyên không âm . Khi ñó :
N* và [x]0 =1
n
N*
)
s’(n+1,c+1) =
" n,c ˛ N
(2.2f)
[ ] n
( .s' k,c
∑
n-k
k=0
Với [x]k = x(x-1)(x-2)...(x-k+1) với k˛ Quy ước : S(n,0) = 0 với " S(0, k) = 0 với "
n ˛ k ˛
N*
d) Cho n và c là các số nguyên không âm . Khi ñó :
S(n, k) = 0 nếu k > n và S(0,0) = 1 .
c
Từ công thức (2.3b) ta xây dựng bảng sau bao gồm một số số
(
)
)
s’(n+c+1,c) =
(2.2g)
( n+k .s' n+k,k
∑
k=0
Stirling loại 2 :
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)
n
n-r
r
a)
(2.3h)
(
[
]
[ ] y
0
1
n )[ ] ∑ x+y = C n,r x r=0
1
0
1
2
0
1
1
(
]
b) [
(2.3i)
[ ] y
n
r
n-r
3
0
1
3
1
n )[ ] ∑ x+y = C n,r x r=0
4
0
1
7
6
1
Bảng 2.3 : Bảng số Stirling loại 2 Định lý 2.3.8 : Với n ˛ N* . Ta có :
5
0
1
15
25
1
10
6
0
1
31
90
15
1
65
(
) (
) (
) (
)
(
)
a)
(2.3j)
∑ C i+j,i s n,i+j = C n,k s k,i s n-k,j
k
7
0
1
63
301
21
1
350
140
8
0
1
127
966
28
1701
1050
266
1
)
(
(
)
(
)
(
)
(
)
b)
(2.3k)
∑ C i+j,i S n,i+j = C n,k S k,i S n-k,j
k
Định lý 2.3.9 :
2.3.3 Các tính chất
+¥
n
)k
x e -1
loại 2 :
, k = 0,1,2,…. , |x|<1
)
)
( S n,k
=
n
( F x = k
∑
n-k
x n!
k!
n=k
(
)
Tính chất 2.3.1 : Cho n và c là các số nguyên không âm . Khi Định lý 2.3.4 : Đẳng thức về hàm sinh lũy thừa cho số Stirling (
S(n+1,c+1) =
(2.3l)
) c+1
( S k,c
∑
k=0
(2.3d)
ñó :
với ri ˛ N* và r1 + r2 + rk = n
∑
c
n! k!
1 r !r !...r ! 1 2 k
)
S(n+c+1,c) =
(2.3m)
( k.S n+k,k
∑
Tính chất 2.3.2 : Cho n và c là các số nguyên không âm . Thì : Hệ quả : S(n,k) =
k
k=0
n
) ( S n,k x =
∑
)(
(
)
x ( ) 1-x 1-2x ... 1-kx
n=k
¥ Định lý 2.3.5 : fk (x) =
2.4 QUAN HỆ GIỮA SỐ STIRLING LOẠI 1 VÀ SỐ
với k = 1,2,…. , |x|<1
(2.3e)
STIRLING LOẠI 2
c
c
1
2
k
Hệ quả : S(n,k) =
với ci ˛ N
c 1 2 ...k
∑
m
c +c +...+c =n-k 1
2
k
)
) ( ( S m,k s k,n =δ
mn
∑
k=n
Định lý 2.4.1 : Cho n , m là các số tự nhiên . Khi ñó :
N ,ta có :
n
Với δ
=
(
(
)
S(n+1,k+1) =
(2.3f)
) C n,r S r,k
Định lý 2.3.6 : Với k ,n ˛
∑
mn
1 khi m = n 0 khi m n
r=k
„
n , ta có :
n-k
n-k
Định lý 2.3.7: Cho n ≥ 1 và 1 £
)
)
k £ (
(2.3g)
k
( S n,k
C n-1,k-1 .k
£ £
2.5 TÍNH CHIA HẾT CHO SỐ NGUYÊN TỐ CỦA
SỐ STIRLING LOẠI 2
CHƯƠNG 3
Định lý 2.5.1 : Nếu p là số nguyên tố thì p | S( p,k) với
ỨNG DỤNG CỦA SỐ STIRLING
2 £
k £
p -1 . Hơn nữa , p ∤S(p,1) và p∤S (p,p) (2.5a)
3.1 Ứng dụng giải một số bài toán tổ hợp
Định lý 2.5.2 : Nếu p là số nguyên tố thì p| S(p+1,k+1) với
k£
p -1 . Hơn nữa , S(p+1,2) ”
1 mod p
(2.5b)
mọi 2£
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ài toán 3.1.1 : Đếm số cách phân phối n vật phân biệt vào m
p –j . Hơn nữa , S(p+j, j+1) ”
1 mod p với
p -2 và 2 £
k £
b) m hộp giống nhau và cho phép có hộp trống .
mọi 2 £
j£
p -2.
(2.5c)
Các hộp ñều phân biệt và mỗi hộp phải có ít nhất một vật
£ Định lý 2.5. 3: Nếu p số nguyên tố thì p | S(p+j,k+j) với mọi 1 j£
tam giác vuông cân có ñộ dài cạnh bên là m sao cho không có
cuộc tấn công nào (nghĩa là 2 quân xe bất kỳ không cùng nằm trên 1 hàng hoặc 1 cột ) là S(m+1, m+1- k) với 1 £
m .
k £
Bài toán 3.1.2 : Chứng minh rằng số cách ñặt k quân xe trên 1
Bài toán 3.1.3 : Chứng minh rằng số cách xếp n người vào k
n
k £
bàn tròn giống hệt nhau sao cho không có bàn nào trống chính là s’(n,k) với s’(n,k) là số Stirling loại 1 không dấu và 1 £
Áp dụng : Có 10 người và 4 cái bàn tròn giống hệt nhau . Hỏi
a) Có 1 bàn trống .
b) Có 2 bàn trống .
có bao nhiêu cách xếp 10 người vào 4 bàn trên sao cho :
a) Tích của 2 số tự nhiên lớn hơn 1.
b) Tích của ba số tự nhiên lớn hơn 1 .
Bài toán 3.1.4 : Có bao nhiêu cách ñể phân tích số 7590 thành
n-w
S(n,k) =
với 0 £
w£
k
(
)
(
)
(
)
C n,r S n-r,w S r,k-w
∑
(
w! ) k
r=k-w
w
Bài toán 3.2.5 : Chứng minh rằng :
3.2. Ứng dụng giải các bài toán giải tích : Bài toán 3.2.1 : Chứng minh rằng với n ˛
N:
(3.2f)
Với (k)w = ( k-w +1) (k-w+2) … k
^ D xD x
d dx
n
a) S(n,n-1) = C(n,2) với n ≥ 2 . b) S(n,2) = 2n-1 – 1 với n ≥ 2 . (
” ” Bài toán 3.2.6 : Đặt . Cho hàm số :
)
c) S(n,3) =
với n ≥3 .
n 3 -3.2 +3
i
1 6
f(n,x) =
¥
∑ với n là số tự nhiên
n i x i!
i=1
d) S(n , n – 2) = C(n,3) + 3C(n,4) với n ≥ 2 .
Khi ñó với r , n ˛
N và x ˛
R. Ta có :
n
n
)
e)
( S n,4 =
n 4 -4.3 +6.2 -4
n
1 24
n
x
r
a)
(3.2g)
^ x D e = e
S(n,r).x
∑
r=1
i
n
n
n-r
b)
(3.2h)
^ x D e =
)
(
)
a)
(3.2a)
S n+1,k =
( k S r,k-1
∑
n i x ∑ i!
i=1
r=k-1
Bài toán 3.2.2 : Với n ˛ N* . Chứng minh rằng : ¥
i
n
n
x
r
(3.2i)
c)
)
(
)
) ( f n,x = e
) ( S n,r .x =
b)
với k £
n
(3.2b)
( S n+1,k =
r.S n+r-k,r
∑
∑
n i x ∑ i!
r=1
i=1
r=k-1
¥
n
¥
3.3 Sử dụng phần mềm Maple ñể tính số Stirling :
)
. Chứng
( S n,k
∑
t n!
n=0
t
Bài toán 3.2.3: Với k ˛ N*, cho Yk (t) = 3.3.1 Sử dụng phần mềm Maple ñể tính số Stirling loại 2 :
kt
-km
(3.2c)
minh rằng : Yk (t) =
e
e Y (m)dm k-1
∫
0
3.3.2 Sử dụng phần mềm Maple ñể tính số Stirling loại 1 :
N* và c = const . Chứng
minh rằng :
m
m-k
n
n
(
)
(
t e +c
kt
a)
(3.2d)
)
( S n,k
=
e
∑
t e +c (
d dt
m!
) ) m-k !
k=0
n
n
)
b)
(3.2e)
=
∑
n n!
( S n,n-k k!
k=0
Bài toán 3.2.4 : Cho m ≥ n ; m , n ˛
Cuối cùng , tôi xin ñược nêu lên một số vấn ñề có thể mở rộng
nghiên cứu tiếp theo về số Stirling trong tương lai ñó là :
KẾT LUẬN
Luận văn ñã trình này một cách có hệ thống tổng quan về lý
(cid:4) Số poly – Stirling .
thuyết tổ hợp , do nội dung chính của luận văn ít liên quan ñến
(cid:4) Số q – stirling loại 2 .
trong chương 1 tôi có trình bày một số khái niệm có mà tôi có
sử dụng trong 2 chương còn lại .
các cấu hình tổ hợp nên tôi chỉ cho một số ví dụ , ngoài ra
Ở chương 2 , tôi ñã ñưa ra ñịnh nghĩa , các tính chất , các ñịnh
chi tiết các ñịnh lý trên . Phương pháp chủ yếu ñể chứng minh
lý , hàm sinh của các số Stirling và chứng minh một cách khá
là phương pháp quy nạp .
Ở chương 3 , tôi ñã nghiên cứu và ñưa ra một số bài toán ứng
2 . Đặc biệt , trong chương này có ñưa ra một số bài toán về
phân hoạch tập hợp và chứng minh bài toán xếp vị trí cho n
người vào k bàn tròn .
Kết quả của luận văn nhằm nâng cao chất lượng dạy và học
dụng ña dạng cho những lý thuyết ñã ñược trình bày ở chương
tư duy toán học cho học sinh phổ thông và ñặc biệt là học sinh
chuyên toán có một tư liệu tham khảo bổ ích , bởi vì tổ hợp
toán tổ hợp nói riêng và toán rời rạc nói chung, nhằm phát triển
ñược xem là môn học khó cho học sinh ở cấp học này .
