Hoán vị, chỉnh hợp, tổ hợp

HOÁN VỊ – TỔ HỢP – CHỈNH HỢP

A. Lí thuyết cơ bản

1. Hoán vị

- Cho tập A gồm n phần tử ( $\displaystyle n\ge 1$ ). Khi xếp n phần tử này theo một thứ tự, ta được một hoán vị các phần tử của tập hợp A, ( gọi tắt là một hoán vị của A).
- Số hoán vị của một tập hợp có n phần tử là:
.

2. Chỉnh hợp

- Cho tập hợp A có n phần tử và cho số nguyên k, ( $\displaystyle 1\le k\le n$ ). Khi lấy k phần tử của A và sắp xếp chúng theo một thứ tự, ta được một chỉnh hợp chập k của n phần tử của A (gọi tắt là một chỉnh hợp n chập k của A).
- Số các chỉnh hợp chập k của một tập hợp có n phần tử là:
.
- Một số qui ước : $\displaystyle 0!=1,A_{n}^{0}=1,A_{n}^{n}=n!$

3. Tổ hợp

- Cho tập hợp A có n phần tử và cho số nguyên k, , ( $\displaystyle 1\le k\le n$ ). Mỗi tập hợp con của A có k phần tử được gọi là một tổ hợp chập k của n phần tử của A.
- Số các tổ hợp chập k của một tập hợp có n phần tử là:
.
- Một số quy ước $\displaystyle C_{n}^{0}=1,C_{n}^{n}=1$ , với qui ước này ta có $\displaystyle C_{n}^{k}=\frac{n!}{(n-k)!k!}$ đúng với số nguyên dương k, thỏa $\displaystyle 0\le k\le n$ .
- Tính chất : $\displaystyle C_{n}^{k}=C_{n}^{n-k},(0\le k\le n)$ và $\displaystyle C_{n+1}^{k}=C_{n}^{k}+C_{n}^{k-1},(1\le k\le n)$ : được gọi là hằng đẳng thức Pascal.

B. Bài tập

Dạng 1. Thực hiện bài toán đếm theo hoán vị, tổ hợp, chỉnh hợp

A. Phương pháp

* Để nhận dạng một bài toán đếm có sử dụng hoán vị của $n$ phần tử, chúng ta thường dựa trên các dấu hiệu sau:
- + Tất cả $n$ phần tử đều có mặt.
- + Mỗi phần tử chỉ xuất hiện một lần.
- + Có phân biệt thứ tự giữa các phần tử.
* Để nhận dạng một bài toán đếm có sử dụng chỉnh hợp chập $k$ của $n$ phần tử, chúng ta thường dựa trên các dấu hiệu sau:
- + Phải chọn $k$ phần tử từ $n$ phần tử cho trước.
- + Có phân biệt thứ tự giữa $k$ phần tử được chọn.
* Để nhận dạng một bài toán đếm có sử dụng tổ hợp chập $k$ của $n$ phần tử, chúng ta thường dựa trên các dấu hiệu sau:
- + Phải chọn $k$ phần tử từ $n$ phần tử cho trước.
- + Không phân biệt thứ tự giữa $k$ phần tử được chọn.

B. Bài tập ví dụ

Ví dụ 1: Xếp 6 người A, B, C, D, E, F vào một ghế dài .Hỏi có bao nhiêu cách sắp xếp sao cho:

a) A và F ngồi ở hai đầu ghế

b) A và F ngồi cạnh nhau

c) A và F không ngồi cạnh nhau

Lời giải:

a) Số cách xếp A, F: $2!=2$

Số cách xếp $B,C,D,E$ : $4!=24$

Số cách xếp thỏa yêu cầu bài toán: $2.24=48$

b) Xem $AF$ là một phần tử $X$ , ta có: $5!=120$ số cách xếp

$X,B,C,D,E$ . Khi hoán vị $A,F$ ta có thêm được một cách xếp

Vậy có $240$ cách xếp thỏa yêu cầu bài toán.

