A303952 a(n) is the number of monic polynomials P(z) of degree n over the complex numbers such that P(z) divides P(z^2).

1, 2, 5, 17, 69, 302, 1367, 6302, 29401, 138356, 655425, 3121439, 14930541, 71675840, 345148893, 1666432817, 8064278289, 39103576700, 189949958333, 924163714217, 4502711570989, 21966152501240, 107284324830303

Offset: 0

Author

Jianing Song, May 03 2018

Keywords

• nonn
• easy

Comments

Note that if z_0 is a root of P(z), so is (z_0)^2, so |z_0| must equal to 0 or 1. As a result, all such polynomials must have the form P(z) = z^d_0 * Product_{j=1..k} (z - exp(2*Pi*i*q_j))^d_j, where Sum_{j=0..k} d_j = n and {q_1, q_2, ..., q_k} is a set of k rational numbers on [0,1) such that if x belongs to it, the fractional part of 2x also belongs to it. That explains the formula a(n) = Sum_{k=1..n} binomial(n,k)*A014300(k) + 1 in the formula section, the "+1" represents the case d_0 = n and k = 0 corresponding to the polynomial P(z) = z^n.

Examples

			For n = 0, P(z) = 1.
For n = 1, P(z) = z or z - 1.
For n = 2, P(z) = z^2, z^2 - 1, z^2 - 2z + 1, z^2 + z or z^2 + z + 1.
		

Crossrefs

Cf. A014300, A128728, A128730.

Programs

PARI

x='x+O('x^50); Vec(2*x/(1-6*x+5*x^2+(1+x)*sqrt(1-6*x+5*x^2))+1/(1-x))

Formula

a(n) = Sum_{k=1..n} binomial(n,k)*A014300(k) + 1. The "+1" represents the polynomial P(z) = z^n.

a(n) = A128730(n+1) + 1.

G.f.: 2x/(1-6x+5x^2+(1+x)sqrt(1-6x+5x^2)) + 1/(1-x).

D-finite with recurrence: +2*n*a(n) +(-13*n+4)*a(n-1) +2*(7*n+3)*a(n-2) +8*(n-7)*a(n-3) +2*(-8*n+33)*a(n-4) +5*(n-4)*a(n-5)=0. - R. J. Mathar, Jan 27 2020

D-finite with recurrence 2*n*a(n) +(-11*n+2)*a(n-1) +(3*n+19)*a(n-2) +(11*n-40)*a(n-3) +5*(-n+3)*a(n-4) +4=0. - R. J. Mathar, Aug 01 2022