Six people of different heights are getting in line to buy donuts. Compute the number of ways they can arrange themselves in line such that no three consecutive people are in increasing order of height, from front to back.
I think I have most of the solution done. We proceed with PIE.
First, we have $6!$ ways to order with no restrictions.
Second, we realize if we have one group three consecutive heights (we'll deal with two groups of three later), we have $\binom{6}{3}*4!$ ways.
Next, we compute the number of ways for four consecutive heights, which is $\binom{6}{4}*3!$.
Similarly we finish the other cases to get $$6!-\bigg(\binom{6}{3}*4!-\binom{6}{4}*3!+\binom{6}{5}*2!-\binom{6}{6}*1!\bigg)$$
Now we have to deal with the case of two groups of three consecutive heights. This should be $\frac{\binom{6}{3}*2}{2}$I'm not sure if we should put it subtracting from 6! or subtracting it from the terms in the parentheses since it overlaps with the last and second case of the PIE.
Thanks!
Observe that a sequence of three consecutive people who appear in increasing order of height must begin in one of the first four positions. Let $A_i$, $1 \leq i \leq 4$, be the set of arrangements in which three consecutive people starting in position $i$ appear in increasing order of height. To find the number of arrangements of six people so that no three consecutive people are in increasing order of height, we must subtract $|A_1 \cup A_2 \cup A_3 \cup A_4|$ from the $6!$ possible arrangements of six people. By the Inclusion-Exclusion Principle, \begin{align*} & |A_1 \cup A_2 \cup A_3 \cup A_4|\\ & \quad = |A_1| + |A_2| + |A_3| + |A_4|\\ & \qquad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_1 \cap A_4| - |A_2 \cap A_3| - |A_2 \cap A_4| - |A_3 \cap A_4|\\ & \quad\qquad + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4|\\ & \qquad\qquad - |A_1 \cap A_2 \cap A_3 \cap A_4| \end{align*}
$|A_1|$: If the first three people are in order of increasing height, there are $\binom{6}{3}$ ways to choose the three people, one way to arrange them in order of increasing height, and $3!$ ways to arrange the remaining people in the remaining three positions. Hence, $$|A_1| = \binom{6}{3}3!$$
By symmetry, $$|A_1| = |A_2| = |A_3| = |A_4|$$
$|A_1 \cap A_2|$: If both the first three and second three people appear in order of increasing height, then the first four people must be arranged in order of increasing height since the sequences overlap. Choose which four people appear in the first four positions. Arrange them in order of increasing height. Arrange the remaining two people in the remaining two positions. $$|A_1 \cap A_2| = \binom{6}{4}2!$$
By symmetry, $$|A_1 \cap A_2| = |A_2 \cap A_3| = |A_3 \cap A_4|$$
$|A_1 \cap A_3|$: If the first three people and third three people appear in order of increasing height, then the first five consecutive people must appear in order of increasing height since the sequences overlap. Choose which five of the six people appear in the first five positions, arrange them in order of increasing height, then place the remaining person in the last position. $$|A_1 \cap A_3| = \binom{6}{5}1!$$
By symmetry, $$|A_1 \cap A_3| = |A_2 \cap A_4|$$
$|A_1 \cap A_4|$: The first three people appear in order of increasing height, as do the last three people. Since the sequences do not overlap, the person who appears in the fourth position may be shorter than the person who appears in the third position. Choose which three people appear in the first three positions, arrange them in order of increasing height, then arrange the other three people in order of increasing height in the last three positions. $$|A_1 \cap A_4| = \binom{6}{3}$$
$|A_1 \cap A_2 \cap A_3|$: If the first three, second three, and third three people each appear in order of increasing height, then the first five people must appear in order of increasing height since the sequences overlap. As we saw above, this means $$|A_1 \cap A_2 \cap A_3| = \binom{6}{5}1!$$
By symmetry, $$|A_1 \cap A_2 \cap A_3| = |A_2 \cap A_3 \cap A_4|$$
$|A_1 \cap A_2 \cap A_4|$: If the first three, second three, and last three people each appear in order of increasing height, then all six people must appear in order of increasing height since the sequences overlap. Hence, $$|A_1 \cap A_2 \cap A_4| = 1$$
By symmetry, $$|A_1 \cap A_2 \cap A_4| = |A_1 \cap A_3 \cap A_4|$$
$|A_1 \cap A_2 \cap A_3 \cap A_4|$: If the first three, second three, third three, and last three people each appear in order of increasing height, then all six people must appear in order of increasing height since the sequences overlap. Hence, $$|A_1 \cap A_2 \cap A_3 \cap A_4| = 1$$
Thus, by the Inclusion-Exclusion Principle, the number of ways six people can be arranged in line so that no three consecutive people appear in order of increasing height is $$6! - 4\binom{6}{3}3! + 3\binom{6}{4}2! + 2\binom{6}{5}1! + \binom{6}{3} - 2\binom{6}{5}1! - 2 \cdot 1 + 1$$