c) Số cách xếp thỏa yêu cầu bài toán: $6!-240=480$ cách

Ví dụ 2: Một hội đồng gồm $2$ giáo viên và $3$ học sinh được chọn từ một nhóm $5$ giáo viên và học sinh. Hỏi có bao nhiêu cách chọn?

A. 200. B. 150. C. $6$ $160$ . D. $180$ .

Lời giải:

Chọn A.

Chọn $2$ trong giáo viên có: cách chọn.

Chọn trong học sinh có cách chọn.

Vậy có cách chọn.

Ví dụ 3: Cho tập

1. Có bao nhiêu tập con của A chứa số 2 mà không chứa số 3

A. 64 B. 83 C. 13 D. 41

2. Từ các chữ số thuộc tập A, lập được bao nhiêu số tự nhiên lẻ gồm 5 chữ số không bắt đầu bởi 123.

A. 3340 B. 3219 $5$ $X$ C. 4942 D. 2220 $X\backslash \left\{ 2 \right\}$

Lời giải:

1. Xét tập $B=\left\{ 1,4,5,6,7,8 \right\}$ , ta có B không chứa số 3.

là một tập con của A thỏa yêu cầu bài toán khi và chỉ khi là một tập con của $B$ . Do đo, số tập con của A thỏa yêu cầu bài toán bằng số tập con của B và bằng ${{2}^{6}}=64$ .

Chọn A.

2. Xét số $x=\overline{abcde}$ được lập từ các chữ số thuộc tập A.

Vì $x$ lẻ nên $e\in \left\{ 1,3,5,7 \right\}$ , suy ra có 4 cách chọn e. Bốn chữ số còn lại được chọn từ 7 chữ số của tập $A\backslash \left\{ e \right\}$ nên có $A_{7}^{4}=840$ cách

Suy ra, có $4.840=3360$ số lẻ gồm năm chữ số khác nhau.

Mà số $x$ bắt đầu bằng 123 có $A_{5}^{2}=20$ số.

Vậy số $x$ thỏa yêu cầu bài toán là : $3360-20-3340$ số.

Chọn A.

Ví dụ 4: Một Thầy giáo có 10 cuốn sách Toán đôi một khác nhau, trong đó có 3 cuốn Đại số, 4 cuốn Giải tích và 3 cuốn Hình học. Ông muốn lấy ra 5 cuốn và tặng cho 5 học sinh sao cho sau khi tặng mỗi loại sách còn lại ít nhất một cuốn. Hỏi có bao nhiêu cách tặng.

A. 23314 B. 32512 C. 24480 D. 24412

Lời giải:

Số cách lấy 5 cuốn sách và đem tặng cho 5 học sinh: $S=A_{10}^{5}=30240$ cách.

Số cách chọn sao cho không còn sách Đại số: ${{S}_{1}}=C_{7}^{2}.5!=2520$ cách

Số cách chọn sao cho không còn sách Giải tích: ${{S}_{2}}=C_{6}^{1}.5!=720$ cách

Số cách chọn sao cho không còn sách Hình học: ${{S}_{3}}=C_{7}^{2}.5!=2520$ cách.

Vậy số cách tặng thỏa yêu cầu bài toán: $S-{{S}_{1}}-{{S}_{2}}-{{S}_{3}}=24480$ cách tặng.

Dạng 2. Giải phương trình, bất phương trình

A. Phương pháp

Dựa vào công thức tổ hợp, chỉnh hợp hoán vị để chuyển phương trình, bất phương trình, hệ phương trình tổ hợp về phương trình, bất phương trình, hệ phương trình đại số.

B. Bài tập ví dụ

Ví dụ 1: Giải các phương trình sau

1. ${{P}_{x}}=120$
2. ${{P}_{x}}A_{x}^{2}+72=6(A_{x}^{2}+2{{P}_{x}})$

Lời giải:

