อ้างอิง:
ข้อความเดิมเขียนโดยคุณ RoSe-JoKer
น้อง dektep ไม่ต้องบอกนะครับว่าเอาโจทย์มาจากไหน ผมค่อนข้างอ่อนคอมบิยังไงก็เอาโจทย์มาให้ฝึกหน่อยนะครับ
|
ผมก็ไม่รู้หรอกครับว่าโจทย์อะไร
วิธีทำ
พิจารณากล่อง $1,2,...,n+k$
ให้ $A_i$ คือเซตของการแจกของ $a_1,a_2,...,a_n$ ลงในกล่องโดยกล่องที่ห้ามใส่ของลงในกล่องที่ $i$ และ $i=1,2,...,n$
พิจารณา $|{A_1}' \cap {A_2}' \cap ... {A_n}'| = |U|-|A_1 \cup A_2 \cup ... \cup A_n|$
โดย $PIE$ จะได้ว่า $|U|-|A_1 \cup A_2 \cup ... \cup A_n|=(n+k)^n-\binom{n}{1}(n+k-1)^n-...+(-1)^n\binom{n}{n}k^n$
โดยการนับแบบที่สอง พิจารณาว่า ${A_1}' \cap {A_2}' \cap ... {A_n}'$ คือวิธีแจกของต่าง $a_1,...,a_n$ ลงใน $n$ กล่องแตกต่างกัน
ซึ่งทำได้ $n!$ วิธี
เนื่องจากการนับทั้งสองทางต้องมีค่าเท่ากันดังนั้น $(n+k)^n-\binom{n}{1}(n+k-1)^n-...+(-1)^n\binom{n}{n}k^n = n!$