43.4 การเรียงของซ้ำและการเรียงเป็นวงกลม

เมื่อนำตัวอักษรเหมือนกันมาสลับ จะมองไม่เห็นความต่าง และเมื่อคนทั้งโต๊ะกลมหมุนไปพร้อมกันอาจถือเป็นการจัดเดิม ทั้งสองอย่างต้องกำหนดก่อนว่าผลลัพธ์ใดนับเป็นแบบเดียวกัน

ลองเรียงตัวอักษรของคำว่า BANANA ใหม่ให้ได้คำที่ต่างกัน ถ้าตัวอักษรทั้งหกตัวต่างกันจะได้ $6!=720$ แบบ แต่ในคำนี้มี A สามตัวและ N สองตัว การสลับ A ตัวที่หนึ่งกับ A ตัวที่สองให้คำเดิมทุกตัวอักษร จำนวนคำที่ต่างกันจริงจึงน้อยกว่า $720$ มาก เช่นเดียวกับเพื่อนห้าคนที่นั่งรอบโต๊ะกลมแล้วขยับไปทางขวาพร้อมกันหนึ่งที่ ทุกคนยังมีเพื่อนข้างซ้ายและข้างขวาคนเดิม หน้านี้ใช้แนวคิดเดียวจากหน้า 43.3 กับทั้งสองเรื่อง คือนับแบบที่ทุกอย่างต่างกันก่อน แล้วหารด้วยจำนวนครั้งที่แต่ละแบบถูกนับซ้ำ

การเรียงที่ถูกนับซ้ำ

ของ $n$ ชิ้นที่มีชนิดซ้ำจำนวน $n_1,n_2,\ldots$ เรียงแนวตรงได้ $n!/(n_1!n_2!\cdots)$ วิธี คนต่างกัน $n$ คนรอบโต๊ะกลมที่ถือการหมุนเหมือนกันแต่ภาพสะท้อนต่างกัน มี $(n-1)!$ วิธี โดยตรึงคนหนึ่งไว้ สองสูตรนี้มีที่มาที่ต้องเข้าใจ เพราะโจทย์ที่มีเงื่อนไขเพิ่มมักต้องกลับไปใช้เหตุผลมากกว่าสูตร

เรียงของที่มีชิ้นเหมือนกัน

ติดป้ายให้ของเหมือนกันเป็นของต่างกันก่อน เช่นเขียน BANANA เป็น B A₁ N₁ A₂ N₂ A₃ ตอนนี้ทั้งหกตัวต่างกัน เรียงได้ $6!$ แบบ จากนั้นถามว่าคำที่ไม่มีป้ายคำหนึ่ง เช่น ABANAN ถูกนับในการเรียงที่มีป้ายกี่ครั้ง ตำแหน่งของ A ทั้งสามช่องถูกกำหนดแล้ว แต่จะวาง A₁ A₂ A₃ ลงสามช่องนั้นได้ $3!$ แบบ และวาง N₁ N₂ ลงสองช่องของ N ได้ $2!$ แบบ แต่ละคำจึงถูกนับซ้ำ $3!\times2!=12$ ครั้งเท่ากันทุกคำ

การเรียงสับเปลี่ยนของที่ไม่แตกต่างกันทั้งหมด

ของ $n$ ชิ้น แบ่งเป็น $k$ ชนิด ชนิดที่หนึ่งมี $n_1$ ชิ้นเหมือนกัน ชนิดที่สองมี $n_2$ ชิ้น และต่อไปจนถึง $n_k$ ชิ้น โดย $n_1+n_2+\cdots+n_k=n$ เรียงเป็นแถวได้ $\dfrac{n!}{n_1!\,n_2!\cdots n_k!}$ วิธี

ชนิดที่มีชิ้นเดียวหารด้วย $1!=1$ จึงไม่ต้องเขียน และถ้าทุกชิ้นต่างกันหมด สูตรนี้ก็กลับเป็น $n!$ ตามหน้า 43.2

ตัวอย่าง 1

เรียงอักษร A A B B C ได้กี่แบบ และเรียงตัวอักษรของคำว่า BANANA ได้กี่แบบ

