Luận văn Thạc sĩ Toán học: Về một vài loại số đặc biệt

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:64

Thêm vào BST

Báo xấu

21
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Về một vài loại số đặc biệt

ĐẠ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 =   Tổ hợp chập k của n k   n   Số Stirling loại 1 k   n Số Stirling loại 2 k  * + n 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: nguyencongcon@gmail.com
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 k!.(n − 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(n − 1) . . . (n − k + 1) n!  = = . k k! k!.(n − 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) k n−k Chứng minh. Theo định lý 1.1.1, ta có     n n! (n − k)! n  = = = . k k!(n − k)! (n − (n − k))! n−k         n n n n Đặc biệt   =   = 1 và   =   = n. 0 n 1 n−1 Định lí 1.2.2. Công thức truy hồi       n n−1 n−1  = + , n, k > 0. (1.3) k k−1 k Chứng minh. Ta có     n−1 n−1 (n − 1)! (n − 1)!  + = + k−1 k (n − k)!(k − 1)! (n − k − 1)!k! (n − 1)!k (n − 1)!(n − k) = + (n − k)!k! (n − k)!k! (n − 1)![k + (n − k)] = (n − k)!k! (n − 1)!n n! = = (n − k)!k! (n − k)!k!   n =  . k Định lý được chứng minh.
4 Định lí 1.2.3 (Định lý nhị thức).   n Xn (x + y)n =   xn−k y k . (1.4) k=0 k 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à   n−1 X n−1 (x + y)n−1 =   xn−1−k y k . k=0 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 = (x + y)   xn−1−k y k k=0 k     n−1 X n−1 n−1 X n−1 =x   xn−1−k y k + y   xn−1−k y k k=0 k k=0 k     n−1 n−1 X n−1 n−k k X n−1 =  x y +   xn−1−k y k+1 k=0 k k=0 k     n−1 X n−1 n X n−1 =   xn−k y k +   xn−k y k k=0 k k=1 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 k k−1 n−1 k=1
5   n−1 n − 1 n X n k k n−1 n = x + x y + y 0 k n − 1 k=1   n−1 n n X n n−k k n n = x + x y + y 0 k n k=1   n X n =   xn−k y k . k=0 k n Sau đây là bảng các giá trị của với 0 ≤ k, n ≤ 10 và được gọi là tam k 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 1 Bảng 1.1: Tam giác Pascal.
6 Hệ quả 1.2.1.   n X n   = 2n . (1.5) k=0 k Chứng minh. Theo (1.4) với x = y = 1. Hệ quả 1.2.2.   n X n (−1)k   = 0. (1.6) k=0 k 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 n−1 k  = n . (1.7) k k−1 Chứng minh. Ta có     n n! (n − 1)! n−1 k  = k =n = n . k k!(n − k)! (k − 1)!(n − k)! k−1 Định lí 1.2.5. Với 0 ≤ k ≤ m ≤ n, ta có       n m n n−k    =   . (1.8) m k k m−k Chứng minh. Ta có    n m n! m!    = . m k m!(n − m)! k!(m − k)! n! = k!(n − m)!(m − k)!
7 n! (n − k)! = . k!(n − k)! (n − m)!(m − k)!    n n−k =   . k m−k Định lí 1.2.6.     n X k n+1  = . (1.9) k=0 c c+1 Chứng minh. Với n = 0 dễ thấy định lý đúng. Giả sử với n ≥ 1 thì     n−1 X k n  = . k=0 c c+1 Khi đó       n n−1 X k X k n  =  +  k=0 c k=0 c c     n n = +  c+1 c   n+1 = . c+1 Định lí 1.2.7.     n X r+k r+n+1  = . (1.10) k=0 k n Chứng minh. Ta có     n n X r+k X r+k  =   (theo 1.2) k=0 k k=0 r
8   r+n+1 =  (theo 1.9) r+1   r+n+1 =  (theo 1.2). n Đị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 = . (1.11) k r−n r 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 2n = . k n k=0 Chứng minh. Theo (1.2) và (1.11), ta có n 2 n X n X n n 2n = = . k k n−k n k=0 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 Quy ước: = 0 với mọi n ∈ N∗ ; 0   0 = 0 với mọi k ∈ N∗ ; k      n 0 = 0 nếu k > n và = 1. k  0 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, ∪ {3, 4} {1, 3} ∪ {2, 4} {1, 4} ∪ {2, 3}. 2}  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 + . (2.1) k   k  k − 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  tập con  nữa n − 1 có đúng một phần tử {n} để nhận được k tập con. Ta sẽ có cách k − 1 phân hoạch kiểu này. Vì vậy       n n − 1 n − 1 =k + . k   k  k − 1 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 Chứng minh. Với n = 2 ta có = 1 = 2 − 1. Vậy 1 = 21 − 1 2 2 (đúng).
11                   n  n   n   n   n   n   n   n   n    n 0  1   2   3   4   5   6   7   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 Bảng 2.1: Bảng số Stirling loại 2.   k  Giả sử đẳng thức đúng với n = k > 2, tức là = 2k−1 − 1, ta chứng 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:   n 1X k 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ó   4 1X 2 2 4 = i (−1)2−i 2 2! i j=0 1h2 2 4 2 4 i 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 + 1 X n   n k = . . (2.4) m + 1 k m k=0
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 + 1 n + 1 X n   n k = = .  2  1 + 1 k 1 k=1 n X n = = 2n − 1. k k=1 b) Ta có     5 X 4   4 k = . 3 k 2 k=2       2 3 4       4 4 4 = . + . + . 2 2 3 2 4 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 + 1 X n k = (m + 1) n−k . (2.5) m + 1 m 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  X n−1 k n−k−1 = (m + 1) m + 1 m k=0 Khi đó ta có       n + 1 n  n  = + (m + 1) m + 1 m m + 1
14     n n−1 X k = + (m + 1) (m + 1)n−k−1 m m k=0     n X n−1 k n−k = + (m + 1) m m k=0   Xn k n−k = (m + 1) . m k=0 Định lý được chứng minh. Ví dụ 2.1.4. Ta có     5 X 4 k  4−k = 3 . 3 2 k=2       2 3 4 4−2 4−3 4−4 =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ó     n + m + 1 X m n + m = k . (2.6)  m  k=0  m  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  n + m n + m = +m  m  m − 1  m 
15     m−1 X n + k  n + m = k +m  k   m  k=0   m X n + 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),  (143)(2),  (243)(1), (12)(34), (13)(24), (14)(23). 4 Vậy   = 11. 2