Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.