A270236 -id:A270236 - cp's OEIS frontend

A285362 Sum T(n,k) of the entries in the k-th blocks of all set partitions of [n]; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

1, 4, 2, 15, 12, 3, 60, 58, 28, 4, 262, 273, 185, 55, 5, 1243, 1329, 1094, 495, 96, 6, 6358, 6839, 6293, 3757, 1148, 154, 7, 34835, 37423, 36619, 26421, 11122, 2380, 232, 8, 203307, 217606, 219931, 180482, 96454, 28975, 4518, 333, 9, 1257913, 1340597, 1376929, 1230737, 787959, 308127, 67898, 7995, 460, 10

Offset: 1

Alois P. Heinz, Apr 17 2017

			T(3,2) = 12 because the sum of the entries in the second blocks of all set partitions of [3] (123, 12|3, 13|2, 1|23, 1|2|3) is 0+3+2+5+2 = 12.
Triangle T(n,k) begins:
      1;
      4,     2;
     15,    12,     3;
     60,    58,    28,     4;
    262,   273,   185,    55,     5;
   1243,  1329,  1094,   495,    96,    6;
   6358,  6839,  6293,  3757,  1148,  154,   7;
  34835, 37423, 36619, 26421, 11122, 2380, 232, 8;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Wikipedia, Partition of a set

Columns k=1-10 give: A285363, A285364, A285365, A285366, A285367, A285368, A285369, A285370, A285371, A285372.
Row sums give A000110(n) * A000217(n) = A105488(n+3).
Main diagonal and first lower diagonal give: A000027, A006000 (for n>0).
T(2n+1,n+1) gives A285410.
Cf. A270236, A285439, A285595.

T:= proc(h) option remember; local b; b:=
      proc(n, m) option remember; `if`(n=0, [1, 0], add((p-> p
        +[0, (h-n+1)*p[1]*x^j])(b(n-1, max(m, j))), j=1..m+1))
      end: (p-> seq(coeff(p, x, i), i=1..n))(b(h, 0)[2])
    end:
seq(T(n), n=1..12);

