1
$\begingroup$

I have a problem with understanding following example: We are given $a_n$ - number of ways that to put $n$ balls(indistinguishable) into $k$ boxes, $k$ is fixed. Now we calculate $\sum_{n=1}^{\infty}a_n\cdot x^n=(1+x+x^2\ldots)\cdot\ldots\cdot(1+x+x^2+\ldots)=\frac{1}{(1-x)^{k}}$ I don't see how we come up with first equality. I will be very glad for simple explanation.

$\endgroup$
3
$\begingroup$

Note that choosing the number of ways that to put $n$ indistinguishable balls into $k$ boxes, is exactly the same as asking for the number of $k$ non-negative integers that add up to $n$, and is therefore the same as asking what the coefficient is (read "how many") of $x^n$ is ("are") in the expression: $$\prod_{i=1}^k\left(\sum_{j=0}^\infty x^j\right)$$

$\endgroup$
1
  • $\begingroup$ I see it now, thanks! $\endgroup$ Jun 17 '17 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.