Chuyên đề Tối ưu hóa bài toán đếm trong đại số tổ hợp

www.MATHVN.com - Toán học Việt Nam

GV: Hoàng Ngọc Hùng - www.mathvn.com 1

Chuyên đề: TỐI ƯU HÓA BÀI TOÁN ĐẾM TRONG ĐẠI SỐ TỔ HỢP I. ĐẶT VẤN ĐỀ Trong kì thi tuyển sinh Đại học năm 2012 và năm 2013 bài toán tổ hợp và xác suất xuất hiện ở đề khối B (câu tổ hợp) và đề khối A (câu xác suất). Điều này đã làm các thí sinh bất ngờ, nhiều em tỏ ra lúng túng và rất khó định hướng cách làm, thậm chí đã trình bày lời giải nhưng không biết rằng lời giải và đáp án của mình liệu có đúng không. Qua nghiên cứu, giảng dạy và học tập kinh nghiệm chúng tôi thiết nghĩ cần có những giải pháp giúp học sinh nắm được bản chất của bài toán tổ hợp, để từ đó học sinh có thêm những công cụ hữu ích giúp cho quá trình tìm lời giải bài toán tổ hợp của học sinh một cách chủ động, chính xác và hiệu quả nhất. Chuyên đề này không có tham vọng giải quyết tất cả các bài toán liên quan đến đại số tổ hợp, chúng tôi chỉ giải quyết một phần của đại số tổ hợp. Nhưng qua chuyên đề này hi vọng rằng các thầy cô giáo và các học sinh có thêm một phần tài liệu quý báu hỗ trợ trong việc tự nghiên cứu, tích lũy chuyên môn, ôn tập và giảng dạy. II. GIẢI QUYẾT VẤN ĐỀ *Bố cục Chuyên đề này được trình bày theo bố cục như sau: A. Cơ sở lý thuyết B. Phương pháp C. Các dạng toán D. Bài tập tự rèn luyện *Nội dung A. Cơ sở lý thuyết Một số kiến thức cơ bản: 1. Quy tắc đếm a. Quy tắc cộng: Một công việc V bao gồm k công việc V1; V2;..Vk độc lập với nhau trong đó: V1: có n1 cách thực hiện V2: có n2 cách thực hiện … Vk có nk cách thực hiện Như vậy Số cách thực hiện công việc V là n = n1 + n2 + …+nk b. Quy tắc nhân: Một công việc V được thực hiện lần lượt qua k giai đoạn Đ1; Đ2;..;Đk độc lập với nhau trong đó: Giai đoạn Đ1: có n1 cách thực hiện Giai đoạn Đ2: có n2 cách thực hiện … Giai đoạn Đk:có nk cách thực hiện Như vậy Số cách thực hiện công việc V là n = n1.n2...nk 2. Hoán vị a) Hoán vị: ( Theo định nghĩa SGK)

ThuVienDeThi.com

www.MATHVN.com - Toán học Việt Nam

GV: Hoàng Ngọc Hùng - www.mathvn.com 2

+Khái niệm: Cho tập hợp A gồm n phần tử khác nhau )1 ( ≥ n . Mỗi cách sắp thứ tự n phần tử của tập được gọi là 1 hoán vị của n phần tử đó. +Công thức xác định: ! 1.2.3 )... 1 ( n n n Pn = − = + Chú ý: Quy ước 0! = 1 b) Hoán vị có lặp + Khái niệm: Có n vật )1 ( ≥ n được sắp vào n vị trí trong đó: Có n1 vật loại 1 Có n2 vật loại 2 …. Có nk vật loại 3 Ở đây n1+n2 + …+nk = n Mỗi cách sắp thứ tự n vật như trên vào n vị trí gọi là hoán vị có lặp của n phần tử đó. Công thức xác định:

+ Công thức xác định: Số hoán vị có lặp của n vật là ! !... !. !

2 1 kn n n n

+Chứng minh: Do có n1 vật giống nhau nên số phương án sắp n1 vật vào n1 vị trí chỉ là một phương án cần tìm, và ta có n1! phương án giống nhau. Tương tự…

Từ đó suy ra có ! !... !. ! ! !... !. 2 1 2 1 k k

n n n n n n n n P = số hoán vị

c) Hoán vị vòng tròn + Khái niệm: Có n vật được sắp vào n vị trí theo một đường tròn + Công thức xác định: Số hoán vị vòng tròn là: )! 1 ( 1.2.3 )... 1 ( 1 − = − = − n n Pn + Chứng minh: Cố định một điểm trên đường tròn, sắp n -1 vật vào n - 1 vị trí còn lại. Như vậy chúng ta có (n -1)! số hoán vị vòng tròn 3. Chỉnh hợp + Khái niệm: Cho tập A gồm n phần tử. Mỗi bộ gồm k ) 1( n k ≤ ≤ phần tử sắp thứ tự của tập A được gọi là 1 chỉnh hợp chập k của n phần tử + Công thức xác định

)! ( ! )1 )...( 2 )( 1 ( k n n k n n n n Ak n − = + − − − =

Chú ý: Khi k = n thì n k n P A = Ví dụ: Cho tập A gồm n số khác nhau { } 9,8 ,.., 2,1 ∈ n . Số có k ( n k ≤ ) chữ số khác nhau lấy từ tập A là k n A 4. Tổ hợp + Khái niệm: Cho tập A gồm n phần tử. Mỗi tập con gồm k ) 0 ( n k ≤ ≤ phần tử của tập A được gọi là 1 tổ hợp chập k của n phần tử + Công thức xác định số tổ hợp chập k của n phần tử

)! (! ! k n k n C k n − =

+ Tính chất: i) k n n k n C C − =

ThuVienDeThi.com