Bài học

Hoán vị của $n$ phần tử

Mục tiêu bài học

Sau bài này, em phát biểu đúng khái niệm hoán vị của $n$ phần tử, chứng minh được công thức $P_n = n!$ bằng chính quy tắc nhân đã học, và vận dụng công thức để đếm số cách sắp xếp toàn bộ một tập hợp phần tử phân biệt theo thứ tự.

Kiến thức nền cần nhớ

Bài trước cho em hai công cụ: quy tắc cộng cho các phương án rời nhau, quy tắc nhân cho các công đoạn nối tiếp (same-grade bridge). Bài này chỉ dùng đúng quy tắc nhân, nhưng theo một cách đặc biệt: mỗi phần tử trong tập hợp chỉ được xếp vào đúng một vị trí, nên số lựa chọn ở mỗi bước sẽ giảm dần đúng một đơn vị — khác hẳn ví dụ mã số ở bài trước, nơi chữ số được phép lặp lại.

Khởi động

5 bạn học sinh xếp hàng chụp ảnh kỷ yếu, mỗi bạn đứng đúng một vị trí trong hàng ngang. Bạn lớp trưởng thắc mắc: có bao nhiêu cách xếp hàng khác nhau cho cả 5 bạn, nếu đổi vị trí hai bạn bất kỳ cũng tính là một cách xếp mới? Đếm trực tiếp bằng cách liệt kê rõ ràng là không khả thi — cần một công thức.

Hoán vị — sắp xếp toàn bộ một tập hợp theo thứ tự

Một cách sắp xếp $n$ phần tử phân biệt vào $n$ vị trí theo một thứ tự nhất định gọi là một hoán vị của $n$ phần tử đó. Để đếm số hoán vị, ta coi việc xếp hàng là một chuỗi $n$ công đoạn nối tiếp: chọn bạn đứng ở vị trí thứ nhất, rồi chọn bạn đứng ở vị trí thứ hai, cứ thế đến vị trí cuối cùng. Vị trí thứ nhất có thể là bất kỳ ai trong 5 bạn: 5 cách. Vì bạn đã đứng vào vị trí thứ nhất không thể đứng thêm vị trí khác, vị trí thứ hai chỉ còn 4 bạn để chọn: 4 cách. Cứ như vậy, số lựa chọn giảm dần đúng một đơn vị qua mỗi vị trí, vì tập phần tử còn lại luôn ít đi một.

Áp dụng quy tắc nhân cho cả 5 công đoạn, số cách xếp 5 bạn thành hàng là $5 \times 4 \times 3 \times 2 \times 1$ . Tích các số nguyên dương liên tiếp từ 1 đến $n$ như vậy có tên riêng là $n$ giai thừa, kí hiệu $n!$ . Vậy số cách xếp 5 bạn là $5! = 120$ cách. Tổng quát, số hoán vị của $n$ phần tử phân biệt, kí hiệu $P_n$ , được tính bởi công thức $P_n = n! = n(n-1)(n-2)\cdots 2 \cdot 1$ — chính là quy tắc nhân áp dụng liên tiếp cho $n$ vị trí, với số lựa chọn giảm dần một đơn vị sau mỗi vị trí đã xếp.

Áp dụng quy tắc nhân cho cả 5 công đoạn, số cách xếp 5 bạn thành hàng là $5 \times 4 \times 3 \times 2 \times 1$. Tích các số nguyên dương liên tiếp từ 1 đến $n$ như vậy có tên riêng là $n$ giai thừa, kí hiệu $n!$. Vậy số cách xếp 5 bạn là $5! = 120$ cách. Tổng quát, số hoán vị của $n$ phần tử phân biệt, kí hiệu $P_n$, được tính bởi công thức $P_n = n! = n(n-1)(n-2)\cdots 2 \cdot 1$ — chính là quy tắc nhân áp dụng liên tiếp cho $n$ vị trí, với số lựa chọn giảm dần một đơn vị sau mỗi vị trí đã xếp.

