Finding number of homeomorphically irreducible trees of degree $N$
There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree $10$. This is discussed in many places, such as here and is by itself a relatively easy to solve puzzle.
The most tricky part in that task, at least for me, is to decide if I have already found every such tree or something is missing. So here comes the question: how to calculate, how much homeomorphically irreducible trees of degree $N$ there are?
I've tried to find if such problem is already solved, but I was finding only various variants of Goodwill Hunting discussions. Is there a formula or algorithm for it? How to cope with that task?
trees
edited Jan 9 '17 at 10:03
Cettt
1,749621
asked May 9 '13 at 17:24
Danubian Sailor
12615
bumped to the homepage by Community♦ 2 days ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree $10$. This is discussed in many places, such as here and is by itself a relatively easy to solve puzzle.
The most tricky part in that task, at least for me, is to decide if I have already found every such tree or something is missing. So here comes the question: how to calculate, how much homeomorphically irreducible trees of degree $N$ there are?
I've tried to find if such problem is already solved, but I was finding only various variants of Goodwill Hunting discussions. Is there a formula or algorithm for it? How to cope with that task?
trees
edited Jan 9 '17 at 10:03
Cettt
1,749621
asked May 9 '13 at 17:24
Danubian Sailor
12615
bumped to the homepage by Community♦ 2 days ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
1
What do you mean by the "degree" of a tree? If you mean the maximum degree, there are infinitely many homeomorphically irreducible trees of maximum degree $3.$
– bof
Feb 10 '17 at 20:52
add a comment |
There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree $10$. This is discussed in many places, such as here and is by itself a relatively easy to solve puzzle.
The most tricky part in that task, at least for me, is to decide if I have already found every such tree or something is missing. So here comes the question: how to calculate, how much homeomorphically irreducible trees of degree $N$ there are?
I've tried to find if such problem is already solved, but I was finding only various variants of Goodwill Hunting discussions. Is there a formula or algorithm for it? How to cope with that task?
trees
edited Jan 9 '17 at 10:03
Cettt
1,749621
asked May 9 '13 at 17:24
Danubian Sailor
12615
There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree $10$. This is discussed in many places, such as here and is by itself a relatively easy to solve puzzle.
The most tricky part in that task, at least for me, is to decide if I have already found every such tree or something is missing. So here comes the question: how to calculate, how much homeomorphically irreducible trees of degree $N$ there are?
I've tried to find if such problem is already solved, but I was finding only various variants of Goodwill Hunting discussions. Is there a formula or algorithm for it? How to cope with that task?
trees
trees
edited Jan 9 '17 at 10:03
Cettt
1,749621
asked May 9 '13 at 17:24
Danubian Sailor
12615
edited Jan 9 '17 at 10:03
Cettt
1,749621
asked May 9 '13 at 17:24
Danubian Sailor
12615
edited Jan 9 '17 at 10:03
Cettt
1,749621
edited Jan 9 '17 at 10:03
Cettt
1,749621
edited Jan 9 '17 at 10:03
Cettt
1,749621
1,749621
asked May 9 '13 at 17:24
Danubian Sailor
12615
asked May 9 '13 at 17:24
Danubian Sailor
12615
asked May 9 '13 at 17:24
Danubian Sailor
12615
12615
bumped to the homepage by Community♦ 2 days ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
bumped to the homepage by Community♦ 2 days ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
1
What do you mean by the "degree" of a tree? If you mean the maximum degree, there are infinitely many homeomorphically irreducible trees of maximum degree $3.$
– bof
Feb 10 '17 at 20:52
add a comment |
1
What do you mean by the "degree" of a tree? If you mean the maximum degree, there are infinitely many homeomorphically irreducible trees of maximum degree $3.$
– bof
Feb 10 '17 at 20:52
1
1
What do you mean by the "degree" of a tree? If you mean the maximum degree, there are infinitely many homeomorphically irreducible trees of maximum degree $3.$
– bof
Feb 10 '17 at 20:52
What do you mean by the "degree" of a tree? If you mean the maximum degree, there are infinitely many homeomorphically irreducible trees of maximum degree $3.$
– bof
Feb 10 '17 at 20:52
add a comment |
2 Answers
2
active
oldest
votes
Yes there is, but I must admit that I don't fully understand it (http://oeis.org/A000014), as I am not a Mathematician. I found the number of trees for n=11 to be 14, and I discovered a way to grind through determining all trees using a method invented by me in under 4 minutes specifically for the task, but these mathematicians already came up with the formula.
I found the site with the formula from http://mathworld.wolfram.com/Series-ReducedTree.html
The method I used was fun in and of itself. I listed the trees for n=11 as follows:
1(10)
2(2,7); 2(3,6); 2(4,5)
3(2,1,5); 3(2,2,4); 3(2,3,3); 3(2,4,2); 3(3,1,4); 3(3,2,3)
4(2,1,1,3); 4(2,2,1,2)
H(0)3(2,2,3)
H(1)3(2,2,2)
Where H(1)3(2,2,2)=
>+<
^
H(1) means a hub from which only 1 branch is a direct end
a hub is a node from which >2 branches are not direct ends
Using this method I was able to easily deduce that there were 14 trees for n=11, and induce that there must be a formula.
answered Jun 20 '13 at 17:45
Seth
11
add a comment |
There is actually an easier way to do this; if we use notation such as {2,1,1,2,5} means:
">-<" with one of the nodes on the right side linked to five more nodes, we can list these as;
{1, 10}
{2, 1, 1, 7}
{2, 1, 1, 2, 5}
{2, 1, 1, 2, 2, 3}
{2, 1, 1, 2, 3, 2}
{2, 1, 1, 3, 4}
{2, 1, 1, 3, 2, 2}
{2, 1, 1, 4, 3}
{3, 1, 1, 6}
{3, 1, 1, 2, 4}
{3, 1, 1, 2, 2, 2}
{3, 1, 1, 3, 3}
{3, 1, 1, 4, 2}
{4, 1, 1, 5}
All possible trees except one have a {1, 1} group, meaning a [(1, 1),(1, 1)] tree with other trees substituted in for the two nodes. Also, I'm sure someone could write an algorithm for my method (if nobody has already discovered it.)
answered Jul 11 '13 at 10:47
Ryan Devanandan
563
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%2f386804%2ffinding-number-of-homeomorphically-irreducible-trees-of-degree-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Yes there is, but I must admit that I don't fully understand it (http://oeis.org/A000014), as I am not a Mathematician. I found the number of trees for n=11 to be 14, and I discovered a way to grind through determining all trees using a method invented by me in under 4 minutes specifically for the task, but these mathematicians already came up with the formula.
I found the site with the formula from http://mathworld.wolfram.com/Series-ReducedTree.html
The method I used was fun in and of itself. I listed the trees for n=11 as follows:
1(10)
2(2,7); 2(3,6); 2(4,5)
3(2,1,5); 3(2,2,4); 3(2,3,3); 3(2,4,2); 3(3,1,4); 3(3,2,3)
4(2,1,1,3); 4(2,2,1,2)
H(0)3(2,2,3)
H(1)3(2,2,2)
Where H(1)3(2,2,2)=
>+<
^
H(1) means a hub from which only 1 branch is a direct end
a hub is a node from which >2 branches are not direct ends
Using this method I was able to easily deduce that there were 14 trees for n=11, and induce that there must be a formula.
answered Jun 20 '13 at 17:45
Seth
11
add a comment |
Yes there is, but I must admit that I don't fully understand it (http://oeis.org/A000014), as I am not a Mathematician. I found the number of trees for n=11 to be 14, and I discovered a way to grind through determining all trees using a method invented by me in under 4 minutes specifically for the task, but these mathematicians already came up with the formula.
I found the site with the formula from http://mathworld.wolfram.com/Series-ReducedTree.html
The method I used was fun in and of itself. I listed the trees for n=11 as follows:
1(10)
2(2,7); 2(3,6); 2(4,5)
3(2,1,5); 3(2,2,4); 3(2,3,3); 3(2,4,2); 3(3,1,4); 3(3,2,3)
4(2,1,1,3); 4(2,2,1,2)
H(0)3(2,2,3)
H(1)3(2,2,2)
Where H(1)3(2,2,2)=
>+<
^
H(1) means a hub from which only 1 branch is a direct end
a hub is a node from which >2 branches are not direct ends
Using this method I was able to easily deduce that there were 14 trees for n=11, and induce that there must be a formula.
answered Jun 20 '13 at 17:45
Seth
11
add a comment |
Yes there is, but I must admit that I don't fully understand it (http://oeis.org/A000014), as I am not a Mathematician. I found the number of trees for n=11 to be 14, and I discovered a way to grind through determining all trees using a method invented by me in under 4 minutes specifically for the task, but these mathematicians already came up with the formula.
I found the site with the formula from http://mathworld.wolfram.com/Series-ReducedTree.html
The method I used was fun in and of itself. I listed the trees for n=11 as follows:
1(10)
2(2,7); 2(3,6); 2(4,5)
3(2,1,5); 3(2,2,4); 3(2,3,3); 3(2,4,2); 3(3,1,4); 3(3,2,3)
4(2,1,1,3); 4(2,2,1,2)
H(0)3(2,2,3)
H(1)3(2,2,2)
Where H(1)3(2,2,2)=
>+<
^
H(1) means a hub from which only 1 branch is a direct end
a hub is a node from which >2 branches are not direct ends
Using this method I was able to easily deduce that there were 14 trees for n=11, and induce that there must be a formula.
answered Jun 20 '13 at 17:45
Seth
11
Yes there is, but I must admit that I don't fully understand it (http://oeis.org/A000014), as I am not a Mathematician. I found the number of trees for n=11 to be 14, and I discovered a way to grind through determining all trees using a method invented by me in under 4 minutes specifically for the task, but these mathematicians already came up with the formula.
I found the site with the formula from http://mathworld.wolfram.com/Series-ReducedTree.html
The method I used was fun in and of itself. I listed the trees for n=11 as follows:
1(10)
2(2,7); 2(3,6); 2(4,5)
3(2,1,5); 3(2,2,4); 3(2,3,3); 3(2,4,2); 3(3,1,4); 3(3,2,3)
4(2,1,1,3); 4(2,2,1,2)
H(0)3(2,2,3)
H(1)3(2,2,2)
Where H(1)3(2,2,2)=
>+<
^
H(1) means a hub from which only 1 branch is a direct end
a hub is a node from which >2 branches are not direct ends
Using this method I was able to easily deduce that there were 14 trees for n=11, and induce that there must be a formula.
answered Jun 20 '13 at 17:45
Seth
11
edited Jun 20 '13 at 17:55
answered Jun 20 '13 at 17:45
Seth
11
answered Jun 20 '13 at 17:45
Seth
11
answered Jun 20 '13 at 17:45
Seth
11
11
add a comment |
add a comment |
There is actually an easier way to do this; if we use notation such as {2,1,1,2,5} means:
">-<" with one of the nodes on the right side linked to five more nodes, we can list these as;
{1, 10}
{2, 1, 1, 7}
{2, 1, 1, 2, 5}
{2, 1, 1, 2, 2, 3}
{2, 1, 1, 2, 3, 2}
{2, 1, 1, 3, 4}
{2, 1, 1, 3, 2, 2}
{2, 1, 1, 4, 3}
{3, 1, 1, 6}
{3, 1, 1, 2, 4}
{3, 1, 1, 2, 2, 2}
{3, 1, 1, 3, 3}
{3, 1, 1, 4, 2}
{4, 1, 1, 5}
All possible trees except one have a {1, 1} group, meaning a [(1, 1),(1, 1)] tree with other trees substituted in for the two nodes. Also, I'm sure someone could write an algorithm for my method (if nobody has already discovered it.)
answered Jul 11 '13 at 10:47
Ryan Devanandan
563
add a comment |
There is actually an easier way to do this; if we use notation such as {2,1,1,2,5} means:
">-<" with one of the nodes on the right side linked to five more nodes, we can list these as;
{1, 10}
{2, 1, 1, 7}
{2, 1, 1, 2, 5}
{2, 1, 1, 2, 2, 3}
{2, 1, 1, 2, 3, 2}
{2, 1, 1, 3, 4}
{2, 1, 1, 3, 2, 2}
{2, 1, 1, 4, 3}
{3, 1, 1, 6}
{3, 1, 1, 2, 4}
{3, 1, 1, 2, 2, 2}
{3, 1, 1, 3, 3}
{3, 1, 1, 4, 2}
{4, 1, 1, 5}
All possible trees except one have a {1, 1} group, meaning a [(1, 1),(1, 1)] tree with other trees substituted in for the two nodes. Also, I'm sure someone could write an algorithm for my method (if nobody has already discovered it.)
answered Jul 11 '13 at 10:47
Ryan Devanandan
563
add a comment |
There is actually an easier way to do this; if we use notation such as {2,1,1,2,5} means:
">-<" with one of the nodes on the right side linked to five more nodes, we can list these as;
{1, 10}
{2, 1, 1, 7}
{2, 1, 1, 2, 5}
{2, 1, 1, 2, 2, 3}
{2, 1, 1, 2, 3, 2}
{2, 1, 1, 3, 4}
{2, 1, 1, 3, 2, 2}
{2, 1, 1, 4, 3}
{3, 1, 1, 6}
{3, 1, 1, 2, 4}
{3, 1, 1, 2, 2, 2}
{3, 1, 1, 3, 3}
{3, 1, 1, 4, 2}
{4, 1, 1, 5}
All possible trees except one have a {1, 1} group, meaning a [(1, 1),(1, 1)] tree with other trees substituted in for the two nodes. Also, I'm sure someone could write an algorithm for my method (if nobody has already discovered it.)
answered Jul 11 '13 at 10:47
Ryan Devanandan
563
There is actually an easier way to do this; if we use notation such as {2,1,1,2,5} means:
">-<" with one of the nodes on the right side linked to five more nodes, we can list these as;
{1, 10}
{2, 1, 1, 7}
{2, 1, 1, 2, 5}
{2, 1, 1, 2, 2, 3}
{2, 1, 1, 2, 3, 2}
{2, 1, 1, 3, 4}
{2, 1, 1, 3, 2, 2}
{2, 1, 1, 4, 3}
{3, 1, 1, 6}
{3, 1, 1, 2, 4}
{3, 1, 1, 2, 2, 2}
{3, 1, 1, 3, 3}
{3, 1, 1, 4, 2}
{4, 1, 1, 5}
All possible trees except one have a {1, 1} group, meaning a [(1, 1),(1, 1)] tree with other trees substituted in for the two nodes. Also, I'm sure someone could write an algorithm for my method (if nobody has already discovered it.)
answered Jul 11 '13 at 10:47
Ryan Devanandan
563
answered Jul 11 '13 at 10:47
Ryan Devanandan
563
answered Jul 11 '13 at 10:47
Ryan Devanandan
563
answered Jul 11 '13 at 10:47
Ryan Devanandan
563
563
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f386804%2ffinding-number-of-homeomorphically-irreducible-trees-of-degree-n%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
1
What do you mean by the "degree" of a tree? If you mean the maximum degree, there are infinitely many homeomorphically irreducible trees of maximum degree $3.$
– bof
Feb 10 '17 at 20:52