วิธีคิดคร่าวๆ ของผมก็คือ สมมุติว่ามีนักเรียน $n$ คู่ เลือกมา $n-1$ คน โดยจะต้องมีนักเรียนที่คู่กันบางคู่ไม่ถูกเลือกทั้งสองคน
วิธีที่ 1 เลือกตรงๆ เลย เพราะยังไงก็จะต้องมีนักเรียนที่คู่กันบางคู่ไม่ถูกเลือกทั้งสองคนอยู่แล้ว ทำได้ $\displaystyle{\binom{2n}{n-1}}$ วิธี
วิธีที่ 2 PIE นิยามเซต $A_i$ แทนจำนวนวิธีในการเลือกนักเรียนดังกล่าวโดยที่นักเรียนคู่ที่ $i$ ไม่ถูกเลือก เราจะพบว่า
$$n(A_{\displaystyle{a_1}}\cap A_{\displaystyle{a_2}}\cap A_{\displaystyle{a_3}}\cap ...\cap A_{\displaystyle{a_r}})=\binom{2n-2r}{n-1}$$
โดย PIE จะได้จำนวนวิธีที่ต้องการเท่ากับ
$$\sum_{r= 1}^{n} (-1)^{r-1}\binom{n}{r}\binom{2n-2r}{n-1}$$
ดังนั้น
$$\sum_{r= 1}^{n} (-1)^{r-1}\binom{n}{r}\binom{2n-2r}{n-1}=\binom{2n}{n-1}$$
ตามต้องการ แล้วก็ขอบอกว่าถ้าไม่ได้ Hint2 นี่ผมก็คงทำไม่ได้เหมือนกันครับ
|