Generating functions for election results

902 Views Asked by At

This is from my textbook which does not give solutions to problems (i.e. not homework).

Find the generating series for the number of election results involving 4 candidates with respect to the number of voters.

This is easy and is obviously $(1+x+x^2+\cdots)^4$. However, the next question is hard:

Do the same, except assume that all 4 candidates vote for themselves.

How would I solve this problem then?

1

There are 1 best solutions below

0
On BEST ANSWER

In the first question, each of the four candidates can have $0$ or more people who vote for them. In the second question, each candidate is guaranteed at least $1$ vote (themselves). Hence, we obtain: $$ (x + x^2 + x^3 + \cdots)^4 $$