การเรียงสับเปลี่ยนเชิงเส้น I

สิ่งของที่แตกต่างกันทั้งหมด

หากเราต้องการเลือกตัวอักษร A, B, C และ D มา 2 ตัวเพื่อเรียงเป็นแนวเส้นตรงจะสามารถทำได้โดยมีวิธีการดังนี้

AB AC AD BA BC BD
CA CB CD DA DB DC

ซึ่งพบว่ามีอยู่ 12 วิธีที่แตกต่างกัน เราสังเกตว่าจำนวนวิธีใส่ตัวอักษรในตำแหน่งที่หนึ่ง (ตำแหน่งซ้ายสุดของการเรียงแต่ละตัว) จะสามารถเลือกใส่ได้ 4 วิธีซึ่งเท่ากับจำนวนตัวอักษรที่มีให้เลือก

มากไปกว่านั้น ในแต่ละวิธีที่เราใส่ตัวอักษรในตำแหน่งแรกเรามีตัวอักษรเหลืออยู่ 3 ตัว จึงเลือกได้ 3 วิธีเพื่อมาใส่ในตำแหน่งที่สอง
ดังนั้นเราสามารถคำนวณจำนวนวิธีได้เป็น 4x3 = 12 นั่นเอง

จากการเรียงข้างต้น หากมีคำถามต่อไปว่าถ้าต้องการเรียงตัวอักษร 3 ตัวในแนวเส้นตรงจะสามารถทำได้กี่วิธี สังเกตว่าทุกๆการเรียงตัวอักษรสามตัวสามารถทำได้จากการเรียงตัวอักษรสองตำแหน่งแรกก่อนแล้วจึงเลือกตัวอักษรที่เลือกมาใส่ในตำแหน่งที่สาม

ตัวอย่างเช่น ถ้าเราพิจารณาการเรียง ABC จะพบว่าการเรียงนี้เกิดจากการเรียง AB แล้วจึงใส่ C ลงในตำแหน่งที่สาม ดังนั้นในการหาจำนวนวิธีการเรียงตัวอักษร 3 ตัวทั้งหมด สามารถหาได้จากจำนวนวิธีการเลือกตัวอักษรมาใส่ตำแหน่งที่หนึ่ง ซึ่งทำได้ 4 วิธี ในแต่ละวิธีของการใส่ตัวอักษรตำแหน่งที่หนึ่ง เราเลือกตัวอักษรที่เหลือมาใส่ตำแหน่งที่สองได้ 3 วิธี ซึ่งขณะนี้เราสามารถทำได้ 4x3 วิธี และในแต่ละวิธีของ 4x3 วิธีนี้เราสามารถเลือกตัวอักษรที่เหลือ 2 ตัวจากการใส่ตำแหน่งที่หนึ่งและสองได้ 2 วิธี เพื่อใส่ตำแหน่งที่สาม ดังนั้นเราสามารถเรียงตัวอักษร 3 ตัวได้ 4x3x2 = 24 วิธี

จากตัวอย่างข้างต้น เราสามารถขยายการนับจำนวนวิธีไปสู่กรณีทั่วไปได้โดยให้มีสิ่งของ n สิ่งที่แตกต่างกันทั้งหมด เลือกสิ่งของเหล่านี้มา r สิ่งเพื่อเรียงเป็นแนวเส้นตรง แล้วหาจำนวนวิธีการเรียงที่แตกต่างกัน ซึ่งเราสามารถทำได้ดังนี้

ตำแหน่งที่ 1 เราเลือกสิ่งของ n สิ่งมาใส่ได้ n วิธี

ตำแหน่งที่ 2 ในแต่ละวิธีของการใส่ตำแหน่งที่ 1 เราเลือกสิ่งของที่เหลือ
n-1 สิ่งมาใส่ได้อีก n-1 วิธี จึงเรียง
2 ตำแหน่งแรกได้ n(n-1) วิธี

ตำแหน่งที่ 3 ในแต่ละวิธีของการใส่
2 ตำแหน่งแรก เราเลือกสิ่งของที่เหลือ
n-2 สิ่งมาใส่ได้อีก n-2 วิธีจึงเรียง
3 ตำแหน่งแรกได้ n(n-1)(n-2) วิธี

ตำแหน่งที่ r ในแต่ละวิธีของการใส่ r-1 ตำแหน่งแรก เราเลือกสิ่งของที่เหลือ
n-(r-1) = n-r+1 สิ่ง มาใส่ได้อีก n-r+1 วิธีจึงทำได้ n(n-1)(n-2)…(n-r+1) วิธี

ถ้าเราให้สัญลักษณ์ P_n,r แทนจำนวนวิธีเลือกสิ่งของ
r สิ่งจากสิ่งของ n สิ่งที่แตกต่างกันมาเรียงเป็นแนว
เส้นตรง จึงได้ว่า P_n,r = n(n-1)(n-2)…(n-r+1)

สังเกตว่าถ้า r > n เราไม่สามารถเลือกสิ่งของจำนวนมากกว่าสิ่งที่มีอยู่มาเรียงได้ เราจึงได้ P_n_,r = 0

ในกรณีที่ r = 0 สัญลักษณ์ P_n,0 หมายถึงการเลือกสิ่งของ 0 สิ่งจาก n สิ่งมาเรียงลำดับ ซึ่งสามาถทำได้ 1 วิธีคือการไม่เรียงนั่นเอง

ดังนั้นเราจึงมักสนใจกรณีที่ 0 ≤ r ≤ n

อันที่จริงแล้ว เราสามารถจัดรูป P_n,rให้อยู่ในรูปของ
แฟกทอเรียลได้ดังนี้
$P subscript n comma r end subscript equals n left parenthesis n minus 1 right parenthesis... left parenthesis n minus r plus 1 right parenthesis space space space space space space space equals n left parenthesis n minus 1 right parenthesis... left parenthesis n minus r plus 1 right parenthesis cross times fraction numerator left parenthesis n minus r right parenthesis...2 cross times 1 over denominator left parenthesis n minus r right parenthesis...2 cross times 1 end fraction space space space space space space space equals fraction numerator n factorial over denominator left parenthesis n minus r right parenthesis factorial end fraction$

การเรียงสับเปลี่ยนเชิงเส้น I

แบบฝึกหัด