A181496 Number of degree n polynomials p(x,y) with all coefficients 0 or 1 such that x+y=1 implies p(x,y)=1.

1, 1, 2, 5, 14, 43, 140, 474, 1648, 5839, 20980, 76202, 279168, 1029962, 3822336, 14256228, 53400912

Offset: 0

Author

Hagen von Eitzen, Oct 24 2010

Keywords

• nonn
• more

Comments

The polynomials are of the form P = (x+y-1) * Q + 1.

Examples

			For degree 0, the only solution is 1, hence a(0) = 1.
For degree 1, the only solution is x + y, hence a(1) = 1.
For degree 2 there are x^2 + x*y + y and x + x*y + y^2 (and no more), hence a(2) = 2.
For n = 3 the a(3) = 5 polynomials are x^3 + x^2 y + x y + y, x^2 y + x y^2 + x^2 + y, x^2 y + x y^2 + x^2 + x y + y^2, x y^2 + y^3 + x y + x, x^2 y + x y^2 +y^2 + x.
		

Links

• Murray S. Klamkin, Problem #3, Missouri State Math Dept. Challenge Archive, 2005/06 discusses the generalization to m variables.

Crossrefs

Cf. A122743.

Programs

PARI

padbin(n, len) = {b = binary(n); while(length(b) < len, b = concat(0, b);); b;}
a(n) = {if (n == 0, return (1)); kill(x); kill(y); poln = vector(n+1, i, x^(i-1)*y^(n-i+1)); polm = [1]; for (i = 1, n-1, polm = concat(polm, vector(i+1, j, x^(j-1)*y^(i-j+1)));); nbpol = 0; nbn = #poln; nbm = #polm; for (i = 1, 2^nbn, bi = padbin(i, nbn); poli = sum(ki = 1, nbn, bi[ki]*poln[ki]); for (j = 0, 2^nbm, bj = padbin(j, nbm); pol = poli + sum(kj = 1, nbm, bj[kj]*polm[kj]); if (subst(pol, y, 1-x) == 1, nbpol++;););); nbpol;} \\ Michel Marcus, Aug 25 2013

Extensions

a(13) from Hagen von Eitzen, Oct 25 2010

a(14)-a(16) from Artem Romanov, Jul 25 2019