Calculate number of subsets
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
I want to find how many subsets $A$ contains the set $ 1,2, dots, 7 $ with the property $$(3 in A iff 2 in A).$$
The set $ 1,2, dots, 7$ has in total $2^7=128$ subsets, right?
In order to find the number of subsets $A$ with the property $(3 in A iff 2 in A)$, we have to find the number of subsets that do not contain both $2$ and $3$ and subtract the result by $128$, right?
But how do we find the number of subsets of $ 1,2, dots, 7 $ that do not conatin both $2$ and $3$ ?
probability elementary-set-theory
edited Sep 2 at 20:37
spaceisdarkgreen
29.3k21549
asked Sep 2 at 20:00
Evinda
552412
add a comment |Â
up vote
4
down vote
favorite
I want to find how many subsets $A$ contains the set $ 1,2, dots, 7 $ with the property $$(3 in A iff 2 in A).$$
The set $ 1,2, dots, 7$ has in total $2^7=128$ subsets, right?
In order to find the number of subsets $A$ with the property $(3 in A iff 2 in A)$, we have to find the number of subsets that do not contain both $2$ and $3$ and subtract the result by $128$, right?
But how do we find the number of subsets of $ 1,2, dots, 7 $ that do not conatin both $2$ and $3$ ?
probability elementary-set-theory
edited Sep 2 at 20:37
spaceisdarkgreen
29.3k21549
asked Sep 2 at 20:00
Evinda
552412
You need to find the number of subsets that contain both 2, and 3, and the number of subsets that contain neither 2, nor 3.
– amWhy
Sep 2 at 20:03
Ah yes. But how can we find these numbers of subsets? @amWhy
– Evinda
Sep 2 at 20:05
Hint: Remove $2,3$ from the set, so you are left with $5$ elements and the number of subsets of the new set is $2^5$.
– Anurag A
Sep 2 at 20:17
@AnuragA So $2^5$ is the number of subsets that contain neither 2, nor 3. The number of subsets that contain both 2, and 3 is also $2^5$ because there are two possibilities for each of the rest of the numbers, right?
– Evinda
Sep 2 at 20:21
Don't you just want to count the subsets of the form $2,3 cup X$ where $X subseteq 1,4,5,6,7$?
– steven gregory
Sep 3 at 5:16
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
I want to find how many subsets $A$ contains the set $ 1,2, dots, 7 $ with the property $$(3 in A iff 2 in A).$$
The set $ 1,2, dots, 7$ has in total $2^7=128$ subsets, right?
In order to find the number of subsets $A$ with the property $(3 in A iff 2 in A)$, we have to find the number of subsets that do not contain both $2$ and $3$ and subtract the result by $128$, right?
But how do we find the number of subsets of $ 1,2, dots, 7 $ that do not conatin both $2$ and $3$ ?
probability elementary-set-theory
edited Sep 2 at 20:37
spaceisdarkgreen
29.3k21549
asked Sep 2 at 20:00
Evinda
552412
I want to find how many subsets $A$ contains the set $ 1,2, dots, 7 $ with the property $$(3 in A iff 2 in A).$$
The set $ 1,2, dots, 7$ has in total $2^7=128$ subsets, right?
In order to find the number of subsets $A$ with the property $(3 in A iff 2 in A)$, we have to find the number of subsets that do not contain both $2$ and $3$ and subtract the result by $128$, right?
But how do we find the number of subsets of $ 1,2, dots, 7 $ that do not conatin both $2$ and $3$ ?
probability elementary-set-theory
probability elementary-set-theory
edited Sep 2 at 20:37
spaceisdarkgreen
29.3k21549
asked Sep 2 at 20:00
Evinda
552412
edited Sep 2 at 20:37
spaceisdarkgreen
29.3k21549
asked Sep 2 at 20:00
Evinda
552412
edited Sep 2 at 20:37
spaceisdarkgreen
29.3k21549
edited Sep 2 at 20:37
spaceisdarkgreen
29.3k21549
edited Sep 2 at 20:37
spaceisdarkgreen
29.3k21549
29.3k21549
asked Sep 2 at 20:00
Evinda
552412
asked Sep 2 at 20:00
Evinda
552412
asked Sep 2 at 20:00
Evinda
552412
552412
You need to find the number of subsets that contain both 2, and 3, and the number of subsets that contain neither 2, nor 3.
– amWhy
Sep 2 at 20:03
Ah yes. But how can we find these numbers of subsets? @amWhy
– Evinda
Sep 2 at 20:05
Hint: Remove $2,3$ from the set, so you are left with $5$ elements and the number of subsets of the new set is $2^5$.
– Anurag A
Sep 2 at 20:17
@AnuragA So $2^5$ is the number of subsets that contain neither 2, nor 3. The number of subsets that contain both 2, and 3 is also $2^5$ because there are two possibilities for each of the rest of the numbers, right?
– Evinda
Sep 2 at 20:21
Don't you just want to count the subsets of the form $2,3 cup X$ where $X subseteq 1,4,5,6,7$?
– steven gregory
Sep 3 at 5:16
add a comment |Â
You need to find the number of subsets that contain both 2, and 3, and the number of subsets that contain neither 2, nor 3.
– amWhy
Sep 2 at 20:03
Ah yes. But how can we find these numbers of subsets? @amWhy
– Evinda
Sep 2 at 20:05
Hint: Remove $2,3$ from the set, so you are left with $5$ elements and the number of subsets of the new set is $2^5$.
– Anurag A
Sep 2 at 20:17
@AnuragA So $2^5$ is the number of subsets that contain neither 2, nor 3. The number of subsets that contain both 2, and 3 is also $2^5$ because there are two possibilities for each of the rest of the numbers, right?
– Evinda
Sep 2 at 20:21
Don't you just want to count the subsets of the form $2,3 cup X$ where $X subseteq 1,4,5,6,7$?
– steven gregory
Sep 3 at 5:16
You need to find the number of subsets that contain both 2, and 3, and the number of subsets that contain neither 2, nor 3.
– amWhy
Sep 2 at 20:03
You need to find the number of subsets that contain both 2, and 3, and the number of subsets that contain neither 2, nor 3.
– amWhy
Sep 2 at 20:03
Ah yes. But how can we find these numbers of subsets? @amWhy
– Evinda
Sep 2 at 20:05
Ah yes. But how can we find these numbers of subsets? @amWhy
– Evinda
Sep 2 at 20:05
Hint: Remove $2,3$ from the set, so you are left with $5$ elements and the number of subsets of the new set is $2^5$.
– Anurag A
Sep 2 at 20:17
Hint: Remove $2,3$ from the set, so you are left with $5$ elements and the number of subsets of the new set is $2^5$.
– Anurag A
Sep 2 at 20:17
@AnuragA So $2^5$ is the number of subsets that contain neither 2, nor 3. The number of subsets that contain both 2, and 3 is also $2^5$ because there are two possibilities for each of the rest of the numbers, right?
– Evinda
Sep 2 at 20:21
@AnuragA So $2^5$ is the number of subsets that contain neither 2, nor 3. The number of subsets that contain both 2, and 3 is also $2^5$ because there are two possibilities for each of the rest of the numbers, right?
– Evinda
Sep 2 at 20:21
Don't you just want to count the subsets of the form $2,3 cup X$ where $X subseteq 1,4,5,6,7$?
– steven gregory
Sep 3 at 5:16
Don't you just want to count the subsets of the form $2,3 cup X$ where $X subseteq 1,4,5,6,7$?
– steven gregory
Sep 3 at 5:16
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
6
down vote
accepted
So you either want subsets that have $2$ and $3$ in or sets with neither. One way to think about this would be to consider $2$ and $3$ as a single object (which is either in or out). So then you are thinking of subsets of the following six objects: $1,2/3,4,5,6,7$.
The reasoning that you have already explained will tell you how to work out the number of subsets of this six element set.
answered Sep 2 at 20:22
Simon Terrington
41526
So there are $2$ possibilities for the numbers $1,4,5,6,7$ and thus the desired number of subsets is $2^5$, right? @SimonTerrington
– Evinda
Sep 2 at 20:29
1
@Evinda there are 2 possibilities for each of $1,4,5,6,7$ individually and then there are two possibilities for $2/3$ combined, yielding $2^6$ total, not $2^5$.
– JMoravitz
Sep 2 at 20:33
@JMoravitz Ah, I see!!!
– Evinda
Sep 2 at 20:34
1
And then $2$ possibilities for the $2/3$ object which will take you to $2^6$. This is nice because it gives the same answer as @gimusi below but just in a different way. It is basically a set of $6$ objects with $2^6$ subsets rather than (as you calculated above) the $2^7$ you subsets that you would have from a set of $7$ objects.
– Simon Terrington
Sep 2 at 20:34
1
It's a pleasure :)
– Simon Terrington
Sep 2 at 20:35
 |Â
