# 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.)