SDR question: What is the number $m$ of different sets $P_k$ in $mathcal P_n$ for a given $n$?
$begingroup$
Consider elements of $Z_{2n}$, that is, numbers $0,1,2,dots, 2n-1$. Let
$mathcal P_n={ P_1,P_2,dots, P_m}$ be a collection of unordered sets, where each $P_k$ consists of $n$ ordered pairs $(a_i,b_i)$ with the following properties:
$(1)$ $A={ a_i| 1leq ileq n}, B={ b_i| 1leq ileq n}$, and
$Acup B={0,1,2,dots,2n-1}$
$(2)$ For every $1leq ileq n$, we have $a_i < b_i$
$(3)$ For any $1leq i,jleq n, ineq j$ we have $a_i < a_j < b_i$ if and only if $a_i < b_j < b_i$
What is the number $m$ of different sets $P_k$ in $mathcal P_n$ for a given $n$?
combinatorics
asked Dec 3 '18 at 17:52
DummKorfDummKorf
335
$endgroup$
add a comment |
$begingroup$
Consider elements of $Z_{2n}$, that is, numbers $0,1,2,dots, 2n-1$. Let
$mathcal P_n={ P_1,P_2,dots, P_m}$ be a collection of unordered sets, where each $P_k$ consists of $n$ ordered pairs $(a_i,b_i)$ with the following properties:
$(1)$ $A={ a_i| 1leq ileq n}, B={ b_i| 1leq ileq n}$, and
$Acup B={0,1,2,dots,2n-1}$
$(2)$ For every $1leq ileq n$, we have $a_i < b_i$
$(3)$ For any $1leq i,jleq n, ineq j$ we have $a_i < a_j < b_i$ if and only if $a_i < b_j < b_i$
What is the number $m$ of different sets $P_k$ in $mathcal P_n$ for a given $n$?
combinatorics
asked Dec 3 '18 at 17:52
DummKorfDummKorf
335
$endgroup$
$begingroup$
What have you tried so far? How far have you gotten?
$endgroup$
– saulspatz
Dec 3 '18 at 18:27
add a comment |
$begingroup$
Consider elements of $Z_{2n}$, that is, numbers $0,1,2,dots, 2n-1$. Let
$mathcal P_n={ P_1,P_2,dots, P_m}$ be a collection of unordered sets, where each $P_k$ consists of $n$ ordered pairs $(a_i,b_i)$ with the following properties:
$(1)$ $A={ a_i| 1leq ileq n}, B={ b_i| 1leq ileq n}$, and
$Acup B={0,1,2,dots,2n-1}$
$(2)$ For every $1leq ileq n$, we have $a_i < b_i$
$(3)$ For any $1leq i,jleq n, ineq j$ we have $a_i < a_j < b_i$ if and only if $a_i < b_j < b_i$
What is the number $m$ of different sets $P_k$ in $mathcal P_n$ for a given $n$?
combinatorics
asked Dec 3 '18 at 17:52
DummKorfDummKorf
335
$endgroup$
Consider elements of $Z_{2n}$, that is, numbers $0,1,2,dots, 2n-1$. Let
$mathcal P_n={ P_1,P_2,dots, P_m}$ be a collection of unordered sets, where each $P_k$ consists of $n$ ordered pairs $(a_i,b_i)$ with the following properties:
$(1)$ $A={ a_i| 1leq ileq n}, B={ b_i| 1leq ileq n}$, and
$Acup B={0,1,2,dots,2n-1}$
$(2)$ For every $1leq ileq n$, we have $a_i < b_i$
$(3)$ For any $1leq i,jleq n, ineq j$ we have $a_i < a_j < b_i$ if and only if $a_i < b_j < b_i$
What is the number $m$ of different sets $P_k$ in $mathcal P_n$ for a given $n$?
combinatorics
combinatorics
asked Dec 3 '18 at 17:52
DummKorfDummKorf
335
asked Dec 3 '18 at 17:52
DummKorfDummKorf
335
asked Dec 3 '18 at 17:52
DummKorfDummKorf
335
asked Dec 3 '18 at 17:52
DummKorfDummKorf
335
asked Dec 3 '18 at 17:52
DummKorfDummKorf
335
335
$begingroup$
What have you tried so far? How far have you gotten?
$endgroup$
– saulspatz
Dec 3 '18 at 18:27
add a comment |
$begingroup$
What have you tried so far? How far have you gotten?
$endgroup$
– saulspatz
Dec 3 '18 at 18:27
$begingroup$
What have you tried so far? How far have you gotten?
$endgroup$
– saulspatz
Dec 3 '18 at 18:27
$begingroup$
What have you tried so far? How far have you gotten?
$endgroup$
– saulspatz
Dec 3 '18 at 18:27
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let $C_n$ be the number of such sets for a given $n$. Clearly, $C_0=C_1=1.$ To establish a recurrence, we ask which number can be paired with $0.$ Suppose $(0,b)$ is one of the pairs. Then in every other pair either both numbers are greater than $b$, or both are less than $b$. That is, $b$ must be odd. Further, the pairings of the numbers from $1$ to $b-1$ and the pairings of the numbers from $b+1$ to $2n-1$ must both obey rule $(3).$
Therefore, $$E_n=sum_{k=0}^{n-1}E_kE_{n-1-k}$$ and we recognize the recurrence for the Catalan numbers. (look at the "First Proof" on the wiki page.
answered Dec 3 '18 at 19:07
saulspatzsaulspatz
15.5k31331
$endgroup$
add a comment |
$begingroup$
With any $P_kin mathcal P_n$, we associate a legal sequence of $n$ open and $n$ closed parentheses by putting an open parentheses at position $a_i$ and a closed one at position $b_i$. Conversely, given any legal sequence of length $2n$, we can pair the positions of corresponding parentheses and the set of such pairs gives us an element of $mathcal P_n$.
Therefore, $$mid mathcal P_nmid= C_n=frac{1}{n+1}binom{2n}{n}$$
Footnotes:
1. https://en.wikipedia.org/wiki/Catalan_number
answered Dec 3 '18 at 19:35
Anubhab GhosalAnubhab Ghosal
1,20919
$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%2f3024429%2fsdr-question-what-is-the-number-m-of-different-sets-p-k-in-mathcal-p-n-f%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$
Let $C_n$ be the number of such sets for a given $n$. Clearly, $C_0=C_1=1.$ To establish a recurrence, we ask which number can be paired with $0.$ Suppose $(0,b)$ is one of the pairs. Then in every other pair either both numbers are greater than $b$, or both are less than $b$. That is, $b$ must be odd. Further, the pairings of the numbers from $1$ to $b-1$ and the pairings of the numbers from $b+1$ to $2n-1$ must both obey rule $(3).$
Therefore, $$E_n=sum_{k=0}^{n-1}E_kE_{n-1-k}$$ and we recognize the recurrence for the Catalan numbers. (look at the "First Proof" on the wiki page.
answered Dec 3 '18 at 19:07
saulspatzsaulspatz
15.5k31331
$endgroup$
add a comment |
$begingroup$
Let $C_n$ be the number of such sets for a given $n$. Clearly, $C_0=C_1=1.$ To establish a recurrence, we ask which number can be paired with $0.$ Suppose $(0,b)$ is one of the pairs. Then in every other pair either both numbers are greater than $b$, or both are less than $b$. That is, $b$ must be odd. Further, the pairings of the numbers from $1$ to $b-1$ and the pairings of the numbers from $b+1$ to $2n-1$ must both obey rule $(3).$
Therefore, $$E_n=sum_{k=0}^{n-1}E_kE_{n-1-k}$$ and we recognize the recurrence for the Catalan numbers. (look at the "First Proof" on the wiki page.
answered Dec 3 '18 at 19:07
saulspatzsaulspatz
15.5k31331
$endgroup$
add a comment |
$begingroup$
Let $C_n$ be the number of such sets for a given $n$. Clearly, $C_0=C_1=1.$ To establish a recurrence, we ask which number can be paired with $0.$ Suppose $(0,b)$ is one of the pairs. Then in every other pair either both numbers are greater than $b$, or both are less than $b$. That is, $b$ must be odd. Further, the pairings of the numbers from $1$ to $b-1$ and the pairings of the numbers from $b+1$ to $2n-1$ must both obey rule $(3).$
Therefore, $$E_n=sum_{k=0}^{n-1}E_kE_{n-1-k}$$ and we recognize the recurrence for the Catalan numbers. (look at the "First Proof" on the wiki page.
answered Dec 3 '18 at 19:07
saulspatzsaulspatz
15.5k31331
$endgroup$
Let $C_n$ be the number of such sets for a given $n$. Clearly, $C_0=C_1=1.$ To establish a recurrence, we ask which number can be paired with $0.$ Suppose $(0,b)$ is one of the pairs. Then in every other pair either both numbers are greater than $b$, or both are less than $b$. That is, $b$ must be odd. Further, the pairings of the numbers from $1$ to $b-1$ and the pairings of the numbers from $b+1$ to $2n-1$ must both obey rule $(3).$
Therefore, $$E_n=sum_{k=0}^{n-1}E_kE_{n-1-k}$$ and we recognize the recurrence for the Catalan numbers. (look at the "First Proof" on the wiki page.
answered Dec 3 '18 at 19:07
saulspatzsaulspatz
15.5k31331
answered Dec 3 '18 at 19:07
saulspatzsaulspatz
15.5k31331
answered Dec 3 '18 at 19:07
saulspatzsaulspatz
15.5k31331
answered Dec 3 '18 at 19:07
saulspatzsaulspatz
15.5k31331
15.5k31331
add a comment |
add a comment |
$begingroup$
With any $P_kin mathcal P_n$, we associate a legal sequence of $n$ open and $n$ closed parentheses by putting an open parentheses at position $a_i$ and a closed one at position $b_i$. Conversely, given any legal sequence of length $2n$, we can pair the positions of corresponding parentheses and the set of such pairs gives us an element of $mathcal P_n$.
Therefore, $$mid mathcal P_nmid= C_n=frac{1}{n+1}binom{2n}{n}$$
Footnotes:
1. https://en.wikipedia.org/wiki/Catalan_number
answered Dec 3 '18 at 19:35
Anubhab GhosalAnubhab Ghosal
1,20919
$endgroup$
add a comment |
$begingroup$
With any $P_kin mathcal P_n$, we associate a legal sequence of $n$ open and $n$ closed parentheses by putting an open parentheses at position $a_i$ and a closed one at position $b_i$. Conversely, given any legal sequence of length $2n$, we can pair the positions of corresponding parentheses and the set of such pairs gives us an element of $mathcal P_n$.
Therefore, $$mid mathcal P_nmid= C_n=frac{1}{n+1}binom{2n}{n}$$
Footnotes:
1. https://en.wikipedia.org/wiki/Catalan_number
answered Dec 3 '18 at 19:35
Anubhab GhosalAnubhab Ghosal
1,20919
$endgroup$
add a comment |
$begingroup$
With any $P_kin mathcal P_n$, we associate a legal sequence of $n$ open and $n$ closed parentheses by putting an open parentheses at position $a_i$ and a closed one at position $b_i$. Conversely, given any legal sequence of length $2n$, we can pair the positions of corresponding parentheses and the set of such pairs gives us an element of $mathcal P_n$.
Therefore, $$mid mathcal P_nmid= C_n=frac{1}{n+1}binom{2n}{n}$$
Footnotes:
1. https://en.wikipedia.org/wiki/Catalan_number
answered Dec 3 '18 at 19:35
Anubhab GhosalAnubhab Ghosal
1,20919
$endgroup$
With any $P_kin mathcal P_n$, we associate a legal sequence of $n$ open and $n$ closed parentheses by putting an open parentheses at position $a_i$ and a closed one at position $b_i$. Conversely, given any legal sequence of length $2n$, we can pair the positions of corresponding parentheses and the set of such pairs gives us an element of $mathcal P_n$.
Therefore, $$mid mathcal P_nmid= C_n=frac{1}{n+1}binom{2n}{n}$$
Footnotes:
1. https://en.wikipedia.org/wiki/Catalan_number
answered Dec 3 '18 at 19:35
Anubhab GhosalAnubhab Ghosal
1,20919
edited Jan 28 at 14:04
answered Dec 3 '18 at 19:35
Anubhab GhosalAnubhab Ghosal
1,20919
answered Dec 3 '18 at 19:35
Anubhab GhosalAnubhab Ghosal
1,20919
answered Dec 3 '18 at 19:35
Anubhab GhosalAnubhab Ghosal
1,20919
1,20919
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%2f3024429%2fsdr-question-what-is-the-number-m-of-different-sets-p-k-in-mathcal-p-n-f%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$
What have you tried so far? How far have you gotten?
$endgroup$
– saulspatz
Dec 3 '18 at 18:27