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

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?

• You left out $31425$ and $35241$ – glowstonetrees Dec 11 '18 at 4:33

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.

• How did you come up with the diagram? – mathpadawan Dec 11 '18 at 10:23
• @mathnoob: Press on the "edit"; then you shall see it. It's $K_5$ minus four edges, arranged in a symmetric way. – Christian Blatter Dec 11 '18 at 12:22

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