Mixing
![Starting a multi core CPU as single core [closed]](https://lh3.googleusercontent.com/-yspgfz81fFw/AAAAAAAAAAI/AAAAAAAAD5o/7CFgAMaSHSE/s72-c/photo.jpg?sz=32)
Formulas for full m-ary trees
$begingroup$
I am studying for an upcoming Discrete Math exam, and the final section is on trees. I understand the theory, but some of the questions require memorizing several formulas for calculating the number of vertices, internal vertices, and leaves.
The professor mentioned that there are maybe just 2 formulas we should learn and algebraically derive the rest, but I am unsure which 2 I should memorize. Any help would be appreciated!
n vertices has i = (n – 1)/m internal vertices and l = [(m – 1)n +
1]/m leaves i internal vertices has n = mi + 1 vertices and l = (m –
1)i + 1 leaves l leaves has n = (ml – 1)/(m – 1) vertices and i = (l –
1)/(m – 1) internal vertices
Edit:
n = vertices
m = edges
discrete-mathematics graph-theory trees
asked Dec 6 '17 at 12:32
jdc220jdc220
287
$endgroup$
add a comment |
$begingroup$
I am studying for an upcoming Discrete Math exam, and the final section is on trees. I understand the theory, but some of the questions require memorizing several formulas for calculating the number of vertices, internal vertices, and leaves.
The professor mentioned that there are maybe just 2 formulas we should learn and algebraically derive the rest, but I am unsure which 2 I should memorize. Any help would be appreciated!
n vertices has i = (n – 1)/m internal vertices and l = [(m – 1)n +
1]/m leaves i internal vertices has n = mi + 1 vertices and l = (m –
1)i + 1 leaves l leaves has n = (ml – 1)/(m – 1) vertices and i = (l –
1)/(m – 1) internal vertices
Edit:
n = vertices
m = edges
discrete-mathematics graph-theory trees
asked Dec 6 '17 at 12:32
jdc220jdc220
287
$endgroup$
$begingroup$
Uhm... so regarding your course which include trees, you want us to give you the most important formulas... ? You will either have to provide a lot more detailed information on the content of the course or actually ask the teacher... We can guess "tree Theorems" for page up and page down, without coming close to what you want to know and even less find "the most important 2 of the course".
$endgroup$
– Ove Ahlman
Dec 6 '17 at 12:35
$begingroup$
Fair point, I have updated with all 6 formulas given.
$endgroup$
– jdc220
Dec 6 '17 at 12:45
$begingroup$
Your quote is missing context. What is $m$? Are you talking about an $m$-ary tree?
$endgroup$
– darij grinberg
Feb 3 at 5:40
$begingroup$
Good call. m = number of edges.
$endgroup$
– jdc220
Feb 3 at 14:59
add a comment |
$begingroup$
I am studying for an upcoming Discrete Math exam, and the final section is on trees. I understand the theory, but some of the questions require memorizing several formulas for calculating the number of vertices, internal vertices, and leaves.
The professor mentioned that there are maybe just 2 formulas we should learn and algebraically derive the rest, but I am unsure which 2 I should memorize. Any help would be appreciated!
n vertices has i = (n – 1)/m internal vertices and l = [(m – 1)n +
1]/m leaves i internal vertices has n = mi + 1 vertices and l = (m –
1)i + 1 leaves l leaves has n = (ml – 1)/(m – 1) vertices and i = (l –
1)/(m – 1) internal vertices
Edit:
n = vertices
m = edges
discrete-mathematics graph-theory trees
asked Dec 6 '17 at 12:32
jdc220jdc220
287
$endgroup$
I am studying for an upcoming Discrete Math exam, and the final section is on trees. I understand the theory, but some of the questions require memorizing several formulas for calculating the number of vertices, internal vertices, and leaves.
The professor mentioned that there are maybe just 2 formulas we should learn and algebraically derive the rest, but I am unsure which 2 I should memorize. Any help would be appreciated!
n vertices has i = (n – 1)/m internal vertices and l = [(m – 1)n +
1]/m leaves i internal vertices has n = mi + 1 vertices and l = (m –
1)i + 1 leaves l leaves has n = (ml – 1)/(m – 1) vertices and i = (l –
1)/(m – 1) internal vertices
Edit:
n = vertices
m = edges
discrete-mathematics graph-theory trees
discrete-mathematics graph-theory trees
asked Dec 6 '17 at 12:32
jdc220jdc220
287
asked Dec 6 '17 at 12:32
jdc220jdc220
287
edited Feb 3 at 14:57
jdc220
asked Dec 6 '17 at 12:32
jdc220jdc220
287
asked Dec 6 '17 at 12:32
jdc220jdc220
287
asked Dec 6 '17 at 12:32
jdc220jdc220
287
287
$begingroup$
Uhm... so regarding your course which include trees, you want us to give you the most important formulas... ? You will either have to provide a lot more detailed information on the content of the course or actually ask the teacher... We can guess "tree Theorems" for page up and page down, without coming close to what you want to know and even less find "the most important 2 of the course".
$endgroup$
– Ove Ahlman
Dec 6 '17 at 12:35
$begingroup$
Fair point, I have updated with all 6 formulas given.
$endgroup$
– jdc220
Dec 6 '17 at 12:45
$begingroup$
Your quote is missing context. What is $m$? Are you talking about an $m$-ary tree?
$endgroup$
– darij grinberg
Feb 3 at 5:40
$begingroup$
Good call. m = number of edges.
$endgroup$
– jdc220
Feb 3 at 14:59
add a comment |
$begingroup$
Uhm... so regarding your course which include trees, you want us to give you the most important formulas... ? You will either have to provide a lot more detailed information on the content of the course or actually ask the teacher... We can guess "tree Theorems" for page up and page down, without coming close to what you want to know and even less find "the most important 2 of the course".
$endgroup$
– Ove Ahlman
Dec 6 '17 at 12:35
$begingroup$
Fair point, I have updated with all 6 formulas given.
$endgroup$
– jdc220
Dec 6 '17 at 12:45
$begingroup$
Your quote is missing context. What is $m$? Are you talking about an $m$-ary tree?
$endgroup$
– darij grinberg
Feb 3 at 5:40
$begingroup$
Good call. m = number of edges.
$endgroup$
– jdc220
Feb 3 at 14:59
$begingroup$
Uhm... so regarding your course which include trees, you want us to give you the most important formulas... ? You will either have to provide a lot more detailed information on the content of the course or actually ask the teacher... We can guess "tree Theorems" for page up and page down, without coming close to what you want to know and even less find "the most important 2 of the course".
$endgroup$
– Ove Ahlman
Dec 6 '17 at 12:35
$begingroup$
Uhm... so regarding your course which include trees, you want us to give you the most important formulas... ? You will either have to provide a lot more detailed information on the content of the course or actually ask the teacher... We can guess "tree Theorems" for page up and page down, without coming close to what you want to know and even less find "the most important 2 of the course".
$endgroup$
– Ove Ahlman
Dec 6 '17 at 12:35
$begingroup$
Fair point, I have updated with all 6 formulas given.
$endgroup$
– jdc220
Dec 6 '17 at 12:45
$begingroup$
Fair point, I have updated with all 6 formulas given.
$endgroup$
– jdc220
Dec 6 '17 at 12:45
$begingroup$
Your quote is missing context. What is $m$? Are you talking about an $m$-ary tree?
$endgroup$
– darij grinberg
Feb 3 at 5:40
$begingroup$
Your quote is missing context. What is $m$? Are you talking about an $m$-ary tree?
$endgroup$
– darij grinberg
Feb 3 at 5:40
$begingroup$
Good call. m = number of edges.
$endgroup$
– jdc220
Feb 3 at 14:59
$begingroup$
Good call. m = number of edges.
$endgroup$
– jdc220
Feb 3 at 14:59
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Just memorise $n=mi+1$ and $l=(m-1)i+1$. The other formulae are just re-arrangements of these two.
For example, if you know $l$ and $m$ and you want to find $i$ and $n$ then
$l=(m-1)i+1 Rightarrow i=dfrac{l-1}{m-1}$
and
$n=mi+1 Rightarrow n=dfrac{m(l-1)}{m-1}+1=dfrac{ml-m+m-1}{m-1}=dfrac{ml-1}{m-1}$
answered Dec 6 '17 at 13:06
gandalf61gandalf61
9,293825
$endgroup$
$begingroup$
thank you! This is exactly what I was trying to figure out.
$endgroup$
– jdc220
Dec 6 '17 at 13:18
add a comment |
Your Answer
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%2f2553753%2fformulas-for-full-m-ary-trees%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$
Just memorise $n=mi+1$ and $l=(m-1)i+1$. The other formulae are just re-arrangements of these two.
For example, if you know $l$ and $m$ and you want to find $i$ and $n$ then
$l=(m-1)i+1 Rightarrow i=dfrac{l-1}{m-1}$
and
$n=mi+1 Rightarrow n=dfrac{m(l-1)}{m-1}+1=dfrac{ml-m+m-1}{m-1}=dfrac{ml-1}{m-1}$
answered Dec 6 '17 at 13:06
gandalf61gandalf61
9,293825
$endgroup$
$begingroup$
thank you! This is exactly what I was trying to figure out.
$endgroup$
– jdc220
Dec 6 '17 at 13:18
add a comment |
$begingroup$
Just memorise $n=mi+1$ and $l=(m-1)i+1$. The other formulae are just re-arrangements of these two.
For example, if you know $l$ and $m$ and you want to find $i$ and $n$ then
$l=(m-1)i+1 Rightarrow i=dfrac{l-1}{m-1}$
and
$n=mi+1 Rightarrow n=dfrac{m(l-1)}{m-1}+1=dfrac{ml-m+m-1}{m-1}=dfrac{ml-1}{m-1}$
answered Dec 6 '17 at 13:06
gandalf61gandalf61
9,293825
$endgroup$
$begingroup$
thank you! This is exactly what I was trying to figure out.
$endgroup$
– jdc220
Dec 6 '17 at 13:18
add a comment |
$begingroup$
Just memorise $n=mi+1$ and $l=(m-1)i+1$. The other formulae are just re-arrangements of these two.
For example, if you know $l$ and $m$ and you want to find $i$ and $n$ then
$l=(m-1)i+1 Rightarrow i=dfrac{l-1}{m-1}$
and
$n=mi+1 Rightarrow n=dfrac{m(l-1)}{m-1}+1=dfrac{ml-m+m-1}{m-1}=dfrac{ml-1}{m-1}$
answered Dec 6 '17 at 13:06
gandalf61gandalf61
9,293825
$endgroup$
Just memorise $n=mi+1$ and $l=(m-1)i+1$. The other formulae are just re-arrangements of these two.
For example, if you know $l$ and $m$ and you want to find $i$ and $n$ then
$l=(m-1)i+1 Rightarrow i=dfrac{l-1}{m-1}$
and
$n=mi+1 Rightarrow n=dfrac{m(l-1)}{m-1}+1=dfrac{ml-m+m-1}{m-1}=dfrac{ml-1}{m-1}$
answered Dec 6 '17 at 13:06
gandalf61gandalf61
9,293825
answered Dec 6 '17 at 13:06
gandalf61gandalf61
9,293825
answered Dec 6 '17 at 13:06
gandalf61gandalf61
9,293825
answered Dec 6 '17 at 13:06
gandalf61gandalf61
9,293825
9,293825
$begingroup$
thank you! This is exactly what I was trying to figure out.
$endgroup$
– jdc220
Dec 6 '17 at 13:18
add a comment |
$begingroup$
thank you! This is exactly what I was trying to figure out.
$endgroup$
– jdc220
Dec 6 '17 at 13:18
$begingroup$
thank you! This is exactly what I was trying to figure out.
$endgroup$
– jdc220
Dec 6 '17 at 13:18
$begingroup$
thank you! This is exactly what I was trying to figure out.
$endgroup$
– jdc220
Dec 6 '17 at 13:18
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%2f2553753%2fformulas-for-full-m-ary-trees%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$
Uhm... so regarding your course which include trees, you want us to give you the most important formulas... ? You will either have to provide a lot more detailed information on the content of the course or actually ask the teacher... We can guess "tree Theorems" for page up and page down, without coming close to what you want to know and even less find "the most important 2 of the course".
$endgroup$
– Ove Ahlman
Dec 6 '17 at 12:35
$begingroup$
Fair point, I have updated with all 6 formulas given.
$endgroup$
– jdc220
Dec 6 '17 at 12:45
$begingroup$
Your quote is missing context. What is $m$? Are you talking about an $m$-ary tree?
$endgroup$
– darij grinberg
Feb 3 at 5:40
$begingroup$
Good call. m = number of edges.
$endgroup$
– jdc220
Feb 3 at 14:59