# 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.

-
Hint: Given a subset $B$ of $y$, each element of the $k$ elements of $y$ is either in $B$ or not in $B$. So subsets of $y$ correspond to $k$-length binary sequences. – David Mitra Feb 4 '14 at 17:11

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$.

-

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 \}$.

-

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.

-

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.$$

-