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$

1 Answer 1

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$ Commented Jun 19, 2016 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
    Commented Jun 19, 2016 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$ Commented Jun 20, 2016 at 8:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .