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.

Assuming you have a set of nodes, how do you determine how many connections are needed to connect every node to every other node in the set?

Example input and output:

In   Out
<=1  0
2    1
3    3
4    6
5    10
6    15
share|improve this question

3 Answers 3

up vote 1 down vote accepted

Figured it out. The formula is:

x = n(n - 1) / 2
share|improve this answer

Here is what you want.$$\sum_{k=1}^{n-1}k=\frac{n(n-1)}{2}$$

share|improve this answer

If there are $n$ nodes, then this is called "$n$ choose $2$", and is equal to the number of $2$-element subsets of a set of $n$ elements. The Wikipedia article on binomial coefficients includes this and generalizations.

Since I started writing you discovered the correct formula. However, if you ever have a similar problem where you are trying to figure out a general form for the terms in a sequence from some initial values, a good tool is The On-Line Encyclopedia of Integer Sequences. In this case, entering 0,1,3,6,10,15 brings up a useful entry in which you can find the general form and references.

share|improve this answer
    
That link to oeis.org looks incredibly useful. I was actually looking for something like that, thanks! –  Jake Petroules Jul 18 '11 at 17:55

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.