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

ข้อ 1

จำนวนวิธีมีค่าเท่ากับจำนวนคำตอบของสมการ $x_{1}+x_{2}+\dotsb +x_{k}=n$ โดยที่ $x_{i}$ แต่ละตัวเป็นจำนวนเต็มที่ไม่เป็นลบ

ดังนั้นจึงมีวิธีจัดหนังสือทั้งหมด ${n+k-1 \choose n}\,$ วิธี

ข้อ 2

ให้แบ่งขั้นตอนการเลือกหนังสือออกเป็น 3 ขึ้นตอน

1. นำหนังสือ n เล่มมาเรียงกันเป็นแถว ได้ว่ามีวิธีเรียงทั้งหมด $n!\,$ วิธี
2. ทำการตัดสินใจว่าจะให้ชั้นหนังสือแต่ละชั้นมีหนังสือกี่เล่ม เนื่องจากมีชั้นหน้งสือ k ชั้น เราได้ว่ามีวิธีตัดสินใจในขั้นนี้เท่ากับจำนวนคำตอบของสมการ $x_{1}+x_{2}+\dotsb +x_{k}=n$ โดยที่ $x_{i}$ แต่ละตัวเป็นจำนวนเต็มที่ไม่เป็นลบ ซึ่งมีจำนวนคำตอบทั้งหมด ${n+k-1 \choose n}\,$ วิธี
3. สมมติว่าในขั้นที่สองเราตัดสินใจว่าชั้นหนังสือที่ 1 จะมีหนังสือ $x_{1}\,$ เล่ม ชั้นที่ 2 จะมีหนังสือ $x_{2}\,$ เล่ม $\ldots \,$ และชั้นหนังสือที่ $n\,$ จะีมีหนั้งสือ $x_{n}\,$ เล่ม

ให้เรานำหนังสือ $x_{1}\,$ เล่มแรกที่เรียงในขั้นที่ 1 ไปเรียงใส่ในชั้นหนังสือที่ 1 แล้วนำหนังสืออีก $x_{2}\,$ เล่มต่อไปไปเรียงขึ้นชั้นที่ 2 แล้วนำหนังสืออีก $x_{3}\,$ เล่มต่อไปไปเรียงใส่ชั้นที่ 3 $\ldots \,$ แล้วนำหนังสืออีก $x_{n}\,$ เล่มต่อไปไปเรียงใส่ชั้นที่ $n\,$

ฉะนั้นจะมีวิธีการจัดหนังสือทั้งหมด $n!{n+k-1 \choose n}=n!{\frac {(n+k-1)!}{n!(k-1)!}}={\frac {(n+k-1)!}{(k-1)!}}$