Mixing
Advanced combinatorics question: rows with open en closed brackets
$begingroup$
Consider a row with open and closed brackets. A row is correct if for each open bracket there is a unique closed bracket further in the row. In other words: if this row of brackets can be seen as a correct mathematical expression from which all numbers and operation symbols are omitted. Or again in other words: for each point in the row, the amount of open brackets for this point has to be at least the amount of closed brackets for this point.
Show that the number of correct rows with $n$ pairs of brackets is given by $frac1{n+1} binom{2n}{n}$.
Remark: Following statements can (you don't have to use them) give some inspiration (you'll need more arguments and the given statements are not written in the correct order!):
- If a row of brackets does not satisfy the conditions (bad row), then there is a point $dots$ on which the number of closed brackets exceeds the number of the open brackets for the first time.
- An alternative row is a row with $n-1$ open brackets and $n+1$ closed brackets.
- It's clear that $g circ f$ is the identity map on the bad rows and that $f circ g$ is the identity map on the alternative rows. This implies that $f$ and $g$ are bijections.
- $$binom{2n}{n} - binom{2n}{n-1} = dots = frac1{n+1} binom{2n}{n}$$
- "... change all open brackets on positions $2k+2, dots, 2n$ in this alternative row $r$ into closed brackets ..."
I have no idea how to start with this proof. Any clues? Thanks a lot!
combinatorics
asked Jan 27 at 14:03
ZacharyZachary
1939
$endgroup$
add a comment |
$begingroup$
Consider a row with open and closed brackets. A row is correct if for each open bracket there is a unique closed bracket further in the row. In other words: if this row of brackets can be seen as a correct mathematical expression from which all numbers and operation symbols are omitted. Or again in other words: for each point in the row, the amount of open brackets for this point has to be at least the amount of closed brackets for this point.
Show that the number of correct rows with $n$ pairs of brackets is given by $frac1{n+1} binom{2n}{n}$.
Remark: Following statements can (you don't have to use them) give some inspiration (you'll need more arguments and the given statements are not written in the correct order!):
- If a row of brackets does not satisfy the conditions (bad row), then there is a point $dots$ on which the number of closed brackets exceeds the number of the open brackets for the first time.
- An alternative row is a row with $n-1$ open brackets and $n+1$ closed brackets.
- It's clear that $g circ f$ is the identity map on the bad rows and that $f circ g$ is the identity map on the alternative rows. This implies that $f$ and $g$ are bijections.
- $$binom{2n}{n} - binom{2n}{n-1} = dots = frac1{n+1} binom{2n}{n}$$
- "... change all open brackets on positions $2k+2, dots, 2n$ in this alternative row $r$ into closed brackets ..."
I have no idea how to start with this proof. Any clues? Thanks a lot!
combinatorics
asked Jan 27 at 14:03
ZacharyZachary
1939
$endgroup$
add a comment |
$begingroup$
Consider a row with open and closed brackets. A row is correct if for each open bracket there is a unique closed bracket further in the row. In other words: if this row of brackets can be seen as a correct mathematical expression from which all numbers and operation symbols are omitted. Or again in other words: for each point in the row, the amount of open brackets for this point has to be at least the amount of closed brackets for this point.
Show that the number of correct rows with $n$ pairs of brackets is given by $frac1{n+1} binom{2n}{n}$.
Remark: Following statements can (you don't have to use them) give some inspiration (you'll need more arguments and the given statements are not written in the correct order!):
- If a row of brackets does not satisfy the conditions (bad row), then there is a point $dots$ on which the number of closed brackets exceeds the number of the open brackets for the first time.
- An alternative row is a row with $n-1$ open brackets and $n+1$ closed brackets.
- It's clear that $g circ f$ is the identity map on the bad rows and that $f circ g$ is the identity map on the alternative rows. This implies that $f$ and $g$ are bijections.
- $$binom{2n}{n} - binom{2n}{n-1} = dots = frac1{n+1} binom{2n}{n}$$
- "... change all open brackets on positions $2k+2, dots, 2n$ in this alternative row $r$ into closed brackets ..."
I have no idea how to start with this proof. Any clues? Thanks a lot!
combinatorics
asked Jan 27 at 14:03
ZacharyZachary
1939
$endgroup$
Consider a row with open and closed brackets. A row is correct if for each open bracket there is a unique closed bracket further in the row. In other words: if this row of brackets can be seen as a correct mathematical expression from which all numbers and operation symbols are omitted. Or again in other words: for each point in the row, the amount of open brackets for this point has to be at least the amount of closed brackets for this point.
Show that the number of correct rows with $n$ pairs of brackets is given by $frac1{n+1} binom{2n}{n}$.
Remark: Following statements can (you don't have to use them) give some inspiration (you'll need more arguments and the given statements are not written in the correct order!):
- If a row of brackets does not satisfy the conditions (bad row), then there is a point $dots$ on which the number of closed brackets exceeds the number of the open brackets for the first time.
- An alternative row is a row with $n-1$ open brackets and $n+1$ closed brackets.
- It's clear that $g circ f$ is the identity map on the bad rows and that $f circ g$ is the identity map on the alternative rows. This implies that $f$ and $g$ are bijections.
- $$binom{2n}{n} - binom{2n}{n-1} = dots = frac1{n+1} binom{2n}{n}$$
- "... change all open brackets on positions $2k+2, dots, 2n$ in this alternative row $r$ into closed brackets ..."
I have no idea how to start with this proof. Any clues? Thanks a lot!
combinatorics
combinatorics
asked Jan 27 at 14:03
ZacharyZachary
1939
asked Jan 27 at 14:03
ZacharyZachary
1939
asked Jan 27 at 14:03
ZacharyZachary
1939
asked Jan 27 at 14:03
ZacharyZachary
1939
asked Jan 27 at 14:03
ZacharyZachary
1939
1939
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here is a combinatorial proof based upon lattice paths.
We consider paths on a $mathbb{Z}timesmathbb{Z}$ grid starting at $(0,0)$ and ending at $(2n,0)$.
We map open brackets to up-steps $(1,1)$ and closed brackets to down-steps $(1,-1)$.
A valid sequence of open and closed brackets of length $2n$ corresponds bijectively to a path of length $2n$ from $(0,0)$ to $(2n,0)$ containing $n$ up-steps $(1,1)$ and $n$ down-steps $(1,-1)$, starting with an up-step $(1,1)$ and never crossing the $x$-axis, i.e. never reaching a point with negative $y$-value.
All paths:
The number of all paths of length $2n$ from $(0,0)$ to $(2n,0)$ with $n$ up-steps and $n$ down-steps is $color{blue}{binom{2n}{n}}$.
Invalid paths:
A path of length $2n$ starting at $(0,0)$ and going to $(2n,0)$ is invalid iff it crosses the $x$-axis. This implies it touches or crosses the line $y=-1$ at least once. Let $(x_0,-1)$ be the first time this invalid path reaches the line $y=-1$. We reflect the beginning of this path from $(0,0)$ up to the point $(x_0,-1)$ at the line $y=-1$ leaving the rest of the path unchanged.
Observe a reflected path starts at the point $(0,-2)$ which is the reflected point of the origin $(0,0)$ at the line $y=-1$. We count all invalid paths by counting the reflected paths. These are all paths of length $2n$ which start from $(0,-2)$ and end in $(2n,0)$. This means we have one up-step more and one down-step less than in valid paths resulting in $color{blue}{binom{2n}{n-1}}$ reflected paths.
Valid paths: We conclude the number of valid paths is the number of all paths minus the number of reflected paths:
begin{align*}
binom{2n}{n}-binom{2n}{n-1}=color{blue}{frac{1}{n+1}binom{2n}{n}}
end{align*}
answered Jan 27 at 18:11
Markus ScheuerMarkus Scheuer
63.1k460150
$endgroup$
add a comment |
$begingroup$
This answer does not really provide a proof.
It might be helpful though, especially by the link and if Catalan numbers are new to you.
Let e.g. the sequence $(()())$ corresponds with path: $(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3)$ where the first coordinate corresponds with the number of open brackets placed and the second with the number of closed brackets.
Note that a row is correct if for every pair $(i,j)$ we have $igeq j$ and if it starts at $(0,0)$ and ends at $(n,n)$.
The number of such paths is $C_n$ where $C_n$ denotes the $n$-th Catalan number.
answered Jan 27 at 14:19
drhabdrhab
103k545136
$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%2f3089593%2fadvanced-combinatorics-question-rows-with-open-en-closed-brackets%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here is a combinatorial proof based upon lattice paths.
We consider paths on a $mathbb{Z}timesmathbb{Z}$ grid starting at $(0,0)$ and ending at $(2n,0)$.
We map open brackets to up-steps $(1,1)$ and closed brackets to down-steps $(1,-1)$.
A valid sequence of open and closed brackets of length $2n$ corresponds bijectively to a path of length $2n$ from $(0,0)$ to $(2n,0)$ containing $n$ up-steps $(1,1)$ and $n$ down-steps $(1,-1)$, starting with an up-step $(1,1)$ and never crossing the $x$-axis, i.e. never reaching a point with negative $y$-value.
All paths:
The number of all paths of length $2n$ from $(0,0)$ to $(2n,0)$ with $n$ up-steps and $n$ down-steps is $color{blue}{binom{2n}{n}}$.
Invalid paths:
A path of length $2n$ starting at $(0,0)$ and going to $(2n,0)$ is invalid iff it crosses the $x$-axis. This implies it touches or crosses the line $y=-1$ at least once. Let $(x_0,-1)$ be the first time this invalid path reaches the line $y=-1$. We reflect the beginning of this path from $(0,0)$ up to the point $(x_0,-1)$ at the line $y=-1$ leaving the rest of the path unchanged.
Observe a reflected path starts at the point $(0,-2)$ which is the reflected point of the origin $(0,0)$ at the line $y=-1$. We count all invalid paths by counting the reflected paths. These are all paths of length $2n$ which start from $(0,-2)$ and end in $(2n,0)$. This means we have one up-step more and one down-step less than in valid paths resulting in $color{blue}{binom{2n}{n-1}}$ reflected paths.
Valid paths: We conclude the number of valid paths is the number of all paths minus the number of reflected paths:
begin{align*}
binom{2n}{n}-binom{2n}{n-1}=color{blue}{frac{1}{n+1}binom{2n}{n}}
end{align*}
answered Jan 27 at 18:11
Markus ScheuerMarkus Scheuer
63.1k460150
$endgroup$
add a comment |
$begingroup$
Here is a combinatorial proof based upon lattice paths.
We consider paths on a $mathbb{Z}timesmathbb{Z}$ grid starting at $(0,0)$ and ending at $(2n,0)$.
We map open brackets to up-steps $(1,1)$ and closed brackets to down-steps $(1,-1)$.
A valid sequence of open and closed brackets of length $2n$ corresponds bijectively to a path of length $2n$ from $(0,0)$ to $(2n,0)$ containing $n$ up-steps $(1,1)$ and $n$ down-steps $(1,-1)$, starting with an up-step $(1,1)$ and never crossing the $x$-axis, i.e. never reaching a point with negative $y$-value.
All paths:
The number of all paths of length $2n$ from $(0,0)$ to $(2n,0)$ with $n$ up-steps and $n$ down-steps is $color{blue}{binom{2n}{n}}$.
Invalid paths:
A path of length $2n$ starting at $(0,0)$ and going to $(2n,0)$ is invalid iff it crosses the $x$-axis. This implies it touches or crosses the line $y=-1$ at least once. Let $(x_0,-1)$ be the first time this invalid path reaches the line $y=-1$. We reflect the beginning of this path from $(0,0)$ up to the point $(x_0,-1)$ at the line $y=-1$ leaving the rest of the path unchanged.
Observe a reflected path starts at the point $(0,-2)$ which is the reflected point of the origin $(0,0)$ at the line $y=-1$. We count all invalid paths by counting the reflected paths. These are all paths of length $2n$ which start from $(0,-2)$ and end in $(2n,0)$. This means we have one up-step more and one down-step less than in valid paths resulting in $color{blue}{binom{2n}{n-1}}$ reflected paths.
Valid paths: We conclude the number of valid paths is the number of all paths minus the number of reflected paths:
begin{align*}
binom{2n}{n}-binom{2n}{n-1}=color{blue}{frac{1}{n+1}binom{2n}{n}}
end{align*}
answered Jan 27 at 18:11
Markus ScheuerMarkus Scheuer
63.1k460150
$endgroup$
add a comment |
$begingroup$
Here is a combinatorial proof based upon lattice paths.
We consider paths on a $mathbb{Z}timesmathbb{Z}$ grid starting at $(0,0)$ and ending at $(2n,0)$.
We map open brackets to up-steps $(1,1)$ and closed brackets to down-steps $(1,-1)$.
A valid sequence of open and closed brackets of length $2n$ corresponds bijectively to a path of length $2n$ from $(0,0)$ to $(2n,0)$ containing $n$ up-steps $(1,1)$ and $n$ down-steps $(1,-1)$, starting with an up-step $(1,1)$ and never crossing the $x$-axis, i.e. never reaching a point with negative $y$-value.
All paths:
The number of all paths of length $2n$ from $(0,0)$ to $(2n,0)$ with $n$ up-steps and $n$ down-steps is $color{blue}{binom{2n}{n}}$.
Invalid paths:
A path of length $2n$ starting at $(0,0)$ and going to $(2n,0)$ is invalid iff it crosses the $x$-axis. This implies it touches or crosses the line $y=-1$ at least once. Let $(x_0,-1)$ be the first time this invalid path reaches the line $y=-1$. We reflect the beginning of this path from $(0,0)$ up to the point $(x_0,-1)$ at the line $y=-1$ leaving the rest of the path unchanged.
Observe a reflected path starts at the point $(0,-2)$ which is the reflected point of the origin $(0,0)$ at the line $y=-1$. We count all invalid paths by counting the reflected paths. These are all paths of length $2n$ which start from $(0,-2)$ and end in $(2n,0)$. This means we have one up-step more and one down-step less than in valid paths resulting in $color{blue}{binom{2n}{n-1}}$ reflected paths.
Valid paths: We conclude the number of valid paths is the number of all paths minus the number of reflected paths:
begin{align*}
binom{2n}{n}-binom{2n}{n-1}=color{blue}{frac{1}{n+1}binom{2n}{n}}
end{align*}
answered Jan 27 at 18:11
Markus ScheuerMarkus Scheuer
63.1k460150
$endgroup$
Here is a combinatorial proof based upon lattice paths.
We consider paths on a $mathbb{Z}timesmathbb{Z}$ grid starting at $(0,0)$ and ending at $(2n,0)$.
We map open brackets to up-steps $(1,1)$ and closed brackets to down-steps $(1,-1)$.
A valid sequence of open and closed brackets of length $2n$ corresponds bijectively to a path of length $2n$ from $(0,0)$ to $(2n,0)$ containing $n$ up-steps $(1,1)$ and $n$ down-steps $(1,-1)$, starting with an up-step $(1,1)$ and never crossing the $x$-axis, i.e. never reaching a point with negative $y$-value.
All paths:
The number of all paths of length $2n$ from $(0,0)$ to $(2n,0)$ with $n$ up-steps and $n$ down-steps is $color{blue}{binom{2n}{n}}$.
Invalid paths:
A path of length $2n$ starting at $(0,0)$ and going to $(2n,0)$ is invalid iff it crosses the $x$-axis. This implies it touches or crosses the line $y=-1$ at least once. Let $(x_0,-1)$ be the first time this invalid path reaches the line $y=-1$. We reflect the beginning of this path from $(0,0)$ up to the point $(x_0,-1)$ at the line $y=-1$ leaving the rest of the path unchanged.
Observe a reflected path starts at the point $(0,-2)$ which is the reflected point of the origin $(0,0)$ at the line $y=-1$. We count all invalid paths by counting the reflected paths. These are all paths of length $2n$ which start from $(0,-2)$ and end in $(2n,0)$. This means we have one up-step more and one down-step less than in valid paths resulting in $color{blue}{binom{2n}{n-1}}$ reflected paths.
Valid paths: We conclude the number of valid paths is the number of all paths minus the number of reflected paths:
begin{align*}
binom{2n}{n}-binom{2n}{n-1}=color{blue}{frac{1}{n+1}binom{2n}{n}}
end{align*}
answered Jan 27 at 18:11
Markus ScheuerMarkus Scheuer
63.1k460150
edited Jan 27 at 19:00
answered Jan 27 at 18:11
Markus ScheuerMarkus Scheuer
63.1k460150
answered Jan 27 at 18:11
Markus ScheuerMarkus Scheuer
63.1k460150
answered Jan 27 at 18:11
Markus ScheuerMarkus Scheuer
63.1k460150
63.1k460150
add a comment |
add a comment |
$begingroup$
This answer does not really provide a proof.
It might be helpful though, especially by the link and if Catalan numbers are new to you.
Let e.g. the sequence $(()())$ corresponds with path: $(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3)$ where the first coordinate corresponds with the number of open brackets placed and the second with the number of closed brackets.
Note that a row is correct if for every pair $(i,j)$ we have $igeq j$ and if it starts at $(0,0)$ and ends at $(n,n)$.
The number of such paths is $C_n$ where $C_n$ denotes the $n$-th Catalan number.
answered Jan 27 at 14:19
drhabdrhab
103k545136
$endgroup$
add a comment |
$begingroup$
This answer does not really provide a proof.
It might be helpful though, especially by the link and if Catalan numbers are new to you.
Let e.g. the sequence $(()())$ corresponds with path: $(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3)$ where the first coordinate corresponds with the number of open brackets placed and the second with the number of closed brackets.
Note that a row is correct if for every pair $(i,j)$ we have $igeq j$ and if it starts at $(0,0)$ and ends at $(n,n)$.
The number of such paths is $C_n$ where $C_n$ denotes the $n$-th Catalan number.
answered Jan 27 at 14:19
drhabdrhab
103k545136
$endgroup$
add a comment |
$begingroup$
This answer does not really provide a proof.
It might be helpful though, especially by the link and if Catalan numbers are new to you.
Let e.g. the sequence $(()())$ corresponds with path: $(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3)$ where the first coordinate corresponds with the number of open brackets placed and the second with the number of closed brackets.
Note that a row is correct if for every pair $(i,j)$ we have $igeq j$ and if it starts at $(0,0)$ and ends at $(n,n)$.
The number of such paths is $C_n$ where $C_n$ denotes the $n$-th Catalan number.
answered Jan 27 at 14:19
drhabdrhab
103k545136
$endgroup$
This answer does not really provide a proof.
It might be helpful though, especially by the link and if Catalan numbers are new to you.
Let e.g. the sequence $(()())$ corresponds with path: $(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(3,3)$ where the first coordinate corresponds with the number of open brackets placed and the second with the number of closed brackets.
Note that a row is correct if for every pair $(i,j)$ we have $igeq j$ and if it starts at $(0,0)$ and ends at $(n,n)$.
The number of such paths is $C_n$ where $C_n$ denotes the $n$-th Catalan number.
answered Jan 27 at 14:19
drhabdrhab
103k545136
edited Jan 27 at 20:59
answered Jan 27 at 14:19
drhabdrhab
103k545136
answered Jan 27 at 14:19
drhabdrhab
103k545136
answered Jan 27 at 14:19
drhabdrhab
103k545136
103k545136
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%2f3089593%2fadvanced-combinatorics-question-rows-with-open-en-closed-brackets%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
