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$ แบบ

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

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

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

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

ดังนั้น $|S_{6}|=20+60+60=140$ แบบ

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

ดังนั้น $|S_{7}|=140$ แบบ

จากข้างต้นจึงสามารถสรุปได้ว่า $|S_{5}\cup S_{6}\cup S_{7}|=|S_{5}|+|S_{6}|+|S_{7}|=90+140+140=370$ แบบ

ข้อย่อย 4

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

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

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

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

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

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

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

กรณีที่ 6 สตริงความยาว 7 ที่ประกอบไปด้วย E 4 ตัว V 1 ตัว G 1 ตัว และ N 1 ตัว จาก Bookkepper Rule จะได้ทั้งหมด ${\frac {7!}{4!1!1!1!}}=210$ แบบ

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

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

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

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

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

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

ดังนั้น $|S_{7}|=4(210)+3(420)+840+1260=4200$ แบบ

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

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

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

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

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

ดังนั้น $|S_{8}|=840+840+1680+3360=6720$ แบบ

เมื่อพิจารณา $|S_{9}|$ จะมีกรณีเดียวคือ สตริงความยาว 9 ที่ประกอบไปด้วย E 4 ตัว V 1 ตัว R 2 ตัว G 1 ตัว และ 1 ตัว จาก Bookkepper Rule จะได้ทั้งหมด ${\frac {9!}{4!1!2!1!1!}}=7560$ แบบ

ดังนั้น $|S_{9}|=7560$ แบบ

ดังนั้น $|S_{7}\cup S_{8}\cup S_{9}|=|S_{7}|+|S_{8}|+|S_{9}|=18480$ แบบ