Bài giảng Lý thuyết xác suất và thống kê toán học - Chương 1: Một số kiến thức cơ bản về giải tích tổ hợp và nhị thức Newton - Phan Văn Tân

10:04:54 LÝ THUYẾT XÁC SUẤT VÀ THỐNG KÊ TOÁN HỌC Phan Văn Tân Bộ mô Khí tượng 10:04:54 GIỚI THIỆU • “Lý thuyết xác suất & thống kê toán học” là một trong 3 môn học bổ sung cho sinh viên các ngành Khí tượng, Thủy văn và Hải dương học: o Phương pháp tính o Cơ chất lỏng o Lý thuyết xác suất & thống kê toán học • Số đơn vị học trình: 3 (45 tiết) • Tài liệu tham khảo: • Hình thức thi: Vấn đáp (Lý thuyết + Bài tập) 10:04:54 QUI ƯỚC Tuyệt đối không sử dụng điện thoại di động trong giờ học 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ NHN THỨC N EWTON • Trong thực tế thường gặp bài toán: Cho một tập hợp hữu hạn, đòi hỏi ghép các phần tử lại thành từng nhóm theo quy luật nào đó tuỳ thuộc vào nội dung của bài toán, và tính số nhóm tạo thành. • Giải tích tổ hợp là ngành toán học chuyên nghiên cứu các loại bài toán này 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON 1.1 Chỉnh hợp • Ví dụ: Cho ba chữ số 2, 3, 5. Hỏi có thể tạo được bao nhiêu số có 2 chữ số khác nhau từ ba chữ số đã cho • Giải: Từ các số 2 3 5 o Lấy 2 ghép với 3 hoặc với 5 ta được 23, 25; o Lấy 3 ghép với 2 hoặc với 5 ta được 32, 35; o Lấy 5 ghép với 2 hoặc với 3 ta được 52, 53 Kết quả ta thu được 6 số tất cả. o Để ý rằng mỗi số tạo thành là một nhóm có thứ tự gồm 2 trong 3 số đã cho. o Mỗi nhóm như vậy được gọi là một chỉnh hợp chập 2 từ 3 phần tử 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON Định nghĩa 1. Ta gọi chỉnh hợp chập k từ n phần tử đã cho (k < n) là một nhóm có thứ tự gồm k phần tử khác nhau lấy từ n phân tử đã cho • N hư vậy từ n phần tử ta có thể tạo nên nhiều chỉnh hợp • N ếu dùng ngôn ngữ tập hợp thì chỉnh hợp chập k từ n phần tử là một tập con được sắp thứ tự của tập hợp n phần tử đã cho • Số lượng chỉnh hợp chập k có thể được tạo nên từ n phần được ký hiệu là Ank 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON Công thức tổng quát tính Ank • Giả sử tập đã cho gồm n phần tử a1, a2 ... an. • Với k=1: Mỗi phần tử đứng riêng có thể coi là một chỉnh hợp chập 1 • N hư vậy: An1 = n • Với k=2: lấy mỗi chỉnh hợp chập 1 (nghĩa là mỗi phần tử ai) đem ghép với một trong n − 1 phần tử còn lại thì tạo được n − 1 chỉnh hợp chập 2 • N hư vậy: An2 = n(n-1) • Tương tự ta có: An3 = n(n-1)(n-2) • Hay, tổng quát: Ank = n(n-1)(n-2)(n-k+1) • Cũng có thể thu được công thức trên theo cách khác: o Ta có n cách chọn phần tử đứng đầu, kết hợp với (n-1) cách chọn phần tử đứng thứ hai, v.v., và kết hợp với (n-k+1) cách chọn phần tử đứng thứ k o Vì vậy có tất cả n(n − 1) ... (n − k + 1) chỉnh hợp chập k của n 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON Ví dụ 1: Tính A53 • Ta có: A53 = 5.4.(5−3+1) = 5.4.3 = 60 Ví dụ 2. Một lớp phải học 10 môn, mỗi ngày học 2 môn. Hỏi có bao nhiêu cách xếp thời khóa biểu trong một ngày • Một cách xếp thời khoá biểu trong một ngày là việc ghép 2 môn trong 10 môn với nhau o 2 môn phải khác nhau o với mỗi nhóm 2 môn thì thứ tự sắp xếp khác nhau là khác nhau • Vì thế mỗi cách xếp ứng với một chỉnh hợp chập 2 của 10 phần tử • Vậy, có tất cả A102 = 10.(10-2+1) = 10.9 = 90 (cách) 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON 1.2 Chỉnh hợp lặp • Trong định nghĩa chỉnh hợp, đòi hỏi mỗi phần tử chỉ được có mặt trong nhóm không quá một lần. N ếu bỏ qua hạn chế ấy thì ta có khái niệm chỉnh hợp lặp Định nghĩa: Chỉnh hợp lặp chập k của n phần tử là một nhóm có thứ tự gồm k phần tử lấy từ n phần tử đã cho, trong đó mỗi phần tử có thể có mặt 1, 2,..., k lần trong nhóm tạo thành Chú ý: Vì mỗi phần tử có thể xuất hiện nhiều lần trong một chỉnh hợp lặp nên ở đây k có thể lớn hơn n 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON • Ví dụ: Cho ba chữ số 2, 3, 5. Hỏi có thể tạo được bao nhiêu số có 2 chữ số từ ba chữ số đã cho • Giải: Từ các số 2 3 5 o Lấy 2 ghép lần lượt với 2,3,5 ta được 22, 23, 25; o Lấy 3 ghép lần lượt với 2,3,5 ta được 32, 33, 35; o Lấy 5 ghép lần lượt với 2,3,5 ta được 52, 53, 55 o Kết quả ta thu được 9 số tất cả. o Để ý rằng mỗi số được tạo thành là một nhóm gồm 2 chữ số không nhất thiết khác nhau lấy từ 3 số đã cho và mỗi chữ số có thể xuất hiện 2 lần o Mỗi nhóm như vậy được gọi là một chỉnh hợp lặp chập 2 từ 3 phần tử • Số chỉnh hợp lặp chập k từ n phần tử được ký hiệu là knA ~ 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON Công thức tổng quát tính • Để có một chỉnh hợp lặp k ta có thể: o Có n cách chọn phần tử đứng ở vị trí thứ nhất o Tương tự, có n cách chọn phần tử đứng ở vị trí thứ hai (vì mỗi phần tử có thể được chọn nhiều lần) o v.v o Có n cách chọn phần tử đứng ở vị trí thứ k o Vậy: k nA ~ kk n nnnnA == .....~ 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON • Ví dụ 1: Để đăng ký số máy cho một loại máy mới, người ta dùng 3 con số trong 9 con số: 1,2,3...,9. Hỏi có thể đánh số được bao nhiêu máy? • Giải: Ở đây mỗi số máy của một máy là một chỉnh hợp lặp chập 3 từ 9 phần tử đã cho. Vậy, số lượng máy có thể đánh số được là 7299~ 339 ==A 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON • Ví dụ 2. Để truyền tin bằng tín hiệu moóc-xơ gồm hai ký hiệu chấm (.) và vạch (−), người ta mã hoá mỗi chữ cái của bảng chữ cái thành một nhóm có thứ tự gồm không quá 4 ký hiệu. Biết rằng một ký hiệu có thể có mặt nhiều lần trong nhóm có thứ tự tạo thành. Hỏi có thể mã được bao nhiêu chữ cái ? • Giải: Mỗi nhóm có thứ tự gồm k ký hiệu (1 ≤ k ≤ 4) tạo nên chính là một chỉnh hợp lặp chập k từ 2 phần tử đã cho (hai phần tử này là các ký hiệu chấm (.) và vạch (−)). Vì vậy số chữa cái mã được là: 30168422222~~~~ 432142 3 2 2 2 1 2 =+++=+++=+++ AAAA 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON • Ví dụ 3. Mỗi ký tự trong bảng mã ASCII (American Standard Code for Information Interchange) được tạo thành bởi một dãy 8 bit. Bit là một đại lượng chỉ trạng thái; trong hệ cơ số nhị phân nó nhận một trong hai giá trị (0, 1). Hỏi có bao nhiêu ký tự trong bảng mã ASCII? • Giải: Trong hệ cơ số nhị phân, số thứ tự của các ký tự trong bảng mã ASCII được xác định bởi một dãy 8 chữ số 0-1. Các số đó là 0000 0000, 0000 0001,, 1111 1110, 11111111. Tức số ký tự trong bảng mã ASCII là 2562~ 882 ==A 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON • Ví dụ 4. Trong máy tính, số nguyên có dấu là số được tạo bởi một dãy các bit (0-1), trong đó bit đầu tiên xác định dấu (1- âm, 0- dương), dãy các bit tiếp theo xác định giá trị của số. Hãy cho biết giá trị lớn nhất, nhỏ nhất (phạm vi biến thiên) của: 1) Số nguyên 1 byte (8 bit); 2) Số nguyên 2 byte (16 bit); 3) Số nguyên 4 byte (32 bit); 4) Số nguyên 8 byte (64 bit). • Giải: Về nhà 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON 1.3 Hoán vị Định nghĩa: Hoán vị của n phần tử là một nhóm có thứ tự gồm đầy đủ tất cả các phần tử đã cho • Các hoán vị của n phần tử chỉ khác nhau bởi thứ tự sắp xếp giữa các phần tử • Một hoán vị của n phần tử cũng chính là một chỉnh hợp chập n của n phân tử • Do đó số hoán vị có thể tạo nên từ n phần tử sẽ là Pn = Ann = n(n-1)(n-2)(n-n+1) = n(n-1)(n-2)3.2.1 Pn = n! 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON • Ví dụ 1. Một phòng thi có 30 chỗ ngồi. Hỏi có bao nhiêu cách đánh số báo danh cho 30 thí sinh? • Giải: Số cách đánh số báo danh bằng số hoán vị của 30 vị trí. Vậy có tất cả 30! cách đánh. • Ví dụ 2: Phòng họp có n chỗ ngồi được bố trí theo hình chữ U hướng về bàn chủ tọa. Trong số n người đến dự có hai người quen nhau. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi để hai người đó ngồi cạnh nhau? • Giải: Hai người quen nhau ngồi cạnh nhau có thể được xem như bị “ghép đôi” thành một người. Do đó, số cách sắp xếp sẽ là số hoán vị của (n-1), tức bằng 2(n-1)! 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON • Ví dụ 3. Trong số n người đến dự “hội nghị bàn tròn” có hai người quen nhau. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi để hai người đó được ngồi cạnh nhau? • Giải: Về nhà 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON 1.4 Tổ hợp Định nghĩa: Tổ hợp chập k từ n phần tử (k ≤ n) là một nhóm không phân biệt thứ tự gồm k phần tử khác nhau trích từ n phần tử đã cho. • Cũng có thể hiểu một tổ hợp chập k là tập con gồm k phần tử của tập n phần tử đã cho • Một tổ hợp cũng là một chỉnh hợp, trong đó các chỉnh hợp chỉ khác nhau về thứ tự sắp xếp thì được coi là một tổ hợp • Số tổ hợp chập k từ n phần tử được ký hiệu là knC 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON Công thức tổng quát tính • Giả sử từ n phần tử đã cho ta tính được Cnk tổ hợp chập • Mỗi tổ hợp đó là một tập con gồm k phần tử trích từ n phần tử ban đầu, nhưng không sắp thự tự • Đối với mỗi tổ hợp đó ta tiến hành hoán vị các phần tử theo mọi cách sẽ được tất cả k! chỉnh hợp • N hư vậy đối với Cnk tổ hợp sẽ có tất cả k!Cnk chỉnh hợp chập k, tức là: k!Cnk = Ank • Hay k nC ! )1)...(2)(1( ! k knnnn k AC k nk n +−−−== 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON • Biến đổi lại ta có: ! )1)...(2)(1( ! k knnnn k AC k nk n +−−−== )!(! ! )!(! 1.2)...1)()(1)...(2)(1( ! knk n knk knknknnnn k AC k nk n −=− −−−+−−−== • Ví dụ: Một giải bóng đá được tổ chức thành 5 bảng A, B, C, D, E, mỗi bảng có 6 đội. Trong vòng loại, các đội trong từng bảng thi đấu theo thể thức “đấu vòng”. Hỏi có tất cả bao nhiêu trận đấu ở vòng loại? • Giải: Trong mỗi bảng, mỗi trận đấu ứng với một nhóm gồm 2 phần tử trong 6 phần tử (không biệt thứ tự). Vì vậy mỗi bảng sẽ có số trận đấu là • Î Có tất cả 15 x 5 = 75 trận đấu loại 15 2 5.6 !4.2 !4.5.6 )!26(!2 !62 6 ===−=C 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON • Các tính chất của tổ hợp • Sử dụng công thức • dễ dàng suy ra: 10 == nnn CC knnkn CC −= k n k n k n CCC 1 1 1 − − − += )!(! ! )!(! 1.2)...1)()(1)...(2)(1( ! knk n knk knknknnnn k AC k nk n −=− −−−+−−−== 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON 1.5 Nhị thức Newton ... 33)( 2)( 33)( 2)( 32233 222 32233 222 babbaaba bababa babbaaba bababa −+−=− +−=− +++=+ ++=+ Một số hằng đẳng thức đáng nhớ quen thuộc • Bằng phép nhân đa thức sẽ thu được các khái triển (a+b)4, (a+b)5, (a-b)4, (a-b)5,... • Î Cần xác định được biểu thức tổng quát tính (a+b)n, với n nguyên dương bất kỳ • Để ý rằng số mũ của biểu thức vế trái có mối liên hệ với số mũ và các hệ số của các hạng tử vế phải: o Tổng số mũ của các nhân tử trong từng hạng tử bằng nhau và bằng số mũ vế trái (n) o Số mũ của a ở vế phải giảm dần từ n đến 0, của b tăng từ 0 đến n o Các hệ số tuân theo một qui luận nào đó mà ta cần xác định được qui luật này 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON 1.5 Nhị thức Newton nkknnnnn bba k knnnbannbnaaba +++−−++−++=+ −−− ... ! )1)...(1(... 2 )1()( 221 Công thức tổng quát Để ý: knCk knnn =+−− ! )1)...(1( nn n kknk n n n n n n n n bCbaCbaCbaCaCba ++++++=+ −−− ......)( 222110Do đó: Hay gọn hơn: ∑ = −=+ n k kknk n n baCba 0 )( 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON 1.5 Nhị thức Newton ∑ = −=+ n k kknk n n baCba 0 )( (x+a)414641 (x+a)31331 (x+a)2121 (x+a)111 (x+a)01 4322344 40312213044 464)( 14641)( babbabaaba babababababa ++++=+ ++++=+ 10:04:54 Chương 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ GIẢI TÍCH TỔ HỢP VÀ N HN THỨC N EWTON Một số bài tập: