3
$\begingroup$

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 !!

  • 0
    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.2012-07-18

1 Answers 1

1

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.