# given two sets how many ways can we choose 2 subsets of same length?

Given two sets (not neccesarily of same size), how many ways can we choose two subsets of same size, each from a different set? Order here doesn't matter and empty subsets count too, also I don't need the answer which includes binomial coefficients. I tried thinking about the Cartesian product of both sets' partitions and how we can eliminate pairs with different lengths but couldn't figure it out.

Example: given two sets {0,1} and {2,3,5} there are $${2\choose 0}*{3\choose 0}+{2\choose 1}*{3\choose 1}+{2\choose 2}*{3\choose 2}$$ possible combinations

• What do you mean by the length of a subset? Its size? So if A has six members and B has eight, there are ${6 \choose 2}{8 \choose 2}$ ways to choose two elements of A and two of B? – Ross Millikan Nov 5 '18 at 17:38
• yeah, I meant size. And no that's not what I meant I'll try to make my question a bit more clear – QApps Nov 5 '18 at 17:43
• I added an example, I hope it's clear now – QApps Nov 5 '18 at 17:53

## 1 Answer

Suppose $$|A| = n, |B| = m$$ (and that $$n \leq m$$). We want to pick a two subsets of size $$k$$, one from $$A$$ and one from $$B$$. Note that we can do this in $$\binom{n}{k} \binom{m}{k}$$ ways; summing over all $$k$$ gives $$\sum\limits_{k=0}^n \binom{n}{k} \binom{m}{k}$$.

But it turns out that there is a closed-form expression for this. Note that $$\binom{n}{k} = \binom{n}{n-k}$$. So our sum is equal to $$\sum\limits_{k=0}^n \binom{n}{n-k} \binom{m}{k}$$. In other words, how many ways can we choose $$k$$ elements of $$B$$ and $$n-k$$ elements of $$A$$ as $$k$$ ranges over all possible values? But this merely asks how many ways are there to pick $$n$$ elements from $$A \cup B$$ (assuming the sets are disjoint), which is $$\binom{m+n}{n}$$. Intuitively, this counts the number of ways to choose $$n-k$$ elements of $$A$$ to exclude and $$k$$ elements of $$B$$ to include.

• Thanks! This was a very helpful answer – QApps Nov 5 '18 at 18:07