Subsets and combinatorics Let $A = \{1,\ldots,n\}$. Also, consider $y$, a subset of $A$ with the size of $k$.  
What is the number of subsets, such that $x \subset y$ ($x\ne y$).  
I know the answer is $2^k-1$, but cannot see why.  
 A: Let $y = \{ y_{1},\ldots,y_{k} \}$, then for all $y_{i} \in y$: either $y_{i} \in x$ or not, i.e. we have $2^{k}$ options. However, you assme $x \neq y$, hence one option is deleted and this results in $2^{k} - 1$.
A: You are simply asking for the number of (proper) subsets of a set $B$  with $k$ elements. A handy way to see the formula is to note that there is a bijective correspondence between subsets of $B$ and functions $B \to \{ 0, 1 \}$. Clearly there are $\lvert \{ 0, 1 \} \rvert^{\lvert B \rvert} = 2^{k}$ such functions.
The correspondence sends a subset $C \subseteq B$ to its characteristic function $f$, that is, the function such that $f(x) = 1$ if and only if $x \in C$. Conversely, to a function $f : B \to \{ 0, 1 \}$ you associate the subset $C = \{ x \in B : f(x) = 1 \}$.
A: You might as well take $k=n, y=A$, because the question of the number of subsets does not depend on what the elements are.  So let.  We want all the subsets of $A$, less the one that is all of $A$.  If we include that one (which we will subtract off later) you can independently choose to have $1, 2, 3, \dots, n$, so there are $n$ binary choices, giving $2^n$ subsets.  Now subtract the one subset that is all of $A$ and you are done.
A: There are ${n \choose k}$ subsets of size $k$ taken from the elements of a set of size $n$.
So the total is
$$S(n,k) = \sum_0^{n-1} {n \choose k} = \sum_0^n {n \choose k} - 1 = 2^n - 1.$$
