Công cụ máy tính hoán vị

Công cụ máy tính hoán vị trực tuyến này giúp bạn tính toán số cách sắp xếp $n$ đối tượng riêng biệt, khi chọn ra $r$ phần tử cho mỗi lần sắp xếp. Máy tính sẽ cho bạn biết tổng số cách sắp xếp các đối tượng thành những nhóm nhỏ, trong đó thứ tự sắp xếp là một yếu tố quan trọng. Tổng số đối tượng cần sắp xếp được ký hiệu là $n$, và số phần tử được chọn ra trong mỗi nhóm (tập hợp con) được ký hiệu là $r$.

Ví dụ: Nếu chúng ta muốn sắp xếp các chữ cái X, Y, Z thành từng nhóm gồm hai chữ cái (không lặp lại), chúng ta sẽ có các trường hợp: XY, XZ, YZ, YX, ZX và ZY. Tổng cộng có 6 cách sắp xếp.

Cách sử dụng công cụ máy tính này rất đơn giản: Bạn chỉ cần nhập $n$ (tổng số phần tử) và $r$ (số phần tử cần chọn để sắp xếp), sau đó nhấp vào "Tính toán" (Calculate).

Hoán vị

Hoán vị của một tập hợp là cách sắp xếp các phần tử của tập hợp đó theo một trình tự hoặc thứ tự nhất định. Đối với hoán vị, thứ tự của các phần tử là yếu tố cực kỳ quan trọng. Ví dụ: AB và BA là hai hoán vị hoàn toàn khác nhau. Số hoán vị của tập hợp $n$ phần tử khi chọn ra $r$ phần tử (còn gọi là chỉnh hợp chập $r$ của $n$) được ký hiệu là $nPr$.

Việc tính toán số hoán vị phụ thuộc vào các phần tử được đem ra sắp xếp và việc các phần tử đó có được phép lặp lại hay không. Trừ khi có yêu cầu cụ thể khác, chúng ta luôn mặc định rằng không cho phép sự lặp lại khi tính toán hoán vị.

Trong bài viết này, chúng ta sẽ chỉ xem xét các ví dụ về hoán vị không lặp.

Hoán vị tuân theo quy tắc nhân (nguyên lý đếm cơ bản). Quy tắc này chỉ ra rằng: Nếu một công việc bao gồm $k$ giai đoạn liên tiếp, trong đó giai đoạn thứ nhất có $n_1$ cách thực hiện, giai đoạn thứ hai có $n_2$ cách thực hiện, và tiếp tục như vậy cho đến giai đoạn thứ $k$ có $n_k$ cách thực hiện; thì tổng số cách để hoàn thành toàn bộ công việc đó là tích của các cách thực hiện đơn lẻ: $n_1 \times n_2 \times ... \times n_k$.

Giả sử chúng ta muốn biết có bao nhiêu cách sắp xếp các chữ cái A, B, C mà không có sự lặp lại. Bất kỳ chữ cái nào cũng có thể đứng ở vị trí đầu tiên, vì vậy có 3 cách để chọn chữ cái thứ nhất.

Sau khi đặt chữ cái đầu tiên, chúng ta còn lại hai chữ cái. Bất kỳ chữ cái nào trong hai chữ cái này cũng có thể xếp ở vị trí thứ hai, do đó có 2 cách chọn chữ cái thứ hai. Sau khi đặt xong chữ cái thứ hai, chúng ta chỉ còn lại đúng một chữ cái. Vì vậy, chỉ có 1 cách duy nhất để đặt chữ cái thứ ba.

Theo quy tắc nhân, chúng ta có tổng cộng 3 × 2 × 1 = 6 cách để sắp xếp các chữ cái A, B, C. Cụ thể là: ABC, ACB, BCA, BAC, CAB và CBA.

Giai thừa

