Finding the upper limit on number of angles given maximum valency of atoms

shitij

Hi all !

Let me explain the problem:

I have boolean matrix which represents which atom is bonded with which atom in a system. (1=bonded,0=nonbonded). I have to extract all the possible angles and dihedrals from this matrix.

Mathematically, I have an adjacency matrix of a graph(undirected, non-cyclic), and what I want to know is the upper bound of the number of two length paths (and similarly three length paths) that can be present assuming that maximum degree of any node is N (valency). I need this to allocate an array. Simply doing C(Natoms,3) and C(Natoms,4) will waste a huge amount of memory, but I dont know enough combinatorics to incorporate maximum degree of a node to this.

Example:
If atoms are [1,2,3,4,5,6] and maximum valency, N=3 (any atom can bond to at most 3 other atoms)
Then angles can be:
1,2,3 (2,3,1 or 3,1,2 cannot be present, and 1,2,3 is same as 3,2,1. Combinations not permutations.)
1,3,4
1,5,6
etc. and notice that 1 and 3 cannot appear in any other combination. As they have filled 3 bonds (1-2,1-3,1-5) and (3-2,3-1,3-4). I want to find the maximum number of such combinations taking 3 atoms at a time and then 4 at a time, seperately.

Thank you in advance !!