A120095 Triangle T(n,k) = total of number at last index for all set partitions of n into k parts.

1, 1, 2, 1, 5, 3, 1, 11, 15, 4, 1, 23, 57, 34, 5, 1, 47, 195, 200, 65, 6, 1, 95, 633, 1010, 550, 111, 7, 1, 191, 1995, 4704, 3850, 1281, 175, 8, 1, 383, 6177, 20874, 24255, 11886, 2646, 260, 9, 1, 767, 18915, 89800, 143115, 97272, 31458, 4992, 369, 10

Offset

1,3

Links

Alois P. Heinz, Rows n = 1..150, flattened

Formula

T(n,k) = (k*(k+1)/2)*S2(n-1,k) + k*S2(n-1,k-1) = 1/2 (S2(n+1,k) + S2(n,k) - S2(n-1,k-2)) = k T(n-1,k) + T(n-1,k-1) + S2(n-2,k-2), where S2 is the Stirling numbers of the second kind (A008277).

Example

The set partitions of 4 objects into 2 parts are {1,1,1,2}, {1,1,2,1}, {1,1,2,2}, {1,2,1,1}, {1,2,1,2}, {1,2,2,1} and {1,2,2,2}. The last terms of these sum to 2+1+2+1+2+1+2 = 11, so T(4,2) = 11.
Table starts:
  1;
  1,  2;
  1,  5,   3;
  1, 11,  15,   4;
  1, 23,  57,  34,  5;
  1, 47, 195, 200, 65, 6;
  ...

Maple

b:= proc(n, m) option remember; `if`(n=0, 1, add((t->
     `if`(n=1, j*x^t, b(n-1, t)))(max(m, j)), j=1..m+1))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)):
seq(T(n), n=1..10);  # Alois P. Heinz, Aug 02 2021

Mathematica

b[n_, m_]:= b[n, m]= If[n==0, 1, Sum[
     If[n==1, j*x^#, b[n-1, #]]&[Max[m, j]], {j, m+1}]];
T[n_] := Table[Coefficient[#, x, i], {i, 1, n}]&[b[n, 0]];
Table[T[n], {n, 10}]//Flatten (* Jean-François Alcover, Aug 19 2021, after Alois P. Heinz *)

Prog

(Magma)
A120095:= func< n, k | (&+[Binomial(j+k, j+1)*StirlingSecond(n-1, k+j-1): j in [0..1]]) >;
[A120095(n, k): k in [1..n], n in [1..15]]; // G. C. Greubel, May 03 2023
(SageMath)
def A120095(n, k):
    return sum(binomial(j+k, j+1)*stirling_number2(n-1, k+j-1) for j in range(2))
flatten([[A120095(n, k) for k in range(1, n+1)] for n in range(1, 16)]) # G. C. Greubel, May 03 2023

Crossrefs

Cf. A008277, A120058.

Row sums are A087648(n-1).

Sequence in context: A330381 A210792 A105728 * A327631 A130197 A106513

Adjacent sequences: A120092 A120093 A120094 * A120096 A120097 A120098

Keyword

nonn,tabl

Author

Franklin T. Adams-Watters, Jun 07 2006

Status

approved