# super generating functions

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.

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

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 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$$.