OFFSET
1,2
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.
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).
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
EXAMPLE
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.
MATHEMATICA
LinearRecurrence[{3, 3, -9}, {1, 4, 6}, 30] (* Amiram Eldar, Sep 02 2023 *)
PROG
(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;
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Mike Speciner, Aug 26 2023
STATUS
approved