A A B B C มี $5$ ตัว A ซ้ำ $2$ ตัว B ซ้ำ $2$ ตัว อักษรซ้ำใช้ $5!/(2!2!)=120/4=30$ แบบ
BANANA มี $6$ ตัว A ซ้ำ $3$ ตัว N ซ้ำ $2$ ตัว B มีตัวเดียว
ได้ $\dfrac{6!}{3!\,2!}=\dfrac{720}{12}=60$ แบบ น้อยกว่า $720$ ถึง $12$ เท่าตามที่คิดไว้ตอนต้นหน้า

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

ตัวอย่าง 2

บ้านของปลาอยู่ที่มุมหนึ่งของซอยที่ตัดกันเป็นตาราง โรงเรียนอยู่ห่างไปทางตะวันออก $4$ ช่วงถนน และทางเหนือ $3$ ช่วงถนน ถ้าปลาเดินไปทางตะวันออกหรือทางเหนือเท่านั้น จะเดินไปโรงเรียนได้กี่เส้นทาง

ทุกเส้นทางที่สั้นที่สุดต้องเดินไปทางตะวันออก $4$ ครั้งและทางเหนือ $3$ ครั้ง ไม่มากไม่น้อยกว่านี้ รวม $7$ ครั้ง
เขียนเส้นทางเป็นคำยาว $7$ ตัว ใช้ ต แทนเดินไปตะวันออก และ น แทนเดินไปเหนือ เช่น ตตนตนนต เส้นทางต่างกันก็ได้คำต่างกัน และคำทุกคำที่มี ต สี่ตัว น สามตัว ก็เป็นเส้นทางที่ใช้ได้
จำนวนเส้นทางจึงเท่ากับจำนวนวิธีเรียง ต $4$ ตัว กับ น $3$ ตัว คือ $\dfrac{7!}{4!\,3!}=\dfrac{5040}{24\times6}=35$ เส้นทาง

ถ้ามองอีกแบบ การเรียง ต สี่ตัวกับ น สามตัวก็คือการเลือก $3$ ตำแหน่งจาก $7$ ตำแหน่งให้เป็น น ได้ $\binom{7}{3}=35$ เท่ากัน สูตรของซ้ำที่มีสองชนิดจึงเป็นการจัดหมู่ในอีกรูปหนึ่ง

ตัวอย่าง 3

เรียงอักษร A A B C โดย A ทั้งสองต้องติดกัน มีกี่แบบ

รวม A A เป็นหนึ่งก้อน ได้ก้อน AA, B, C รวมสามสิ่ง
เรียงสามสิ่งได้ $3!=6$ แบบ
ภายในก้อน A เหมือนกันจึงไม่คูณ $2!$ ซ้ำ

ตรวจวิธีคิด

ถ้าภายในก้อนเป็นคนต่างกันต้องคูณการเรียงภายใน แต่ของเหมือนกันสลับแล้วไม่เกิดแบบใหม่ วิธีบล็อกกับสูตรของซ้ำต้องใช้อย่างสอดคล้องกับสิ่งที่มองเห็นในคำตอบ

ลองคิดก่อน

เรียงตัวอักษรของ BANANA โดยให้ขึ้นต้นด้วย B เพื่อนคิดว่าทั้งหมดมี $60$ แบบ และแต่ละตัวอักษรมีโอกาสขึ้นต้นเท่ากันทั้งสามชนิด จึงตอบ $60\div3=20$ แบบ ถูกหรือไม่

ดูคำตอบ

ไม่ถูก ตัวอักษรสามชนิดไม่ได้มีจำนวนเท่ากัน A มีสามตัวจึงขึ้นต้นบ่อยกว่า B ที่มีตัวเดียว วิธีที่ถูกคือวาง B ไว้ช่องแรก แล้วเรียงที่เหลือ A A A N N ในห้าช่อง ได้ $\dfrac{5!}{3!\,2!}=10$ แบบ ตรวจได้ด้วยการนับคำที่ขึ้นต้นด้วย A ซึ่งเหลือ B A A N N ได้ $\dfrac{5!}{2!\,2!}=30$ แบบ และขึ้นต้นด้วย N ซึ่งเหลือ B A A A N ได้ $\dfrac{5!}{3!}=20$ แบบ รวม $10+30+20=60$ พอดี การหารเท่าๆ กันใช้ได้เฉพาะเมื่อแต่ละกรณีมีขนาดเท่ากันจริง

