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

ให้เซต $B\,$ เป็นเซตของวิธีกระจายลูกบอลที่ต่างกัน 8 ลูก ลงในไห 3 ใบ โดยที่ไม่มีเงื่อนไขอะไรเลย จะได้ว่า $|B|=3^{8}$ เนื่องจากลูกบอลแต่ละลูกสามารถเลือกไหที่ตัวเองจะอยู่ได้ 3 วิธี

ให้เซต $A\,$ เป็นเซตของวิธีกระจายลูกบอลที่ต่างกัน 8 ลูก ลงในไห 3 ใบ โดยที่แต่ละไหจะต้องมีลูกบอลอย่างน้อย 1 ลูก

ได้ว่า $B-A\,$ คือเซตของวิธีกระจายลูกบอลที่ต่างกัน 8 ลูก ลงในไห 3 ไบ โดยที่มีไหว่างอย่างน้อย 1 ไห

ให้ $C_{1},C_{2},C_{3}\,$ เป็นเซตของวิธีกระจายลูกบอลที่ต่างกัน 8 ลูก ลงในไห 3 ไบ โดยที่ไหหมายเลข 1 ว่าง, ไหหมายเลข 2 ว่าง และไหหมายเลข 3 ว่าง ตา่มลำดับ

ให้ $C_{12},C_{23},C_{31}\,$ เป็นเซตของธีกระจายลูกบอลที่ต่างกัน 8 ลูก ลงในไห 3 ไบ โดยที่ไหหมายเลข 1 และ 2 ว่าง, ไหหมายเลข 2 และ 3 ว่าง และไหหมายเลข 3 และ 1 ว่าง ตา่มลำดับ

เราได้ว่า $B-A=C_{1}\cup C_{2}\cup C_{3}\cup C_{12}\cup C_{23}\cup C_{31}\,$ และเนื่องจากเซตต่างๆ ทางขวามีของสมการไม่มีส่วนร่วมกันเป็นคู่ๆ เราได้ว่า $|B-A|=|C_{1}|+|C_{2}|+|C_{3}|+|C_{12}|+|C_{23}|+|C_{3}1|$

พิจารณาเซต $C_{12},C_{23},C_{31}\,$ เราได้ว่า $|C_{12}|=|C_{23}|=|C_{31}|=1\,$ เนื่องจากลูกบอลทุกลูกจะต้องไปอยู่ในไหที่ไม่ว่างที่เหลือ จึีงมีวิธีกระจายแค่วิธีเดียว

พิจารณาเซต $C_{1},C_{2},C_{3}\,$ เราได้ว่า $|C_{1}|=|C_{2}|=|C_{3}|\,$ เนื่องจากทั้งสามเซตเป็นกรณีที่สมมาตรกัน (เราสามารถเปลี่ยนชื่อไหให้ $C_{1}\,$ กลายเป็น $C_{2}\,$ ได้)

พิจารณาเซต $C_{1}\,$ เราได้ว่า $|C_{1}|=2^{8}-2\,$ เนื่องจากลูกบอลแต่ละลูกสามารถเลือกอยู่ในไหหมายเลข 2 หรือหมายเลข 3 ได้ แต่มีวิธีการกระจายที่ใช้ไม่ได้อยู่สองวิธ๊ คือกรณีที่ลูกบอลทุกลูกอยู่ในไหหมายเลข 2 และกรณีที่ลูกบอลทุกลูกอยู่ในไหหมายเลข 3

ดังนั้นเราได้ว่า $|B-A|=3(2^{8}-2)+3=3\cdot 2^{8}-3\,$ ฉะนั้น $|A|=|B|-|B-A|=3^{8}-3\cdot 2^{8}+3\,$