Given the following problem:

A national singing contest has five distinct entrants from each state. Use a generating function for modeling the number of ways to pick $20$ semifinalists if there are at most three people from each state.

Up until this question, I've been dealing with only identical objects. I'd like to say that the function will be


but the problem with this is that I'm assuming that all of the contestants are identical. How can I take account for the fact that each contestant is distinct?

  • $\begingroup$ For anyone else wondering like me where the number $50$ came from: it's from the assumption that there are $50$ states in whatever country this problem is about. $\endgroup$ – ShreevatsaR Mar 4 '14 at 4:11

If the contestants are all distinct, you can take account of that by changing your coefficients:

Of the $5$ entrants from each state, there are $\binom{5}{0}$ ways to choose 0 of them, $\binom{5}{1}$ ways to choose $1$, $\binom{5}{2}$ ways to choose $2$, and so on. So, the generating function for contestants from a single state is $$ f(x)=\binom{5}{0}+\binom{5}{1}x+\binom{5}{2}x^2+\binom{5}{3}x^3=1+5x+10x^2+10x^3, $$ since we cut off at $3$ per state.

So, in all, $$ g(x)=(1+5x+10x^2+10x^3)^{50}. $$

  • 2
    $\begingroup$ $(1+x)^{250}$ looks like it does not take into account the limitations of at most 3 per state. Given your other advice, however, I came up with $g(x)=(1+5x+10x^{2}+10x^{3})^{50}$ $\endgroup$ – agent154 Mar 3 '14 at 17:07
  • $\begingroup$ Oy. Yeah, I screwed the pooch on that one! I'll fix it quick. Your answer is absolutely right. $\endgroup$ – Nick Peterson Mar 3 '14 at 17:19

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.