How many subsets of $[20]$ have smallest element $4$ and largest element $15$?

Question

$[20] = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20\}$.

We could probably remove all $n < 4 \text { and all } n > 15$. Then the new set will have $2^ {12}$ subsets. Now I am not sure how to get rid of all subsets in $\{4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15\}$ that don't contain $4 \text { and } 15$. Then we could subtract that number of removed subsets from $2^{12}$. Or, maybe, all this is either simply wrong or inefficient. Any hints and/or comments would be appreciated.

score 1 · Answer 1 · answered Dec 27 '14 at 14:07

1

Just include $4$ and $15$ and then take every subset of $\{5, 6, \dots, 14\}$. You will have exactly $2^{10}$ subsets.

answered Dec 27 '14 at 14:07

Jihad

3,284

score 1 · Accepted Answer · answered Dec 27 '14 at 14:10

1

We remove all $n<4$ and $n>15$. That's eight elements. The new set is $\{4,5,...,15\}$, with cardinality $12$.

The subset must contain $4$ as the smallest element and $15$ as the largest element. So it must contain $4$ and $15$. Then we want to add elements to this subset: there are ten eligible elements, the set $\{5,6,...14\}$. This set has $2^{10}$ subsets, since a set with cardinality $n$ has $2^n$ subsets.

So there are $2^{10}$ satisfactory subsets.

answered Dec 27 '14 at 14:10

Newb

17,672
13
67
114

Do we take the union of ${4, 15}$ with every subset of ${5, 6 \ldots 14}$? – permutation Dec 27 '14 at 14:20
@permutation yes – Newb Dec 27 '14 at 14:44

How many subsets of $[20]$ have smallest element $4$ and largest element $15$?

2 Answers2