Can You Solve This Combinatorics Problem?

In summary, the conversation discusses a problem where a set of numbers is mapped onto a smaller set, and the goal is to find ways to list the first set without any numbers repeating as neighbors in the second set. The difficulty increases when a certain distance between repeating numbers is required, and when only a subset of the first set is allowed. The individual seeking help eventually solves the problem through experimenting with different examples.
  • #1
madness
815
70
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!
 
Mathematics news on Phys.org
  • #2
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
I figured out how to solve it, but thanks anyway!
 

1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and arranging objects or events in a systematic way. It involves the study of combinations, permutations, and other methods of organizing and selecting objects.

2. What are some real-life applications of combinatorics?

Combinatorics has many practical applications, such as in computer science, genetics, cryptography, and statistics. It can be used to analyze and optimize algorithms, design experiments, and model complex systems.

3. What is the difference between combinations and permutations?

Combinations are unordered selections of objects, while permutations are ordered arrangements of objects. In other words, combinations do not take into account the order of the objects, while permutations do.

4. How do I solve a combinatorics problem?

The first step in solving a combinatorics problem is to identify the type of problem it is (e.g. combination, permutation, etc.) and determine what information is given and what needs to be found. Then, use the appropriate formula or method to calculate the answer.

5. What are some common mistakes to avoid in combinatorics problems?

Some common mistakes in combinatorics problems include not considering all possible cases, double counting, and using the wrong formula or method. It is important to carefully read the problem and make sure all conditions are met before solving.

Similar threads

  • General Math
Replies
2
Views
1K
  • General Math
Replies
1
Views
629
  • General Math
Replies
8
Views
984
Replies
2
Views
586
  • General Math
Replies
8
Views
1K
  • General Math
Replies
1
Views
1K
Replies
5
Views
1K
  • General Math
Replies
3
Views
3K
Replies
6
Views
909
  • General Math
Replies
12
Views
1K
Back
Top