Mathcenter Forum - order preserving transformation and Function

อ้างอิง:

ข้อความเดิมเขียนโดยคุณ MoDErN_SnC (ข้อความที่ 19916)

ทีนี้เรื่องจำนวนฟังก์ชัน จากการที่ทำโปรเจค
อ.แนะนำเกี่ยวกับ Stirling Number\[
S_{(n,r)} = \frac{1}{{r!}}\sum\limits_{\color{red}{i = 0}}^r {( - 1)^{\color{red}{i}} \left( \begin{array}{l}
n \\
r \\
\end{array} \right)\left( {r - 1} \right)^n }
\]มันเป็นอย่างไรช่วยชี้แจงแถลงไขหน่อยครับ :)

สูตรผิดหรือเปล่า ส่วนที่เกี่ยวข้องกับ $i$ มีแค่ $(-1)^i$ เท่านั้น เทอมที่เหลือไม่น่าจะอยู่หลัง $\Sigma$ นะครับ

สูตรที่ใกล้เคียงที่สุดที่ผมมีคือ
\[S_{n,r} = \frac{1}{r!} \sum_{j = 1}^{r} (-1)^{r-j} \binom{r}{j} j^n \]
ซึ่งเป็น Stirling numbers of the second kind (จากชื่อของมัน แสดงให้เห็นว่าต้องมี Stirling numbers of the first kind)

สัญลักษณ์ที่ใช้เขียนแทนจำนวน Stirling numbers ทั้งสองแบบอีกวิธีหนึ่ง เขียนคล้ายกับสัมประสิทธิ์ทวินาม คือ ${n \brack r}$ และ ${n \brace r}$ แทน Stirling numbers of the first kind และ Stirling numbers of the second kind ตามลำดับ (ยังมี Eulerian number ซึ่งเขียนคล้ายกันคือ ${n \euler r}$)

สำหรับความหมายของ Stirling numbers of the second kind อ้างอิงจาก Concrete Mathematics โดย สุดยอดปรมาจารย์คอมพิวเตอร์ Donald E. Knuth

${n \brace r}$ คือจำนวนวิธีแบ่งของ $n$ สิ่ง ซึ่งแตกต่างกันทั้งหมด ออกเป็น $r$ กลุ่ม โดยแต่ละกลุ่มห้ามว่างเปล่า (nonempty)

ยกตัวอย่างเช่น เราจะแบ่ง $\{1 , 2 , 3 , 4\}$ ออกเป็น $2$ กลุ่ม จะทำได้ $7$ วิธีคือ
$\{1 , 2 , 3\}\cup \{4\}$
$\{1 , 2 , 4\} \cup \{3\}$
$\{1 , 3 , 4\} \cup \{2\}$
$\{2 , 3 , 4\} \cup \{1\}$
$\{1 , 2\} \cup \{3 , 4\}$
$\{1 , 3\} \cup \{2 , 4\}$
$\{1 , 4\} \cup \{2 , 3\}$
ดังนั้นในกรณีนี้ จะได้ ${4 \brace 2} = 7$

เนื่องจากมีเพียงวิธีเดียวในการแบ่งของ $n$ สิ่ง เป็น $1$ กลุ่ม ดังนั้น ${n \brace 1} = 1\ ,\ \forall n > 0$ (แต่ ${0 \brace 1} = 0$ เพราะไม่มีสิ่งของให้แบ่ง)

นอกจากนี้ ${0 \brace 0} = 1$ เพราะมีเพียงวิธีเดียวในการแบ่งของที่ไม่มีอยู่ ออกเป็น 0 กลุ่มที่ไม่ว่างเปล่า และ ${n \brace 0} = 0\ ,\ \forall n > 0$ เพราะของที่มีอยู่ อย่างน้อยต้องแบ่งได้หนึ่งกลุ่มที่ไม่ว่างเปล่าเสมอ

แล้ว ${n \brace 2} = ?$
กรณีที่ $n > 0$ ลองเลือกของสักชิ้นหนึ่งมาพิจารณา เราจะพบว่าของอีก $n-1$ ชิ้นที่เหลือนั้น มีจำนวนวิธีเลือกที่จะมากองอยู่รวมกันกับของชิ้นนี้ได้ทั้งสิ้น $2^{n-1}$ วิธี แต่จะเลือกมาทั้งหมดไม่ได้เพราะ จะแบ่งได้เพียงกลุ่มเดียว ดังนั้นเราจึงได้ว่า ${n \brace 2} = 2^{n-1} - 1$
(จากตัวอย่างที่แล้ว จะได้ ${4 \brace 2} = 7 = 2^{4-1} - 1$)

สำหรับ ${n \brace r}$ ก็พิจารณาในทำนองเดียวกัน ลองเลือกของสักชิ้นหนึ่งมาพิจารณา เราจะพบว่าวิธีแบ่งกลุ่มมีสองแนวทางหลักคือ

ของที่เลือกมานี้อยู่อย่างโดดเดี่ยว ดังนั้นของ $n-1$ สิ่งที่เหลือจึงนำมาแบ่งกลุ่มกันเองได้ทั้งสิ้น ${n-1 \brace r-1}$ วิธี
ของที่เลือกมานี้อยู่รวมกับของชิ้นอื่น ซึ่งของ $n-1$ ที่เหลือนำมาแบ่งกลุ่มกันเองได้ทั้งสิ้น ${n-1 \brace r}$ วิธี และในแต่ละวิธีเราเลือกกลุ่มที่จะนำของชิ้นนี้ไปรวมด้วยได้ $r$ วิธี จึงได้จำนวนวิธีทั้งหมดเป็น $r{n-1 \brace r}$ วิธี

ดังนั้นจะได้สูตรในรูปของความสัมพันธ์เวียนบังเกิดคือ \[{n \brace r} = {n-1 \brace r-1} + r{n-1 \brace r}\ ,\ \forall n > 0\]
เห็นวิธีพิจารณาแล้วคุ้นไหมครับ :sung: หากเราตัด $r$ ที่คูณออกไปสักตัว ก็จะดูคล้ายกับสูตรของสัมประสิทธิ์ทวินามอันหนึ่ง :rolleyes: คือ \[{n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}\ ,\ \forall n > 0\]