การเรียงสับเปลี่ยน หลักการทางคณิตศาสตร์และการประยุกต์ใช้

ในทางคณิตศาสตร์ การเรียงสับเปลี่ยน (Permutation) มีความหมายหลักสองประการ ประการแรกคือ การจัดเรียงสมาชิกของเซตให้อยู่ในลำดับหรือลำดับเชิงเส้น (Sequence or Linear Order) และประการที่สองคือ กระบวนการหรือการกระทำในการเปลี่ยนลำดับเชิงเส้นของเซตที่ถูกจัดลำดับไว้แล้ว

นิยามและการคำนวณ

การจัดเรียงลำดับ

ตัวอย่างของการเรียงสับเปลี่ยนในความหมายแรกคือ การนำเซต {1, 2, 3} มาจัดเรียงลำดับ ซึ่งจะได้ทั้งหมด 6 รูปแบบ ได้แก่ (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) และ (3, 2, 1) เช่นเดียวกับการสร้างคำอนาแกรม (Anagram) จากคำที่ตัวอักษรไม่ซ้ำกัน ซึ่งเป็นการนำตัวอักษรเดิมมาเรียงสับเปลี่ยนตำแหน่งใหม่

จำนวนวิธีการเรียงสับเปลี่ยนของวัตถุที่แตกต่างกัน n ชิ้น คือ n แฟกทอเรียล (n!) ซึ่งหมายถึงผลคูณของจำนวนเต็มบวกทั้งหมดที่มีค่าน้อยกว่าหรือเท่ากับ n

ฟังก์ชันทางคณิตศาสตร์

ในความหมายที่สอง การเรียงสับเปลี่ยนของเซต S คือ ฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึง (Bijection) จาก S ไปยัง S ซึ่งหมายความว่าทุกสมาชิกใน S จะปรากฏเป็นค่าผลลัพธ์เพียงครั้งเดียว

ฟังก์ชันนี้เทียบเท่ากับการจัดเรียงสมาชิกของ S ใหม่ โดยที่สมาชิก i จะถูกแทนที่ด้วย σ(i) ตัวอย่างเช่น การเรียงสับเปลี่ยน (3, 1, 2) จะตรงกับฟังก์ชัน σ ที่กำหนดให้ σ(1) = 3, σ(2) = 1 และ σ(3) = 2

กลุ่มของการเรียงสับเปลี่ยนทั้งหมดของเซตหนึ่งจะรวมกันเป็นกลุ่มที่เรียกว่า กลุ่มสมมาตร (Symmetric Group) โดยมีการดำเนินการคือการประกอบฟังก์ชัน (Composition of functions) ซึ่งผลลัพธ์ที่ได้จะเป็นการเรียงสับเปลี่ยนรูปแบบใหม่

การเรียงสับเปลี่ยนบางส่วน (Partial Permutations)

ในวิชาคอมบิเนทอริกเบื้องต้น k-permutations หรือการเรียงสับเปลี่ยนบางส่วน คือการจัดเรียงลำดับของสมาชิก k ตัวที่เลือกมาจากเซตที่มีสมาชิกทั้งหมด n ตัว หาก k มีค่าเท่ากับขนาดของเซต จะกลายเป็นการเรียงสับเปลี่ยนแบบเต็มรูปแบบตามที่กล่าวไว้ข้างต้น

ประวัติความเป็นมา

แนวคิดเรื่องการเรียงสับเปลี่ยนปรากฏอยู่ในหลายวัฒนธรรมทั่วโลก:

• จีน: มีการใช้สิ่งที่คล้ายกับการเรียงสับเปลี่ยนในคัมภีร์อี้จิง (I Ching) ตั้งแต่ 1,000 ปีก่อนคริสตกาล
• กรีก: พลูทาร์คบันทึกว่า เซโนเครทีสแห่งคาลเซดอน (396–314 ปีก่อนคริสตกาล) ได้ศึกษาจำนวนพยางค์ที่แตกต่างกันในภาษากรีก ซึ่งถือเป็นความพยายามครั้งแรกๆ ในการแก้ปัญหาการเรียงสับเปลี่ยนและจัดหมู่
• อาหรับ: อัล-คาลิล (ค.ศ. 717–786) นักคณิตศาสตร์และนักถอดรหัส ได้เขียนหนังสือเกี่ยวกับการถอดรหัสที่ใช้การเรียงสับเปลี่ยนเพื่อหาคำที่เป็นไปได้ทั้งหมดในภาษาอาหรับ
• อินเดีย: กฎการคำนวณจำนวนการเรียงสับเปลี่ยนของวัตถุ n ชิ้น เป็นที่รู้จักในวัฒนธรรมอินเดียราว ค.ศ. 1150 โดยปรากฏในตำรา ลิลวตี (Lilavati) ของภาสการะที่ 2 (Bhāskara II)
• ยุโรป: ในปี ค.ศ. 1677 เฟเบียน สเตดแมน (Fabian Stedman) ได้อธิบายเรื่องแฟกทอเรียลผ่านการจัดลำดับเสียงระฆัง (Change ringing) โดยใช้วิธีการคิดแบบเรียกซ้ำ (Recursive process)

ในช่วงปี ค.ศ. 1770 โจเซฟ หลุยส์ ลากรานฌ์ (Joseph Louis Lagrange) พบว่าคุณสมบัติของการเรียงสับเปลี่ยนรากของสมการพหุนามมีความสัมพันธ์กับความเป็นไปได้ในการหาคำตอบของสมการนั้น ซึ่งนำไปสู่การพัฒนา ทฤษฎีของกาลัว (Galois Theory) โดยเอวาริสต์ กาลัว (Évariste Galois) ซึ่งอธิบายขอบเขตของการแก้สมการพหุนามด้วยเครื่องหมายกรณฑ์ (Radicals)

การประยุกต์ใช้ในศาสตร์ต่างๆ

การเรียงสับเปลี่ยนถูกนำไปใช้ในหลากหลายสาขา ได้แก่:

• วิทยาการคอมพิวเตอร์: ใช้ในการวิเคราะห์อัลกอริทึมการเรียงลำดับ (Sorting algorithms)
• ฟิสิกส์ควอนตัม: ใช้ในการอธิบายสถานะของอนุภาค
• ชีววิทยา: ใช้ในการอธิบายลำดับของ RNA