Chuyên đề đại số tổ hợp Toán 10 Cánh Diều

CHUYÊN ĐỀ V – TOÁN 10 – CHƯƠNG V – ĐẠI SỐ TỔ HỢP

Page 1

BÀI 1: QUY TẮC CỘNG. QUY TẮC NHÂN. SƠ ĐỒ HÌNH CÂY

1. Quy tắc cộng

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.

CHƯƠNG

V ĐẠI SỐ TỔ HỢP

LÝ THUYẾT. I

CHUYÊN ĐỀ V – TOÁN 10 – CHƯƠNG V – ĐẠI SỐ TỔ HỢP

Page 2

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.

Ví dụ:

CHUYÊN ĐỀ V – TOÁN 10 – CHƯƠNG V – ĐẠI SỐ TỔ HỢP

Page 3

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.