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

ข้อย่อย 1

พิจารณาเซต 3 เซตที่สอดคล้องกับตัวอักษรและตัวเลขที่สามารถปรากฏได้ในตำแหน่งต่าง ๆ ของสตริงความยาว 6 ดังนี้ ให้เซต X คือเซตของสระภาษาอังกฤษและY คือเซตของพยัญชนะภาษาอังกฤษ จะได้ว่า $|X|=5,|Y|=21$ ให้ $A_{i}$ เมื่อ $1\leq i\leq 6$ คือสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษและตัวเลขที่มีสระอยู่ตำแหน่งที่ i ดังนั้นจำนวนของสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษที่มีสระ 1 ตัว = $|A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\cup A_{5}\cup A_{6}|=|A_{1}|+|A_{2}|+|A_{3}|+|A_{4}|+|A_{5}|+|A_{6}|$

พิจารณา $A_{1}=X\times Y^{5}=|X|.|Y|^{5}=5.(21)^{5}$

และ $A_{2},A_{3},A_{4},A_{5},A_{6}$ ก็คิดได้เหมือนกันกับกรณีข้างต้น

ดังนั้นจำนวนของสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษและตัวเลขที่มีสระ 1 ตัว $=(5.(21)^{5})+(5.(21)^{5})+(5.(21)^{5})+(5.(21)^{5})+(5.(21)^{5})+(5.(21)^{5})=6.(5.(21)^{5})$

ข้อย่อย 2

พิจารณาสตริงความยาว 6 ที่มีสระสองตัว คือการเลือกสระ 2 ตัว จากสระ 5 ตัว และเราต้องเลือกด้วยว่าจะให้สระสองตัวนี้อยู่ตำแหน่งไหนในสตริงความยาว 6 ตัว นอกจากนี้สระ 2 ตัวที่เลือกมายังสามารถสลับตำแหน่งกันได้อีก ดังนั้น สตริงความยาว 6 ที่มีสระสองตัวมีทั้งหมด ${6 \choose 2}{5 \choose 2}(21^{4})(2!)$ แบบ

ข้อย่อย 3

ให้ A เป็นเซตของสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษทั้งหมด จะได้ว่า $|A|=26^{6}(6!)$ แบบ (เกิดจากการที่แต่ละตำแหน่งเป็นตัวอักษรได้ 26 ตัว และมีทั้งหมด 6 ตำแหน่ง นอกจากนี้ตัวอักษร 6 ตัวที่เลือกมายังสามารถมาเรียงสับเปลี่ยนกันได้เป็นสตริงอีก 6! แบบ)

ให้ B เป็นเซตของสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษทั้งหมดที่มีสระอย่างน้อย 1 ตัว

จะได้ว่า A-B คือเป็นเซตของสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษทั้งหมดที่ไม่มีสระเลย

ซึ่ง $|A-B|=21^{6}(6!)$

ดังนั้น $|B|=26^{6}(6!)-21^{6}(6!)$ แบบ

ข้อย่อย 4

ให้ A เป็นเซตของสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษทั้งหมด จากข้อย่อย 3 ข้างต้นจะได้ $|A|=26^{6}(6!)$ แบบ

ให้ B เป็นเซตของสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษที่มีสระอย่างน้อย 2 ตัว

จะได้ว่า A-B คือเป็นเซตของสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษที่มีสระ 1 ตัว และสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษที่ไม่มีสระเลย

ซึ่งจากข้อย่อย 1 และข้อย่อย 3 ข้างต้นจะได้ว่า $|A-B|={6 \choose 1}5^{1}(21)^{5}+21^{6}(6!)$

ดังนั้น $|B|=26^{6}(6!)-{6 \choose 1}5^{1}(21)^{5}-21^{6}(6!)$ แบบ

ข้อย่อย 5

จากโจทย์การที่สตริงความยาว 6 ไม่มีสระใด ๆ ปรากฏมากกว่า 1 ครั้ง แสดงว่าสระทุกตัวปรากฏได้อย่างมากแค่ 1 ครั้ง แสดงว่าสตริงความยาว 6 นี้มีสระได้มากสุด 5 ตัว

ให้ $A_{k}$ เป็นเซตของสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษที่มีสระ k ตัว

ดังนั้นจำนวนสตริงความยาว 6 ที่ไม่มีสระใด ๆ ปรากฏมากกว่า 1 ครั้ง คือ $|A_{1}|+|A_{2}|+|A_{3}|+|A_{4}|+|A_{5}|$

หา $|A_{1}|$ จากข้อย่อย 1 จะได้ว่า $|A_{1}|={5 \choose 1}{6 \choose 1}21^{5}$

หา $|A_{2}|$ จากข้อย่อย 2 จะได้ว่า $|A_{2}|={5 \choose 2}{6 \choose 2}21^{4}(2!)$

ด้วยการคิดวิธีเดียวกันจะได้ว่า

$|A_{3}|={5 \choose 3}{6 \choose 3}21^{3}(3!)$

$|A_{4}|={5 \choose 4}{6 \choose 4}21^{2}(4!)$

$|A_{5}|={5 \choose 5}{6 \choose 5}21(5!)$

ดังนั้นจำนวนสตริงความยาว 6 ที่ไม่มีสระใด ๆ ปรากฏมากกว่า 1 ครั้ง คือ $(5)(6)21^{5}+{5 \choose 2}{6 \choose 2}21^{4}(2!)+{5 \choose 3}{6 \choose 3}21^{3}(3!)+{5 \choose 4}{6 \choose 4}21^{2}(4!)+{6 \choose 5}21(5!)$ แบบ

ข้อย่อย 6

พิจารณาการสร้างสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรที่ไม่มีตัวอักษรใด ๆ ปรากฏมากกว่า 1 ครั้ง จะได้ว่า ตำแหน่งแรกเลือกตัวอักษรได้ 26 ตัว ตำแหน่งที่สองเลือกได้ 25 ตัวเพราะเลือกตัวอักษรที่ซ้ำกับตำแหน่งแรกไม่ได้แล้ว ตำแหน่งที่สามเลือกตัวอักษรได้ 24 ตัว เพราะเลือกตัวอักษรที่ซ้ำกับตำแหน่งแรกและตำแหน่งที่สองไม่ได้แล้ว คิดแบบนี้ไปเรื่อย ๆ จนครบหกตำแหน่งจะได้ว่า จำนวนสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรและตัวเลขที่ไม่มีตัวอักษรใด ๆ ปรากฏมากกว่า 1 ครั้ง = $26\times 25\times 24\times 23\times 22\times 21$ แบบ