There are 10 people waiting in line at a cafe, and each person has a different height. In how many ways can they be permuted such that there are no 6 consecutive people in increasing order of height (from back to front)?
I have been thinking about this question for a while now and I know that without the restrictions the people can be lined up in 10! ways and I think it should be divided by 6! since there can not be 6 consecutive people in increasing order of height (from back to front) standing next to each other. Can anyone confirm my answer or help me fix it if it needs something added?
Thank you in advance for any answers or explanations!
Best Answer
There are $10!$ ways to arrange the people. Let us subtract the number of arrange with $6$ consecutive people in height order. There are $\binom{10}{6}$ ways to choose the people, and there are $5$ places they can be. That is, the line of $6$ people can start in positions $1$ through $5$. Then we can arrange the remaining $4$ people in $4!$ ways, giving $$10!-5\binom{10}64!$$
However, there may be $7$ consecutive people arranged in order, and we've subtracted each such arrangement twice, once for the first $6$ people, and once for the last $6$ people. We have to add those arrangement back in, so that we only subtract them once. Proceeding as above, we now get $$10!-5\binom{10}64!+4\binom{10}{7}3!$$
Now what if there are $8$ consecutive people arranged in order? We've subtracted it $3$ times, and added it twice, so no adjustment is necessary. You should check that no adjustment is necessary in the $9$- or $10$-in-a-row cases, either.
So, the final answer is $$10!-5\binom{10}64!+4\binom{10}{7}3!=3,606,480$$