Mixing
The number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$...
$begingroup$
Problem: What is the number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components?
Solution given by the professor Janos Pach: Take an arbitrary tree $T$ on the vertices $v _ { 1 } , ldots , v _ { k }$ . Any forest of $k$ components where $v _ { 1 } , ldots , v _ { k }$ are in distinct components, together with $T$ is a tree on $n$ vertices, and vica-versa. So, we need to compute how many labeled trees on $n$ vertices contain a given labeled subtree on a given subset of $k$ vertices. Using the previous exercise, we obtain $k n ^ { n - k - 1 }$.
Previous exercice: Let $T _ { 1 } , ldots , T _ { k }$ be trees on disjoint sets of points and $V = V left( T _ { 1 } right) cup ldots cup V left( T _ { k } right) .$ What is the number of labeled trees on $V$ containing $T _ { 1 } , ldots , T _ { k } ?$
Answer: $left| V left( T _ { 1 } right) right| ldots left| V left( T _ { k } right) right| cdot | V ( T ) | ^ { k - 2 }$
My question: I think I'm having difficulties in the understanding of the exercise. Is $T$ a tree with each vertices being a subtree? Are there $k$ subtrees in the forest? How manies vertices are there in a subtree? How does it relate numerically to the answer of the previous exercise?
combinatorics discrete-mathematics graph-theory trees
asked Jan 18 at 16:26
NotAbelianGroupNotAbelianGroup
18211
$endgroup$
add a comment |
$begingroup$
Problem: What is the number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components?
Solution given by the professor Janos Pach: Take an arbitrary tree $T$ on the vertices $v _ { 1 } , ldots , v _ { k }$ . Any forest of $k$ components where $v _ { 1 } , ldots , v _ { k }$ are in distinct components, together with $T$ is a tree on $n$ vertices, and vica-versa. So, we need to compute how many labeled trees on $n$ vertices contain a given labeled subtree on a given subset of $k$ vertices. Using the previous exercise, we obtain $k n ^ { n - k - 1 }$.
Previous exercice: Let $T _ { 1 } , ldots , T _ { k }$ be trees on disjoint sets of points and $V = V left( T _ { 1 } right) cup ldots cup V left( T _ { k } right) .$ What is the number of labeled trees on $V$ containing $T _ { 1 } , ldots , T _ { k } ?$
Answer: $left| V left( T _ { 1 } right) right| ldots left| V left( T _ { k } right) right| cdot | V ( T ) | ^ { k - 2 }$
My question: I think I'm having difficulties in the understanding of the exercise. Is $T$ a tree with each vertices being a subtree? Are there $k$ subtrees in the forest? How manies vertices are there in a subtree? How does it relate numerically to the answer of the previous exercise?
combinatorics discrete-mathematics graph-theory trees
asked Jan 18 at 16:26
NotAbelianGroupNotAbelianGroup
18211
$endgroup$
$begingroup$
@ThomasLesgourgues That's what I was thought, but then how do I compute with the previous result the total number of forests?
$endgroup$
– NotAbelianGroup
Jan 18 at 16:46
$begingroup$
@ThomasLesgourgues The professor doesn't properly define what $T$ is, but it appears to be the tree created in such a way that it goes through only one vertices of each tree of the forest. So by creating a path that goes through $v _ { 1 } , dots , v _ { k }$ we are linking all the trees without creating any cycle, so we get at the $T$, a tree linking all the trees.
$endgroup$
– NotAbelianGroup
Jan 18 at 16:54
$begingroup$
@ThomasLesgourgues I think it makes sense that $|V(T)|$ is equal to $n$ since $T$ is linking all of the $n$ vertices among every $T_i$.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:09
$begingroup$
That was actually my question in the main problem, $T$ has size $k$, not $n$. $T$ is not the forest plus some edges, $T$ is only built from the additionnal edges, so that $T$ plus the forest in the total tree. But in Previous problem I don't know if the definition of $T$ is the same. Could you clear this issue on definition, and then deletes these comments? they will be useless
$endgroup$
– Thomas Lesgourgues
Jan 18 at 17:12
$begingroup$
link Here is the solution of Previous problem. As you can see the professor doesn't precise what $T$ is. You are right $T$ has size $k$ but then I am getting even more confused how the formula applies.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:16
add a comment |
$begingroup$
Problem: What is the number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components?
Solution given by the professor Janos Pach: Take an arbitrary tree $T$ on the vertices $v _ { 1 } , ldots , v _ { k }$ . Any forest of $k$ components where $v _ { 1 } , ldots , v _ { k }$ are in distinct components, together with $T$ is a tree on $n$ vertices, and vica-versa. So, we need to compute how many labeled trees on $n$ vertices contain a given labeled subtree on a given subset of $k$ vertices. Using the previous exercise, we obtain $k n ^ { n - k - 1 }$.
Previous exercice: Let $T _ { 1 } , ldots , T _ { k }$ be trees on disjoint sets of points and $V = V left( T _ { 1 } right) cup ldots cup V left( T _ { k } right) .$ What is the number of labeled trees on $V$ containing $T _ { 1 } , ldots , T _ { k } ?$
Answer: $left| V left( T _ { 1 } right) right| ldots left| V left( T _ { k } right) right| cdot | V ( T ) | ^ { k - 2 }$
My question: I think I'm having difficulties in the understanding of the exercise. Is $T$ a tree with each vertices being a subtree? Are there $k$ subtrees in the forest? How manies vertices are there in a subtree? How does it relate numerically to the answer of the previous exercise?
combinatorics discrete-mathematics graph-theory trees
asked Jan 18 at 16:26
NotAbelianGroupNotAbelianGroup
18211
$endgroup$
Problem: What is the number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components?
Solution given by the professor Janos Pach: Take an arbitrary tree $T$ on the vertices $v _ { 1 } , ldots , v _ { k }$ . Any forest of $k$ components where $v _ { 1 } , ldots , v _ { k }$ are in distinct components, together with $T$ is a tree on $n$ vertices, and vica-versa. So, we need to compute how many labeled trees on $n$ vertices contain a given labeled subtree on a given subset of $k$ vertices. Using the previous exercise, we obtain $k n ^ { n - k - 1 }$.
Previous exercice: Let $T _ { 1 } , ldots , T _ { k }$ be trees on disjoint sets of points and $V = V left( T _ { 1 } right) cup ldots cup V left( T _ { k } right) .$ What is the number of labeled trees on $V$ containing $T _ { 1 } , ldots , T _ { k } ?$
Answer: $left| V left( T _ { 1 } right) right| ldots left| V left( T _ { k } right) right| cdot | V ( T ) | ^ { k - 2 }$
My question: I think I'm having difficulties in the understanding of the exercise. Is $T$ a tree with each vertices being a subtree? Are there $k$ subtrees in the forest? How manies vertices are there in a subtree? How does it relate numerically to the answer of the previous exercise?
combinatorics discrete-mathematics graph-theory trees
combinatorics discrete-mathematics graph-theory trees
asked Jan 18 at 16:26
NotAbelianGroupNotAbelianGroup
18211
asked Jan 18 at 16:26
NotAbelianGroupNotAbelianGroup
18211
edited Jan 18 at 16:34
NotAbelianGroup
asked Jan 18 at 16:26
NotAbelianGroupNotAbelianGroup
18211
asked Jan 18 at 16:26
NotAbelianGroupNotAbelianGroup
18211
asked Jan 18 at 16:26
NotAbelianGroupNotAbelianGroup
18211
18211
$begingroup$
@ThomasLesgourgues That's what I was thought, but then how do I compute with the previous result the total number of forests?
$endgroup$
– NotAbelianGroup
Jan 18 at 16:46
$begingroup$
@ThomasLesgourgues The professor doesn't properly define what $T$ is, but it appears to be the tree created in such a way that it goes through only one vertices of each tree of the forest. So by creating a path that goes through $v _ { 1 } , dots , v _ { k }$ we are linking all the trees without creating any cycle, so we get at the $T$, a tree linking all the trees.
$endgroup$
– NotAbelianGroup
Jan 18 at 16:54
$begingroup$
@ThomasLesgourgues I think it makes sense that $|V(T)|$ is equal to $n$ since $T$ is linking all of the $n$ vertices among every $T_i$.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:09
$begingroup$
That was actually my question in the main problem, $T$ has size $k$, not $n$. $T$ is not the forest plus some edges, $T$ is only built from the additionnal edges, so that $T$ plus the forest in the total tree. But in Previous problem I don't know if the definition of $T$ is the same. Could you clear this issue on definition, and then deletes these comments? they will be useless
$endgroup$
– Thomas Lesgourgues
Jan 18 at 17:12
$begingroup$
link Here is the solution of Previous problem. As you can see the professor doesn't precise what $T$ is. You are right $T$ has size $k$ but then I am getting even more confused how the formula applies.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:16
add a comment |
$begingroup$
@ThomasLesgourgues That's what I was thought, but then how do I compute with the previous result the total number of forests?
$endgroup$
– NotAbelianGroup
Jan 18 at 16:46
$begingroup$
@ThomasLesgourgues The professor doesn't properly define what $T$ is, but it appears to be the tree created in such a way that it goes through only one vertices of each tree of the forest. So by creating a path that goes through $v _ { 1 } , dots , v _ { k }$ we are linking all the trees without creating any cycle, so we get at the $T$, a tree linking all the trees.
$endgroup$
– NotAbelianGroup
Jan 18 at 16:54
$begingroup$
@ThomasLesgourgues I think it makes sense that $|V(T)|$ is equal to $n$ since $T$ is linking all of the $n$ vertices among every $T_i$.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:09
$begingroup$
That was actually my question in the main problem, $T$ has size $k$, not $n$. $T$ is not the forest plus some edges, $T$ is only built from the additionnal edges, so that $T$ plus the forest in the total tree. But in Previous problem I don't know if the definition of $T$ is the same. Could you clear this issue on definition, and then deletes these comments? they will be useless
$endgroup$
– Thomas Lesgourgues
Jan 18 at 17:12
$begingroup$
link Here is the solution of Previous problem. As you can see the professor doesn't precise what $T$ is. You are right $T$ has size $k$ but then I am getting even more confused how the formula applies.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:16
$begingroup$
@ThomasLesgourgues That's what I was thought, but then how do I compute with the previous result the total number of forests?
$endgroup$
– NotAbelianGroup
Jan 18 at 16:46
$begingroup$
@ThomasLesgourgues That's what I was thought, but then how do I compute with the previous result the total number of forests?
$endgroup$
– NotAbelianGroup
Jan 18 at 16:46
$begingroup$
@ThomasLesgourgues The professor doesn't properly define what $T$ is, but it appears to be the tree created in such a way that it goes through only one vertices of each tree of the forest. So by creating a path that goes through $v _ { 1 } , dots , v _ { k }$ we are linking all the trees without creating any cycle, so we get at the $T$, a tree linking all the trees.
$endgroup$
– NotAbelianGroup
Jan 18 at 16:54
$begingroup$
@ThomasLesgourgues The professor doesn't properly define what $T$ is, but it appears to be the tree created in such a way that it goes through only one vertices of each tree of the forest. So by creating a path that goes through $v _ { 1 } , dots , v _ { k }$ we are linking all the trees without creating any cycle, so we get at the $T$, a tree linking all the trees.
$endgroup$
– NotAbelianGroup
Jan 18 at 16:54
$begingroup$
@ThomasLesgourgues I think it makes sense that $|V(T)|$ is equal to $n$ since $T$ is linking all of the $n$ vertices among every $T_i$.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:09
$begingroup$
@ThomasLesgourgues I think it makes sense that $|V(T)|$ is equal to $n$ since $T$ is linking all of the $n$ vertices among every $T_i$.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:09
$begingroup$
That was actually my question in the main problem, $T$ has size $k$, not $n$. $T$ is not the forest plus some edges, $T$ is only built from the additionnal edges, so that $T$ plus the forest in the total tree. But in Previous problem I don't know if the definition of $T$ is the same. Could you clear this issue on definition, and then deletes these comments? they will be useless
$endgroup$
– Thomas Lesgourgues
Jan 18 at 17:12
$begingroup$
That was actually my question in the main problem, $T$ has size $k$, not $n$. $T$ is not the forest plus some edges, $T$ is only built from the additionnal edges, so that $T$ plus the forest in the total tree. But in Previous problem I don't know if the definition of $T$ is the same. Could you clear this issue on definition, and then deletes these comments? they will be useless
$endgroup$
– Thomas Lesgourgues
Jan 18 at 17:12
$begingroup$
link Here is the solution of Previous problem. As you can see the professor doesn't precise what $T$ is. You are right $T$ has size $k$ but then I am getting even more confused how the formula applies.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:16
$begingroup$
link Here is the solution of Previous problem. As you can see the professor doesn't precise what $T$ is. You are right $T$ has size $k$ but then I am getting even more confused how the formula applies.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:16
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Is $T$ a tree with each vertex being a subtree?
No quite; $T$ is a tree with vertex set ${1,2,dots,k}$.
Are there $k$ subtrees in the forest?
For each forest $F$ counted by $F(n,k)$, there are $k$ components, and each component is a subtree. However, there are more subtrees. For example, in the below forest, counted by $F(5,2)$, 1 - 3 is a subtree:
1 - 3 - 4
2 - 5
How many vertices are there in a subtree?
Each component in $F$ can have between $1$ and $n-k+1$ vertices.
How does this relate numerically to the previous exercise?
It does not.
Let $T$ be any tree on the vertex set ${1,2,dots,k}$; for example, you could just have $T$ be the line $1-2-dots-k$. The idea is that, if $F$ is a forest counted by $F(n,k)$, then adding the edges of $T$ to $F$ results in a new tree with vertices ${1,2,dots,n}$, let's call it $T'$, which contains $T$. Conversely, given any tree $T'$ which contains $T$, removing the edges in $T$ results in a forest with $k$ components such that ${1,2,dots,k}$ are in different components. This bijection shows that $F(n,k)$ is equal to the number of trees containing $T$.
How do we use the previous exercise to count trees on ${1,2,dots,n}$ containing $T$? Define $T_1, T_2,dots,T_{n-k+1}$ as follows:
$T_1$ is the tree $T$ on vertex set ${1,2,dots,k}$.
$T_2$ is a tree with no edges on the vertex set ${k+1}$.
$T_3$ is a tree with no edges on the vertex set ${k+2}$.
$vdots$
$T_{n-k+1}$ is a tree with no edges on the vertex set ${n}$.
Note that the union of the vertex sets for $T_1,T_2,dots,T_{n-k+1}$ is equal to ${1,2,dots,n}$, and a tree on ${1,2,dots,n}$ contains all of the $T_i$ if and only if it contains $T_1=T$, since any tree will trivially contain all of the trees $T_2,T_3,dots,T_{n-k+1}$. Using the theorem, you will get $kn^{n-k-1}$.
answered Jan 18 at 18:25
Mike EarnestMike Earnest
23.9k12051
$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%2f3078457%2fthe-number-fn-k-of-forests-on-the-vertex-set-n-having-k-components-and%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$
Is $T$ a tree with each vertex being a subtree?
No quite; $T$ is a tree with vertex set ${1,2,dots,k}$.
Are there $k$ subtrees in the forest?
For each forest $F$ counted by $F(n,k)$, there are $k$ components, and each component is a subtree. However, there are more subtrees. For example, in the below forest, counted by $F(5,2)$, 1 - 3 is a subtree:
1 - 3 - 4
2 - 5
How many vertices are there in a subtree?
Each component in $F$ can have between $1$ and $n-k+1$ vertices.
How does this relate numerically to the previous exercise?
It does not.
Let $T$ be any tree on the vertex set ${1,2,dots,k}$; for example, you could just have $T$ be the line $1-2-dots-k$. The idea is that, if $F$ is a forest counted by $F(n,k)$, then adding the edges of $T$ to $F$ results in a new tree with vertices ${1,2,dots,n}$, let's call it $T'$, which contains $T$. Conversely, given any tree $T'$ which contains $T$, removing the edges in $T$ results in a forest with $k$ components such that ${1,2,dots,k}$ are in different components. This bijection shows that $F(n,k)$ is equal to the number of trees containing $T$.
How do we use the previous exercise to count trees on ${1,2,dots,n}$ containing $T$? Define $T_1, T_2,dots,T_{n-k+1}$ as follows:
$T_1$ is the tree $T$ on vertex set ${1,2,dots,k}$.
$T_2$ is a tree with no edges on the vertex set ${k+1}$.
$T_3$ is a tree with no edges on the vertex set ${k+2}$.
$vdots$
$T_{n-k+1}$ is a tree with no edges on the vertex set ${n}$.
Note that the union of the vertex sets for $T_1,T_2,dots,T_{n-k+1}$ is equal to ${1,2,dots,n}$, and a tree on ${1,2,dots,n}$ contains all of the $T_i$ if and only if it contains $T_1=T$, since any tree will trivially contain all of the trees $T_2,T_3,dots,T_{n-k+1}$. Using the theorem, you will get $kn^{n-k-1}$.
answered Jan 18 at 18:25
Mike EarnestMike Earnest
23.9k12051
$endgroup$
add a comment |
$begingroup$
Is $T$ a tree with each vertex being a subtree?
No quite; $T$ is a tree with vertex set ${1,2,dots,k}$.
Are there $k$ subtrees in the forest?
For each forest $F$ counted by $F(n,k)$, there are $k$ components, and each component is a subtree. However, there are more subtrees. For example, in the below forest, counted by $F(5,2)$, 1 - 3 is a subtree:
1 - 3 - 4
2 - 5
How many vertices are there in a subtree?
Each component in $F$ can have between $1$ and $n-k+1$ vertices.
How does this relate numerically to the previous exercise?
It does not.
Let $T$ be any tree on the vertex set ${1,2,dots,k}$; for example, you could just have $T$ be the line $1-2-dots-k$. The idea is that, if $F$ is a forest counted by $F(n,k)$, then adding the edges of $T$ to $F$ results in a new tree with vertices ${1,2,dots,n}$, let's call it $T'$, which contains $T$. Conversely, given any tree $T'$ which contains $T$, removing the edges in $T$ results in a forest with $k$ components such that ${1,2,dots,k}$ are in different components. This bijection shows that $F(n,k)$ is equal to the number of trees containing $T$.
How do we use the previous exercise to count trees on ${1,2,dots,n}$ containing $T$? Define $T_1, T_2,dots,T_{n-k+1}$ as follows:
$T_1$ is the tree $T$ on vertex set ${1,2,dots,k}$.
$T_2$ is a tree with no edges on the vertex set ${k+1}$.
$T_3$ is a tree with no edges on the vertex set ${k+2}$.
$vdots$
$T_{n-k+1}$ is a tree with no edges on the vertex set ${n}$.
Note that the union of the vertex sets for $T_1,T_2,dots,T_{n-k+1}$ is equal to ${1,2,dots,n}$, and a tree on ${1,2,dots,n}$ contains all of the $T_i$ if and only if it contains $T_1=T$, since any tree will trivially contain all of the trees $T_2,T_3,dots,T_{n-k+1}$. Using the theorem, you will get $kn^{n-k-1}$.
answered Jan 18 at 18:25
Mike EarnestMike Earnest
23.9k12051
$endgroup$
add a comment |
$begingroup$
Is $T$ a tree with each vertex being a subtree?
No quite; $T$ is a tree with vertex set ${1,2,dots,k}$.
Are there $k$ subtrees in the forest?
For each forest $F$ counted by $F(n,k)$, there are $k$ components, and each component is a subtree. However, there are more subtrees. For example, in the below forest, counted by $F(5,2)$, 1 - 3 is a subtree:
1 - 3 - 4
2 - 5
How many vertices are there in a subtree?
Each component in $F$ can have between $1$ and $n-k+1$ vertices.
How does this relate numerically to the previous exercise?
It does not.
Let $T$ be any tree on the vertex set ${1,2,dots,k}$; for example, you could just have $T$ be the line $1-2-dots-k$. The idea is that, if $F$ is a forest counted by $F(n,k)$, then adding the edges of $T$ to $F$ results in a new tree with vertices ${1,2,dots,n}$, let's call it $T'$, which contains $T$. Conversely, given any tree $T'$ which contains $T$, removing the edges in $T$ results in a forest with $k$ components such that ${1,2,dots,k}$ are in different components. This bijection shows that $F(n,k)$ is equal to the number of trees containing $T$.
How do we use the previous exercise to count trees on ${1,2,dots,n}$ containing $T$? Define $T_1, T_2,dots,T_{n-k+1}$ as follows:
$T_1$ is the tree $T$ on vertex set ${1,2,dots,k}$.
$T_2$ is a tree with no edges on the vertex set ${k+1}$.
$T_3$ is a tree with no edges on the vertex set ${k+2}$.
$vdots$
$T_{n-k+1}$ is a tree with no edges on the vertex set ${n}$.
Note that the union of the vertex sets for $T_1,T_2,dots,T_{n-k+1}$ is equal to ${1,2,dots,n}$, and a tree on ${1,2,dots,n}$ contains all of the $T_i$ if and only if it contains $T_1=T$, since any tree will trivially contain all of the trees $T_2,T_3,dots,T_{n-k+1}$. Using the theorem, you will get $kn^{n-k-1}$.
answered Jan 18 at 18:25
Mike EarnestMike Earnest
23.9k12051
$endgroup$
Is $T$ a tree with each vertex being a subtree?
No quite; $T$ is a tree with vertex set ${1,2,dots,k}$.
Are there $k$ subtrees in the forest?
For each forest $F$ counted by $F(n,k)$, there are $k$ components, and each component is a subtree. However, there are more subtrees. For example, in the below forest, counted by $F(5,2)$, 1 - 3 is a subtree:
1 - 3 - 4
2 - 5
How many vertices are there in a subtree?
Each component in $F$ can have between $1$ and $n-k+1$ vertices.
How does this relate numerically to the previous exercise?
It does not.
Let $T$ be any tree on the vertex set ${1,2,dots,k}$; for example, you could just have $T$ be the line $1-2-dots-k$. The idea is that, if $F$ is a forest counted by $F(n,k)$, then adding the edges of $T$ to $F$ results in a new tree with vertices ${1,2,dots,n}$, let's call it $T'$, which contains $T$. Conversely, given any tree $T'$ which contains $T$, removing the edges in $T$ results in a forest with $k$ components such that ${1,2,dots,k}$ are in different components. This bijection shows that $F(n,k)$ is equal to the number of trees containing $T$.
How do we use the previous exercise to count trees on ${1,2,dots,n}$ containing $T$? Define $T_1, T_2,dots,T_{n-k+1}$ as follows:
$T_1$ is the tree $T$ on vertex set ${1,2,dots,k}$.
$T_2$ is a tree with no edges on the vertex set ${k+1}$.
$T_3$ is a tree with no edges on the vertex set ${k+2}$.
$vdots$
$T_{n-k+1}$ is a tree with no edges on the vertex set ${n}$.
Note that the union of the vertex sets for $T_1,T_2,dots,T_{n-k+1}$ is equal to ${1,2,dots,n}$, and a tree on ${1,2,dots,n}$ contains all of the $T_i$ if and only if it contains $T_1=T$, since any tree will trivially contain all of the trees $T_2,T_3,dots,T_{n-k+1}$. Using the theorem, you will get $kn^{n-k-1}$.
answered Jan 18 at 18:25
Mike EarnestMike Earnest
23.9k12051
answered Jan 18 at 18:25
Mike EarnestMike Earnest
23.9k12051
answered Jan 18 at 18:25
Mike EarnestMike Earnest
23.9k12051
answered Jan 18 at 18:25
Mike EarnestMike Earnest
23.9k12051
23.9k12051
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%2f3078457%2fthe-number-fn-k-of-forests-on-the-vertex-set-n-having-k-components-and%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$
@ThomasLesgourgues That's what I was thought, but then how do I compute with the previous result the total number of forests?
$endgroup$
– NotAbelianGroup
Jan 18 at 16:46
$begingroup$
@ThomasLesgourgues The professor doesn't properly define what $T$ is, but it appears to be the tree created in such a way that it goes through only one vertices of each tree of the forest. So by creating a path that goes through $v _ { 1 } , dots , v _ { k }$ we are linking all the trees without creating any cycle, so we get at the $T$, a tree linking all the trees.
$endgroup$
– NotAbelianGroup
Jan 18 at 16:54
$begingroup$
@ThomasLesgourgues I think it makes sense that $|V(T)|$ is equal to $n$ since $T$ is linking all of the $n$ vertices among every $T_i$.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:09
$begingroup$
That was actually my question in the main problem, $T$ has size $k$, not $n$. $T$ is not the forest plus some edges, $T$ is only built from the additionnal edges, so that $T$ plus the forest in the total tree. But in Previous problem I don't know if the definition of $T$ is the same. Could you clear this issue on definition, and then deletes these comments? they will be useless
$endgroup$
– Thomas Lesgourgues
Jan 18 at 17:12
$begingroup$
link Here is the solution of Previous problem. As you can see the professor doesn't precise what $T$ is. You are right $T$ has size $k$ but then I am getting even more confused how the formula applies.
$endgroup$
– NotAbelianGroup
Jan 18 at 17:16