CHƯƠNG 2. PHÉP ĐẾM

Nội dung chương 2: Các nguyên lý; Giải tích tổ hợp; Hoán vị lặp; Tổ hợp lặp.
Nội dung trích xuất từ tài liệu:
CHƯƠNG 2. PHÉP ĐẾM Cơ sở LogicCHƯƠNG 2. PHÉP ĐẾM •Các nguyên lý •Giải tích tổ hợp •Hoán vị lặp •Tổ hợp lặpI.Các nguyên lý 3+5=8 cách2. Nguyên lý nhân Giả sử công việc nào đó được chia thành k giai đọan thực hiện: Giai đọan 1: có n1 cách thực hiện Giai đọan 2: có n2 cách thực hiện …………. Giai đọan k: có nk cách thực hiện Khi đó, số cách thực hiện cả công việc là: n1.n2…nkVí dụ:Có 3 cách đi từ thành phố A đến thành phố B, có 5cách đi từ thành phố B đến thành phố C và có 2 cáchđi từ thành phố C đến thành phố D. Hỏi có bao nhiêucách đi từ thành phố A đến thành phố D ? 1 1 2 1 A B C 2 3 D 3 4 2 5 n = 3.5.2 = 30 cách Hình 1Cách phát biểu khác:Có n con thỏ được nhốt vào k cái lồng. Khi đó tồntại (ít nhất một) cái lồng chứa không ít hơn ncon thỏ. k• Đặc biệt, nếu số thỏ lớn hơn số lồng (n > k) thìtồn tại lồng chứa ít nhất 2 con thỏ.Bài tập•Các nguyên lý•Giải tích tổ hợp•Hoán vị lặp•Tổ hợp lặpII. Giải tích tổ hợpCho tập hợp A gồm n phần tử. Mỗi cách sắp đặt cóthứ tự n phần tử của A được gọi là một hoán vị củan phần tử.Số các hoán vị của n phần tử, ký hiệu là Pn Pn = n! = 1.2.3…(n-2).(n-1).nQuy ước: 0! = 1Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phầntử (1≤k≤n) sắp thứ tự của tập hợp A được gọi là mộtchỉnh hợp chập k của n phần tử.Số các chỉnh hợp chập k của n phần tử ký hiệu là: AnkCông thức: n! An  k (n  k )!Ví dụ: