The number of subset pairs

1. Oct 20, 2016

Lilia

Mod note: Moved from a technical math forum, so missing the homework template.
Given a set A = {a1, a2, ..., an} and its two subsets - X, Y so that these subsets satisfy a condition, find the number of such possible (X, Y) pairs

Condition 1: X ∩ Y = {a1, a2},
Condition 2: X ⊆ Y,
Condition 3: | (X - Y) ∪ (Y - X) | = 1

I've tried to solve these but I still can't figure out the right way to think when solving these.

For X ∩ Y = the number of subsets is ΣC(n,k) × 2n-k, where k=0÷n.

This is how I think - so, for Condition 1, X and Y should have only a1 and a2 in common and can have other distinct elements, so we need to choose those two elements but how to choose them for both X and Y?

For Condition 2, |X| can be k, |Y| can be k (or k-1?), therefore the number of subsets - C(n,k) × C(n,k) = (C(n,k))2? Is this right?

For Condition 3, X is a subset of Y, or Y is a subset of X, and they have one element in common, right? If so, how to count the number of subsets?

Last edited by a moderator: Oct 20, 2016
2. Oct 20, 2016

Staff: Mentor

But Condition 1 says that X ∩ Y is not empty.
a1 and a2 have to be elements of both X and Y.
No, |Y| can't be k - 1.
If |Y| = k, then |X| can be at most k, but at least 2.
Condition 2 says that X is either a proper subset of Y or X = Y.
No, they have two elements in common, which is what Condition 1 says.
If X ⊂ Y, then X - Y = ∅, and Y - X would be all of the elements in Y that aren't elements of X
If X = Y, then X - Y = Y - X.

3. Oct 20, 2016

Lilia

Empty intersection wasn't a part of the problem, I just wrote that to show how I choose X and Y for a given condition (in that case - ∅)

For Condition 1, if I choose k elements for X (k≥2), then for Y I'll have to choose from n-k elements, that'll be ΣC(n,k) × 2n-k, k=2÷n. How do I say that a1 and a2 and mutual for both X and Y?

For Condition 2, I just noticed I made a mistake, I should've said |X| is maybe k-1? So if it's a subset of Y then for Y we can choose C(n,k) and for X: 2k

And for Condition 3, either X-Y or Y-X is ∅, that crossed my mind but I don't get why they have 2 elements in common? Condition 1 is a separate condition.

4. Oct 20, 2016

Staff: Mentor

Does this mean, it consists of three separate exercises instead of all conditions have to hold simultaneously?
That makes a big difference which you haven't mentioned!

5. Oct 20, 2016

Lilia

All of the three are separate conditions, I'm sorry not to have mentioned it before

6. Oct 20, 2016

Staff: Mentor

@Lilia, in the future, please post homework-type questions in the Homework & Coursework sections, not in the technical math sections. I have moved your post.

7. Oct 20, 2016

Staff: Mentor

For Condition 1, I would investigate the problem with specific numbers for the number of elements in A, such as n = 2, n = 3, n = 4, and look for a pattern.

8. Oct 20, 2016

Lilia

Okay, got it.

For Condition 1, I got ΣC(n,k+2) × 2n-k. Do I also need multiply this by C(n,2) and will that be correct?

9. Oct 21, 2016

Ray Vickson

If $X \subset Y$, do we not have $X \cap Y = X$?

10. Oct 21, 2016

Lilia

The three conditions are separate conditions, it's X ⊆ Y, so |X| can be anything from 0 to n (for n elements), and |Y| can be at most k, so I wrote ΣC(n,k) × 2n but does this ensure that the chosen Y subset contains X?

And for Condition 1 I should've written ΣC(n,k+2) × 2n-k-2, where k=0,n-2. Or C(n,2) × (∑C(n-2,k) × 2n-2-k), k=0,n-2?

Last edited: Oct 21, 2016
11. Oct 22, 2016

haruspex

Setting aside the two elements we know both must have, what conditions apply to the rest of X and Y?
No, X is a subset of Y, Y cannot be smaller. If |X|=k, how many ways are there of choosing Y?
The first statement is right, but it is not that they have one element in common. Can you draw a Venn diagram?

12. Oct 23, 2016

Lilia

Assuming that X-Y is empty, then drawing the Venn diagram - Y is a set (a circle) and X is another set (a circle) fully inside it.

And, then how many elements do they have in common?

13. Oct 23, 2016

haruspex

That's not the first question to ask here. How many elements do they have NOT in common?

Last edited: Oct 23, 2016
14. Oct 23, 2016

Lilia

That will be A-Y elements

15. Oct 23, 2016

haruspex

This is for condition 3, right? Maybe I need to be clearer. How many elements are in only one of X and Y?

16. Oct 23, 2016

Lilia

Yes it's for the 3rd condition.
If there are k elements in Y (k=0,n) and if X-Y is empty and Y-X isn't empty then Y has more elements than X so there are m=0,k-1 (or m=k-1?) elements in X?

17. Oct 23, 2016

haruspex

That is the interesting question. What do you think?
(If you are considering the case where X is the smaller, it might be simpler to work in terms of what is the size of Y given the size of X.)