Chương 1: GiẢI TÍCH KẾT HỢP

Bài toán của giải tích kết hợp : Từ tập hợp { a1, …, an } lập các nhóm gồm k phần tử với điều kiện nào đó và tính số các nhóm được tạo thành. Qui tắc cộng : Nếu công việc 1 có n1 cách thực hiện, công việc 2 có n2 cách thực hiện và các cách thực hiện công việc 1 không trùng với bất kỳ cách thực hiện công việc 2 nào thì có n1 + n2 cách thực hiện “công việc 1 hoặc công việc 2”.
Nội dung trích xuất từ tài liệu:
Chương 1:GiẢI TÍCH KẾT HỢPChương 1:GiẢI TÍCH KẾT HỢPI. Các khái niệm cơ bảnBài toán của giải tích kết hợp :Từ tập hợp { a1, …, an } lập các nhóm gồm kphần tử với điều kiện nào đó và tính số cácnhóm được tạo thành.Qui tắc cộng :Nếu công việc 1 có n1 cách thực hiện, côngviệc 2 có n2 cách thực hiện và các cách thựchiện công việc 1 không trùng với bất kỳ cáchthực hiện công việc 2 nào thì có n1 + n2 cáchthực hiện “công việc 1 hoặc công việc 2”.Qui tắc nhân :Nếu công việc 1 có n1 cách thực hiện và ứng vớimỗi cách đó có n2 cách thực hiện công việc 2 thìcó n1 × n2 cách thực hiện “công việc 1 rồi côngviệc 2”.Nhóm có thứ tự :Khi đổi vị trí các phần tử khác nhau của nhóm nàyta nhận được nhóm khác.Nhóm không thứ tự :Khi đổi vị trí các phần tử khác nhau của nhóm nàyta không nhận được nhóm khác.Nhóm có lặp :Các phần tử của nhóm có thể có mặt nhiều lầntrong nhóm.Nhóm không lặp :Các phần tử của nhóm chỉ có mặt một lần trongnhóm.II. Các công thức thường dùng1. Chỉnh hợp chập k từ n phần tử là nhóm khônglặp, có thứ tự gồm k phần tử từ n phần tử đã cho.Số chỉnh hợp : k = n( n − 1)...[n − ( k − 1)] An2. Chỉnh hợp lặp chập k từ n phần tử là nhómcó lặp, có thứ tự gồm k phần tử từ n phần tử đãcho.Số chỉnh hợp lặp : k = nk An3. Hoán vị của n phần tử là nhóm có thứ tự gồmđủ mặt n phần tử đã cho.Số hoán vị: Pn = n!4. Tổ hợp chập k từ n phần tử là nhóm không lặp,không thứ tự gồm k phần tử từ n phần tử đã cho.Số tổ hợp : Ak Cn = n k (1) k! n! C= k (2) k !( n − k )! n5. Tổ hợp lặp chập k từ n phần tử là nhóm cólặp, không thứ tự gồm k phần tử từ n phần tử đãcho.Số tổ hợp lặp : C =C k k n + k −1 nIII. Nhị thức Newton n ∑ C nk a k b n − k (a + b)n = k =0Thí dụ : (a +b)2 = C2 a0 b2−0 + C2 a1 b2−1 + C2 a2 b2−2 0 1 2 = b + 2ab + a 2 2