How Many Valid Orderings Avoid Neighboring Duplicates in Mappings from N to M?

[madness]

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.

Thanks!

 

[jedishrfu]

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.

 

[madness]

I figured out how to solve it, but thanks anyway!