Calculating interaction beween 100 objects with each other.

Question

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result would involve interaction of each light with 99 other lights. So I wondered if it could be considered a complete graph with 100 nodes. I tried the following calculation, since if we have one object, the number of interactions is 0, if two, then 2, if three then 6 etc. This amounts to the following sequence, 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, ... which I calculated to equal to $$T(n) = 2(T(n-1)+n)$$ but that equals to $$T(n) = O(2^n)$$ which is hard to believe because this number is so huge. If we cut a piece of paper in half and stacked it on top of each other that would span 13.4 billion light years so how could that equal interaction of only 100 point light sources in the scene? Am I thinking of this wrong or is my calculation incorrect at some point?

Answer 1

You are wrong, if there are three men they will have three interactions between them. interactions between A,B and C are AB, AC and BC because interactions AB and BA are considered same.

No. of interactions between $n$ persons can be calculated by simply using the formula $n\choose2$ because for interactions we will have to choose any two persons out of $n$ and it can be done in $^nC_2$ ways. $n\choose2$ can also be written as $\frac{n(n-1)}{2}$.

So the no. of interactions between $100$ persons is $100 \choose 2$$=4950$

Answer 2

If you are looking at counting edges amongst 100 nodes (ie., was there an interaction?), then Dheeraj Kumar is correct. However, if you are looking at it from a dynamical systems perspective, then it is computationally intractable to enumerate all the states. A dynamical systems approach helps to describe and predict how everything will interact. Suppose each vertex has a state in $\{0, 1\}$. You have $2^{n}$ possible states over which to enumerate. Over a complete graph, there is a lot of interaction on each time step. Over a cycle graph, there would be a lot less interaction.

Some more on graph dynamical systems: http://en.wikipedia.org/wiki/Graph_dynamical_system http://www.samsi.info/sites/default/files/samsi-05-dec-08.pdf