show 1 more comment
up vote
4
down vote
As noticed in the comments we need to find the number of subsets that contain both $2$ and $3$ and the number of subsets that contain neither $2$ nor $3$.
We have that
the number of subsets with both $2$ and $3$ can be obtained by $2^5$ indeed
the number of subsets not containing $2$ nor $3$ can be obtained by $2^5$ indeed.
answered Sep 2 at 20:21
gimusi
75.4k73889
2
In the first case the empty set is not included (but the whole set is). In the second case the empty set is included (but the whole set is not).
– Simon Terrington
Sep 2 at 20:23
1
@SimonTerrington Yes of course! Thanks I've fixed that.
– gimusi
Sep 2 at 20:25
1
That's cool. Now we both get the same answer in interesting different ways :)
– Simon Terrington
Sep 2 at 20:30
1
@Evinda no, there are $2^5$ where $2$ and $3$ are both included and $2^5$ where $2$ and $3$ are both excluded. Adding these gives the total as $2^5+2^5=2cdot 2^5 = 2^6$.
– JMoravitz
Sep 2 at 20:34
1
@Evinda We have $2^5+2^5=2cdot2^5=2^6$ which agrees with the clever interpretation given by Simon.
– gimusi
Sep 2 at 20:36
 |Â
show 3 more comments
up vote
1
down vote
"we have to find the number of subsets that do not contain both 2 and
3 and subtract the result by 128, right?"
That's one way to do it. But it's probably easier to find the number of subsets that do contain both and the the number that contain neither and add those up.
The number that contain both must contain $2$ or $3$ and may or may not contain the remaining $5$ so that that is $2^5 = 32$. And the sets that contain neither may or may not contain the remaining $5$ so that is $2^5 = 32$. So there are $64$ than contain either both or neither.
We could attempt to find those that contain one or or the other but not both. There are $2$ options whether it contains $2$ or whether it contains $3$. And for the remaining $5$ there are $2^5=32$ ways it may contain any combination of those. So there are $2*32 =64$ ways it can contain one or the other but not both. ANd therefore $128 - 64 = 64$ ways it can contains both or neither.
Perhaps to make this less symmetric. Suppose it were the set $1,....,10$ and $A$ is the set that it contains $2,3$ or $4$ if and only if it contains all three. Then either it contains all three of them (there is $2^7=128$ ways this can occur) or it contains none (there are $2^7=18$ ways this can occur) so there are $128 + 128 = 256$ ways this can occur.
Alternatively we can say. There $2^7=128$ options as to whether it contains $1,5,6...$ and two options whether it contains all or none of the remaining three so there are $2*128 = 256$ ways to do this.
If we attempt to calculate how many ways it can contain $1$ or $2$ but not all $3$ and not none of the three. There are $3choose 1 =3$ ways we can choose one of $2,3,4$ and there are $3choose 2 =3$ ways we can choose two of $2,3,4$. And of the remaining seven there are $2^7 = 128$ ways to choose them so there are $(3+3)*128 = 768$ to choose one or two of $2,3,4$. And so there are $2^10 - 768 = 256$ ways to choose either all three or none.
answered Sep 2 at 22:04
fleablood
62.1k22678
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
So you either want subsets that have $2$ and $3$ in or sets with neither. One way to think about this would be to consider $2$ and $3$ as a single object (which is either in or out). So then you are thinking of subsets of the following six objects: $1,2/3,4,5,6,7$.
The reasoning that you have already explained will tell you how to work out the number of subsets of this six element set.
answered Sep 2 at 20:22
Simon Terrington
41526
So there are $2$ possibilities for the numbers $1,4,5,6,7$ and thus the desired number of subsets is $2^5$, right? @SimonTerrington
– Evinda
Sep 2 at 20:29
1
@Evinda there are 2 possibilities for each of $1,4,5,6,7$ individually and then there are two possibilities for $2/3$ combined, yielding $2^6$ total, not $2^5$.
– JMoravitz
Sep 2 at 20:33
@JMoravitz Ah, I see!!!
– Evinda
Sep 2 at 20:34
1
And then $2$ possibilities for the $2/3$ object which will take you to $2^6$. This is nice because it gives the same answer as @gimusi below but just in a different way. It is basically a set of $6$ objects with $2^6$ subsets rather than (as you calculated above) the $2^7$ you subsets that you would have from a set of $7$ objects.
– Simon Terrington
Sep 2 at 20:34
1
It's a pleasure :)
– Simon Terrington
Sep 2 at 20:35
 |Â
