# Non-increasing arrangement

We are arranging the numbers from 1 to 8 in an order so that three consecutive terms cannot be increasing. For example, 12345678 isn’t allowed but 81436572 is. How many ways are there to do it? Please don’t use computers.

• Interesting question, I think I have an idea for how to solve it, I'll give it a try in the morning. Commented Mar 6, 2021 at 5:30
• The answer is obviously 049774, but I don't know in which sense is there a no-computer answer. For such a low limit, it is certainly possible to follow the recurrence relation by hand, but it would be lengthy and boring. From the linked paper, there doesn't seem to be a nice trick to solve it, although an interesting exponential generating function exists. Commented Mar 6, 2021 at 11:13
• In case anyone reads WhatsUp's comment above and also the accepted answer and thinks "haha, what a doofus, said the answer was obvious and didn't even get it right", note that 049774 is an OEIS sequence number, not the actual answer to the question. Commented Mar 6, 2021 at 13:49

Probably not the smartest approach but works:

(Confession: I did check with computer but only afterwards.)

Use inclusion-exclusion to count all permutations with at least one increasing triplet.

For each of the possible 6 positions there are 8x7x6x5x4 = 6720 such triplets.
Pairwise intersections give increasing quadruplets,quintuplets or pairs of triplets. These contribute terms 5 x 1680, 4 x 336 and 6 x 56 x 20. The last term arises as 6 placements of two triplets, 8x7 ways to fill the two remaining cells and 20 ways to distribute 6 numbers over two tiplets.
Threeway intersections give increasing quintuplets to septuplets, and triplets paired with quadruplets or quintuplets. Terms: 4 x 336, 3 x 2 x 56, 2 x 8, 2 x 3 x 8 x 35, 2 x 56
Fourway intersections give increasing sextuplets to octuplets and pairs of quadruplets or triplets and quintuplets. Terms: 3 x 56, 2 x 3 x 8, 3 x 1, 70, 2 x 56
Fiveway intersections give increasing septuplets and octuplets. Terms: 2 x 8, 4 x 1
The full intersection gives the octuplet. Terms: 1

Taken together:

6 x 6720 - (5 x 1680 + 4 x 336 + 6 x 56 x 20) + (4 x 336 + 3 x 2 x 56 + 2 x 8 + 2 x 3 x 8 x 35 + 2 x 56) - (3 x 56 + 2 x 3 x 8 + 3 x 1 + 70 + 2 x 56) + (2 x 8 + 4 x 1) - 1 =
6 x 6720 - 5 x 1680 - 117 x 56 + 208 x 8 - 70 =
40320 - 8400 - 6552 + 1664 - 70 =
26962
This we have to subtract from the full permutation count 8! = 40320.

The final result is therefore:

13358

• Was about to write up a similar answer, nicely summarized! Commented Mar 6, 2021 at 12:21