%I #76 Sep 22 2023 11:26:09
%S 1,4,6,21,45,144,378,1161,3321,10044,29646,89181,266085,798984,
%T 2392578,7179921,21526641,64586484,193720086,581179941,1743421725,
%U 5230324224,15690618378,47072032281,141215033961,423645633324,1270933711326,3812802728301,11438398618965,34315200639864
%N Number of inequivalent height 1 degree n polynomials with nonzero constant term.
%C A height 1 degree n polynomial p(x) is considered equivalent to -p(x), p(-x), x^n * p(1/x). Together, these transformations (polynomial negation, variable negation, variable inversion) generate an equivalence relationship among height 1 degree n polynomials with nonzero constant term. Two equivalent polynomials have equivalent factorizations.
%C If we consider only monic polynomials, equivalence classes can comprise 1, 2, or 4 different polynomials.
%C Proof for n = 2k+1: There are 2*3^2k monic degree n height 1 polynomials with nonzero constant term. Of those, 2*3^k are transformed to themselves by p(0)*x^n*p(1/x). For odd degree monic polynomials, that is the only equivalence transformation that has a fixed point. The number of equivalence classes is thus 2*3^k/2 + (2*3^2k-2*3^k)/4 = 3^k*(3^k+1)/2.
%C Proof for n = 2k+2:
%C Let T be the set of monic height 1 degree-n polynomials with nonzero constant term.
%C Let V be the subset for which p(0)*x^n*p(1/x) = p(x).
%C Let N be the subset for which p(-x) = p(x).
%C Let G be the subset for which p(0)*x^n*p(-1/x) = p(x).
%C Let A be the intersection of V, N, and G.
%C A comprises the elements of T in 1-element equivalence classes.
%C V-A, N-A, and G-A are disjoint. Their union comprises the elements of T in 2-element equivalence classes.
%C The remaining element of T are those in 4-element equivalence classes.
%C The number of equivalence classes is |A| + (|V-A|+|N-A|+|G-A|)/2 + |T-A-(V-A)-(N-A)-(G-A)|/4 = |A|+(|V|+|N|+|G|-3|A|)/2 + (|T|-|V|-|N|-|G|+2|A|)/4 = (|T|+|V|+|N|+|G|)/4.
%C It is not hard to show |T|=2*3^(2k+1), |V|=|G| = 4*3^k and |N| = 2*3^k. Then we have (|T|-|V|-|N|-|G|)/4 = 3^k*(3^(k+1)+2+1+2)/2 = 3^k*(3^(k+1)+5)/2.
%H Mike Speciner, <a href="/A323845/a323845.py.txt">Python code to compute a(n) by counting equivalence classes</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,3,-9).
%F a(2k+1) = 3^k*(3^k+1)/2, and a(2k+2) = 3^k*(3^(k+1)+5)/2.
%F G.f.: x*(1 + x - 9*x^2)/((1 - 3*x)*(1 - 3*x^2)). - _Stefano Spezia_, Sep 02 2023
%e For n = 2, the degree 2 height 1 polynomials with nonzero constant term are x^2-x-1, x^2-x+1, x^2-1, x^2+1, x^2+x-1, x^2+x+1, and their (equivalent) negatives. x^2-x-1 is equivalent to x^2+x-1 (either by variable negation or a combination of variable inversion and polynomial negation), and x^2-x+1 is equivalent to x^2+x+1 (by variable negation), while x^2+1 and x^2-1 are each (together with their negative) in their own equivalence class, so a(2) = 4.
%t LinearRecurrence[{3, 3, -9}, {1, 4, 6}, 30] (* _Amiram Eldar_, Sep 02 2023 *)
%o (Python)
%o def a(n) :
%o k = (n-1)//2;
%o return 3**k*((3**k+1) if n&1 else (3**(k+1)+5))//2 if n else 1;
%K nonn,easy
%O 1,2
%A _Mike Speciner_, Aug 26 2023