ตัวเลข Stirling ประเภทที่สอง: จัดของขวัญไม่ซ้ำลงกล่องที่เหมือนกันได้กี่แบบ
ตัวเลข Stirling ประเภทที่สอง (ชื่อภาษาอังกฤษเท่ๆ ว่า Stirling Number of the 2nd Kind – ฟังแล้วเหมือนจะโดนมนุษย์ต่างดาวจับตัวไปยังไงยังงั้น 555) เป็นตัวเลขชุดหนึ่งที่เอาไว้ใช้อธิบายวิธีการจัดกลุ่มของสิ่งของที่ไม่ซ้ำกัน
สมมุติว่าเราเป็นซานต้ามีของเล่นอยู่ทั้งหมด $n$ ชิ้น (ไม่มีชิ้นใดซ้ำกัน) ต้องการจัดของเล่นใส่กล่อง $k$ กล่อง (ทุกกล่องเหมือนกัน) โดยมีข้อแม้ว่า เมื่อจัดของเล่นเสร็จต้องไม่มีกล่องใดว่างเปล่า ให้คำนวณจำนวนวิธีการจัดของเล่น $S(n,k)$ ว่ามีค่าเป็นเท่าไหร่?
ฟังดูเหมือนจะยากถ้าพยายามคำนวณตรงๆ สำหรับแต่ละ $S(n,k)$ แต่ถ้ามองว่าการหาค่าดังกล่าวสามารถใช้ค่าก่อนหน้ามาช่วยคำนวณได้ (recursive) ก็จะทำให้ปัญหานี้ง่ายลงมาก การใช้ข้อมูลชุดก่อนหน้าสามารถแบ่งได้เป็น 2 แนวทาง ดังนี้
- APPEND: จัดของเล่น $n-1$ ชิ้นลงกล่อง $k$ กล่องไปเรียบร้อยแล้ว (ได้ $S(n-1,k)$ วิธี) เมื่อต้องการจัดของเล่นเพิ่มอีกหนึ่งชิ้น เนื่องจากทุกกล่องมีของเล่นอย่างน้อยหนึ่งชิ้นแล้ว ของเล่นชิ้นที่เพิ่มมานี้จะถูกจัดลงกล่องใดก็ได้ ซึ่งหมายถึงมีทางเลือกเพิ่ม $k$ ทาง (เท่ากับจำนวนกล่อง) ดังนั้นก็จะจัดของเล่นได้เพิ่มเป็น $k$ เท่าของ $S(n-1,k)$
- CREATE: จัดของเล่น $n-1$ ชิ้นลงกล่อง $k-1$ กล่องไปเรียบร้อยแล้ว (ได้ $S(n-1,k-1)$ วิธี) เมื่อต้องการจัดของเล่นเพิ่มอีกหนึ่งชิ้น จะโดนบังคับให้จัดของเล่นชิ้นนี้ลงกล่องที่ยังว่างเปล่าไม่มีของเล่นเท่านั้น ดังนั้นวิธีการจัดของเล่นจะเท่าเดิม
เนื่องจากทั้ง 2 แนวทางดังกล่าวไม่สามารถเกิดขึ้นพร้อมกันได้ และไม่มีแนวทางอื่นใดในการจัดของอีก ผลลัพธ์ของวิธีการทั้งหมดก็คือการจับวิธีทั้งสองมารวมกัน
\[S(n,k) = \underbrace{kS(n-1,k)}_\text{APPEND} + \underbrace{S(n-1,k-1)}_\text{CREATE}\]ค่าตัวอย่างบางค่าของ $S(n,k)$ ต่างๆ เมื่อนำมาแสดงเป็นตาราง คือ
\[\begin{array}{r|rr} n \backslash k & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 1 & \\ 2 & 1 & 1 \\ 3 & 1 & 3 & 1 \\ 4 & 1 & 7 & 6 & 1 \\ 5 & 1 & 15 & 25 & 10 & 1 \\ 6 & 1 & 31 & 90 & 65 & 15 & 1 \\ \end{array}\]แล้วถ้าซานต้าใจดี ไม่อยากเห็นเด็กร้องไห้เสียใจหากได้ของเล่นน้อยเกินไป เลยตั้งกฎว่าแต่ละกล่องต้องมีของเล่นอย่างน้อย $r$ ชิ้นหละ? วิธีคิดจะคล้ายเดิมเลย เพียงแต่เปลี่ยนแนวทางที่สองเป็น
- CREATE: มีของเล่น $n-1$ ชิ้น เลือกของเล่น $r-1$ ชิ้นออกมาใส่กล่องเดียวก่อน แล้วเอาของเล่นชิ้นใหม่ใส่ตามลงไปพร้อมห่อของกล่องขวัญกล่องนี้ไม่ใส่ของเล่นเพิ่มได้อีก การสร้างกล่องนี้กล่องเดียวมีจำนวนวิธีเท่ากับ $\binom{n-1}{r-1}$ ซึ่งจะเป็นตัวคูณของวิธีการจัดของเล่น $n-r$ ชิ้นลงกล่อง $k-1$ กล่องที่เหลือ
โดยทั้ง 2 แนวทางนี้ก็ยังไม่มีทางที่จะเกิดขึ้นได้พร้อมกัน เพราะ APPEND จะทำให้กล่องที่มีของเล่นชิ้นใหม่นั้น มีจำนวนของเล่นมากกว่า $r$ ชิ้นแน่นอน ส่วน CREATE จะทำให้กล่องที่มีของเล่นชิ้นใหม่มีของเล่นทั้งหมดเท่ากับ $r$ ชิ้นพอดี ดังนั้นจึงได้สมการว่า
\[S_r(n,k) = k S_r(n-1,k) + \underbrace{ \binom{n-1}{r-1} S_r(n-r,k-1) }_\text{CREATE}\]สังเกตว่า หากแทนค่า $r=1$ จะได้ผลลัพธ์กลับไปเป็นสมการแบบแรกนั่นเอง
เมื่อรู้พื้นฐานแล้ว ก็เอาไปเขียนโปรแกรมแบบง่ายๆ ได้ดังนี้
from math import factorial
choose = lambda n, r: factorial(n) // factorial(r) // factorial(n-r)
def stirling2nd(n, k, r=1):
if n < r:
return 0
if k == 1 and n >= r:
return 1
return k * stirling2nd(n-1, k, r) + choose(n-1, r-1) * stirling2nd(n-r, k-1, r)
ไม่รู้ว่าจะใช้ได้ดีกับเลขใหญ่ๆ หรือเปล่า เพราะดูแล้วมันน่าจะ recursive ไปเยอะมากเลย ถ้าจะเอาไปใช้จริงเขียนเป็น dynamic เก็บในตารางด้วยก็ดี
author