number of permutation in a boolean expression containing only ANDs and ORs

375 Views Asked by At

I need to find the number of permutations of some expression which contains only conjunctions and disjunctions e.g.: $$ e = x_1x_2 \vee x_3x_4 $$ where $x_1x_2$ and $x_3x_4$ are boolean summands, interpreted as $x_1 \wedge x_2$, $x_3 \wedge x_4$. The variables $x_1, x_2, \ldots x_4$ are the boolean factors.

I need to know the number of permutations, that such an expression can have, i.e.:

x1x2 V x3x4
x2x1 V x3x4
x1x2 V x4x3
...
x3x4 V x1x2
...

According to my calculations, my formula for the number of permutations for this type of boolean expressions is:

$$ n!(\prod_{i \in n} m_i!) $$

where $n$ is the number of boolean summands, and $m$ the number of boolean factors (in a boolean summand). I would appreciate it a lot, if you could tell me if this formula is correct, and if not, show a correct one.

thanks in advance!