Hoán vị là một kỹ thuật toán học xác định số cách sắp xếp có thể có trong một tập hợp khi thứ tự sắp xếp có ý nghĩa. Hãy để chúng tôi hiểu khái niệm này bằng ví dụ dưới đây:
Stacy có 3 chiếc váy và 2 chiếc túi xách. Có ba cách để chọn một chiếc váy vì có 3 chiếc váy có sẵn. Đối với mỗi sự lựa chọn của một chiếc váy, có hai sự lựa chọn của chiếc túi xách. Do đó, có 3 × 2 = 6 cặp váy và túi xách. Gọi 3 chiếc váy là D 1 , D 2 và D 3 và hai túi xách là H 1 và H 2 . 
Nguyên tắc cơ bản của đếm nói rằng-
| Nếu một biến cố có thể xảy ra theo m cách khác nhau, sau đó biến cố khác có thể xảy ra theo n cách khác nhau thì tổng số lần xuất hiện của biến cố theo thứ tự đã cho là m × n . |
tương tự, đối với ba sự kiện, nguyên tắc như sau:
Nếu một biến cố có thể xảy ra theo m cách khác nhau, tiếp theo biến cố kia xảy ra theo n cách khác nhau, tiếp theo biến cố thứ ba có thể xảy ra theo p cách khác nhau thì tổng số lần xuất hiện của biến cố theo thứ tự đã cho là m × n × P
Trong ví dụ của chúng ta, những cách khác nhau để chọn một chiếc váy và một chiếc túi xách là số cách khác nhau để xảy ra liên tiếp sự kiện sau:
Ví dụ 1: Cho 4 bóng đèn có màu đỏ, lục, lam, vàng khác nhau. Có bao nhiêu tín hiệu khác nhau có thể được tạo ra nếu một tín hiệu yêu cầu sử dụng hai bóng đèn nằm dưới bóng đèn kia?
Lời giải: Có hai chỗ trống có thể lấp đầy bằng bốn bóng đèn có màu khác nhau này. 
Vị trí trống phía trên có thể được chiếm bởi bất kỳ bóng đèn nào trong số bốn bóng đèn, do đó vị trí trên cùng có thể được lấp đầy theo 4 cách khác nhau. Chỗ trống phía dưới có thể được lấp đầy bởi 3 bóng đèn còn lại, do đó có thể lấp đầy chỗ trống phía dưới theo 3 cách khác nhau. Do đó, số lượng tín hiệu cần thiết mà chúng ta có thể tạo ra bằng cách sử dụng 4 bóng đèn là 4 × 3 = 12.
Ở đây chúng tôi đang đếm các hoán vị của 4 bóng đèn khác nhau được lấy 2 bóng đèn cùng một lúc.
Tích của n số tự nhiên đầu tiên 1 × 2 × 3 × 4 × ... × (n−1) × n được gọi là 'n giai thừa' và được ký hiệu là \(n!\)
Hãy nhớ \(0! = 1 \)
Ví dụ 2: Đánh giá \(5!\)
Lời giải: 5 × 4 × 3 × 2 × 1 = 120
Số hoán vị của n đối tượng khác nhau được lấy r tại một thời điểm được ký hiệu là \(^nP_r\) . |
| Số hoán vị của n đối tượng khác nhau được lấy r tại thời điểm cho phép lặp lại là \(n^r\) |
Hãy để chúng tôi hiểu cả hai định lý này bằng cách sử dụng một ví dụ.
Ví dụ 3: Tìm số từ có 4 chữ cái có nghĩa hoặc không có nghĩa, có thể được tạo thành từ các chữ cái của từ HEAD , không được lặp lại các chữ cái.
Giải pháp: Sử dụng định lý 1, \(^nP_r = \frac{n!}{(nr)!}\) , trong đó n là 4 và r là 4, do đó
\(^4 P _4 = \frac{4!}{(4-4)!} = \frac{4!}{1} = 24\)
Bây giờ hãy xem xét nếu cho phép lặp lại các chữ cái, thì số hoán vị có thể có theo định lý 2 là \(4^4 = 256\) .
Ví dụ 4: Tìm số cách chọn một hiệu trưởng và một phó hiệu trưởng trong một nhóm 10 người sao cho cùng một người không được giữ cả hai chức vụ này.
Giải: \(^{10} P _2 = \frac{10!}{(10-2)!} = \frac{10!}{8!} = 10 \times 9 = 90\) tại một thời điểm
| Số hoán vị của n đối tượng, trong đó p 1 đối tượng cùng loại, p 2 cùng loại,... p k thuộc loại k và các đối tượng còn lại, nếu có, thuộc loại khác là \(\frac{n!}{p_1!p_2!...p_k!} \) |
Hãy cho chúng tôi hiểu ứng dụng của định lý này bằng ví dụ dưới đây
Ví dụ 5: Tìm số cách sắp xếp các chữ cái của từ INDEPENDENCE.
Giải pháp: Do các chữ cái lặp lại nên chúng ta sử dụng công thức \(\frac{n!}{p_1!p_2!...p_k!} \) . Có 3 N , 4 E , 2 D , 1 I , 1 P và 1 C .
\(\mathcal{\frac{12!}{3!4!2!} }\) = 1663200
Hãy đổi câu hỏi trên thành: tìm số cách sắp xếp mà từ bắt đầu bằng P
Ở đây vì vị trí của chữ P là cố định nên hãy đếm cách sắp xếp của 11 chữ cái còn lại.
\(\frac{11!}{3!4!2!} = 138600\)
