A045618 Partial sums of A000337(n+4), n >= 0.

1, 6, 23, 72, 201, 522, 1291, 3084, 7181, 16398, 36879, 81936, 180241, 393234, 851987, 1835028, 3932181, 8388630, 17825815, 37748760, 79691801, 167772186, 352321563, 738197532, 1543503901, 3221225502, 6710886431, 13958643744

Offset: 0

Author

Wolfdieter Lang

Keywords

• easy
• nonn

Comments

Convolution of A000225(n+1), n >= 0, (partial sums of powers of 2).

Sum of diameters of all nonempty subsets of {1, 2, ..., n+2}. - Charles R Greathouse IV, Nov 21 2011

a(n) is the sum of all the ways of adding the k-tuples of the terms found in A000079(0) to A000079(n). For a(2) the result is (1)+(2)+(4)=7; (1+2)+(2+4)=9; (1+2+4)=7 with 7+9+7=23. - J. M. Bergot, Jun 19 2017

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 14.
• Brian Nakamura and Elizabeth Yang, Competition graphs induced by permutations, arXiv preprint arXiv:1503.05617 [math.CO], 2015.
• Alina F. Y. Zhao, Pattern Popularity in Multiply Restricted Permutations, Journal of Integer Sequences, 17 (2014), #14.10.3.
• Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Crossrefs

Cf. A000337.

Programs

Mathematica

Table[Sum[(-1)^(n - k) k (-1)^(n - k) Binomial[n + 2, k + 2], {k, 0, n}], {n, 1, 28}] (* Zerinvary Lajos, Jul 08 2009 *)
Rest[Accumulate[LinearRecurrence[{5,-8,4},{0,1,5},40]]] (* Harvey P. Dale, Dec 19 2011 *)
CoefficientList[Series[1/((1 - x)^2 (1 - 2 x)^2), {x, 0, 30}], x] (* Vincenzo Librandi, Jul 22 2014 *)
LinearRecurrence[{6, -13, 12, -4},{1, 6, 23, 72},28] (* Ray Chandler, Aug 03 2015 *)

PARI

a(n)=(n-1)<<(n+2)+n+5 \\ Charles R Greathouse IV, Nov 21 2011

Formula

a(n) = n + 5 + (n-1)*2^(n+2).

G.f.: 1/((1-2*x)*(1-x))^2.

a(n) = Sum_{i=0...n+1} (2^(n+2-i) - 1)*(2^i - 1). - J. M. Bergot, Sep 16 2017

a(n) = Sum_{k=0..n+2} Sum_{i=0..n+2} (i-k) * C(n-k+2,i). - Wesley Ivan Hurt, Sep 19 2017

a(n) = 4*a(n-1) - 4*a(n-2) + n + 1, with a(-1) = a(-2) = 0. - Jesse Fiedler, Aug 20 2019

E.g.f.: exp(x)*(5 + x + exp(x)*(- 4 + 8*x)). - Stefano Spezia, Aug 20 2019

a(n) = Sum_{k=0..n} Stirling2(k+2,2) * Stirling2(n-k+2,2). - Seiichi Manyama, May 12 2025