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