Giải tích tổ hợp

Nguyên lý nhân: Một công việc được chia làm k giai đoạn. Cón 1cách hoàn thành giai đoạn 1, Có n2 cách hoàn thành giai đoạn 2, . . . , Có nk cách hoàn thành giai đoạnk. Số cách thực hiện công việc
Nội dung trích xuất từ tài liệu:
Giải tích tổ hợp GIẢI TÍCH TỔ HỢP1.1 Nguyên lý nhân: Một công việc đượcchia làm k giai đoạn. Có n1 cách hoànthành giai đoạn 1, Có n2 cách hoàn thànhgiai đoạn 2, . . . , Có nk cách hoàn thànhgiai đoạn k. Số cách thực hiện công việc n = n1.n2 ...nkVí dụ. Có tất cả bao nhiêu xâu nhị phân cóđộ dài bằng 4?1.2 Hoán vị: Cho A là tập hợp khác ∅ cósố phần tử là n. Một hoán vị của A là mộtcách sặp xếp có thứ tự các phần tử của A.Mệnh đề. Số hoán vị của tập A có n phầntử bằng n!.Ví dụ. Có bao nhiêu cách sắp 5 người vàomột bàn dài có 5 chỗ ngồi.1.3 Chỉnh hợp. Cho A là tập hợp có nphần tử. Một cách sắp xếp có thứ tự mphần tử trong n phần tử của tập hợp A đượcgọi là một chỉnh hợp chập m của n phần tửMệnh đề. Số chỉnh hợp châp m của nphần tử là: m n! An = (n - m)! Ví dụ có bao nhiêu cách sắp xếp 5 cuốnsách khác nhau vào kệ sách có 15 ô.1.4 Chỉnh hợp lặp. Một bộ thứ tự gồm mphần tử không nhất thiết khác nhau cùa 1tập hợp A gồm n phần tử được gọi là mộtchình hợp lặp chập m cùa n phần tử,Mệnh đề. Số chỉnh hợp lặp chập m của nphận từ bằmg: An = n m . mVí dụ. Cho A là tập có n phần tử tính sốtập con của nó1.5 Tổ hợp. Một cách chọn m phần tửtrong một tập hợp gồm n phần tử được gọilà một tổ hợp chập m cùa n phần tử.Mệnh đề. Số tổ hợp chập m của n phần tửbằng: m n! Cn = m!(n - m)!Ví dụ. Có bao nhiêu cách chia 12 cuốnsách cho bốn học sinh mỗi em được 3 cuốn1.6 Tổ hợp lặp: Một nhóm có m phần tửkhông phân biệt thứ tự, có thể trùng nhauđược gọi là một tổ hợp lặp chập m của nphần tử.Mệnh đề. Số tổ hợp lặp chập m của n phầntử bằng. Cn = Cn+ m- 1 = Cn+ 1 - 1 m m n- mĐịnh lý. Số cách chia m vật đồng chấtgiống nhau vào n hộp khác nhau là m C nVí dụ 1. Có bao nhiêu cách chia 10 viên bigiống nhau cho 5 đứa trẻ trong các trườnghợp sau:a. Không có một hạn chế nào. b. Đứa trẻ lớn nhất được ít nhất 2 viên bi.Ví dụ 2. Có bao nhiêu cách chia 10 viên bikhác nhau cho 5 đứa trẻ trong các trườnghợp sau:a. Không có một hạn chế nào. b. Đứa trẻ lớn nhất được ít nhất 2 viên bi.1.7 Phân hoạch: Cho A là tập hợp có nphần tử. Ký hiệu A = n.Một sự phân chia tập A thành những tậpcon A1 , A2 ,K , Ak khác rỗng sao cho: k A= U Ai ; Ai I i= 1 A j = Æ(i ¹ j )Được gọi là một phân hoạch của tâp Athành k tập con.Mệnh đề. Số phân hoạch khác nhau thànhk tập con của tập A là n! n1 !n2 !K nk !