Find the number of triples $(A, B, C)$ of subsets of $[n]$ such that at least one of $A cap B$, $A cap C$, or...
$begingroup$
Find the number of triples $(A, B, C)$ of subsets of $[n]$ such that at least one of $A cap B$, $A cap C$, or $B cap C$ is empty
I got $6^ncdot 3-3cdot 5^n+4^n$, not sure if this is correct.
Please help me on this.
combinatorics
edited Dec 16 '18 at 20:10
t.ysn
1457
asked Dec 16 '18 at 17:08
MojicaMojica
202
$endgroup$
add a comment |
$begingroup$
Find the number of triples $(A, B, C)$ of subsets of $[n]$ such that at least one of $A cap B$, $A cap C$, or $B cap C$ is empty
I got $6^ncdot 3-3cdot 5^n+4^n$, not sure if this is correct.
Please help me on this.
combinatorics
edited Dec 16 '18 at 20:10
t.ysn
1457
asked Dec 16 '18 at 17:08
MojicaMojica
202
$endgroup$
3
$begingroup$
Please explain how you got your answer. It is much easier to check work than to redo it. It is correct for $n=1$.
$endgroup$
– Ross Millikan
Dec 16 '18 at 17:42
add a comment |
$begingroup$
Find the number of triples $(A, B, C)$ of subsets of $[n]$ such that at least one of $A cap B$, $A cap C$, or $B cap C$ is empty
I got $6^ncdot 3-3cdot 5^n+4^n$, not sure if this is correct.
Please help me on this.
combinatorics
edited Dec 16 '18 at 20:10
t.ysn
1457
asked Dec 16 '18 at 17:08
MojicaMojica
202
$endgroup$
Find the number of triples $(A, B, C)$ of subsets of $[n]$ such that at least one of $A cap B$, $A cap C$, or $B cap C$ is empty
I got $6^ncdot 3-3cdot 5^n+4^n$, not sure if this is correct.
Please help me on this.
combinatorics
combinatorics
edited Dec 16 '18 at 20:10
t.ysn
1457
asked Dec 16 '18 at 17:08
MojicaMojica
202
edited Dec 16 '18 at 20:10
t.ysn
1457
asked Dec 16 '18 at 17:08
MojicaMojica
202
edited Dec 16 '18 at 20:10
t.ysn
1457
edited Dec 16 '18 at 20:10
t.ysn
1457
edited Dec 16 '18 at 20:10
t.ysn
1457
1457
asked Dec 16 '18 at 17:08
MojicaMojica
202
asked Dec 16 '18 at 17:08
MojicaMojica
202
asked Dec 16 '18 at 17:08
MojicaMojica
202
202
3
$begingroup$
Please explain how you got your answer. It is much easier to check work than to redo it. It is correct for $n=1$.
$endgroup$
– Ross Millikan
Dec 16 '18 at 17:42
add a comment |
3
$begingroup$
Please explain how you got your answer. It is much easier to check work than to redo it. It is correct for $n=1$.
$endgroup$
– Ross Millikan
Dec 16 '18 at 17:42
3
3
$begingroup$
Please explain how you got your answer. It is much easier to check work than to redo it. It is correct for $n=1$.
$endgroup$
– Ross Millikan
Dec 16 '18 at 17:42
$begingroup$
Please explain how you got your answer. It is much easier to check work than to redo it. It is correct for $n=1$.
$endgroup$
– Ross Millikan
Dec 16 '18 at 17:42
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I assume $[n]={1,2,ldots,n}$. For an arbitrary triples $(A,B,C)$ (not requiring anything), each $kin [n]$ can stay in one of the following list of sets:
- $[n]-(Acup Bcup C)$
- $A-(Bcup C)$
- $B-(Ccup A)$
- $C-(Acup B)$
- $Bcap C-Acap Bcap C$
- $Ccap A -Acap Bcap C$
- $Acap B-Acap Bcap C$
$Acap Bcap C$.
To meet your requirement, $k$ cannot stay in $Acap Bcap C$ and must omit one of the sets $Bcap C$, $Ccap A$, and $Acap B$.
Let $n_A$, $n_B$, and $n_C$ denote the number of triples $(A,B,C)$ s.t. each $kin [n]$ does not stay in $Bcap C$, $Ccap A$, and $Acap B$, respectively. To count $n_A$, each $k$ has only six choices from the list of sets above. That is, we have $n_A=6^n$, and likewise, $n_B=n_C=6^n$.
Now, write $n_{A,B}$ for the number of triples $(A,B,C)$ s.t. each $kin[n]$ does not stay in $Bcap C$ and $Ccap A$. Define $n_{B,C}$ and $n_{C,A}$ similarly. To count $n_{A,B}$, each $k$ has only $5$ choices from the list of sets above. That is, $n_{A,B}=5^n$, and likewise, $n_{B,C}=n_{C,A}=5^n$.
Finally, let $n_{A,B,C}$ be the number of triples $(A,B,C)$ s.t. each $[k]$ stays in none of $Bcap C$, $Ccap A$, and $Acap B$. Then each $k$ has only $4$ possible places to be in the list above. So $n_{A,B,C}=4^n$. By PIE the answer is
$$(n_A+n_B+n_C)-(n_{A,B}+n_{B,C}+n_{C,A})+n_{A,B,C}=3cdot 6^n-3cdot 5^n+4^n.$$
Your answer is correct.
$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%2f3042851%2ffind-the-number-of-triples-a-b-c-of-subsets-of-n-such-that-at-least-on%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$
I assume $[n]={1,2,ldots,n}$. For an arbitrary triples $(A,B,C)$ (not requiring anything), each $kin [n]$ can stay in one of the following list of sets:
- $[n]-(Acup Bcup C)$
- $A-(Bcup C)$
- $B-(Ccup A)$
- $C-(Acup B)$
- $Bcap C-Acap Bcap C$
- $Ccap A -Acap Bcap C$
- $Acap B-Acap Bcap C$
$Acap Bcap C$.
To meet your requirement, $k$ cannot stay in $Acap Bcap C$ and must omit one of the sets $Bcap C$, $Ccap A$, and $Acap B$.
Let $n_A$, $n_B$, and $n_C$ denote the number of triples $(A,B,C)$ s.t. each $kin [n]$ does not stay in $Bcap C$, $Ccap A$, and $Acap B$, respectively. To count $n_A$, each $k$ has only six choices from the list of sets above. That is, we have $n_A=6^n$, and likewise, $n_B=n_C=6^n$.
Now, write $n_{A,B}$ for the number of triples $(A,B,C)$ s.t. each $kin[n]$ does not stay in $Bcap C$ and $Ccap A$. Define $n_{B,C}$ and $n_{C,A}$ similarly. To count $n_{A,B}$, each $k$ has only $5$ choices from the list of sets above. That is, $n_{A,B}=5^n$, and likewise, $n_{B,C}=n_{C,A}=5^n$.
Finally, let $n_{A,B,C}$ be the number of triples $(A,B,C)$ s.t. each $[k]$ stays in none of $Bcap C$, $Ccap A$, and $Acap B$. Then each $k$ has only $4$ possible places to be in the list above. So $n_{A,B,C}=4^n$. By PIE the answer is
$$(n_A+n_B+n_C)-(n_{A,B}+n_{B,C}+n_{C,A})+n_{A,B,C}=3cdot 6^n-3cdot 5^n+4^n.$$
Your answer is correct.
$endgroup$
add a comment |
$begingroup$
I assume $[n]={1,2,ldots,n}$. For an arbitrary triples $(A,B,C)$ (not requiring anything), each $kin [n]$ can stay in one of the following list of sets:
- $[n]-(Acup Bcup C)$
- $A-(Bcup C)$
- $B-(Ccup A)$
- $C-(Acup B)$
- $Bcap C-Acap Bcap C$
- $Ccap A -Acap Bcap C$
- $Acap B-Acap Bcap C$
$Acap Bcap C$.
To meet your requirement, $k$ cannot stay in $Acap Bcap C$ and must omit one of the sets $Bcap C$, $Ccap A$, and $Acap B$.
Let $n_A$, $n_B$, and $n_C$ denote the number of triples $(A,B,C)$ s.t. each $kin [n]$ does not stay in $Bcap C$, $Ccap A$, and $Acap B$, respectively. To count $n_A$, each $k$ has only six choices from the list of sets above. That is, we have $n_A=6^n$, and likewise, $n_B=n_C=6^n$.
Now, write $n_{A,B}$ for the number of triples $(A,B,C)$ s.t. each $kin[n]$ does not stay in $Bcap C$ and $Ccap A$. Define $n_{B,C}$ and $n_{C,A}$ similarly. To count $n_{A,B}$, each $k$ has only $5$ choices from the list of sets above. That is, $n_{A,B}=5^n$, and likewise, $n_{B,C}=n_{C,A}=5^n$.
Finally, let $n_{A,B,C}$ be the number of triples $(A,B,C)$ s.t. each $[k]$ stays in none of $Bcap C$, $Ccap A$, and $Acap B$. Then each $k$ has only $4$ possible places to be in the list above. So $n_{A,B,C}=4^n$. By PIE the answer is
$$(n_A+n_B+n_C)-(n_{A,B}+n_{B,C}+n_{C,A})+n_{A,B,C}=3cdot 6^n-3cdot 5^n+4^n.$$
Your answer is correct.
$endgroup$
add a comment |
$begingroup$
I assume $[n]={1,2,ldots,n}$. For an arbitrary triples $(A,B,C)$ (not requiring anything), each $kin [n]$ can stay in one of the following list of sets:
- $[n]-(Acup Bcup C)$
- $A-(Bcup C)$
- $B-(Ccup A)$
- $C-(Acup B)$
- $Bcap C-Acap Bcap C$
- $Ccap A -Acap Bcap C$
- $Acap B-Acap Bcap C$
$Acap Bcap C$.
To meet your requirement, $k$ cannot stay in $Acap Bcap C$ and must omit one of the sets $Bcap C$, $Ccap A$, and $Acap B$.
Let $n_A$, $n_B$, and $n_C$ denote the number of triples $(A,B,C)$ s.t. each $kin [n]$ does not stay in $Bcap C$, $Ccap A$, and $Acap B$, respectively. To count $n_A$, each $k$ has only six choices from the list of sets above. That is, we have $n_A=6^n$, and likewise, $n_B=n_C=6^n$.
Now, write $n_{A,B}$ for the number of triples $(A,B,C)$ s.t. each $kin[n]$ does not stay in $Bcap C$ and $Ccap A$. Define $n_{B,C}$ and $n_{C,A}$ similarly. To count $n_{A,B}$, each $k$ has only $5$ choices from the list of sets above. That is, $n_{A,B}=5^n$, and likewise, $n_{B,C}=n_{C,A}=5^n$.
Finally, let $n_{A,B,C}$ be the number of triples $(A,B,C)$ s.t. each $[k]$ stays in none of $Bcap C$, $Ccap A$, and $Acap B$. Then each $k$ has only $4$ possible places to be in the list above. So $n_{A,B,C}=4^n$. By PIE the answer is
$$(n_A+n_B+n_C)-(n_{A,B}+n_{B,C}+n_{C,A})+n_{A,B,C}=3cdot 6^n-3cdot 5^n+4^n.$$
Your answer is correct.
$endgroup$
I assume $[n]={1,2,ldots,n}$. For an arbitrary triples $(A,B,C)$ (not requiring anything), each $kin [n]$ can stay in one of the following list of sets:
- $[n]-(Acup Bcup C)$
- $A-(Bcup C)$
- $B-(Ccup A)$
- $C-(Acup B)$
- $Bcap C-Acap Bcap C$
- $Ccap A -Acap Bcap C$
- $Acap B-Acap Bcap C$
$Acap Bcap C$.
To meet your requirement, $k$ cannot stay in $Acap Bcap C$ and must omit one of the sets $Bcap C$, $Ccap A$, and $Acap B$.
Let $n_A$, $n_B$, and $n_C$ denote the number of triples $(A,B,C)$ s.t. each $kin [n]$ does not stay in $Bcap C$, $Ccap A$, and $Acap B$, respectively. To count $n_A$, each $k$ has only six choices from the list of sets above. That is, we have $n_A=6^n$, and likewise, $n_B=n_C=6^n$.
Now, write $n_{A,B}$ for the number of triples $(A,B,C)$ s.t. each $kin[n]$ does not stay in $Bcap C$ and $Ccap A$. Define $n_{B,C}$ and $n_{C,A}$ similarly. To count $n_{A,B}$, each $k$ has only $5$ choices from the list of sets above. That is, $n_{A,B}=5^n$, and likewise, $n_{B,C}=n_{C,A}=5^n$.
Finally, let $n_{A,B,C}$ be the number of triples $(A,B,C)$ s.t. each $[k]$ stays in none of $Bcap C$, $Ccap A$, and $Acap B$. Then each $k$ has only $4$ possible places to be in the list above. So $n_{A,B,C}=4^n$. By PIE the answer is
$$(n_A+n_B+n_C)-(n_{A,B}+n_{B,C}+n_{C,A})+n_{A,B,C}=3cdot 6^n-3cdot 5^n+4^n.$$
Your answer is correct.
answered Dec 16 '18 at 20:48
user614671
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%2f3042851%2ffind-the-number-of-triples-a-b-c-of-subsets-of-n-such-that-at-least-on%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
3
$begingroup$
Please explain how you got your answer. It is much easier to check work than to redo it. It is correct for $n=1$.
$endgroup$
– Ross Millikan
Dec 16 '18 at 17:42