Take the 2-minute tour ×

We have to form a number of n digits having digits from 1 to 9. Constraint is that first and last digit must be same and no two consecutive digits must be same. How many such number of n digits can be there?

share|improve this question
$n$ has to be larger than $2$ then? Try some examples...! Is this homework? –  draks ... Oct 5 '12 at 6:48
Not a homework. Came through it while practicing a problem. –  Shashwat Kumar Oct 5 '12 at 6:52
I guess $n=1$ would fit the constraints given here. –  user22805 Oct 5 '12 at 6:57
add comment

1 Answer

up vote 1 down vote accepted

Since the first and last digits have to be the same, this is the same as asking how many ways there are to colour $n-1$ points on a circle with $9$ colours such that any two adjacent points have different colours. The answer is given here: $(-1)^{n-1}(9-1)+(9-1)^{n-1}=(-1)^{n-1}\cdot8+8^{n-1}$

share|improve this answer
add comment

Your Answer


