A062810 -id:A062810 - cp's OEIS frontend

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

1, 2, 4, 9, 23, 66, 210, 733, 2781, 11378, 49864, 232769, 1151915, 6018786, 33087206, 190780213, 1150653921, 7241710930, 47454745804, 323154696185, 2282779990495, 16700904488706, 126356632390298, 987303454928973, 7957133905608837, 66071772829247410

Offset: 0

N. J. A. Sloane

nonn

Row sums of A004248, A009998, A009999.
First differences are in A047970.
First differences of A103439.
Antidiagonal sums of array A003992.
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
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
From Gus Wiseman, Jan 08 2019: (Start)
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:
  {{1},{2},{3},{4}}
  {{1},{2},{3,4}}
  {{1},{2,4},{3}}
  {{1,4},{2},{3}}
  {{1},{2,3,4}}
  {{1,3},{2,4}}
  {{1,4},{2,3}}
  {{1,3,4},{2}}
  {{1,2,3,4}}
Missing from this list are:
  {{1},{2,3},{4}}
  {{1,2},{3},{4}}
  {{1,3},{2},{4}}
  {{1,2},{3,4}}
  {{1,2,3},{4}}
  {{1,2,4},{3}}
(End)
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

			G.f.: A(x) = 1 + 2*x + 4*x^2 + 9*x^3 + 23*x^4 + 66*x^5 + 210*x^6 + ...
where we have the identity:
A(x) = 1/(1-x) + x/(1-2*x) + x^2/(1-3*x) + x^3/(1-4*x) + x^4/(1-5*x) + ...
is equal to
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)) + ...
From _Joerg Arndt_, Mar 07 2015: (Start)
The a(5-1) = 23 RGS described in the comment are (dots denote zeros):
01:  [ . . . . . ]
02:  [ . 1 . . . ]
03:  [ . 1 . . 1 ]
04:  [ . 1 . 1 . ]
05:  [ . 1 . 1 1 ]
06:  [ . 1 1 . . ]
07:  [ . 1 1 . 1 ]
08:  [ . 1 1 1 . ]
09:  [ . 1 1 1 1 ]
10:  [ . 1 2 . . ]
11:  [ . 1 2 . 1 ]
12:  [ . 1 2 . 2 ]
13:  [ . 1 2 1 . ]
14:  [ . 1 2 1 1 ]
15:  [ . 1 2 1 2 ]
16:  [ . 1 2 2 . ]
17:  [ . 1 2 2 1 ]
18:  [ . 1 2 2 2 ]
19:  [ . 1 2 3 . ]
20:  [ . 1 2 3 1 ]
21:  [ . 1 2 3 2 ]
22:  [ . 1 2 3 3 ]
23:  [ . 1 2 3 4 ]
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..500
Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, Set Partitions and Other Bell Number Enumerated Objects, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.
Giulio Cerbai, Pattern-avoiding modified ascent sequences, arXiv:2401.10027 [math.CO], 2024. See p. 12.
Giulio Cerbai and Anders Claesson, Counting fixed-point-free Cayley permutations, arXiv:2507.09304 [math.CO], 2025. See p. 25.
Sajed Haque, Discriminators of Integer Sequences, 2017, See p. 33 Corollary 29.
Mathematics Stack Exchange, Asymptotics of ..., 2011.
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019. See p. 3.
Robin D. P. Zhou, Pattern avoidance in revised ascent sequences, arXiv:2505.05171 [math.CO], 2025. See p. 4.

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

Cf. A105795, A179928, A287215, A287216.

a026898 n = sum $ zipWith (^) [n + 1, n .. 1] [0 ..]
-- Reinhard Zumkeller, Sep 14 2014

[(&+[(n-k+1)^k: k in [0..n]]): n in [0..50]]; // Stefano Spezia, Jan 09 2019

a:= n-> add((n+1-j)^j, j=0..n): seq(a(n), n=0..23); # Zerinvary Lajos, Apr 18 2009

Table[Sum[(n-k+1)^k, {k,0,n}], {n, 0, 25}] (* Michael De Vlieger, Apr 01 2015 *)

{a(n)=polcoeff(sum(m=0,n,x^m/(1-(m+1)*x+x*O(x^n))),n)} /* Paul D. Hanna, Sep 13 2011 */

