Bài toán đếm

Kỳ thi ĐGTD ĐH Bách Khoa

Đổi lựa chọn

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ử đó.

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

\(P = n\left( {n - 1} \right)\left( {n - 2} \right)...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\).

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\).

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

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

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\).

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

\(C_n^k = \dfrac{{n!}}{{k!\left( {n - k} \right)!}} = \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}\)

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\)