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

1/ Giai thừa:

\[n!=1.2.3\ldots n~~\] Qui ước: \[0!=1\]

\[n!=\left( n1 \right)!n\]

\[\dfrac{n!}{p!}=\left( p+1 \right).\left( p+2 \right)\ldots n\] (với \[n>p\])

\[\dfrac{n!}{(n-p)!}=\left( np+1 \right).\left( np+2 \right)\ldots n\]   (với \[n>p\])

2/ Hoán vị (không lặp):

Một tập hợp gồm n phần tử (n ³ 1). Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó được gọi là một hoán vị của n phần tử.

Số các hoán vị của n phần tử là:  \[{{P}_{n}}\text{ }=\text{ }n!\]

3/ Hoán vị lặp:

Cho k phần tử khác nhau: \[{{a}_{1}},\text{ }{{a}_{2}},\text{ }\ldots ,\text{ }{{a}_{k}}.\] Một cách sắp xếp \[n\] phần tử trong đó gồm \[{{n}_{1}}\] phần tử \[{{a}_{1}},\text{ }{{n}_{2}}\] phần tử \[{{a}_{2}},\text{ }\ldots ,{{n}_{k}}\] phần tử \[{{a}_{k}}\] \[\left( {{n}_{1}}+n2+\text{ }\ldots +\text{ }nk\text{ }=\text{ }n \right)\] theo một thứ tự nào đó được gọi là một hoán vị lặp cấp \[n\] và kiểu \[\left( {{n}_{1}},\text{ }{{n}_{2}},\text{ }\ldots ,\text{ }{{n}_{k}} \right)\] của \[k\] phần tử.

Số các hoán vị lặp cấp \[n\] kiểu \[\left( {{n}_{1}},\text{ }{{n}_{2}},\text{ }\ldots ,\text{ }{{n}_{k}} \right)\] của \[k\] phần tử là:

\[{{P}_{n}}\left( {{n}_{1}},\text{ }{{n}_{2}},\text{ }\ldots ,\text{ }{{n}_{k}} \right)\text{ }=\dfrac{n!}{{{n}_{1}}!{{n}_{2}}!…{{n}_{k}}!}\]

4/ Hoán vị vòng quanh:

Cho tập A gồm n phần tử. Một cách sắp xếp n phần tử của tập A thành một dãy kín được gọi là một hoán vị vòng quanh của n phần tử.

Số các hoán vị vòng quanh của n phần tử là:  \[{{Q}_{n}}\text{ }=\text{ }\left( n\text{ }\text{ }1 \right)!\]

1/ Chỉnh hợp (không lặp):

Cho tập hợp A gồm n phần tử. Mỗi cách sắp xếp k phần tử của A (1 £ k £ n) 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ủa tập A.

Số chỉnh hợp chập k của n phần tử:

\[A_{n}^{k}=n(n-1)(n-2)…(n-k+1)=\dfrac{n!}{(n-k)!}\]

• Công thức trên cũng đúng cho trường hợp k = 0 hoặc k = n.
• Khi k = n thì $A_{n}^{n}=\text{ }{{P}_{n}}\text{ }=\text{ }n!$

2/ Chỉnh hợp lặp:

Cho tập A gồm n phần tử. Một dãy gồm k phần tử của A, trong đó mỗi phần tử có thể được lặp lại nhiều lần, được sắp xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập k của n phần tử của tập A.

Số chỉnh hợp lặp chập k của n phần tử: \[\overline{A_{n}^{k}}={{n}^{k}}\]

1/ Tổ hợp (không lặp):

Cho tập A gồm n phần tử. Mỗi tập con gồm k (1 £ k £ n) phần tử của A được gọi là một tổ hợp chập k của n phần tử.

Số các tổ hợp chập k của n phần tử:   \[C_{n}^{k}=\dfrac{A_{n}^{k}}{k!}=\dfrac{n!}{k!(n-k)!}\]

• Qui ước: $C_{n}^{0}$ = 1

Tính chất:

\[C_{n}^{0}=C_{n}^{n}=1;C_{n}^{k}=C_{n}^{n-k};C_{n}^{k}=C_{n-1}^{k-1}+C_{n-1}^{k};C_{n}^{k}=\dfrac{n-k+1}{k}C_{n}^{k-1}\]

2/ Tổ hợp lặp:

Cho tập A = \[\left\{ {{a}_{1}};{{a}_{2}};…;{{a}_{n}} \right\}\] và số tự nhiên k bất kì. Một tổ hợp lặp chập k của n phần tử là một hợp gồm k phần tử, trong đó mỗi phần tử là một trong n phần tử của A.

Số tổ hợp lặp chập k của n phần tử:   \[\overline{C_{n}^{k}}=C_{n+k-1}^{k}=C_{n+k-1}^{m-1}\]

3/ Phân biệt chỉnh hợp và tổ hợp:

• Chỉnh hợp và tổ hợp liên hệ nhau bởi công thức: \[A_{n}^{k}=k!C_{n}^{k}\]
• Chỉnh hợp: có thứ tự.
• Tổ hợp: không có thứ tự.

Þ Những bài toán mà kết quả phụ thuộc vào vị trí các phần tử –> chỉnh hợp

Ngược lại, là tổ hợp.

• Cách lấy k phần tử từ tập n phần tử (k £ n):

+ Không thứ tự, không hoàn lại: \[C_{n}^{k}\]

+ Có thứ tự, không hoàn lại: \[A_{n}^{k}\]

+ Có thứ tự, có hoàn lại: \[\overline{A_{n}^{k}}\]

Phương án 2: Đếm gián tiếp (đếm phần bù)

Trong trường hợp hành động $H$ chia nhiều trường hợp thì ta đi đếm phần bù của bài toán như sau:

$\bullet $ Đếm số phương án thực hiện hành động $H$ (không cần quan tâm đến có thỏa tính chất $T$ hay không) ta được $a$phương án.

$\bullet $ Đếm số phương án thực hiện hành động $H$ không thỏa tính chất $T$ ta được $b$ phương án.

Khi đó số phương án thỏa yêu cầu bài toán là: $a-b$.