0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – drhab Aug 4 '17 at 10:16
  • $\begingroup$ @drhab I found out what is wrong. check my answer if interested. $\endgroup$ – parvin Aug 4 '17 at 10:18
  • $\begingroup$ @drhab you are right too . yes. $\endgroup$ – parvin Aug 4 '17 at 10:19
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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