show 1 more comment
up vote
6
down vote
accepted
So you either want subsets that have $2$ and $3$ in or sets with neither. One way to think about this would be to consider $2$ and $3$ as a single object (which is either in or out). So then you are thinking of subsets of the following six objects: $1,2/3,4,5,6,7$.
The reasoning that you have already explained will tell you how to work out the number of subsets of this six element set.
answered Sep 2 at 20:22
Simon Terrington
41526
So there are $2$ possibilities for the numbers $1,4,5,6,7$ and thus the desired number of subsets is $2^5$, right? @SimonTerrington
– Evinda
Sep 2 at 20:29
1
@Evinda there are 2 possibilities for each of $1,4,5,6,7$ individually and then there are two possibilities for $2/3$ combined, yielding $2^6$ total, not $2^5$.
– JMoravitz
Sep 2 at 20:33
@JMoravitz Ah, I see!!!
– Evinda
Sep 2 at 20:34
1
And then $2$ possibilities for the $2/3$ object which will take you to $2^6$. This is nice because it gives the same answer as @gimusi below but just in a different way. It is basically a set of $6$ objects with $2^6$ subsets rather than (as you calculated above) the $2^7$ you subsets that you would have from a set of $7$ objects.
– Simon Terrington
Sep 2 at 20:34
1
It's a pleasure :)
– Simon Terrington
Sep 2 at 20:35
 |Â
