login
A328005
Number of distinct coefficients in functional composition of 1 + x + ... + x^(n-1) with itself.
1
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).
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
KEYWORD
nonn,easy
AUTHOR
STATUS
approved