Luận Văn Số Stirling Và ứng Dụng

Có thể bạn quan tâm

Đăng ký
Đăng nhập
Liên hệ

Luận văn, đồ án, đề tài, tiểu luận, luận án

Cộng đồng chia sẻ luận văn, đồ án, tiểu luận, đề tài tham khảo cho các bạn học sinh, sinh viên

Trang Chủ
Tài Liệu
Upload

Luận văn Số stirling và ứng dụng

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 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 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.1.2 : Chứng minh rằng số cách ñặt k quân xe trên 1 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 ≤ k ≤ m . Bài toán 3.1.3 : Chứng minh rằng số cách xếp n người vào 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 ≤ k ≤ n Áp dụng : Có 10 người và 4 cái bàn tròn giống hệt nhau . Hỏi có bao nhiêu cách xếp 10 người vào 4 bàn trên sao cho : a) Có 1 bàn trống . b) Có 2 bàn trống . Bài toán 3.1.4 : Có bao nhiêu cách ñể phân tích số 7590 thành 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

11 trang | Chia sẻ: ngoctoan84 | Lượt xem: 1681 | Lượt tải: 0

Bạn đang xem nội dung tài liệu Luận văn Số stirling và ứng dụng, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ĐẶNG THỊ NGUYỄN VIỆT SỐ STIRLING VÀ ỨNG DỤNG Chuyên ngành : PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số : 60.46.40 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 Đà Nẵng - Năm 2012 Công trình ñược hoà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 : Phản biện 2 :. 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ăm2012.. 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 truờng Đại học sư phạm , Đại học Đà Nẵng A. MỞ ĐẦU 1. LÝ DO CHỌN ĐỀ TÀI : Năm 1730 , cuốn sách quan trọng nhất của James Sitirling (1692 – 1770 ) ñã ñược xuất bản , “ Methodus differentialis , sive Tractatus de Summatine et Interpolatione Serireum Infinitarum ” . Trong cuốn sách này ông ñã chỉ ra cách tăng nhanh ñộ hội tụ của một dãy số và các biến ñổi nói chung của các dãy số này với mục ñích tăng tốc ñộ hội tụ . Điều này thường kéo theo sự biến ñổi của các giai thừa sang lũy thừa và ngược lại và ông ấy ñã viết lên bảng ñể thực hiện ý ñịnh này . Những con số trong bảng ñược gọi là số Stirling . Có hai loại số Stirling là số Stirling loại một và số Stirling loại hai. Trong luận văn này chúng ta chủ yếu nghiên cứu về số Stirling 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 toán học . Số Stirling loại hai ñã xuất hiện trong nhiều bài toán tổ hợp và có ứng dụng trong lý thuyết thống kê. 2. MỤC ĐÍCH NGHIÊN CỨU Trên cơ sở nghiên cứu ñề tài , tôi muốn giới thiệu ñến ñộc giả nguồn gốc và các ứng dụng của số Stirling . Từ ñó, ñộc giả có thể hiểu hơn rõ hơn số Stirling , nắm bắt những ứng dụng của nó ñể có thể vận dụng vào các bài toán . Mục ñích của luận văn này là nghiên cứu thêm các ứng dụng của số Stirling và áp dụng nó vào một số lĩnh vực khác của Toán học . 3. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU Đối tượng : Số Stirling loại 1 và số Stirling loại 2 và các ứng dụng của nó . Phạm vi nghiên cứu : Để thực hiện ñề tài này tôi sẽ tiến hành 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 cuốn sách ñề cập ñến số Stirling . 4. PHƯƠNG PHÁP NGHIÊN CỨU 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 , của các ñồng nghiệp cũng như từ các học viên trong lớp . 5. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI : Việc sử dụng số Stirling loại một , số Stirling loại một không dấu và số Stirling loại hai sẽ giải ñược một số bài toán tổ hợp và một số bài toán giải tích một cách ñơn giản hơn . 6. CẤU TRÚC CỦA LUẬN VĂN Luận văn ñược cấu trúc bởi 3 chương . Chương 1 : Tổng quan về tổ hợp Chương này tôi giới thiệu sơ lược về lịch sử tổ hợp và nê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ợ có liên quan ñến luận văn Chương 2 : Số Stirling Chương này nêu ñầy ñủ một cách có hệ thống ñịnh nghĩa về số Stirling loại một , số Stirling loại một không dấu và số Stirling loại hai . Các ñịnh lý , tính chất , hàm sinh của các số Stirling và quan hệ giữa chúng . Chương 3 : Ứng dụng của số Stirling 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 dụng của số Stirling ñể giải các bài toán giải tích . B. NỘI DUNG 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. |A1 ∪ A2 ∪...∪ Ak| = |A1| + |A2| + ... + |Ak|. (1.1a) 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ừ Cho A1, A2 là hai tập hữu hạn, khi ñó : |A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2|. (1.1b) và bằng quy nạp, với k tập hữu hạn A1, A2, ..., Ak ta có: |A1 ∪ A2 ∪ ... ∪ Ak| = N1 − N2 + N3 − ... + (−1)k-1Nk (1.1d) trong ñó Nm (1 ≤ m ≤ k) là tổng phần tử của tất cả các giao m tập lấy từ k tập ñã cho, nghĩa là : Nm = |...| ...1 21 21 m m i kiii ii AAA ∩∩∩∑ ≤<<<≤ Định lý ( Công thức Sieve) : Nếu A1 , A2 ,, Am là những tập con của một tập hữu hạn X . iA là ký hiệu phần bù của Ai trong tập X với i = 1 , 2,, m thì : ( ) m1 2 1 2 mA A ... A =|X|-S +S -...+ -1 Sm∩ ∩ ∩ (1.1e) Trong ñó Sk là ký hiệu của tổng các lực lượng của tất cả những k- bộ giao nhau ñược tạo ra từ m tập hợp ở trên . S1 = |A1| + |A2| + + |Am| ; S2 = ____ i j i,j=1,m i j A A ≠ ∩∑ , Định lý : Với kí hiệu giống ñịnh lí trên |A1 ∪A2 ∪∪Am| = S1 – S2 + + ( -1)m-1 Sm 1.2 CÁC CẤU HÌNH TỔ HỢP CƠ BẢN 1.2.1 Hoán vị Định nghĩa 1.2.1 : 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ử ñó . 1.2.2 Hoán vị lặp Định nghĩa 1.2.2 : Hoán vị lặp là hoán vị trong ñó mỗi phần tử ñược ấn ñịnh một số lần lặp lại cho trước . 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 : ( )1 2 k 1 2 k n!P n,n ,n ,...,n n !.n !....n ! = . 1.2.3 Chỉnh hợp lặp Đị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 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 1.2.4 Chỉnh hợp không lặp Đị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ừ n phần tử ñã cho . Các thành phần không ñược lặp lại . Số tất cả các chỉnh hợp không lặp của n phần tử : A(n,k) = n(n-1)(n-k+1) = ( ) n! n-k ! 1.2.5 Tổ hợp Đị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 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ó 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.2.6 Tổ hợp lặp Định nghĩa 1.2.6 : Tổ hợ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ể 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 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) 1.2.7 Nhị thức Newton : Công thức nhị thức Newton ( ) ( )nn n-k k k=0 a+b = C n,k a b∑ 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 : Định lý l.1 ( Khai triển lũy thừa của 1 hàm ) : Cho hàm f khả vi vô hạn lần trên R . Khi ñó : ( ) ( )20 00 0 0f'(x ) f''(x )f(x) = f(x )+ x-x + x-x +...1! 2! Định nghĩa 1.2.7 ( Ma trận chuyển cơ sở ) Giả sử B = { e1, e2 , , en} , B’ = { e’1, e’2 , , e’n} là hai cơ sở của không gian vectơ V . Ma trận của hệ vectơ B’ trong cơ sở B ñược gọi là ma trận chuyển từ cơ sở B sang cơ sở B’ nếu : n _____ j ij i i=1 e' = t e , j = 1,n∑ thì P = [ tij ] là ma trận chuyển từ cơ sở B sang B’ . (1.1f) Định nghĩa 1.2.8 ( Ma trận nghịch ñảo ) : Ma trận vuông A ñược gọi là khả nghịch nếu tồn tại ma trận cùng cấp B sao cho 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) CHƯƠNG 2 SỐ STIRLING 2.1 SỐ STIRLING LOẠI 1 2.1.1 Định nghĩa Định nghĩa 2.1.1 : Cho n ∈ N , k ∈ N . Số Stirling loại một kí hiệu là s(n, k) ñược cho bởi công thức : [ ] ( )n k n k=0 x = s n,k x∑ (2.1a) Với [x]n = x(x-1)(x-2)...(x-n+1) với n ∈ N* và [x]0 = 1 với n ∈ N* và [x]0 = 1 (2.1b) Quy ước : s(n,0) = 0 với ∀ n∈N* s(0, k ) = 0 với ∀ k∈N* s(n, k) = 0 nếu k >n và s(0,0) = 1 2.1.2 Các ñịnh lý Định lí 2.1.1 : Cho n ∈ N , k ∈ N , ta có : s(n+1, k) = s(n, k-1) - n s(n,k) (2.1c) Ví dụ 2.1.2 : Cho n ∈ N . Chứng minh : a) s(n,n) = 1 b) s(n,1) = (-1)n-1 (n-1)! ∀n ∈ N* c) s(n,n-1) = - C(n,2) d) ( )n k=0 s n,k =0∑ Từ công thức (2.1c) ta có bảng số Stirling loại 1 như sau : Bảng 2.1 : Bảng số Stirling loại 1 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 2 3 4 5 6 7 8 1 0 0 0 0 0 0 0 0 1 -1 2 -6 24 -120 720 -5040 1 -3 11 -50 274 -1764 13068 1 - 6 35 -225 1624 -13132 1 -10 85 -735 6769 1 -15 175 -1960 1 -21 322 1 -28 1 Định lý 2.1.2 : Đẳng thức về hàm sinh lũy thừa cho số Stirling loại 1 : ( ) ( ) n k n k 1 s n,k = ln 1+y n! k! y ≥   ∑ (2.1d) 2.2 SỐ STIRLING LOẠI MỘT KHÔNG DẤU 2.2.1 Các ñịnh nghĩa Định nghĩa 2.2.1 : Giá trị tuyệt ñối của s(n,k) ñược gọi là số Stirling loại 1 không dấu và ñược kí hiệu là s’(n,k) với s’(n,k) = | s(n,k)| . Ngoài ra s’(n,k) còn tượng trưng cho số cách xếp n ñồ vật vào k xích .Xích là một cách sắp xếp trên vòng tròn . Hai xích là giống nhau nếu có thể chặt xích ở vị trí nào ñó và căng ra ta thu ñược 2 tập có thứ tự giống nhau . Với xích [A,B,C,D] ta có : [A,B,C,D] = [B,C,D,A] = [C,D,A,B] = [D,A,B,C] nhưng xích [A,B,C,D] lại khác với [A,B,D,C] hay [D,C,B,A]. Và ta có 11 cách chia 4 phần tử thành 2 xích là : [1,2,3][4] ; [1,2,4][3] ; [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 , k ∈ N . Số Stirling loại một không dấu kí hiệu là s’(n, k) ñược cho bởi công thức : [ ] ( )n k k=0 x = s' n,k x n ∑ (2.2a) Với [x]n = x(x+1)(x+2)...(x+n-1) với n ∈ N* và [x]0 = 1 (2.2b) Quy ước : s’(n,0) = 0 với ∀ n∈N* s’(0, k) = 0 với ∀ k∈N* s’(n, k) = 0 nếu k >n và s’(0,0) = 1 2.2.2 Các tính chất : 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 c) ( ) 0 s' n,k =n! n k= ∑ với n ∈N Từ các công thức trên ta xây dựng tam giác của số Stirling loại 1 không dấu Bảng 2.2 : Bảng số Stirling loại 1 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) s’(n,8) 0 1 2 3 4 5 6 7 8 1 0 0 0 0 0 0 0 0 1 1 2 6 24 120 720 5040 1 3 11 50 274 1764 13068 1 6 35 225 1624 13132 1 10 85 735 6769 1 15 175 1960 1 21 322 1 28 1 Định nghĩa số Harmonic : Cho n ,r ∈ N* Số Harmonic kí hiệu là : (r) nH với n (r) n r k=1 1H = k∑ Tính chất 2.2.2 : Quan hệ giữa số Stirling loại 1 không dấu và số Harmonic : a) s’(n+1,2) = n!Hn b) s’(n+1,3) = 2 n 2 2 n! 1 1H - 1+ +....+ 2 2 n          = 2 (2) n n n! H -H 2    c) s’(n+1,4)= 3 (2) (3) n n n n n! H -3H H +2H 6    Tính chất 2.2.3 : Các tính chất trên hàng, cột và ñường chéo của bảng số Stirling loại 1 không dấu . a) Cho n là số tự nhiên . Khi ñó : n j=0 j.s'(n,j)=s'(n+1,2)∑ ∀n ∈N* (2.2d) b) Cho n và c là các số nguyên không âm . Khi ñó : ( ) ( ) ( )n j=0 C j,c .s' n,j =s' n+1,c+1∑ (2.2e) c) Cho n và c là các số nguyên không âm . Khi ñó : s’(n+1,c+1) = [ ] ( )n n-k k=0 n .s' k,c∑ ∀n,c ∈N (2.2f) d) Cho n và c là các số nguyên không âm . Khi ñó : s’(n+c+1,c) = ( ) ( )c k=0 n+k .s' n+k,k∑ (2.2g) 2.3 SỐ STIRLING LOẠI 2 2.3.1 Định nghĩa Đị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) . Nói cách khác , số Stirling loại 2 là số cách phân phối n quả bóng phân biệt vào k hộp giống nhau mà không có hộp nào rỗng . 2.3.2 Các ñịnh lý Mệnh ñề 1 : Số toàn ánh từ tập hợp n phần tử vào tập k phần tử bằng k!S(n,k) Định lý 2.3.1 : Số Stirling loại 2 có thể tính trực tiếp qua công thức sau : ( ) ( ) ( )( )k i n i=0 1S n,k = -1 C k,i k-i k!∑ (2.3a) Định lí 2.3.2 : Cho n và k là số tự nhiên . Ta có : S(n + 1 ,k) = S(n, k-1) + k S(n, k) (2.3b) Định lý 2.3.3 : Cho n ∈ N . Số Stirling loại 2 ñược cho bởi công thức : ( )[ ]nn k k=0 x = S n,k x∑ (2.3c) Với [x]k = x(x-1)(x-2)...(x-k+1) với k∈ N* và [x]0 =1 Quy ước : S(n,0) = 0 với ∀ n ∈ N* S(0, k) = 0 với ∀ k ∈ N* S(n, k) = 0 nếu k > n và S(0,0) = 1 . Từ công thức (2.3b) ta xây dựng bảng sau bao gồm một số số Stirling loại 2 : Bảng 2.3 : Bảng số 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) 0 1 2 3 4 5 6 7 8 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 3 7 15 31 63 127 1 6 25 90 301 966 1 10 65 350 1701 1 15 140 1050 1 21 266 1 28 1 Định lý 2.3.4 : Đẳng thức về hàm sinh lũy thừa cho số Stirling loại 2 : ( ) ( ) ( ) k xn k n=k e -1xF x = S n,k = n! k! +∞ ∑ , k = 0,1,2,. , |x|<1 (2.3d) Hệ quả : S(n,k) = 1 2 k n! 1 k! r !r !...r !∑ với ri ∈N* và r1 + r2 + rk = n Định lý 2.3.5 : fk (x) = ( ) ( )( ) ( ) k n n=k xS n,k x = 1-x 1-2x ... 1-kx ∞ ∑ với k = 1,2,. , |x|<1 (2.3e) Hệ quả : S(n,k) = 1 2 k 1 2 k c c c c +c +...+c =n-k 1 2 ...k∑ với ci ∈N Định lý 2.3.6 : Với k ,n ∈ N ,ta có : S(n+1,k+1) = ( ) ( )n r=k C n,r S r,k∑ (2.3f) Định lý 2.3.7: Cho n ≥ 1 và 1 ≤ k ≤ n , ta có : ( ) ( )n-k n-kk S n,k C n-1,k-1 .k≤ ≤ (2.3g) Định lý 2.3.8 : Với n ∈N* . Ta có : a) [ ] ( )[ ] [ ]nn n-r r r=0 x+y = C n,r x y∑ (2.3h) b) [ ] ( )[ ] [ ]n n n-r r r=0 x+y = C n,r x y∑ (2.3i) Định lý 2.3.9 : a) ( ) ( ) ( ) ( ) ( ) k C i+j,i s n,i+j = C n,k s k,i s n-k,j∑ (2.3j) b) ( ) ( ) ( ) ( ) ( ) k C i+j,i S n,i+j = C n,k S k,i S n-k,j∑ (2.3k) 2.3.3 Các tính chất Tính chất 2.3.1 : Cho n và c là các số nguyên không âm . Khi ñó : S(n+1,c+1) = ( ) ( )n n-k k=0 c+1 S k,c∑ (2.3l) Tính chất 2.3.2 : Cho n và c là các số nguyên không âm . Thì : S(n+c+1,c) = ( )c k=0 k.S n+k,k∑ (2.3m) 2.4 QUAN HỆ GIỮA SỐ STIRLING LOẠI 1 VÀ SỐ STIRLING LOẠI 2 Định lý 2.4.1 : Cho n , m là các số tự nhiên . Khi ñó : ( ) ( )m mn k=n S m,k s k,n =δ∑ Với δ 1 khi m = n = mn 0 khi m n    ≠ 2.5 TÍNH CHIA HẾT CHO SỐ NGUYÊN TỐ CỦA SỐ STIRLING LOẠI 2 Định lý 2.5.1 : Nếu p là số nguyên tố thì p | S( p,k) với 2 ≤ k ≤ p -1 . Hơn nữa , p ∤S(p,1) và p∤S (p,p) (2.5a) Định lý 2.5.2 : Nếu p là số nguyên tố thì p| S(p+1,k+1) với mọi 2≤ k≤ p -1 . Hơn nữa , S(p+1,2) ≡ 1 mod p (2.5b) Đị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≤ p -2 và 2 ≤ k ≤ p –j . Hơn nữa , S(p+j, j+1) ≡ 1 mod p với mọi 2 ≤ j≤ p -2. (2.5c) CHƯƠNG 3 ỨNG DỤNG CỦA SỐ STIRLING 3.1 Ứng dụng giải một số bài toán tổ hợp 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 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 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.1.2 : Chứng minh rằng số cách ñặt k quân xe trên 1 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 ≤ k ≤ m . Bài toán 3.1.3 : Chứng minh rằng số cách xếp n người vào 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 ≤ k ≤ n Áp dụng : Có 10 người và 4 cái bàn tròn giống hệt nhau . Hỏi có bao nhiêu cách xếp 10 người vào 4 bàn trên sao cho : a) Có 1 bàn trống . b) Có 2 bàn trống . Bài toán 3.1.4 : Có bao nhiêu cách ñể phân tích số 7590 thành 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 . 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: a) S(n,n-1) = C(n,2) với n ≥ 2 . b) S(n,2) = 2n-1 – 1 với n ≥ 2 . c) S(n,3) = ( )n n1 3 -3.2 +36 với n ≥3 . d) S(n , n – 2) = C(n,3) + 3C(n,4) với n ≥ 2 . e) ( ) n n n1S n,4 = 4 -4.3 +6.2 -4 24    Bài toán 3.2.2 : Với n ∈N* . Chứng minh rằng : a) ( ) ( )n n-r r=k-1 S n+1,k = k S r,k-1∑ (3.2a) b) ( ) ( )n r=k-1 S n+1,k = r.S n+r-k,r∑ với k ≤ n (3.2b) Bài toán 3.2.3: Với k ∈N*, cho Yk (t) = ( ) n n=0 tS n,k n! ∞ ∑ . Chứng minh rằng : Yk (t) = t kt -km k-1 0 e e Y (m)dm∫ (3.2c) Bài toán 3.2.4 : Cho m ≥ n ; m , n ∈ N* và c = const . Chứng minh rằng : a) ( ) ( ) ( )( ) m m-kt tn n kt k=0 e +c e +cd = S n,k e dt m! m-k !       ∑ (3.2d) b) ( )n n k=0 S n,n-kn = n! k!∑ (3.2e) Bài toán 3.2.5 : Chứng minh rằng : S(n,k) = ( ) ( ) ( ) ( ) n-w r=k-ww w! C n,r S n-r,w S r,k-w k ∑ với 0 ≤ w≤ k Với (k)w = ( k-w +1) (k-w+2) k (3.2f) Bài toán 3.2.6 : Đặt ^ dD xD x dx ≡ ≡ . Cho hàm số : f(n,x) = n i i=1 i x i! ∞ ∑ với n là số tự nhiên Khi ñó với r , n ∈ N và x ∈ R. Ta có : a) ^ nn x x r r=1 D e = e S(n,r).x∑ (3.2g) b) n i^ n x i=1 i xD e = i! ∞ ∑ (3.2h) c) ( ) ( ) n in x r r=1 i=1 i xf n,x = e S n,r .x = i! ∞ ∑ ∑ (3.2i) 3.3 Sử dụng phần mềm Maple ñể tính số Stirling : 3.3.1 Sử dụng phần mềm Maple ñể tính số Stirling loại 2 : 3.3.2 Sử dụng phần mềm Maple ñể tính số Stirling loại 1 : 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ý thuyết tổ hợp , do nội dung chính của luận văn ít liên quan ñến các cấu hình tổ hợp nên tôi chỉ cho một số ví dụ , ngoài ra 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 . Ở chương 2 , tôi ñã ñưa ra ñịnh nghĩa , các tính chất , các ñịnh lý , hàm sinh của các số Stirling và chứng minh một cách khá chi tiết các ñịnh lý trên . Phương pháp chủ yếu ñể chứng minh 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 dụng ña dạng cho những lý thuyết ñã ñược trình bày ở chươ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 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 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 ñược xem là môn học khó cho học sinh ở cấp học này . 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à : Số poly – Stirling . Số q – stirling loại 2 .

