Permutations & Combinations
Distribution of identical objects with lower bounds
Grade 11
Question:
<p>The total number of ways in which \(n^2\) number of identical balls can be put in \(n\) numbered boxes \((1, 2, 3, \ldots, n)\) such that \(i^{\text{th}}\) box contains at least \(i\) number of balls is</p>
<p>\({}^{n^2}C_{n-1}\)</p>
<p>\({}^{n^2-1}C_{n-1}\)</p>
<p>\({}^{\frac{n^2+n-2}{2}}C_{n-1}\)</p>
<p>none of these</p>
Step-by-Step Solution
Key Concept: Transform the constraint problem into an unconstrained one by first placing i balls in box i (satisfying the minimum requirement), then distribute the remaining n² - (1+2+...+n) = n² - n(n+1)/2 identical balls freely among n boxes.
<p><strong>Step 1:</strong> Calculate minimum balls required. Box i must contain at least i balls, so minimum = 1 + 2 + 3 + ... + n = n(n+1)/2</p><p><strong>Step 2:</strong> After placing the mandatory balls, remaining balls = n² - n(n+1)/2 = n² - n²/2 - n/2 = (n² - n)/2 = n(n-1)/2</p><p><strong>Step 3:</strong> Now distribute n(n-1)/2 identical balls freely into n numbered boxes. This is a standard stars and bars problem.</p><p><strong>Step 4:</strong> Using stars and bars formula: ways = C(remaining + n - 1, n - 1) = C(n(n-1)/2 + n - 1, n - 1)</p><p><strong>Step 5:</strong> Simplify: C(n(n-1)/2 + n - 1, n - 1) = C([n(n-1) + 2(n-1)]/2, n - 1) = C([(n-1)(n+2)]/2, n - 1) = C(n(n+1)/2, n-1)</p><p>∴ Answer: C</p>
Correct Answer: C