Máy tính Hoán vị lệch (Giai thừa phụ)

Chào mừng bạn đến với Máy tính hoán vị lệch (Giai thừa phụ), một công cụ tổ hợp toàn diện giúp tính toán số lượng hoán vị lệch cho bất kỳ tập hợp n phần tử nào. Hoán vị lệch là một hoán vị mà không phần tử nào xuất hiện ở vị trí ban đầu của nó, được ký hiệu là !n hoặc D(n). Cho dù bạn đang nghiên cứu về tổ hợp, giải bài toán kiểm tra mũ cổ điển hay khám phá lý thuyết xác suất, máy tính này đều cung cấp các giải pháp chi tiết từng bước với hình ảnh minh họa tương tác.

Hoán vị lệch là gì?

Một hoán vị lệch (còn được gọi là giai thừa phụ) là một hoán vị của các phần tử của một tập hợp mà không có phần tử nào xuất hiện ở vị trí ban đầu của nó. Số lượng hoán vị lệch của n phần tử được viết là !n (với dấu chấm than trước n) hoặc D(n).

Ví dụ: xem xét ba vật phẩm ở các vị trí {1, 2, 3}. Có tổng cộng 3! = 6 hoán vị, nhưng chỉ có 2 hoán vị lệch:

• (2, 3, 1) — vật phẩm 1 chuyển sang vị trí 2, vật phẩm 2 chuyển sang vị trí 3, vật phẩm 3 chuyển sang vị trí 1
• (3, 1, 2) — vật phẩm 1 chuyển sang vị trí 3, vật phẩm 2 chuyển sang vị trí 1, vật phẩm 3 chuyển sang vị trí 2

Vì vậy !3 = 2.

Công thức hoán vị lệch

Công thức bao hàm-loại trừ

Công thức cơ bản nhất được rút ra từ nguyên lý bao hàm-loại trừ:

Công thức truy hồi

Hoán vị lệch cũng có thể được tính bằng cách truy hồi:

với các trường hợp cơ sở: !0 = 1, !1 = 0.

Công thức số nguyên gần nhất

Đối với \(n \geq 1\), giai thừa phụ bằng số nguyên gần nhất với \(n!/e\):

Bài toán kiểm tra mũ

Ứng dụng nổi tiếng nhất của hoán vị lệch là bài toán kiểm tra mũ (problème des rencontres): nếu n vị khách gửi mũ và những chiếc mũ được trả lại một cách ngẫu nhiên, xác suất để không vị khách nào nhận được đúng mũ của mình là bao nhiêu?

Câu trả lời là \(!n / n!\), hội tụ cực kỳ nhanh về \(1/e \approx 0,3679\). Điều này có nghĩa là khoảng 36,8% tất cả các hoán vị ngẫu nhiên là hoán vị lệch, bất kể có bao nhiêu vật phẩm.

Cách sử dụng máy tính này

1. Nhập n: Nhập số lượng phần tử (0 đến 170). Sử dụng các nút ví dụ nhanh để thử các giá trị phổ biến.
2. Tính toán: Nhấp vào "Tính !n" để tính số hoán vị lệch.
3. Xem kết quả: Xem !n, n!, xác suất hoán vị lệch và tỷ lệ so với 1/e.
4. Khám phá hoạt ảnh: Đối với n nhỏ, hãy tương tác với hoạt ảnh trực quan để xem cách hoạt động của hoán vị lệch.
5. Nghiên cứu các bước: Xem chi tiết phân tích bao hàm-loại trừ và bảng hoán vị lệch.

15 số hoán vị lệch đầu tiên

Ứng dụng của hoán vị lệch

Ông già Noel bí mật / Trao đổi quà

Khi tổ chức trao đổi quà Secret Santa, mỗi người tham gia bốc thăm một cái tên. Một lần bốc thăm thành công khi không ai bốc trúng tên mình chính là một hoán vị lệch. Đối với một nhóm 10 người, có 1.334.961 cách sắp xếp hợp lệ trong tổng số 3.628.800 cách.