1. Điều kiện: $\left\{ \begin{array}{l}x\in \mathbb{N}\\x\ge 1\end{array} \right.$

Ta có: ${{P}_{5}}=120$

$\bullet$ Với $x>5\Rightarrow {{P}_{x}}>{{P}_{5}}=120\Rightarrow$ phương trình vô nghiệm

$\bullet$ Với $x<5\Rightarrow {{P}_{x}}<{{P}_{5}}=120\Rightarrow$ phương trình vô nghiệm

Vậy $x=5$ là nghiệm duy nhất.

2. Điều kiện: $\left\{ \begin{array}{l}x\in \mathbb{N}\\x\ge 2\end{array} \right.$

Phương trình $\Leftrightarrow A_{x}^{2}\left( {{P}_{x}}-6 \right)-12({{P}_{x}}-6)=0$

$\Leftrightarrow ({{P}_{x}}-6)(A_{x}^{2}-12)=0\Leftrightarrow \left[ \begin{array}{l}{{P}_{x}}=6\\A_{x}^{2}=12\end{array} \right.\Leftrightarrow \left[ \begin{array}{l}x!=6\\x(x-1)=12\end{array} \right.\Leftrightarrow \left[ \begin{array}{l}x=3\\x=4\end{array} \right.$ .

Ví dụ 2:

1. Cho $C_{n}^{n-3}=1140$ . Tính $A=\frac{A_{n}^{6}+A_{n}^{5}}{A_{n}^{4}}$

2. Tính $B=\frac{1}{A_{2}^{2}}+\frac{1}{A_{3}^{2}}+...+\frac{1}{A_{n}^{2}}$ , biết $C_{n}^{1}+2\frac{C_{n}^{2}}{C_{n}^{1}}+...+n\frac{C_{n}^{n}}{C_{n}^{n-1}}=45$

3. Tính $M=\frac{A_{n+1}^{4}+3A_{n}^{3}}{\left( n+1 \right)!}$ , biết $C_{n+1}^{2}+2C_{n+2}^{2}+2C_{n+3}^{2}+C_{n+4}^{2}=149$ .

Lời giải:

1. ĐK: $\left\{ \begin{array}{l}n\in \mathbb{N}\\n\ge 6\end{array} \right.$

Ta có: $C_{n}^{n-3}=1140\Leftrightarrow \frac{n!}{3!(n-3)!}=1140\Leftrightarrow n=20$

Khi đó: $A=\frac{n(n-1)...(n-5)+n(n-1)...(n-4)}{n(n-1)...(n-3)}=n-4+(n-4)(n-5)=256$

2. Ta có: $C_{n}^{1}=n$ ; $2\frac{C_{n}^{2}}{C_{n}^{1}}=2.\frac{\frac{n!}{2!.(n-2)!}}{\frac{n!}{1!.(n-1)!}}=n-1$ ;…; $\displaystyle n\frac{C_{n}^{n}}{C_{n}^{n-1}}=\frac{1}{\frac{n!}{1!.(n-1)!}}=1$

Nên $C_{n}^{1}+2\frac{C_{n}^{2}}{C_{n}^{1}}+...+n\frac{C_{n}^{n}}{C_{n}^{n-1}}=45\Leftrightarrow \frac{n(n-1)}{2}=45\Leftrightarrow n=10$

$B=\frac{1}{A_{2}^{2}}+\frac{1}{A_{3}^{2}}+...+\frac{1}{A_{n}^{2}}=1-\frac{1}{n}=\frac{9}{10}$ .

3. Điều kiện: $\left\{ \begin{array}{l}n\in \mathbb{N}\\n\ge 3\end{array} \right.$

Ta có: $C_{n+1}^{2}+2C_{n+2}^{2}+2C_{n+3}^{2}+C_{n+4}^{2}=149$

$\Leftrightarrow \frac{\left( n+1 \right)!}{2!\left( n-1 \right)!}+2\frac{\left( n+2 \right)!}{2!n!}+2\frac{\left( n+3 \right)!}{2!\left( n+1 \right)!}+\frac{\left( n+4 \right)!}{2!\left( n+2 \right)!}=149\Leftrightarrow n=5$