# Counting sets two different ways

I have been stuck on this problem and I was hopeing that someone could let me know if I am doing it right.

• k, m, n are integers
• $0 \le k \le m \le n$
• $S$ is a set of size $n$

$n \choose k$${n - k} \choose {m - k}$$=$$n\choose m$$m \choose k$

Show by counting two different ways the number of ordered pairs $(A,B)$ with $A \subseteq S$, $B \subseteq S$, $A \subseteq B$, $|A|=k$, and $|B|=m$

So I am thinking to answer this I need to just explain what the formula is counting and how it is equal to the other formula?

Here is what I got:

$n \choose k$: This is choosing $k$ elements (which is the size of A) out of the entire set $S$.

${n - k} \choose {m - k}$: Here we are choosing $m-k$ elements from the set S, but we are only choosing elements that have not yet been chosen.

And for the right side:

$n\choose m$: we are choosing m (the size of |B|) elements out of the set $S$.

$m \choose k$: we are choosing k (the size of |A|) elements out of the set B.

Am I on the right track ? Is there a better way of doing these types of problems?

• That's pretty much it. It would be good to mention what you are "choosing the elements for." You don't really make any mention of that. You also refer in the second counting to the set $B$, but you have not yet defined $B$. Note, this problem has been asked before here. In general though, the principle of counting in two ways says that if you have two mathematical expressions that both count the same thing then they must be equal. – JMoravitz Sep 23 '15 at 0:02

You’re doing fine so far, and it should be pretty clear now why $\binom{n}k\binom{m}k$ counts the specified collection of ordered pairs. The main task remaining is to explain why $\binom{n}k\binom{n-k}{m-k}$ counts that set. As you say, the first factor is the number of ways to choose the set $A$. Can you see how to interpret $\binom{n-k}{m-k}$ as the number of ways to choose the set $B$?
• Wouldn't ${m−k} \choose {m−k}$ $= 1$? – kayla Sep 23 '15 at 0:06
• @kayla: Sorry: that was a typo for $\binom{n-k}{m-k}$. I’ve fixed it and another typo now. – Brian M. Scott Sep 23 '15 at 0:10
• We are choosing $n-k$ because we have already chosen those elements from S when we did $n \choose k$. Since $A \subseteq B$ we need to the subtraction of $m-k$ so that we don't count elements twice? – kayla Sep 23 '15 at 0:14
• @kayla: We’re not choosing $n-k$ things; we’re choosing $m-k$ things from a set of $n-k$ things. The $n-k$ things are the ones that we did not choose for $A$. In terms of $A$ and $B$, what do you think the $m-k$ things that we’re choosing are? – Brian M. Scott Sep 23 '15 at 0:18
• A is a proper subset of B, so it contains fewer elements. $m - k$ is choosing the remaining elements that were not chosen when we did $n \choose k$. – kayla Sep 23 '15 at 0:27