1
$\begingroup$

Can someone please explain to me how this works in a little more depth? I have the question and the solution and I'm not sure why it works.

Here's the question:

Set $A$ contains $\{1, 2, 3..., 11\}$ Compute the number of subsets of length $4$ of which at least $2$ numbers are $\leq 6$.

Here's the solution:

We subtract subsets with fewer than $2$ numbers less than or equal to $6$ from the total number of $k$-subsets to get $C(n, k)−C(n−6, k)·C(6, 0)−C(n−6, k−1)·C(6, 1)$. Answer: $C(11, 4) − C(5, 4) − 6 \cdot C(5, 3)$

I don't understand why I can't simply multiply $C(6,2) \cdot C(9,2)$ ... (Choosing $2$ numbers less than $6$, and then choosing the last $2$ numbers)

Thanks!

$\endgroup$
1
  • 1
    $\begingroup$ If you choose a number twice, the subset won't be of length 4, i.e., all the numbers you choose need to be different. $\endgroup$
    – ryagami
    Apr 28, 2015 at 23:03

2 Answers 2

1
$\begingroup$

Note that your expression will count certain sets more than once. For the set $\{1,2,3,8\}$, you could first choose $1$ and $2$ before choosing $3$ and $8$. But you could also choose $2$ and $3$ before choosing $1$ and $8$.

This defect can be fixed, but it makes the expression more complicated. If there are $3$ elements from $\{1,2,3,4,5,6\}$, then the set is counted $3$ times, so we can remove the double-counting by subtracting $2\binom{6} {3}$. If all elements are $\le 6$, then the set is counted $\binom{4}{2} = 6$ times, so we can subtract $5\binom{6}{4}$. The overall result of $\binom{6}{2}\binom{9}{2} - 2\binom{6}{3} - 5\binom{6}{4}$ yields the same result as the proffered answer.

$\endgroup$
0
$\begingroup$

Your second claim $ \binom 6 2 \cdot \binom 9 2$ does not work since you are not counting $ \{1,2,3,4\} $. The first one is not clear me.

Hint

  • Consider cases: $A$ has only two elements in $\{1,2,3,4,5,6\}$, $A$ has $3$ elements less than or equal to $6$ or all four elements of $A$ are from $\{1,2,3,4,5,6\}$.

Now follow in previously travelled steps.

$\endgroup$

You must log in to answer this question.

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