Ở ví dụ trên, chúng ta đã xác định được số hoán vị của 3 phần tử phân biệt là 3 × 2 × 1 = 6. Nhìn chung, số hoán vị của một tập hợp gồm $n$ phần tử được tính bằng $n \times (n-1) \times (n-2) \times ... \times 1$.

Đây chính là tích của tất cả các số tự nhiên liên tiếp từ $n$ lùi về 1. Phép toán nhân tất cả các số tự nhiên từ $n$ đến 1 được gọi là giai thừa và được ký hiệu bằng dấu chấm than “!”.

Theo định nghĩa, $n! = n \times (n-1) \times (n-2) \times ... \times 1$, và được đọc là "$n$ giai thừa".

Lưu ý quan trọng: 0! = 1 và 1! = 1.

Ví dụ về hoán vị

Đường đua tiêu chuẩn cho các cự ly điền kinh tại Thế vận hội Olympic thường có 9 làn chạy. Tuy nhiên, đối với cự ly chạy nước rút 100 mét, làn số 1 thường không được sử dụng. Tám vận động viên sẽ được sắp xếp vào các làn từ số 2 đến số 9. Vậy có bao nhiêu cách để sắp xếp 8 vận động viên này vào 8 làn chạy trống?

Áp dụng quy tắc nhân:

• Bất kỳ 1 ai trong 8 vận động viên cũng có thể được xếp vào làn 2.
• Bất kỳ 1 ai trong 7 vận động viên còn lại cũng có thể được xếp vào làn 3.
• Bất kỳ 1 ai trong 6 vận động viên còn lại cũng có thể được xếp vào làn 4.
• Bất kỳ 1 ai trong 5 vận động viên còn lại cũng có thể được xếp vào làn 5.
• Bất kỳ 1 ai trong 4 vận động viên còn lại cũng có thể được xếp vào làn 6.
• Bất kỳ 1 ai trong 3 vận động viên còn lại cũng có thể được xếp vào làn 7.
• Bất kỳ 1 ai trong 2 vận động viên còn lại cũng có thể được xếp vào làn 8.
• Vận động viên duy nhất còn lại sẽ chạy ở làn 9.

Do đó, tổng số cách hoán vị có thể xảy ra khi sắp xếp 8 vận động viên vào 8 làn chạy là: 8! = 8 × 7 × 6 × ... × 2 × 1 = 40.320 cách.

Nếu sử dụng máy tính hoán vị của chúng tôi, bạn chỉ cần nhập số 8 vào cả hai ô $n$ (tổng số phần tử) và $r$ (số phần tử cần xếp), sau đó nhấp vào "Tính toán" để nhận ngay kết quả 40.320.

Hoán vị của tập hợp con (Chỉnh hợp)

Trong các ví dụ trước, chúng ta đã tính toán hoán vị khi tất cả các phần tử đều được đem ra sắp xếp cùng lúc. Tuy nhiên, trong thực tế, có rất nhiều tình huống chúng ta chỉ chọn ra một nhóm nhỏ các phần tử từ một tập hợp lớn để sắp xếp.

Trong trường hợp này, tổng số phần tử ban đầu là $n$, số lượng phần tử được chọn ra để sắp xếp là $r$. Công thức tính số hoán vị (chỉnh hợp) như sau:

$$ₙPᵣ = \frac{n!}{\left(n-r\right)!}$$

Công thức này được dùng để tính số hoán vị không lặp khi chúng ta cần chọn ra $r$ phần tử từ tập hợp $n$ phần tử và sắp xếp chúng theo một thứ tự nhất định.

Nếu chúng ta cần sắp xếp tất cả các phần tử của tập hợp theo một thứ tự nhất định (không lặp lại), công thức sẽ được rút gọn thành:

$$ₙPᵣ=n!$$

Ví dụ

