A003101 - OEIS

%I M2745 #92 Feb 09 2024 10:07:24

%S 0,1,3,8,22,65,209,732,2780,11377,49863,232768,1151914,6018785,

%T 33087205,190780212,1150653920,7241710929,47454745803,323154696184,

%U 2282779990494,16700904488705,126356632390297,987303454928972,7957133905608836,66071772829247409

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

%C For n > 0: a(n) = sum of row n of triangles A051129 and A247358. - _Reinhard Zumkeller_, Sep 14 2014

%C 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

%C 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

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

%H Charles R Greathouse IV, <a href="/A003101/b003101.txt">Table of n, a(n) for n = 0..598</a>

%H Henry W. Gould, <a href="/A003099/a003099.pdf">Letters to N. J. A. Sloane, Oct 1973 and Jan 1974</a>.

%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 Daniel Ropp, <a href="https://cms.math.ca/wp-content/uploads/crux-pdfs/Crux_v14n01_Jan.pdf">Problem 2 - 16th Austrian Mathematical Olympiad (Final round)</a>, Crux Mathematicorum, page 7, Vol. 14, Jun. 88.

%H The IMO compendium, <a href="https://imomath.com/othercomp/Aut/AutMO85.pdf">Problem 2</a>, 16th Austrian Mathematical Olympiad, 1985.

%H <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.

%F a(n) = A026898(n) - 1.

%F 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

%F G.f.: Sum_{k>=1} x^k/(1 - (k + 1)*x). - _Ilya Gutkovskiy_, Oct 09 2018

%F a(n) = n^1 + (n-1)^2 + (n-2)^3 + ... + 3^(n-2) + 2^(n-1) + 1^n. - _Bernard Schott_, Jan 07 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 + 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.

%e 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.

%p A003101 := n->add((n-k+1)^k, k=1..n);

%p a:= n-> add((n-j+1)^j, j=1..n): seq(a(n), n=0..30); # _Zerinvary Lajos_, Jun 07 2008

%t Table[Sum[(n-k+1)^k,{k,n}],{n,0,25}] (* _Harvey P. Dale_, Aug 14 2011 *)

%o (PARI) a(n)=sum(k=1,n,(n-k+1)^k) \\ _Charles R Greathouse IV_, Oct 31 2011

%o (Haskell)

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

%o -- _Reinhard Zumkeller_, Sep 14 2014

%o (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

%o (SageMath)

%o def A003101(n): return sum( (n-k+1)^k for k in range(1,n+1))

%o [A003101(n) for n in range(50)] # _G. C. Greubel_, Oct 26 2022

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

%Y First differences are in A047970.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, _Henry W. Gould_