Quy ước $0! = 1$ (không có phần tử nào để xếp thì chỉ có đúng một cách — "không làm gì"), quy ước này sẽ cần dùng lại khi tính chỉnh hợp và tổ hợp ở hai bài sau. Giai thừa tăng cực nhanh: $4! = 24$ , nhưng $7! = 5040$ — chỉ thêm ba phần tử mà số cách xếp đã tăng hơn 200 lần. Đây là lý do những bài toán xếp chỗ tưởng đơn giản (xếp học sinh vào ghế, xếp sách lên giá) lại có đáp số lớn đến bất ngờ nếu không quen với tốc độ tăng của giai thừa.

Quy ước $0! = 1$ (không có phần tử nào để xếp thì chỉ có đúng một cách — "không làm gì"), quy ước này sẽ cần dùng lại khi tính chỉnh hợp và tổ hợp ở hai bài sau. Giai thừa tăng cực nhanh: $4! = 24$, nhưng $7! = 5040$ — chỉ thêm ba phần tử mà số cách xếp đã tăng hơn 200 lần. Đây là lý do những bài toán xếp chỗ tưởng đơn giản (xếp học sinh vào ghế, xếp sách lên giá) lại có đáp số lớn đến bất ngờ nếu không quen với tốc độ tăng của giai thừa.

Chỉ thêm một phần tử, số cách xếp đã tăng gấp nhiều lần — đặc trưng của hàm giai thừa.

Nhìn vào biểu đồ trên, từ $P_5=120$ lên $P_6=720$ , số cách xếp tăng gấp 6 lần — đúng bằng phần tử thứ 6 vừa được thêm vào, vì $P_6 = 6 \times P_5$ . Quy luật này áp dụng cho mọi $n$ : $P_n = n \times P_{n-1}$ , vì thêm một phần tử mới nghĩa là chọn thêm một vị trí cho phần tử đó trong số $n$ vị trí sẵn có, còn $n-1$ phần tử cũ vẫn giữ nguyên các cách xếp tương đối đã có với nhau. Hiểu quy luật này giúp em kiểm tra nhanh một kết quả tính hoán vị có hợp lý hay không, không cần tính lại toàn bộ giai thừa từ đầu.

Nhìn vào biểu đồ trên, từ $P_5=120$ lên $P_6=720$, số cách xếp tăng gấp 6 lần — đúng bằng phần tử thứ 6 vừa được thêm vào, vì $P_6 = 6 \times P_5$. Quy luật này áp dụng cho mọi $n$: $P_n = n \times P_{n-1}$, vì thêm một phần tử mới nghĩa là chọn thêm một vị trí cho phần tử đó trong số $n$ vị trí sẵn có, còn $n-1$ phần tử cũ vẫn giữ nguyên các cách xếp tương đối đã có với nhau. Hiểu quy luật này giúp em kiểm tra nhanh một kết quả tính hoán vị có hợp lý hay không, không cần tính lại toàn bộ giai thừa từ đầu.

Hoán vị xuất hiện trong rất nhiều tình huống ngoài việc xếp hàng chụp ảnh: xếp lịch thi đấu cho các đội bóng, xếp thứ tự phát biểu trong một cuộc họp, hay xếp các món trong thực đơn theo đúng trình tự phục vụ. Điểm chung của mọi bài toán hoán vị là: có đúng $n$ đối tượng phân biệt, có đúng $n$ vị trí, và mỗi đối tượng nhận đúng một vị trí — không thừa, không thiếu, không lặp lại. Thiếu bất kỳ điều kiện nào trong ba điều đó, bài toán không còn là hoán vị thuần tuý nữa.

Ví dụ

Xếp 5 học sinh thành một hàng chụp ảnh

