Phân dạng và bài tập đại số tổ hợp

CHUYÊN ĐỀ: ĐẠI SỐ TỔ HỢP

Bài 1: QUY TẮC ĐẾM

A. TÓM TẮT LÝ THUYẾT:

1. Quy tắc cộng và sơ đồ hình cây

Quy tắc cộng

Giả sử một công việc nào đó có thể thực hiện theo một trong hai phương án khác nhau: - Phương án 1 có 1n cách thực hiện.

- Phương án 2 có 2n cách thực hiện.

Khi đó số cách thực hiện công việc là : 1 2 n n + cách

Phương án 1.. 1n cách

Phương án 2 .. 2n cách

Một công việc được hoàn thành bởi một trong hai hành động. Nếu hành động này có m cách thực hiên, hành động kia có n cách thực hiên không trùng với bất kì cách nào của hành động thứ nhất thì công việc đó có m + n cách thực hiện.

Chú ý: số phần tử của tập hợp hữu hạn X được kí hiệu là X hoặc ( ) n X .

Quy tắc cộng được phát biểu ở trên thực chất là quy tắc đếm số phần tử của hợp hai tập hợp hữu hạn không giao nhau: Nếu A và B là các tập hợp hữu hạn không giao nhau thì

( ) ( ) ( ) n A B n A n B ∪ = +

Mở rộng: Một công việc được hoàn thành bởi một trong k hành động

1 2 3 , , ,..., k A A A A .Nếu hành động A1 có m1cách thực hiện, hành động A2 có m2 cách thực

hiện,…, hành động Ak có mk cách thực hiện và các cách thực hiên của các hành động trên không trùng nhau thì công việc đó có 1 2 3 ... k m m m m + + + + cách thực hiện.

2. Quy tắc nhân

Một công việc được hoàn thành bởi hai hành động liên tiếp.Nếu có m cách thực hiện hành động thứ nhất và ứng với mỗi cách đó có n cách thực hiện hành động thứ hai thì công việc đó có m.n cách thực hiện.

Mở rộng: Một công việc được hoàn thành bởi k hành động 1 2 3 , , ,..., k A A A A liên tiếp. Nếu hành

động A1 có m1cách thực hiện, ứng với mỗi cách thực hiện hành động A1 có m2 cách thực hiện hành động A2,…, có mk cách thực hiện hành động Ak thì công việc đó có 1 2 3 . . ..... k m m m m cách

hoàn thành.

NHẬN XÉT CHUNG:

Để đếm số cách lựa chọn để thực hiện một công việc A bằng quy tắc cộng, ta thực hiện các bước như sau:

Bước 1: Phân tích xem có bao nhiêu phương án riêng biệt để thực hiện công việc A (có nghĩa công việc A có thể hoàn thành một trong các phương án A1, A2,...,An).

Bước 2: Đếm số cách chọn 1 2 , ,..., n x x x trong các phương án 1 2 , ,..., n A A A .

Bước 3: Dùng quy tắc cộng ta tính được số cách lựa chọn để thực hiện công việc A là:

1 2 n x x x x = + +⋅⋅⋅+ .

Để đếm số cách lựa chọn để thực hiện công việc A bằng quy tắc nhân, ta thực hiện các bước sau:

Bước 1: Phân tích xem có bao nhiêu công đoạn liên tiếp cần phải tiến hành để thực hiện công việc A (giả sử A chỉ hoàn thành sau khi tất cả các công đoạn 1 2 , ,..., n A A A hoàn thành).

Bước 2: Đếm số cách chọn 1 2 , ,..., n x x x trong các công đoạn 1 2 , ,..., n A A A .

Bước 3: Dùng quy tắc nhân ta tính được số cách lựa chọn để thực hiện công việc A là:

1 2 . . . n x x x x = ⋅⋅⋅ .

Cách đếm gián tiếp (đếm phần bù)

Trong trường hợp hành động H chia nhiều trường hợp thì ta đi đếm phần bù của bài toán như sau:

• Đếm số phương án thực hiện hành động H (không cần quan tâm đến có thỏa tính chất T hay không) ta được a phương án.

• Đếm số phương án thực hiện hành động H không thỏa tính chất T ta được b phương án.

Khi đó số phương án thỏa yêu cầu bài toán là: a b −.

B. PHƯƠNG PHÁP GIẢI TOÁN:

1. Dạng 1: Quy tắc cộng

a) Phương pháp:

Nếu một công việc nào nó có thể thực hiện theo n hướng khác nhau, trong đó:

Hướng thứ 1 có m1 cách thực hiện

Hướng thứ 2 có m2 cách thực hiện

…. ……….

Hướng thứ n có mn cách thực hiện

Khi đó, có: 1 2 ... n m m m + + + cách để hoàn thành công việc đã cho.

b) Ví dụ minh họa:

Ví dụ 1: Một quán bán ba loại đồ uống: trà sữa, nước hoa quả và sinh tố. Có 5 loại trà sữa, 6 loại nước hoa quả và 4 loại sinh tố. Hỏi khách hàng có bao nhiêu cách chọn một loại đồ uống?

Lời giải:

Khách hàng có ba phương án lựa chọn đồ uống. Phương án 1: uống trà sữa có 5 cách Phương án 2: uống nước hoa quả có 6 cách Phương án 3: uống sinh tố có 4 cách Theo quy tắc cộng có 5 6 4 15 + + = cách. Vậy khách hàng có 15 cách chọn một loại đồ uống Ví dụ 2: Gia đình bạn Liên dự định đi du lịch ở Quy Nhơn (Bình Định). Hướng dẫn viên du lịch đưa ra …