Mixing
Understanding an expression which related to full binary trees
$begingroup$
I am quite new to discrete mathematics. I was going through graph and found this expression which was for full binary tree, where $B_h$ represents graph i.e. full binary tree of length/ height h
$B_h := ([2]^{≤h}, {{u,ux} such that uepsilon [2]^{<h}, xepsilon [2]})$
I got confused here. what do $[2]^{≤h}$ and $[2]^{<h}$ mean here, i am quite certain that [2] means {1,2}. But that exponent on the set is quite not clear to me. does that mean cartesian product? I would be thankful for any kind of help. thanks!
discrete-mathematics elementary-set-theory graph-theory notation
asked Jan 28 at 21:48
the hitchhikerthe hitchhiker
62
$endgroup$
add a comment |
$begingroup$
I am quite new to discrete mathematics. I was going through graph and found this expression which was for full binary tree, where $B_h$ represents graph i.e. full binary tree of length/ height h
$B_h := ([2]^{≤h}, {{u,ux} such that uepsilon [2]^{<h}, xepsilon [2]})$
I got confused here. what do $[2]^{≤h}$ and $[2]^{<h}$ mean here, i am quite certain that [2] means {1,2}. But that exponent on the set is quite not clear to me. does that mean cartesian product? I would be thankful for any kind of help. thanks!
discrete-mathematics elementary-set-theory graph-theory notation
asked Jan 28 at 21:48
the hitchhikerthe hitchhiker
62
$endgroup$
$begingroup$
We can make educated guesses, but also you have some typos in your formula, and for a definitely correct answer you probably want to say something about where this expression comes from so that we have context.
$endgroup$
– Misha Lavrov
Jan 28 at 21:58
add a comment |
$begingroup$
I am quite new to discrete mathematics. I was going through graph and found this expression which was for full binary tree, where $B_h$ represents graph i.e. full binary tree of length/ height h
$B_h := ([2]^{≤h}, {{u,ux} such that uepsilon [2]^{<h}, xepsilon [2]})$
I got confused here. what do $[2]^{≤h}$ and $[2]^{<h}$ mean here, i am quite certain that [2] means {1,2}. But that exponent on the set is quite not clear to me. does that mean cartesian product? I would be thankful for any kind of help. thanks!
discrete-mathematics elementary-set-theory graph-theory notation
asked Jan 28 at 21:48
the hitchhikerthe hitchhiker
62
$endgroup$
I am quite new to discrete mathematics. I was going through graph and found this expression which was for full binary tree, where $B_h$ represents graph i.e. full binary tree of length/ height h
$B_h := ([2]^{≤h}, {{u,ux} such that uepsilon [2]^{<h}, xepsilon [2]})$
I got confused here. what do $[2]^{≤h}$ and $[2]^{<h}$ mean here, i am quite certain that [2] means {1,2}. But that exponent on the set is quite not clear to me. does that mean cartesian product? I would be thankful for any kind of help. thanks!
discrete-mathematics elementary-set-theory graph-theory notation
discrete-mathematics elementary-set-theory graph-theory notation
asked Jan 28 at 21:48
the hitchhikerthe hitchhiker
62
asked Jan 28 at 21:48
the hitchhikerthe hitchhiker
62
edited Jan 28 at 22:09
the hitchhiker
asked Jan 28 at 21:48
the hitchhikerthe hitchhiker
62
asked Jan 28 at 21:48
the hitchhikerthe hitchhiker
62
asked Jan 28 at 21:48
the hitchhikerthe hitchhiker
62
62
$begingroup$
We can make educated guesses, but also you have some typos in your formula, and for a definitely correct answer you probably want to say something about where this expression comes from so that we have context.
$endgroup$
– Misha Lavrov
Jan 28 at 21:58
add a comment |
$begingroup$
We can make educated guesses, but also you have some typos in your formula, and for a definitely correct answer you probably want to say something about where this expression comes from so that we have context.
$endgroup$
– Misha Lavrov
Jan 28 at 21:58
$begingroup$
We can make educated guesses, but also you have some typos in your formula, and for a definitely correct answer you probably want to say something about where this expression comes from so that we have context.
$endgroup$
– Misha Lavrov
Jan 28 at 21:58
$begingroup$
We can make educated guesses, but also you have some typos in your formula, and for a definitely correct answer you probably want to say something about where this expression comes from so that we have context.
$endgroup$
– Misha Lavrov
Jan 28 at 21:58
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If you will permit, I am more comfortable thinking of $[2]$ as ${0,1}$.
$[2]^h$ is the Cartesian product of $[2]$ with itself $[h]$ times:
$$
[2]^h=[2]times[2]timesdotstimes[2]cong{(b_1,b_2,dots,b_h)mid b_iin [2]text{ for }1le ile h}
$$
In other words, $[2]^h$ consists of binary sequences of length $h$. Then,
$$
[2]^{le h}=[2]^0cup [2]^1cup dotscup [2]^h
$$
is the set of binary sequences of length at most $h$. That is, $2^{le [h]}$ is not a Cartesian product, but a union of Cartesian products. You can probably imagine now what $[2]^{<h}$ is; it consists of binary sequences whose lengths are strictly less than $h$.
The set of edges is of the form ${u,ux}$, where $u$ is a binary sequence of length less than $h$, and $xin {0,1}$. The multiplication here is concatenation. For example, letting $u=(0,1,0)$, and $x=0$, there is an edge between $(0,1,0)$ and $(0,1,0,0)$; we add a $0$ to the end of $u$ to get its neighbor.
answered Jan 29 at 3:14
Mike EarnestMike Earnest
26.2k22151
$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%2f3091437%2funderstanding-an-expression-which-related-to-full-binary-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$
If you will permit, I am more comfortable thinking of $[2]$ as ${0,1}$.
$[2]^h$ is the Cartesian product of $[2]$ with itself $[h]$ times:
$$
[2]^h=[2]times[2]timesdotstimes[2]cong{(b_1,b_2,dots,b_h)mid b_iin [2]text{ for }1le ile h}
$$
In other words, $[2]^h$ consists of binary sequences of length $h$. Then,
$$
[2]^{le h}=[2]^0cup [2]^1cup dotscup [2]^h
$$
is the set of binary sequences of length at most $h$. That is, $2^{le [h]}$ is not a Cartesian product, but a union of Cartesian products. You can probably imagine now what $[2]^{<h}$ is; it consists of binary sequences whose lengths are strictly less than $h$.
The set of edges is of the form ${u,ux}$, where $u$ is a binary sequence of length less than $h$, and $xin {0,1}$. The multiplication here is concatenation. For example, letting $u=(0,1,0)$, and $x=0$, there is an edge between $(0,1,0)$ and $(0,1,0,0)$; we add a $0$ to the end of $u$ to get its neighbor.
answered Jan 29 at 3:14
Mike EarnestMike Earnest
26.2k22151
$endgroup$
add a comment |
$begingroup$
If you will permit, I am more comfortable thinking of $[2]$ as ${0,1}$.
$[2]^h$ is the Cartesian product of $[2]$ with itself $[h]$ times:
$$
[2]^h=[2]times[2]timesdotstimes[2]cong{(b_1,b_2,dots,b_h)mid b_iin [2]text{ for }1le ile h}
$$
In other words, $[2]^h$ consists of binary sequences of length $h$. Then,
$$
[2]^{le h}=[2]^0cup [2]^1cup dotscup [2]^h
$$
is the set of binary sequences of length at most $h$. That is, $2^{le [h]}$ is not a Cartesian product, but a union of Cartesian products. You can probably imagine now what $[2]^{<h}$ is; it consists of binary sequences whose lengths are strictly less than $h$.
The set of edges is of the form ${u,ux}$, where $u$ is a binary sequence of length less than $h$, and $xin {0,1}$. The multiplication here is concatenation. For example, letting $u=(0,1,0)$, and $x=0$, there is an edge between $(0,1,0)$ and $(0,1,0,0)$; we add a $0$ to the end of $u$ to get its neighbor.
answered Jan 29 at 3:14
Mike EarnestMike Earnest
26.2k22151
$endgroup$
add a comment |
$begingroup$
If you will permit, I am more comfortable thinking of $[2]$ as ${0,1}$.
$[2]^h$ is the Cartesian product of $[2]$ with itself $[h]$ times:
$$
[2]^h=[2]times[2]timesdotstimes[2]cong{(b_1,b_2,dots,b_h)mid b_iin [2]text{ for }1le ile h}
$$
In other words, $[2]^h$ consists of binary sequences of length $h$. Then,
$$
[2]^{le h}=[2]^0cup [2]^1cup dotscup [2]^h
$$
is the set of binary sequences of length at most $h$. That is, $2^{le [h]}$ is not a Cartesian product, but a union of Cartesian products. You can probably imagine now what $[2]^{<h}$ is; it consists of binary sequences whose lengths are strictly less than $h$.
The set of edges is of the form ${u,ux}$, where $u$ is a binary sequence of length less than $h$, and $xin {0,1}$. The multiplication here is concatenation. For example, letting $u=(0,1,0)$, and $x=0$, there is an edge between $(0,1,0)$ and $(0,1,0,0)$; we add a $0$ to the end of $u$ to get its neighbor.
answered Jan 29 at 3:14
Mike EarnestMike Earnest
26.2k22151
$endgroup$
If you will permit, I am more comfortable thinking of $[2]$ as ${0,1}$.
$[2]^h$ is the Cartesian product of $[2]$ with itself $[h]$ times:
$$
[2]^h=[2]times[2]timesdotstimes[2]cong{(b_1,b_2,dots,b_h)mid b_iin [2]text{ for }1le ile h}
$$
In other words, $[2]^h$ consists of binary sequences of length $h$. Then,
$$
[2]^{le h}=[2]^0cup [2]^1cup dotscup [2]^h
$$
is the set of binary sequences of length at most $h$. That is, $2^{le [h]}$ is not a Cartesian product, but a union of Cartesian products. You can probably imagine now what $[2]^{<h}$ is; it consists of binary sequences whose lengths are strictly less than $h$.
The set of edges is of the form ${u,ux}$, where $u$ is a binary sequence of length less than $h$, and $xin {0,1}$. The multiplication here is concatenation. For example, letting $u=(0,1,0)$, and $x=0$, there is an edge between $(0,1,0)$ and $(0,1,0,0)$; we add a $0$ to the end of $u$ to get its neighbor.
answered Jan 29 at 3:14
Mike EarnestMike Earnest
26.2k22151
edited Jan 29 at 4:30
answered Jan 29 at 3:14
Mike EarnestMike Earnest
26.2k22151
answered Jan 29 at 3:14
Mike EarnestMike Earnest
26.2k22151
answered Jan 29 at 3:14
Mike EarnestMike Earnest
26.2k22151
26.2k22151
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%2f3091437%2funderstanding-an-expression-which-related-to-full-binary-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$
We can make educated guesses, but also you have some typos in your formula, and for a definitely correct answer you probably want to say something about where this expression comes from so that we have context.
$endgroup$
– Misha Lavrov
Jan 28 at 21:58