A328005 Number of distinct coefficients in functional composition of 1 + x + ... + x^(n-1) with itself.

0, 1, 2, 4, 8, 13, 19, 25, 33, 41, 51, 61, 73, 85, 99, 113, 129, 145, 163, 181, 201, 221, 243, 265, 289, 313, 339, 365, 393, 421, 451, 481, 513, 545, 579, 613, 649, 685, 723, 761, 801, 841, 883, 925, 969, 1013, 1059, 1105, 1153, 1201, 1251, 1301, 1353, 1405, 1459

Offset: 0

Author

Vladimir Reshetnikov, Oct 01 2019

Keywords

• nonn
• easy

Comments

Sum_{i=0..n-1} x^i = (x^n - 1)/(x - 1).

Examples

			For n = 4, the composition of 1 + x + x^2 + x^3 with itself is 1 + (1 + x + x^2 + x^3) + (1 + x + x^2 + x^3)^2 + (1 + x + x^2 + x^3)^3 = 4 + 6 x + 10 x^2 + 15 x^3 + 15 x^4 + 14 x^5 + 11 x^6 + 6 x^7 + 3 x^8 + x^9 that has 8 distinct coefficients [1, 3, 4, 6, 10, 11, 14, 15], so a(4) = 8.
The first few polynomials p_n(x) are 0, 1, x + 2, x^4 + 2*x^3 + 4*x^2 + 3*x + 3, ... with p_n(1) = A023037(n), n >= 0.
		

Links

• Wikipedia, Function composition

Crossrefs

Cf. A099392, A080827, A023037.

Programs

Maple

f:= n-> unapply(add(x^j, j=0..n-1), x):
a:= n-> nops({coeffs(expand((f(n)@@2)(x)))} minus {0}):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 01 2019

Mathematica

Table[With[{s = Sum[x^k, {k, 0, n - 1}]}, Length[Union[CoefficientList[Expand[s /. x -> s], x]]]], {n, 0, 53}]

PARI

a(n)={my(p=(1-x^n)/(1-x)); #Set(Vec(subst(p,x,p)))} \\ Andrew Howroyd, Oct 01 2019

SageMath

def A328005(n):
    R. = PolynomialRing(ZZ)
    q = R(sum(x^k for k in range(n)))
    return len(Set(q.substitute(x=q).list()))
print([A328005(n) for n in range(55)]) # Peter Luschny, Oct 02 2019

Formula

It appears that a(n) = (2*n^2 + (-1)^n + 3)/4 for n >= 5.

Conjectured g.f.: (x^7 - x^6 - x^5 + 2*x^3 + 1)*x/((x + 1)*(1 - x)^3).