A136011 -id:A136011 - cp's OEIS frontend

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

Clark Kimberling

nonn

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

			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

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

Row sums of A136011.

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

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

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

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

A298668 Number T(n,k) of set partitions of [n] into k blocks such that the absolute difference between least elements of consecutive blocks is always > 1; triangle T(n,k), n>=0, 0<=k<=ceiling(n/2), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 3, 0, 1, 7, 2, 0, 1, 15, 12, 0, 1, 31, 50, 6, 0, 1, 63, 180, 60, 0, 1, 127, 602, 390, 24, 0, 1, 255, 1932, 2100, 360, 0, 1, 511, 6050, 10206, 3360, 120, 0, 1, 1023, 18660, 46620, 25200, 2520, 0, 1, 2047, 57002, 204630, 166824, 31920, 720

Offset: 0

Alois P. Heinz, Jan 24 2018

			T(5,1) = 1: 12345.
T(5,2) = 7: 1234|5, 1235|4, 123|45, 1245|3, 124|35, 125|34, 12|345.
T(5,3) = 2: 124|3|5, 12|34|5.
T(7,4) = 6: 1246|3|5|7, 124|36|5|7, 124|3|56|7, 126|34|5|7, 12|346|5|7, 12|34|56|7.
T(9,5) = 24: 12468|3|5|7|9, 1246|38|5|7|9, 1246|3|58|7|9, 1246|3|5|78|9, 1248|36|5|7|9, 124|368|5|7|9, 124|36|58|7|9, 124|36|5|78|9, 1248|3|56|7|9, 124|38|56|7|9, 124|3|568|7|9, 124|3|56|78|9, 1268|34|5|7|9, 126|348|5|7|9, 126|34|58|7|9, 126|34|5|78|9, 128|346|5|7|9, 12|3468|5|7|9, 12|346|58|7|9, 12|346|5|78|9, 128|34|56|7|9, 12|348|56|7|9, 12|34|568|7|9, 12|34|56|78|9.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1;
  0, 1,    1;
  0, 1,    3;
  0, 1,    7,     2;
  0, 1,   15,    12;
  0, 1,   31,    50,     6;
  0, 1,   63,   180,    60;
  0, 1,  127,   602,   390,    24;
  0, 1,  255,  1932,  2100,   360;
  0, 1,  511,  6050, 10206,  3360,  120;
  0, 1, 1023, 18660, 46620, 25200, 2520;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy

Columns k=0-11 give (offsets may differ): A000007, A057427, A168604, A028243, A028244, A028245, A032180, A228909, A228910, A228911, A228912, A228913.
Row sums give A229046(n-1) for n>0.
T(2n+1,n+1) gives A000142.
T(2n,n) gives A001710(n+1).
Cf. A000629, A000670, A008277, A028246, A048993, A076726, A110654, A136011, A173018.

b:= proc(n, m, t) option remember; `if`(n=0, x^m, add(
      b(n-1, max(m, j), `if`(j>m, 1, 0)), j=1..m+1-t))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..14);
# second Maple program:
T:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), (k-1)!*Stirling2(n-k+1, k)):
seq(seq(T(n, k), k=0..ceil(n/2)), n=0..14);
# third Maple program:
T:= proc(n, k) option remember; `if`(k<2, `if`(n=0 xor k=0, 0, 1),
      `if`(k>ceil(n/2), 0, add((k-j)*T(n-1-j, k-j), j=0..1)))
    end:
seq(seq(T(n, k), k=0..ceil(n/2)), n=0..14);

T[n_, k_] := T[n, k] = If[k < 2, If[Xor[n == 0, k == 0], 0, 1],
     If[k > Ceiling[n/2], 0, Sum[(k-j) T[n-1-j, k-j], {j, 0, 1}]]];
Table[Table[T[n, k], {k, 0, Ceiling[n/2]}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Mar 08 2021, after third Maple program *)

T(n,k) = (k-1)! * Stirling2(n-k+1,k) for k>0, T(n,0) = A000007(n).
T(n,k) = Sum_{j=0..k-1} (-1)^j*C(k-1,j)*(k-j)^(n-k) for k>0, T(n,0) = A000007(n).
T(n,k) = (k-1)! * A136011(n,k) for n, k >= 1.
Sum_{j>=0} T(n+j,j) = A076726(n) = 2*A000670(n) = A000629(n) + A000007(n).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula