Máy tính Hoán vị Có lặp

Giới thiệu về Máy tính Hoán vị Có lặp

Máy tính Hoán vị Có lặp tính toán số lượng các cách sắp xếp có thứ tự khi các phần tử có thể được chọn nhiều hơn một lần, sử dụng công thức n^r. Nhập số lượng phần tử có sẵn (n) và số lượng vị trí cần điền (r) để nhận ngay kết quả tổng cộng, lời giải chi tiết từng bước, hình ảnh trực quan hóa vòng quay tương tác, so sánh với các phương pháp đếm khác, bảng tăng trưởng và các ví dụ thực tế. Công cụ này hỗ trợ cả các giá trị nhỏ và các giá trị cực lớn mang tính thiên văn.

Hoán vị có lặp là gì?

Hoán vị có lặp (còn được gọi là sắp xếp có thứ tự có hoàn lại hoặc r-tuple) đếm số cách để lấp đầy r vị trí có thứ tự bằng cách sử dụng n phần tử riêng biệt, trong đó mỗi phần tử có thể được sử dụng bất kỳ số lần nào. Kết quả là n^r bởi vì mỗi vị trí trong số r vị trí đều có n lựa chọn một cách độc lập.

Ví dụ, tạo mã PIN 4 chữ số từ các chữ số 0–9: mỗi vị trí trong số 4 vị trí có thể là bất kỳ chữ số nào trong 10 chữ số, tạo ra 10⁴ = 10.000 mã PIN khả thi. Mã "1111" là hợp lệ (tất cả các vị trí sử dụng cùng một chữ số) và "1234" khác với "4321" (thứ tự quan trọng).

Công thức: n^r

Công thức được suy ra trực tiếp từ nguyên lý nhân (còn gọi là nguyên lý đếm cơ bản):

• Vị trí 1 có n lựa chọn
• Vị trí 2 có n lựa chọn (phần tử có thể lặp lại)
• Vị trí 3 có n lựa chọn
• … và tiếp tục như vậy cho tất cả r vị trí

Tổng số cách sắp xếp = n × n × n × … × n (r lần) = n^r

Hoán vị có lặp so với các phương pháp đếm khác

Có bốn công thức đếm chính trong tổ hợp xác suất. Việc hiểu khi nào nên sử dụng mỗi công thức phụ thuộc vào hai câu hỏi: Thứ tự có quan trọng không? và Các phần tử có thể lặp lại không?

• Hoán vị có lặp (n^r) — thứ tự quan trọng, cho phép lặp lại. Ví dụ: Mã PIN, mật khẩu.
• Hoán vị không lặp (n!/(n−r)!) — thứ tự quan trọng, không lặp lại. Ví dụ: vị trí về đích trong một cuộc đua.
• Tổ hợp không lặp (C(n,r) = n!/(r!(n−r)!)) — thứ tự không quan trọng, không lặp lại. Ví dụ: bốc thăm xổ số.
• Tổ hợp có lặp (C(n+r−1,r)) — thứ tự không quan trọng, cho phép lặp lại. Ví dụ: chọn các viên kem.

Ứng dụng thực tế phổ biến

• Mã PIN và mật khẩu: Một mã PIN 4 chữ số sử dụng 0–9 có 10⁴ = 10.000 khả năng. Một mật khẩu 8 ký tự sử dụng 62 ký tự (a–z, A–Z, 0–9) có 62⁸ ≈ 218 nghìn tỷ khả năng.
• Chuỗi nhị phân: Một byte 8-bit có 2⁸ = 256 giá trị có thể có. Một số nguyên 32-bit có 2³² ≈ 4,3 tỷ giá trị.
• Tung xúc xắc: Tung một con xúc xắc 6 mặt tiêu chuẩn 3 lần tạo ra 6³ = 216 chuỗi kết quả có thể có.
• Biển số xe: Một biển số với 6 vị trí ký tự số và chữ sử dụng 36 ký tự tạo ra 36⁶ ≈ 2,18 tỷ biển số duy nhất.
• Bài kiểm tra trắc nghiệm: Một bài kiểm tra 20 câu hỏi với 4 lựa chọn mỗi câu có 4²⁰ ≈ 1,1 nghìn tỷ bảng trả lời có thể có.
• Trình tự di truyền: Các trình tự DNA có độ dài r sử dụng 4 loại nucleotide (A, T, C, G) có 4^r trình tự khả thi.

