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!

Combinatorics problem

  1. Feb 20, 2015 #1
    Hi all,

    I've come across an interesting problem that I'm unsure how to solve. Let say we have N numbers {1, 2, ... N}. Each number in this list is mapped to one number in {1,..,M} where M < N.

    What are the possible ways I can list the first set, such that the numbers of the second set which they are mapped onto never repeat as neighbours.

    For example, I can reorder the first set as {5, 3, 10, ..., N, ..., 1}. Writing this out in terms of the second set which each of these numbers is mapped onto, it might look something like {7, 2, 2, ..., 3, ..., 5}.

    In the above example, the {.., 2, 2, ...} part is an example of two numbers repeating as neighbours. But how can I figure out how many orderings there are which don't do this?

    Now, if that is not difficult enough, I have some more difficult questions. What if I require that the two numbers can't repeat within some distance D of each other. For example, {...,2,1,2,...} if D=2 or {...2,1,3,2,...} if D=3.

    Finally, what if we don't have to order the whole list {1,...,N} in this way, but are allowed to pick any subset of P elements (where P is a fixed number). Can I then calculate how many possible lists there are?

    I'm willing to work through this with anyone who will help me, but for now I have no idea where to start.

  2. jcsd
  3. Feb 20, 2015 #2


    Staff: Mentor

    This may not be helpful but have you tried using concrete examples like N=2 and M=3 then bumping it up to N=3 and M=4 or 5...

    Perhaps you'll see a pattern that you can exploit.
  4. Feb 21, 2015 #3
    I figured out how to solve it, but thanks anyway!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook