1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of ways to place n numbers in a circle?

  1. Apr 5, 2013 #1
    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. jcsd
  3. Apr 5, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Apr 5, 2013 #3
    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
  5. Apr 5, 2013 #4


    User Avatar
    Science Advisor
    Homework Helper

    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.
  6. Apr 5, 2013 #5
    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?
  7. Apr 7, 2013 #6


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted