Hoán vị

Hoán vị là trường hợp đặc biệt của chỉnh hợp, khi có một tập hợp gồm n phần tử và ta muốn biết số tất cả các bộ n phần tử khác nhau.

Công thức

Ta nhắc lại chỉnh hợp. Cho tập hợp các chữ số {1; 2; 3; 4; 5}. Từ các chữ số này có thể lập được bao nhiêu số có ba chữ số, nếu không chữ số nào được lặp lại? Đây là ví dụ điển hình về chỉnh hợp, giải được bằng công thức quen thuộc

$${\mathrm{A}}_n^k=\frac{n!}{(n-k)!}=\frac{5!}{(5-3)!}=60.$$

Có thể lập được bao nhiêu số có năm chữ số?

$${\mathrm{A}}_5^5=\frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120.$$

Ta nhận thấy rằng nếu có một tập hợp gồm 5 phần tử và cần tìm số tất cả các bộ 5 phần tử khác nhau thì kết quả bằng 5!. Tổng quát hoá lên: nếu có một tập hợp gồm n phần tử thì có tất cả n! bộ n phần tử khác nhau. Từ đó ta đi đến khái niệm hoán vị.

Hoán vị là gì

Cho tập hợp M gồm n phần tử. Một hoán vị là một bộ n phần tử bất kì gồm các phần tử của tập hợp M, trong đó không phần tử nào được lặp lại. Ví dụ: với tập hợp M = {a; b; c; d}, các bộ (a; b; d; c) hay (d; b; a; c) là những hoán vị. Số tất cả các hoán vị khác nhau bằng

$${\mathrm{P}}_n={\mathrm{A}}_n^n=n!$$

Ví dụ có lời giải

1. Có 6 cuốn sách cần xếp lên giá theo một thứ tự nào đó. Có tất cả bao nhiêu thứ tự khác nhau? Có 6 cuốn sách, mỗi lần ta hoán vị tất cả các cuốn sách, nên kết quả bằng P₆ = 6! = 720.

2. Ngoài 6 cuốn sách tiếng Việt ở ví dụ trước, có thêm 4 cuốn sách viết bằng tiếng Latinh. Có bao nhiêu cách xếp 10 cuốn sách này lên giá, nếu muốn tất cả sách tiếng Việt đứng cạnh nhau và tất cả sách tiếng Latinh đứng cạnh nhau?

   Có những cách xếp nào? Có thể xếp 6 cuốn sách tiếng Việt trước rồi đến 4 cuốn sách tiếng Latinh, hoặc ngược lại: 4 cuốn tiếng Latinh trước rồi đến 6 cuốn tiếng Việt. Có 6! cách xếp sách tiếng Việt và 4! cách xếp sách tiếng Latinh. Áp dụng quy tắc nhân, ta nhân các kết quả này: 6! · 4! = 17.280. Vì có 2 cách bố trí hai nhóm sách (tiếng Việt trước rồi tiếng Latinh, hoặc ngược lại), ta nhân số này với 2. Kết quả cuối cùng là 17.280 · 2 = 34.560.