Bài giảng Xác suất thống kê - Chương 0: Đại số tổ hợp

ĐẠI SỐ TỔ HỢP NGUYÊN LÝ NHÂN	(Xem)	Ví dụ 0.1 (Xem) CHỈNH HỢP 	(Xem)	Ví dụ 0.2 (Xem) TỔ HỢP 	(Xem) 	Ví dụ 0.3 (Xem) NGUYÊN LÝ CỘNG 	(Xem) 	Ví dụ 0.4 (Xem) HOÁN VỊ 	(Xem) 	Ví dụ 0.5 (Xem) PHÂN HOẠCH 	(Xem)	Ví dụ 0.6 (Xem) NHỊ THỨC NEWTON 	(Xem) 	Ví dụ 0.7 (Xem) NGUYÊN LÝ NHÂN Một công việc được chia ra k giai đoạn thực hiện, k = 1,2,... Mỗi giai đoạn có ni cách thực hiện (độc lập), i = 1,2,...,k. Vậy số cách (phương án) thực hiện công việc là n = n1.n2...nk hay Một biểu đồ hình cây thường được dùng trong mối quan hệ với nguyên lý nhân. Ví dụ 0.1. Một người đàn ông có 2 áo sơ- mi và 4 cà-vạt thì có bao nhiêu cách để người này chọn 1 áo sơ-mi và 1 cà-vạt? ta có thể chia công việc trên thành hai giai đoạn và theo nguyên lý nhân ta có 24 = 8 cách chọn một áo sơ-mi và một cà-vạt. ta có biểu đồ hình cây với S là áo sơ-mi và T là cà-vạt NGUYÊN LÝ NHÂN Một tập có n phần tử khác nhau. Một chỉnh hợp chập k là một dãy có thứ tự gồm k phần tử khác nhau được chọn từ n phần tử (k  n). Ký hiệu Akn là số chỉnh hợp chập k được chọn từ n phần tử. Công thức CHỈNH HỢP Ví dụ 0.2. Từ 7 mẫu tự A, B, C, D, E, F, G. Chọn ra 3 mẫu tự, có bao nhiêu từ (không cần nghĩa) được tạo thành từ 7 mẫu tự trên? Do 3 mẫu tự chọn từ 7 mẫu tự trên có kể đến thứ tự, nghĩa là ABC, BAC, CAB,... Như vậy số từ được tạo thành từ 7 mẫu tự trên là một chỉnh hợp chập 3 của 7 phần tử Vậy số từ là CHỈNH HỢP Một tập hợp có n phần tử khác nhau. Một tổ hợp chập k là một dãy không phân biệt thứ tự gồm k phần tử khác nhau được chọn từ n phần tử (k  n). Ký hiệu Ckn số tổ hợp chập k từ n phần tử. Công thức TỔ HỢP Ví dụ 0.3. Có bao nhiêu cách thành lập một hội đồng (gồm 3 nam và 4 nữ) khác nhau từ 8 nam và 6 nữ? Ta có thể chia công việc trên làm 2 giai đoạn: chọn 3 nam từ 8 nam và 4 nữ từ 6 nữ, do cách chọn không kể thứ tự nên ta sử dụng cách đếm của tổ hợp Áp dụng nguyên lý nhân, ta có số cách thành lập một hội đồng là TỔ HỢP Một công việc được chia ra k trường hợp. Mỗi trường hợp có ni cách thực hiện, i= 1, 2, ..., k. Không có cách thực hiện nào của trường hợp này trùng với cách thực hiện của trường hợp khác. Số cách thực hiện công việc là: n = n1 + n2 + ... + nk NGUYÊN LÝ CỘNG Ví dụ 0.4. Một nhóm gồm 10 sinh viên, trong đó có 4 nam, đăng ký mua vé tàu về quê. Phòng bán vé chỉ còn 4 vé, hỏi có bao nhiêu cách phân phối vé cho 10 sinh viên trên, với ưu tiên có ít nhất 1 nữ được mua vé? Có thể chia 4 trường hợp: 1 nữ và 3 nam; 2 nữ và 2 nam; 3 nữ và 1 nam; 4 đều là nữ. Mỗi trường hợp áp dụng nguyên lý nhân và cuối cùng áp dụng nguyên lý cộng, ta có NGUYÊN LÝ CỘNG 	Một tập có n phần tử khác nhau. Một hoán vị của n phần tử là sự sắp xếp n phần tử đó thành một dãy theo một thứ tự nào đó (mỗi phần tử chỉ xuất hiện một lần trong dãy). Ký hiệu: Pn là số hoán vị n phần tử. Công thức:	 Pn = n! HOÁN VỊ Ví dụ 0.5. Có 3 bộ sách: bộ thứ nhất có 6 tập; bộ thứ hai có 2 tập và bộ thứ ba có 3 tập. Tất cả được đặt lên một giá sách, có bao nhiêu cách sắp nếu: Sắp tùy ý, Các tập được đặt theo từng bộ, 3 tập được chỉ định phải xếp cùng nhau, 2 tập được chỉ định phải xếp cuối cùng. HOÁN VỊ Sắp tùy ý. Mỗi cách sắp là một hoán vị 11 phần tử. Suy ra số cách sắp tùy ý là P11 = 11! Sắp theo bộ Mỗi bộ sách là một phần tử lớn.  Có n1 = 3! cách sắp xếp 3 phần tử này. Các tập sách trong mỗi bộ sách có thể hoán vị với nhau. 	 có n2= 6! 2! 3! cách sắp Vậy số cách sắp: n= n1n2= 3! 6! 2! 3! HOÁN VỊ 3 tập được chỉ định phải xếp cùng nhau 3 tập được chỉ định được xếp cùng nhau xem như là một phần tử cùng xếp với 8 tập còn lại, ta có n1 = P9 = 9! Cách xếp của 3 tập được chỉ định được xếp cùng nhau, ta có n2 = P3 = 3! Vậy số cách sắp: n= n1n2= 9! 3! 2 tập được chỉ định phải xếp cuối cùng 2 tập được chỉ định xếp cuối cùng có 2! Cách và với cách xếp của 9 tập còn lại (9!) nên ta có số cách xếp là 2! 9! HOÁN VỊ Một tập có n phần tử khác nhau, trong đó có n1 phần tử cùng một loại (giữa chúng không phân biệt được), có n2 phần tử cùng một loại thứ hai,..., có nk phần tử cùng một loại thứ k. n = n1 + n2 + ... + nk Số phân hoạch là QUY TẮC PHÂN HOẠCH VÍ DỤ 0.6. Năm bi đỏ, hai bi trắng và ba bi xanh được sắp trên một hàng. Nếu các viên bi có cùng màu không thể phân biệt được thì có bao nhiêu cách khác nhau để sắp các viên bi trên cùng một hàng? Theo quy tắc phân hoạch, ta có số cách sắp các viên bi trên theo yêu cầu như sau QUY TẮC PHÂN HOẠCH Công thức khai triển 	Khai triển nhị thức trên ta thu được cách sắp của các hệ số, được gọi là tam giác Pascal n = 1	1 n = 2	1	2	1 n = 3	1	3	3	1 n = 4	1	4	6	4	1 n = 5	1	5	10	10	5	1 n = 6	1	6	15	20	15	6	1 NHỊ THỨC NEWTON VÍ DỤ 0.7. Tìm số hạng là hằng số trong khai triển của Theo công thức khai triển nhị thức, ta có Số hạng là hằng số khi 3k – 12 = 0  k = 4 Vậy: NHỊ THỨC NEWTON NGUYỄN CÔNG TRÍEmail: nctri@ueh.edu.vn