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

ข้อย่อย 1

จากเงื่อนไขที่การเลือกลำดับ $(S_{1},S_{2},...,S_{k})\,$ โดยที่ $S_{1}\subseteq S_{2}\subseteq S_{3}\subseteq ...\subseteq S_{k}$

ให้ $x\,$ เป็นสมาชิกใดๆ ของเซต $\{1,2,3,\ldots ,n\}\,$ หาก $x\in S_{i}$ แล้ว $x\in X_{j}\,$ สำหรับ $j\,$ สำหรับจำนวนเต็ม $j\,$ ทุกตัวที่มีค่ามากกว่า $i\,$ ฉะนั้นเราได้ว่าสำหรับสมาชิกของเซต $\{1,2,\ldots ,n\}\,$ แต่ละตัว มันทางเลือก $k+1\,$ ทางเลือกดังต่อไปนี้

• ไม่เป็นสมาชิกของ $S_{1},S_{2},\ldots ,S_{k}$ สักตัว
• เป็นสมาชิกของ $S_{i},S_{i+1},S_{i+2},\ldots ,S_{k}\,$ สำหรับ $i=1,2,\ldots ,k\,$

ฉะนั้นจำนวนของลำดับ $(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}}\,$ ลำดับ