T[h_] := T[h] = Module[{b}, b[n_, m_] := b[n, m] = If[n == 0, {1, 0}, Sum[# + {0, (h - n + 1)*#[[1]]*x^j}&[b[n - 1, Max[m, j]]], {j, 1, m + 1}]]; Table[Coefficient[#, x, i], {i, 1, n}]&[b[h, 0][[2]]]];
Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Apr 30 2018, after Alois P. Heinz *)

A185105 Number T(n,k) of entries in the k-th cycles of all permutations of {1,2,..,n}; each cycle is written with the smallest element first and cycles are arranged in increasing order of their first elements.

Original entry on oeis.org

1, 3, 1, 12, 5, 1, 60, 27, 8, 1, 360, 168, 59, 12, 1, 2520, 1200, 463, 119, 17, 1, 20160, 9720, 3978, 1177, 221, 23, 1, 181440, 88200, 37566, 12217, 2724, 382, 30, 1, 1814400, 887040, 388728, 135302, 34009, 5780, 622, 38, 1, 19958400, 9797760, 4385592, 1606446, 441383, 86029, 11378, 964, 47, 1

Offset: 1

Wouter Meeussen, Dec 26 2012

Row sums are n!*n = A001563(n) (see example).

For fixed k>=1, A185105(n,k) ~ n!*n/2^k. - Vaclav Kotesovec, Apr 25 2017

			The six permutations of n=3 in ordered cycle form are:
{ {1}, {2}, {3}    }
{ {1}, {2, 3}, {}  }
{ {1, 2}, {3}, {}  }
{ {1, 2, 3}, {}, {}}
{ {1, 3, 2}, {}, {}}
{ {1, 3}, {2}, {}  }
.
The lengths of the cycles in position k=1 sum to 12, those of the cycles in position k=2 sum to 5 and those of the cycles in position k=3 sum to 1.
Triangle begins:
       1;
       3,     1;
      12,     5,     1;
      60,    27,     8,     1;
     360,   168,    59,    12,    1;
    2520,  1200,   463,   119,   17,   1;
   20160,  9720,  3978,  1177,  221,  23,  1;
  181440, 88200, 37566, 12217, 2724, 382, 30, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Wikipedia, Permutation

Columns k=1-10 give: A001710(n+1), A138772, A159324(n-1)/2 or A285231, A285232, A285233, A285234, A285235, A285236, A285237, A285238.
T(2n,n) gives A285239.
Cf. A000142, A001563, A270236, A284816, A285439.

b:= proc(n, i) option remember; expand(`if`(n=0, 1,
      add((p-> p+coeff(p, x, 0)*j*x^i)(b(n-j, i+1))*
       binomial(n-1, j-1)*(j-1)!, j=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 1)):
seq(T(n), n=1..12);  # Alois P. Heinz, Apr 15 2017

Table[it = Join[RotateRight /@ ToCycles[#], Table[{}, {k}]] & /@ Permutations[Range[n]]; Tr[Length[Part[#, k]]& /@ it], {n, 7}, {k, n}]
(* Second program: *)
b[n_, i_] := b[n, i] = Expand[If[n==0, 1, Sum[Function[p, p + Coefficient[ p, x, 0]*j*x^i][b[n-j, i+1]]*Binomial[n-1, j-1]*(j-1)!, {j, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, 1]];
Array[T, 12] // Flatten (* Jean-François Alcover, May 30 2018, after Alois P. Heinz *)

More terms from Alois P. Heinz, Apr 15 2017

A070071 a(n) = n*B(n), where B(n) are the Bell numbers, A000110.

Original entry on oeis.org

0, 1, 4, 15, 60, 260, 1218, 6139, 33120, 190323, 1159750, 7464270, 50563164, 359377681, 2672590508, 20744378175, 167682274352, 1408702786668, 12277382510862, 110822101896083, 1034483164707440, 9972266139291771, 99147746245841106, 1015496134666939958

Offset: 0

Karol A. Penson, Apr 19 2002

nonn

a(n) is the total number of successions among all partitions of {1,2,...,n+1}; a succession is a pair (i,i+1) of consecutive integers lying in a block. For example, a(3)=15 because {1,2,3,4} has 6 partitions with 1 succession - 1/2/34, 1/23/4, 12/3/4, 14/23, 134/2, 124/3, 3 partitions with 2 successions - 1/234, 123/4, 12/34 and 1 partition with 3 successions - 1234. Thus a(3) = 6*1 + 3*2 + 1*3 = 15. - Augustine O. Munagi, Jul 01 2008
a(n) is the number of occurrences of integers in a list of all partitions of the set {1,...,n}. For example, the list 123, 1/23, 2/13, 3/12, 1/2/3 of all partitions of the set {1,2,3} requires 15 occurrences of integers each belonging to that set. [From Michael Hardy (hardy(AT)math.umn.edu), Nov 08 2008]
The bijection between the two foregoing characterizations is as follows: Fix x in {1,2,...,n} and associate x with the succession (x,x+1) which appears in some partitions of {1,2,...,n+1}. Replace x,x+1 by x and partition the n-set {1,2,...,x,x+2,...,n+1}, giving B(n) partitions. Thus the succession (x,x+1) occurs among partitions of {1,2,...,n+1} exactly B(n) times. - Augustine O. Munagi, Jun 02 2010

Alois P. Heinz, Table of n, a(n) for n = 0..574 (terms n=0..200 from Vincenzo Librandi)
Augustine O. Munagi, Extended set partitions with successions, European J. Combin. 29(5) (2008), 1298--1308.

Cf. A000110, A052889, A105479, A105480, A105481, A175757.

Row sums of A270236, A270701, A270702, A286416, A319298, A319375.

[n*Bell(n): n in [0..25]]; // Vincenzo Librandi, Mar 15 2014

with(combinat): a:=n->sum(numbcomb (n,0)*bell(n), j=1..n): seq(a(n), n=0..21); # Zerinvary Lajos, Apr 25 2007
with(combinat): a:=n->sum(bell(n), j=1..n): seq(a(n), n=0..21); # Zerinvary Lajos, Apr 25 2007
a:=n->sum(sum(Stirling2(n, k), j=1..n), k=1..n): seq(a(n), n=0..21); # Zerinvary Lajos, Jun 28 2007

a[n_] := n!*Coefficient[Series[x E^(E^x+x-1), {x, 0, n}], x, n]
Table[Sum[BellB[n, 1], {i, 1, n}], {n, 0, 21}] (* Zerinvary Lajos, Jul 16 2009 *)
Table[n*BellB[n], {n, 0, 20}] (* Vaclav Kotesovec, Mar 13 2014 *)

a(n)=local(t); if(n<0,0,t=exp(x+O(x^n)); n!*polcoeff(x*t*exp(t-1),n))

[bell_number(n)*n for n in range(22) ] # Zerinvary Lajos, Mar 14 2009

E.g.f: x*exp(x)*exp(exp(x)-1).
Sum_{k=1..n} n*binomial(n-1, k-1)*Bell(n-k), n >= 2. - Zerinvary Lajos, Nov 22 2006
a(n) ~ n^(n+1) * exp(n/LambertW(n)-1-n) / (sqrt(1+LambertW(n)) * LambertW(n)^n). - Vaclav Kotesovec, Mar 13 2014
a(n) = Sum_{k=1..n} k * A175757(n,k). - Alois P. Heinz, Mar 03 2020
a(n) = Sum_{j=0..n} n * Stirling2(n,j). - Detlef Meya, Apr 11 2024

A124427 Sum of the sizes of the blocks containing the element 1 in all set partitions of {1,2,...,n}.

Original entry on oeis.org

0, 1, 3, 9, 30, 112, 463, 2095, 10279, 54267, 306298, 1838320, 11677867, 78207601, 550277003, 4055549053, 31224520322, 250547144156, 2090779592827, 18110124715919, 162546260131455, 1509352980864191, 14478981877739094, 143299752100925452, 1461455003961745247

Offset: 0

Emeric Deutsch, Nov 10 2006

nonn

			a(3)=9 because the 5 (=A000110(3)) set partitions of {1,2,3} are 123, 12|3, 13|2, 1|23 and 1|2|3 and 3+2+2+1+1=9.

Alois P. Heinz, Table of n, a(n) for n = 0..575

Cf. A000110, A056857.
Column p=1 of A270236 or of A270702.
Main diagonal of A270701.

with(combinat): seq(add(k*binomial(n-1,k-1)*bell(n-k),k=1..n),n=0..30);

Table[Sum[Binomial[n-1,k-1] * BellB[n-k] * k, {k,1,n}], {n,0,22}] (* Geoffrey Critzer, Jun 14 2013 *)
Flatten[{0, Table[(n-1)*BellB[n-1] + BellB[n], {n, 1, 20}]}] (* Vaclav Kotesovec, Mar 19 2016, after Vladeta Jovovic *)

a(n) = Sum(k*binomial(n-1,k-1)*B(n-k), k=1..n) = Sum(k*A056857(n,k), k=1..n), where B(q) are the Bell numbers (A000110).
a(n) = (n-1)*B(n-1)+B(n). - Vladeta Jovovic, Nov 10 2006
a(n) ~ Bell(n) * (LambertW(n) + 1). - Vaclav Kotesovec, Jul 28 2021

a(0)=0 prepended by Alois P. Heinz, Mar 17 2016

A286416 Number T(n,k) of entries in the k-th last blocks of all set partitions of [n]; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 3, 1, 8, 6, 1, 24, 25, 10, 1, 83, 98, 63, 15, 1, 324, 399, 338, 135, 21, 1, 1400, 1746, 1727, 980, 257, 28, 1, 6609, 8271, 8874, 6426, 2455, 448, 36, 1, 33758, 42284, 47191, 40334, 20506, 5474, 730, 45, 1, 185136, 231939, 263458, 250839, 158827, 57239, 11128, 1128, 55, 1

Offset: 1

Alois P. Heinz, May 08 2017

			T(3,2) = 6 because the number of entries in the second last blocks of all set partitions of [3] (123, 12|3, 13|2, 1|23, 1|2|3) is 0+2+2+1+1 = 6.
Triangle T(n,k) begins:
     1;
     3,    1;
     8,    6,    1;
    24,   25,   10,    1;
    83,   98,   63,   15,    1;
   324,  399,  338,  135,   21,   1;
  1400, 1746, 1727,  980,  257,  28,  1;
  6609, 8271, 8874, 6426, 2455, 448, 36, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Wikipedia, Partition of a set

Columns k=1-2 give: A038561 (for n>1), A286433.
Main diagonal and first lower diagonal give: A000012, A000217.
Row sums give A070071.
Cf. A000110, A130534, A270236, A286232.

A346772 Total sum of block indices of the elements over all partitions of [n].

Original entry on oeis.org

0, 1, 5, 22, 100, 482, 2475, 13527, 78476, 481687, 3117962, 21218851, 151387882, 1129430737, 8790433999, 71222812912, 599577147056, 5235054113412, 47331036294905, 442462325254995, 4270909302907430, 42514043248222709, 435920900603529954, 4599155199953703373

Offset: 0

Alois P. Heinz, Aug 02 2021

nonn

			a(3) = 22 = 3 + 4 + 4 + 5 + 6, summing block indices 111, 112, 121, 122, 123 of the 5 partitions of [3]: 123, 12|3, 13|2, 1|23, 1|2|3.

Alois P. Heinz, Table of n, a(n) for n = 0..574
Wikipedia, Partition of a set

Row sums of A120057.

Cf. A000110, A070071, A105488, A126347, A270236.

b:= proc(n, m) option remember; `if`(n=0, [1, 0], add(
     (p-> p+[0, p[1]*j])(b(n-1, max(m, j))), j=1..m+1))
    end:
a:= n-> b(n, 0)[2]:
seq(a(n), n=0..25);

b[n_, m_] := b[n, m] = If[n == 0, {1, 0}, Sum[
     Function[p, p+{0, p[[1]]*j}][b[n-1, Max[m, j]]], {j, 1, m+1}]];
a[n_] := b[n, 0][[2]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 27 2022, after Alois P. Heinz *)

a(n) = Sum_{k=1..n} A120057(n,k).
a(n) = Sum_{k=0..n*(n-1)/2} (n+k) * A126347(n,k).
a(n) = Sum_{k=1..n} k * A270236(n,k).

A270529 Sum of the sizes of the (n+1)-th blocks in all set partitions of {1,2,...,2n+1}.

Original entry on oeis.org

1, 5, 47, 675, 13276, 334751, 10354804, 380797185, 16262852622, 792102157717, 43370872479317, 2638621340623857, 176656418678888190, 12910491906798508171, 1022900642521227415940, 87345042902079159197907, 7997120745886569461943400, 781580696472700788364550933

Offset: 0

Alois P. Heinz, Mar 18 2016

nonn

			a(1) = 5 = 0+1+1+2+1 = sum of the sizes of the second blocks in all A000110(3) = 5 set partitions of 3: 123, 12|3, 13|2, 1|23, 1|2|3.

Alois P. Heinz, Table of n, a(n) for n = 0..200
Wikipedia, Partition of a set

Cf. A000110, A270236, A285410.

b:= proc(n, m, k) option remember; `if`(n=0, [1, 0], add((p->p+
      `if`(j=k, [0, p[1]], 0))(b(n-1, max(m, j), k)), j=1..m+1))
    end:
a:= n-> b(2*n+1, 0, n+1)[2]:
seq(a(n), n=0..20);

b[n_, m_, k_] := b[n, m, k] = If[n == 0, {1, 0}, Sum[# + If[j == k, {0, #[[1]]}, 0]&[b[n - 1, Max[m, j], k]], {j, 1, m + 1}]];
a[n_] := b[2*n + 1, 0, n + 1][[2]];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 23 2018, translated from Maple *)

a(n) = A270236(2n+1,n+1).

a(n) ~ 2^(2*n+1/2) * n^(n-1/2) / (sqrt(Pi*(1-c)) * exp(n) * c^(n+1) * (2-c)^n), where c = -A226775 = -LambertW(-2*exp(-2)) = 0.4063757399599599... . - Vaclav Kotesovec, Mar 19 2016

A270494 Sum of the sizes of the second blocks in all set partitions of {1,2,...,n}.

Original entry on oeis.org

1, 5, 21, 88, 387, 1816, 9123, 48971, 279855, 1695902, 10856879, 73173016, 517597981, 3831970709, 29617983433, 238460465120, 1995828043987, 17333096360920, 155936489571399, 1451019052068763, 13945778132786915, 138259832617525950, 1412263078623261399

Offset: 2

Alois P. Heinz, Mar 18 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..575
Wikipedia, Partition of a set

Column p=2 of A270236.

b:= proc(n, m) option remember; `if`(n=0, [1, 0],
      add((p->`if`(j<3, [p[1], p[2]+p[1]*x^j], p))(
       b(n-1, max(m, j))), j=1..m+1))
    end:
a:= n-> coeff(b(n, 0)[2], x, 2):
seq(a(n), n=2..25);

b[n_, m_] := b[n, m] = If[n == 0, {1, 0}, Sum[Function[p, If[j < 3, {p[[1]], p[[2]] + p[[1]]*x^j}, p]][b[n-1, Max[m, j]]], {j, 1, m + 1}]];
a[n_] := Coefficient[b[n, 0][[2]], x, 2];
Table[a[n], {n, 2, 25}] (* Jean-François Alcover, May 27 2018, translated from Maple *)

A270495 Sum of the sizes of the third blocks in all set partitions of {1,2,...,n}.

Original entry on oeis.org

1, 8, 47, 253, 1345, 7304, 41193, 243152, 1506521, 9799547, 66844755, 477297022, 3560469469, 27692022408, 224128400923, 1884299045789, 16427961558365, 148293477761232, 1384008870213057, 13336887952918752, 132535336519342301, 1356662080571809755

Offset: 3

Alois P. Heinz, Mar 18 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..575
Wikipedia, Partition of a set

Column p=3 of A270236.

b:= proc(n, m) option remember; `if`(n=0, [1, 0],
      add((p->`if`(j<4, [p[1], p[2]+p[1]*x^j], p))(
       b(n-1, max(m, j))), j=1..m+1))
    end:
a:= n-> coeff(b(n, 0)[2], x, 3):
seq(a(n), n=3..25);

b[n_, m_] := b[n, m] = If[n == 0, {1, 0}, Sum[Function[p, If[j < 4, {p[[1]], p[[2]] + p[[1]]*x^j}, p]][b[n - 1, Max[m, j]]], {j, 1, m + 1}]];
a[n_] := Coefficient[b[n, 0][[2]], x, 3];
Table[a[n], {n, 3, 25}] (* Jean-François Alcover, May 27 2018, translated from Maple *)

A270496 Sum of the sizes of the fourth blocks in all set partitions of {1,2,...,n}.

Original entry on oeis.org

1, 12, 97, 675, 4418, 28396, 183615, 1211936, 8237223, 57944187, 422950882, 3206531728, 25247250641, 206313943476, 1747990803645, 15336960025775, 139187730958406, 1304967471569208, 12624893940830455, 125892638744630088, 1292581981392588771

Offset: 4

Alois P. Heinz, Mar 18 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..575
Wikipedia, Partition of a set

Column p=4 of A270236.

b:= proc(n, m) option remember; `if`(n=0, [1, 0],
      add((p->`if`(j<5, [p[1], p[2]+p[1]*x^j], p))(
       b(n-1, max(m, j))), j=1..m+1))
    end:
a:= n-> coeff(b(n, 0)[2], x, 4):
seq(a(n), n=4..30);

b[n_, m_] := b[n, m] = If[n == 0, {1, 0}, Sum[Function[p, If[j < 5, {p[[1]], p[[2]] + p[[1]]*x^j}, p]][b[n - 1, Max[m, j]]], {j, 1, m + 1}]];
a[n_] := Coefficient[b[n, 0][[2]], x, 4];
Table[a[n], {n, 4, 30}] (* Jean-François Alcover, May 27 2018, translated from Maple *)

cp's OEIS Frontend

A285362 Sum T(n,k) of the entries in the k-th blocks of all set partitions of [n]; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A185105 Number T(n,k) of entries in the k-th cycles of all permutations of {1,2,..,n}; each cycle is written with the smallest element first and cycles are arranged in increasing order of their first elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A070071 a(n) = n*B(n), where B(n) are the Bell numbers, A000110.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A124427 Sum of the sizes of the blocks containing the element 1 in all set partitions of {1,2,...,n}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A286416 Number T(n,k) of entries in the k-th last blocks of all set partitions of [n]; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

A346772 Total sum of block indices of the elements over all partitions of [n].

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A270529 Sum of the sizes of the (n+1)-th blocks in all set partitions of {1,2,...,2n+1}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A270494 Sum of the sizes of the second blocks in all set partitions of {1,2,...,n}.

Views