I came across this questions:

Suppose that 10 fish are caught at a lake that contains 5 distinct types of fish. How many different outcomes are possible, where an outcome specifies the numbers of caught fish of each of the 5 types?

I know how the answer is $\binom{10+5-1}{5-1}=4$ This is just star and bar (type 2 on wikipedia) problem with $n=10$ and $r=5$. But I am not able to guess how I can solve the same with generating functions?

I felt it will be coefficient of $x^10$ in $(1+x+x^2+...)^5$. I calculated it as follows: $(1+x+x^2+...)^5=\sum_{j=0}^\infty\binom{10+j-1}{10-1}x^j$
Coefficient of $x^{10}$ in this is $\binom{10+10-1}{10-1}=\binom{19}{9}=92378$ which definitely does not look correct.

When I checked wolfram alpha it was saying coefficient of $x^10$ in $(1+x+x^2+...)^5$ is $0$.

Whats going on here?

  • 1
    $\begingroup$ ${14 \choose 4} = 1001$, not $4$. $\endgroup$ – Travis Willse Sep 26 at 5:45

The correct generating function here is $$(1+x+ \cdots + x^{10})^5 = \left(\frac{1-x^{11}}{1-x} \right)^5$$

Now, use

  • $\frac{1}{(1-x)^5} = \sum_{n=0}^{\infty}\binom{n+4}{4}x^n$

You get $$[x^{10}]\left(\frac{1-x^{11}}{1-x} \right)^5 = [x^{10}]\sum_{n=0}^{\infty}\binom{n+4}{4}x^n = \binom{10+4}{4} = 1001$$

  • $\begingroup$ Yess got my silly mistake. Here if we consider $(1+x+x^2+...)^5$ instead of $(1+x+x^2+...+x^{10} )^5$ we still get same answer. Am wondering when will considering infinite series instead of finite one will give wrong answer? $\endgroup$ – anir Sep 26 at 10:04

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.