A024427 S(n,1) + S(n-1,2) + S(n-2,3) + ... + S(n+1-k,k), where k = floor((n+1)/2) and S(i,j) are Stirling numbers of the second kind.

1, 1, 2, 4, 9, 22, 58, 164, 495, 1587, 5379, 19195, 71872, 281571, 1151338, 4902687, 21696505, 99598840, 473466698, 2327173489, 11810472444, 61808852380, 333170844940, 1847741027555, 10532499571707, 61649191750137, 370208647200165, 2278936037262610

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Comments

a(n) is the number of ways to partition {1,2,...,n+1} into any number of blocks such that each block has at least 2 elements and the smallest 2 elements in each block are consecutive integers. - Geoffrey Critzer, Dec 02 2013

Examples

			a(5) = 9 because we have: {1,2,3,4,5,6}; {1,2,3,4},{5,6}; {1,2,3},{4,5,6}; {1,2},{3,4,5,6}; {1,2,5,6},{3,4}; {1,2,5},{3,4,6}; {1,2,6},{3,4,5}; {1,2,3,6},{4,5}; {1,2},{3,4},{5,6}. - _Geoffrey Critzer_, Dec 02 2013
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..300

Crossrefs

Row sums of A136011.

Programs

Maple

with(combinat): seq(add(stirling2(n+1-i, i), i=0..n), n=1..26); # Zerinvary Lajos, Jan 31 2008

Mathematica

Table[Total[Table[StirlingS2[n - k + 1, k], {k, Floor[(n + 1)/2]}]], {n, 30}] (* T. D. Noe, Oct 29 2013 *)

PARI

a(n) = sum(j=1,floor((n+1)/2), stirling(n+1-j,j,2) ); /* Joerg Arndt, Apr 14 2013 */

Formula

G.f.: Sum_{k>=0} x^(2*k) / Product_{l=1..k} (1-l*x). - Ralf Stephan, Apr 18 2004

a(n) = Sum_{i=0..n} stirling2(n+1-i, i). - Zerinvary Lajos, Jan 31 2008

G.f.: ((G(0) - 1)/(x-1)-x)/x^3 where G(k) = 1 - x/(1-k*x)/(1-x/(x-1/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 16 2013

G.f.: 1/x^2/Q(0) - 1/x^2 where Q(k) = 1 - x^2/(1 - x*(k+1)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Apr 14 2013

G.f.: T(0)/(x^2*(1-x^2)) - 1/x^2, where T(k) = 1 - (k+1)*x^3/((k+1)*x^3 - (1 - x^2 - x*k)*(1 - x - x^2 - x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 29 2013

G.f.: 1/(Q(0)-x^2), where Q(k) = 1 - x*(k+1)/( 1 - x^2/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 03 2013