1
$\begingroup$

Consider $x_i$, with $i=1,\ldots, 10$, such that $$ 5 \leq 3(x_1 + x_2 + x_3 + x_4) +2(x_5 + x_6 + x_7 + x_8 + x_9 + x_{10}) \leq 12\,, $$ where each $x_i$ can be either $0$ or $1$. In addition, each $x_i$ from $i=5$ to $10$ are restricted to be $0$ if some of the $x_i$ from $i=1$ to $4$ are equal to $1$, according to the following diagram:

enter image description here

Each $x_i$ in the bottom line is restricted by two of the $x_i$ in the top line. For example, if $x_1 = x_2 = 0$, then $x_5$ can be either $0$ or $1$, but if $x_1=1$ and/or $x_2 = 1$, then $x_5=0$ necessarily. The problem is to know in how many ways can we satisfy the inequality, subjected to these restrictions, using a method which is easily used for a computer, like generating functions, for example.

The way I'm trying to answer this is the following: if the additional restrictions did not exist, the number of solutions would be obtainable by using the generating function $$ (1+x^3)^4 (1+x^2)^6 $$ and the solution would be the sum of all coefficients from $x^5$ to $x^{12}$. The restrictions can be incorporated by defining $x^c_i$ such that, in the case of $i=5$ for example, $$ x^c_5 = \quad \left\{ \begin{array}{lll} 0, \quad \, \textrm{if} \quad (1-x_1)(1-x_2)=0 \\ \\ x_5, \quad \, \textrm{if} \quad (1-x_1)(1-x_2)=1 \\ \end{array} \right. \,, $$ and so on for the other variables. Using these $x^c_i$ in the inequality, instead of the $x_i$ (for $i=5$ up to $10$), we have $$ 5 \leq 3(x_1 + x_2 + x_3 + x_4) +2(x^c_5 + x^c_6 + x^c_7 + x^c_8 + x^c_9 + x^c_{10}) \leq 12 $$ which in principle should contain all the restricted possibilities. This is where I'm currently stuck, as I don't know how the generating function for this inequality should be built.

$\endgroup$
  • $\begingroup$ Not the approach you are pursuing, but just building the characteristic function of the set yields a count of 87. $\endgroup$ – Fabio Somenzi Feb 23 '17 at 18:52
  • $\begingroup$ Thanks for the reply! I'm not sure what you mean by characteristic function of the set though, could you be more specific as how you did it? $\endgroup$ – GKiu Feb 23 '17 at 20:15
  • $\begingroup$ The characteristic function I referred to is a function of Boolean variables $x_1,\ldots,x_{10}$ that evaluates to true if and only if the constraints are all satisfied. It can be built as the conjunction of characteristic functions for the individual constraints. The incompatibility constraints are simple: for example $\neg x_5 \vee (\neg x_1 \wedge \neg x_2)$. The linear inequalities are a bit more complicated, but not much. Of course, I let the computer take the conjunctions and count the models. $\endgroup$ – Fabio Somenzi Feb 23 '17 at 21:31
  • $\begingroup$ Although this works, I was looking for an answer in terms of generating functions like @Jeremy Dover suggested, but thank you for the clarification nonetheless. $\endgroup$ – GKiu Feb 24 '17 at 19:09
  • $\begingroup$ Understood. That's why I posted a comment and not an answer. $\endgroup$ – Fabio Somenzi Feb 24 '17 at 19:45
2
$\begingroup$

This only really works because of the symmetry between the variables $x_1 \ldots x_4$ and $x_5 \ldots x_{10}$, but I think you can build a generating function this way:

If none of the $x_1 \ldots x_4$ are 1, then any of the $x_5 \ldots x_{10}$ can be 0 or 1 freely, so we get the generating function $(1+x^2)^6$ to count these solutions.

If exactly one of the $x_1 \ldots x_4$ is 1, then three of the $x_5 \ldots x_{10}$ must be zero, but the remainder are free, yielding the generating function $4x^3(1+x^2)^3$.

If exactly two of the $x_1 \ldots x_4$ are 1, then five of the $x_5 \ldots x_{10}$ must be zero with only one free, so we get the generating function $6x^6(1+x^2)$.

If three or four of the $x_1 \ldots x_4$ are 1, then all of the $x_5 \ldots x_{10}$ must be zero, so we get the generating function $4x^9+x^{12}$.

We can add all of these up to get the generating function: $$(1+x^2)^6 + 4x^3(1+x^2)^3 + 6x^6(1+x^2) + 4x^9+x^{12}$$ Like @Fabio Somenzi, when I calculate I also find 87 to be the answer.

$\endgroup$
  • $\begingroup$ Thank you very much for your answer! This is exactly what I was looking for. $\endgroup$ – GKiu Feb 24 '17 at 19:07

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.