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!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Combinatorics problem
  1. Combinatorical Problem (Replies: 1)

  2. Combinatorics problem (Replies: 14)