Elementary Generating Function Models

466 Views Asked by At

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.

1

There are 1 best solutions below

1
On

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.