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,3

Comments

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

Links

Table of n, a(n) for n=0..54.

Wikipedia, Function composition

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).

Example

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.

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}]

Prog

(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.<x> = 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

Crossrefs

Cf. A099392, A080827, A023037.

Sequence in context: A346992 A058329 A037380 * A186752 A360512 A030503

Adjacent sequences: A328002 A328003 A328004 * A328006 A328007 A328008

Keyword

nonn,easy

Author

Vladimir Reshetnikov, Oct 01 2019

Status

approved