Các file đính kèm theo tài liệu này:

dang_thi_nguyen_viet_3695_2084396.pdf

Luận văn liên quan

Đề tài Nâng cao hiệu quả quản lý văn bản quản lý nhà nước tại văn phòng ủy ban nhân dân huyện Ý Yên
42 trang | Lượt xem: 2446 | Lượt tải: 5
Bình luận về vai trò của Luật quốc tế trong giai đoạn hợp tác và đối thoại hiện nay
11 trang | Lượt xem: 2814 | Lượt tải: 3
Nghiên cứu sự ảnh hưởng của thao tác người công nhân đến năng suất chuyền may áo sơ mi nữ thời trang
120 trang | Lượt xem: 3765 | Lượt tải: 2
Đề tài Xã hội học đại cương
18 trang | Lượt xem: 2770 | Lượt tải: 2
Quy trình đo đạc tách tách thửa phục vụ cho công tác cấp giấy chứng nhận quyền sử dụng đất dụng đất tại văn phòng đăng kí quyền sử dụng đất TP Vĩnh Long
45 trang | Lượt xem: 4329 | Lượt tải: 3
Công cụ lao động và vai trò của nó
8 trang | Lượt xem: 50657 | Lượt tải: 1
Luận văn Nghiên cứu phát triển Du lịch theo hướng bền vững tại thành phố Đồng Hới tỉnh Quảng Bình
127 trang | Lượt xem: 2986 | Lượt tải: 2
Luận văn Mức độ ảnh hưởng của nợ xấu đến hiệu quả ngân hàng tại hệ thống ngân hàng thương mại Việt Nam
200 trang | Lượt xem: 1087 | Lượt tải: 1
Bài giảng luật chứng khoán
52 trang | Lượt xem: 4298 | Lượt tải: 2
Phân tích tình hình nhập kẩu nguyên vật liệu của công ty Innova
18 trang | Lượt xem: 2925 | Lượt tải: 1