How many ways are there to arrange a sequence of 5 distinct numbers such that no 3 consecutive numbers are strictly increasing? For example, let's say we have a set of 5 numbers: $1, 2, 3, 4, 5$
The order $1, 3, 2, 5, 4$ would work but $1, 3, 2, 4, 5$ wouldn't. I have no idea how to approach this, any help?
My own progress:
I tried to arrange them in decreasing order and then swap a number with a number that comes after it. I feel like that doesn't take into account every possible arrangement even if the same procedure is done for every number, though.
 A: If you are careful, you can solve this with complementary counting, That is, you only need the "exclusion" part of the principle of inclusion exclusion.
The "bad" permutations $[a_1,a_2,a_3,a_4,a_5]$ fall into one of three categories:

*

*Permutations where $a_3<a_4<a_5$.


*Permutations where $a_2<a_3<a_4$, but $a_4>a_5$.


*Permutations where $a_1<a_2<a_3$, but $a_3>a_4$.
The reason for the "but" clauses is to ensure these three bad categories are disjoint, to prevent double-counting. In effect, we are grouping together bad permutations according to the rightmost occurrence of its three increasing entries.
Anyways, there are $5!/3!=20$ permutations in the first category (each of the $3!$ relative orderings of $a_3,a_4$ and $a_5$ are equally likely) and $5!/(4\cdot 2)=15$ permutations in each of the second and third categories. To explain the count for category $2$, note that $a_2<a_3<a_4>a_5$ occurs if and only if $a_4$ is the largest of $\{a_2,a_3,a_4,a_5\}$, and if $a_2<a_3$. These are independent events with probabilities $1/4$ and $1/2$, respectively.
Therefore, the number of good permutations is $120-20-15-15=70$.
The same method works seamlessly for permutations of length $6$. However, once we get to length $7$, this method will still have some double-counting to deal with.  Never mind, there is double counting already for length $6$, since it is possible to have $a_1<a_2<a_3>a_4<a_5<a_6$, i.e, you can have two increasing sequences of length $3$ which are not part of a larger increasing subsequence.
A: As per my comment, just apply PIE.
Let $ A $ be the configurations where the first 3 are increasing.
Let $ B $ be the configurations where the middle 3 are increasing.
Let $ C $ be the configurations where the last 3 are increasing.
We are interested in the set of all configurations excluding $ A \cup B \cup C$.
PIE states that
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B | - |B \cap C | - |C \cap A| + |A \cap B \cap C |,$$
so we just need to hunt down these values.
Applying basic permutations counting, we can show that

 $|A| =  20, |B| = 20, |C| = 20$,
$|A \cap B| = 5, |B \cap C | = 5, |A \cap C | = 1 $,
$|A \cap B \cap C | = 1 $

Hence, by PIE,

 $|A \cup B \cup C| = 20 + 20 + 20 - 5 - 5 - 1 + 1 = 50$.

Thus, the number of allow configurations is $ 120 - 50 = 70$.

Notes

*

*It is not that much harder for 6 numbers, as long as you carefully list out the $ \cap A$, and consider how they overlap. Try it for yourself.

*However, it quickly becomes tedious (unless you have a great way or categorizing the possible intersections).

*I intentionally avoided calling them $ A_i$, because $A_i \cap A_j$ greatly depends on the $i,j$ values.

