Number of permutations such that each prime is followed by at least one composite

Question

Question: Let $P$ be the number of permutations of $\{3,4,5,6,7,8\}$ such that each prime is followed by at least one composite number. Find $P$.

Using the string method I got $36$ as the answer and by another approach I got $1440$ as the answer. I do not think that these are the correct answers. Please help.

Answer 1

To tackle this problem, we can start with the condition:

each prime is followed by at least one composite.

I think Vinyl_cape_jawa has interpreted this incorrectly -- it means that each prime is followed by at least one composite somewhere on the list. But this is equivalent to saying that the last prime is followed by at least one composite. And all of these numbers are either composite or prime.

So it's actually just saying that: the list ends in a composite!

So: how many permutations are there such that the list ends in a composite? Start by finding the number of ways to choose the last element; then find the number of ways to order all the remaining elements.

P.S. I haven't heard of the "string method", but I think that neither of your two answers are right.

$1440$ can't be right because the total number of permutations of the set is $6! = 720$, which is smalle.r

$36$ I think would be correct if Vinyl_cape_jawa's interpretation is right.