login
a(n) = Sum_{k=0..n} (n-k+1)^k.
46

%I #129 Jan 31 2024 17:54:01

%S 1,2,4,9,23,66,210,733,2781,11378,49864,232769,1151915,6018786,

%T 33087206,190780213,1150653921,7241710930,47454745804,323154696185,

%U 2282779990495,16700904488706,126356632390298,987303454928973,7957133905608837,66071772829247410

%N a(n) = Sum_{k=0..n} (n-k+1)^k.

%C Row sums of A004248, A009998, A009999.

%C First differences are in A047970.

%C First differences of A103439.

%C Antidiagonal sums of array A003992.

%C a(n-1), for n>=1, is the number of length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(0)=0 and s(k)<=1+max(prefix) for k>=1, that are simultaneously projections as maps f: [n] -> [n] where f(x)<=x and f(f(x))=f(x); see example and the two comments (Arndt, Apr 30 2011 Jan 04 2013) in A000110. - _Joerg Arndt_, Mar 07 2015

%C Number of finite sequences s of length n+1 whose discriminator sequence is s itself. Here the discriminator sequence of s is the one where the n-th term (n>=1) is the least positive integer k such that the first n terms are pairwise incongruent, modulo k. - _Jeffrey Shallit_, May 17 2016

%C From _Gus Wiseman_, Jan 08 2019: (Start)

%C Also the number of set partitions of {1,...,n+1} whose minima form an initial interval of positive integers. For example, the a(3) = 9 set partitions are:

%C {{1},{2},{3},{4}}

%C {{1},{2},{3,4}}

%C {{1},{2,4},{3}}

%C {{1,4},{2},{3}}

%C {{1},{2,3,4}}

%C {{1,3},{2,4}}

%C {{1,4},{2,3}}

%C {{1,3,4},{2}}

%C {{1,2,3,4}}

%C Missing from this list are:

%C {{1},{2,3},{4}}

%C {{1,2},{3},{4}}

%C {{1,3},{2},{4}}

%C {{1,2},{3,4}}

%C {{1,2,3},{4}}

%C {{1,2,4},{3}}

%C (End)

%C a(n) is the number of m-tuples of nonnegative integers less than or equal to n-m (including the "0-tuple"). - _Mathew Englander_, Apr 11 2021

%H Reinhard Zumkeller, <a href="/A026898/b026898.txt">Table of n, a(n) for n = 0..500</a>

%H Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Beyene/beyene13.html">Set Partitions and Other Bell Number Enumerated Objects</a>, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.

%H Giulio Cerbai, <a href="https://arxiv.org/abs/2401.10027">Pattern-avoiding modified ascent sequences</a>, arXiv:2401.10027 [math.CO], 2024. See p. 12.

%H Sajed Haque, <a href="http://hdl.handle.net/10012/12234">Discriminators of Integer Sequences</a>, 2017, See p. 33 Corollary 29.

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/77790/asymptotics-of-1n-2n-1-3n-2-cdots-n-12-n1/78167#78167">Asymptotics of ...</a>, 2011.

%H Chunyan Yan and Zhicong Lin, <a href="https://arxiv.org/abs/1912.03674">Inversion sequences avoiding pairs of patterns</a>, arXiv:1912.03674 [math.CO], 2019.

%F a(n) = A003101(n) + 1.

%F G.f.: Sum_{n>=0} x^n/(1 - (n+1)*x). - _Paul D. Hanna_, Sep 13 2011