นั่งรอบโต๊ะกลม

โต๊ะกลมไม่มีหัวโต๊ะ ที่นั่งแต่ละที่ไม่มีหมายเลข สิ่งที่บอกว่าการนั่งสองแบบต่างกันคือใครนั่งข้างใคร ถ้าทุกคนขยับไปทางเดียวกันพร้อมกันหนึ่งที่ ทุกคนยังมีเพื่อนข้างซ้ายและข้างขวาคนเดิม จึงถือว่าเป็นการนั่งแบบเดิม

ทั้งสามโต๊ะเป็นการนั่งแบบเดียวกัน อ่านตามเข็มนาฬิกาได้ A B C ทุกโต๊ะ แต่ถ้าเขียนเป็นแถวตรงโดยเริ่มจากที่นั่งด้านบนจะได้ ABC CAB BCA ซึ่งนับเป็นสามแบบ

คนสามคนเรียงแถวตรงได้ $3!=6$ แบบ แต่รอบโต๊ะกลม ทุกการนั่งหนึ่งแบบให้แถวตรง $3$ แบบตามที่นั่งที่เลือกเป็นจุดเริ่มอ่าน จึงเหลือ $6\div3=2$ แบบ คือ ABC กับ ACB ตามเข็มนาฬิกา ในกรณีทั่วไปคน $n$ คนเรียงแถวตรงได้ $n!$ แบบ และการนั่งรอบโต๊ะหนึ่งแบบถูกนับซ้ำ $n$ ครั้ง จึงได้ $\dfrac{n!}{n}=(n-1)!$ แบบ

อีกวิธีที่ให้คำตอบเดียวกันคือตรึงคนหนึ่งไว้ ให้คนแรกนั่งลงก่อน ที่นั่งของเขาไม่ต้องเลือก เพราะทุกที่นั่งเหมือนกันหมด แต่พอเขานั่งแล้ว ที่นั่งที่เหลือมีความหมายทันที เช่นที่ถัดไปทางขวาของเขา คนที่เหลือ $n-1$ คนจึงเรียงเหมือนแถวตรงได้ $(n-1)!$ แบบ วิธีตรึงคนนี้สะดวกมากเมื่อโจทย์มีเงื่อนไข

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

คนต่างกัน $n$ คนนั่งรอบโต๊ะกลม โดยถือว่าการหมุนทั้งวงให้การนั่งแบบเดิม จัดได้ $(n-1)!$ วิธี

ตัวอย่าง 4

ให้คนต่างกันห้าคนนั่งโต๊ะกลมได้กี่แบบ และถ้าเป็นนักเรียนชาย $4$ คน หญิง $4$ คน นั่งรอบโต๊ะกลมสลับชายหญิง ได้กี่แบบ

โต๊ะกลมตรึงคนหนึ่งไว้ จัดที่เหลือได้ $4!=24$ แบบ
ข้อสอง ให้ชายนั่งรอบโต๊ะก่อน เป็นการนั่งเชิงวงกลมของ $4$ คน ได้ $(4-1)!=3!=6$ แบบ
เมื่อชายนั่งแล้ว ช่องระหว่างชายมี $4$ ช่อง และแต่ละช่องมีตำแหน่งชัดเจน เช่นช่องทางขวาของชายคนแรก การหมุนถูกจัดการไปแล้วในขั้นที่สอง หญิง $4$ คนจึงเรียงลงสี่ช่องได้ $4!=24$ แบบ ไม่หารด้วยสี่อีก
รวม $3!\times4!=6\times24=144$ แบบ

ตัวอย่าง 5

เพื่อน $6$ คนนั่งรอบโต๊ะกลมในร้านหมูกระทะ โดยแบมกับบีมต้องนั่งติดกัน ได้กี่แบบ

