418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงการจัด/เฉลยข้อ 9

ข้อย่อย 1

จากคำว่า MISSISSIPPI มีความยาว 11 ตัว และจะได้ว่ามีตัวอักษร M อยู่ 1 ตัว,ตัวอักษร I อยู่ 4 ตัว, ตัวอักษร S อยู่ 4 ตัว, ตัวอักษร P อยู่ 2 ตัว

จาก Bookkepper Rule จะได้ว่าจำนวนของสตริงทั้งหมดที่ได้จากการเรียงตัวอักษรในคำว่า MISSISSIPI ใหม่ $={\frac {11!}{1!4!4!2!}}=34650$ แบบ

ข้อย่อย 2

จากคำว่า AARDVARK ถ้าต้องการให้ตัวอักษร A ทั้งสามตัวติดกันเสมอ จะมองเหมือนกับ AAA เป็นตัวอักษร 1 ตัว ดังนั้นตัวอักษรทั้งหมดที่จะนำมาเรียงจะกลายเป็น 6 ตัวอักษร โดยที่มีตัวอักษร A 1 ตัว (จริง ๆ คือ AAA) ตัวอักษร R 2 ตัว ตัวอักษร D 1 ตัว ตัวอักษร V 1 ตัว และตัวอักษร K 1 ตัว ดังนั้นจาก Bookkeepper Rule จะได้ว่าจำนวนสตริงทั้งหมดที่ได้จากการเรียงตัวอักษรในคำว่า AARDVARK ใหม่โดยที่ตัวอักษร A ทั้งสามตัวจะต้องอยู่ติดกันคือ ${\frac {6!}{1!2!1!1!1!}}=360$ แบบ

ข้อย่อย 3

ให้ $S_{i}$ คือสตริงที่มีความยาว $i;i=5,6,7$ จากโจทย์ต้องการรู้ $|S_{5}\cup S_{6}\cup S_{7}|$ ซึ่งจากกฏการบวกจะได้ว่า $|S_{5}\cup S_{6}\cup S_{7}|=|S_{5}|+|S_{6}|+|S_{7}|$

เมื่อพิจารณา $|S_{5}|$ จะสามารถแยกออกเป็นกรณีต่าง ๆ ดังนี้

กรณีที่ 1 สตริงความยาว 5 ที่ประกอบไปด้วย S 3 ตัว และ E 2 ตัว จาก Bookkepper Rule จะได้ทั้งหมด ${\frac {5!}{3!2!}}=10$ แบบ

กรณีที่ 2 สตริงความยาว 5 ที่ประกอบไปด้วย S 3 ตัว E 1 ตัว และ R 1 ตัว จาก Bookkepper Rule จะได้ทั้งหมด ${\frac {5!}{3!1!1!}}=20$ แบบ

กรณีที่ 3 สตริงความยาว 5 ที่ประกอบไปด้วย S 2 ตัว และ E 3 ตัว จาก Bookkepper Rule จะได้ทั้งหมด ${\frac {5!}{2!3!}}=10$ แบบ

กรณีที่ 4 สตริงความยาว 5 ที่ประกอบไปด้วย S 2 ตัว E 2 ตัวและ R 1 ตัว จาก Bookkepper Rule จะได้ทั้งหมด ${\frac {5!}{2!2!1!}}=30$ แบบ

กรณีที่ 5 สตริงความยาว 5 ที่ประกอบไปด้วย S 1 ตัว E 3 ตัวและ R 1 ตัว จาก Bookkepper Rule จะได้ทั้งหมด ${\frac {5!}{1!3!1!}}=20$ แบบ

ดังนั้น $|S_{5}|=10+20+10+30+20=90$ แบบ