show 1 more comment
up vote
6
down vote
accepted
up vote
6
down vote
accepted
So you either want subsets that have $2$ and $3$ in or sets with neither. One way to think about this would be to consider $2$ and $3$ as a single object (which is either in or out). So then you are thinking of subsets of the following six objects: $1,2/3,4,5,6,7$.
The reasoning that you have already explained will tell you how to work out the number of subsets of this six element set.
answered Sep 2 at 20:22
Simon Terrington
41526
So you either want subsets that have $2$ and $3$ in or sets with neither. One way to think about this would be to consider $2$ and $3$ as a single object (which is either in or out). So then you are thinking of subsets of the following six objects: $1,2/3,4,5,6,7$.
The reasoning that you have already explained will tell you how to work out the number of subsets of this six element set.
answered Sep 2 at 20:22
Simon Terrington
41526
answered Sep 2 at 20:22
Simon Terrington
41526
answered Sep 2 at 20:22
Simon Terrington
41526
answered Sep 2 at 20:22
Simon Terrington
41526
41526
So there are $2$ possibilities for the numbers $1,4,5,6,7$ and thus the desired number of subsets is $2^5$, right? @SimonTerrington
– Evinda
Sep 2 at 20:29
1
@Evinda there are 2 possibilities for each of $1,4,5,6,7$ individually and then there are two possibilities for $2/3$ combined, yielding $2^6$ total, not $2^5$.
– JMoravitz
Sep 2 at 20:33
@JMoravitz Ah, I see!!!
– Evinda
Sep 2 at 20:34
1
And then $2$ possibilities for the $2/3$ object which will take you to $2^6$. This is nice because it gives the same answer as @gimusi below but just in a different way. It is basically a set of $6$ objects with $2^6$ subsets rather than (as you calculated above) the $2^7$ you subsets that you would have from a set of $7$ objects.
– Simon Terrington
Sep 2 at 20:34
1
It's a pleasure :)
– Simon Terrington
Sep 2 at 20:35
 |Â
