|
%I #13 Jul 25 2019 09:15:58
%S 1,1,2,5,14,43,140,474,1648,5839,20980,76202,279168,1029962,3822336,
%T 14256228,53400912
%N Number of degree n polynomials p(x,y) with all coefficients 0 or 1 such that x+y=1 implies p(x,y)=1.
%C The polynomials are of the form P = (x+y-1) * Q + 1.
%H Murray S. Klamkin, <a href="http://people.missouristate.edu/lesreid/POW03_0506.html">Problem #3</a>, Missouri State Math Dept. Challenge Archive, 2005/06 discusses the generalization to m variables.
%e For degree 0, the only solution is 1, hence a(0) = 1.
%e For degree 1, the only solution is x + y, hence a(1) = 1.
%e For degree 2 there are x^2 + x*y + y and x + x*y + y^2 (and no more), hence a(2) = 2.
%e 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.
%o (PARI) padbin(n, len) = {b = binary(n); while(length(b) < len, b = concat(0, b);); b;}
%o 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
%Y Cf. A122743.
%K nonn,more
%O 0,3
%A _Hagen von Eitzen_, Oct 24 2010
%E a(13) from _Hagen von Eitzen_, Oct 25 2010
%E a(14)-a(16) from _Artem Romanov_, Jul 25 2019
|
