How many labellings are there for a tree on 7 vertices?
$begingroup$
I know that Cayleys formula tells us there are $7^5=16807$ unique labelled trees. I also know the 11 trees that form these 16807 different variations.
What I can't calculate is how many of each type of tree there are. If we have a tree where every vertex has order 1 except one vertex which has order 6, then clearly we can only have 7 unique possible labelled trees for this tree.
However when I investigate the tree which has degree sequence ${1,1,1,1,1,2,5}$ I do not know how to calculate how many labelled trees this has.
graph-theory trees
edited Mar 12 '18 at 17:08
Parcly Taxel
41.8k1372101
asked Mar 12 '18 at 16:37
peter rocherpeter rocher
277
$endgroup$
add a comment |
$begingroup$
I know that Cayleys formula tells us there are $7^5=16807$ unique labelled trees. I also know the 11 trees that form these 16807 different variations.
What I can't calculate is how many of each type of tree there are. If we have a tree where every vertex has order 1 except one vertex which has order 6, then clearly we can only have 7 unique possible labelled trees for this tree.
However when I investigate the tree which has degree sequence ${1,1,1,1,1,2,5}$ I do not know how to calculate how many labelled trees this has.
graph-theory trees
edited Mar 12 '18 at 17:08
Parcly Taxel
41.8k1372101
asked Mar 12 '18 at 16:37
peter rocherpeter rocher
277
$endgroup$
$begingroup$
I believe it to be 210, as the vertex with order 5 has 7 possibilities, the connected vertex with order 2 - we have 6 choices. Then we have 4 like vertices all connected to our 'root'; and one unique vertex, which we now have 5 choices for. 7*6*5 = 210? Is this correct?
$endgroup$
– peter rocher
Mar 12 '18 at 16:47
$begingroup$
By 'order' do you mean 'degree'? In which case, it seems like you are asking how many trees a degree sequence has. For example, [3, 3, 2, 1, 1, 1, 1] has (at least) two trees : 2(3(1)(1))(3(1)(1)) and 3(2(1)(1))(2(1))(1)
$endgroup$
– gilleain
Mar 12 '18 at 16:54
$begingroup$
You are correct; that tree has 210 labellings. See my complete answer for more.
$endgroup$
– Parcly Taxel
Mar 12 '18 at 17:17
add a comment |
$begingroup$
I know that Cayleys formula tells us there are $7^5=16807$ unique labelled trees. I also know the 11 trees that form these 16807 different variations.
What I can't calculate is how many of each type of tree there are. If we have a tree where every vertex has order 1 except one vertex which has order 6, then clearly we can only have 7 unique possible labelled trees for this tree.
However when I investigate the tree which has degree sequence ${1,1,1,1,1,2,5}$ I do not know how to calculate how many labelled trees this has.
graph-theory trees
edited Mar 12 '18 at 17:08
Parcly Taxel
41.8k1372101
asked Mar 12 '18 at 16:37
peter rocherpeter rocher
277
$endgroup$
I know that Cayleys formula tells us there are $7^5=16807$ unique labelled trees. I also know the 11 trees that form these 16807 different variations.
What I can't calculate is how many of each type of tree there are. If we have a tree where every vertex has order 1 except one vertex which has order 6, then clearly we can only have 7 unique possible labelled trees for this tree.
However when I investigate the tree which has degree sequence ${1,1,1,1,1,2,5}$ I do not know how to calculate how many labelled trees this has.
graph-theory trees
graph-theory trees
edited Mar 12 '18 at 17:08
Parcly Taxel
41.8k1372101
asked Mar 12 '18 at 16:37
peter rocherpeter rocher
277
edited Mar 12 '18 at 17:08
Parcly Taxel
41.8k1372101
asked Mar 12 '18 at 16:37
peter rocherpeter rocher
277
edited Mar 12 '18 at 17:08
Parcly Taxel
41.8k1372101
edited Mar 12 '18 at 17:08
Parcly Taxel
41.8k1372101
edited Mar 12 '18 at 17:08
Parcly Taxel
41.8k1372101
41.8k1372101
asked Mar 12 '18 at 16:37
peter rocherpeter rocher
277
asked Mar 12 '18 at 16:37
peter rocherpeter rocher
277
asked Mar 12 '18 at 16:37
peter rocherpeter rocher
277
277
$begingroup$
I believe it to be 210, as the vertex with order 5 has 7 possibilities, the connected vertex with order 2 - we have 6 choices. Then we have 4 like vertices all connected to our 'root'; and one unique vertex, which we now have 5 choices for. 7*6*5 = 210? Is this correct?
$endgroup$
– peter rocher
Mar 12 '18 at 16:47
$begingroup$
By 'order' do you mean 'degree'? In which case, it seems like you are asking how many trees a degree sequence has. For example, [3, 3, 2, 1, 1, 1, 1] has (at least) two trees : 2(3(1)(1))(3(1)(1)) and 3(2(1)(1))(2(1))(1)
$endgroup$
– gilleain
Mar 12 '18 at 16:54
$begingroup$
You are correct; that tree has 210 labellings. See my complete answer for more.
$endgroup$
– Parcly Taxel
Mar 12 '18 at 17:17
add a comment |
$begingroup$
I believe it to be 210, as the vertex with order 5 has 7 possibilities, the connected vertex with order 2 - we have 6 choices. Then we have 4 like vertices all connected to our 'root'; and one unique vertex, which we now have 5 choices for. 7*6*5 = 210? Is this correct?
$endgroup$
– peter rocher
Mar 12 '18 at 16:47
$begingroup$
By 'order' do you mean 'degree'? In which case, it seems like you are asking how many trees a degree sequence has. For example, [3, 3, 2, 1, 1, 1, 1] has (at least) two trees : 2(3(1)(1))(3(1)(1)) and 3(2(1)(1))(2(1))(1)
$endgroup$
– gilleain
Mar 12 '18 at 16:54
$begingroup$
You are correct; that tree has 210 labellings. See my complete answer for more.
$endgroup$
– Parcly Taxel
Mar 12 '18 at 17:17
$begingroup$
I believe it to be 210, as the vertex with order 5 has 7 possibilities, the connected vertex with order 2 - we have 6 choices. Then we have 4 like vertices all connected to our 'root'; and one unique vertex, which we now have 5 choices for. 7*6*5 = 210? Is this correct?
$endgroup$
– peter rocher
Mar 12 '18 at 16:47
$begingroup$
I believe it to be 210, as the vertex with order 5 has 7 possibilities, the connected vertex with order 2 - we have 6 choices. Then we have 4 like vertices all connected to our 'root'; and one unique vertex, which we now have 5 choices for. 7*6*5 = 210? Is this correct?
$endgroup$
– peter rocher
Mar 12 '18 at 16:47
$begingroup$
By 'order' do you mean 'degree'? In which case, it seems like you are asking how many trees a degree sequence has. For example, [3, 3, 2, 1, 1, 1, 1] has (at least) two trees : 2(3(1)(1))(3(1)(1)) and 3(2(1)(1))(2(1))(1)
$endgroup$
– gilleain
Mar 12 '18 at 16:54
$begingroup$
By 'order' do you mean 'degree'? In which case, it seems like you are asking how many trees a degree sequence has. For example, [3, 3, 2, 1, 1, 1, 1] has (at least) two trees : 2(3(1)(1))(3(1)(1)) and 3(2(1)(1))(2(1))(1)
$endgroup$
– gilleain
Mar 12 '18 at 16:54
$begingroup$
You are correct; that tree has 210 labellings. See my complete answer for more.
$endgroup$
– Parcly Taxel
Mar 12 '18 at 17:17
$begingroup$
You are correct; that tree has 210 labellings. See my complete answer for more.
$endgroup$
– Parcly Taxel
Mar 12 '18 at 17:17
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Any graph on $n$ vertices with $k$ automorphisms – ways its vertices can be mapped onto themselves to preserve the edges – has $frac{n!}k$ labellings. Applying this to the trees on seven vertices (the image below taken from Peter Steinbach's Field Guide to Simple Graphs, available on the OEIS under the links at A000055):
we see that the trees from left to right have the following numbers of automorphisms:
$$2,2,1,6,8,2,6,4,12,24,720$$
Dividing $7!=5040$ by each number gives the number of labellings of each of these trees:
$$2520,2520,5040,840,630,2520,840,1260,420,210,7$$
As expected, they add up to $7^5=16807$.
Finding the order of the automorphism group of a tree
As an example, take the second tree from the left. There is only one order-3 vertex, so it must stay fixed in any automorphism. Three paths radiate from this vertex – one of length 4 that must also stay fixed, and two of length 1 that can be swapped. Multiplying the numbers together gives two automorphisms.
For the rightmost star, while the central hub must stay fixed, the six spokes can be permuted in any order, yielding $6!=720$ automorphisms.
answered Mar 12 '18 at 17:07
Parcly TaxelParcly Taxel
41.8k1372101
$endgroup$
$begingroup$
Hi! I was wondering how you are able to know the number of automorphisms of a tree? I didn't study this in class, maybe can you give me some insights?
$endgroup$
– Marine Galantin
Jan 19 at 1:37
$begingroup$
@MarineGalantin This is mostly a matter of looking at the tree and finding its global symmetries, then zooming into branches in turn and finding their symmetries recursively, then multiplying the orders of the groups that fall out in that way.
$endgroup$
– Parcly Taxel
Jan 19 at 1:42
$begingroup$
Would you mind to do a concrete small example? If you have the time now or another time... I m not sure to understand. For example on the second tree (the path with horns) and on the last one, the star?
$endgroup$
– Marine Galantin
Jan 19 at 1:43
1
$begingroup$
@MarineGalantin see the bottom section of my edited answer.
$endgroup$
– Parcly Taxel
Jan 19 at 1:54
$begingroup$
Thank you a lot for the time and energy in editing this post.
$endgroup$
– Marine Galantin
Jan 19 at 2:02
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%2f2688083%2fhow-many-labellings-are-there-for-a-tree-on-7-vertices%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Any graph on $n$ vertices with $k$ automorphisms – ways its vertices can be mapped onto themselves to preserve the edges – has $frac{n!}k$ labellings. Applying this to the trees on seven vertices (the image below taken from Peter Steinbach's Field Guide to Simple Graphs, available on the OEIS under the links at A000055):
we see that the trees from left to right have the following numbers of automorphisms:
$$2,2,1,6,8,2,6,4,12,24,720$$
Dividing $7!=5040$ by each number gives the number of labellings of each of these trees:
$$2520,2520,5040,840,630,2520,840,1260,420,210,7$$
As expected, they add up to $7^5=16807$.
Finding the order of the automorphism group of a tree
As an example, take the second tree from the left. There is only one order-3 vertex, so it must stay fixed in any automorphism. Three paths radiate from this vertex – one of length 4 that must also stay fixed, and two of length 1 that can be swapped. Multiplying the numbers together gives two automorphisms.
For the rightmost star, while the central hub must stay fixed, the six spokes can be permuted in any order, yielding $6!=720$ automorphisms.
answered Mar 12 '18 at 17:07
Parcly TaxelParcly Taxel
41.8k1372101
$endgroup$
$begingroup$
Hi! I was wondering how you are able to know the number of automorphisms of a tree? I didn't study this in class, maybe can you give me some insights?
$endgroup$
– Marine Galantin
Jan 19 at 1:37
$begingroup$
@MarineGalantin This is mostly a matter of looking at the tree and finding its global symmetries, then zooming into branches in turn and finding their symmetries recursively, then multiplying the orders of the groups that fall out in that way.
$endgroup$
– Parcly Taxel
Jan 19 at 1:42
$begingroup$
Would you mind to do a concrete small example? If you have the time now or another time... I m not sure to understand. For example on the second tree (the path with horns) and on the last one, the star?
$endgroup$
– Marine Galantin
Jan 19 at 1:43
1
$begingroup$
@MarineGalantin see the bottom section of my edited answer.
$endgroup$
– Parcly Taxel
Jan 19 at 1:54
$begingroup$
Thank you a lot for the time and energy in editing this post.
$endgroup$
– Marine Galantin
Jan 19 at 2:02
add a comment |
$begingroup$
Any graph on $n$ vertices with $k$ automorphisms – ways its vertices can be mapped onto themselves to preserve the edges – has $frac{n!}k$ labellings. Applying this to the trees on seven vertices (the image below taken from Peter Steinbach's Field Guide to Simple Graphs, available on the OEIS under the links at A000055):
we see that the trees from left to right have the following numbers of automorphisms:
$$2,2,1,6,8,2,6,4,12,24,720$$
Dividing $7!=5040$ by each number gives the number of labellings of each of these trees:
$$2520,2520,5040,840,630,2520,840,1260,420,210,7$$
As expected, they add up to $7^5=16807$.
Finding the order of the automorphism group of a tree
As an example, take the second tree from the left. There is only one order-3 vertex, so it must stay fixed in any automorphism. Three paths radiate from this vertex – one of length 4 that must also stay fixed, and two of length 1 that can be swapped. Multiplying the numbers together gives two automorphisms.
For the rightmost star, while the central hub must stay fixed, the six spokes can be permuted in any order, yielding $6!=720$ automorphisms.
answered Mar 12 '18 at 17:07
Parcly TaxelParcly Taxel
41.8k1372101
$endgroup$
$begingroup$
Hi! I was wondering how you are able to know the number of automorphisms of a tree? I didn't study this in class, maybe can you give me some insights?
$endgroup$
– Marine Galantin
Jan 19 at 1:37
$begingroup$
@MarineGalantin This is mostly a matter of looking at the tree and finding its global symmetries, then zooming into branches in turn and finding their symmetries recursively, then multiplying the orders of the groups that fall out in that way.
$endgroup$
– Parcly Taxel
Jan 19 at 1:42
$begingroup$
Would you mind to do a concrete small example? If you have the time now or another time... I m not sure to understand. For example on the second tree (the path with horns) and on the last one, the star?
$endgroup$
– Marine Galantin
Jan 19 at 1:43
1
$begingroup$
@MarineGalantin see the bottom section of my edited answer.
$endgroup$
– Parcly Taxel
Jan 19 at 1:54
$begingroup$
Thank you a lot for the time and energy in editing this post.
$endgroup$
– Marine Galantin
Jan 19 at 2:02
add a comment |
$begingroup$
Any graph on $n$ vertices with $k$ automorphisms – ways its vertices can be mapped onto themselves to preserve the edges – has $frac{n!}k$ labellings. Applying this to the trees on seven vertices (the image below taken from Peter Steinbach's Field Guide to Simple Graphs, available on the OEIS under the links at A000055):
we see that the trees from left to right have the following numbers of automorphisms:
$$2,2,1,6,8,2,6,4,12,24,720$$
Dividing $7!=5040$ by each number gives the number of labellings of each of these trees:
$$2520,2520,5040,840,630,2520,840,1260,420,210,7$$
As expected, they add up to $7^5=16807$.
Finding the order of the automorphism group of a tree
As an example, take the second tree from the left. There is only one order-3 vertex, so it must stay fixed in any automorphism. Three paths radiate from this vertex – one of length 4 that must also stay fixed, and two of length 1 that can be swapped. Multiplying the numbers together gives two automorphisms.
For the rightmost star, while the central hub must stay fixed, the six spokes can be permuted in any order, yielding $6!=720$ automorphisms.
answered Mar 12 '18 at 17:07
Parcly TaxelParcly Taxel
41.8k1372101
$endgroup$
Any graph on $n$ vertices with $k$ automorphisms – ways its vertices can be mapped onto themselves to preserve the edges – has $frac{n!}k$ labellings. Applying this to the trees on seven vertices (the image below taken from Peter Steinbach's Field Guide to Simple Graphs, available on the OEIS under the links at A000055):
we see that the trees from left to right have the following numbers of automorphisms:
$$2,2,1,6,8,2,6,4,12,24,720$$
Dividing $7!=5040$ by each number gives the number of labellings of each of these trees:
$$2520,2520,5040,840,630,2520,840,1260,420,210,7$$
As expected, they add up to $7^5=16807$.
Finding the order of the automorphism group of a tree
As an example, take the second tree from the left. There is only one order-3 vertex, so it must stay fixed in any automorphism. Three paths radiate from this vertex – one of length 4 that must also stay fixed, and two of length 1 that can be swapped. Multiplying the numbers together gives two automorphisms.
For the rightmost star, while the central hub must stay fixed, the six spokes can be permuted in any order, yielding $6!=720$ automorphisms.
answered Mar 12 '18 at 17:07
Parcly TaxelParcly Taxel
41.8k1372101
edited Jan 19 at 1:54
answered Mar 12 '18 at 17:07
Parcly TaxelParcly Taxel
41.8k1372101
answered Mar 12 '18 at 17:07
Parcly TaxelParcly Taxel
41.8k1372101
answered Mar 12 '18 at 17:07
Parcly TaxelParcly Taxel
41.8k1372101
41.8k1372101
$begingroup$
Hi! I was wondering how you are able to know the number of automorphisms of a tree? I didn't study this in class, maybe can you give me some insights?
$endgroup$
– Marine Galantin
Jan 19 at 1:37
$begingroup$
@MarineGalantin This is mostly a matter of looking at the tree and finding its global symmetries, then zooming into branches in turn and finding their symmetries recursively, then multiplying the orders of the groups that fall out in that way.
$endgroup$
– Parcly Taxel
Jan 19 at 1:42
$begingroup$
Would you mind to do a concrete small example? If you have the time now or another time... I m not sure to understand. For example on the second tree (the path with horns) and on the last one, the star?
$endgroup$
– Marine Galantin
Jan 19 at 1:43
1
$begingroup$
@MarineGalantin see the bottom section of my edited answer.
$endgroup$
– Parcly Taxel
Jan 19 at 1:54
$begingroup$
Thank you a lot for the time and energy in editing this post.
$endgroup$
– Marine Galantin
Jan 19 at 2:02
add a comment |
$begingroup$
Hi! I was wondering how you are able to know the number of automorphisms of a tree? I didn't study this in class, maybe can you give me some insights?
$endgroup$
– Marine Galantin
Jan 19 at 1:37
$begingroup$
@MarineGalantin This is mostly a matter of looking at the tree and finding its global symmetries, then zooming into branches in turn and finding their symmetries recursively, then multiplying the orders of the groups that fall out in that way.
$endgroup$
– Parcly Taxel
Jan 19 at 1:42
$begingroup$
Would you mind to do a concrete small example? If you have the time now or another time... I m not sure to understand. For example on the second tree (the path with horns) and on the last one, the star?
$endgroup$
– Marine Galantin
Jan 19 at 1:43
1
$begingroup$
@MarineGalantin see the bottom section of my edited answer.
$endgroup$
– Parcly Taxel
Jan 19 at 1:54
$begingroup$
Thank you a lot for the time and energy in editing this post.
$endgroup$
– Marine Galantin
Jan 19 at 2:02
$begingroup$
Hi! I was wondering how you are able to know the number of automorphisms of a tree? I didn't study this in class, maybe can you give me some insights?
$endgroup$
– Marine Galantin
Jan 19 at 1:37
$begingroup$
Hi! I was wondering how you are able to know the number of automorphisms of a tree? I didn't study this in class, maybe can you give me some insights?
$endgroup$
– Marine Galantin
Jan 19 at 1:37
$begingroup$
@MarineGalantin This is mostly a matter of looking at the tree and finding its global symmetries, then zooming into branches in turn and finding their symmetries recursively, then multiplying the orders of the groups that fall out in that way.
$endgroup$
– Parcly Taxel
Jan 19 at 1:42
$begingroup$
@MarineGalantin This is mostly a matter of looking at the tree and finding its global symmetries, then zooming into branches in turn and finding their symmetries recursively, then multiplying the orders of the groups that fall out in that way.
$endgroup$
– Parcly Taxel
Jan 19 at 1:42
$begingroup$
Would you mind to do a concrete small example? If you have the time now or another time... I m not sure to understand. For example on the second tree (the path with horns) and on the last one, the star?
$endgroup$
– Marine Galantin
Jan 19 at 1:43
$begingroup$
Would you mind to do a concrete small example? If you have the time now or another time... I m not sure to understand. For example on the second tree (the path with horns) and on the last one, the star?
$endgroup$
– Marine Galantin
Jan 19 at 1:43
1
1
$begingroup$
@MarineGalantin see the bottom section of my edited answer.
$endgroup$
– Parcly Taxel
Jan 19 at 1:54
$begingroup$
@MarineGalantin see the bottom section of my edited answer.
$endgroup$
– Parcly Taxel
Jan 19 at 1:54
$begingroup$
Thank you a lot for the time and energy in editing this post.
$endgroup$
– Marine Galantin
Jan 19 at 2:02
$begingroup$
Thank you a lot for the time and energy in editing this post.
$endgroup$
– Marine Galantin
Jan 19 at 2:02
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%2f2688083%2fhow-many-labellings-are-there-for-a-tree-on-7-vertices%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
$begingroup$
I believe it to be 210, as the vertex with order 5 has 7 possibilities, the connected vertex with order 2 - we have 6 choices. Then we have 4 like vertices all connected to our 'root'; and one unique vertex, which we now have 5 choices for. 7*6*5 = 210? Is this correct?
$endgroup$
– peter rocher
Mar 12 '18 at 16:47
$begingroup$
By 'order' do you mean 'degree'? In which case, it seems like you are asking how many trees a degree sequence has. For example, [3, 3, 2, 1, 1, 1, 1] has (at least) two trees : 2(3(1)(1))(3(1)(1)) and 3(2(1)(1))(2(1))(1)
$endgroup$
– gilleain
Mar 12 '18 at 16:54
$begingroup$
You are correct; that tree has 210 labellings. See my complete answer for more.
$endgroup$
– Parcly Taxel
Mar 12 '18 at 17:17