show 1 more comment
So there are $2$ possibilities for the numbers $1,4,5,6,7$ and thus the desired number of subsets is $2^5$, right? @SimonTerrington
– Evinda
Sep 2 at 20:29
1
@Evinda there are 2 possibilities for each of $1,4,5,6,7$ individually and then there are two possibilities for $2/3$ combined, yielding $2^6$ total, not $2^5$.
– JMoravitz
Sep 2 at 20:33
@JMoravitz Ah, I see!!!
– Evinda
Sep 2 at 20:34
1
And then $2$ possibilities for the $2/3$ object which will take you to $2^6$. This is nice because it gives the same answer as @gimusi below but just in a different way. It is basically a set of $6$ objects with $2^6$ subsets rather than (as you calculated above) the $2^7$ you subsets that you would have from a set of $7$ objects.
– Simon Terrington
Sep 2 at 20:34
1
It's a pleasure :)
– Simon Terrington
Sep 2 at 20:35
So there are $2$ possibilities for the numbers $1,4,5,6,7$ and thus the desired number of subsets is $2^5$, right? @SimonTerrington
– Evinda
Sep 2 at 20:29
So there are $2$ possibilities for the numbers $1,4,5,6,7$ and thus the desired number of subsets is $2^5$, right? @SimonTerrington
– Evinda
Sep 2 at 20:29
1
1
@Evinda there are 2 possibilities for each of $1,4,5,6,7$ individually and then there are two possibilities for $2/3$ combined, yielding $2^6$ total, not $2^5$.
– JMoravitz
Sep 2 at 20:33
@Evinda there are 2 possibilities for each of $1,4,5,6,7$ individually and then there are two possibilities for $2/3$ combined, yielding $2^6$ total, not $2^5$.
– JMoravitz
Sep 2 at 20:33
@JMoravitz Ah, I see!!!
– Evinda
Sep 2 at 20:34
@JMoravitz Ah, I see!!!
– Evinda
Sep 2 at 20:34
1
1
And then $2$ possibilities for the $2/3$ object which will take you to $2^6$. This is nice because it gives the same answer as @gimusi below but just in a different way. It is basically a set of $6$ objects with $2^6$ subsets rather than (as you calculated above) the $2^7$ you subsets that you would have from a set of $7$ objects.
– Simon Terrington
Sep 2 at 20:34
And then $2$ possibilities for the $2/3$ object which will take you to $2^6$. This is nice because it gives the same answer as @gimusi below but just in a different way. It is basically a set of $6$ objects with $2^6$ subsets rather than (as you calculated above) the $2^7$ you subsets that you would have from a set of $7$ objects.
– Simon Terrington
Sep 2 at 20:34
1
1
It's a pleasure :)
– Simon Terrington
Sep 2 at 20:35
It's a pleasure :)
– Simon Terrington
Sep 2 at 20:35
 |Â
show 1 more comment
up vote
4
down vote
As noticed in the comments we need to find the number of subsets that contain both $2$ and $3$ and the number of subsets that contain neither $2$ nor $3$.
We have that
the number of subsets with both $2$ and $3$ can be obtained by $2^5$ indeed
the number of subsets not containing $2$ nor $3$ can be obtained by $2^5$ indeed.
answered Sep 2 at 20:21
gimusi
75.4k73889
2
In the first case the empty set is not included (but the whole set is). In the second case the empty set is included (but the whole set is not).
– Simon Terrington
Sep 2 at 20:23
1
@SimonTerrington Yes of course! Thanks I've fixed that.
– gimusi
Sep 2 at 20:25
1
That's cool. Now we both get the same answer in interesting different ways :)
– Simon Terrington
Sep 2 at 20:30
1
@Evinda no, there are $2^5$ where $2$ and $3$ are both included and $2^5$ where $2$ and $3$ are both excluded. Adding these gives the total as $2^5+2^5=2cdot 2^5 = 2^6$.
– JMoravitz
Sep 2 at 20:34
1
@Evinda We have $2^5+2^5=2cdot2^5=2^6$ which agrees with the clever interpretation given by Simon.
– gimusi
Sep 2 at 20:36
 |Â
show 3 more comments
up vote
4
down vote
As noticed in the comments we need to find the number of subsets that contain both $2$ and $3$ and the number of subsets that contain neither $2$ nor $3$.
We have that
the number of subsets with both $2$ and $3$ can be obtained by $2^5$ indeed
the number of subsets not containing $2$ nor $3$ can be obtained by $2^5$ indeed.
answered Sep 2 at 20:21
gimusi
75.4k73889
2
In the first case the empty set is not included (but the whole set is). In the second case the empty set is included (but the whole set is not).
– Simon Terrington
Sep 2 at 20:23
1
@SimonTerrington Yes of course! Thanks I've fixed that.
– gimusi
Sep 2 at 20:25
1
That's cool. Now we both get the same answer in interesting different ways :)
– Simon Terrington
Sep 2 at 20:30
1
@Evinda no, there are $2^5$ where $2$ and $3$ are both included and $2^5$ where $2$ and $3$ are both excluded. Adding these gives the total as $2^5+2^5=2cdot 2^5 = 2^6$.
– JMoravitz
Sep 2 at 20:34
1
@Evinda We have $2^5+2^5=2cdot2^5=2^6$ which agrees with the clever interpretation given by Simon.
– gimusi
Sep 2 at 20:36
 |Â
