order preserving transformation and Function

[MoDErN_SnC]

เรื่องดังกล่าวนี้จะหาได้จากที่ไหนบ้างอ่ะครับ (โดยเฉพาะ order preserving transformation)

เพราะผมหาทั้งในอินเตอร์เน็ตและห้องสมุดของมหาวิทยาลัยก็หาไม่เจอเลยอ่ะคับ

เรื่องฟังก์ชันนี่...อยากรู้ว่า ฟังก์ชันประกอบ มีสมบัติทางพีชคณิตอะไรบ้าง....
พวก เปลี่ยนกลุ่ม เอกลักษณ์ สมบัติปิด เป็นต้น
หนังสือที่จะหานี่ควรใช้หนังสือประเภทไหนดีครับ
(หาในอินเตอร์เนทแล้วหาไม่เจออ่ะครับ)

ทีนี้เรื่องจำนวนฟังก์ชัน จากการที่ทำโปรเจค
อ.แนะนำเกี่ยวกับ Stirling Number

\[
S_{(n,r)} = \frac{1}{{r!}}\sum\limits_{i = 0}^r {( - 1)^i \left( \begin{array}{l}
n \\
r \\
\end{array} \right)\left( {r - 1} \right)^n }
\]

มันเป็นอย่างไรช่วยชี้แจงแถลงไขหน่อยครับ

[nooonuii]

ข้อความเดิมเขียนโดยคุณ MoDErN_SnC

เรื่องดังกล่าวนี้จะหาได้จากที่ไหนบ้างอ่ะครับ (โดยเฉพาะ order preserving transformation)

น่าจะมีในหนังสือพวก Universal Algebra ครับ

ข้อความเดิมเขียนโดยคุณ MoDErN_SnC

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

อย่างน้อยๆก็มีคุณสมบัติของ semigroup ครับ
ลองหาจากตำราวิชา Algebraic Semigroup Theory ดูครับ

ส่วน Stirling Number ผมไม่ทราบครับ รอผู้รู้ทางด้าน Combinatorics มาแถลงครับ

[TOP]

ข้อความเดิมเขียนโดยคุณ MoDErN_SnC

ทีนี้เรื่องจำนวนฟังก์ชัน จากการที่ทำโปรเจค
อ.แนะนำเกี่ยวกับ 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\]
เห็นวิธีพิจารณาแล้วคุ้นไหมครับ หากเราตัด $r$ ที่คูณออกไปสักตัว ก็จะดูคล้ายกับสูตรของสัมประสิทธิ์ทวินามอันหนึ่ง คือ \[{n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}\ ,\ \forall n > 0\]

[MoDErN_SnC]

ถามเพิ่มเติมอีกนิดนึงครับ

การคอมโพสิทของฟังก์ชัน เป็น binary operation หรือเปล่าครับ?

[nooonuii]

ข้อความเดิมเขียนโดยคุณ MoDErN_SnC

การคอมโพสิทของฟังก์ชัน เป็น binary operation หรือเปล่าครับ?

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