# Counting ordered pairs $(X,Y)$

Consider two disjoint sets $$A$$ and $$B$$ with $$|A|=|B|=8$$. Find two ways to count the number of ordered pairs $$(X,Y)$$ with $$X \subseteq A$$ and $$Y \subseteq (B \cup X)$$ with $$|Y|=8$$.

Is my guess correct?

• We have $$|B \cup X| = |B| + |X| - |B \cap X| = 8+|X|$$ (since $$A$$ and $$B$$ are disjoint, $$X \subseteq A$$). We know that $$1 \le^* |X| \le |A| = 8$$ and $$|Y| = 8 \le 8 + |X|$$.

(*We'll leave out $$|X| = 0$$, since it does not contribute to the number of ordered pairs $$(X,Y)$$).

• This results in $$16 \ge |B \cup X| \ge 9$$. So for all possible elements for $$Y$$ we do the following: $$\sum_{i=9}^{16} \binom{i}{8}$$. There are from $$1$$ through $$8$$ possible elements for $$X$$ (chosen from $$A$$): $$\sum_{k=1}^8 \binom{8}{k}$$.

• The number of ordered pairs is $$\sum_{k=1}^8 \binom{8}{k} \cdot \sum_{i=9}^{16} \binom{i}{8}$$.

I'm struggling to find another way.

• "couple" is not the right word for (a,b) in english ; it has to be replaced by "ordered pair". – Jean Marie Jan 28 at 19:43
• Thanks! I edited my post. Do you think my answer is correct, @JeanMarie? – Zachary Jan 28 at 19:49
• If I compute well, the number of such ordered pairs should be $\sum_{k=\color{red}{0}}^8 \binom{8}{k} \cdot \binom{8+k}{8}$ (the remark in red : the void set is not forbidden): without a double summation. – Jean Marie Jan 28 at 20:06