Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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 at 17:11
add comment

4 Answers

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.