Bài toán đếm

1. Quy tắc cộng

Có \(k\) phương án \({A_1},{A_2},{A_3},...,{A_k}\) để thực hiện công việc. Trong đó:

- Có \({n_1}\) cách thực hiện phương án \({A_1}\),

- Có \({n_2}\) cách thực hiện phương án \({A_2}\)

- Có \({n_k}\) cách thực hiện phương án \({A_k}\).

Khi đó, số cách để thực hiện công việc là: \({n_1} + {n_2} + ... + {n_k}\) cách.

Đặc biệt: Nếu \(A\) và \(B\) là hai tập hợp hữu hạn không giao nhau thì số phần tử của \(A \cup B\) bằng tổng số phần tử của \(A\) và của \(B\), tức là: \(\left| {A \cup B} \right| = \left| A \right| + \left| B \right|\).

Ví dụ: Đi từ Hà Nội vào TP. Hồ Chí Minh có thể đi bằng ô tô, tàu hỏa, máy bay. Biết có \(10\) chuyến ô tô, \(2\) chuyến tàu hỏa và \(1\) chuyến máy bay có thể vào được TP. Hồ Chí Minh. Số cách có thể đi để vào TP. Hồ Chí Minh từ Hà Nội là:

Hướng dẫn:

Có \(3\) phương án đi từ Hà Nội vào TP. Hồ Chí Minh là: ô tô, tàu hỏa, máy bay.

- Có \(10\) cách đi bằng ô tô (vì có \(10\) chuyến).

- Có \(2\) cách đi bằng tàu hỏa (vì có \(2\) chuyến).

- Có \(1\) cách đi bằng máy bay (vì có \(1\) chuyến).

Vậy có tất cả \(10 + 2 + 1 = 13\) cách đi từ HN và TP.HCM.

2. Quy tắc nhân.

Có \(k\) công đoạn \({A_1},{A_2},...,{A_k}\) để thực hiện công việc.

- Có \({n_1}\) cách thực hiện công đoạn \({A_1}\).

- Có \({n_2}\) cách thực hiện công đoạn \({A_2}\).

- Có \({n_k}\) cách thực hiện công đoạn \({A_k}\).

Khi đó, số cách để thực hiện công việc là: \({n_1}.{n_2}.....{n_k}\) cách.

Ví dụ: Mai muốn đặt mật khẩu nhà có \(4\) chữ số. Chữ số đầu tiên là một trong \(3\) chữ số \(1;2;0\), chữ số thứ hai là một trong \(3\) chữ số \(6;4;3\), chữ số thứ ba là một trong \(4\) chữ số \(9;1;4;6\) và chữ số thứ tư là một trong \(4\) chữ số \(8;6;5;4\). Có bao nhiêu cách để Mai đặt mật khẩu nhà?

Hướng dẫn:

Việc đặt mật khẩu nhà có \(4\) công đoạn (từ chữ số đầu tiên đến chữ số cuối cùng).

- Có \(3\) cách thực hiện công đoạn 1 (ứng với \(3\) cách chọn chữ số đầu tiên).

- Có \(3\) cách thực hiện công đoạn 2 (ứng với \(3\) cách chọn chữ số thứ hai).

- Có \(4\) cách thực hiện công đoạn 3 (ứng với \(4\) cách chọn chữ số thứ ba).

- Có \(4\) cách thực hiện công đoạn 4 (ứng với \(4\) cách chọn chữ số thứ tư).

Vậy có tất cả \(3.3.4.4 = 144\) cách để Mai đặt mật khẩu nhà.

3. Hoán vị

Tập hợp hữu hạn \(A\) có \(n\) phần tử \((n \ge 1)\). Mỗi cách sắp thứ tự các phần tử của \(A\) được gọi là một hoán vị của \(n\) phần tử đó.

Định lý: Số các hoán vị khác nhau của \(n\) phần tử là:

\(P = n(n - 1)(n - 2)...2.1 = n!\)

Ví dụ: Có bao nhiêu cách xếp \(3\) bạn vào một bàn có \(3\) chỗ ngồi?

Giải:

Mỗi cách xếp cho ta một hoán vị khác nhau của \(3\) bạn. Vậy số cách xếp là \({P_3} = 3! = 6\).

4. Chỉnh hợp

Xét một tập hợp \(A\) gồm \(n\) phần tử \((n \ge 1)\) và một số nguyên \(k\) với \(1 \le k \le n\). Mỗi cách lấy ra \(k\) phần tử của \(A\) và sắp xếp chúng theo một thứ tự nào đó được gọi là chỉnh hợp chập \(k\) của \(n\) phần tử của \(A\).

Định lý: Số chỉnh hợp chập \(k\) của \(n\) phần tử là:

\(A_n^k = \dfrac{{n!}}{{(n - k)!}} = n(n - 1)(n - 2)...(n - k + 1)\)

Ví dụ: Có bao nhiêu số nguyên dương gồm \(3\) chữ số đôi một khác nhau và khác \(0\)?

Giải:

Mỗi số cần tìm có dạng \(\overline {abc} (a,b,c \in \left\{ {1;2;3;...;9} \right\},a \ne b \ne c)\).

Mỗi số dạng trên là một chỉnh hợp chập \(3\) của \(9\). Do đó số các số cần tìm là: \(A_9^3 = \dfrac{{9!}}{{(9 - 3)!}} = 9.8.7 = 504\) số.

5. Tổ hợp

Cho tập hợp hữu hạn \(A\) và số nguyên \(k\) với \(0 \le k \le n\). Mỗi cách lấy ra \(k\) phần tử của tập \(A\) được gọi là một tổ hợp chập \(k\) của \(n\) phần tử của \(A\).

Định lý: Số tổ hợp chập \(k\) của \(n\) phần tử là:

\(C_n^k = \dfrac{{n!}}{{k!(n - k)!}} = \dfrac{{A_n^k}}{{k!}}\) (quy ước \(0! = 1\))

Một số tính chất:

Với \(k,n \in Z,0 \le k \le n\) thì:

+) \(C_n^k = C_n^{n - k}\)

+) \(C_{n + 1}^k = C_n^k + C_n^{k - 1}\)