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

IV. Bài toán đếm trong hình học - hình học không gian

1. Cho $n$ điểm trong không gian, trong đó không có 3 điểm nào thẳng hàng.

Số đường thẳng đi qua 2 điểm: $C_{n}^{2}=\dfrac{n(n-1)}{2}$.

Số vectơ nối hai điểm bất kì: $n^{2}$.

Số vectơ khác $\overrightarrow{0}$ nối hai điểm bất kì: $A_{n}^{2}=n(n-1)$.

Số tam giác tạo thành: $C_{n}^{3}=\dfrac{n(n-1)(n-2)}{6}$.

Nếu trong $n$ điểm không có 4 điểm nào đồng phẳng, thì số tứ diện được tạo thành: $C_{n}^{4}$.

2. Cho đa giác lồi n đỉnh

Số đường chéo của đa giác: $C_{n}^{2}-n=\dfrac{n(n-3)}{2}$.

Số đường chéo cùng đi qua 1 đỉnh của đa giác: $n-3$.

Nếu không có 3 đường chéo nào đồng quy thì số giao điểm giữa các đường chéo

$C_{n}^{4}=\dfrac{n(n-1)(n-2)(n-3)}{24}$

Số tam giác có 3 đỉnh là đỉnh của đa giác: $C_{n}^{3}=\dfrac{n(n-1)(n-2)}{6}$.

Số tam giác có đúng 1 cạnh của đa giác 2 cạnh còn lại là đường chéo: $n C_{n-4}^{1}=n(n-4)$.

Số tam giác có 2 cạnh của đa giác, 1 cạnh còn lại là đường chéo: $n$.

Số tam giác có cạnh đều là các đường chéo của đa giác: $C_{n}^{3}-n-n(n-4)=\dfrac{n\left(n^{2}-9 n+20\right)}{6}$

3. Cho đa giác đều $2n$ đỉnh $n \ge 2$

Số đường chéo xuyên tâm = số hình chữ nhật: $C_n^2 = \dfrac{{n\left( {n - 2} \right)}}{2}$

Số tam giác vuông: $\left( {2n - 2} \right)C_n^2$