เครื่องคำนวณดีเรนจ์เมนต์ ซับแฟกทอเรียล

ยินดีต้อนรับสู่ เครื่องคำนวณดีเรนจ์เมนต์ ซับแฟกทอเรียล เครื่องมือทางด้านคอมบิเนทอริกส์ที่ครอบคลุมสำหรับคำนวณจำนวนดีเรนจ์เมนต์สำหรับเซตของ n องค์ประกอบใดๆ ดีเรนจ์เมนต์คือการเรียงสับเปลี่ยนที่ไม่มีองค์ประกอบใดปรากฏในตำแหน่งเดิม เขียนแทนด้วย !n หรือ D(n) ไม่ว่าคุณจะกำลังศึกษาเรื่องคอมบิเนทอริกส์ แก้ปัญหาการคืนหมวกแบบคลาสสิก หรือสำรวจทฤษฎีความน่าจะเป็น เครื่องคำนวณนี้จะให้ผลลัพธ์โดยละเอียดทีละขั้นตอนพร้อมภาพประกอบเชิงโต้ตอบ

ดีเรนจ์เมนต์ คืออะไร?

ดีเรนจ์เมนต์ (หรือเรียกว่า ซับแฟกทอเรียล) คือการเรียงสับเปลี่ยนขององค์ประกอบในเซตที่ ไม่มีองค์ประกอบใดปรากฏในตำแหน่งเดิม จำนวนดีเรนจ์เมนต์ของ n องค์ประกอบเขียนเป็น !n (มีเครื่องหมายอัศเจรีย์หน้า n) หรือ D(n)

ตัวอย่างเช่น พิจารณาสิ่งของสามชิ้นในตำแหน่ง {1, 2, 3} มีการเรียงสับเปลี่ยนทั้งหมด 3! = 6 แบบ แต่มีเพียง 2 แบบเท่านั้นที่เป็นดีเรนจ์เมนต์:

• (2, 3, 1) — ชิ้นที่ 1 ไปที่ตำแหน่ง 2, ชิ้นที่ 2 ไปที่ตำแหน่ง 3, ชิ้นที่ 3 ไปที่ตำแหน่ง 1
• (3, 1, 2) — ชิ้นที่ 1 ไปที่ตำแหน่ง 3, ชิ้นที่ 2 ไปที่ตำแหน่ง 1, ชิ้นที่ 3 ไปที่ตำแหน่ง 2

ดังนั้น !3 = 2

สูตรดีเรนจ์เมนต์

สูตรการรวมเข้าและแยกออก (Inclusion-Exclusion Formula)

สูตรพื้นฐานที่สุดมาจากหลักการรวมเข้าและแยกออก:

สูตรการเรียกซ้ำ (Recursive Formula)

ดีเรนจ์เมนต์ยังสามารถคำนวณได้โดยใช้ความสัมพันธ์เวียนเกิด:

โดยมีกรณีฐานคือ: !0 = 1, !1 = 0

สูตรจำนวนเต็มที่ใกล้เคียงที่สุด

สำหรับ \(n \geq 1\) ซับแฟกทอเรียลจะมีค่าเท่ากับจำนวนเต็มที่ใกล้ที่สุดของ \(n!/e\):

ปัญหาการคืนหมวก (The Hat-Check Problem)

การประยุกต์ใช้ดีเรนจ์เมนต์ที่มีชื่อเสียงที่สุดคือ ปัญหาการคืนหมวก (problème des rencontres): หากมีแขก n คนฝากหมวกไว้และหมวกถูกส่งคืนแบบสุ่ม ความน่าจะเป็นที่ ไม่มีแขกคนใดได้รับหมวกของตัวเองคืนเลย คือเท่าไร?