มัดแบมกับบีมเป็นก้อนเดียวเหมือนหน้า 43.2 ตอนนี้มีของที่ต้องจัดรอบโต๊ะ $5$ สิ่ง คือก้อนหนึ่งก้อนกับเพื่อนอีก $4$ คน
จัด $5$ สิ่งรอบโต๊ะกลมได้ $(5-1)!=24$ แบบ
ในก้อน แบมอาจนั่งทางซ้ายหรือทางขวาของบีม ได้ $2!=2$ แบบ
รวม $24\times2=48$ แบบ

ลองคิดก่อน

นั่งโต๊ะกลมแล้วหารด้วยสองเสมอเพราะมีภาพสะท้อน ถูกหรือไม่

ดูคำตอบ

ไม่ถูก ในโจทย์โต๊ะกลมปกติซ้ายขวาของแต่ละคนมีความหมาย จึงถือภาพสะท้อนต่างกัน การหารสองต้องมีเงื่อนไขเพิ่มเติมว่าอนุญาตให้พลิกแล้วเหมือนกันจริง เช่นร้อยลูกปัดสีต่างกัน $5$ เม็ดเป็นสร้อยข้อมือ ซึ่งพลิกด้านได้ จึงได้ $\dfrac{4!}{2}=12$ แบบ ส่วนคนนั่งโต๊ะพลิกตัวกลับหัวไม่ได้ จึงใช้ $(n-1)!$ ตามเดิม

ตรวจด้วยกรณีเล็กก่อนใช้สูตรใหญ่

สูตรของซ้ำเกิดจากการเริ่มสมมติว่าของทุกชิ้นติดป้ายต่างกัน แล้วหารจำนวนการสลับป้ายที่มองไม่เห็น ถ้าบางชิ้นมีเงื่อนไขตำแหน่งพิเศษ การหารแฟกทอเรียลแบบเดียวกันอาจใช้ไม่ได้ ต้องวิเคราะห์ว่าแต่ละแบบถูกนับซ้ำเท่ากันจริงหรือไม่ เช่นเดียวกับโต๊ะกลมซึ่งต้องกำหนดว่ามีที่นั่งระบุหมายเลขหรือไม่มี ถ้าที่นั่งมีหมายเลขกำกับ เช่นโต๊ะจีนที่จัดป้ายชื่อไว้ทุกที่ การหมุนทั้งวงทำให้ทุกคนย้ายไปนั่งเก้าอี้หมายเลขอื่น ถือเป็นการจัดใหม่ จึงนับเหมือนแถวตรงคือ $n!$

วิธีตรวจที่ใช้ได้ทุกครั้งคือลดโจทย์ลงเหลือสามหรือสี่ชิ้น แล้วเขียนทุกแบบออกมานับเอง ถ้าคำตอบจากการเขียนตรงกับสูตร ก็มั่นใจได้ว่าเลือกสูตรถูก

สรุป

ของซ้ำหารด้วยแฟกทอเรียลของแต่ละชนิด $\dfrac{n!}{n_1!\,n_2!\cdots n_k!}$
เส้นทางบนตารางถนนเขียนเป็นคำที่มีตัวอักษรซ้ำแล้วใช้สูตรเดียวกันได้
โต๊ะกลมต้องระบุว่าถือการหมุนและสะท้อนอย่างไร คนต่างกัน $n$ คนนั่งได้ $(n-1)!$ แบบ
เมื่อมีเงื่อนไข ให้ตรึงคนหนึ่งหรือกลุ่มหนึ่งไว้ก่อน แล้วที่นั่งที่เหลือจะมีตำแหน่งชัดเจน
ทุกสูตรในหน้านี้มาจากการนับแบบติดป้ายแล้วหารการนับซ้ำ

ในตัวอย่างเส้นทางเดิน เราเห็นว่าการเรียงของสองชนิดเท่ากับ $\binom{n}{r}$ ตัวเลขชุดนี้ยังโผล่ในการกระจาย $(a+b)^n$ ด้วย หน้า 43.5 จะใช้เหตุผลเดียวกันพิสูจน์ทฤษฎีบททวินาม