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

  • $\begingroup$ 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? $\endgroup$ – Ross Millikan Nov 5 '18 at 17:38
  • $\begingroup$ yeah, I meant size. And no that's not what I meant I'll try to make my question a bit more clear $\endgroup$ – QApps Nov 5 '18 at 17:43
  • $\begingroup$ I added an example, I hope it's clear now $\endgroup$ – QApps Nov 5 '18 at 17:53

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.

| cite | improve this answer | |
  • $\begingroup$ Thanks! This was a very helpful answer $\endgroup$ – QApps Nov 5 '18 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.