madness
- 813
- 69
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!
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!