Number of ways to place n numbers in a circle?

[Avichal]

Homework Statement

In a circle we can place k numbers. The numbers can range from 1 to n. One position in the circle is fixed, say by 1. We have to place the other k-1 places with numbers in the range 1 to n such that no adjacent numbers are equal.

Homework Equations

The Attempt at a Solution

I tried using the basic principle of counting and came up with the equation n^k-1 but I guess that is wrong(upon playing with small values of n and k).

I want to come up with a general method to find the answer

 

[CompuChip]

Playing with a small example with values for n and k sounds like a good idea. How did you get to n^k-1 based on that? Because thought it's wrong, it's close.

 

[Avichal]

At every position there are n-1 things we can place. (n-1) because you can't put the same as the previous one.
So do this k-1 times and you get (n-1)^(k-1)...confused between (n-1)^(k-1) and n^(k-1) [Anyways both are wrong]

But I guess the problem is the last position. I have to take care of the previous as well as the upcoming position. So I think that is where I am going wrong.

Hope I make sense

 

[CompuChip]

Ok so you can do that k - 2 times. The last - (k - 1)th - one depends on whether number k - 2 is the same as number 1 or not.

 

[Avichal]

Hmm, so I just need to find how many ways can you get to the (k-2)th position with number other than 1. Then that many ways multiplied by k is the answer?

 

[haruspex]

Hmm, so I just need to find how many ways can you get to the (k-2)th position with number other than 1. Then that many ways multiplied by k is the answer?

It's a bit more complicated than that. You can start by not worrying about collisions between the kth position and the first position, giving you (n-1)^k-1. Now subtract off those where position k got the number 1. But in the cases where position k-1 got the number 1, you would not have counted patterns with position k getting 1 anyway, so now you've subtracted too much... You can repeat this process to arrive at a series that sums to the right answer.
A clearer way may be to think of the circle (having assigned number 1 to position 1) as a chain of length k+1, both endpoints having the number 1. There are n-1 ways to number position 2; each of these gives you a chain of length k (dropping position 1) but now the endpoints have different numbers. Assigning a number to position 3 can lead to either situation: a chain with endpoints numbered the same or differently. Can you see how to turn this into two recurrence relations involving two functions?