1
$\begingroup$

I've been going crazy trying to solve this. The question asks

For some $0 \le r \le k \le n$, how many subsets of {1...n} have r elements in common with the set {1..k}. Describe two sets S and T such that the answer to the questions is the cardinality of the Cartesian product S x T, and then determine what is the answer.

Example Let r = 2, k = 3, and n = 5. Then we have to find the number of subsets of {1,2,3,4,5} that have 2 elements in common with the set {1,2,3}. The subsets of {1,2,3,4,5} are

$$\emptyset$$ $$(1) (2) (3) (4) (5)$$ $$(1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5)$$ $$(1,2,3) (1,2,4) (1,2,5) (1,3,4) (1,3,5) (1,4,5) (2,3,4) (2,3,5) (2,4,5) (3,4,5)$$ $$(1,2,3,4) (1,2,3,5) (1,2,4,5) (1,3,4,5) (2,3,4,5)$$ $$(1,2,3,4,5)$$

I can see some patterns here but I have no idea how to express the answer mathematically. Furthermore, I don't' know what this has to do with the Cartesian product of S and T. Any help would be appreciated. Thanks

$\endgroup$
3
$\begingroup$

We want to find the number of subsets of $\{1,\ldots,n\}$ that have $r$ elements in common with the set $\{1,\ldots, k\}$, where $r \le k \le n$. The number of ways to choose such a subset is the number of ways to choose $r$ elements from $\{1,\ldots,k\}$ times the number of ways to choose which elements to include from the remaining set $\{k+1,k+2,\ldots,n\}$. The former is ${k \choose r}$ and the latter is $2^{n-k}$. Hence, the total number of subsets in question is the product ${k \choose r} \cdot 2^{n-k}$.

Recall that the cardinality of $|S \times T|$ is the product $|S| \cdot |T|$. So we can define $S$ and $T$ to be sets having cardinality ${k \choose r}$ and $2^{n-k}$, respectively. Can you define these two sets?

$\endgroup$
3
  • $\begingroup$ Thank you for the answer.. It really helped. I think you defined S and T above. Or am I not understanding this correctly? $\endgroup$ Jun 19 '16 at 12:59
  • $\begingroup$ The answer gives the sizes of the sets, that is $|S| = \binom{k}{r}$ and $|T| = 2^{n-k}$. However, the sets themselves have not been (explicitly) defined. $\endgroup$
    – Shagnik
    Jun 19 '16 at 16:05
  • $\begingroup$ $S$ would be the set of all $r$-element subsets of $\{1,\ldots,k\}$. $T$ would be the set of all subsets of $\{k+1,\ldots,n\}$. $\endgroup$ Jun 20 '16 at 8:06

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.