Mixing
Partition a set into 2 subsets
$begingroup$
I was dealing with this problem:
Consider the set $S={1,2,3,dots,100}$. We construct two subsets $A$
and $B$ with $10$ elements each, such that the elements of $A$ are all smaller than the ones of $B$. How many ways are there to construct two such sets?
The answer is straightforward: $binom{100}{20}$ But then, this following question came to my mind and I struggled to find an approach.
Consider the set $S={1,2,3,dots,100}$. We construct two subsets $A$
and $B$ with $10$ elements each, such that; when their elements are
arranged in ascending order, each $i$th element of $A$ is smaller
than the $i$th element of $B$. How many ways are there to construct
two such sets?
I'm not interested in a computational solution; other than that, is there a nice way to solve this?
combinatorics
asked Feb 26 '14 at 18:08
Zafer CesurZafer Cesur
8281621
$endgroup$
add a comment |
$begingroup$
I was dealing with this problem:
Consider the set $S={1,2,3,dots,100}$. We construct two subsets $A$
and $B$ with $10$ elements each, such that the elements of $A$ are all smaller than the ones of $B$. How many ways are there to construct two such sets?
The answer is straightforward: $binom{100}{20}$ But then, this following question came to my mind and I struggled to find an approach.
Consider the set $S={1,2,3,dots,100}$. We construct two subsets $A$
and $B$ with $10$ elements each, such that; when their elements are
arranged in ascending order, each $i$th element of $A$ is smaller
than the $i$th element of $B$. How many ways are there to construct
two such sets?
I'm not interested in a computational solution; other than that, is there a nice way to solve this?
combinatorics
asked Feb 26 '14 at 18:08
Zafer CesurZafer Cesur
8281621
$endgroup$
$begingroup$
Do $A$ and $B$ have to be disjoint or can they overlap?
$endgroup$
– bof
Jan 26 at 6:32
add a comment |
$begingroup$
I was dealing with this problem:
Consider the set $S={1,2,3,dots,100}$. We construct two subsets $A$
and $B$ with $10$ elements each, such that the elements of $A$ are all smaller than the ones of $B$. How many ways are there to construct two such sets?
The answer is straightforward: $binom{100}{20}$ But then, this following question came to my mind and I struggled to find an approach.
Consider the set $S={1,2,3,dots,100}$. We construct two subsets $A$
and $B$ with $10$ elements each, such that; when their elements are
arranged in ascending order, each $i$th element of $A$ is smaller
than the $i$th element of $B$. How many ways are there to construct
two such sets?
I'm not interested in a computational solution; other than that, is there a nice way to solve this?
combinatorics
asked Feb 26 '14 at 18:08
Zafer CesurZafer Cesur
8281621
$endgroup$
I was dealing with this problem:
Consider the set $S={1,2,3,dots,100}$. We construct two subsets $A$
and $B$ with $10$ elements each, such that the elements of $A$ are all smaller than the ones of $B$. How many ways are there to construct two such sets?
The answer is straightforward: $binom{100}{20}$ But then, this following question came to my mind and I struggled to find an approach.
Consider the set $S={1,2,3,dots,100}$. We construct two subsets $A$
and $B$ with $10$ elements each, such that; when their elements are
arranged in ascending order, each $i$th element of $A$ is smaller
than the $i$th element of $B$. How many ways are there to construct
two such sets?
I'm not interested in a computational solution; other than that, is there a nice way to solve this?
combinatorics
combinatorics
asked Feb 26 '14 at 18:08
Zafer CesurZafer Cesur
8281621
asked Feb 26 '14 at 18:08
Zafer CesurZafer Cesur
8281621
asked Feb 26 '14 at 18:08
Zafer CesurZafer Cesur
8281621
asked Feb 26 '14 at 18:08
Zafer CesurZafer Cesur
8281621
asked Feb 26 '14 at 18:08
Zafer CesurZafer Cesur
8281621
8281621
$begingroup$
Do $A$ and $B$ have to be disjoint or can they overlap?
$endgroup$
– bof
Jan 26 at 6:32
add a comment |
$begingroup$
Do $A$ and $B$ have to be disjoint or can they overlap?
$endgroup$
– bof
Jan 26 at 6:32
$begingroup$
Do $A$ and $B$ have to be disjoint or can they overlap?
$endgroup$
– bof
Jan 26 at 6:32
$begingroup$
Do $A$ and $B$ have to be disjoint or can they overlap?
$endgroup$
– bof
Jan 26 at 6:32
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The below assumes that $A$ and $B$ must be disjoint. It is not clear if that was required or not in the problem statement.
First choose $A cup B$, which is $100 choose 20$. Then you need to find the number of ways to partition $[1,20]$ into two $10$ element subsets subject to the corresponding element condition. These are the Catalan numbers. Look at the monotonic paths staying below the diagonal. Think of $n=10$ (the number of elements in $A$). If there is a right arrow, the next number goes in $A$, if there is an up arrow, the next number goes in $B$ As long as we don't get above the diagonal, we meet the corresponding element condition. So there are ${100 choose 20}C_{10}={100 choose 20}frac 1{11}{20 choose 10}$ ways
answered Feb 26 '14 at 18:30
Ross MillikanRoss Millikan
300k24200374
$endgroup$
$begingroup$
@bof: you are correct I assumed A and B are disjoint in my answer. I don't immediately see a way to fix it. I thought about adding $1$ to all the elements in B, but that doesn't seem to work out. I added a note.
$endgroup$
– Ross Millikan
Jan 26 at 15:24
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%2f691520%2fpartition-a-set-into-2-subsets%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$
The below assumes that $A$ and $B$ must be disjoint. It is not clear if that was required or not in the problem statement.
First choose $A cup B$, which is $100 choose 20$. Then you need to find the number of ways to partition $[1,20]$ into two $10$ element subsets subject to the corresponding element condition. These are the Catalan numbers. Look at the monotonic paths staying below the diagonal. Think of $n=10$ (the number of elements in $A$). If there is a right arrow, the next number goes in $A$, if there is an up arrow, the next number goes in $B$ As long as we don't get above the diagonal, we meet the corresponding element condition. So there are ${100 choose 20}C_{10}={100 choose 20}frac 1{11}{20 choose 10}$ ways
answered Feb 26 '14 at 18:30
Ross MillikanRoss Millikan
300k24200374
$endgroup$
$begingroup$
@bof: you are correct I assumed A and B are disjoint in my answer. I don't immediately see a way to fix it. I thought about adding $1$ to all the elements in B, but that doesn't seem to work out. I added a note.
$endgroup$
– Ross Millikan
Jan 26 at 15:24
add a comment |
$begingroup$
The below assumes that $A$ and $B$ must be disjoint. It is not clear if that was required or not in the problem statement.
First choose $A cup B$, which is $100 choose 20$. Then you need to find the number of ways to partition $[1,20]$ into two $10$ element subsets subject to the corresponding element condition. These are the Catalan numbers. Look at the monotonic paths staying below the diagonal. Think of $n=10$ (the number of elements in $A$). If there is a right arrow, the next number goes in $A$, if there is an up arrow, the next number goes in $B$ As long as we don't get above the diagonal, we meet the corresponding element condition. So there are ${100 choose 20}C_{10}={100 choose 20}frac 1{11}{20 choose 10}$ ways
answered Feb 26 '14 at 18:30
Ross MillikanRoss Millikan
300k24200374
$endgroup$
$begingroup$
@bof: you are correct I assumed A and B are disjoint in my answer. I don't immediately see a way to fix it. I thought about adding $1$ to all the elements in B, but that doesn't seem to work out. I added a note.
$endgroup$
– Ross Millikan
Jan 26 at 15:24
add a comment |
$begingroup$
The below assumes that $A$ and $B$ must be disjoint. It is not clear if that was required or not in the problem statement.
First choose $A cup B$, which is $100 choose 20$. Then you need to find the number of ways to partition $[1,20]$ into two $10$ element subsets subject to the corresponding element condition. These are the Catalan numbers. Look at the monotonic paths staying below the diagonal. Think of $n=10$ (the number of elements in $A$). If there is a right arrow, the next number goes in $A$, if there is an up arrow, the next number goes in $B$ As long as we don't get above the diagonal, we meet the corresponding element condition. So there are ${100 choose 20}C_{10}={100 choose 20}frac 1{11}{20 choose 10}$ ways
answered Feb 26 '14 at 18:30
Ross MillikanRoss Millikan
300k24200374
$endgroup$
The below assumes that $A$ and $B$ must be disjoint. It is not clear if that was required or not in the problem statement.
First choose $A cup B$, which is $100 choose 20$. Then you need to find the number of ways to partition $[1,20]$ into two $10$ element subsets subject to the corresponding element condition. These are the Catalan numbers. Look at the monotonic paths staying below the diagonal. Think of $n=10$ (the number of elements in $A$). If there is a right arrow, the next number goes in $A$, if there is an up arrow, the next number goes in $B$ As long as we don't get above the diagonal, we meet the corresponding element condition. So there are ${100 choose 20}C_{10}={100 choose 20}frac 1{11}{20 choose 10}$ ways
answered Feb 26 '14 at 18:30
Ross MillikanRoss Millikan
300k24200374
edited Mar 14 at 17:46
answered Feb 26 '14 at 18:30
Ross MillikanRoss Millikan
300k24200374
answered Feb 26 '14 at 18:30
Ross MillikanRoss Millikan
300k24200374
answered Feb 26 '14 at 18:30
Ross MillikanRoss Millikan
300k24200374
300k24200374
$begingroup$
@bof: you are correct I assumed A and B are disjoint in my answer. I don't immediately see a way to fix it. I thought about adding $1$ to all the elements in B, but that doesn't seem to work out. I added a note.
$endgroup$
– Ross Millikan
Jan 26 at 15:24
add a comment |
$begingroup$
@bof: you are correct I assumed A and B are disjoint in my answer. I don't immediately see a way to fix it. I thought about adding $1$ to all the elements in B, but that doesn't seem to work out. I added a note.
$endgroup$
– Ross Millikan
Jan 26 at 15:24
$begingroup$
@bof: you are correct I assumed A and B are disjoint in my answer. I don't immediately see a way to fix it. I thought about adding $1$ to all the elements in B, but that doesn't seem to work out. I added a note.
$endgroup$
– Ross Millikan
Jan 26 at 15:24
$begingroup$
@bof: you are correct I assumed A and B are disjoint in my answer. I don't immediately see a way to fix it. I thought about adding $1$ to all the elements in B, but that doesn't seem to work out. I added a note.
$endgroup$
– Ross Millikan
Jan 26 at 15:24
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%2f691520%2fpartition-a-set-into-2-subsets%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$
Do $A$ and $B$ have to be disjoint or can they overlap?
$endgroup$
– bof
Jan 26 at 6:32