Combinatorics problem

  • Thread starter madness
  • Start date
  • #1
780
53
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!
 

Answers and Replies

  • #2
12,239
5,952
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.
 
  • #3
780
53
I figured out how to solve it, but thanks anyway!
 

Related Threads on Combinatorics problem

  • Last Post
Replies
14
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
12
Views
853
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
5
Views
1K
Replies
7
Views
3K
Replies
5
Views
894
Replies
3
Views
2K
Top