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
$\begingroup$
$\endgroup$
J. M. ain't a mathematician
74.2k7 gold badges206 silver badges338 bronze badges
asked Jul 18, 2011 at 16:32
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
Here is what you want.$$\sum_{k=1}^{n-1}k=\frac{n(n-1)}{2}$$
$\begingroup$
$\endgroup$
1
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.
answered Jul 18, 2011 at 16:46
-
$\begingroup$ That link to oeis.org looks incredibly useful. I was actually looking for something like that, thanks! $\endgroup$ Jul 18, 2011 at 17:55
$\begingroup$
$\endgroup$
Figured it out. The formula is:
x = n(n - 1) / 2
answered Jul 18, 2011 at 16:40