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.
$\begingroup$
$\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$– AnkitCommented Mar 6, 2021 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$– WhatsUpCommented Mar 6, 2021 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 ♦Commented Mar 6, 2021 at 13:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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
-
$\begingroup$ Was about to write up a similar answer, nicely summarized! $\endgroup$– hexominoCommented Mar 6, 2021 at 12:21