A328005 - OEIS

%I #34 Oct 06 2019 17:31:16

%S 0,1,2,4,8,13,19,25,33,41,51,61,73,85,99,113,129,145,163,181,201,221,

%T 243,265,289,313,339,365,393,421,451,481,513,545,579,613,649,685,723,

%U 761,801,841,883,925,969,1013,1059,1105,1153,1201,1251,1301,1353,1405,1459

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

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Function_composition">Function composition</a>

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

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

%e 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.

%e 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.

%p f:= n-> unapply(add(x^j, j=0..n-1), x):

%p a:= n-> nops({coeffs(expand((f(n)@@2)(x)))} minus {0}):

%p seq(a(n), n=0..60);  # _Alois P. Heinz_, Oct 01 2019

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

%o (PARI) a(n)={my(p=(1-x^n)/(1-x)); #Set(Vec(subst(p,x,p)))} \\ _Andrew Howroyd_, Oct 01 2019

%o (SageMath)

%o def A328005(n):

%o     R.<x> = PolynomialRing(ZZ)

%o     q = R(sum(x^k for k in range(n)))

%o     return len(Set(q.substitute(x=q).list()))

%o print([A328005(n) for n in range(55)]) # _Peter Luschny_, Oct 02 2019

%Y Cf. A099392, A080827, A023037.

%K nonn,easy

%O 0,3

%A _Vladimir Reshetnikov_, Oct 01 2019