# Number of ways to place n numbers in a circle?

1. Apr 5, 2013

### Avichal

1. The problem statement, all variables and given/known data
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.

2. Relevant equations

3. The attempt at a solution
I tried using the basic principle of counting and came up with the equation nk-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

2. Apr 5, 2013

### CompuChip

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

3. Apr 5, 2013

### 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

4. Apr 5, 2013

### 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.

5. Apr 5, 2013

### 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?

6. Apr 7, 2013

### haruspex

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?