Mixing
Find the number of trees on $2m$ given vertices in which all vertices have degree $1$ or $3$.
$begingroup$
Problem: Find the number of trees on $2m$ given vertices in which all vertices have degree $1$ or $3$.
My attempt: We know that for a tree $T$, we have $2(n-1) = sum _ { v in T } d ( v )$, with $n$ the number of vertices and $d(v)$ the degree of a vertex $v$. We can call $n_k$ the number of vertices of degree $k$. Hence we have that $$2(n_1+n_3-1)=n_1+3n_3$$
and $$2m=n_1+n_3$$.
From this we can conclude that either $n_1$ and $n_3$ are both even, or both odd. Now we also now that $n_3=n_1-2$. One can easily check an example, with $n_1=3, n_3=3-2=1, n_1+n_3=2cdot 2$, we do have a star graph with 3 leaves and a center of degree 3.
My question: now I have a formula to draw such trees, but I don't have the number of trees for a given $2m$ vertices. Maybe I could calculate the number of pairs $(n_1, n_3)$ such that the sum is even. Can someone help me conclude?
combinatorics discrete-mathematics graph-theory trees
edited Jan 26 at 1:28
darij grinberg
11.1k33167
asked Jan 20 at 13:39
NotAbelianGroupNotAbelianGroup
18211
$endgroup$
add a comment |
$begingroup$
Problem: Find the number of trees on $2m$ given vertices in which all vertices have degree $1$ or $3$.
My attempt: We know that for a tree $T$, we have $2(n-1) = sum _ { v in T } d ( v )$, with $n$ the number of vertices and $d(v)$ the degree of a vertex $v$. We can call $n_k$ the number of vertices of degree $k$. Hence we have that $$2(n_1+n_3-1)=n_1+3n_3$$
and $$2m=n_1+n_3$$.
From this we can conclude that either $n_1$ and $n_3$ are both even, or both odd. Now we also now that $n_3=n_1-2$. One can easily check an example, with $n_1=3, n_3=3-2=1, n_1+n_3=2cdot 2$, we do have a star graph with 3 leaves and a center of degree 3.
My question: now I have a formula to draw such trees, but I don't have the number of trees for a given $2m$ vertices. Maybe I could calculate the number of pairs $(n_1, n_3)$ such that the sum is even. Can someone help me conclude?
combinatorics discrete-mathematics graph-theory trees
edited Jan 26 at 1:28
darij grinberg
11.1k33167
asked Jan 20 at 13:39
NotAbelianGroupNotAbelianGroup
18211
$endgroup$
add a comment |
$begingroup$
Problem: Find the number of trees on $2m$ given vertices in which all vertices have degree $1$ or $3$.
My attempt: We know that for a tree $T$, we have $2(n-1) = sum _ { v in T } d ( v )$, with $n$ the number of vertices and $d(v)$ the degree of a vertex $v$. We can call $n_k$ the number of vertices of degree $k$. Hence we have that $$2(n_1+n_3-1)=n_1+3n_3$$
and $$2m=n_1+n_3$$.
From this we can conclude that either $n_1$ and $n_3$ are both even, or both odd. Now we also now that $n_3=n_1-2$. One can easily check an example, with $n_1=3, n_3=3-2=1, n_1+n_3=2cdot 2$, we do have a star graph with 3 leaves and a center of degree 3.
My question: now I have a formula to draw such trees, but I don't have the number of trees for a given $2m$ vertices. Maybe I could calculate the number of pairs $(n_1, n_3)$ such that the sum is even. Can someone help me conclude?
combinatorics discrete-mathematics graph-theory trees
edited Jan 26 at 1:28
darij grinberg
11.1k33167
asked Jan 20 at 13:39
NotAbelianGroupNotAbelianGroup
18211
$endgroup$
Problem: Find the number of trees on $2m$ given vertices in which all vertices have degree $1$ or $3$.
My attempt: We know that for a tree $T$, we have $2(n-1) = sum _ { v in T } d ( v )$, with $n$ the number of vertices and $d(v)$ the degree of a vertex $v$. We can call $n_k$ the number of vertices of degree $k$. Hence we have that $$2(n_1+n_3-1)=n_1+3n_3$$
and $$2m=n_1+n_3$$.
From this we can conclude that either $n_1$ and $n_3$ are both even, or both odd. Now we also now that $n_3=n_1-2$. One can easily check an example, with $n_1=3, n_3=3-2=1, n_1+n_3=2cdot 2$, we do have a star graph with 3 leaves and a center of degree 3.
My question: now I have a formula to draw such trees, but I don't have the number of trees for a given $2m$ vertices. Maybe I could calculate the number of pairs $(n_1, n_3)$ such that the sum is even. Can someone help me conclude?
combinatorics discrete-mathematics graph-theory trees
combinatorics discrete-mathematics graph-theory trees
edited Jan 26 at 1:28
darij grinberg
11.1k33167
asked Jan 20 at 13:39
NotAbelianGroupNotAbelianGroup
18211
edited Jan 26 at 1:28
darij grinberg
11.1k33167
asked Jan 20 at 13:39
NotAbelianGroupNotAbelianGroup
18211
edited Jan 26 at 1:28
darij grinberg
11.1k33167
edited Jan 26 at 1:28
darij grinberg
11.1k33167
edited Jan 26 at 1:28
darij grinberg
11.1k33167
11.1k33167
asked Jan 20 at 13:39
NotAbelianGroupNotAbelianGroup
18211
asked Jan 20 at 13:39
NotAbelianGroupNotAbelianGroup
18211
asked Jan 20 at 13:39
NotAbelianGroupNotAbelianGroup
18211
18211
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Using Pruefer codes we have that the leaves of degree one do not
appear in the code at all. Therefore the code consists of two
appearances of all nodes of degree three. As the length of the code is
$2m-2$ there are $m-1$ such nodes. Hence we choose these, and select
two slots for each in turn, proceeding in order. This yields
$${2mchoose m-1} frac{(2m-2)!}{2^{m-1}}.$$
This gives the sequence
$$1, 4, 90, 5040, 529200, 89812800, 22475653200,
\ 7791559776000, 3576325937184000, 2100278686746240000, ldots$$
which points us to OEIS A274056 where these
values are confirmed.
answered Jan 20 at 15:02
Marko RiedelMarko Riedel
40.6k339109
$endgroup$
$begingroup$
Could you explain $frac { ( 2 m - 2 ) ! } { 2 ^ { m - 1 } }$? If I try to identify, $( 2 m - 2 ) !$ is the number of permutation in the Pruefer but what is $2^{m-1}$? And why are we dividing $( 2 m - 2 ) !$?
$endgroup$
– NotAbelianGroup
Jan 21 at 15:49
$begingroup$
Simpler perhaps: There is also an explicit formula for the number of trees on $n$ vertices $1,2,ldots,n$ such that these vertices have degrees $d_1, d_2, ldots, d_n$, respectively: Namely, this number is $dfrac{left(n-2right)!}{left(d_1-1right)! left(d_2-1right)! cdots left(d_n-1right)!}$ (assuming that $n geq 2$). This formula can be easily proven by induction if you don't like the Prüfer code. Now, we can use this formula to see that the number of trees on $2m$ vertices $1,2,ldots,2m$ such that these vertices have degrees $1,1,ldots,1,3,3,ldots,3$, respectively ...
$endgroup$
– darij grinberg
Jan 26 at 1:31
$begingroup$
(with $m+1$ times $1$ and $m-1$ times $3$), is $dfrac{left(2m-2right)!}{left(1-1right)!^{m+1} left(3-1right)!^{m-1}} = dfrac{left(2m-2right)!}{1^{m+1} 2^{m-1}} = dfrac{left(2m-2right)!}{2^{m-1}}$. But this counts only those trees whose first $m+1$ vertices $1,2,ldots,m+1$ have degree $1$ and whose last $m-1$ vertices $m+2,m+3,ldots,2m$ have degree $3$. Since you want to count all trees having $m+1$ vertices of degree $1$ and $m-1$ vertices of degree $3$, you need to multiply this result by $dbinom{2m}{m+1}$, since that is the number of ways to choose $m+1$ out of $2m$ given ...
$endgroup$
– darij grinberg
Jan 26 at 1:33
$begingroup$
... vertices. (I am using the fact that if a tree on $2m$ vertices has only vertices of degrees $1$ and $3$, then it has exactly $m+1$ vertices of degree $1$ and exactly $m-1$ vertices of degree $3$. This is because in any tree, the sum of the degrees of all vertices is twice the number of edges, but the latter number is the number of vertices minus $1$.)
$endgroup$
– darij grinberg
Jan 26 at 1:43
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%2f3080589%2ffind-the-number-of-trees-on-2m-given-vertices-in-which-all-vertices-have-degre%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$
Using Pruefer codes we have that the leaves of degree one do not
appear in the code at all. Therefore the code consists of two
appearances of all nodes of degree three. As the length of the code is
$2m-2$ there are $m-1$ such nodes. Hence we choose these, and select
two slots for each in turn, proceeding in order. This yields
$${2mchoose m-1} frac{(2m-2)!}{2^{m-1}}.$$
This gives the sequence
$$1, 4, 90, 5040, 529200, 89812800, 22475653200,
\ 7791559776000, 3576325937184000, 2100278686746240000, ldots$$
which points us to OEIS A274056 where these
values are confirmed.
answered Jan 20 at 15:02
Marko RiedelMarko Riedel
40.6k339109
$endgroup$
$begingroup$
Could you explain $frac { ( 2 m - 2 ) ! } { 2 ^ { m - 1 } }$? If I try to identify, $( 2 m - 2 ) !$ is the number of permutation in the Pruefer but what is $2^{m-1}$? And why are we dividing $( 2 m - 2 ) !$?
$endgroup$
– NotAbelianGroup
Jan 21 at 15:49
$begingroup$
Simpler perhaps: There is also an explicit formula for the number of trees on $n$ vertices $1,2,ldots,n$ such that these vertices have degrees $d_1, d_2, ldots, d_n$, respectively: Namely, this number is $dfrac{left(n-2right)!}{left(d_1-1right)! left(d_2-1right)! cdots left(d_n-1right)!}$ (assuming that $n geq 2$). This formula can be easily proven by induction if you don't like the Prüfer code. Now, we can use this formula to see that the number of trees on $2m$ vertices $1,2,ldots,2m$ such that these vertices have degrees $1,1,ldots,1,3,3,ldots,3$, respectively ...
$endgroup$
– darij grinberg
Jan 26 at 1:31
$begingroup$
(with $m+1$ times $1$ and $m-1$ times $3$), is $dfrac{left(2m-2right)!}{left(1-1right)!^{m+1} left(3-1right)!^{m-1}} = dfrac{left(2m-2right)!}{1^{m+1} 2^{m-1}} = dfrac{left(2m-2right)!}{2^{m-1}}$. But this counts only those trees whose first $m+1$ vertices $1,2,ldots,m+1$ have degree $1$ and whose last $m-1$ vertices $m+2,m+3,ldots,2m$ have degree $3$. Since you want to count all trees having $m+1$ vertices of degree $1$ and $m-1$ vertices of degree $3$, you need to multiply this result by $dbinom{2m}{m+1}$, since that is the number of ways to choose $m+1$ out of $2m$ given ...
$endgroup$
– darij grinberg
Jan 26 at 1:33
$begingroup$
... vertices. (I am using the fact that if a tree on $2m$ vertices has only vertices of degrees $1$ and $3$, then it has exactly $m+1$ vertices of degree $1$ and exactly $m-1$ vertices of degree $3$. This is because in any tree, the sum of the degrees of all vertices is twice the number of edges, but the latter number is the number of vertices minus $1$.)
$endgroup$
– darij grinberg
Jan 26 at 1:43
add a comment |
$begingroup$
Using Pruefer codes we have that the leaves of degree one do not
appear in the code at all. Therefore the code consists of two
appearances of all nodes of degree three. As the length of the code is
$2m-2$ there are $m-1$ such nodes. Hence we choose these, and select
two slots for each in turn, proceeding in order. This yields
$${2mchoose m-1} frac{(2m-2)!}{2^{m-1}}.$$
This gives the sequence
$$1, 4, 90, 5040, 529200, 89812800, 22475653200,
\ 7791559776000, 3576325937184000, 2100278686746240000, ldots$$
which points us to OEIS A274056 where these
values are confirmed.
answered Jan 20 at 15:02
Marko RiedelMarko Riedel
40.6k339109
$endgroup$
$begingroup$
Could you explain $frac { ( 2 m - 2 ) ! } { 2 ^ { m - 1 } }$? If I try to identify, $( 2 m - 2 ) !$ is the number of permutation in the Pruefer but what is $2^{m-1}$? And why are we dividing $( 2 m - 2 ) !$?
$endgroup$
– NotAbelianGroup
Jan 21 at 15:49
$begingroup$
Simpler perhaps: There is also an explicit formula for the number of trees on $n$ vertices $1,2,ldots,n$ such that these vertices have degrees $d_1, d_2, ldots, d_n$, respectively: Namely, this number is $dfrac{left(n-2right)!}{left(d_1-1right)! left(d_2-1right)! cdots left(d_n-1right)!}$ (assuming that $n geq 2$). This formula can be easily proven by induction if you don't like the Prüfer code. Now, we can use this formula to see that the number of trees on $2m$ vertices $1,2,ldots,2m$ such that these vertices have degrees $1,1,ldots,1,3,3,ldots,3$, respectively ...
$endgroup$
– darij grinberg
Jan 26 at 1:31
$begingroup$
(with $m+1$ times $1$ and $m-1$ times $3$), is $dfrac{left(2m-2right)!}{left(1-1right)!^{m+1} left(3-1right)!^{m-1}} = dfrac{left(2m-2right)!}{1^{m+1} 2^{m-1}} = dfrac{left(2m-2right)!}{2^{m-1}}$. But this counts only those trees whose first $m+1$ vertices $1,2,ldots,m+1$ have degree $1$ and whose last $m-1$ vertices $m+2,m+3,ldots,2m$ have degree $3$. Since you want to count all trees having $m+1$ vertices of degree $1$ and $m-1$ vertices of degree $3$, you need to multiply this result by $dbinom{2m}{m+1}$, since that is the number of ways to choose $m+1$ out of $2m$ given ...
$endgroup$
– darij grinberg
Jan 26 at 1:33
$begingroup$
... vertices. (I am using the fact that if a tree on $2m$ vertices has only vertices of degrees $1$ and $3$, then it has exactly $m+1$ vertices of degree $1$ and exactly $m-1$ vertices of degree $3$. This is because in any tree, the sum of the degrees of all vertices is twice the number of edges, but the latter number is the number of vertices minus $1$.)
$endgroup$
– darij grinberg
Jan 26 at 1:43
add a comment |
$begingroup$
Using Pruefer codes we have that the leaves of degree one do not
appear in the code at all. Therefore the code consists of two
appearances of all nodes of degree three. As the length of the code is
$2m-2$ there are $m-1$ such nodes. Hence we choose these, and select
two slots for each in turn, proceeding in order. This yields
$${2mchoose m-1} frac{(2m-2)!}{2^{m-1}}.$$
This gives the sequence
$$1, 4, 90, 5040, 529200, 89812800, 22475653200,
\ 7791559776000, 3576325937184000, 2100278686746240000, ldots$$
which points us to OEIS A274056 where these
values are confirmed.
answered Jan 20 at 15:02
Marko RiedelMarko Riedel
40.6k339109
$endgroup$
Using Pruefer codes we have that the leaves of degree one do not
appear in the code at all. Therefore the code consists of two
appearances of all nodes of degree three. As the length of the code is
$2m-2$ there are $m-1$ such nodes. Hence we choose these, and select
two slots for each in turn, proceeding in order. This yields
$${2mchoose m-1} frac{(2m-2)!}{2^{m-1}}.$$
This gives the sequence
$$1, 4, 90, 5040, 529200, 89812800, 22475653200,
\ 7791559776000, 3576325937184000, 2100278686746240000, ldots$$
which points us to OEIS A274056 where these
values are confirmed.
answered Jan 20 at 15:02
Marko RiedelMarko Riedel
40.6k339109
answered Jan 20 at 15:02
Marko RiedelMarko Riedel
40.6k339109
answered Jan 20 at 15:02
Marko RiedelMarko Riedel
40.6k339109
answered Jan 20 at 15:02
Marko RiedelMarko Riedel
40.6k339109
40.6k339109
$begingroup$
Could you explain $frac { ( 2 m - 2 ) ! } { 2 ^ { m - 1 } }$? If I try to identify, $( 2 m - 2 ) !$ is the number of permutation in the Pruefer but what is $2^{m-1}$? And why are we dividing $( 2 m - 2 ) !$?
$endgroup$
– NotAbelianGroup
Jan 21 at 15:49
$begingroup$
Simpler perhaps: There is also an explicit formula for the number of trees on $n$ vertices $1,2,ldots,n$ such that these vertices have degrees $d_1, d_2, ldots, d_n$, respectively: Namely, this number is $dfrac{left(n-2right)!}{left(d_1-1right)! left(d_2-1right)! cdots left(d_n-1right)!}$ (assuming that $n geq 2$). This formula can be easily proven by induction if you don't like the Prüfer code. Now, we can use this formula to see that the number of trees on $2m$ vertices $1,2,ldots,2m$ such that these vertices have degrees $1,1,ldots,1,3,3,ldots,3$, respectively ...
$endgroup$
– darij grinberg
Jan 26 at 1:31
$begingroup$
(with $m+1$ times $1$ and $m-1$ times $3$), is $dfrac{left(2m-2right)!}{left(1-1right)!^{m+1} left(3-1right)!^{m-1}} = dfrac{left(2m-2right)!}{1^{m+1} 2^{m-1}} = dfrac{left(2m-2right)!}{2^{m-1}}$. But this counts only those trees whose first $m+1$ vertices $1,2,ldots,m+1$ have degree $1$ and whose last $m-1$ vertices $m+2,m+3,ldots,2m$ have degree $3$. Since you want to count all trees having $m+1$ vertices of degree $1$ and $m-1$ vertices of degree $3$, you need to multiply this result by $dbinom{2m}{m+1}$, since that is the number of ways to choose $m+1$ out of $2m$ given ...
$endgroup$
– darij grinberg
Jan 26 at 1:33
$begingroup$
... vertices. (I am using the fact that if a tree on $2m$ vertices has only vertices of degrees $1$ and $3$, then it has exactly $m+1$ vertices of degree $1$ and exactly $m-1$ vertices of degree $3$. This is because in any tree, the sum of the degrees of all vertices is twice the number of edges, but the latter number is the number of vertices minus $1$.)
$endgroup$
– darij grinberg
Jan 26 at 1:43
add a comment |
$begingroup$
Could you explain $frac { ( 2 m - 2 ) ! } { 2 ^ { m - 1 } }$? If I try to identify, $( 2 m - 2 ) !$ is the number of permutation in the Pruefer but what is $2^{m-1}$? And why are we dividing $( 2 m - 2 ) !$?
$endgroup$
– NotAbelianGroup
Jan 21 at 15:49
$begingroup$
Simpler perhaps: There is also an explicit formula for the number of trees on $n$ vertices $1,2,ldots,n$ such that these vertices have degrees $d_1, d_2, ldots, d_n$, respectively: Namely, this number is $dfrac{left(n-2right)!}{left(d_1-1right)! left(d_2-1right)! cdots left(d_n-1right)!}$ (assuming that $n geq 2$). This formula can be easily proven by induction if you don't like the Prüfer code. Now, we can use this formula to see that the number of trees on $2m$ vertices $1,2,ldots,2m$ such that these vertices have degrees $1,1,ldots,1,3,3,ldots,3$, respectively ...
$endgroup$
– darij grinberg
Jan 26 at 1:31
$begingroup$
(with $m+1$ times $1$ and $m-1$ times $3$), is $dfrac{left(2m-2right)!}{left(1-1right)!^{m+1} left(3-1right)!^{m-1}} = dfrac{left(2m-2right)!}{1^{m+1} 2^{m-1}} = dfrac{left(2m-2right)!}{2^{m-1}}$. But this counts only those trees whose first $m+1$ vertices $1,2,ldots,m+1$ have degree $1$ and whose last $m-1$ vertices $m+2,m+3,ldots,2m$ have degree $3$. Since you want to count all trees having $m+1$ vertices of degree $1$ and $m-1$ vertices of degree $3$, you need to multiply this result by $dbinom{2m}{m+1}$, since that is the number of ways to choose $m+1$ out of $2m$ given ...
$endgroup$
– darij grinberg
Jan 26 at 1:33
$begingroup$
... vertices. (I am using the fact that if a tree on $2m$ vertices has only vertices of degrees $1$ and $3$, then it has exactly $m+1$ vertices of degree $1$ and exactly $m-1$ vertices of degree $3$. This is because in any tree, the sum of the degrees of all vertices is twice the number of edges, but the latter number is the number of vertices minus $1$.)
$endgroup$
– darij grinberg
Jan 26 at 1:43
$begingroup$
Could you explain $frac { ( 2 m - 2 ) ! } { 2 ^ { m - 1 } }$? If I try to identify, $( 2 m - 2 ) !$ is the number of permutation in the Pruefer but what is $2^{m-1}$? And why are we dividing $( 2 m - 2 ) !$?
$endgroup$
– NotAbelianGroup
Jan 21 at 15:49
$begingroup$
Could you explain $frac { ( 2 m - 2 ) ! } { 2 ^ { m - 1 } }$? If I try to identify, $( 2 m - 2 ) !$ is the number of permutation in the Pruefer but what is $2^{m-1}$? And why are we dividing $( 2 m - 2 ) !$?
$endgroup$
– NotAbelianGroup
Jan 21 at 15:49
$begingroup$
Simpler perhaps: There is also an explicit formula for the number of trees on $n$ vertices $1,2,ldots,n$ such that these vertices have degrees $d_1, d_2, ldots, d_n$, respectively: Namely, this number is $dfrac{left(n-2right)!}{left(d_1-1right)! left(d_2-1right)! cdots left(d_n-1right)!}$ (assuming that $n geq 2$). This formula can be easily proven by induction if you don't like the Prüfer code. Now, we can use this formula to see that the number of trees on $2m$ vertices $1,2,ldots,2m$ such that these vertices have degrees $1,1,ldots,1,3,3,ldots,3$, respectively ...
$endgroup$
– darij grinberg
Jan 26 at 1:31
$begingroup$
Simpler perhaps: There is also an explicit formula for the number of trees on $n$ vertices $1,2,ldots,n$ such that these vertices have degrees $d_1, d_2, ldots, d_n$, respectively: Namely, this number is $dfrac{left(n-2right)!}{left(d_1-1right)! left(d_2-1right)! cdots left(d_n-1right)!}$ (assuming that $n geq 2$). This formula can be easily proven by induction if you don't like the Prüfer code. Now, we can use this formula to see that the number of trees on $2m$ vertices $1,2,ldots,2m$ such that these vertices have degrees $1,1,ldots,1,3,3,ldots,3$, respectively ...
$endgroup$
– darij grinberg
Jan 26 at 1:31
$begingroup$
(with $m+1$ times $1$ and $m-1$ times $3$), is $dfrac{left(2m-2right)!}{left(1-1right)!^{m+1} left(3-1right)!^{m-1}} = dfrac{left(2m-2right)!}{1^{m+1} 2^{m-1}} = dfrac{left(2m-2right)!}{2^{m-1}}$. But this counts only those trees whose first $m+1$ vertices $1,2,ldots,m+1$ have degree $1$ and whose last $m-1$ vertices $m+2,m+3,ldots,2m$ have degree $3$. Since you want to count all trees having $m+1$ vertices of degree $1$ and $m-1$ vertices of degree $3$, you need to multiply this result by $dbinom{2m}{m+1}$, since that is the number of ways to choose $m+1$ out of $2m$ given ...
$endgroup$
– darij grinberg
Jan 26 at 1:33
$begingroup$
(with $m+1$ times $1$ and $m-1$ times $3$), is $dfrac{left(2m-2right)!}{left(1-1right)!^{m+1} left(3-1right)!^{m-1}} = dfrac{left(2m-2right)!}{1^{m+1} 2^{m-1}} = dfrac{left(2m-2right)!}{2^{m-1}}$. But this counts only those trees whose first $m+1$ vertices $1,2,ldots,m+1$ have degree $1$ and whose last $m-1$ vertices $m+2,m+3,ldots,2m$ have degree $3$. Since you want to count all trees having $m+1$ vertices of degree $1$ and $m-1$ vertices of degree $3$, you need to multiply this result by $dbinom{2m}{m+1}$, since that is the number of ways to choose $m+1$ out of $2m$ given ...
$endgroup$
– darij grinberg
Jan 26 at 1:33
$begingroup$
... vertices. (I am using the fact that if a tree on $2m$ vertices has only vertices of degrees $1$ and $3$, then it has exactly $m+1$ vertices of degree $1$ and exactly $m-1$ vertices of degree $3$. This is because in any tree, the sum of the degrees of all vertices is twice the number of edges, but the latter number is the number of vertices minus $1$.)
$endgroup$
– darij grinberg
Jan 26 at 1:43
$begingroup$
... vertices. (I am using the fact that if a tree on $2m$ vertices has only vertices of degrees $1$ and $3$, then it has exactly $m+1$ vertices of degree $1$ and exactly $m-1$ vertices of degree $3$. This is because in any tree, the sum of the degrees of all vertices is twice the number of edges, but the latter number is the number of vertices minus $1$.)
$endgroup$
– darij grinberg
Jan 26 at 1:43
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%2f3080589%2ffind-the-number-of-trees-on-2m-given-vertices-in-which-all-vertices-have-degre%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