คำตอบคือ \(!n / n!\) ซึ่งลู่เข้าสู่ \(1/e \approx 0.3679\) อย่างรวดเร็วอย่างน่าประหลาดใจ ซึ่งหมายความว่าประมาณ 36.8% ของการเรียงสับเปลี่ยนแบบสุ่มทั้งหมดจะเป็นดีเรนจ์เมนต์ ไม่ว่าจะมีจำนวนรายการเท่าใดก็ตาม

วิธีใช้เครื่องคำนวณนี้

1. ใส่ค่า n: ป้อนจำนวนองค์ประกอบ (0 ถึง 170) ใช้ปุ่มตัวอย่างด่วนเพื่อลองใช้ค่าที่พบบ่อย
2. คำนวณ: คลิก "คำนวณ !n" เพื่อหาค่าจำนวนดีเรนจ์เมนต์
3. ตรวจสอบผลลัพธ์: ดูค่า !n, n!, ความน่าจะเป็นของดีเรนจ์เมนต์ และอัตราส่วนเทียบกับ 1/e
4. สำรวจแอนิเมชัน: สำหรับ n ขนาดเล็ก ให้โต้ตอบกับแอนิเมชันเพื่อดูว่าดีเรนจ์เมนต์ทำงานอย่างไร
5. ศึกษาขั้นตอน: ตรวจสอบการแจกแจงสูตรการรวมเข้าและแยกออกโดยละเอียด และตารางดีเรนจ์เมนต์

จำนวนดีเรนจ์เมนต์ 15 ลำดับแรก

การประยุกต์ใช้ดีเรนจ์เมนต์

Secret Santa / การแลกของขวัญ

เมื่อจัดกิจกรรมแลกของขวัญ Secret Santa ผู้เข้าร่วมแต่ละคนจะจับสลากชื่อ การจับสลากที่ประสบความสำเร็จคือไม่มีใครจับได้ชื่อตัวเอง ซึ่งก็คือดีเรนจ์เมนต์ สำหรับกลุ่มคน 10 คน มีการจัดเรียงที่ถูกต้อง 1,334,961 แบบจากการจัดเรียงทั้งหมด 3,628,800 แบบ

วิทยาการรหัสลับและทฤษฎีการเข้ารหัส

ดีเรนจ์เมนต์ปรากฏในการวิเคราะห์รหัสลับแบบแทนที่ (substitution ciphers) และรหัสแก้ไขข้อผิดพลาด (error-correcting codes) แนวคิดเรื่อง "ไม่มีจุดคงที่" เป็นพื้นฐานในการทำความเข้าใจความแข็งแกร่งของรหัสและการเข้ารหัสแบบใช้การเรียงสับเปลี่ยน

การสับไพ่และเกมต่างๆ

ในเกมไพ่ ดีเรนจ์เมนต์จะวัดความน่าจะเป็นที่ไม่มีไพ่ใบใดกลับมาอยู่ที่ตำแหน่งเดิมหลังจากการสับไพ่ สิ่งนี้มีประโยชน์ในการวิเคราะห์คุณภาพของการสับไพ่และความยุติธรรมของเกม

ทฤษฎีความน่าจะเป็น

ดีเรนจ์เมนต์เป็นตัวอย่างที่สง่างามของหลักการรวมเข้าและแยกออก และแสดงให้เห็นว่าความน่าจะเป็นสามารถลู่เข้าสู่ขีดจำกัดที่เรียบง่ายได้อย่างไร (1/e ในกรณีนี้)

คุณสมบัติหลัก

• อัตราส่วน \(!n/n!\) ลู่เข้าสู่ \(1/e \approx 0.367879\) เมื่อ \(n \to \infty\)
• การลู่เข้านั้นเร็วมาก — มีความแม่นยำถึงทศนิยม 6 ตำแหน่งเมื่อ n = 10
• \(!n\) สอดคล้องกับความสัมพันธ์เวียนเกิด: \(!n = n \cdot !(n-1) + (-1)^n\)
• ฟังก์ชันก่อกำเนิดเลขชี้กำลังคือ \(e^{-x}/(1-x)\)
• \(!0 = 1\) (การเรียงสับเปลี่ยนว่างถือเป็นดีเรนจ์เมนต์โดยปริยาย)

