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

ằng số Fibonacci fn+1, tức là: n ∑ k=0 ( n− k k ) = fn+1 (1.9) 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 ∑ k=0 ( n−1− k k ) = fn và n−2 ∑ k=0 ( n−2− k k ) = fn−1 * Bước quy nạp. Bằng quan hệ hồi quy Pascal, ta có( n− k k ) = ( n− k−1 k−1 ) + ( n− k−1 k ) 12 do đó n ∑ k=0 ( n− k k ) = n ∑ k=0 ( n− k−1 k−1 ) + n ∑ k=0 ( n− k−1 k ) = n−2 ∑ j=0 ( n− j−2 j ) + n−1 ∑ k=0 ( n− k−1 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. 4 ( 7 4 ) = 4 ·35= 140= 7 ·20= 7 ( 6 3 ) n (n 2 ) (n 3 ) (n 4 ) (n 5 ) 5 6 20 7 35 8( 7 4 ) · 4 7 = 35 · 4 7 = 20= ( 6 3 ) hoặc tương đương( 7 4 ) ·4= 140= ( 6 3 ) ·7 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 k ) k = n ( n−1 k−1 ) (1.10) Chứng minh. (Chứng minh đại số). Bằng biến đổi đại số, ta có( n k ) k = nk k! k = nk (k−1)! = n (n−1)k−1 (k−1)! = n ( n−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 ( n−1 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ố (7 4 ) ta có 20= ( 6 3 ) = ( 7 4 ) 41 71 = 35 · 4 7 14 ở vị trí 3 về phía tây bắc của (7 4 ) trong tam giác Pascal, ta có 4= ( 4 1 ) = ( 7 4 ) 43 73 = 35 · 24 210 n (n 1 ) (n 2 ) (n 3 ) (n 4 ) (n 5 ) 4 4 5 6 7 35 8 35 · 4 3 73 = ( 7 4 ) · 4 3/3! 73/3! = ( 4 1 ) = 4 hoặc tương đương( 7 4 ) · ( 4 3 ) = ( 7−3 4−3 ) · ( 7 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 )( m k ) = ( n k )( n− k m− k ) (1.11) 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 )( m k ) = n! m!(n−m)! · m! k!(m− k)! = n! k!(n−m)!(m− k)! = n! k!(n− k)! · (n− k)! (n−m)!(m− k)! 15 = ( n k )( n− 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 k )( n− 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 ∑ j=0 ( n j )( m k− j ) = ( n+m k ) (1.12) 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 k ) cách chọn, đó là giá trị ở vế phải. Số cách để chọn j phần tử màu xanh và k− j phần tử màu đỏ là tích (nj)( mk− 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 k ) = ( n−1 k ) + ( n−1 k−1 ) quan hệ hồi quy Pascal( n k ) = nk k! Công thức bậc lũy thừa( n k ) = n! k!(n− k)! Công thức giai thừa( n k ) = ( n n− k ) Tính đối xứng n ∑ k=0 ( n k ) = 2n Tổng dòng n ∑ r=0 ( r c ) = ( n+1 c+1 ) Tổng cột n ∑ k=0 ( r+ k k ) = ( r+n+1 n ) Đường chéo đông nam m ∑ k=0 ( n− k m− k ) = ( n+1 m ) Đường chéo tây bắc n ∑ k=0 ( n− k k ) = fn+1 Đường chéo đông bắc Fibonacci( n k ) k = n ( n−1 k−1 ) Tính hấp thu( n m )( m k ) = ( n k )( n− k m− k ) Tập con của một tập con n ∑ j=0 ( n j )( m k− j ) = ( n+m k ) Phép nhân chập Vandermonde 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 17 hạn như ( 165 93 ) mà không cần phải tính toán. Tam giác Pascal sẽ cho ta biết điều bí mật này. Ta thấy rằng tất cả các hạng tử trong dòng 1, 3 và 7, các số có dạng 2n− 1 là lẻ. Hơn nữa, số lượng các số lẻ liên tiếp dường như là lũy thừa của 2. Sự xác định tính chẵn lẻ của một hệ số nhị thức đã được nghiên cứu có hệ thống bởi nhà toán học người Anh James Glaisher (1848-1928). Định lí 1.1.22. Giả sử n và k là các số nguyên không âm, khi đó ( n k ) ≡ 0 mod 2 nếu n là chẵn và k là lẻ(bn/2c bk/2c ) mod 2 nếu n lẻ và k chẵn. Chứng minh. Để chứng minh định lý này ta xét 4 trường hợp sau đây. *Trường hợp 1: n chẵn và k lẻ. Vì n là chẵn, rõ ràng trong trường hợp này giá trị ở vế phải của đồng nhất thức hấp thu k ( n k ) = n ( n−1 k−1 ) là chẵn. Vì tích số k (n k ) ở vế trái cũng phải là chẵn và vì k là số lẻ nên theo đó (n k ) là chẵn. *Trường hợp 2: n chẵn và k chẵn. Trong trường hợp này chúng ta khai triển các hệ số nhị thức( n k ) = nk k! = n(n−1)(n−2)...(n− k+1) 1.2.3...k = (n−1)(n−3)...(n− k+1) 1.3.5...(k−1) · n(n−2)(n−4)...(n− k+2) 2.4.6...k Vì mẫu thức có k/2 thừa số chẵn, chúng ta tiếp tục = (n−1)(n−3)...(n− k+1) 1.3.5...(k−1) · n(n−2)(n−4)...(n− k+2) 2 k 2 ·1 ·2 ·3 · · · k2 18 và vì tử thức có k/2 thừa số chẵn, = (n−1)(n−3)...(n− k+1) 1.3.5...(k−1) · 2 k 2 · n2(n2−1)(n2−2) · · ·(n2− k2+1) 2 k 2 ·1 ·2 ·3 · · · k2 = (n−1)(n−3)...(n− k+1) 1.3.5...(k−1) · ( n/2 k/2 ) Do đó, 1.3.5....(k−1) ( n k ) = (n−1)(n−3)...(n− k+1) ( n/2 k/2 ) Từ đó suy ra cả n và k đều chẵn,( n k ) ≡ ( n/2 k/2 ) ≡ (bn/2c bk/2c ) mod 2 (1.13) Sự tương đương đầu tiên trong (1.13) là vì mỗi thừa số đứng trước hệ số nhị thức trong tử số và mẫu số là lẻ và phép nhân của một số nguyên với một số lẻ không làm thay đổi tính chẵn lẻ. Điều thứ hai là vì n/2= bn/2c và k/2= bk/2c cho cả n và k đều chẵn. *Trường hợp 3: n lẻ và k lẻ. Tương tự như trường hợp 1, điểm bắt đầu của chúng ta là đồng nhất thức hấp thu. k ( n k ) = n ( n−1 k−1 ) vì n và k đều là lẻ, và lại một lần nữa từ phép nhân của một số nguyên bởi một số lẻ không làm thay đổi tính chẵn lẻ, từ đó suy ra( n k ) ≡ ( n−1 k−1 ) mod 2 Từ n−1 và k−1 đều là chẵn, theo trường hợp 2 thì( n−1 k−1 ) ≡ (bn/2c bk/2c ) mod 2 và như vậy thì ( n k ) ≡ (bn/2c bk/2c ) mod 2 19 *Trường hợp 4: n lẻ và k chẵn. Theo tính đối xứng của đồng nhất thức thì (n− k) ( n k ) = (n− k) ( n n− k ) và n ( n−1 n− k−1 ) = n ( n−1 k ) Tiếp đó theo tính hấp thu của đồng nhất thức (n− k) ( n n− k ) = n ( n−1 n− k−1 ) thì (n− k) ( n k ) = n ( n−1 k ) vì n− k và n đều lẻ, ta có( n k ) ≡ ( n−1 k ) mod 2 Áp dụng trường hợp 2 vào vế phải, ta thu được( n k ) ≡ (b(n−1)/2c bk/2c ) mod 2 vì n là lẻ, nên chỉ số trên b(n−1)/2c bằng bn/2c Một thuật toán đơn giản quyết định tính chẵn lẻ của một hệ số nhị thức là áp dụng định lí 1.1.22 lặp đi lặp lại cho đến khi chỉ số trên là chẵn và chỉ số dưới là lẻ hoặc chỉ số dưới là 0. Ví dụ 1.1.23. Cả thẩy có hai kiểu kết thúc (chẵn, lẻ):( 165 93 ) ≡ ( 82 46 ) ≡ ( 41 23 ) ≡ ( 20 11 ) ≡ 0 mod 2( 75 11 ) ≡ ( 37 5 ) ≡ ( 18 2 ) ≡ ( 9 1 ) ≡ ( 4 0 ) ≡ 1 mod 2 Ta xét xem lý do tại sao số các hệ số nhị thức là lẻ liên tiếp trong một dòng của tam giác Pascal là lũy thừa của 2, chúng ta quan sát thấy trong hệ đếm nhị phân, phép toán lấy phần nguyên n 7→ bn/2c 20 đạt được bằng cách xóa bít ngoài cùng bên phải. Chúng ta cũng quan sát thấy trong trường hợp 1 cuả định lý 1.1.22 với n là số chẵn và k là số lẻ, là phân biệt bởi một 0-bit ở cuối bên phải của số nhị phân đối với n và 1-bit ở cuối bên phải của số nhị phân đối với k. Ví dụ 1.1.24. Trong biểu diễn các số dạng nhị phân 16510 = 101001012 9310 = 010111012 xét từ phải sang trái, sự xuất hiện của số 0 đầu tiên ở hàng trên tại 21−bit. Vì cũng tồn tại 0-bit ở ngay bên dưới nó, ta tiếp tục phân tích. Số 0 tiếp theo ở hàng trên xuất hiện tại 23−bit và có 1-bit bên dưới nó. Vì vậy quá trình phân tích kết thúc, và kết luận về tính chẵn lẻ là chẵn. Trong biểu diễn dạng nhị phân 7510 = 10010112 1110 = 00010112 ta thấy rằng có 0-bit hàng dưới mỗi khi có 0-bit ở hàng trên, vì vậy kết luận về tính chẵn lẻ là lẻ. Mệnh đề 1.1.25. Số các số nhị thức lẻ trong dòng n của tam giác Pascal là 2w, trong đó w là số các 1-bits trong phép biểu diễn nhị phân của n. Chứng minh. Do hệ số nhị thức (n k ) là lẻ, phải có số 0 ở mỗi bit trong khai triển nhị phân của k mà tại đó có số 0 ở bit tương ứng của khai triển nhị phân của n. Tuy nhiên nếu tồn tại số 1 tại một bit của khai triển nhị phân của n, thì có thể tồn tại hoặc 0 hoặc 1 ở bit tương ứng của khai triển nhị phân của k. Nếu tồn tại w 1-bits đối với n, thì tồn tại 2w giá trị đối với k thỏa mãn các quy tắc đối với 0-bits. 21 Hệ quả 1.1.26. Nếu số nguyên n có dạng 2r− 1, thì mỗi hệ số nhị thức trong hàng n của tam giác Pascal là số lẻ. Chứng minh. Không có 0-bits trong biểu diễn nhị phân của 2n−1 1.2 Nghịch đảo các số nhị thức Trong phần này sẽ phát triển một kỹ thuật đối với các hệ số nhị thức, được gọi là nghịch đảo nhị thức. Ứng dụng chính của nó trong phần này là lời giải cho một quan hệ hồi quy. Định nghĩa 1.2.1. Biến đổi của dãy 〈 fn〉 bởi nghịch đảo nhị thức là dãy 〈gn〉 với gn = n ∑ j=0 ( n j ) (−1) j f j (1.14) Có một tính chất đặc trưng của bất kỳ khái niệm toán học nào, gọi là phép toán đối ngẫu, là áp dụng hai lần phép toán sẽ khôi phục lại đối tượng ban đầu. Định lý 1.2.2 khẳng định rằng phép biến đổi nghịch đảo nhị thức các dãy có tính chất nói trên. Định lí 1.2.2. Giả sử 〈 fn〉 là một dãy và 〈gn〉 là biến đổi của nó bởi phép nghịch đảo nhị thức. Khi đó, với mọi n≥ 0 fn = n ∑ j=0 ( n j ) (−1) jg j (1.15) Nói cách khác, biến đổi hai lần phục hồi lại dãy ban đầu 〈 fn〉. Chứng minh. Xuất phát từ vế phải của phương trình (1.15) và thay thế công thức nghịch đảo của phương trình (1.14) đối với g j n ∑ j=0 ( n j ) (−1) jg j = n ∑ j=0 ( n j ) (−1) j j ∑ i=0 ( j i ) (−1)i fi 22 = n ∑ j=0 j ∑ i=0 ( n j )( j i ) (−1) j+i fi (1.16) Sự thay đổi thứ tự của phép lấy tổng là hữu ích ở đây = n ∑ i=0 n ∑ j=i ( n j )( j i ) (−1) j+i fi (1.17) Áp dụng đồng nhất thức tập con của một tập con (Mệnh đề 1.1.20) ta đưa về phép lấy tổng theo chỉ số j = n ∑ i=0 n ∑ j=i ( n i )( n− i j− i ) (−1) j+i fi Sau đó rút gọn thừa số bên trong tổng = n ∑ i=0 ( n i ) fi n ∑ j=i ( n− i j− i ) (−1) j−i với (−1)2i = 1 Thay k = j− i = n ∑ i=0 ( n i ) fi n−i ∑ k=0 ( n− i k ) (−1)k Tổng bên trong −→ số mũ nhị thức = n ∑ i=0 ( n i ) fi(1− x)n−i  x=1 = n ∑ i=0 ( n i ) fi(i= n) = ( n n ) fn(n= n) = fn Trong phương trình (1.17) ở trên, ta thấy rằng trong tổng chỉ số j xuất hiện 2 lần trong số hạng bên trong hệ số nhị thức, một lần là chỉ số trên và một lần là chỉ số dưới. Trong trường hợp như vậy, như đã thấy ở đây, 23 đồng nhất thức tập con của tập con thường làm biến đổi dễ dàng hơn, nó cho phép giảm số lần xuất hiện chỉ số trong. Một vài ví dụ cơ bản của phép nghịch đảo Ba ví dụ đầu tiên sau đây về phép nghịch đảo nhằm giới thiệu phép nghịch đảo được tiến hành như thế nào. Ví dụ 1.2.3. Dãy số không đổi 〈 fn〉= 1 1 1 1 · ·· có nghịch đảo là gn = n ∑ j=0 ( n j ) (−1) j f j = n ∑ j=0 ( n j ) (−1) j = (1− x)n  x=1 = (1−1)n = 1 nếu n= 00 nếu n> 0 ⇒ 〈gn〉= 1 0 0 0 · ·· Một cách tổng quát, dãy 〈 fn〉= c c c c · · · có nghịch đảo là 〈gn〉= c 0 0 0 · · · Ví dụ 1.2.4. Dãy số tự nhiên 〈 fn〉= 0 1 2 3 · · · 24 được nghịch đảo như sau gn = n ∑ j=0 ( n j ) (−1) j f j = n ∑ j=0 j ( n j ) (−1) j (1.18) Áp dụng đồng nhất thức hấp thu để loại bỏ sự xuất hiện của chỉ số j. = n ∑ j=0 n ( n−1 j−1 ) (−1) j = n n ∑ j=0 ( n−1 j−1 ) (−1) j Thay j = i+1 để sắp xếp các hệ số nhị thức với giới hạn của tổng. = n n−1 ∑ i=0 ( n−1 i ) (−1)i+1 =−n n−1 ∑ i=0 ( n−1 i ) (−1)i =−n(1− x)n−1  x=1 = −1 nếu n= 10 nếu n 6= 1 ⇒ 〈gn〉= 0 −1 0 0 · · · Trong phương trình (1.18) của ví dụ này, chỉ số lấy tổng j xuất hiện trong một hệ số nhị thức và cũng như là một nhân tử. Đồng nhất thức hấp thu là đồng nhất thức nhị thức thông thường mà số lần xuất hiện của biến chỉ số được rút gọn trong trường hợp như vậy. Dãy 0 1 2 3 · · · cũng có thể được biểu diễn như là 〈(n 1 )〉 . Theo đó, không có gì phải ngạc nhiên nếu nghịch đảo của dãy (n r ) tương tự như ví dụ 1.2.3. Ví dụ 1.2.5. Dãy số nhị thức fn = ( n r ) 25 đối với số không âm cố định r có dãy nghịch đảo là gn = n ∑ j=0 ( n j ) (−1) j f j = n ∑ j=0 ( j r )( n j ) (−1) j (1.19) Áp dụng đồng nhất thức tập con của một tập con và đặt nhân tử chung = n ∑ j=0 ( n r )( n− r j− r ) (−1) j = ( n r ) n ∑ j=0 ( n− r j− r ) (−1) j Thay j = i+ r, ta có gn = ( n r ) n−r ∑ i=−r ( n− r i ) (−1)i+r = ( n r )n−r ∑ i=0 ( n− r i ) (−1)i+r = (−1)r ( n r )n−r ∑ i=0 ( n− r i ) (−1)i = (−1) n nếu n= r 0 nếu n 6= r Ở phương trình (1.19), số hạng xuất hiện 2 lần có chỉ số lấy tổng là j. Lần này cả hai đều ở trong các hệ số nhị thức khác nhau, với một lần xuất hiện như chỉ số trên và một lần xuất hiện như chỉ số dưới. Đồng nhất thức tập con của một tập con thường được sử dụng để loại bỏ một trong những lần xuất hiện các số hạng như vậy. Do đó tổng được rút gọn. Sự xáo trộn Nghịch đảo nhị thức có nhiều ứng dụng đặc biệt. 26 Ví dụ 1.2.6. Mỗi hoán vị của đoạn các số nguyên [1 : n] có thể thu được bằng cách chọn r số từ đoạn [1 : n] và làm thay đổi thứ tự của chúng. Theo đó, nếu D j là một sự xáo trộn (thay đổi thứ tự) số, thì n!= ( n 0 ) D0+ ( n 1 ) D1+ ( n 2 ) D2+ · · ·+ ( n n ) Dn Từ đó suy ra rằng fn = (−1)nDn có nhị thức nghịch đảo gn = n! Bởi tính chất đối ngẫu nghịch đảo nhị thức, ta có fn = (−1)nDn = n ∑ j=0 ( n j ) (−1) jg j từ đó suy ra Dn = (−1)n n ∑ j=0 ( n j ) (−1) jg j = (−1)n n ∑ j=0 ( n j ) (−1) j j! = n ∑ j=0 n j(−1) j ⇒ Dn n! = 1− 1 1! + 1 2! − 1 3! + · · ·+(−1)n 1 n! lim−−−→ n→∞ e −1 Vì vậy, tỷ lệ giữa các xáo trộn và số các hoán vị của một tập hợp n đối tượng tiến dần đến e−1 khi n lớn. Các ví dụ khác về phép nghịch đảo Các phương pháp lấy tổng được trình bày trong phần này đối với các phép biến đổi dãy được áp dụng rộng rãi. Chúng ta bổ sung trong phần này thêm 27 hai ví dụ, kết hợp cả phương pháp nghịch đảo các số nhị thức với đồng nhất thức của các số nhị thức đã đề cập trước đây. Ví dụ 1.2.7. Khi hai thừa số của một số hạng là hai hệ số nhị thức có chứa chỉ số của phép lấy tổng như là chỉ số dưới, mấu chốt của sự đơn giản hoá là thiết lập một ánh xạ của phép nhân chập Vandermonde để rút gọn số hạng đó. Dãy số fn = (−1)n ( N n ) có dãy nhị thức nghịch đảo là gn = n ∑ j=0 ( n j ) (−1) j f j = n ∑ j=0 ( n j ) (−1) j(−1) j ( N j ) = n ∑ j=0 ( N j )( n j ) áp dụng đồng nhất thức đối xứng ta được = n ∑ j=0 ( N j )( n n− j ) và sau đó dùng phép nhân chập Vandermonde = ( N+n n ) Ví dụ 1.2.8. Đôi khi tồn tại thương của hai hệ số nhị thức mà cả hai đều chứa chỉ số của phép lấy tổng. Dãy số fn = (−1)n ( N n )−1 có biến đổi qua phép nghịch đảo nhị thức là dãy gn = n ∑ j=0 ( n j ) (−1) j f j 28 = n ∑ j=0 ( n j ) (−1) j(−1) j ( N j )−1 = n ∑ j=0 (n j )(N j ) Ở đây chúng ta áp dụng đồng nhất thức tập con của một tập con( N n )( n j ) = ( N j )( N− j n− j ) và có được gn = n ∑ j=0 (n j )(N n )(n j )/(N− j n− j ) = ( N n )−1 n ∑ j=0 ( N− j n− j ) có thể đơn giản hóa bằng cách sử dụng đồng nhất thức tổng đường chéo = ( N n )−1(N+1 n ) = N+1 N−n+1 29 Chương 2 Một số ứng dụng của số nhị thức trong thống kê Thống kê là khoa học nghiên cứu các phương pháp thu thập, phân tích và xử lý các số liệu nhằm phát hiện các quy luật thống kê trong tự nhiên và xã hội. Trong thống kê, giá trị trung bình, phương sai, độ lệch chuẩn, ... là các số đặc trưng để thu được các thông tin quan trọng. Các số đặc trưng này phản ánh những khía cạnh khác nhau của dấu hiệu điều tra và có mối liên hệ mật thiết với các số nhị thức. Vì vậy trong chương này tác giả xin trình bày một số ứng dụng của số nhị thức trong thống kê để thấy rõ hơn về mối quan hệ đó. 2.1 Một số khái niệm của xác suất Xác suất và các biến ngẫu nhiên Một số định nghĩa cơ bản được nhắc lại từ cơ sở của thống kê và xác suất. Định nghĩa 2.1.1. Không gian xác suất rời rạc là một cặp 〈Ω,Pr〉 xác định như sau: • Tập rời rạc Ω được gọi là không gian mẫu. • Một tập hợp con của Ω được gọi là biến cố. 30 • Tập 2Ω của tất cả các tập con của Ω được gọi là không gian biến cố. • Hàm xác suất Pr : 2Ω −→ R được gọi là độ đo xác suất, thỏa mãn các tiên đề sau: 1. 0 ≤ Pr(A) ≤ 1, với mọi biến cố A ⊆ Ω. Số Pr(A) được gọi là xác suất của biến cố A. 2. Pr(Ω) = 1. 3. Nếu các biến cố As, với s ∈ S là các tập con đôi một rời nhau của Ω thì Pr(∪As s∈S ) =∑ s∈S Pr(As) . Định nghĩa 2.1.2. Một biến ngẫu nhiên X trên một không gian mẫu là một hàm giá trị thực. Nó được gọi là biến ngẫu nhiên rời rạc nếu tập các giá trị của nó là hữu hạn hoặc vô hạn đếm được. Ký hiệu: Giả sử X : Ω−→ R là một biến ngẫu nhiên rời rạc trên một không gian mẫu Ω với độ đo xác suất là Pr. Với x ∈ R, xác suất của tập {ω ∈Ω | X(ω) = x} được ký hiệu là Pr(x). Giá trị trung bình và phương sai. Giá trị trung bình của một biến ngẫu nhiên, hay còn gọi là giá trị kỳ vọng, thường được mô tả như trung bình có trọng số. Phương sai và độ lệch chuẩn là số đo sự phân tán từ giá trị trung bình. Định nghĩa 2.1.3. Giả sử X : Ω−→R là một biến ngẫu nhiên rời rạc trên một không gian mẫu Ω với độ đo xác suất Pr, và giả sử D là tập các giá trị của X. Giá trị kỳ vọng hoặc giá trị trung bình của biến ngẫu nhiên X được 31 ký hiệu là E(X) hoặc µX , là tổng E(X) = µX = ∑ x∈D x ·Pr(x) (2.1) Định nghĩa 2.1.4. Giả sử X : Ω−→R là một biến ngẫu nhiên rời rạc trên một không gian mẫu Ω với độ đo xác suất Pr, và giả sử D là tập các giá trị của X. Phương sai của biến ngẫu nhiên X được ký hiệu là V(X) hoặc σ2X là tổng V (X) = σ2X = ∑ x∈D (x−µX)2 ·Pr(x) = E([X−µX ]2). (2.2) Định nghĩa 2.1.5. Giả sử X : Ω−→R là biến ngẫu nhiên rời rạc. Độ lệch chuẩn của biến ngẫu nhiên X ký hiệu là SD(X) hoặc σX là căn bậc hai của phương sai. SD(X) = σX = √ σ2X . (2.3) Các chỉ số giá trị trung bình và phương sai có thể được ký hiệu ngắn gọn là µ và σ2. Định nghĩa 2.1.6. Khi tính toán giá trị trung bình của một bảng các số hoặc phương sai của một bảng các số, mỗi một phần tử của bảng được xem bình đẳng như nhau. Mệnh đề 2.1.7. Giả sử X : Ω−→ R là biến ngẫu nhiên rời rạc. Khi đó σ2X = E(X 2)−µ2. (2.4) 2.2 Phân bố nhị thức Thí nghiệm điển hình trong đó xuất hiện phân bố nhị thức là một dãy n lần tung đồng tiền. Chọn một trong những khả năng xuất hiện của một lần 32 tung, chẳng hạn, mặt trước, là "thành công", thì số lần xuất hiện mặt trước có phân bố nhị thức. Chúng ta áp dụng các đồng nhất thức của các số nhị thức của chương 1 để tính giá trị trung bình và phương sai của phân bố nhị thức. Định nghĩa 2.2.1. Biến ngẫu nhiên rời rạc X có phân phối nhị thức B(n, p) nếu X biểu thị số lần xuất hiện sự kiện A nào đó trong dãy n phép thử độc lập Becnuli với xác suất để xuất hiện A trong mỗi phép thử đều bằng p. Khi đó: Pr(X = j) = ( n j ) p j(1− p)n− j. (2.5) Mệnh đề 2.2.2. Giá trị kỳ vọng của biến ngẫu nhiên nhị thức X trên n phép thử, mỗi phép thử có xác suất thành công p là E(X) = np Chứng minh. Phương trình (2.1) xác định giá trị kỳ vọng E(X) = n ∑ j=0 j ·Pr(X = j) Chúng ta thay xác suất của biến ngẫu nhiên nhị thức như đã được cho bởi phương trình (2.5) = n ∑ j=0 j ( n j ) p j(1− p)n− j Sự hấp thu loại trừ 1 trong 4 lần xuất hiện chỉ số j của tổng = n ∑ j=0 n ( n−1 j−1 ) p j(1− p)n− j = np n ∑ j=0 ( n−1 j−1 ) p j−1(1− p)n− j. Thay i= j−1 đưa đến tổng = np n−1 ∑ i=0 ( n−1 i ) pi(1− p)n−1−i 33 mà ta nhận ra là một khai triển nhị thức, và rút gọn = np [p+(1− p)]n−1 = np. Mệnh đề 2.2.3. Phương sai của biến ngẫu nhiên nhị thức X trong n phép thử với xác suất thành công p là: V (X) = np(1− p) Chứng minh. Một lần nữa ta bắt đầu từ phương trình (2.1) E(X2) = n ∑ j=0 j2 ·Pr(X = j) = n ∑ j=0 j2 ( n j ) p j(1− p)n− j. Một lần nữa chỉ số j của tổng xuất hiện 4 lần. Áp dụng sự hấp thu làm giảm số mũ của j trong một lần xuất hiện là một bước hợp lý. = n ∑ j=0 jn ( n−1 j−1 ) p j(1− p)n− j = np n ∑ j=0 j ( n−1 j−1 ) p j−1(1− p)n− j. Thay i = j− 1 để sắp xếp các chỉ số của các hệ số nhị thức với giới hạn trên và dưới của tổng là một bước hợp lý khác. = np n−1 ∑ i=0 (1+ i) ( n−1 i ) pi(1− p)n−1−i Chia tổng này giống như ở đây = np n−1 ∑ i=0 ( n−1 i ) pi(1− p)n−1−i+np n−1 ∑ i=0 i ( n−1 i ) pi(1− p)n−1−i 34 Vì tổng trong phần thứ nhất đã được nhận thấy như là một khai triển nhị thức = np+np n−1 ∑ i=0 i ( n−1 i ) pi(1− p)n−1−i Áp dụng sự hấp thu một lần nữa để loại trừ sự xuất hiện của chỉ số tổng = np+np n ∑ i=0 (n−1) ( n−2 i−1 ) pi(1− p)n−1−i Thay k = i− 1 rồi sắp xếp lại chỉ số dưới của hệ số nhị thức với giới hạn dưới của tổng. = np+n(n−1)p2 n ∑ k=0 ( n−2 k ) pk(1− p)n−2−k = np+n(n−1)p2 = np+n2p2−np2 = n2p2+np(1− p). Theo mệnh đề 2.1.7 và 2.2.2 σ2X = E(X 2)−E(X)2 = [ n2p2+np(1− p) ] −n2p2 = np(1− p). Ước lượng không chệch của giá trị trung bình Một phương pháp thống kê trực quan để ước lượng tỷ lệ cá thể trong một tập hợp có kích thước lớn N có đặc điểm đặc trưng ( chẳng hạn như có sở thích về toán học) là lấy một mẫu ngẫu nhiên và sử dụng tỷ lệ trong mẫu đó để ước lượng tỷ lệ trong tập hợp tổng quát. Chúng ta sẽ sử dụng đồng nhất thức của các số nhị thức để khẳng định tính đúng đắn của cách tiếp cận này. 35 Định nghĩa 2.2.4. Ước lượng θ̂ của đặc trưng thống kê θ của một tập hợp được gọi là ước lượng không chệch nếu giá trị kỳ vọng E(θ̂) của mẫu ngẫu nhiên bằng θ . Mệnh đề 2.2.5. Tỷ lệ mẫu là một ước lượng không chệch của tỷ lệ các cá thể có đặc trưng cho trước và tập hợp đầy đủ các đối tượng. Chứng minh. Giả sử rằng trong một tập hợp đối tượng kích thước N có đúng M cá thể có đặc điểm đang xét. Một mẫu cỡ n được lấy. Biến ngẫu nhiên được quan tâm là số m các cá thể với đặc điểm đang xét và tỷ lệ X = m n của những cá thể với đặc điểm đang xét. Tổng số các cách để chọn một mẫu kích thước n là ( N n ) . Số cách chọn một mẫu kích thước n sao cho có thể có đúng j cá thể với đặc điểm quy định là tích ( M j )( N−M n− j ) của số cách chọn j cá thể từ tập độ lớn M với đặc điểm đang xét và số cách chọn n− j cá thể còn lại từ tập N−M cá thể không có đặc điểm đang xét. Vì vậy Pr(m= j) = (M j )(N−M n− j )(N n ) Theo đó, E(X) = n ∑ j=0 j n ·Pr(m= j) = 1 n n ∑ j=0 j · (M j )(N−M n− j )(N n ) 36 = 1 n ( N n )−1 n ∑ j=0 j · ( M j )( N−M n− j ) Áp dụng đồng nhất thức hấp thu để loại bỏ một lần xuất hiện của chỉ số tổng = 1 n ( N n )−1 n ∑ j=0 M · ( M−1 j−1 )( N−M n− j ) = M n ( N n )−1 n ∑ j=0 ( M−1 j−1 )( N−M n− j ) Bây giờ sử dụng phép nhân chập Vandermonde = M n ( N n )−1(N−1 n−1 ) = M n · n! Nn · (N−1) n−1 (n−1)! = M N Như vậy, phương pháp trực quan ước lượng giá trị trung bình là không chệch. Ước lượng không chệch của phương sai Giả sử X là một biến ngẫu nhiên trên không gian mẫu Ω. Các biến ngẫu nhiên phân bố đồng nhất X1 X2 · · · Xn là các giá trị của X trên n mẫu từ Ω, với giá trị trung bình mẫu X . Các nhà thống kê sử dụng các ước lượng σ̂2 = ∑ (Xi−X)2 n−1 = ∑X2i −n−1(∑Xi)2 n−1 với n−1 ở mẫu số (chứ không phải n) cho phương sai. Điều này được giải th