0

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?

N. F. Taussig
  • 76,571
parvin
  • 209
  • 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 04 '17 at 10:16
  • @drhab I found out what is wrong. check my answer if interested. – parvin Aug 04 '17 at 10:18
  • @drhab you are right too . yes. – parvin Aug 04 '17 at 10:19

1 Answers1

0

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.

uniquesolution
  • 18,541