Counting positive integer linear inequality solutions with constraints

253 Views Asked by At

The context is Project Euler #600, counting equiangular hexagons.

My approach is to first count solutions without congruence/symmetry and then try Burnside's lemma for congruences. The number of hexagons is the number of positive integer solutions (for fixed $n$) to $$a + b + c + d + e + f \le n$$ with constraints $$a+b=d+e$$ $$b+c=e+f$$ (constraint $c+d = f+a$ is redundant). Inequality can be turned into equality with a slack variable, and positive integers can be turned into non-negative integers by subtracting 1: $$a'+b'+c'+d'+e'+f'+s=n-6$$ But how can the constraints be incorporated into one equality over non-negative integers for a generating function counting approach? I can do a substitution like $e = a + b - d, f= c+d-a$, but this doesn't preserve the constraints $e,f \ge 1$. I think it is possible by introducing more variables but I don't see how.

WolframAlpha suggests $a'=v+w, \ b'=x+y,\ c'=v+z,\ d'=w+x,\ e'=v+y, \ f' = x+z$ but I don't know how it arrived at this. It also seems to over-count solutions: The coefficient of $x^{12}$ in g.f. $x^6 / ((1-x^3)^2 (1-x^2)^3 (1-x))$ is 31, but I count only 30 solutions with a brute-force program.

Update: I'm not sure why I didn't check this earlier, but $a+b+c+d+e+f=n$ is A053090(n-3). I'm still looking for a combintorial explanation of the generating function or formula.

1

There are 1 best solutions below

0
On BEST ANSWER

The parameterization is given by Jianing Song in the OEIS link and is actually quite simple. The constraints imply an invariant $t$ $$ a-d = e-b = c-f = t $$

He considers cases $t \ge 0, t \le 0, t = 0$. It's similar to consider disjoint cases $t > 0, t < 0, t= 0$.

Suppose $t > 0$. Then naturally $a = d+t, e = b+t, c=f+t$. The solutions to $2b + 2d + 2f + 3t \le n$ can be re-parameterized as non-negative solutions to $2b' + 2d' + 2f' + 3t' + s = n-9$. Symmetric for $t < 0$.

For case $t=0$, we have $a = d, b = e, c = f$, so similarly we count positive solutions to $2a + 2b + 2c \le n$.

The final generating function is $$ \frac{2 x^9}{(1-x^2)^3(1-x^3)(1-x)} + \frac{x^6}{(1-x^2)^3(1-x)} = \frac{x^6 + x^9}{(1-x^2)^3(1-x^3)(1-x)} $$


All hexagons with congruence are uniquely parameterized from $b \le d \le f, t \ge 0$. (If $t < 0$, swap $(a,d), (b,e), (c,f)$ in a 180 deg rotation). Parameterize $d = b + y, f = d + z = b + y + z$. Then $$a + b + c + d + e + f = 6b + 4y + 2z + 3t \le n$$ Equivalently, the non-negative solutions to $$6b' + 4y + 2z + 3t + s = n-6$$ The final generating function is $$\frac{x^6}{(1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^6)}$$