login
Number of inequivalent height 1 degree n polynomials with nonzero constant term.
1

%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