We give a combinatorial proof for a second order recurrence for the polynomials p_n(x), where p_n(k) counts the number of integer-coordinate lattice points x = (x₁,...,x_n) with ||x|| = \sum_{i=1}^n |x_i| = k. This is the main step to get finiteness results on the number of solutions of the diophantine equation p_n(x) = p_m(y) if n and m have different parity. The combinatorial approach also allows to extend the original diophantine result to more general combinatorial situations.