Luận văn Thạc sĩ Toán học: Các số tổ hợp và một số ứng dụng trong thống kê

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

Thêm vào BST

Báo xấu

30
lượt xem 5
download

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

Luận văn trình bày nhiều công thức của các số tổ hợp với hai cách chứng minh: chứng minh đại số và chứng minh tổ hợp, nhằm giúp độc giả hiểu sâu hơn bản chất vấn đề. Phần còn lại của luận văn được dành để giới thiệu một số ứng dụng của các số tổ hợp trong thống kê, với mục đích giúp người đọc, đặc biệt là các em học sinh thấy rõ hơn những ứng dụng của Toán học trong đời sống thực tiễn.

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: Các số tổ hợp và một số ứng dụng trong thống kê

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC KHOA THỊ KIM THOA CÁC SỐ TỔ HỢP VÀ MỘT SỐ ỨNG DỤNG TRONG THỐNG KÊ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC KHOA THỊ KIM THOA CÁC SỐ TỔ HỢP VÀ MỘT SỐ ỨNG DỤNG TRONG THỐNG KÊ LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH. HÀ HUY KHOÁI Thái Nguyên - 2017
iii Mục lục Mở đầu 1 1 Các số nhị thức: những khía cạnh đại số và tổ hợp 3 1.1 Đồng nhất thức các số nhị thức: chứng minh đại số và tổ hợp 3 1.2 Nghịch đảo các số nhị thức . . . . . . . . . . . . . . . . . . . 21 2 Một số ứng dụng của số nhị thức trong thống kê 29 2.1 Một số khái niệm của xác suất . . . . . . . . . . . . . . . . . 29 2.2 Phân bố nhị thức . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Hồi quy Catalan . . . . . . . . . . . . . . . . . . . . . . . . . 38 Kết luận 49 Tài liệu tham khảo 50
iv Lời cảm ơn Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành với sự hướng dẫn của GS.TSKH. Hà Huy Khoái (Trường Đại học Thăng Long). Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán - Tin, cùng các giảng viên đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu. Tác giả muốn gửi những lời cảm ơn tốt đẹp nhất tới tập thể Lớp B, cao học Toán khóa 9 (2015 - 2017) đã động viên và giúp đỡ tác giả rất nhiều trong suốt quá trình học tập. Nhân dịp này, tác giả cũng xin chân thành cảm ơn Sở Giáo dục và Đào tạo Hải Phòng, Ban Giám hiệu và các đồng nghiệp ở Trường THPT Nguyễn Đức Cảnh, Huyện Kiến Thụy, Thành phố Hải Phòng đã tạo điều kiện cho tác giả hoàn thành tốt nhiệm vụ học tập và công tác của mình. Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến bố mẹ và đại gia đình đã luôn động viên và chia sẻ những khó khăn để tác giả hoàn thành tốt luận văn này.
1 Mở đầu Các số nhị thức là đề tài đã được đề cập nhiều trong các tài liệu về Toán học ở trường THPT. Với mỗi công thức của các số nhị thức, người ta thường dùng phương pháp chứng minh quy nạp. Phương pháp này có ưu điểm là dễ hiểu, gọn, nhưng nhiều khi làm mất "ý nghĩa tổ hợp" của đẳng thức. Điều này làm cho học sinh đôi khi không hiểu sâu vấn đề, và do đó khó khăn khi vận dụng. Vì thế, tôi chọn nghiên cứu đề tài " Các số tổ hợp và một số ứng dụng trong thống kê" làm luận văn thạc sĩ của mình. Một phần của luận văn này được dành để trình bày nhiều công thức của các số tổ hợp với hai cách chứng minh: chứng minh đại số và chứng minh tổ hợp, nhằm giúp độc giả hiểu sâu hơn bản chất vấn đề. Phần còn lại của luận văn được dành để giới thiệu một số ứng dụng của các số tổ hợp trong thống kê, với mục đích giúp người đọc, đặc biệt là các em học sinh thấy rõ hơn những ứng dụng của Toán học trong đời sống thực tiễn. Luận văn gồm hai chương: • Chương 1. Các số nhị thức: những khía cạnh đại số và tổ hợp được dành để trình bày về các đồng nhất thức của các số nhị thức, phân tích những khía cạnh đại số và tổ hợp của các số nhị thức như tính đối xứng; tính chất tổng dòng, tổng cột, tổng đường chéo, tính chẵn
2 lẻ của các số nhị thức; nghịch đảo các số nhị thức cũng được trình bày trong chương này. Tài liệu sử dụng là tài liệu số [2]. • Chương 2. Một số ứng dụng của số nhị thức trong thống kê trình bày một số khái niệm của xác suất, sự phân bố nhị thức và phép hồi quy Catalan. Tài liệu sử dụng là tài liệu số [1] và [2]. Thái Nguyên, ngày 10 tháng 7 năm 2017 Tác giả Khoa Thị Kim Thoa
3 Chương 1 Các số nhị thức: những khía cạnh đại số và tổ hợp 1.1 Đồng nhất thức các số nhị thức: chứng minh đại số và tổ hợp Bảng tam giác Pascal của các số nhị thức n n n n n n n n n n 0 1 2 3 4 5 6 7 8 ∑ 0 1 1 1 1 1 2 2 1 2 1 4 3 1 3 3 1 8 4 1 4 6 4 1 16 5 1 5 10 10 5 1 32 6 1 6 15 20 15 6 1 64 7 1 7 21 35 35 21 7 1 128 8 1 8 28 56 70 56 28 8 1 256
4 Mệnh đề 1.1.1. Các số tổ hợp nk thỏa mãn quan hệ hồi quy Pascal (1.1). n =1 với mọi n ≥ 0 : cột bên trái 0 0 =0 với mọi k ≥ 1 : dòng đầu tiên trên cùng k n n−1 n−1 = + với n ≥ 1 (1.1) k k−1 k • Các số nhị thức bn,k là các hệ số của xk trong khai triển nhị thức n n (1 + x) = ∑ bn,k xk k=0 Mệnh đề 1.1.2. Các số nhị thức thỏa mãn quan hệ hồi quy Pascal (1.1). Hệ quả 1.1.3. Với mọi k, n ∈ N, n = bn,k k • Vì các số tổ hợp có cùng giá trị với các số nhị thức nên theo hệ quả 1.1.3 chúng đều được gọi là các số nhị thức. Mệnh đề 1.1.4. Với mọi số nguyên không âm n và k, nk n = (1.2) k k! với nk = n(n − 1)(n − 2) · · · (n − k + 1) Hệ quả 1.1.5. Với mọi số nguyên không âm n và k, n n! = (1.3) k k!(n − k)!
5 Chứng minh đại số, chứng minh tổ hợp • Chứng minh đại số của đẳng thức được thực hiện bằng những biến đổi đại số. Thông thường, người ta dùng phương pháp quy nạp. Phương pháp quy nạp có ưu điểm là đưa ra chứng minh rất ngắn gọn, nhưng nhược điểm lớn nhất là nhiều khi không làm rõ được bản chất vấn đề cũng như ý nghĩa của công thức. • Chứng minh tổ hợp được dùng nhằm khắc phục nhược điểm nêu trên. Cụ thể là trong chứng minh đẳng thức nào đó bằng phương pháp tổ hợp, người ta thường tính đại lượng ở hai vế của đẳng thức theo hai cách khác nhau. Từ đó thấy rõ bản chất của vấn đề đang xét. Chúng ta sẽ minh hoạ hai phương pháp nêu trên qua một số ví dụ . Tính đối xứng Một số đồng nhất thức là sự khái quát của tính chất dễ dàng nhận thấy trong tam giác Pascal. Một trong các tính chất đó là mỗi dòng của tam giác Pascal có tính xuôi ngược, nó được đọc giống nhau từ phải sang trái hoặc từ trái sang phải. Ví dụ chúng ta quan sát tính đối xứng của dòng 8: 1 8 28 56 70 56 28 8 1 Mệnh đề 1.1.6. (Tính đối xứng theo dòng). Với số nguyên n, k bất kỳ mà 0 ≤ k ≤ n, n n = (1.4) k n−k Chứng minh. (Chứng minh đại số). Sử dụng phương trình ( 1.3 ) ta có ngay kết quả của phép chứng minh đại số này. n n! n! n = = = k k!(n − k)! (n − k)!k! n−k
6 Chứng minh. (Chứng minh tổ hợp). Đại lượng ở vế trái của đẳng thức (1.4 ) là số các cách khác nhau để chọn k phần tử từ tập n phần tử. Vế phải là các cách khác nhau để chọn (n-k) phần tử còn lại từ tập đó. Vì mỗi cách chọn k phần tử từ tập n phần tử chính là một cách chọn (n-k) phần tử còn lại trong n phần tử nên hai cách chọn đều có số lượng như nhau. Tính chất tổng dòng Một tính chất khác của tam giác Pascal là tổng của các hạng tử trong mỗi dòng là lũy thừa của 2. Ví dụ trong dòng 8, 1 + 8 + 28 + 56 + 70 + 56 + 28 + 8 + 1 = 256 = 28 Mệnh đề 1.1.7. (Tính chất tổng dòng). Tổng các hạng tử trong dòng n của tam giác Pascal là 2n , tức là: n n ∑ k = 2n (1.5) k=0 Chứng minh. (Chứng minh tổ hợp ).Theo hệ quả 1.1.3, các số hạng ở vế trái là số cách chọn các tập con lực lượng k từ tập S gồm n phần tử, và làm như vậy với mỗi giá trị của k. Như vậy, số các tập con của tập hữu hạn S có n phần tử là 2n . Chứng minh. (Chứng minh đại số). Thay x = 1 vào cả hai vế của phương trình rồi khai triển nhị thức ta được kết quả sau đây, n n n (1 + x)n = ∑ x k=0 k   n n n n n n ⇒ (1 + x)n   =∑ x  =∑ 1  k=0 k k  x=1  x=1 k=0
7 n n ⇒ 2n = ∑ k=0 k Chứng minh. ( Chứng minh đại số). Một phép chứng minh đại số khác là bằng quy nạp, bắt đầu với dòng 0 của tam giác Pascal như là trường hợp cơ sở, và sau đó sử dụng quan hệ hồi quy Pascal để chỉ ra tổng trong dòng n gấp đôi tổng trong dòng n − 1. Tính chất tổng cột Một số tính chất khác của tam giác Pascal xuất hiện khi nghiên cứu sâu hơn. Ví dụ như, tổng của tất cả các hạng tử trong cột nào đó đến dòng n, bao gồm cả hạng tử trong dòng n, có thể được tìm thấy trong cột tiếp theo ở dòng n + 1. Ví dụ 1.1.8. Trong các cột 2 và 3 của tam giác Pascal, chúng ta thấy tình trạng sau đây, n n n n 1 2 3 2 1 3 3 4 6 5 10 6 15 7 35 1 + 3 + 6 + 10 + 15 = 35 Mệnh đề 1.1.9. (Tính chất tổng cột). Tổng các hạng tử trong cột c (c ≥ 0) của tam giác Pascal, từ dòng 0 xuống dòng n, bằng hạng tử trong dòng
8 n + 1, cột c + 1. n k n+1 ∑ c = c+1 (1.6) k=0 Chứng minh. Bằng quy nạp trên dòng thứ n, ta có * Bước cơ sở. Cho n = 0, tổng các hạng tử xuống dòng 0 là 1 trong cột c = 0 và là 0 trong cột c 6= 0.  1 nếu c = 0  1 = c+1 0 nếu c 6= 0.  * Giả thiết quy nạp. Giả sử n ≥ 1 ta có n−1 k n ∑ c = c+1 k=0 * Bước quy nạp. Ta có n n−1 k k n ∑ c =∑ c + c k=0 k=0 n n = + ( giả thiết quy nạp) c+1 c n+1 = ( quan hệ hồi quy Pascal). c+1 Tính chất tổng đường chéo Định nghĩa 1.1.10. Đường chéo từ góc trên bên trái của bảng hai chiều hướng xuống phía dưới bên phải được gọi là đường chéo đông nam. Đường chéo theo hướng ngược lại gọi là đường chéo tây bắc. Định nghĩa 1.1.11. Đường chéo từ góc dưới bên trái của bảng hai chiều hướng lên phía trên bên phải được gọi là đường chéo đông bắc. Đường chéo theo hướng ngược lại gọi là đường chéo tây nam.
9 Chúng ta thấy rằng tổng các hạng tử đầu tiên trên một đoạn hữu hạn trên đường chéo đông nam của tam giác Pascal hiển thị ngay bên dưới hạng tử cuối cùng về phía đông nam. Ví dụ 1.1.12. Theo dõi bảng tam giác Pascal ta thấy, n n n n n n 0 1 2 3 4 2 1 3 3 4 6 5 10 6 15 7 35 1 + 3 + 6 + 10 + 15 = 35 Mệnh đề 1.1.13. (Tính chất tổng đường chéo đông nam). Tổng n + 1 hạng tử đầu tiên trên đường chéo đông nam từ dòng r, cột 0 trong tam giác Pascal bằng hạng tử trong dòng r + n + 1, cột n, hạng tử ngay bên dưới hạng tử cuối cùng của đường chéo, tức là: n r+k r+n+1 ∑ k = (1.7) k=0 n Chứng minh. Kết quả sau đây được suy ra từ 2 tính chất trước của tam giác Pascal. n n r+k r+k ∑ k =∑ r ( tính chất đối xứng) k=0 k=0 r+n+1 = ( tính chất tổng cột) r+1 r+n+1 = ( tính chất đối xứng). n
10 Hệ quả sau đây chỉ đơn giản là đảo ngược thứ tự của tổng các phần tử trên đường chéo. Hệ quả 1.1.14. (Tính chất tổng đường chéo tây bắc). Đối với số nguyên m không âm bất kỳ với 0 ≤ m ≤ n, các hệ số nhị thức thỏa mãn phương trình: m n−k n+1 ∑ = (1.8) k=0 m−k m Chứng minh. Đảo ngược đường chéo tây bắc n−0 n−1 n−m + +···+ m−0 m−1 m−m ở vế trái của phương trình ta được kết quả tổng đường chéo đông nam n−m n−m+1 n + +···+ 0 1 m mà bắt đầu từ dòng n − m và bao gồm m + 1 hạng tử trở xuống, kết thúc ở dòng n, cột m. Theo mệnh đề 1.1.13 giá trị của tổng đường chéo đông nam là hệ số nhị thức n+1 m Tổng của các hạng tử trên đường chéo đông bắc là các số Fibonacci. Ví dụ tổng 1 + 5 + 6 + 1 dọc theo đường chéo về phía đông bắc bắt đầu từ 6 0 là số Fibonacci f 7 = 13 Ví dụ 1.1.15. Các số Fibonacci trong hộp hiển thị ở đây không thực sự xuất hiện ở các vị trí hiển thị. Chúng chỉ đơn giản là các tổng dọc theo đường chéo về phía đông bắc dẫn đến chúng.
11 n n n n n n 0 1 2 3 4 1 5 2 1 3 3 21 4 1 4 5 10 6 6 7 1 1 +3 +1 = 5 = f5 1 + 6 + 10 + 4 = 21 = f8 Mệnh đề 1.1.16. ( Tính chất đường chéo đông bắc Fibonacci). Tổng các hạng tử trên đường chéo đông bắc từ dòng n, cột 0 trong tam giác Pascal bằng số Fibonacci fn+1 , tức là: n n−k ∑ k = fn+1 (1.9) k=0 Chứng minh. * Bước cơ sở. Đối với n = 0 và n = 1 thì tổng đường chéo đông bắc lần lượt là 1 = f1 và 1 + 0 = f2 . * Giả thiết quy nạp. Với n ≥ 2, giả sử rằng n−1 n−1−k ∑ = fn k=0 k và n−2 n−2−k ∑ = fn−1 k=0 k * Bước quy nạp. Bằng quan hệ hồi quy Pascal, ta có n−k n−k−1 n−k−1 = + k k−1 k
12 do đó n n n n−k n−k−1 n−k−1 ∑ k = ∑ k−1 + ∑ k k=0 k=0 k=0 n−2 n−1 n− j−2 n−k−1 =∑ +∑ j=0 j k=0 k = fn−1 + fn ( giả thiết quy nạp) = fn+1 ( phép hồi quy Fibonacci) Tích của hệ số nhị thức Một tính chất khác trong tam giác Pascal là hệ thức liên hệ giữa mỗi một phần tử và phần tử phía trên bên trái của nó. Ví dụ 1.1.17. Chúng ta theo dõi phần được thêm vào từ tam giác Pascal. 7 6 4 = 4 · 35 = 140 = 7 · 20 = 7 4 3 n n n n n 2 3 4 5 5 6 20 7 35 8 7 4 4 6 · = 35 · = 20 = 4 7 7 3 hoặc tương đương 7 6 · 4 = 140 = ·7 4 3
13 Nguyên tắc chung của hệ thức này được gọi là tính hấp thu, được thiết lập bởi mệnh đề tiếp theo. Mệnh đề 1.1.18. ( Tính hấp thu). Với 0 ≤ k ≤ n, ta có: n n−1 k=n (1.10) k k−1 Chứng minh. (Chứng minh đại số). Bằng biến đổi đại số, ta có nk nk (n − 1)k−1 n n−1 k= k= =n =n k k! (k − 1)! (k − 1)! k−1 Chứng minh. (Chứng minh tổ hợp). Ta thấy rằng ở vế trái n k k là số cách chọn k phần tử từ tập n phần tử nhân với k. Ở vế phải là lấy phần tử n nhân với số cách chọn k − 1 phần tử từ n − 1 phần tử còn lại n−1 n k−1 Hai kết quả này là tương đương nhau. Tính hấp thu là một trường hợp đặc biệt của mối quan hệ giữa một phần tử và các phần tử khác dọc theo đường chéo tây bắc. Mối quan hệ này được biểu thị bằng một đồng nhất thức tổ hợp bậc cao, là sự tổng quát hóa cho minh họa sau đây. Ví dụ 1.1.19. Tiếp theo, ta nhận thấy rằng ở vị trí 1 về phía tây bắc của hệ số 74 ta có 1 6 7 4 4 20 = = = 35 · 3 4 71 7
14 ở vị trí 3 về phía tây bắc của 74 trong tam giác Pascal, ta có 3 4 7 4 24 4= = 3 = 35 · 1 4 7 210 n n n n n n 1 2 3 4 5 4 4 5 6 7 35 8 43 3 7 4 /3! 4 35 · 3 = · 3 = =4 7 4 7 /3! 1 hoặc tương đương 7 4 7−3 7 · = · 4 3 4−3 3 Tính chất của phương trình sau đây là tính chất tập con của tập con. Mệnh đề 1.1.20. (Đồng nhất thức tập con của một tập con). Đối với 0 ≤ k ≤ m ≤ n, ta có: n m n n−k = (1.11) m k k m−k Chứng minh. (Chứng minh đại số). Bằng các tính toán đại số đơn giản, ta có n m n! m! = · m k m!(n − m)! k!(m − k)! n! = k!(n − m)!(m − k)! n! (n − k)! = · k!(n − k)! (n − m)!(m − k)!
15 n n−k = k m−k Chứng minh. (Chứng minh tổ hợp). Chúng ta thấy rằng tổ hợp ở vế trái n m m k là số cách chọn m phần tử từ tập có n phần tử nhân với số cách chọn k phần tử từ tập có m phần tử. Điều này rõ ràng tương đương với số cách chọn k phần tử từ tập n nhân với số cách chọn m − k phần tử từ tập n − k phần tử còn lại như ở vế phải. n n−k k m−k Phép nhân chập Vandermonde. Định lí 1.1.21. (Phép nhân chập Vandermonde). Giả sử m, n, k là các số nguyên không âm , khi đó n n m n+m ∑ = (1.12) j=0 j k− j k Chứng minh. (Chứng minh tổ hợp). Giả định rằng có n + m phần tử trong một tập, n phần tử màu xanh và m phần tử màu đỏ, và phải chọn ra k phần tử, thì có n+m cách chọn, đó là giá trị ở vế phải. Số cách để chọn j phần k tử màu xanh và k − j phần tử màu đỏ là tích nj k− m j . Vì vậy tổng tất cả các tích này ở vế trái phải giống như ở vế phải. Chứng minh. (Chứng minh khác). Tổng bên trái của phương trình tổ hợp trên bằng hệ số của xk ở vế trái của phương trình đa thức (1 + x)n (1 + x)m = (1 + x)n+m
16 và hệ số nhị thức ở vế phải của phương trình tổ hợp bằng hệ số của xk ở vế phải của phương trình đa thức đó. Bảng tóm tắt các đồng nhất thức của các số nhị thức cơ bản n n−1 n−1 = + quan hệ hồi quy Pascal k k k−1 nk n = Công thức bậc lũy thừa k k! n n! = Công thức giai thừa k k!(n − k)! n n = Tính đối xứng k n−k n n ∑ k = 2n Tổng dòng k=0 n r n+1 ∑ c = c+1 Tổng cột r=0 n r+k r+n+1 ∑ k = Đường chéo đông nam k=0 n m n−k n+1 ∑ m−k = m Đường chéo tây bắc k=0 n n−k ∑ k = fn+1 Đường chéo đông bắc Fibonacci k=0 n n−1 k=n Tính hấp thu k k−1 n m n n−k = Tập con của một tập con m k k m−k n n m n+m ∑ j k− j = k Phép nhân chập Vandermonde j=0 Tính chẵn lẻ của các số nhị thức Một điều thú vị nữa khi tìm hiểu về các số nhị thức, đó là làm thế nào ta có thể xác định được tính chẵn lẻ của một hệ số nhị thức nhất định, chẳng