Lý thuyết Hoán vị – Chỉnh hợp và Tổ hợp bao gồm định nghĩa, định lí, các khái niệm về tổ hợp chập n của phần tử.

1. Khái niệm hoán vị

Cho n phần tử khác nhau (n ≥ 1). Mỗi cách sắp thứ tự của n phần tử đã cho, mà trong đó mỗi phần tử có mặt đúng một lần, được gọi là một hoán vị của n phần tử đó.

Định lí: Số các hoán vị của n phần tử khác nhau đã cho (n ≥ 1) được kí hiệu là Pn và bằng:

Pn =n(n-1)(n-2)…2.1=n!

2. Chỉnh hợp

Định nghĩa chỉnh hợp: Cho n phần tử khác nhau (n ≥ 1). Mỗi tập con sắp thứ tự gồm k phần tử khác nhau (1 ≤ k ≤ n) của tập hợp n phần tử đã cho được gọi là một chỉnh hợp chập k của n phần tử đã cho.

Chú ý:

Mỗi hoán vị của n phần tử khác nhau đã cho chính là một chỉnh hợp chập n của n phần tử đó.

Định lí:

Số chỉnh hợp chập k của n phần tử khác nhau đã cho được kí hiệu là Akn và bằng

Akn=n(n−1)…(n−k+1)=n!(n−k)! với (1 ≤ k ≤ n),

Với quy ước 0! = 1.

3. Tổ hợp

Định nghĩa:

Cho n phần tử khác nhau (n ≥ 1). Mỗi tập con gồm k phần tử khác nhau (không phân biệt thứ tự) của tập hợp n phần tử đã cho (0 ≤ k ≤ n) được gọi là một tổ hợp chập k của n phần tử dã cho (với quy ước tổ hợp chập 0 của n phần tử bất kỳ là tập rỗng).

Định lí:

Số các tổ hợp chập k của n phần tử khác nhau đã cho được kí hiệu là Ckn và bằng

Ckn=n!k!(n−k)!=Aknk! , (0 ≤ k ≤ n).

Định lí:

Với mọi n ≥ 1; 0 ≤ k ≤ n, ta có:

a) Ckn=Cn−kn

b) Ckn+Ck+1n=Ck+1n+1 ( công thức Pascal).