%F G.f.: G(0) where G(k) = 1 + x*(2*k*x-1)/((2*k*x+x-1) - x*(2*k*x+x-1)^2/(x*(2*k*x+x-1) + (2*k*x+2*x-1)/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jan 26 2013

%F E.g.f.: Sum_{n>=0} Integral^n exp((n+1)*x) dx^n, where Integral^n F(x) dx^n is the n-th integration of F(x) with no constant of integration. - _Paul D. Hanna_, Dec 28 2013

%F O.g.f.: Sum_{n>=0} n! * x^n/(1-x)^(n+1) / Product_{k=1..n} (1 + k*x). - _Paul D. Hanna_, Jul 20 2014

%F a(n) = A101494(n+1,0). - _Vladimir Kruchinin_, Apr 01 2015

%F a(n-1) = Sum_{k = 1..n} k^(n-k). - _Gus Wiseman_, Jan 08 2019

%F log(a(n)) ~ (1 - 1/LambertW(exp(1)*n)) * n * log(1 + n/LambertW(exp(1)*n)). - _Vaclav Kotesovec_, Jun 15 2021

%F a(n) ~ sqrt(2*Pi/(n+1 + (n+1)/w(n))) * ((n+1)/w(n))^(n+2 - (n+1)/w(n)), where w(n) = LambertW(exp(1)*(n+1)). - _Vaclav Kotesovec_, Jun 25 2021, after user "leonbloy", see Mathematics Stack Exchange link.

%e G.f.: A(x) = 1 + 2*x + 4*x^2 + 9*x^3 + 23*x^4 + 66*x^5 + 210*x^6 + ...

%e where we have the identity:

%e A(x) = 1/(1-x) + x/(1-2*x) + x^2/(1-3*x) + x^3/(1-4*x) + x^4/(1-5*x) + ...

%e is equal to

%e A(x) = 1/(1-x) + x/((1-x)^2*(1+x)) + 2!*x^2/((1-x)^3*(1+x)*(1+2*x)) + 3!*x^3/((1-x)^4*(1+x)*(1+2*x)*(1+3*x)) + 4!*x^4/((1-x)^5*(1+x)*(1+2*x)*(1+3*x)*(1+4*x)) + ...

%e From _Joerg Arndt_, Mar 07 2015: (Start)

%e The a(5-1) = 23 RGS described in the comment are (dots denote zeros):

%e 01: [ . . . . . ]

%e 02: [ . 1 . . . ]

%e 03: [ . 1 . . 1 ]

%e 04: [ . 1 . 1 . ]

%e 05: [ . 1 . 1 1 ]

%e 06: [ . 1 1 . . ]

%e 07: [ . 1 1 . 1 ]

%e 08: [ . 1 1 1 . ]

%e 09: [ . 1 1 1 1 ]

%e 10: [ . 1 2 . . ]

%e 11: [ . 1 2 . 1 ]

%e 12: [ . 1 2 . 2 ]

%e 13: [ . 1 2 1 . ]

%e 14: [ . 1 2 1 1 ]

%e 15: [ . 1 2 1 2 ]

%e 16: [ . 1 2 2 . ]

%e 17: [ . 1 2 2 1 ]

%e 18: [ . 1 2 2 2 ]

%e 19: [ . 1 2 3 . ]

%e 20: [ . 1 2 3 1 ]

%e 21: [ . 1 2 3 2 ]

%e 22: [ . 1 2 3 3 ]

%e 23: [ . 1 2 3 4 ]

%e (End)

%p a:= n-> add((n+1-j)^j, j=0..n): seq(a(n), n=0..23); # _Zerinvary Lajos_, Apr 18 2009

%t Table[Sum[(n-k+1)^k, {k,0,n}], {n, 0, 25}] (* _Michael De Vlieger_, Apr 01 2015 *)

%o (PARI) {a(n)=polcoeff(sum(m=0,n,x^m/(1-(m+1)*x+x*O(x^n))),n)} /* _Paul D. Hanna_, Sep 13 2011 */

%o (PARI) {INTEGRATE(n,F)=local(G=F);for(i=1,n,G=intformal(G));G}

%o {a(n)=local(A=1+x);A=sum(k=0,n,INTEGRATE(k,exp((k+1)*x+x*O(x^n))));n!*polcoeff(A,n)} \\ _Paul D. Hanna_, Dec 28 2013

%o for(n=0,30,print1(a(n),", "))

%o (PARI)

%o {a(n)=polcoeff( sum(m=0, n, m!*x^m/(1-x +x*O(x^n))^(m+1)/prod(k=1, m, 1+k*x +x*O(x^n))), n)} /* From o.g.f. (_Paul D. Hanna_, Jul 20 2014) */

%o for(n=0, 25, print1(a(n), ", "))

%o (Haskell)

%o a026898 n = sum $ zipWith (^) [n + 1, n .. 1] [0 ..]

%o -- _Reinhard Zumkeller_, Sep 14 2014

%o (Magma) [(&+[(n-k+1)^k: k in [0..n]]): n in [0..50]]; // _Stefano Spezia_, Jan 09 2019

%o (Sage) [sum((n-j+1)^j for j in (0..n)) for n in (0..30)] # _G. C. Greubel_, Jun 15 2021

%Y Cf. A000110, A000258, A000670, A003101, A008277, A038125, A062810.

%Y Cf. A105795, A179928, A287215, A287216.

%K nonn

%O 0,2

%A _N. J. A. Sloane_

%E a(23)-a(25) from _Paul D. Hanna_, Dec 28 2013