Find number of five digit natural numbers using digits $1,2,3,4,5$ such that consecutive digits do not appear together

Question

Find number of five digit natural numbers using digits $1,2,3,4,5$ without Repetition such that consecutive digits do not appear together

I just tried in by listing the possibilities in a sequential manner:

The possibilities are:

$1)$ $13524$

$2)$ $14253$

$3)$ $24135$

$4)$ $24153$

$5)$ $25314$

$6)$ $31524$

$7)$ $35142$

$8)$ $41352$

$9)$ $42531$

$10)$ $42513$

$11)$ $52413$

$12)$ $53142$

So i got $12$ possibilities.

Is there a Mathematical or formal way to solve this and can we generalize it for $n$ digit numbers?

Answer 1

It's all in the following picture: $$\matrix{ &&3&&\cr &/&&\setminus &\cr &1\ &--&\ 5\cr &\setminus &&/&&\cr &\ 4&-&2\ &&\cr}$$ We can begin by $(31\ldots)$, $(13\ldots)$, $(14\ldots)$, $(41\ldots)$, and $(42\ldots)$. This will lead to $7$ strings, which then have to be multiplied by $2$ for the beginnings $(35\ldots)$, $(53\ldots)$, etcetera.

Answer 2

Possible partners for each number are 1: 3,4,5 2: 4,5 3: 1,5 4: 1,2 5: 1,2,3

Suppose 2 is at the left end, it may be followed by 4 or 5 in case of 4 next option is only 1 followed by 35 or 53 so we have 2 options. In case of 5 next option can only be 314. Thus 2 on left edge gives us 3 options.

By symmetry 2 on right edge will also give 3 options.

If 2 is not on edges it is sandwiched between 45 or 54. So we have 2 possibilities. 1 can be placed on either sides of 2 options giving us 4 possibilities. If 1 is near 4, 3 can be placed on other side of 1 or next to 5. if 1 is near 5, 3 can be placed on either side of 1, again multiplying possibility by 2. So we have 8 such options.

On the whole we have 3+3+8=14 strings