show 3 more comments
up vote
4
down vote
up vote
4
down vote
As noticed in the comments we need to find the number of subsets that contain both $2$ and $3$ and the number of subsets that contain neither $2$ nor $3$.
We have that
the number of subsets with both $2$ and $3$ can be obtained by $2^5$ indeed
the number of subsets not containing $2$ nor $3$ can be obtained by $2^5$ indeed.
answered Sep 2 at 20:21
gimusi
75.4k73889
As noticed in the comments we need to find the number of subsets that contain both $2$ and $3$ and the number of subsets that contain neither $2$ nor $3$.
We have that
the number of subsets with both $2$ and $3$ can be obtained by $2^5$ indeed
the number of subsets not containing $2$ nor $3$ can be obtained by $2^5$ indeed.
answered Sep 2 at 20:21
gimusi
75.4k73889
edited Sep 2 at 20:24
answered Sep 2 at 20:21
gimusi
75.4k73889
answered Sep 2 at 20:21
gimusi
75.4k73889
answered Sep 2 at 20:21
gimusi
75.4k73889
75.4k73889
2
In the first case the empty set is not included (but the whole set is). In the second case the empty set is included (but the whole set is not).
– Simon Terrington
Sep 2 at 20:23
1
@SimonTerrington Yes of course! Thanks I've fixed that.
– gimusi
Sep 2 at 20:25
1
That's cool. Now we both get the same answer in interesting different ways :)
– Simon Terrington
Sep 2 at 20:30
1
@Evinda no, there are $2^5$ where $2$ and $3$ are both included and $2^5$ where $2$ and $3$ are both excluded. Adding these gives the total as $2^5+2^5=2cdot 2^5 = 2^6$.
– JMoravitz
Sep 2 at 20:34
1
@Evinda We have $2^5+2^5=2cdot2^5=2^6$ which agrees with the clever interpretation given by Simon.
– gimusi
Sep 2 at 20:36
 |Â
show 3 more comments
2
In the first case the empty set is not included (but the whole set is). In the second case the empty set is included (but the whole set is not).
– Simon Terrington
Sep 2 at 20:23
1
@SimonTerrington Yes of course! Thanks I've fixed that.
– gimusi
Sep 2 at 20:25
1
That's cool. Now we both get the same answer in interesting different ways :)
– Simon Terrington
Sep 2 at 20:30
1
@Evinda no, there are $2^5$ where $2$ and $3$ are both included and $2^5$ where $2$ and $3$ are both excluded. Adding these gives the total as $2^5+2^5=2cdot 2^5 = 2^6$.
– JMoravitz
Sep 2 at 20:34
1
@Evinda We have $2^5+2^5=2cdot2^5=2^6$ which agrees with the clever interpretation given by Simon.
– gimusi
Sep 2 at 20:36
2
2
In the first case the empty set is not included (but the whole set is). In the second case the empty set is included (but the whole set is not).
– Simon Terrington
Sep 2 at 20:23
In the first case the empty set is not included (but the whole set is). In the second case the empty set is included (but the whole set is not).
– Simon Terrington
Sep 2 at 20:23
1
1
@SimonTerrington Yes of course! Thanks I've fixed that.
– gimusi
Sep 2 at 20:25
@SimonTerrington Yes of course! Thanks I've fixed that.
– gimusi
Sep 2 at 20:25
1
1
That's cool. Now we both get the same answer in interesting different ways :)
– Simon Terrington
Sep 2 at 20:30
That's cool. Now we both get the same answer in interesting different ways :)
– Simon Terrington
Sep 2 at 20:30
1
1
@Evinda no, there are $2^5$ where $2$ and $3$ are both included and $2^5$ where $2$ and $3$ are both excluded. Adding these gives the total as $2^5+2^5=2cdot 2^5 = 2^6$.
– JMoravitz
Sep 2 at 20:34
@Evinda no, there are $2^5$ where $2$ and $3$ are both included and $2^5$ where $2$ and $3$ are both excluded. Adding these gives the total as $2^5+2^5=2cdot 2^5 = 2^6$.
– JMoravitz
Sep 2 at 20:34
1
1
@Evinda We have $2^5+2^5=2cdot2^5=2^6$ which agrees with the clever interpretation given by Simon.
– gimusi
Sep 2 at 20:36
@Evinda We have $2^5+2^5=2cdot2^5=2^6$ which agrees with the clever interpretation given by Simon.
– gimusi
Sep 2 at 20:36
 |Â