Trở lại với ví dụ về môn điền kinh, chúng ta đã tính được số cách sắp xếp làn chạy cho tất cả 8 vận động viên. Bây giờ, hãy xét đến kết quả chung cuộc: Có 3 tấm huy chương dành cho 3 người về đích đầu tiên. Người về nhất nhận huy chương Vàng, người về nhì nhận huy chương Bạc và người về ba nhận huy chương Đồng. Hỏi có bao nhiêu cách để phân định bộ ba huy chương Vàng, Bạc, Đồng cho 8 vận động viên tham gia?

Theo quy tắc nhân, bất kỳ ai trong số 8 vận động viên đều có khả năng về nhất. Sau khi xác định được người vô địch, sẽ còn lại 7 vận động viên cạnh tranh cho vị trí thứ hai. Tương tự, sau khi xác định được người về nhì, 6 người còn lại sẽ tranh giành vị trí thứ ba.

Do đó, tổng số hoán vị có thể xảy ra cho Top 3 người dẫn đầu từ 8 vận động viên là: 8 × 7 × 6 = 336

Áp dụng công thức hoán vị:

$$ₙPᵣ = \frac{n!}{\left(n-r\right)!}$$

Chúng ta sẽ có phép tính:

$$₈P₃=\frac{8!}{\left(8-3\right)!}=\frac{8!}{5!}=\frac{8×7×6×5×4×\ldots×1}{5×4×\ldots×1}=8×7×6=336$$

Trên công cụ máy tính hoán vị, bạn nhập 8 vào ô $n$ và 3 vào ô $r$, sau đó nhấn "Tính toán" để nhận về kết quả là 336.

Hoán vị và tổ hợp: Sự khác biệt

Một kỹ thuật đếm toán học quan trọng khác là tổ hợp. Tổ hợp là số cách chọn ra một nhóm gồm $r$ phần tử từ một tập hợp lớn hơn gồm $n$ phần tử. Số lượng tổ hợp chập $r$ của $n$ phần tử được ký hiệu là ₙCᵣ.

Như đã định nghĩa, đối với hoán vị, thứ tự sắp xếp là yếu tố bắt buộc phải quan tâm. Đây chính là điểm khác biệt cốt lõi giữa hoán vị và tổ hợp: Trong tổ hợp, thứ tự không quan trọng.

Ví dụ: Chúng ta đã biết số hoán vị khi chọn 2 chữ cái từ tập hợp 3 chữ cái X, Y, Z là 6 cách, bao gồm: XY, XZ, YZ, YX, ZX và ZY.

Tuy nhiên, số tổ hợp khi chọn 2 chữ cái từ tập hợp X, Y, Z chỉ có 3 cách: XY, XZ và YZ. Điều này là do trong tổ hợp, XY và YX được coi là một; XZ và ZX là một; YZ và ZY là một. Tóm lại, thứ tự lựa chọn trước hay sau hoàn toàn không làm thay đổi kết quả của một tổ hợp.

Công thức tính số tổ hợp chập $r$ của $n$ phần tử là:

$$ₙСᵣ=\frac{n!}{r!\left(n-r\right)!}$$

Ví dụ về tính số tổ hợp

Cùng xem lại ví dụ về cuộc đua 100 mét. Chúng ta đã biết cách tính số trường hợp có thể xảy ra cho các vị trí Nhất, Nhì, Ba (có phân biệt huy chương). Nhưng giả sử chúng ta chỉ muốn biết số cách chọn ra 3 vận động viên bước lên bục nhận giải từ nhóm 8 người mà không quan tâm ai giành huy chương gì. Miễn là lọt vào Top 3 để có huy chương là được.

Trong trường hợp này, vì thứ tự (màu huy chương) không quan trọng nên chúng ta sẽ sử dụng công thức tổ hợp để giải quyết bài toán:

$$ₙСᵣ = \frac{n!}{r!(n-r)!}$$

Số cách chọn ra 3 người đạt huy chương bất kỳ từ 8 vận động viên là:

$$₈C₃=\frac{8!}{3! × \left(8-3\right)!}=\frac{8!}{3! × 5!}=\frac{8 × 7 × 6}{3 × 2 × 1}=8×7=56$$