{INTEGRATE(n,F)=local(G=F);for(i=1,n,G=intformal(G));G}
{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
for(n=0,30,print1(a(n),", "))

{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) */
for(n=0, 25, print1(a(n), ", "))

[sum((n-j+1)^j for j in (0..n)) for n in (0..30)] # G. C. Greubel, Jun 15 2021

a(n) = A003101(n) + 1.
G.f.: Sum_{n>=0} x^n/(1 - (n+1)*x). - Paul D. Hanna, Sep 13 2011
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
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
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
a(n) = A101494(n+1,0). - Vladimir Kruchinin, Apr 01 2015
a(n-1) = Sum_{k = 1..n} k^(n-k). - Gus Wiseman, Jan 08 2019
log(a(n)) ~ (1 - 1/LambertW(exp(1)*n)) * n * log(1 + n/LambertW(exp(1)*n)). - Vaclav Kotesovec, Jun 15 2021
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.

a(23)-a(25) from Paul D. Hanna, Dec 28 2013

A003101 a(n) = Sum_{k = 1..n} (n - k + 1)^k.

Original entry on oeis.org

0, 1, 3, 8, 22, 65, 209, 732, 2780, 11377, 49863, 232768, 1151914, 6018785, 33087205, 190780212, 1150653920, 7241710929, 47454745803, 323154696184, 2282779990494, 16700904488705, 126356632390297, 987303454928972, 7957133905608836, 66071772829247409

Offset: 0

N. J. A. Sloane, Henry W. Gould

For n > 0: a(n) = sum of row n of triangles A051129 and A247358. - Reinhard Zumkeller, Sep 14 2014
a(n-1) is the number of set partitions of [n] into two or more blocks such that all absolute differences between least elements of consecutive blocks are 1. a(3) = 8: 134|2, 13|24, 14|23, 1|234, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4. - Alois P. Heinz, May 22 2017
Min_{n >= 1} a(n+1)/a(n) = 8/3. This is the answer to the 4th problem proposed during the first day of the final round of the 16th Austrian Mathematical Olympiad in 1985 (see link IMO Compendium). - Bernard Schott, Jan 07 2019
If n rings of different internal diameter can fit close together on a tapering column, a(n) is the number of different arrangements of at least one ring. For example, if the rings increasing in size are 1, 2 and 3, then a(3) = 8 corresponding to the possible arrangements from the point on the column of smallest diameter (1XX), (X2X), (XX3), (12X), (32X), (1X3), (X23) and (123), where X denotes a space on the column. - Ian Duff, Jun 23 2025

			For n = 3 we get a(3) = 3^1 + 2^2 + 1^3 = 8. For n = 4 we get a(4) = 4^1 + 3^2 + 2^3 + 1^4 = 22.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Charles R Greathouse IV, Table of n, a(n) for n = 0..598
Henry W. Gould, Letters to N. J. A. Sloane, Oct 1973 and Jan 1974.
Mathematics Stack Exchange, Asymptotics of 1^n+2^(n-1)+3^(n-2)+...+(n-1)^2+n^1, 2011.
Daniel Ropp, Problem 2 - 16th Austrian Mathematical Olympiad (Final round), Crux Mathematicorum, page 7, Vol. 14, Jun. 88.
The IMO compendium, Problem 2, 16th Austrian Mathematical Olympiad, 1985.
Index to sequences related to Olympiads.

Cf. A026898, A051129, A062810, A247358, A287215.

First differences are in A047970.

a003101 n = sum $ zipWith (^) [0 ..] [n + 1, n .. 1]
-- Reinhard Zumkeller, Sep 14 2014

[n eq 0 select 0 else (&+[(n-j+1)^j: j in [1..n]]): n in [0..50]]; // G. C. Greubel, Oct 26 2022

A003101 := n->add((n-k+1)^k, k=1..n);
a:= n-> add((n-j+1)^j, j=1..n): seq(a(n), n=0..30); # Zerinvary Lajos, Jun 07 2008

Table[Sum[(n-k+1)^k,{k,n}],{n,0,25}] (* Harvey P. Dale, Aug 14 2011 *)

a(n)=sum(k=1,n,(n-k+1)^k) \\ Charles R Greathouse IV, Oct 31 2011

def A003101(n): return sum( (n-k+1)^k for k in range(1,n+1))
[A003101(n) for n in range(50)] # G. C. Greubel, Oct 26 2022

a(n) = A026898(n) - 1.
G.f.: G(0)/x-1/(1-x)/x 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) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 26 2013
G.f.: Sum_{k>=1} x^k/(1 - (k + 1)*x). - Ilya Gutkovskiy, Oct 09 2018
a(n) = n^1 + (n-1)^2 + (n-2)^3 + ... + 3^(n-2) + 2^(n-1) + 1^n. - Bernard Schott, Jan 07 2019
log(a(n)) ~ (1 - 1/LambertW(exp(1)*n)) * n * log(1 + n/LambertW(exp(1)*n)). - Vaclav Kotesovec, Jun 15 2021
a(n) ~ sqrt(2*Pi/(n+1 + w(n))) * w(n)^(n+2 - w(n)), where w(n) = (n+1)/LambertW(exp(1)*(n+1)). - Vaclav Kotesovec, Jun 25 2021, after user "leonbloy", see Mathematics Stack Exchange link.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

Extensions

A003101 a(n) = Sum_{k = 1..n} (n - k + 1)^k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

A062811 a(n) = Sum_{i=1..n} i^(n - i) + (i - n)^i.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A062812 a(n) = Sum_{i=1..n} i^(n - i) + (-1)^(n - i)*(n - i)^i.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI