3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Interesting question, I think I have an idea for how to solve it, I'll give it a try in the morning. $\endgroup$
    – Ankit
    Mar 6 at 5:30
  • $\begingroup$ 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. $\endgroup$
    – WhatsUp
    Mar 6 at 11:13
  • $\begingroup$ 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. $\endgroup$
    – Gareth McCaughan
    Mar 6 at 13:49
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Was about to write up a similar answer, nicely summarized! $\endgroup$
    – hexomino
    Mar 6 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.