Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

An international singing contest has $5$ distinct entrants from 50 different countries. Use a generating function for modeling the number of ways to pick $20$ semifinalists if there is at most $1$ person from each country.

Solution: We want the coefficient of $x^{20}$ from $$ \underbrace{(1+x)^5}_{USA}\underbrace{(1+x)^5}_{England}+\ldots + \underbrace{(1 + x)^5}_{Australia} $$

I don't believe my solution is correct as they specifically say there are $5$ distinct entrants from each state, but I'm not sure how else to address it.

share|cite|improve this question
Please make questions globally intelligible. The language of this site is English, but the site is not for English-speaking countries only. Not everyone in the world knows that there are $50$ states in the USA or that these states have two-letter abbreviations. – joriki Feb 15 '13 at 8:00
@joriki Yeah, I initially put the abbreviations there to address that issue, but I now realize that the abbreviations don't help much either. Thanks. – AlanH Feb 15 '13 at 19:45

I'll assume that you're talking about the United States of America, which currently comprise $50$ states.

Your right that your solution is wrong, but not for the reason you state. It does count $5$ distinct entrants from each state, but it doesn't impose the restriction that there's at most $1$ person from each state. To do so, you need to take only that part of each factor that counts at most $1$ person from that state, that is, you need to replace $(1+x)^5$ by $1+5x$. Then the desired count it the coefficient of $x^{20}$ in $(1+5x)^{50}$, which is

$$ \binom{50}{20}5^{20}\;. $$

That makes sense, since you can choose $20$ states out of $50$, and then choose $1$ of $5$ entrants in each of those states.

share|cite|improve this answer
Could you explain why the coefficient of $x^{20}$ is $\binom{50}{20}5^{20}$. Specifically, why you it's $5$ that is raised to the power of $20$. – AlanH Feb 15 '13 at 19:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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