Answer to Question #120099 in Discrete Mathematics for Shweta

Question

A company wants to select no more than 2 projects from a set of 4 possible projects. Which of the following constraints ensures that no more than 2 will be selected, assuming that the P variables are binary and represent whether a project is selected (value of 1) or not (value of 0)?

Answer 1

Let, the four projects be $x_1,x_2,x_3,x_4$

Hence,The number of ways in which company will select no more than 2 projects out of 4 is equivalent to finding the number of non zero integer solution which satisfy the following constraint,thus

$$x_1+x_2+x_3+x_4\leq2$$

where,

$$x_i\in \{0,1\} \: \forall i\in\{1,2,3,4\}$$

To find the number of non zero integer solution, we can introduce a dummy variable $2\geq t\geq 0$ such that

$$x_1+x_2+x_3+x_4+t=2$$

As, each $x_i$ has two value,thus it has contribution of $1+x$ equally and t contributes $(1+x+x^2)$ ,hence we have to find the coefficient of $x^2$ in the expansion of $(1+x)^4(1+x+x^2)$ will give the number of possible solution and which is

$$1+{4\choose 1}+{4\choose 2}=11$$