show 3 more comments
up vote
1
down vote
"we have to find the number of subsets that do not contain both 2 and
3 and subtract the result by 128, right?"
That's one way to do it. But it's probably easier to find the number of subsets that do contain both and the the number that contain neither and add those up.
The number that contain both must contain $2$ or $3$ and may or may not contain the remaining $5$ so that that is $2^5 = 32$. And the sets that contain neither may or may not contain the remaining $5$ so that is $2^5 = 32$. So there are $64$ than contain either both or neither.
We could attempt to find those that contain one or or the other but not both. There are $2$ options whether it contains $2$ or whether it contains $3$. And for the remaining $5$ there are $2^5=32$ ways it may contain any combination of those. So there are $2*32 =64$ ways it can contain one or the other but not both. ANd therefore $128 - 64 = 64$ ways it can contains both or neither.
Perhaps to make this less symmetric. Suppose it were the set $1,....,10$ and $A$ is the set that it contains $2,3$ or $4$ if and only if it contains all three. Then either it contains all three of them (there is $2^7=128$ ways this can occur) or it contains none (there are $2^7=18$ ways this can occur) so there are $128 + 128 = 256$ ways this can occur.
Alternatively we can say. There $2^7=128$ options as to whether it contains $1,5,6...$ and two options whether it contains all or none of the remaining three so there are $2*128 = 256$ ways to do this.
If we attempt to calculate how many ways it can contain $1$ or $2$ but not all $3$ and not none of the three. There are $3choose 1 =3$ ways we can choose one of $2,3,4$ and there are $3choose 2 =3$ ways we can choose two of $2,3,4$. And of the remaining seven there are $2^7 = 128$ ways to choose them so there are $(3+3)*128 = 768$ to choose one or two of $2,3,4$. And so there are $2^10 - 768 = 256$ ways to choose either all three or none.
answered Sep 2 at 22:04
fleablood
62.1k22678
add a comment |Â
up vote
1
down vote
"we have to find the number of subsets that do not contain both 2 and
3 and subtract the result by 128, right?"
That's one way to do it. But it's probably easier to find the number of subsets that do contain both and the the number that contain neither and add those up.
The number that contain both must contain $2$ or $3$ and may or may not contain the remaining $5$ so that that is $2^5 = 32$. And the sets that contain neither may or may not contain the remaining $5$ so that is $2^5 = 32$. So there are $64$ than contain either both or neither.
We could attempt to find those that contain one or or the other but not both. There are $2$ options whether it contains $2$ or whether it contains $3$. And for the remaining $5$ there are $2^5=32$ ways it may contain any combination of those. So there are $2*32 =64$ ways it can contain one or the other but not both. ANd therefore $128 - 64 = 64$ ways it can contains both or neither.
Perhaps to make this less symmetric. Suppose it were the set $1,....,10$ and $A$ is the set that it contains $2,3$ or $4$ if and only if it contains all three. Then either it contains all three of them (there is $2^7=128$ ways this can occur) or it contains none (there are $2^7=18$ ways this can occur) so there are $128 + 128 = 256$ ways this can occur.
Alternatively we can say. There $2^7=128$ options as to whether it contains $1,5,6...$ and two options whether it contains all or none of the remaining three so there are $2*128 = 256$ ways to do this.
If we attempt to calculate how many ways it can contain $1$ or $2$ but not all $3$ and not none of the three. There are $3choose 1 =3$ ways we can choose one of $2,3,4$ and there are $3choose 2 =3$ ways we can choose two of $2,3,4$. And of the remaining seven there are $2^7 = 128$ ways to choose them so there are $(3+3)*128 = 768$ to choose one or two of $2,3,4$. And so there are $2^10 - 768 = 256$ ways to choose either all three or none.
answered Sep 2 at 22:04
fleablood
62.1k22678
add a comment |Â
up vote
1
down vote
up vote
1
down vote
"we have to find the number of subsets that do not contain both 2 and
3 and subtract the result by 128, right?"
That's one way to do it. But it's probably easier to find the number of subsets that do contain both and the the number that contain neither and add those up.
The number that contain both must contain $2$ or $3$ and may or may not contain the remaining $5$ so that that is $2^5 = 32$. And the sets that contain neither may or may not contain the remaining $5$ so that is $2^5 = 32$. So there are $64$ than contain either both or neither.
We could attempt to find those that contain one or or the other but not both. There are $2$ options whether it contains $2$ or whether it contains $3$. And for the remaining $5$ there are $2^5=32$ ways it may contain any combination of those. So there are $2*32 =64$ ways it can contain one or the other but not both. ANd therefore $128 - 64 = 64$ ways it can contains both or neither.
Perhaps to make this less symmetric. Suppose it were the set $1,....,10$ and $A$ is the set that it contains $2,3$ or $4$ if and only if it contains all three. Then either it contains all three of them (there is $2^7=128$ ways this can occur) or it contains none (there are $2^7=18$ ways this can occur) so there are $128 + 128 = 256$ ways this can occur.
Alternatively we can say. There $2^7=128$ options as to whether it contains $1,5,6...$ and two options whether it contains all or none of the remaining three so there are $2*128 = 256$ ways to do this.
If we attempt to calculate how many ways it can contain $1$ or $2$ but not all $3$ and not none of the three. There are $3choose 1 =3$ ways we can choose one of $2,3,4$ and there are $3choose 2 =3$ ways we can choose two of $2,3,4$. And of the remaining seven there are $2^7 = 128$ ways to choose them so there are $(3+3)*128 = 768$ to choose one or two of $2,3,4$. And so there are $2^10 - 768 = 256$ ways to choose either all three or none.
answered Sep 2 at 22:04
fleablood
62.1k22678
"we have to find the number of subsets that do not contain both 2 and
3 and subtract the result by 128, right?"
That's one way to do it. But it's probably easier to find the number of subsets that do contain both and the the number that contain neither and add those up.
The number that contain both must contain $2$ or $3$ and may or may not contain the remaining $5$ so that that is $2^5 = 32$. And the sets that contain neither may or may not contain the remaining $5$ so that is $2^5 = 32$. So there are $64$ than contain either both or neither.
We could attempt to find those that contain one or or the other but not both. There are $2$ options whether it contains $2$ or whether it contains $3$. And for the remaining $5$ there are $2^5=32$ ways it may contain any combination of those. So there are $2*32 =64$ ways it can contain one or the other but not both. ANd therefore $128 - 64 = 64$ ways it can contains both or neither.
Perhaps to make this less symmetric. Suppose it were the set $1,....,10$ and $A$ is the set that it contains $2,3$ or $4$ if and only if it contains all three. Then either it contains all three of them (there is $2^7=128$ ways this can occur) or it contains none (there are $2^7=18$ ways this can occur) so there are $128 + 128 = 256$ ways this can occur.
Alternatively we can say. There $2^7=128$ options as to whether it contains $1,5,6...$ and two options whether it contains all or none of the remaining three so there are $2*128 = 256$ ways to do this.
If we attempt to calculate how many ways it can contain $1$ or $2$ but not all $3$ and not none of the three. There are $3choose 1 =3$ ways we can choose one of $2,3,4$ and there are $3choose 2 =3$ ways we can choose two of $2,3,4$. And of the remaining seven there are $2^7 = 128$ ways to choose them so there are $(3+3)*128 = 768$ to choose one or two of $2,3,4$. And so there are $2^10 - 768 = 256$ ways to choose either all three or none.
answered Sep 2 at 22:04
fleablood
62.1k22678
answered Sep 2 at 22:04
fleablood
62.1k22678
answered Sep 2 at 22:04
fleablood
62.1k22678
answered Sep 2 at 22:04
fleablood
62.1k22678
62.1k22678
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2903157%2fcalculate-number-of-subsets%23new-answer', 'question_page');
);
Post as a guest
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
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
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
You need to find the number of subsets that contain both 2, and 3, and the number of subsets that contain neither 2, nor 3.
– amWhy
Sep 2 at 20:03
Ah yes. But how can we find these numbers of subsets? @amWhy
– Evinda
Sep 2 at 20:05
Hint: Remove $2,3$ from the set, so you are left with $5$ elements and the number of subsets of the new set is $2^5$.
– Anurag A
Sep 2 at 20:17
@AnuragA So $2^5$ is the number of subsets that contain neither 2, nor 3. The number of subsets that contain both 2, and 3 is also $2^5$ because there are two possibilities for each of the rest of the numbers, right?
– Evinda
Sep 2 at 20:21
Don't you just want to count the subsets of the form $2,3 cup X$ where $X subseteq 1,4,5,6,7$?
– steven gregory
Sep 3 at 5:16