My question is about a method to approach counting in MATHCOUNTS States #29 2019 by using generating functions.

Here is the problem:

Chris flips a coin 16 times. Given that exactly 12 of the flips land heads, what is the probability that Chris never flips five heads in a row? Express your answer as a common fraction.

Now, there are $\dbinom{12}4$ possible combinations, but the counting at the top is giving me a problem.

To turn this problem into a generating function problem, I considered the amount of heads before each tail. $0,1,2,3,$ or $4$ heads are allowed. Now, we have to do this $5$ times - $4$ before a coin and $1$ at the end. Therefore, we need the coefficient of $x^{12}$ in $(x^4+x^3+x^2+x+1)^5$, which would be our number. However, from here, I cannot do much to simplify this. I can try expressing it as $\frac{(x-1)^5}{(x^5-1)^5}$ but I can't follow with any combinatorics.

I came here to ask if there is a method in which this generating function can be applied which does not involve major computation. (i.e. expanding)

  • $\begingroup$ Your generating function is upside down. $\endgroup$ May 18, 2019 at 7:03
  • $\begingroup$ Adding to the previous comment: to be precise, $1+x+x^2+x^3+x^4=\frac{1-x^5}{1-x}$ (or $\frac{x^5-1}{x-1}$ if you prefer). $\endgroup$ May 18, 2019 at 7:05

1 Answer 1


Write it as $(1-x^5)^5(1-x)^{-5}$. One may apply the binomial expansion to the first power, and the newton-binomial expansion to the second (even when the exponent $-5$ is negative). One gets

$$ \left[\binom{5}{0}-\binom{5}{1}x^5+\binom{5}{2}x^{10}-\cdots\right]\left[1-\binom{-5}{1}x+\binom{-5}{2}x^2-\cdots\right]. $$

Therefore the coefficient of $x^{12}$ is given by combining like terms:

$$ \binom{5}{0}\binom{-5}{12}+\binom{5}{1}\binom{-5}{7}+\binom{5}{2}\binom{-5}{2}. $$

Note you can evaluate binomial coefficients with negative top argument via

$$ \binom{n}{k}:=\frac{n(n-1)\cdots}{k(k-1)\cdots} $$

(There are $k$ factors up top and down below.)

  • $\begingroup$ +1. Alternatively to working out the negative upper index binomial coefficients, one may use the negation formula $\binom{-n}k=(-1)^k\binom{n+k-1}k$, so your answer becomes $\binom50\binom{16}{12}+\binom51\binom{11}7+\binom52\binom62=3620$ $\endgroup$ May 18, 2019 at 7:11
  • 1
    $\begingroup$ I've looked at this again, and I have a question: how come the signs are alternating? I think that multiplying $-\binom{5}{1}x^5$ with $-\binom{-5}7x^7$ would result in a positive $\binom51\cdot\binom{-5}7x^{12}$. $\endgroup$
    – Jason Kim
    Dec 20, 2019 at 6:00

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.