Q.1.5 - A First Course in Probability

Question

Determine the number of vectors $(x_1, ... , x_n),$such that each $x_i$is either $0$or$1$ and$\sum _{i=1}^n{x}_i\ge k$.

Step-by-Step Solution

Answer

There are $\sum _{m=k}^n\frac{n!}{m!(n-m)!}$different ways.

Step 1 Given Information.

The number of vectors $\left(x_1,\dots ,x_n\right)$is either 0 or 1and$\sum _{i=1}^n{x}_i\ge k$.

Step 2 Explanation.

The condition $\sum _{i=1}^n{x}_i\ge k$holds if and only if the vector $x=\left(x_1,\dots ,x_n\right)$has $k$or more components equal to$1$.

Let us fix that the vector shall have exactly $m$components equal to$1$. Therefore, we can arrange this collection of ones and zeros in $n !$different ways. But, because we do not want to count twice the permutations of zeros and ones among ourselves, we should divide by $m !(m-k)!$

The result follows by considering all $m$between $k$and$n$.

Step 3 Explanation.

There are $\sum _{m=k}^n\frac{n!}{m!(n-m)!}$different ways.