6
$\begingroup$

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
$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That link to oeis.org looks incredibly useful. I was actually looking for something like that, thanks! $\endgroup$ – Jake Petroules Jul 18 '11 at 17:55
6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Figured it out. The formula is:

x = n(n - 1) / 2
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.