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

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

Author

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

Keywords

• nonn
• easy

Comments

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

Examples

			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.
		

References

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

Links

• 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.

Crossrefs

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

First differences are in A047970.

Programs

Haskell

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

Magma

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

Maple

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

Mathematica

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

PARI

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

SageMath

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

Formula

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.