Chỉnh hợp
Mỗi cách sắp xếp $k$ phần tử (phân biệt) vào $n$ vị trí phân biệt ($n\geq k$) được gọi là một chỉnh hợp chập $k$ của $n$.
Tính chất. Số chỉnh hợp chập $k$ của $n$ là $$A_n^k = \dfrac{(n!)}{(n-k)!}$$
Hoán vị.
Mỗi chỉnh hợp chập $n$ của $n$ được gọi là một hoán vị, hay mỗi cách sắp xếp $n$ phần tử vào $n$ vị trí được gọi là một hoán vị của $n$ phần tử. Số hoán vị của $n$ phần tử là $P_n = n!$.
Định nghĩa khác. Cho tập $A = {1, 2, \cdots, n}$. Mỗi song ánh từ $A$ vào $A$ được gọi là một hoán vị.
Ví dụ 1. Có 8 bạn nam và 2 bạn nữ được xếp thành một hàng dài. Hỏi có bao nhiêu cách xếp thỏa:
a) Xếp bất kì.
b) 8 bạn nam kề nhau,2 bạn nữ kề nhau.
c) Các bạn nam giữa hai bạn nữ.
Ví dụ 2. Có 8 bạn nam và 4 bạn nữ. Có bao nhiêu cách sắp xếp các bạn này thành một hàng sao cho không có hai bạn nữ nào đứng kề nhau.
Ví dụ 3. Cho tập $A = {0, 1, 2, 3, 4, 5}$. Từ $A$ có thể lập được bao nhiêu số
a) Là số chẵn có 4 chữ số khác nhau.
b) Là số lẻ có 5 chữ số khác nhau và chia hết cho 3.
Tổ hợp. Cho tập hợp $A$ có $n$ phần tử. Một tập hợp con có $k$ phần tử của $A$ được gọi là một tổ hợp chập $k$ của $n$ phần tử.
Tính chất. Số tổ hợp có chập $k$ của $n$ là: [C_n^k = \dfrac{A_n^k}{k!} = \dfrac{n!}{(n-k)! k!}]
Ví dụ 4. Đội văn nghệ của trường gồm 4 bạn học sinh lớp 10, 5 học sinh lớp 11, 4 học sinh lớp 12.
a) Có bao nhiêu cách chọn ra hai bạn hát song ca?
b) Có bao nhiêu cách chọn ra 3 bạn hát tam ca mà mỗi khối có một học sinh?
c) Có bao nhiêu cách chọn ra một đội múa gồm 5 bạn trong đó có ít nhất 2 học sinh lớp 11.
Ví dụ 5. Cho tập $A = {1, 2, 3, 4, 5}, B = {a, b, c, d, e, }$, $C = {x, y, z}$.
a) Có bao nhiêu song ánh từ $A$ vào $B$.
b) Có bao nhiêu ánh xạ từ $A$ vào $C$? Có bao nhiêu đơn ánh từ $C$ vào $A$.
c) Có bao nhiêu đơn ánh từ $C$ và $A$ sao cho $f(x) + f(y) + f(z)$ là số chẵn.
Bài tập rèn luyện
Bài 1. Cho tập $A = {0, 1, 2, 3, 4,5,6, a, b, c, d}$
a) Có bao nhiêu hoán vị của $A$.
b) Có bao nhiêu hoán vị của $A$ mà các chữ số đứng kề nhau.
c) Có bao nhiêu hoán vị của $A$ mà không có chữ cái nào đứng kề nhau?
Bài 2. Cho tập $A = {0, 1, 2, 3, 4, 5, 6 }$
a)Từ A có thể lập được bao nhiêu số có 5 chữ số khác nhau.
b) Có bao nhiêu hoán vị của A mà hai chữ số lẻ không đứng kề nhau.
c) Từ A có thể lập được bao nhiêu số có 4 chữ số mà chữ số đứng sau lớn hơn chữ số đứng liền trước.
d) Từ A có thể lập được bao nhiêu số có 3 chữ số chia hết cho 3.
Bài 3. Xếp $ m $ bạn nam và $ n $ bạn nữ thành 1 hàng, với $m,n\in \mathbb{N}$. Hỏi có bao nhiêu cách xếp nếu:
a) Xếp tùy ý;
b) Không có bạn nam nào đứng cạnh nhau $\left( m\le n+1 \right);$
c) $ n $ bạn nữ đứng liền kề nhau;
d) Một bạn nam A và một bạn nữ B đứng cạnh nhau.
Bài 4. Tính: $1\cdot 1!+2\cdot 2!+3\cdot 3!+\cdot \cdot \cdot +n\cdot n!,n\in \mathbb{N}.$
Bài 5. Tính: $\dfrac{1}{\left( 1+1 \right)!}+\dfrac{2}{\left( 2+1 \right)!}+\cdot \cdot \cdot +\dfrac{n}{\left( n+1 \right)!}$ với $n\in \mathbb{N}.$
Bài 6. Cho $n,r\in \mathbb{N}$ với $r\le n.$ Chứng minh rằng:
a) $A_{n}^{r}=nA_{n-1}^{r-1};$
b) $A_{n}^{r}=\left( n-r+1 \right)A_{n}^{r-1};$
c) $A_{n}^{r}=\dfrac{n}{n-r}A_{n}^{r-1},$ với $r<n;$
d) $A_{n+1}^{r}=A_{n}^{r}+rA_{n}^{r-1};$
e) $A_{n+1}^{r}=r!+r\left( A_{n}^{r-1}+A_{n-1}^{r-1}+…+A_{r}^{r-1} \right).$
Bài 7. Một nhóm có 15 hóc sinh, trong đó có 5 bạn nữ. Hỏi có bao nhiêu cách chọn 9 học sinh sao cho có đúng 3 học sinh nữ:
a) để thành lập một hội đồng.
b) để thành lập một hội đồng với 9 vị trí khác nhau.
Bài 8. Có 10 cái ghế được xếp thành một hàng. 7 học sinh được xếp vào 7 cái ghế sao cho không có 2 học sinh nào ngồi chung một cái ghế. Hỏi có bao nhiêu cách xếp sao cho không có 2 cái ghế trống nào liền nhau.
Bài 9. Có 8 cái hộp được xếp thành hàng. Hỏi có bao nhiêu cách đặt 5 viên bi khác nhau vào các hộp nếu mỗi hộp chứa nhiều nhất 1 viên bi và không có hai hộp không chứa bi nào đứng cạnh nhau?
Bài 10. Xếp một nhóm có 20 học sinh, trong đó có 3 bạn nữ là: A, B, C và 4 bạn nam: X,Y,Z,T thành 2 hàng, mỗi hàng 10 học sinh. Hỏi có bao nhiêu cách xếp sao cho 3 bạn nữ luôn ở hàng trước, còn 4 bạn nam ở hàng phía sau.
Bài 11. Hỏi có bao nhiêu cách xếp 7 bạn nam và 2 bạn nữa thành một hàng sao cho các bạn gái cách nhau bởi đúng 3 bạn nam?
Bài 12. Tìm số $(m+n)$-nhị phân là một dãy chữ số với $ m $ số 0 và $ n $ số 1 sao cho không có 2 số 1 nào đứng kề nhau, khi $n\le m+1.$
Bài 13. Lớp A có 10 bạn nữ và 15 bạn nam và lớp B có 4 nữ và 10 nam. Một hội đồng gồm 7 thành viên được chọn từ 2 lớp đó. Hỏi có bao nhiêu cách chọn các thành viên sao cho có đúng 4 bạn của lớp B và có đúng 5 bạn nam.
Bài 14. Trong mỗi trường hợp sau, tìm số tuyến đường ngắn nhất từ $ O $ đến $ P $ trong sơ đồ được cho dưới đây:
a) Tuyến đường phải đi qua $ A $.
b) Tuyến đường phải qua đoạn $AB$.
c) Tuyến đường phải đi qua $A$ và $C$.
d) Đoạn đường $AB$ bị đóng.
Bài 15. Tìm số cách chọn một nhóm gồm $ 2k $ người từ $n$ cặp đôi, với $k,n\in \mathbb{N}$ và $2k\le n,$ trong mỗi trường hợp sau đây:
a) Có $k$ cặp đôi trong nhóm đó.
b) Không có cặp đôi nào trong nhóm đó.
c) Có ít nhất một cặp đôi được chọn trong nhóm.
d) Có đúng 2 cặp đôi được chọn trong nhóm đó.
Bài 16. Cho một đa giác có 10 đỉnh.
a) Có bao nhiêu đường chéo.
b) Có bao nhiêu tam giác có 3 đỉnh là 3 đỉnh thuộc đa giác.
c) Có bao nhiêu tam giác có đúng 1 cạnh trùng với cạnh của đa giác.
d) Có bao nhiêu tam giác không có cạnh nào trùng với cạnh của đa giác.
e) Biết rằng không có 3 đường chéo nào đồng quy. Tìm số giao điểm của các đường chéo.
Bài 17. Cho đa giác đều có 100 cạnh. Hỏi có bao nhiêu hình chữ nhật tạo ra từ các đỉnh của đa giác trên.
Bài 18. Cho A là tập hợp các số nguyên dương từ 1 đến 100. Hỏi có bao nhiêu tập con có 3 phần tử của A thỏa:
a) Tổng các số chia hết cho 3
b) Tổng các số chia hết cho 4.
Bài 19. Chung kết cuộc thi tiếng hát học đường có 3 bạn vào chung kết, mỗi bạn hát 2 bài khác nhau. Hỏi có bao nhiêu cách sắp xếp chương trình sao cho không có ai hát liên tiếp.
Bài 20. Có bao nhiêu cách chọn ra 3 số từ tập $A = {1, 2, \cdots, 100}$ sao cho một số là trung bình cộng của hai số còn lại.