Tại sao n^r tăng trưởng quá nhanh

Sự tăng trưởng theo hàm mũ vô cùng mạnh mẽ. Ngay cả những gia tăng nhỏ trong n hoặc r cũng dẫn đến kết quả khổng lồ:

• Gấp đôi r sẽ làm bình phương kết quả: n^2r = (n^r)²
• Thêm 1 vào r sẽ nhân kết quả với n: n^r+1 = n × n^r
• Đây là lý do tại sao mật khẩu dài hơn an toàn hơn theo cấp số nhân — mỗi ký tự thêm vào sẽ nhân không gian tìm kiếm với n

Các trường hợp đặc biệt

• n⁰ = 1 — Có chính xác một cách để lấp đầy không vị trí: không làm gì cả (sắp xếp rỗng).
• n¹ = n — Lấp đầy một vị trí đơn giản là chọn một trong n phần tử.
• 1^r = 1 — Nếu chỉ có một phần tử, mọi vị trí đều phải sử dụng nó, tạo ra một cách sắp xếp duy nhất.
• 2^r — Chuỗi nhị phân có độ dài r. Điều này bằng số lượng tập hợp con của một tập hợp có r phần tử.

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

1. Nhập n, tổng số phần tử riêng biệt có sẵn để chọn (ví dụ: 10 cho các chữ số 0–9, 26 cho các chữ cái A–Z).
2. Nhập r, số lượng vị trí hoặc ô cần lấp đầy. Mỗi vị trí có thể sử dụng bất kỳ phần tử nào trong n phần tử, bao gồm cả các phần tử đã được sử dụng ở nơi khác.
3. Nhấp vào "Tính toán hoán vị" để tính kết quả.
4. Xem lại lời giải từng bước, trực quan hóa ô, bảng so sánh, biểu đồ tăng trưởng và ví dụ thực tế.
5. Sử dụng các nút kịch bản nhanh để khám phá các ví dụ thực tế phổ biến.

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

Hoán vị có lặp là gì?

Hoán vị có lặp là các cách sắp xếp có thứ tự trong đó mỗi phần tử có thể được chọn nhiều hơn một lần. Công thức là n^r, trong đó n là số phần tử để chọn và r là số vị trí cần lấp đầy. Ví dụ, mã PIN 4 chữ số sử dụng các chữ số 0–9 có 10⁴ = 10.000 cách sắp xếp có thể có.

Sự khác biệt giữa hoán vị có lặp và không lặp là gì?

Trong hoán vị không lặp, một khi phần tử đã được sử dụng thì không thể sử dụng lại, tạo ra n!/(n−r)! cách sắp xếp (và yêu cầu r ≤ n). Với hoán vị có lặp, mỗi phần tử có thể được tái sử dụng ở bất kỳ vị trí nào, tạo ra n^r cách sắp xếp. Hoán vị có lặp luôn tạo ra kết quả lớn hơn hoặc bằng vì không có hạn chế về việc tái sử dụng và r có thể vượt quá n.

Khi nào tôi nên sử dụng hoán vị có lặp?

Sử dụng hoán vị có lặp khi (1) thứ tự quan trọng (cách sắp xếp ABC khác với CBA) và (2) các phần tử có thể được tái sử dụng (cùng một phần tử có thể xuất hiện ở nhiều vị trí). Các ví dụ phổ biến bao gồm mã PIN, mật khẩu, tung xúc xắc, biển số xe, chuỗi nhị phân và trình tự di truyền.

r có thể lớn hơn n không?

Có. Không giống như hoán vị không lặp (yêu cầu r ≤ n), hoán vị có lặp cho phép r là bất kỳ số nguyên không âm nào. Một mật khẩu 10 ký tự được rút ra từ 26 chữ cái (r = 10, n = 26) có 26¹⁰ ≈ 141 nghìn tỷ khả năng.

Công thức tính hoán vị có lặp là gì?

Công thức là n^r (n lũy thừa r), trong đó n là số phần tử riêng biệt có sẵn và r là số vị trí cần lấp đầy. Điều này tuân theo nguyên lý nhân: mỗi vị trí trong số r vị trí đều có n lựa chọn độc lập, vì vậy tổng cộng là n × n × … × n (r lần).