# How do I design a generating function to count subsets of distinct objects?

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

$$g(x)=(1+x+x^2+x^3)^{50}$$

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?

• 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. – ShreevatsaR Mar 4 '14 at 4:11

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}.$$
• $(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}$ – agent154 Mar 3 '14 at 17:07