Hoán vị vòng cổ là gì?
Hoán vị vòng cổ (còn gọi là sắp xếp vòng tay, hay trong tiếng Nhật là hoán vị "juzu" — chuỗi tràng hạt) đếm số cách khác nhau để sắp xếp n vật phân biệt thành một vòng kín, trong đó hai cách sắp xếp được xem là giống nhau nếu có thể biến cách này thành cách kia bằng cách xoay vòng hoặc lật ngược nó lại (phép phản chiếu qua gương). Khái niệm này nâng cao hơn một bậc so với hoán vị vòng tròn: hoán vị vòng tròn chỉ loại bỏ tính đối xứng khi xoay, còn vòng cổ thì loại bỏ thêm cả tính đối xứng qua gương.
Cách dùng máy tính này
Bạn nhập số lượng vật phân biệt n (một số nguyên không âm) và máy tính sẽ trả về số cách sắp xếp vòng cổ khác nhau. Để bạn dễ so sánh, công cụ còn hiển thị thêm số hoán vị tuyến tính (\(n!\)) và số hoán vị vòng tròn (\((n-1)!\)). Vì giai thừa tăng cực kỳ nhanh, kết quả được tính bằng số học số nguyên với độ chính xác tùy ý, nên ngay cả những giá trị n rất lớn cũng được hiển thị chính xác tuyệt đối.
Giải thích công thức
Với n vật sắp xếp theo hàng tuyến tính thì có \(n!\) cách. Cố định một vật trên vòng để loại bỏ n cách xoay tương đương, ta còn lại \((n-1)!\) cách sắp xếp vòng tròn. Vòng cổ còn coi một mẫu theo chiều kim đồng hồ và ảnh phản chiếu ngược chiều của nó là giống nhau, nên ta chia thêm cho 2 một lần nữa:
$$P = \frac{(n - 1)!}{2}$$với n ≥ 3.
Với n = 0, 1 và 2, công thức đơn giản này sẽ cho ra số không nguyên hoặc đếm thiếu, nên theo quy ước, đáp án trong từng trường hợp này đều là 1: chỉ tồn tại đúng một vòng khác biệt (hoặc vòng rỗng).
Ví dụ minh họa
Với n = 5: $$\frac{(5 - 1)!}{2} = \frac{4!}{2} = \frac{24}{2} = \mathbf{12}$$ vòng cổ khác nhau. Với n = 6: \(\frac{5!}{2} = \frac{120}{2} = 60\). Với n = 4: \(\frac{3!}{2} = 3\).
Câu hỏi thường gặp
Hoán vị vòng cổ khác hoán vị vòng tròn ở điểm nào? Hoán vị vòng tròn là \((n-1)!\) và coi các cách xoay là giống nhau nhưng xem ảnh phản chiếu là khác nhau. Hoán vị vòng cổ chia kết quả đó cho 2 vì phép lật cũng được coi là giống nhau.
Tại sao đáp án bằng 1 khi n = 2? Với hai vật chỉ có duy nhất một vòng khả dĩ; việc xoay hay lật nó chỉ đơn giản là hoán đổi vị trí của hai vật, nên mọi cách sắp xếp đều trùng nhau. Công thức \(\frac{(2-1)!}{2} = \frac{1}{2}\) không hợp lệ ở đây, đó là lý do ta dùng trường hợp đặc biệt.
Công thức có giả định mọi vật đều khác nhau không? Đúng vậy. Máy tính này giả định n vật phân biệt. Nếu có một số vật giống nhau, số lượng cách sắp xếp sẽ nhỏ hơn và cần một cách xử lý khác (định lý Burnside/Polya).
