I have two questions here, with the first one concerning a solved example, while the second concerns possible constraints for $k$ given $n$.
1 . It is given in a solved problem in book titled Combinatorics, A guided Tour, by David Mazur that for a circular lock with $30$ digits from $0-29$, the possible values for a $4$ digit combination is: $30*27*27*27$.
For the first digit, the number of choices is obvious; & for the second the choices are :
=> $30$ – (the chosen first digit) – (two digits adjacent to the chosen first digit)
=> $27$
It is given that the choices for the 3rd digit are : $27$
I am unable to understand how the choices are $27$ for third digit. For me, it should :
$30$ – (two existing choices) -(either $3$ or $4$ adjacent digits) => either $25$ or $24$ choices
Similarly, it is given that the choices for the 4th digit are : $27$, which is not understandable at all too.
2 . The second question arose in my attempt to have a smaller example to understand the given solution. I took lock with $9$ digits from $0-8$ & combination of $3$ digits. I took the first digit as $0$, second one is having $7$ choices from $1-7$, while the third digit's choices vary with the actual second digit chosen.
Say, if the second digit is $2$, the choices available for the 3rd digit: $4,5,6,7$; while for the second digit of $3$, the choices available are : $5,6,7$.
So, my small example is not even getting a consistent value for the number of choices for the 3rd digit.
This makes me think that may be for $n=8$, the value of $k=3$ is too high.
So, in the given circular lock of $n$ digits, is there a bar on the number of combination digits ($k$) with the stated constraints.
Update – for 2nd question : The modification made in light of responses is shown below:
Say, if the second digit is $2$, the choices available for the 3rd digit: $0, 4,5,6,7,8$ –or $6$ choices; while for the second digit of $3$, the choices available are : $0,1,5,6,7,8$ –or $6$ choices.
So, effectively my second question is solved.
Best Answer
In general, for such circular lock with $n$ digits and with the properties that consecutive digits in the password of length $k$ can't share the same digit as well as the neighboring digits.
For the first number, there is no restriction so there are $n$ options.
For the remaining $k-1$ digits, they have to avoid the digit that the previous digit has just chosen and also to avoid their neighbors, hence each of them have $n-3$ options.
Hence the general formula should be $n \cdot (n-3)^{k-1}$.