1
$\begingroup$

I think that I need to use super generating functions but I am not sure if this is correct or where to find more information.

Let's say I have a few relations where each variable $x_i \in \{0,1\}$:

$x_1+x_2+x_3+x_4 = 1 \\ x_3+x_4+x_5+x_6 \neq 1$

I want to count all possible solutions. For a single constraint I know how to use a single generating function to count all possible solutions, however, how do I link several constraints that share variables?

For instance, in the example for $x_3,x_4$: Do I need to use two generating functions? If so, then how do I connect the constraints?

Clearly, this is just a very simple example. I am trying to understand the concept, not to solve this very simple case.

$\endgroup$
  • $\begingroup$ As I said, $x_i$ can only be zero or one. The number of solutions is countable. $\endgroup$ – Juan Leni Feb 3 '17 at 15:57
0
$\begingroup$

This may not be the solution you're looking for, but it seems the right thing to do is to break your problem up into disjoint cases which allow you to break down your relations into non-overlapping components. In your example, you can break into two cases, depending on whether $x_3+x_4$ is $0$ or $1$:

If $x_3+x_4 = 0$, then your constraints look like $x_1+x_2 = 1$, $x_3+x_4 = 0$ and $x_5+x_6 \neq 1$, which you can solve with the generating function $(x_1+x_2)(1+x_5x_6)$.

If $x_3+x_4 = 1$, then your constraints are $x_1+x_2 = 0$, $x_3+x_4 = 1$ and $x_5+x_6 \ne 0$, which can be solved with the generating function $(x_3+x_4)(x_5+x_6+x_5x_6)$.

Since these solution sets are disjoint, the generating function for the entire solution is the sum of these two generating functions.

$\endgroup$
  • $\begingroup$ I was already doing something like. What I am trying to do is to avoid having to consider every possible disjoint set. Hopefully this is possible using multivariate generating functions. $\endgroup$ – Juan Leni Feb 3 '17 at 18:22
0
$\begingroup$

I'm not sure I fully understood this question.
Since every variable $a_{i}$ has two possible values, $1$ and $0$, you may simply expand this OGF: $(1+x)^4$ And see the coefficient for the term $x$, that is 4. Thus there are two possible solutions for the first equation. Solutions for the second one can be determined by counting others terms' coefficient and add them together. It is $12$.

$\endgroup$

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.