cp's OEIS Frontend

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

%I A323845 #76 Sep 22 2023 11:26:09
%S A323845 1,4,6,21,45,144,378,1161,3321,10044,29646,89181,266085,798984,
%T A323845 2392578,7179921,21526641,64586484,193720086,581179941,1743421725,
%U A323845 5230324224,15690618378,47072032281,141215033961,423645633324,1270933711326,3812802728301,11438398618965,34315200639864
%N A323845 Number of inequivalent height 1 degree n polynomials with nonzero constant term.
%C A323845 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 A323845 If we consider only monic polynomials, equivalence classes can comprise 1, 2, or 4 different polynomials.
%C A323845 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 A323845 Proof for n = 2k+2:
%C A323845 Let T be the set of monic height 1 degree-n polynomials with nonzero constant term.
%C A323845 Let V be the subset for which p(0)*x^n*p(1/x) = p(x).
%C A323845 Let N be the subset for which p(-x) = p(x).
%C A323845 Let G be the subset for which p(0)*x^n*p(-1/x) = p(x).
%C A323845 Let A be the intersection of V, N, and G.
%C A323845 A comprises the elements of T in 1-element equivalence classes.
%C A323845 V-A, N-A, and G-A are disjoint. Their union comprises the elements of T in 2-element equivalence classes.
%C A323845 The remaining element of T are those in 4-element equivalence classes.
%C A323845 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 A323845 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 A323845 Mike Speciner, <a href="/A323845/a323845.py.txt">Python code to compute a(n) by counting equivalence classes</a>
%H A323845 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,3,-9).
%F A323845 a(2k+1) = 3^k*(3^k+1)/2, and a(2k+2) = 3^k*(3^(k+1)+5)/2.
%F A323845 G.f.: x*(1 + x - 9*x^2)/((1 - 3*x)*(1 - 3*x^2)). - _Stefano Spezia_, Sep 02 2023
%e A323845 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 A323845 LinearRecurrence[{3, 3, -9}, {1, 4, 6}, 30] (* _Amiram Eldar_, Sep 02 2023 *)
%o A323845 (Python)
%o A323845 def a(n) :
%o A323845   k = (n-1)//2;
%o A323845   return 3**k*((3**k+1) if n&1 else (3**(k+1)+5))//2 if n else 1;
%K A323845 nonn,easy
%O A323845 1,2
%A A323845 _Mike Speciner_, Aug 26 2023