Proper Subsets

The answer is $2^{19} - 1$ . First note that $(1+1)^n = \sum_{i=0}^{i=n} {{n}\choose{i}} = 2^{n}$ . To form all 0-element subsets, we only have ${{n}\choose{0}} = 1$ possible set (the empty set). For 1 element subsets we have ${{n}\choose{1}}$ possibilities. Continue this up to subsets containing $n-1$ elements (we would go to n-element subsets if it weren't for the restriction of the subsets being proper), and we get ${{n}\choose{n-1}}$ . Adding together all possible subsets, we get $\sum_{i=0}^{i=n-1}{{n}\choose{i}} = 2^{n} - 1$ proper subsets. In this case, it is $2^{19}-1$ since there are 19 elements in $S$ .