Formula for the number of connections needed to connect every node in a set?
$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
combinatorics graph-theory
edited Jan 1 '12 at 3:46
J. M. is not a mathematician
61.1k5151290
asked Jul 18 '11 at 16:32
Jake PetroulesJake Petroules
17617
$endgroup$
add a comment |
$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
combinatorics graph-theory
edited Jan 1 '12 at 3:46
J. M. is not a mathematician
61.1k5151290
asked Jul 18 '11 at 16:32
Jake PetroulesJake Petroules
17617
$endgroup$
add a comment |
$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
combinatorics graph-theory
edited Jan 1 '12 at 3:46
J. M. is not a mathematician
61.1k5151290
asked Jul 18 '11 at 16:32
Jake PetroulesJake Petroules
17617
$endgroup$
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
combinatorics graph-theory
combinatorics graph-theory
edited Jan 1 '12 at 3:46
J. M. is not a mathematician
61.1k5151290
asked Jul 18 '11 at 16:32
Jake PetroulesJake Petroules
17617
edited Jan 1 '12 at 3:46
J. M. is not a mathematician
61.1k5151290
asked Jul 18 '11 at 16:32
Jake PetroulesJake Petroules
17617
edited Jan 1 '12 at 3:46
J. M. is not a mathematician
61.1k5151290
edited Jan 1 '12 at 3:46
J. M. is not a mathematician
61.1k5151290
edited Jan 1 '12 at 3:46
J. M. is not a mathematician
61.1k5151290
61.1k5151290
asked Jul 18 '11 at 16:32
Jake PetroulesJake Petroules
17617
asked Jul 18 '11 at 16:32
Jake PetroulesJake Petroules
17617
asked Jul 18 '11 at 16:32
Jake PetroulesJake Petroules
17617
17617
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$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.
answered Jul 18 '11 at 16:46
Jonas MeyerJonas Meyer
40.6k6146254
$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
add a comment |
$begingroup$
Here is what you want.$$sum_{k=1}^{n-1}k=frac{n(n-1)}{2}$$
answered Jul 18 '11 at 16:45
XiangXiang
478313
$endgroup$
add a comment |
$begingroup$
Figured it out. The formula is:
x = n(n - 1) / 2
answered Jul 18 '11 at 16:40
Jake PetroulesJake Petroules
17617
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f52194%2fformula-for-the-number-of-connections-needed-to-connect-every-node-in-a-set%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered Jul 18 '11 at 16:46
Jonas MeyerJonas Meyer
40.6k6146254
$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
add a comment |
$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.
answered Jul 18 '11 at 16:46
Jonas MeyerJonas Meyer
40.6k6146254
$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
add a comment |
$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.
answered Jul 18 '11 at 16:46
Jonas MeyerJonas Meyer
40.6k6146254
$endgroup$
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 '11 at 16:46
Jonas MeyerJonas Meyer
40.6k6146254
answered Jul 18 '11 at 16:46
Jonas MeyerJonas Meyer
40.6k6146254
answered Jul 18 '11 at 16:46
Jonas MeyerJonas Meyer
40.6k6146254
answered Jul 18 '11 at 16:46
Jonas MeyerJonas Meyer
40.6k6146254
40.6k6146254
$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
add a comment |
$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
$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
$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
add a comment |
$begingroup$
Here is what you want.$$sum_{k=1}^{n-1}k=frac{n(n-1)}{2}$$
answered Jul 18 '11 at 16:45
XiangXiang
478313
$endgroup$
add a comment |
$begingroup$
Here is what you want.$$sum_{k=1}^{n-1}k=frac{n(n-1)}{2}$$
answered Jul 18 '11 at 16:45
XiangXiang
478313
$endgroup$
add a comment |
$begingroup$
Here is what you want.$$sum_{k=1}^{n-1}k=frac{n(n-1)}{2}$$
answered Jul 18 '11 at 16:45
XiangXiang
478313
$endgroup$
Here is what you want.$$sum_{k=1}^{n-1}k=frac{n(n-1)}{2}$$
answered Jul 18 '11 at 16:45
XiangXiang
478313
answered Jul 18 '11 at 16:45
XiangXiang
478313
answered Jul 18 '11 at 16:45
XiangXiang
478313
answered Jul 18 '11 at 16:45
XiangXiang
478313
478313
add a comment |
add a comment |
$begingroup$
Figured it out. The formula is:
x = n(n - 1) / 2
answered Jul 18 '11 at 16:40
Jake PetroulesJake Petroules
17617
$endgroup$
add a comment |
$begingroup$
Figured it out. The formula is:
x = n(n - 1) / 2
answered Jul 18 '11 at 16:40
Jake PetroulesJake Petroules
17617
$endgroup$
add a comment |
$begingroup$
Figured it out. The formula is:
x = n(n - 1) / 2
answered Jul 18 '11 at 16:40
Jake PetroulesJake Petroules
17617
$endgroup$
Figured it out. The formula is:
x = n(n - 1) / 2
answered Jul 18 '11 at 16:40
Jake PetroulesJake Petroules
17617
answered Jul 18 '11 at 16:40
Jake PetroulesJake Petroules
17617
answered Jul 18 '11 at 16:40
Jake PetroulesJake Petroules
17617
answered Jul 18 '11 at 16:40
Jake PetroulesJake Petroules
17617
17617
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f52194%2fformula-for-the-number-of-connections-needed-to-connect-every-node-in-a-set%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