Ví dụ về tính số hoán vị

1. Nhà sản xuất của một chương trình tin tức cần chọn ra 3 diễn giả từ danh sách 5 khách mời chuyên gia. Vì mỗi người sẽ trình bày theo một thứ tự cụ thể (người nói trước, người nói sau) nên thứ tự xuất hiện của khách mời là rất quan trọng. Ngoài ra, một khách mời không thể xuất hiện hai lần trong cùng một chương trình nên không có sự lặp lại. Do đó, chúng ta áp dụng công thức hoán vị:

$$ₙPᵣ = \frac{n!}{(n-r)!}$$

$$₅P₃ = \frac{5!}{(5-3)!} = \frac{5!}{2!} = 5 × 4 × 3 = 60$$

Như vậy, nhà sản xuất có 60 cách khác nhau để sắp xếp thứ tự phát biểu cho các diễn giả.

2. Một chuyên gia phê bình ẩm thực đã chọn ra 10 nhà hàng sushi ngon nhất thị trấn và muốn lập bảng xếp hạng Top 3. Các nhà hàng này phải được sắp xếp theo thứ tự rõ ràng (Hạng 1, Hạng 2, Hạng 3) và không một nhà hàng nào được xuất hiện hai lần trong bảng xếp hạng. Bài toán này đáp ứng đầy đủ hai điều kiện của hoán vị: có phân biệt thứ tự và không lặp lại. Chúng ta sử dụng công thức:

$$ₙPᵣ = \frac{n!}{(n-r)!}$$

$$₁₀P₃ = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 × 9 × 8 = 720$$

Có tới 720 cách để lập bảng xếp hạng Top 3 từ 10 nhà hàng.

3. Khi chúng ta nói rằng "thứ tự là yếu tố quan trọng" trong hoán vị, điều đó không nhất thiết có nghĩa thứ tự phải luôn là các con số từ 1 đến 10 hay Thứ nhất, Thứ hai, v.v. Thứ tự có thể được đại diện bởi các đối tượng cụ thể mà chúng ta đang gán phần tử vào.

Hãy lấy ví dụ về người quản lý của một công ty dịch vụ sửa chữa nhà cửa. Hôm nay, anh ấy nhận được 4 đơn đặt hàng sơn tường ở 4 địa điểm: Một văn phòng làm visa, một nhà kho của nhà máy, một cửa hàng quần áo và một căn phòng trong nhà dân. Công ty hiện có 6 thợ sơn. Mỗi thợ chỉ có thể làm việc ở 1 địa điểm trong ngày. Hai thợ sơn không được phân công sẽ được nghỉ phép.

Trong bài toán này, các địa điểm làm việc (văn phòng làm visa, nhà kho, cửa hàng quần áo, nhà dân) đóng vai trò tương tự như vị trí số 1, 2, 3 và 4.

Người quản lý sẽ phân công như sau:

• Có 6 sự lựa chọn nhân viên để đi sơn văn phòng,
• Có 5 sự lựa chọn nhân viên (từ những người còn lại) để đi sơn nhà kho,
• Có 4 sự lựa chọn nhân viên để đi sơn cửa hàng,
• Có 3 sự lựa chọn nhân viên cuối cùng để đi sơn nhà dân.

Tổng số cách sắp xếp công việc là: 6 × 5 × 4 × 3 = 360 cách.

Rõ ràng, việc ai làm ở đâu là rất quan trọng (có phân biệt thứ tự) và một thợ sơn không thể làm việc ở hai nơi cùng lúc (không lặp lại). Công thức hoán vị giải quyết bài toán này một cách nhanh chóng:

$$ₙPᵣ = \frac{n!}{(n-r)!}$$

$$\frac{6!}{(6-4)!} = \frac{6!}{2!} = 6 × 5 × 4 × 3 = 360$$

Kết quả là người quản lý có đến 360 cách khác nhau để phân công 6 người thợ đi làm tại 4 địa điểm trong ngày hôm đó.