เครื่องคำนวณจำนวนสเตอร์ลิง

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

จำนวนสเตอร์ลิงคืออะไร?

จำนวนสเตอร์ลิงเป็นกลุ่มตัวเลขสองชุดที่เกิดขึ้นตามธรรมชาติในวิชาเชิงการจัด พีชคณิต และการวิเคราะห์ ตั้งชื่อตามนักคณิตศาสตร์ชาวสก็อต เจมส์ สเตอร์ลิง (1692–1770) พวกมันทำหน้าที่เชื่อมโยงระหว่างแฟกทอเรียล สัมประสิทธิ์ทวินาม และเอกลักษณ์พหุนาม แม้ว่าพวกมันจะเป็นที่รู้จักน้อยกว่าสามเหลี่ยมปาสกาล แต่พวกมันก็มีความสำคัญพื้นฐานและปรากฏอยู่ทั่ววิชาคณิตศาสตร์ไม่ต่อเนื่อง

จำนวนสเตอร์ลิงชนิดที่หนึ่ง

จำนวนสเตอร์ลิงชนิดที่หนึ่งแบบไม่มีเครื่องหมาย เขียนแทนด้วย \(|s(n,k)|\) หรือ \(\left[{n \atop k}\right]\) คือจำนวนวิธีการ เรียงสับเปลี่ยน ของสมาชิก \(n\) ตัวที่แยกออกเป็นวงจรที่แยกจากกันได้ \(k\) วงจร พอดี

สัญชาตญาณ: พิจารณาว่าสมาชิก \(n\) ไปอยู่ที่ไหน มันสามารถถูกแทรกลงในหนึ่งในวงจรที่มีอยู่ (มีตำแหน่งที่สามารถแทรกได้ \(n-1\) ตำแหน่ง คือก่อนสมาชิกตัวอื่นๆ \(n-1\) ตัว) — ซึ่งตรงกับพจน์ \((n-1)\cdot|s(n-1,k)|\) — หรือมันสร้างวงจรใหม่ที่มีสมาชิกเพียงตัวเดียว ซึ่งตรงกับพจน์ \(|s(n-1,k-1)|\)

ข้อเท็จจริงสำคัญ:

• \(|s(n,1)| = (n-1)!\) — การเรียงสับเปลี่ยนแบบวงกลม (หนึ่งวงจรใหญ่)
• \(|s(n,n)| = 1\) — การเรียงสับเปลี่ยนเอกลักษณ์ (จุดตรึงทั้งหมด)
• \(|s(n,n-1)| = \binom{n}{2}\) — การสลับที่หนึ่งคู่
• \(\sum_{k=0}^{n} |s(n,k)| = n!\) — จำนวนการเรียงสับเปลี่ยนทั้งหมด

จำนวนสเตอร์ลิงชนิดที่สอง

จำนวนสเตอร์ลิงชนิดที่สอง เขียนแทนด้วย \(S(n,k)\) หรือ \(\left\{{n \atop k}\right\}\) คือจำนวนวิธีในการ แบ่ง เซตที่มีสมาชิก \(n\) ตัวออกเป็น \(k\) เซตย่อยที่ไม่ว่างพอดี

สัญชาตญาณ: พิจารณาว่าสมาชิก \(n\) ไปอยู่ที่ไหน มันสามารถเข้าร่วมกับหนึ่งใน \(k\) เซตย่อยที่มีอยู่ (มี \(k\) ทางเลือก) — ซึ่งตรงกับพจน์ \(k \cdot S(n-1,k)\) — หรือมันสร้างเซตย่อยใหม่ที่มีมันเพียงตัวเดียว ซึ่งตรงกับพจน์ \(S(n-1,k-1)\)

ข้อเท็จจริงสำคัญ:

• \(S(n,1) = 1\) — มีเพียงวิธีเดียว: สมาชิกทั้งหมดอยู่ในเซตเดียว
• \(S(n,n) = 1\) — มีเพียงวิธีเดียว: ทุกสมาชิกเป็นเซตย่อยที่มีตัวเดียว
• \(S(n,2) = 2^{n-1} - 1\) — วิธีในการแยกออกเป็นสองเซตย่อยที่ไม่ว่าง
• \(S(n,n-1) = \binom{n}{2}\) — เลือกคู่ที่ใช้เซตย่อยร่วมกัน
• \(\sum_{k=0}^{n} S(n,k) = B(n)\) — จำนวนเบลล์ลำดับที่ \(n\)

สูตรชัดแจ้ง (ชนิดที่สอง)

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

1. ป้อน n: จำนวนสมาชิกทั้งหมด (0 ถึง 200)
2. ป้อน k: จำนวนวงจร (ชนิดที่หนึ่ง) หรือเซตย่อย (ชนิดที่สอง) โดยที่ 0 ≤ k ≤ n
3. เลือกชนิด: เลือกชนิดที่หนึ่ง, ชนิดที่สอง หรือทั้งสองอย่างเพื่อเปรียบเทียบแบบเคียงข้างกัน
4. คำนวณ: คลิก "คำนวณจำนวนสเตอร์ลิง" เพื่อดูผลลัพธ์พร้อมการหาค่าทีละขั้นตอน การแสดงภาพสามเหลี่ยม และแผนภูมิการกระจาย

การเปรียบเทียบ: ชนิดที่หนึ่ง vs ชนิดที่สอง

การประยุกต์ใช้จำนวนสเตอร์ลิง

การแปลงพหุนาม

จำนวนสเตอร์ลิงเชื่อมโยงฐานพหุนามที่แตกต่างกัน:

• แฟกทอเรียลแบบเพิ่ม: \(x^{(n)} = \sum_{k} |s(n,k)|\, x^k\)
• กำลังปกติ: \(x^n = \sum_{k} S(n,k)\, x^{\underline{k}}\) (แฟกทอเรียลแบบลด)

