..
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN CÔNG CÒN
VỀ MỘT VÀI LOẠI SỐ ĐẶC BIỆT
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - 2015
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN CÔNG CÒN
VỀ MỘT VÀI LOẠI SỐ ĐẶC BIỆT
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số:
60 46 01 13
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. NÔNG QUỐC CHINH
Thái Nguyên - 2015
i
Mục lục
Mục lục
i
Lời cảm ơn
ii
Một số ký hiệu
iii
Mở đầu
1
1
Kiến thức chuẩn bị
2
1.1
Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . . . . .
2
1.2
Một số tính chất . . . . . . . . . . . . . . . . . . . . . . . .
3
2
Một vài loại số đặc biệt
9
2.1
Số Stirling . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2
Số Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.3
Số Harmonic . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.4
Số Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . .
41
2.5
Ứng dụng trong toán phổ thông . . . . . . . . . . . . . . . .
51
2.5.1
Ứng dụng của số Fibonacci . . . . . . . . . . . . . .
51
2.5.2
Ứng dụng của số Stirling . . . . . . . . . . . . . . .
53
Kết luận
58
Tài liệu tham khảo
59
ii
Lời cảm ơn
Luận văn này được hoàn thành tại trường Đại học Khoa học - Đại học
Thái Nguyên. Tác giả xin bày tỏ lòng biết ơn sâu sắc với PGS.TS. Nông Quốc
Chinh, đã trực tiếp hướng dẫn tận tình và động viên tác giả trong suốt thời
gian nghiên cứu vừa qua.
Xin chân thành cảm ơn tới các thầy, cô giáo trong Khoa Toán - Tin, Phòng
Đào tạo, các bạn học viên lớp Cao học Toán K7D trường Đại học Khoa học
- Đại học Thái Nguyên, và các bạn đồng nghiệp đã tạo điều kiện thuận lợi,
động viên tác giả trong quá trình học tập và nghiên cứu tại trường.
Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người thân
luôn khuyến khích, động viên tác giả trong suốt quá trình học tập và làm luận
văn.
Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót
và hạn chế. Tác giả mong nhận được những ý kiến đóng góp quý báu của các
thầy cô và bạn đọc để luận văn được hoàn thiện hơn.
Thái Nguyên, 2015
Nguyễn Công Còn
Học viên Cao học Toán K7D,
Trường ĐH Khoa học - ĐH Thái Nguyên
iii
Một số ký hiệu
n
Ckn =
k
n
k
n
k
* +
n
Tổ hợp chập k của n
Số Stirling loại 1
Số Stirling loại 2
Số Euler bậc 1
k
* +(2)
n
Số Euler bậc 2
k
Hn
Số Harmonic thứ n
Fn
Số Fibonacci thứ n
1
Mở đầu
Số học luôn được mệnh danh là nữ hoàng của toán học, bởi trong nó chứa
đựng nhiều vẻ đẹp của tư duy logic. Việc nghiên cứu các loại số có tính chất
đặc biệt như số nguyên tố, số Bernoulli, số Hoàn hảo, .v.v. . . luôn là một đề
tài hấp dẫn đối với những người yêu toán xưa và nay. Mục tiêu của luận văn
này là trình bày một số kết quả về một vài số đặc biệt đó là số Stirling, số
Euler, số Harmonic, số Fibonacci và một vài ứng dụng của chúng trong toán
phổ thông.
Luận văn được trình bày thành 2 chương chính với nội dung cụ thể là:
Chương 1 trình bày các kiến thức cơ bản có liên quan cần sử dụng cho
chương 2.
Chương 2 trình bày các khái niệm, tính chất, định lý, hệ quả về các số
Stirling, Euler, Harmonic, Fibonacci và một số công thức biểu thị mối quan
hệ giữa các số đó, ứng dụng của chúng trong toán phổ thông. Sau một thời
gian nghiên cứu luận văn đã được hoàn thành.
Mặc dù tác giả đã hết sức cố gắng, tuy nhiên luận văn vẫn không tránh
khỏi những sai sót, tác giả xin tiếp thu các ý kiến góp ý của các thầy cô giáo
và các bạn đồng nghiệp. Chúng tôi xin chân thành cảm ơn.
Thái Nguyên, ngày 20 tháng 11 năm 2015
Nguyễn Công Còn
Email:
[email protected]
2
Chương 1
Kiến thức chuẩn bị
1.1
Định nghĩa và ví dụ
n
Định nghĩa 1.1.1. Số tập con có k phần tử của tập n phần tử, kí hiệu
k
và được gọi là tổ hợp chập k của n.
Ví dụ 1.1.1. Có 6 tập con có 2 phần tử của tập {1, 2, 3, 4} đó là
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.
4
Do vậy = 6.
2
Định lí 1.1.1. Cho n, k là các số nguyên dương và 0 ≤ k ≤ n. Khi đó
n!
n
=
.
(1.1)
k!.(n
−
k)!
k
Chứng minh. Đầu tiên, tính số dãy có k phần tử: có n cách chọn phần tử thứ
nhất, có n − 1 cách chọn phần tử thứ hai, ..., có n − k + 1 cách chọn phần tử
thứ k. Do vậy có tất cả n(n − 1) . . . (n − k + 1) cách chọn. Vì mỗi tập con có
k phần tử có k! cách sắp thứ tự khác nhau. Do đó
n(n − 1) . . . (n − k + 1)
n!
n
=
=
.
k!
k!.(n
−
k)!
k
3
1.2
Một số tính chất
Định lí 1.2.1. Cho n và k là các số nguyên bất kì sao cho 0 ≤ k ≤ n. Khi đó
n
n
.
=
(1.2)
n−k
k
Chứng minh. Theo định lý 1.1.1, ta có
n!
(n − k)!
n
n
=
.
=
=
k!(n
−
k)!
(n
−
(n
−
k))!
k
n−k
n
n
n
n
= n.
Đặc biệt = = 1 và =
0
n
1
n−1
Định lí 1.2.2. Công thức truy hồi
n−1
n−1
n
,
+
=
k
k−1
k
n, k > 0.
Chứng minh. Ta có
(n − 1)!
(n − 1)!
n−1
n−1
=
+
+
(n − k)!(k − 1)! (n − k − 1)!k!
k
k−1
(n − 1)!k
=
(n − k)!k!
(n − 1)!(n − k)
+
(n − k)!k!
(n − 1)![k + (n − k)]
=
(n − k)!k!
(n − 1)!n
=
(n − k)!k!
n
= .
k
Định lý được chứng minh.
n!
=
(n − k)!k!
(1.3)
4
Định lí 1.2.3 (Định lý nhị thức).
n
xn−k y k .
(x + y)n =
k
k=0
n
X
(1.4)
Chứng minh. Chứng minh bằng quy nạp trên n. Dễ dàng kiểm tra định lý
đúng với n = 0, 1, 2.
Giả sử định lý đúng với n − 1, tức là
(x + y)n−1 =
n−1
X
k=0
n−1
k
xn−1−k y k .
Từ giả thiết quy nạp và (1.3), ta có
(x + y)n = (x + y)(x + y)n−1
n−1
X n−1
xn−1−k y k
= (x + y)
k
k=0
n−1
n−1
X n−1
X n−1
xn−1−k y k
xn−1−k y k + y
=x
k
k
k=0
k=0
n−1
n−1
X
X
n−1
n−1
n−k
k
xn−1−k y k+1
x y +
=
k
k
k=0
k=0
n−1
n
X n−1
X n−1
xn−k y k +
xn−k y k
=
k
k−1
k=0
k=1
n−1
n
n − 1 n X n − 1 n−k k X n − 1 n−k k
=
x +
x y +
x y
0
k
k−1
k=1
k=1
n−1 n
+
y
n−1
n−1
n − 1 n X n − 1 n − 1 n−k k
n−1 n
=
x +
+
x y +
y
0
n−1
k
k−1
k=1
5
n−1
n−1 n
n − 1 n X n k k
x y +
=
y
x +
n
−
1
0
k
k=1
n−1
n n
n n X n n−k k
x y +
y
=
x +
n
0
k
k=1
n
X
n
xn−k y k .
=
k
k=0
Sau đây là bảng các giá trị của
n
k
với 0 ≤ k, n ≤ 10 và được gọi là tam
giác Pascal.
n n n n n n n n n
n
0
1
2
3
4
5
6
7
8
0 1
1 1
1
2 1
2
1
3 1
3
3
1
4 1
4
6
4
1
5 1
5
10
10
5
1
6 1
6
15
20
15
6
1
7 1
7
21
35
35
21
21
1
8 1
8
28
56
70
56
28
8
Bảng 1.1: Tam giác Pascal.
1
6
Hệ quả 1.2.1.
n
= 2n .
k
k=0
n
X
(1.5)
Chứng minh. Theo (1.4) với x = y = 1.
Hệ quả 1.2.2.
n
(−1)k = 0.
k
k=0
n
X
(1.6)
Chứng minh. Theo (1.4) với x = 1 và y = −1.
Định lí 1.2.4. Với 0 ≤ k ≤ n, ta có
n−1
n
.
k = n
k−1
k
(1.7)
Chứng minh. Ta có
n!
(n
−
1)!
n
n−1
.
k = k
=n
= n
k!(n
−
k)!
(k
−
1)!(n
−
k)!
k
k−1
Định lí 1.2.5. Với 0 ≤ k ≤ m ≤ n, ta có
n
m
n
n−k
=
.
m
k
k
m−k
Chứng minh. Ta có
m!
n!
n
m
=
.
m!(n − m)! k!(m − k)!
m
k
n!
=
k!(n − m)!(m − k)!
(1.8)
7
(n − k)!
n!
=
.
k!(n − k)! (n − m)!(m − k)!
n−k
n
.
=
m−k
k
Định lí 1.2.6.
n+1
k
.
=
c+1
c
k=0
n
X
(1.9)
Chứng minh. Với n = 0 dễ thấy định lý đúng.
Giả sử với n ≥ 1 thì
n
k
.
=
c+1
c
k=0
n−1
X
Khi đó
n−1
X k
n
k
+
=
c
c
c
k=0
k=0
n
n
+
=
c
c+1
n+1
.
=
c+1
n
X
Định lí 1.2.7.
n
X
r+k
k=0
k
=
r+n+1
n
.
Chứng minh. Ta có
n
X
k=0
r+k
k
=
n
X
k=0
r+k
r
(theo 1.2)
(1.10)
8
=
=
r+n+1
r+1
r+n+1
n
(theo 1.9)
(theo 1.2).
Định lí 1.2.8 (Đẳng thức Vandermonde). Cho m, n và r là các số nguyên
không âm sao cho r ≤ m và r ≤ n. Khi đó
r
X
m
n
m+n
=
.
k
r−n
r
(1.11)
k=0
Chứng minh. Phân hoạch tập S gồm m + n phần tử thành hai tập con T có
m phần tử và tập U có n phần tử. Chọn r phần tử từ S, k phần tử tử T và còn
lại phần tử từ U .
Định lí 1.2.9.
n 2
X
n
k=0
k
2n
=
.
n
Chứng minh. Theo (1.2) và (1.11), ta có
n 2
X
n
k=0
k
n
X
n
n
2n
=
=
.
k
n−k
n
k=0
9
Chương 2
Một vài loại số đặc biệt
2.1
Số Stirling
Định nghĩa 2.1.1. Số phân hoạch một tập hợp
có
n phần tử thành k tập con
n
.
khác rỗng gọi là số Stirling loại 2 và kí hiệu là
k
n
= 0 với mọi n ∈ N∗ ;
Quy ước:
0
0
= 0 với mọi k ∈ N∗ ;
k
0
n
= 1.
= 0 nếu k > n và
0
k
Ví dụ 2.1.1. Có 7 cách phân hoạch một tập có 4 phần tử {1, 2, 3, 4} thành 2
tập con khác rỗng, đó là
{1, 2, 3} ∪ {4} {1, 2, 4} ∪ {3} {1, 3, 4} ∪ {2} {2, 3, 4} ∪ {1}
{1,
2}
∪ {3, 4} {1, 3} ∪ {2, 4} {1, 4} ∪ {2, 3}.
4
Do đó
= 7.
2
10
Mệnh đề 2.1.1. Cho n, k là các số nguyên dương. Khi đó
n
n − 1 n − 1
=k
+
.
k
k k − 1
(2.1)
Chứng minh. Kí hiệu [n] là tập gồm n phần tử.
Vì mỗi cách phân hoạch [n] thành k tập con khác rỗng có thể ta thu được từ
một phân hoạch [n − 1] thành k tập con khác rỗng, sau đó bổ sung phần tử n
vào một trong k tập con khác rỗng đó.
Với mỗi cách chia tập [n − 1] thành k tập con khác rỗng,
ta có
k cách bổ
n − 1
sung phần tử thứ n vào một trong k tập con đó, nên ta có
cách phân
k
hoạch. Mặt khác ta có thể chia tập [n] thành k tập con khác rỗng bằng cách
chia tập [n − 1] thành (k − 1) tập con, sau đó bổ sung thêm một
nữa
tập con
n − 1
cách
có đúng một phần tử {n} để nhận được k tập con. Ta sẽ có
k − 1
phân hoạch kiểu này. Vì vậy
n − 1 n − 1
n
.
+
=k
k k − 1
k
Từ công thức (2.1) của mệnh đề 2.1.1 ta nhận được tam giác số Stirling
loại 2 như sau:
Định lí 2.1.1. Với mọi số nguyên n ≥ 2, ta có
n
= 2n−1 − 1.
2
2
(2.2)
2
1
Chứng minh. Với n = 2 ta có
= 1 = 2 − 1. Vậy
= 21 − 1
2
2
(đúng).
11
n
n
n
n
n
n
n
n
n
n
8
7
6
5
4
3
2
1
0
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
Bảng 2.1: Bảng số Stirling loại 2.
k
= 2k−1 − 1, ta chứng
Giả sử đẳng thức đúng với n = k > 2, tức là
2
minh đẳng thức đúng với n = k + 1, thật vậy:
k + 1 k
k
=
+2
2 1
2
= 1 + 2(2k−1 − 1)
= 1 + 2k − 2 = 2(k+1)−1 − 1.
Vậy bài toán được chứng minh.
4
Trở lại định lý 2.1.1, ta thấy
= 24−1 − 1 = 7.
2
12
Định lí 2.1.2. Số Stirling loại 2 có thể tính trực tiếp qua công thức sau:
k
n
1X
k n
(−1)k−i
=
i .
(2.3)
k k!
i
i=0
Chứng minh. Gọi N và K là hai tập hợp với |N | = n, |K| = k, H là tập con
của K và f (H) là số ánh xạ từ N tới K\H.
Thay i = k − j, ta có
n
k!.
= {f : N → K|f là toàn ánh}
k
X
=
(−1)|H| f (H)
H⊆K
=
k
X
(−1)j Cjk (k − j)n
j=0
=
k
X
(−1)k−i Cjk (i)n .
i=0
Ví dụ 2.1.2. Ta có
2
4
1X
2 4
i (−1)2−i
=
2 2!
i
j=0
i
1h2
2 4
2 4
4
2−0
2−1
2−2
=
0 (−1) +
1 (−1) +
2 (−1)
2 0
1
2
1
= [1.0.1 + 2.1.(−1) + 1.16.1] = 7.
2
Định lí 2.1.3. Cho n và m là các số nguyên không âm. Ta có
n
n + 1 X
k
n
=
.
.
m + 1
k m
k=0
(2.4)
13
Chứng minh. Phân hoạch n + 1 số nguyên 1, . . . , n + 1 thành m + 1 tập
con,
k
n
ta có k cách chọn n − k số nguyên khác nhau thành một tập con và
m
cách phân hoạch k số còn lại thành m tập con. Vậy ta có đẳng thức cần chứng
minh.
Ví dụ 2.1.3. a) Ta có
n
n + 1 n + 1 X
k
n
=
=
.
2 1 + 1
k 1
k=1
n
X
n
=
= 2n − 1.
k
k=1
b) Ta có
4
5 X
k
4
=
.
3
k 2
k=2
4
3
2
4
4
4
+
.
+
.
=
.
4 2
3 2
2 2
= 6.1 + 4.3 + 1.7 = 25.
Định lí 2.1.4. Cho n và m là các số nguyên không âm. Ta có
n
n + 1 X
k
n−k
.
=
(m + 1)
m
m + 1
(2.5)
k=0
Chứng minh. Ta chứng minh bằng quy nạp. Công thức trên hiển nhiên đúng
khi n = 0. Giả sử
n−1
n X
k
n−k−1
=
(m + 1)
m
m + 1
k=0
Khi đó ta có
n + 1
n
n
=
+ (m + 1)
m + 1 m
m + 1
14
n
n−1
X
k
(m + 1)n−k−1
+ (m + 1)
m
m
k=0
n−1
k
n X
n−k
(m + 1)
=
+
m
m
k=0
n
k
X
n−k
(m + 1)
.
=
m
=
k=0
Định lý được chứng minh.
Ví dụ 2.1.4. Ta có
4
5 X
k
4−k
=
3 .
2
3
k=2
4
3
2
4−4
4−3
4−2
+3 .
+3 .
=3 .
2
2
2
= 32 .1 + 31 .3 + 30 .7 = 25.
Định lí 2.1.5. Cho n và m là các số nguyên không âm. Ta có
m
n + m
n + m + 1 X
.
=
k
m
m
(2.6)
k=0
Chứng minh. Chứng minh bằng quy nạp. Công thức hiển nhiên đúng với
n ≥ 0 khi m = 0.
Giả sử
n + m m−1
X
n + m
=
k
, ∀n ≥ 0.
m − 1
m
k=0
Khi đó, ta có
n + m + 1
m
n + m
n + m
=
+m
m − 1
m
15
m−1
X
n + k
n + m
+m
m
k
k=0
m
X
n + k
k
.
=
k
=
k
k=0
Định lý được chứng minh.
Tiếp theo ta tìm hiểu về số Stirling loại 1. Trước hết ta định nghĩa về chu
trình:
Chu trình là một hoán vị vòng tròn, giống như dây chuyền. Chu trình
có thể viết như [A, B, C, D] với cách hiểu là
[A, B, C, D] = [B, C, D, A] = [C, D, A, B] = [D, A, B, C].
Mặt khác, chu trình [A, B, C, D] khác [A, B, D, C] hoặc [D, C, B, A].
Định nghĩa 2.1.2. Cho
n và k là các số nguyên khác không, n ≤ k. Số
n
Stirling loại 1 ký hiệu là số cách sắp xếp (số hoán vị) n phần tử thành k
k
chu trình khác nhau.
Ví dụ 2.1.5. * Tập X = {1, 2, 3, 4} có thể sắp xếp thành 2 chu trình như sau:
(123)(4), (124)(3), (134)(2), (234)(1), (132)(4), (142)(3),
(243)(1), (12)(34), (13)(24), (14)(23).
(143)(2),
4
Vậy = 11.
2
.PDF 
64 
1 
136 
