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}$