0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ You left out $31425$ and $35241$ $\endgroup$ – glowstonetrees Dec 11 '18 at 4:33
5
$\begingroup$

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.

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

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

$\endgroup$

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.