Determine the number of vectors

math2009 · #1 $Old$ May 29th, 2009, 07:24 PM

Determine the number of vectors $\begin {bmatrix} x_1 \\ \cdots \\ x_n \end {bmatrix}$ , such that each $x_i$ is either 0 or 1 and $\sum _{i=1}^{n} {x_i} \geq k$

CaptainBlack · #2 $Old$ May 30th, 2009, 01:48 AM

Quote:

Originally Posted by math2009 $View Post$

Determine the number of vectors $\begin {bmatrix} x_1 \\ \cdots \\ x_n \end {bmatrix}$ , such that each $x_i$ is either 0 or 1 and $\sum _{i=1}^{n} {x_i} \geq k$

This is equivalent to finding the probability of $k$ or more successes in $n$ Bernoulli trials with probability of successes $0.5$ , then multiplying by the total number of such vectors.

CB

math2009 · #3 $Old$ May 30th, 2009, 05:36 PM

I mean to count quantity of possbile vectors
if k=1,then $\sum _{i=1}^{n} {x_i} \geq 1$ . There are $( \begin{array}{ccc} n \\ 1 \end{array} ) 2^{n-1}$ vectors

I don't confirm whether to be right

CaptainBlack · #4 $Old$ May 30th, 2009, 11:43 PM

Quote:

Originally Posted by math2009 $View Post$

I mean to count quantity of possbile vectors
if k=1,then $\sum _{i=1}^{n} {x_i} \geq 1$ . There are $( \begin{array}{ccc} n \\ 1 \end{array} ) 2^{n-1}$ vectors

I don't confirm whether to be right

There are a total of $2^n$ such binary vectors, and of these $1$ such that $\sum _{i=1}^{n} {x_i} < 1$ , that is the vector with all zeros. Therefore the total number of binary vectors for which $\sum _{i=1}^{n} {x_i} \geq 1$ is $2^n-1$ .

CB