ไม่มีอะไรมาก แค่มาเติมเล่น ๆ กันลืมครับ. ข้อที่ 3 วันที่ 2
ให้ S(m,n) แทนจำนวนแบบของการเรียงสับเปลี่ยนของนักเรียน m คน เมื่อ n = จำนวนครั้งของการสลับ จะได้ว่า n = 0, 1, 2, ... , m(m -1)/2 (mC2)
และ
S(m, 0) = 1, m ณ 1
S(m, 1) = m - 1 ; m ณ 2
S(m, 2) = (m + 1)(m - 2)/2 ; m ณ 3
S(m, 3) = [ (m - 1)(m - 2)(m + 3)/6 ] - 1 ; m ณ 3
และ S(m, n) = S(m , n - m(m - 1)/2)
และ โดยทั่วไป S(m, n) = S(m - 1, n) + S(m, n - 1) เมื่อ n ฃ m - 1
ทำไม : S(m, n) = S(m - 1, n) + S(m, n - 1)
รูปแบบของการจัดคน m เพื่อให้เกิดการสลับจำนวน n ครั้ง เมื่อ 0 ฃ n ฃ m(m-1)/2 สมมติให้คนทั้ง m คน แทนด้วย จำนวน 1, 2, 3, ... , m ดังนั้นคนที่สูงที่สุด คือ m จำนวนแบบของการสลับทั้งหมด S(m,n ) แบบ จะสามารถแบ่งออกเป็น 2 กรณีคือ
กรณีที่ 1: คนที่สูงที่สุด คือ m ยืนอยู่หลังสุด
กรณีที่ 2 : คนที่สูงที่สุด คือ m ยืนอยู่ตำแหน่งอื่น ๆ ที่ไม่ใช่ตำแหน่งหลังสุด
กรณีที่ 1 : นำคนจำนวน m - 1 คน มายืนในแบบต่าง ๆ เพื่อให้เกิดการสลับทั้งหมด n ครั้ง ซึ่งจะมี S(m - 1, n) แบบ จากนั้นนำคนที่สูงที่สุด ไปยืนข้างหลังสุด จะได้ว่าจำนวนครั้งของการสลับจะไม่เพิ่มขึ้น อีกทั้งจำนวนแบบก็จะเท่าเดิม คือ S(m - 1, n)
กรณีที่ 2 : นำคนจำนวน m คน (รวมนาย m ด้วย) มายืนเพื่อให้เกิดการสลับจำนวน n - 1 ครั้ง โดยให้นาย m ซึ่งสูงที่สุด ยืนอยู่ตรงไหนก็ได้ตั้งแต่ตำแหน่งที่ 2 ถึง ตำแหน่งหลังสุด ซึ่งตอนนี้จะยืนได้ S(m, n - 1) แบบ จากนั้นในแต่ละแบบ ให้สลับ นาย m กับคนที่ยืนอยู่ข้างหน้าเขา ก็จะได้ว่า จำนวนการสลับของคนทั้งหมดจะเพิ่มจากเดิม คือ n - 1 ครั้ง ไปเป็น n - 1 + 1 = n ครั้ง ซึ่งจะมีอยู่ S(m, n - 1) แบบ
นั่นคือ S(m, n) = S(m - 1, n) + S(m, n - 1)
เช่น S(18, 150) = S(18, 153 - 150) = S(18, 3) = (18 - 1)(18 - 2)(18 + 3)/6 - 1 = 952 - 1 = 951
13 กรกฎาคม 2004 20:12 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ gon
|