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

ข้อย่อย 1

จากเงื่อนไขที่การเลือกลำดับ $(S_{1},S_{2},...,S_{k})$ โดยที่ $S_{1}\subseteq S_{2}\subseteq S_{3}\subseteq ...\subseteq S_{k}$ นั้นแสดงว่า ถ้า $x\in S_{i}$ แล้ว $x\in S_{j};j>i$ ด้วย และถ้า $x\notin S_{i}$ แล้ว $x\notin S_{j};j>i$ ด้วย ดังนั้น จำนวนของลำดับ $(S_{1},S_{2},...,S_{k})$ ในข้อนี้คือ ${(k+1)}^{n}$

ข้อย่อย 2

การที่ $S_{1},S_{2},...,S_{k}\,$ ไม่มีส่วนร่วมกันเป็นคู่ ๆ คือ สำหรับสมาชิก x ใด ๆ แล้ว x จะอยู่ในสับเซตได้เพียงตัวเดียวเท่านั้น หรือถ้าไม่อยู่ก็ไม่อยู่ทุกสับเซตเลย ดังนั้น จำนวนของลำดับ $(S_{1},S_{2},...,S_{k})\,$ ในข้อนี้คือ ${(k+1)}^{n}\,$

ข้อย่อย 3

การที่ $S_{1}\cap S_{2}\cap S_{3}\cap ...\cap S_{k}=\emptyset$ นั้นแสดงว่าสำหรับสมาชิก x ใด ๆ นั้น x สามารถอยู่ได้ในหลายสับเซต แต่จะอยู่ทั้ง k สับเซตไม่ได้ ฉะนั้นสมาชิกแต่ละตัวจึงมีวิธีเลือกสับเซตที่มันอยู่เท่ากับ $2^{k}-1$ วิธี เนื่องจากมีวิธีเลือกสับเซตทั้งหมด $2^{k}\,$ วิธี แต่มีวิธีที่ใช้ไม่ได้ (อยู่ในสับเซตทุกสับเซต) อยู่หนึ่งวิธี ฉะนั้นจึงมีลำดับ $(S_{1},S_{2},...,S_{k})\,$ ทั้งหมด ${(2^{k}-1)^{n}}\,$ ลำดับ