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

1, 4, 6, 21, 45, 144, 378, 1161, 3321, 10044, 29646, 89181, 266085, 798984, 2392578, 7179921, 21526641, 64586484, 193720086, 581179941, 1743421725, 5230324224, 15690618378, 47072032281, 141215033961, 423645633324, 1270933711326, 3812802728301, 11438398618965, 34315200639864

Offset: 1

Author

Mike Speciner, Aug 26 2023

Keywords

• nonn
• easy

Comments

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.

If we consider only monic polynomials, equivalence classes can comprise 1, 2, or 4 different polynomials.

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.

Proof for n = 2k+2:

Let T be the set of monic height 1 degree-n polynomials with nonzero constant term.

Let V be the subset for which p(0)*x^n*p(1/x) = p(x).

Let N be the subset for which p(-x) = p(x).

Let G be the subset for which p(0)*x^n*p(-1/x) = p(x).

Let A be the intersection of V, N, and G.

A comprises the elements of T in 1-element equivalence classes.

V-A, N-A, and G-A are disjoint. Their union comprises the elements of T in 2-element equivalence classes.

The remaining element of T are those in 4-element equivalence classes.

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.

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.

Examples

			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.
		

Links

• Mike Speciner, Python code to compute a(n) by counting equivalence classes
• Index entries for linear recurrences with constant coefficients, signature (3,3,-9).

Programs

Mathematica

LinearRecurrence[{3, 3, -9}, {1, 4, 6}, 30] (* Amiram Eldar, Sep 02 2023 *)

Python

def a(n) :
  k = (n-1)//2;
  return 3**k*((3**k+1) if n&1 else (3**(k+1)+5))//2 if n else 1;

Formula

a(2k+1) = 3^k*(3^k+1)/2, and a(2k+2) = 3^k*(3^(k+1)+5)/2.

G.f.: x*(1 + x - 9*x^2)/((1 - 3*x)*(1 - 3*x^2)). - Stefano Spezia, Sep 02 2023