คำถามที่พบบ่อย

ดีเรนจ์เมนต์คืออะไร?

ดีเรนจ์เมนต์คือการเรียงสับเปลี่ยนของเซตที่ไม่มีองค์ประกอบใดปรากฏในตำแหน่งเดิม ตัวอย่างเช่น หากสิ่งของถูกติดป้าย {1, 2, 3} การเรียงสับเปลี่ยน (2, 3, 1) คือดีเรนจ์เมนต์เนื่องจากไม่มีรายการใดอยู่ในที่เดิม จำนวนดีเรนจ์เมนต์ของ n รายการ เขียนแทนด้วย !n (ซับแฟกทอเรียล n)

สูตรสำหรับซับแฟกทอเรียล !n คืออะไร?

ซับแฟกทอเรียล !n สามารถคำนวณได้โดยใช้สูตรการรวมเข้าและแยกออก: \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\) นอกจากนี้ยังสามารถคำนวณแบบเรียกซ้ำได้: \(!n = (n-1)(!(n-1) + !(n-2))\) โดยที่ !0 = 1 และ !1 = 0 อีกสูตรที่มีประโยชน์คือ \(!n = \text{round}(n! / e)\) สำหรับ \(n \geq 1\)

ความน่าจะเป็นที่การเรียงสับเปลี่ยนแบบสุ่มจะเป็นดีเรนจ์เมนต์คือเท่าไร?

ความน่าจะเป็นที่การเรียงสับเปลี่ยนแบบสุ่มของ n รายการจะเป็นดีเรนจ์เมนต์จะเข้าใกล้ \(1/e \approx 0.3679\) เมื่อ n เพิ่มขึ้น แม้แต่สำหรับ n ขนาดเล็ก ค่าประมาณนี้ก็มีความแม่นยำอย่างมาก สำหรับ n = 5 ความน่าจะเป็นที่แน่นอนคือ 44/120 ≈ 0.3667 ซึ่งใกล้เคียงกับ 1/e มากแล้ว

ปัญหาการคืนหมวกคืออะไร?

ปัญหาการคืนหมวก (หรือที่เรียกว่า problème des rencontres) เป็นปริศนาความน่าจะเป็นแบบคลาสสิก: หากมีคน n คนฝากหมวกไว้ที่ร้านอาหารและหมวกถูกส่งคืนแบบสุ่ม ความน่าจะเป็นที่จะไม่มีใครได้รับหมวกของตัวเองคืนเลยคือเท่าไร? คำตอบคือจำนวนดีเรนจ์เมนต์ !n หารด้วยการเรียงสับเปลี่ยนทั้งหมด n! ซึ่งเข้าใกล้ \(1/e \approx 36.79\%\)

ความสัมพันธ์ระหว่างดีเรนจ์เมนต์และแฟกทอเรียลคืออะไร?

ดีเรนจ์เมนต์ (!n) และแฟกทอเรียล (n!) มีความสัมพันธ์กันอย่างใกล้ชิด: \(!n = n! \times \sum(-1)^k/k!\) สำหรับ k ตั้งแต่ 0 ถึง n อัตราส่วน !n/n! ให้ค่าความน่าจะเป็นของดีเรนจ์เมนต์ ซึ่งลู่เข้าสู่ 1/e นอกจากนี้ !n ยังเป็นจำนวนเต็มที่ใกล้เคียงที่สุดกับ n!/e สำหรับ \(n \geq 1\) ทำให้ n!/e เป็นค่าประมาณที่มีประโยชน์มาก

แหล่งข้อมูลเพิ่มเติม

• ดีเรนจ์เมนต์ - Wikipedia
• หลักการรวมเข้าและแยกออก - Wikipedia
• OEIS A000166 - ลำดับซับแฟกทอเรียล