ความน่าจะเป็นและสถิติ

จำนวนสเตอร์ลิงปรากฏในการคำนวณ โมเมนต์ของการแจกแจงความน่าจะเป็น โดยเฉพาะอย่างยิ่งเมื่อต้องแปลงระหว่างโมเมนต์ปกติและโมเมนต์แฟกทอเรียล มีความจำเป็นในการวิเคราะห์การเรียงสับเปลี่ยนแบบสุ่มและปัญหาการเข้าพัก (occupancy problems)

วิทยาการคอมพิวเตอร์

ในการวิเคราะห์อัลกอริทึม จำนวนสเตอร์ลิงปรากฏในการนับวิธีจัดสรรวัตถุลงในภาชนะ การวิเคราะห์ตารางแฮช และการศึกษาการเรียงสับเปลี่ยนแบบสุ่ม ชนิดที่สองเกี่ยวข้องโดยตรงกับการนับ ฟังก์ชันทั่วถึง (surjective function): จำนวนฟังก์ชันทั่วถึงจากเซต n ไปยังเซต k คือ \(k!\, S(n,k)\)

ทฤษฎีจำนวน

จำนวนสเตอร์ลิงเชื่อมโยงกับ จำนวนเบอร์นูลลี, จำนวนฮาร์มอนิก และเอกลักษณ์การรวมต่างๆ ปรากฏในแคลคูลัสผลต่างจำกัด (finite difference calculus) และในสูตร Euler-Maclaurin

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

จำนวนสเตอร์ลิงชนิดที่หนึ่งคืออะไร?

จำนวนสเตอร์ลิงชนิดที่หนึ่งแบบไม่มีเครื่องหมาย เขียนแทนด้วย |s(n,k)| นับจำนวนการเรียงสับเปลี่ยนของ n สมาชิกที่แยกออกเป็นวงจรที่แยกจากกันได้ k วงจรพอดี เป็นไปตามความสัมพันธ์เวียนเกิด |s(n,k)| = (n−1)·|s(n−1,k)| + |s(n−1,k−1)| โดยที่ |s(0,0)| = 1 ผลรวมของแถวคือ n! เนื่องจากทุกการเรียงสับเปลี่ยนจะมีจำนวนวงจรจำนวนหนึ่ง

จำนวนสเตอร์ลิงชนิดที่สองคืออะไร?

จำนวนสเตอร์ลิงชนิดที่สอง เขียนแทนด้วย S(n,k) นับจำนวนวิธีในการแบ่งเซตของ n สมาชิกออกเป็น k เซตย่อยที่ไม่ว่างพอดี เป็นไปตามความสัมพันธ์เวียนเกิด S(n,k) = k·S(n−1,k) + S(n−1,k−1) โดยที่ S(0,0) = 1 ผลรวมของแถวจะให้ค่าจำนวนเบลล์ B(n)

ความแตกต่างระหว่างจำนวนสเตอร์ลิงชนิดที่หนึ่งและชนิดที่สองคืออะไร?

ชนิดที่หนึ่ง (unsigned) นับการเรียงสับเปลี่ยนด้วย k วงจร — ลำดับภายในแต่ละวงจรมีความสำคัญ ชนิดที่สองนับการแบ่งเซตเป็น k เซตย่อย — ลำดับภายในเซตย่อยไม่มีความสำคัญ ทั้งสองมีความสัมพันธ์กันผ่านการอินเวอร์สเมทริกซ์ โดยสามเหลี่ยมของชนิดที่หนึ่งแบบมีเครื่องหมายคือตัวผกผันของสามเหลี่ยมชนิดที่สอง

จำนวนสเตอร์ลิงถูกนำไปใช้ในคณิตศาสตร์อย่างไร?

จำนวนสเตอร์ลิงปรากฏในการแปลงพหุนามระหว่างแฟกทอเรียลแบบลด/เพิ่มและกำลังปกติ ในการคำนวณโมเมนต์ของการแจกแจงความน่าจะเป็น ในเอกลักษณ์เชิงการจัด ในทฤษฎีจำนวน และในการวิเคราะห์อัลกอริทึม

ความสัมพันธ์ระหว่างจำนวนสเตอร์ลิงและจำนวนเบลล์คืออะไร?

จำนวนเบลล์ลำดับที่ n B(n) เท่ากับผลรวมของจำนวนสเตอร์ลิงชนิดที่สองทั้งหมดในแถว n: B(n) = Σ S(n,k) สำหรับ k = 0 ถึง n จำนวนเบลล์นับจำนวนวิธีทั้งหมดในการแบ่งเซตของ n สมาชิกออกเป็นเซตย่อยที่ไม่ว่างกี่เซตก็ได้

มีสูตรชัดแจ้งสำหรับจำนวนสเตอร์ลิงหรือไม่?

ใช่ ชนิดที่สองมีสูตรชัดแจ้งผ่านหลักการรวมเข้าและตัดออก: S(n,k) = (1/k!) Σ (−1)^(k−j) C(k,j) j^n สำหรับ j = 0 ถึง k ส่วนชนิดที่หนึ่งสามารถคำนวณได้จากความสัมพันธ์เวียนเกิดหรือผ่านความเชื่อมโยงกับแฟกทอเรียลแบบเพิ่ม

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

• จำนวนสเตอร์ลิงชนิดที่หนึ่ง - Wikipedia
• จำนวนสเตอร์ลิงชนิดที่สอง - Wikipedia
• OEIS A008277 - จำนวนสเตอร์ลิงชนิดที่สอง
• OEIS A130534 - จำนวนสเตอร์ลิงชนิดที่หนึ่งแบบไม่มีเครื่องหมาย