A218452 Number of ways to factor (1 + x + x^2+ ... + x^(n - 1))^2 as the product of two monic polynomials of degree n - 1 with positive coefficients (counting order).

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 7, 9, 9, 13, 11, 17, 19, 33

Offset

1,12

Comments

a(n) is the number of ways one can divide the unit square in n possibly irregular lines * n possibly irregular columns (parallel to the sides) so that each of the diagonals of the n X n irregular checkerboard thus constructed has the same area as it would in a regular checkerboard. Alternatively, this is the number of ways to construct a pair of n-sided dice (probability distribution on the n sides, labeled 0 through n-1), no face having probability 0, so that the sum of the two dice follows the expected probability distribution for the sum of two fair n-sided dice. Note that a(n) is always odd because there is always the obvious factorization of (1+x+...+x^(n-1))^2 as 1+x+...+x^(n-1) times itself, and each other factorization counts twice.

Links

Table of n, a(n) for n=1..21.

Example

For n=12 we have a(n)=3 because apart from the obvious factorization of (1+x+...+x^11)^2 as (1+x+...+x^11) times itself, there exist the factorizations p*q and q*p where p = (1-sqrt(3)*x+x^2) * (1-x+x^2) * (1+x^2) * (1+x+x^2)^2 * (1+x) and q = (1-sqrt(3)*x+x^2) * (1-x+x^2) * (1+x^2) * (1+sqrt(3)*x+x^2)^2 * (1+x), both of which have positive coefficients, and those are the only two possible.

Prog

(Sage)
R.<x> = AA['x']
def has_positive_coefficients(pol):
    return not any(c <= 0 for c in pol.coeffs())
def trydie(m):
    results = []
    tmp = list(factor(sum([x^i for i in range(m)])))
    facs = [f for (f, _) in tmp]
    n = len(facs)
    for i in range((3^n+1)//2):
        exps = [(i//(3^k))%3 for k in range(n)]
        coexps = [2-v for v in exps]
        pol = R(prod([facs[k]^exps[k] for k in range(n)]))
        copol = R(prod([facs[k]^coexps[k] for k in range(n)]))
        if pol.degree()<m and copol.degree()<m and has_positive_coefficients(pol) and has_positive_coefficients(copol):
            pol /= pol.subs({x:1})
            copol /= copol.subs({x:1})
            results += [(pol.coeffs(), copol.coeffs())]
    return 2*len(results)-1

Crossrefs

Sequence in context: A265527 A217250 A213923 * A007731 A306590 A249494

Adjacent sequences: A218449 A218450 A218451 * A218453 A218454 A218455

Keyword

nonn

Author

David A. Madore, Oct 28 2012

Status

approved