Hoán vị - Chỉnh hợp - Tổ hợp

 1. Hoán vị

Định nghĩa. Cho tập hợp $A$ gồm $n$ phần tử $(n\ge 1)$.

Một cách sắp xếp của $n$ phần tử trong tập hợp $A$ được gọi là một hoán vị của $n$ phần tử đó.

Công thức số hoán vị. Số các hoán vị của $n$ phần tử: $$P_n=n!=n(n-1)\ldots 2.1$$

---

1.2. Hoán vị lặp

Định nghĩa. Cho $n$ phần tử, trong đó có $n_1$ phần tử $x_1$, $n_2$ phần tử $x_2$,..., $n_k$ phần tử $x_k$, $(n_1+n_2+\cdots+n_k=n)$. Mỗi cách sắp xếp $n$ phần tử đó vào $n$ vị trí được gọi là hoán vị lặp của $n$.

Công thức. Số các hoán vị lặp của $n$ phần tử ở trên là $$P(n_1,n_2,\ldots,n_k)=\frac{n!}{n_1!n_2!\ldots n_k!}$$

Ví dụ. Từ tập $X=\{1;2;3;4;5;6\}$ có thể lập được bao nhiêu số tự nhiên có $10$ chữ số sao cho chữ số $1$ xuất hiện $3$ lần, chữ số $2$ xuất hiện $3$ lần, các chữ số còn lại xuất hiện đúng một lần.

Giải.

Áp dụng công thức hoán vị lặp: $$P=\frac{10!}{3!3!}=100800.$$

Ví dụ. Có $4$ cái quần dài giống nhau, $6$ cái áo trắng giống nhau, $5$ cái áo sơ mi giống nhau. Treo tất cả thành một hàng thẳng trong tủ treo đồ, hỏi có bao nhiêu cách sắp xếp?

Giải.

Áp dụng công thức hoán vị lặp: $$P=\frac{15!}{4!5!6!}=630630.$$

---

1.3. Hoán vị vòng quanh

Hoán vị vòng quanh là sắp xếp trên vòng tròn.

Công thức. Số hoán vị vòng quanh của $n$ phần tử là $$P_q=(n-1)!.$$

---

2. Chỉnh hợp

Định nghĩa. Cho tập $A$ gồm $n$ phần tử $(n\ge 1)$.

Lấy $k$ phần tử của tập hợp $A$ và sắp xếp theo một thứ tự nào đó được gọi là một chỉnh hợp chập $k$ của $n$ phần tử.

Công thức số các chỉnh hợp. $$A^k_n=\frac{n!}{(n-k)!}=n(n-1)(n-2)\ldots (n-k+1), (0\le k\le n).$$ Với quy ước $0!=1; A^0_n=1.$

Nhận xét. $A^n_n=P_n$.

---

3. Tổ hợp

Định nghĩa. Cho tập $A$ gồm $n$ phần tử $(n\ge 1)$.

Mỗi tập con gồm $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ử.

Công thức số các tổ hợp. $$C^k_n=\frac{A^k_n}{k!}=\frac{n!}{k!(n-k)!}=\frac{n(n-1)(n-2)\ldots (n-k+1)}{k!}, (0\le k\le n).$$

---

4. Tính chất của tổ hợp

Tính chất 1. $$C^k_n=C^{n-k}_n, (0\le k\le n).$$

Tính chất 2. (Công thức Pascal) $$C^{k-1}_{n-1}+C^k_{n-1}=C^k_n, (1\le k<n).$$