Bài giảng Giải tích tổ hợp

GIẢI TÍCH TỔ HỢP 1.1 Nguyên lý nhân: Một công việc được chia làm k giai đoạn. Có n1 cá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ạn k. Số cách thực hiện công việc Ví 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ột cá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ần tử bằng n!. Ví dụ. Có bao nhiêu cách sắp 5 người vào một bàn dài có 5 chỗ ngồi. 1.3 Chỉnh hợp. Cho A là tập hợp có n phần tử. Một cách sắp xếp có thứ tự m phần tử trong n phần tử của tập hợp A được gọ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 n phần tử là: Ví dụ có bao nhiêu cách sắp xếp 5 cuốn sá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 m phần tử không nhất thiết khác nhau cùa 1 tập hợp A gồm n phần tử được gọi là một chì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 n phận từ bằmg: Ví 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ọi là 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: Ví dụ. Có bao nhiêu cách chia 12 cuốn sách cho bốn học sinh mỗi em được 3 cuốn 1.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 n phần tử. Mệnh đề. Số tổ hợp lặp chập m của n phần tử bằng. Định lý. Số cách chia m vật đồng chất giống nhau vào n hộp khác nhau là Ví dụ 1. Có bao nhiêu cách chia 10 viên bi giống nhau cho 5 đứa trẻ trong các trường hợ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 bi khác nhau cho 5 đứa trẻ trong các trường hợ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ó n phần tử. Ký hiệu Một sự phân chia tập A thành những tập con khác rỗng sao cho: Được gọi là một phân hoạch của tâp A thành k tập con. Mệnh đề. Số phân hoạch khác nhau thành k tập con của tập A là