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

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,3

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

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

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.

Example

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.

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 *)

Prog

(PARI) a(n)=sum(k=1, n, (n-k+1)^k) \\ Charles R Greathouse IV, Oct 31 2011
(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
(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

Crossrefs

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

First differences are in A047970.

Sequence in context: A372528 A290898 A117420 * A064443 A000732 A092090

Adjacent sequences: A003098 A003099 A003100 * A003102 A003103 A003104

Keyword

nonn,easy

Author

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

Status

approved