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