Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The twist is that each number should be 'associated' with at most K other numbers. Let me explain 'association' with an example: Notation: (1 A 2) means 1 is associated with 2, and (1 A 2) is equivalent to (2 A 1).

Let the numbers be {1,2,3,4,5,6}, and let K=3. Then the combinations CAN be:

{1-2-3} ----- (1 A 2), (2 A 3)
{1-3-4} ----- (1 A 3), (3 A 4)
{1-5-6} ----- (1 A 5), (5 A 6)
etc.

Note 1: 1 has completed its share of three associations, and cannot appear in any other combination. Similarly, 3 has also completed 3 associations. Note 2: The combinations themselves do NOT matter, but their maximum possible number does. What I want to calculate is the upper bound of the number of such combinations, given N numbers with associations capped at K.

I need this to allocate an array. The actual problem is in chemistry and is to find all possible angles given the atoms and their bonds. Association is actually bonds, (max associations=valency)and numbers are atoms themselves.

EDIT: A more chemistry example:

     6
     |
1 -- 2 -- 3
|    | 
4    5 

Here, the dashes show bonds, so the angles here are:

1-2-3
1-2-5
1-2-6
2-1-4 (4-1-2 is the same angle, and 1-2-4 or 1-4-2 is NOT an angle, 
so only ONE of 1-2-4, 4-2-1, 2-1-4, 4-1-2, 1-4-2, 2-4-1 can appear)
3-2-5
3-2-6
5-2-6

As you can see, the MAXIMUM valency (max association) is 4 because of atom 2. So, I want to calculate the maximum possible angles that can be present, assuming the maximum associations are 4 for any atom. (In this instance, there is only one atom with valency 4, but there might be instances in which many or even all have valency of 4). That is why I need only the upper bound.

Thank you in advance !!

share|improve this question
    
Since 1-2-3 is not the same as 1-3-2 (in the first case, 1 is associated with 2, in the second case, not), these aren't combinations, they are permutations. –  Gerry Myerson Jul 18 '12 at 5:19
    
I do not understand the heuristics behind this. Why can you not associate 1 with 4? –  Arkamis Jul 18 '12 at 5:20
    
@GerryMyerson Actually only one of 1-2-3 and 1-3-2 can appear in the list of combinations. Which one of them appears doesn't matter. As I said in the question, the exact list of combinations doesnt matter, but the upper bound on their numbers does. –  Shitij Bhargava Jul 18 '12 at 5:49
    
@EdGorcenski That was only an example. Once more, it doesn't matter if I associated 1 with 4 or 5 or 6. The number of unique sets of combinations themselves can many, but I am not concerned with that. I am only concerned with the maximum number of combinations from all possible sets of combinations. –  Shitij Bhargava Jul 18 '12 at 5:53
    
Also, the associations are bonds. So for example, if 1 was Carbon (C) it can bond to a maximum of 4 other atoms (called valency). In the system, I have a list of what atom is bonded to what atom. I have to find the angles. Like if C1 is bonded to C2, which is bonded to O, then C1-C2-O is an angle. I have to find the maximum angles that can be there in the system to allocate an array. I hope this gives the problem some context. –  Shitij Bhargava Jul 18 '12 at 5:55
add comment

1 Answer

The number of permutations of $n$ things taken 3 at a time is $$n(n-1)(n-2)$$ Each permutation gives rise to 2 "associations". Each thing is only supposed to have at most $k$ associations, so all told you can't have more than $kn/2$ associations (the division by 2 happens because, say, the association of 1 with 2 also counts as an association of 2 with 1). So you can't use more than $kn/4$ permutations. So the maximum number of permutations is no more than the smaller of $kn/4$ and $n(n-1)(n-2)$.

In your example, $n=6$, and $k=3$, so you can't have more than $18/4$, which is to say, 4 permutations. You can have that many by using the three you have and 2-4-5.

This is just an upper bound - I don't guarantee you can always achieve it.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.