cp's OEIS Frontend

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

%I A328005 #34 Oct 06 2019 17:31:16
%S A328005 0,1,2,4,8,13,19,25,33,41,51,61,73,85,99,113,129,145,163,181,201,221,
%T A328005 243,265,289,313,339,365,393,421,451,481,513,545,579,613,649,685,723,
%U A328005 761,801,841,883,925,969,1013,1059,1105,1153,1201,1251,1301,1353,1405,1459
%N A328005 Number of distinct coefficients in functional composition of 1 + x + ... + x^(n-1) with itself.
%C A328005 Sum_{i=0..n-1} x^i = (x^n - 1)/(x - 1).
%H A328005 Wikipedia, <a href="https://en.wikipedia.org/wiki/Function_composition">Function composition</a>
%F A328005 It appears that a(n) = (2*n^2 + (-1)^n + 3)/4 for n >= 5.
%F A328005 Conjectured g.f.: (x^7 - x^6 - x^5 + 2*x^3 + 1)*x/((x + 1)*(1 - x)^3).
%e A328005 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 A328005 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 A328005 f:= n-> unapply(add(x^j, j=0..n-1), x):
%p A328005 a:= n-> nops({coeffs(expand((f(n)@@2)(x)))} minus {0}):
%p A328005 seq(a(n), n=0..60);  # _Alois P. Heinz_, Oct 01 2019
%t A328005 Table[With[{s = Sum[x^k, {k, 0, n - 1}]}, Length[Union[CoefficientList[Expand[s /. x -> s], x]]]], {n, 0, 53}]
%o A328005 (PARI) a(n)={my(p=(1-x^n)/(1-x)); #Set(Vec(subst(p,x,p)))} \\ _Andrew Howroyd_, Oct 01 2019
%o A328005 (SageMath)
%o A328005 def A328005(n):
%o A328005     R.<x> = PolynomialRing(ZZ)
%o A328005     q = R(sum(x^k for k in range(n)))
%o A328005     return len(Set(q.substitute(x=q).list()))
%o A328005 print([A328005(n) for n in range(55)]) # _Peter Luschny_, Oct 02 2019
%Y A328005 Cf. A099392, A080827, A023037.
%K A328005 nonn,easy
%O A328005 0,3
%A A328005 _Vladimir Reshetnikov_, Oct 01 2019