# Using generating functions to determine conditional probability of five heads in a row

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)

• Your generating function is upside down. May 18, 2019 at 7:03
• 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). May 18, 2019 at 7:05

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.)

• +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$ May 18, 2019 at 7:11
• 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}$. Dec 20, 2019 at 6:00