1
5 bạn học sinh xếp thành một hàng ngang để chụp ảnh kỷ yếu, mỗi bạn đứng đúng một vị trí. Hỏi có bao nhiêu cách xếp hàng khác nhau?
2
Ta có đây là bài toán sắp xếp toàn bộ 5 phần tử phân biệt vào 5 vị trí theo thứ tự — đúng dạng hoán vị của 5 phần tử.
3
Theo công thức $P_n = n!$ , với $n=5$ , số cách xếp là $P_5 = 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ .
Theo công thức $P_n = n!$, với $n=5$, số cách xếp là $P_5 = 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.
4
Vị trí 1: 5 cách. Vị trí 2: 4 cách (còn lại sau khi 1 bạn đã đứng vào vị trí 1). Vị trí 3: 3 cách. Vị trí 4: 2 cách. Vị trí 5: 1 cách duy nhất còn lại. Tích $5 \times 4 \times 3 \times 2 \times 1 = 120$ , khớp với kết quả dùng công thức.
Vị trí 1: 5 cách. Vị trí 2: 4 cách (còn lại sau khi 1 bạn đã đứng vào vị trí 1). Vị trí 3: 3 cách. Vị trí 4: 2 cách. Vị trí 5: 1 cách duy nhất còn lại. Tích $5 \times 4 \times 3 \times 2 \times 1 = 120$, khớp với kết quả dùng công thức.
5
Vậy có 120 cách xếp 5 bạn học sinh thành một hàng.

Ví dụ

Xếp sách lên giá — dạng thi

1
Một giá sách có đúng 4 ngăn liền nhau, mỗi ngăn xếp đúng 1 trong 4 cuốn sách khác nhau (Toán, Lý, Hoá, Sinh). Hỏi có bao nhiêu cách xếp 4 cuốn sách đó lên giá?
2
Ta có 4 cuốn sách phân biệt cần xếp vào 4 vị trí (4 ngăn), mỗi cuốn dùng đúng một lần — đây là hoán vị của 4 phần tử.
3
$P_4 = 4! = 4 \times 3 \times 2 \times 1 = 24$ .
$P_4 = 4! = 4 \times 3 \times 2 \times 1 = 24$.
4
Ngăn 1 có 4 lựa chọn, ngăn 2 còn 3 lựa chọn (một cuốn đã dùng), ngăn 3 còn 2, ngăn 4 còn đúng 1 cuốn duy nhất — tích $4 \times 3 \times 2 \times 1 = 24$ , khớp kết quả trên. Vậy có 24 cách xếp 4 cuốn sách lên giá.
Ngăn 1 có 4 lựa chọn, ngăn 2 còn 3 lựa chọn (một cuốn đã dùng), ngăn 3 còn 2, ngăn 4 còn đúng 1 cuốn duy nhất — tích $4 \times 3 \times 2 \times 1 = 24$, khớp kết quả trên. Vậy có 24 cách xếp 4 cuốn sách lên giá.

Sai lầm thường gặp

Nhiều bạn nhầm hoán vị với quy tắc nhân có lặp ở bài trước, tính nhầm $5^5$ thay vì $5!$ cho bài xếp hàng — sai vì mỗi bạn chỉ được đứng đúng một vị trí, không được lặp lại ở vị trí khác. Một sai lầm khác là quên rằng đổi chỗ hai bạn cũng tạo ra một cách xếp mới — hoán vị luôn tính thứ tự, xếp "An - Bình" và "Bình - An" là hai cách khác nhau.

Luyện tập có hướng dẫn

Luyện tập độc lập

Kiểm tra nhanh

Ghi nhớ

Hoán vị của $n$ phần tử là một cách sắp xếp toàn bộ $n$ phần tử phân biệt theo thứ tự, và số hoán vị bằng $P_n = n!$ — chính là quy tắc nhân áp dụng liên tiếp cho $n$ vị trí, với số lựa chọn giảm dần một đơn vị sau mỗi vị trí vì không được lặp lại phần tử.

Bài tiếp theo hỏi một câu gần giống nhưng khác một chi tiết quan trọng: nếu chỉ cần chọn và sắp xếp $k$ trong số $n$ phần tử — không phải toàn bộ — thì đếm thế nào? Đó là nội dung của chỉnh hợp.