ก่อนหน้านั้นผมได้เขียนบทความการเรียงสับเปลี่ยนเชิงเส้นไปแล้ว และได้ยกตัวอย่างไว้เป็นอันมากหลาย ใครที่ยังไม่ได้อ่านก็ควรเริ่มอ่านจากบทความนี้ก่อน การเรียงสับเปลี่ยนเชิงเส้น สำหรับบทความนี้ก็เป็นการเรียงสับเปลี่ยนเชิงเส้นเหมือนกันแต่เป็นการเรียงสับเปลี่ยนเชิงเส้นสำหรับสิ่ิงของที่ไม่ต่างกันทั้งหมด พูดง่ายๆก็คือมีสิ่งของซ้ำกันนั่นเองครับ
ไม่พูดพร่ำทำเพลงอธิบายให้ยืดยาว เรามาดูสูตรในการเรียงสับเปลี่ยนสิ่งของที่ไม่แตกต่างกันทั้งหมดเลยครับ
ถ้ามีสิ่งของอยู่ n สิ่งในจำนวนนี้มี \(n_{1}\) สิ่งที่เหมือนกันเป็นกลุ่มที่หนึ่ง มี \(n_{2}\) สิ่งที่เหมือนกันเป็นกลุ่มที่สอง...มี \(n_{k}\) สิ่งที่เหมือนกันเป็นกลุ่มที่ k โดยทีี \(n_{1}+n_{2}+...n_{k}=n\) จำนวนวิธีเรียงสับเปลี่ยนกลุ่มของสิ่งของ n สิ่งที่ไม่แตกต่างกันทั้งหมดเท่ากับ \[\frac{n!}{n_{1}!\times n_{2}! \times ...\times n_{k}!}\] |
มาดูตัวอย่างการทำโจทย์กันเลยครับ
ตัวอย่างที่ 1 จงหาจำนวนวิธีเรียงสับเปลี่ยนตัวอักษรจากคำว่า "MATHEMATICS" ที่แตกต่างกัน โดยที่ไม่คำนึงถึงความหมาย
วิธีทำ นับจำนวนตัวอักษรได้ทั้งหมด 11 ตัว นั่นคือ \(n! = 11!\)
มีตัวอักษร M อยู่ 2 ตัว
มีตัวอักษร A อยู่ 2 ตัว
มีตัวอักษร T อยู่ 2 ตัว
และมีตัวอักษร H,E,I,C และ S อย่างละ 1 ตัว
จำนวนวิธีเรียงสับเปลี่ยนตัวอักษรดังกล่าวเท่ากับ
\(\frac{11!}{2!2!2!1!1!1!1!1!}=4989,600\) วิธี ต่อไปที่สิ่งของมีอย่างละ 1 ตัวคือ 1! ไม่ต้องใส่ก็ได้ค่าเท่าเดิม
ตัวอย่างที่ 2 มีหนังสือคณิตศาสตร์ 3 เล่ม หนังสือภาษาอังกฤษ 2 เล่ม และหนังสือและหนังสือภาษาไทย 4 เล่ม ถ้าถือว่าหนังสือวิชาเดียวกันไม่แตกต่างกันแล้วจะจัดเรียงหนังสือทั้งหมดบนชั้นวางหน้ังสือได้กี่วิธี
วิธีทำ ข้อนี้จะเห็นว่าหนังสือไม่แตกต่างกันก็คือสิ่ิงของที่เรานำมาจัดเรียงไม่แตกต่างกันทั้งหมด หรือมีสิ่งของซ้ำกันนั่นเองใช้สูตรข้างบนได้เลย
มีหนังสือรวมทั้งหมด 3+2+4=9 เล่ม
มีหน้งสือคณิตศาสตร์ที่ไม่แตกต่างกัน 3 เล่ม
มีหนังสือภาษาอังกฤษที่ไม่แตกต่างกัน 2 เล่ม
มีหนังสือภาษาไทยที่ไม่แตกต่างกัน 4 เล่ม
ดังนั้นจะมีจำนวนวิธีจังเรียงหนังสือทั้งหมดบนชั้นวาง \(\frac{9!}{3!2!4!}=1260\) วิธี
ตัวอย่างที่ 3 มีหลอดไฟสีขาว 4 หลอด สีแดง 5 หลอด และสีน้ำเงิน 6 หลอด ต้องการนำหลอดไฟทั้งหมดไปประดับตามรั้วในแนวเส้นตรงจะประดับได้กี่วิธีที่แตกต่างกันเมื่อหลอดไฟสีเดียวกันไม่ต่างกัน
วิธีทำ ข้อนี้มีสิ่งของทั้งหมดก็คือมีหลอดไฟทั้งหมด 4+5+6=15 หลอด
หลอดไฟสีขาว 4 หลอด
หลอดไฟสีแดง 5 หลอด
หลอดไฟสีน้ำเงิน 6 หลอด
ดังนั้นจะมีจำนวนวิธีในการประดับหลอดไฟที่แตกต่างกันทั้งหมด \(\frac{15!}{4!5!6!}=630,630\) วิธี
ตัวอย่างที่ 4 จำนวนวิธีจัดเรียงตัวอักษร "ENTRANCE" ซึ่งตัวอักษร E ไม่อยู่ติดกันเท่ากับเท่าใด
วิธีทำ การคิดข้อนี้เราจะคิดแบบตรงข้ามนะครับ บางทีคิดแบบตรงๆมันยาก เราก็ต้องทำในทางตรงกันข้าม ก็คือ
เอาจำนวนวิธีเรียงสับเปลี่ยนสิ่งของทั้งหมด ลบด้วย จำนวนวิธีจัดเรียงแบบให้ E ติดกัน ก็จะได้ จำนวนวิธีเรียงสับเปลี่ยนที่ E ไม่ติดกันจริงไหม
ขั้นตอนแรก หาจำนวนวิธีเรียงสับเปลี่ยนสิ่งของทั้งหมดก่อน
มีตัวอักษรทั้งหมด 8 ตัว
มี E ทั้งหมด 2 ตัว
มี N ทั้งหมด 2 ตัว
มี T ทั้งหมด 1 ตัว
มี R ทั้งหมด 1 ตัว
มี A ทั้งหมด 1 ตัว
มี C ทั้งหมด 1 ตัว
ดั้งนั้นจำนวนวิธีในการเรียงสับเปลี่ยนตัวอักษรนี้มีทั้งหมด \(\frac{8!}{2!2!1!1!1!1!}=10080\) วิธี
ขั้นตอนที่สอง หาจำนวนวิธีเรียงสับเปลี่ยนสิ่ิงของโดยให้ตัว E ติดกันครับ
ก็คือมัด E ที่มีสองตัวเป็นหนึ่งมัดเดียวกัน ฉะนั้น
เราจะมีตัวอัักษรทั้งหมด 7 ตัว
มี E ทั้งหมด 1 ตัว (มัดรวมกันแล้วเลยนับเป็น 1 ตัว)
มี N ทั้งหมด 2 ตัว
มี T ทั้งหมด 1 ตัว
มี R ทั้งหมด 1 ตัว
มี A ทั้งหมด 1 ตัว
มี C ทั้งหมด 1 ตัว
ดังนั้นจะได้จำนวนวิธีเรียงสับเปลี่ยนโดยตัว E ติดเท่ากับ \(\frac{7!}{1!2!1!1!1!1!}=2520\) วิธี
เพราะฉะนั้นคำตอบของข้อนี้
จำนวนวิธีเรียงสับเปลี่ยนโดยให้ E ไม่ติดกัน = จำนวนวิธีเรียงสับเปลี่ยนทั้งหมด - จำนวนวิธีเรียงสับเปลี่ยนโดยให้ E ติดกัน
ซึ่งก็คือ 10080-2520=7560 วิธี
ตัวอย่างที่ 5 ถ้านำเลขโดด 0,2,2,3,3,3,4 มาสร้างเป็นจำนวนที่มีค่ามากกว่าหนึ่งล้าน จะมีทั้งหมดกี่จำนวน
วิธีทำ ข้อนี้ไม่ยาก ข้อนี้สังเกตเขาให้เลขโดดเรามา 7 ตัว มาสร้างเป็นเลขที่มีค่ามากกว่าหนึ่งล้าน สังเกตว่าถ้า 0 อยู่ในหลักล้าน เลขที่เราสร้างจะมีค่าไม่ถึงล้าน เข้าใจไหม เช่น 0423,233 เลขนี้ไม่ค่าไม่ถึงล้าน ดังนั้นหลักการในการหาคำตอบข้อนี้คือ
นำเลขโดดทั้งหมดมาเรียงสับเปลี่ยนก่อน และในบรรดาทั้งหมดที่เราเรียงสับเปลี่ยนนั้นมันจะมีประเภทที่ 0 อยู่ในหลักล้าน เราค่อยหาว่าประเภทที่ 0 อยู่ในหลักล้านมีกี่ตัว แล้วค่อยเอาไปลบออกก็จะเป็นคำตอบ ไม่รู้ว่าจะอ่านเข้าใจหรือเปล่า ไม่พูดมากแล้วไปทำกันเลยดีกว่า
นำเลขโดดทั้งหมดที่โจทย์ให้มาเรียงสับเปลี่ยนก็จะได้ \(\frac{7!}{1!2!3!1!}=420 \) จำนวน
ใน 420 จำนวนนี้มันจะมีประเภทที่ว่า มีเลข 0 อยู่ในหลักล้านด้วยนะ ดังนั้นต่อไปต้องหาว่าประเภทที่มีเลข 0 ในหลักล้านมีกี่จำนวน วิธีการคือ เอา 2,2,3,3,3,4 มาเรียงสับเปลี่ยน เข้าใจไหม เลข 0 ไม่ต้องเอามาด้วยนะคิดออกนะ
จะได้ \(\frac{6!}{2!3!1!}=60\)
เพราะฉะนั้น จำนวนที่มีค่ามากกว่าหนึ่งล้านมีทั้งหมด 420-60=360 จำนวน
ตัวอย่างที่ 6 มีลูกบอล 6 ลูก เป็นสีแดง 1 ลูก สีขาว 1 ลูก สีเหลือง 1 ลูก และสีดำ 3 ลูก ทุกลูกมีขนาดเท่ากัน เลือกลูกบอล 4 ลูก มาจัดเรียงเป็นแถวตรงได้ทั้งหมดกี่วิธี
วิธีทำ ข้อนี้สิ่งที่ต้องวิเคราะห์คือ เลือกลูกบอล 4 ลูก มาจัดเรียง เราจึงต้องแบ่งกรณีในการคิดได้ดังนี้
กรณีที่ 1 เลือกลูกบอลสีดำ 3 ลูก และสีอื่นอีก 1 ลูกครบแล้ว 4 ลูก
*** เลือกลูกบอลสีดำมา 3 ลูกอีกลูกเลือกสีแดง ก็จะได้ลูกบอล 4 ลูกนำทั้งหมดนี้มาเรียงสับเปลี่ยน
มีลูกบอลทั้งหมด 4 ลูก ดังนั้น \(n!=4!\)
เป็นลูกบอลสีดำที่เหมือนกัน 3 ลูก
เป็นลูกบอลสีแดง 1 ลูก
จะได้จำนวนวิธีจัดเรียงคือ \(\frac{4!}{3!1!}= 4\) วิธี
***เลือกลูกบอลสีดำมา 3 ลูกอีกลูกเลือกสีขาว ก็จะได้ลูกบอล 4 ลูกนำทั้งหมดนี้มาเรียงสับเปลี่ยน
มีลูกบอลทั้งหมด 4 ลูก ดังนั้น \(n!=4!\)
เป็นลูกบอลสีดำที่เหมือนกัน 3 ลูก
เป็นลูกบอลสีขาว 1 ลูก
จะได้จำนวนวิธีจัดเรียงคือ \(\frac{4!}{3!1!}= 4\) วิธี
***เลือกลูกบอลสีดำมา 3 ลูกอีกลูกเลือกสีเหลือง ก็จะได้ลูกบอล 4 ลูกนำทั้งหมดนี้มาเรียงสับเปลี่ยน
มีลูกบอลทั้งหมด 4 ลูก ดังนั้น \(n!=4!\)
เป็นลูกบอลสีดำที่เหมือนกัน 3 ลูก
เป็นลูกบอลสีเหลือง 1 ลูก
จะได้จำนวนวิธีจัดเรียงคือ \(\frac{4!}{3!1!}= 4\) วิธี
ดังนั้นในกรณีที่ จัดเรียงได้ทั้งหมด 4+4+4=(3)4=12 วิธี
หรือเราจะคิดแบบง่ายคือคิดแค่ *** เพียงแค่ครั้งเดียวแล้วก็คูณ 3 เอาเพราะดอกจันทน์ที่เหลือได้ค่าเท่ากัน งงไหม
กรณีที่ 2 เลือกสีดำ 2 ลูกและเลือกสีอื่นอีก 2 ลูก กรณีนี้ผมจับคูณ 3 เลยนะไม่ทำเหมือนกรณีที่ 1 มันยาว
มีลูกบอลทั้งหมด 4 ลูก
เป็นสีดำ 2 ลูก
เป็นสีอื่นสองสี สีละ 1 ลูก
ดังนั้นจำนวนวิธีในการจัดเรียงคือ \(\frac{4!}{2!1!1!}\times 3=36\) วิธี
กรณีที่ 3 เลือกสีดำ 1 ลูกและเลือกสีอื่นอีก 3 ลูก
มีลูกบอลทั้งหมด 4 ลูก
เป็นสีดำ 1 ลูก
และอื่นสีละ 1 ลูก
กรณีนี้จะเห็นว่าคือการนำสิ่งของที่แตกต่างกัน 4 สิ่งมาเรียงสับเปลี่ยนกัน จะได้จำนวนวิธีคือ \(P_{4,4}=4!=24\) วิธี
เอาทุกกรณีมารวมกันก็จะเป็นคำตอบครับ \(12+36+24=72\) วิธี
ตัวอย่างที่ 7 นำแจกันเดียวกัน 12 ใบ ซึ่งเป็นแจกันเคลือบเงา 4 ใบ แจกันลายดอก 4 ใบ และแจกันดินเผา 4 ใบ มาเรียงเป็นแถวได้กี่วิธี ถ้า
1) ไม่มีเงื่อนไขเพิ่มเติม
วิธีทำ ข้อนี้วิธีการทำก็คือการเอาสิ่งของที่ไม่แตกต่างกันทั้งหมดมาเรียงสับเปลี่ยนนั้นเองก็จะได้จำนวนวิธีคือ
\(\frac{12!}{4!4!4!}\) วิธี คำนวณเป็นตัวเลขเองนะครับ
2) มีแจกันดินเผาอยู่ริมสุดทั้งสองข้าง
วิธีทำ เลือกแจกันดินเผา 2 ใบมาวางด้านริมสุดทั้งสองข้าง แล้วหาจำนวนวิธีเรียงสับเปลี่ยนสิ่งของที่เหลือที่อยู่ระหว่างแจกันดินเผา 2 ใบที่วางริมสองข้างจะได้จำนวนวิธีคือ
\(\frac{10!}{4!4!2!}\) วิธี
3) มีแจกันดินเผาอยู่ติดกันเสมอ
วิธีทำ มัดแจกันดินเผา 4 ใบรวมเป็น 1 มัดนับที่เรามัดไว้เป็น 1 มัดนะครับดังนั้นเราจะมีแจกันให้เราเรียงสับเปลี่ยนจำนวน 9 ใบ เราจะได้จำนวนวิธีคือ
\(\frac{9!}{4!4!1!}\) วิธี
ตัวอย่างที่ 8 กำหนดแผงผังเมืองหนึ่งดังรูป
รอยเส้นในแผนผังแทนถนนน ต้องการเดินทางออกจากจุด O ไปยังจุด P โดยมีเงื่อนไขว่าจะต้องเดินทางไปทางทิศเหนือหรือทิศตะวันออกเท่ากนั้น จงหาจำนวนเส้นทางทั้งหมดจากจุด O ไปยังจุด P โดยที่
1) ไม่มีเงื่อนไขเพิ่มเติม
2) เส้นทางต้องผ่านจุด A
3) เส้นทางต้องไม่ผ่านจุด A
วิธีทำ แนวทางการทำโจทย์ข้อนี้ก็คือ
สมมติว่า
เดินทางไปทางเหนือ 1 ช่องแทนด้วย ตัว N หนึ่งตัว
เดินทางไปตะวันออก 1 ช่องแทนด้วย ตัว E หนึ่งตัว
ดังนั้นเส้นทางที่จากจุด O ไปยังจุด P เราไปจะเดินแบบนี้ก็ได้ คือ เดินขึ้นเหนือไป 8 ช่องแล้วเลี้ยวขวาไปทางทิศตะวันออกอีก 7 ช่องเราก็จะได้เส้นทางในการเดินดังนี้
NNNNNNNNEEEEEEE
หรือ เดินทางไปทางทิศตะวันออก 7 ช่องแล้วค่อยเดินขึ้นไปทางเหนืออีก 8 ช่องก็จะถึงจุด P เราก็จะได้เส้นทางในการเดินดังนี้
EEEEEEENNNNNNNN
หรือเราจะเดินแบบนี้ก็ได้
EENNNENENEEENNN
สรุปก็คือต้องเดินผ่านช่อง E จำนวน 7 ครั้งและผ่านช่อง N จำนวน 8 ครั้ง จึงจะถึงจุด P ครับ
ดังนั้นจำนวนเส้นทางทั้งหมดถ้าพิจารณาดีๆ ก็คือ การนำสิ่งของเหล่านี้คือ EEEEEEENNNNNNNN มาเรียงสับเปลี่ยนเชิงเส้นนั้นเองครับ เริ่มหาคำตอบกันแต่ละข้อเลยครับ
1) ไม่มีเงื่อนไขเพิ่มเติม
จำนวนเส้นทางจากจุด P ไปยังจุด O ก็คือเป็นการหาจำนวนวิธีในการเรียงสับเปลี่ยนเชิงเส้นของ EEEEEEENNNNNNNN
ดังนั้นจำนวนเส้นทางจากจุด O ไปยัง P เท่ากับ \(\frac{15!}{7!8!}=6435\) เส้นทาง
2) เส้นทางต้องผ่านจุด A
จำนวนเส้นทางจากจุด O ไปยังจุด P โดยผ่านจุด A เสมอ คือ ดูรูปประกอบนะครับจะเห็นว่าการที่เราจะเดินทางจากจุด Pไปยังจุด A นั้นเราต้องเดินไปทางตะวันออก 4 ช่องนั่นคือต้องมี EEEE และเดินทางไปทางทิศเหนือ 4 ช่องนั่นคือต้องมี NNNN ดังนั้นจำนวนเส้นทางจากจุด O ไปยังจุด A เท่ากับ
\[\frac{8!}{4!4!}\]
ต่อหาจำนวนเส้นทาง จากจุด A ยังจุด P
จากรูปถ้าเราจะเดินทางจาก A ไปยัง P จะต้องเดินไปทางตะวันออก 3 ช่องนั่นคือต้องมี EEE และต้องไปทางเหนือ 4 ช่องนั่นคือต้องมี NNNN ดังนั้นจำนวนเส้นทางจากจุด A ไปยังจุด P เท่ากับ
\[\frac{7!}{3!4!}\]
สรุป จะเห็นว่าการที่เราจะหาจำนวนเส้นทางในการเดินทางไปยังจุด P โดยต้องเดินผ่านจุด A นั้นเป็นการทำงาน 2 ขั้นตอนคือ
ขั้นตอนที่ 1 หาจำนวนเส้นทางจาก O ไปยังจุด A ก่อนซึ่งมีทั้งหมด
\(\frac{8!}{4!4!}\) เส้นทาง
ขั้นตอนที่ 2 หาจำนวนเส้นทางจาก A ไปยังจุด P ซึ่งมีทั้งหมด
\(\frac{7!}{3!4!}\) เส้นทาง
ดังนั้น จำนวนเส้นทางจากจุด O ไปยังจุด P โดยผ่านจุด A เท่ากับ
\[\left(\frac{8!}{4!4!}\right)\left(\frac{7!}{3!4!}\right)=2450 \] เส้นทาง
3) เส้นทางต้องไม่ผ่านจุด A
ข้อนี้เราจะไม่หาแบบตรงนะครับ เราจะหาโดย
เอาจำนวนเส้นทางจากจุด O ไปยังจุด P ลบออกด้วย จำนวนเส้นทางจากจุด O ไปยังจุด P โดยผ่านจุด A ก็จะได้จำนวนเส้นทางจากจุด O ไปยังจุด P โดยที่ไม่ผ่านจุด A ครับ ก็คือเอาคำตอบจากข้อย่อยที่ 1) ลบออกด้วยคำตอบของข้อย่อยที่ 2) นั่นคือ \(6435-2450=3985\) เส้นทาง
ตัวอย่างที่ 8 คำว่า MACBAKA ถ้านำตัวอักษรมาเรียงใหม่โดยไม่สนใจความหมายจะเรียงได้ทั้งหมดกี่วิธี ถ้า B ห้ามอยู่ติดกับ A
วิธีทำ ข้อนี้เราจะให้วิธีการหาคำตอบโดยการทำตรงแบบตรงกันข้ามนะครับ ก็คือ
เอาจำนวนวิธีในการเรียงสับเปลี่ยนคำว่า MACBAKA ที่ได้ทั้งหมด ลบออกด้วย จำนวนวิธีในการเรียงสับเปลี่ยนคำว่า MACBAKA โดยที่ให้ B ติดกับ A
ขั้นตอนที่ 1 หาจำนวนวิธีในการเรียงสับเปลี่ยนคำว่า MACBAKA ซึ่งจะได้เท่ากับ
\begin{array}{lcl}\frac{7!}{3!}&=&840\end{array} วิธี
ขั้นตอนที่ 2 หาจำนวนวิธีในการเรียงสับเปลี่ยนคำว่า MACBAKA โดยที่ให้ B ติดกับ A ซึ่งถ้าลองคิดตามเราจะได้หน้าตาในการเรียงประมาณนี้
BAMCKAA
BAMCAKA
BAAAMCK
MBAKCAA
ABAAKMC
AABAMKC
ซึ่งถ้าคำนวณออกมาจะได้จำนวนทั้งหมด (มัด BA เป็นก้อนเดียวกัน)
\begin{array}{lcl}\frac{6!}{2!}&=&360\end{array}
แต่เราสามารถสลับที่ BA เป็น AB ได้ ซึ่งก็จะได้จำนวนวิธีในการเรียงสับเปลี่ยนมาอีก 360 วิธี
นั่นก็คือ จำนวนวิธีเรียงสับเปลี่ยน คำว่า MACBAKA โดยที่ B ติดกับ A จะมีจำนวนเท่ากับ 360+360=720 วิธี
ดังนั้น จำนวนวิธีในการเรียงสับเปลียนคำว่า MACBAKA โดยที่ B ห้ามติดกับ A จึงเท่ากับ
\(840-720=120\) วิธี