Bài toán đếm

I. Hoán vị

Tập hợp hữu hạn $A$ có $n$ phần tử $\left( {n \ge 1} \right)$. 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ử đó.

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$.

II. Chỉnh hợp

Xét một tập hợp $A$ gồm $n$ phần tử $\left( {n \ge 1} \right)$ 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$.

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} \left( {a,b,c \in \left\{ {1;2;3;...;9} \right\},a \ne b \ne c} \right)$.

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!}}{{\left( {9 - 3} \right)!}} = 9.8.7 = 504$ số.

III. 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$.

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}$