# Combination question: Which solution is correct?

Q: There is a list of vectors $(x_1,...x_n)$ each $x_i$ is either $0$ or $1$;

Determine the number of vectors that satisfy the equation bellow: $$\sum_{i=1}^n x_i \leq k$$

so knowing that $k$ is a number greater or equal to $0$, we know we should have $k$ times $1$, so this is how I solved it:$${{n} \choose {k}} \times 2^{n-k}$$ collecting the sufficient number of $1s$ which is $k$ times $1$, by choosing $Xs$ and then multiplying them in the number of different combinations they can make with the rest of the $Xs$, the different conditions of the rest of the $Xs$ which is $2^{n-k};$ ($0$ or$1$).

but the book has solved it this way: $$\sum_{j=k}^n {{n}\choose{j}}$$ to me it's like it's choosing the number of $Xs$ considering them as $1s$ to get minimum number of k and then choosing extra $1s$ for it should be equal or greater than k, and consider the rest of not-chosen $Xs$ as $0$.

so what is what!? To me both are correct but not the same! I don't get it. What is wrong in here?

• If you have chosen a set $I$ of $k$ indices $i$ with $x_i=1$ then $i\notin I\implies x_i=0$ is necessary. So multiplying by $2^{n-k}$ is wrong. Secondly this is only the case sum$=k$, while (if $k>0$) cases where sum$<k$ must be considered too. – drhab Aug 4 '17 at 10:16
• @drhab I found out what is wrong. check my answer if interested. – parvin Aug 4 '17 at 10:18
• @drhab you are right too . yes. – parvin Aug 4 '17 at 10:19

## 1 Answer

Since there is a $1-1$ correspondence between $0-1$ vectors of length $n$ and subsets of $[1,n]$, what you are counting is the number of subsets of $[1,n]$ whose cardinality is at most $k$, and this number is clearly the sum of the first $k$ binomials, that is: $${n\choose 0}+{n\choose 1}+\cdots + {n\choose k}=\sum_{j=0}^k{n\choose j}$$ and not as you claim your text-book has written.