Mật mã học và Lý thuyết mã hóa

Hoán vị lệch xuất hiện trong phân tích mật mã thay thế và mã sửa lỗi. Khái niệm "không có điểm cố định" là nền tảng để hiểu sức mạnh của mật mã và mã hóa dựa trên hoán vị.

Xáo bài và Trò chơi

Trong các trò chơi bài, hoán vị lệch đo lường xác suất không có lá bài nào trở lại vị trí ban đầu sau khi tráo. Điều này hữu ích trong việc phân tích chất lượng tráo bài và tính công bằng của trò chơi.

Lý thuyết xác suất

Hoán vị lệch cung cấp một ví dụ thanh lịch về nguyên lý bao hàm-loại trừ và minh họa cách các xác suất có thể hội tụ về các giới hạn đơn giản (trong trường hợp này là 1/e).

Các thuộc tính chính

• Tỷ lệ \(!n/n!\) hội tụ về \(1/e \approx 0,367879\) khi \(n \to \infty\)
• Sự hội tụ cực kỳ nhanh — đã chính xác đến 6 chữ số thập phân ở n = 10
• \(!n\) thỏa mãn hệ thức: \(!n = n \cdot !(n-1) + (-1)^n\)
• Hàm tạo lũy thừa là \(e^{-x}/(1-x)\)
• \(!0 = 1\) (hoán vị rỗng được coi là một hoán vị lệch một cách hiển nhiên)

Câu hỏi thường gặp

Hoán vị lệch là gì?

Hoán vị lệch là một hoán vị của một tập hợp mà không có phần tử nào xuất hiện ở vị trí ban đầu của nó. Ví dụ: nếu các phần tử được gắn nhãn {1, 2, 3}, hoán vị (2, 3, 1) là một hoán vị lệch vì không có phần tử nào ở đúng chỗ cũ. Số lượng hoán vị lệch của n phần tử được ký hiệu là !n (giai thừa phụ n).

Công thức tính giai thừa phụ !n là gì?

Giai thừa phụ !n có thể được tính bằng công thức bao hàm-loại trừ: \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\). Nó cũng có thể được tính bằng công thức truy hồi: \(!n = (n-1)(!(n-1) + !(n-2))\), với !0 = 1 và !1 = 0. Một công thức hữu ích khác là \(!n = \text{làm tròn}(n! / e)\) cho \(n \geq 1\).

Xác suất để một hoán vị ngẫu nhiên là một hoán vị lệch là bao nhiêu?

Xác suất để một hoán vị ngẫu nhiên của n phần tử là một hoán vị lệch tiến tới \(1/e \approx 0,3679\) khi n tăng lên. Ngay cả với n nhỏ, giá trị xấp xỉ này vẫn cực kỳ chính xác. Với n = 5, xác suất chính xác là 44/120 ≈ 0,3667, đã rất gần với 1/e.

Bài toán kiểm tra mũ là gì?

Bài toán kiểm tra mũ (hay còn gọi là problème des rencontres) là một câu đố xác suất kinh điển: nếu n người gửi mũ tại một nhà hàng và những chiếc mũ được trả lại một cách ngẫu nhiên, xác suất để không ai nhận lại đúng mũ của mình là bao nhiêu? Câu trả lời là số hoán vị lệch !n chia cho tổng số hoán vị n!, tiến tới \(1/e \approx 36,79\%\).

Mối quan hệ giữa hoán vị lệch và giai thừa là gì?

Hoán vị lệch (!n) và giai thừa (n!) có liên quan chặt chẽ: \(!n = n! \times \sum(-1)^k/k!\) cho k từ 0 đến n. Tỷ lệ !n/n! cho biết xác suất của một hoán vị lệch, hội tụ về 1/e. Ngoài ra, !n là số nguyên gần nhất với n!/e cho \(n \geq 1\), khiến n!/e trở thành một giá trị xấp xỉ rất hữu ích.

Tài nguyên bổ sung

• Hoán vị lệch - Wikipedia
• Nguyên lý bao hàm-loại trừ - Wikipedia