Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer
That link to looks incredibly useful. I was actually looking for something like that, thanks! – Jake Petroules Jul 18 '11 at 17:55

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

share|cite|improve this answer
up vote 1 down vote accepted

Figured it out. The formula is:

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

Your Answer


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.