A370945 Number T(n,k) of partitions of [n] whose singletons sum to k; triangle T(n,k), n>=0, 0<=k<=A000217(n), read by rows.

1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 4, 1, 1, 2, 2, 2, 1, 1, 0, 0, 1, 11, 4, 4, 5, 5, 6, 3, 3, 3, 3, 2, 1, 1, 0, 0, 1, 41, 11, 11, 15, 15, 19, 20, 13, 10, 11, 8, 8, 5, 4, 4, 3, 2, 1, 1, 0, 0, 1, 162, 41, 41, 52, 52, 63, 67, 78, 41, 45, 39, 39, 33, 30, 20, 17, 14, 10, 10, 6, 5, 4, 3, 2, 1, 1, 0, 0, 1

Offset

0,15

Links

Alois P. Heinz, Rows n = 0..50, flattened

Wikipedia, Partition of a set

Formula

Sum_{k=0..A000217(n)} k * T(n,k) = A105479(n+1).

T(n,A161680(n)) = A370946(n).

T(n,A000217(n)) = 1.

Example

T(4,0) = 4: 1234, 12|34, 13|24, 14|23.
T(4,1) = 1: 1|234.
T(4,2) = 1: 134|2.
T(4,3) = 2: 124|3, 1|2|34.
T(4,4) = 2: 123|4, 1|24|3.
T(4,5) = 2: 1|23|4, 14|2|3.
T(4,6) = 1: 13|2|4.
T(4,7) = 1: 12|3|4.
T(4,10) = 1: 1|2|3|4.
Triangle T(n,k) begins:
   1;
   0, 1;
   1, 0, 0, 1;
   1, 1, 1, 1, 0, 0, 1;
   4, 1, 1, 2, 2, 2, 1, 1, 0, 0, 1;
  11, 4, 4, 5, 5, 6, 3, 3, 3, 3, 2, 1, 1, 0, 0, 1;
  ...

Maple

h:= proc(n) option remember; `if`(n=0, 1,
      add(h(n-j)*binomial(n-1, j-1), j=2..n))
    end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, h(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
T:= (n, k)-> b(k, min(n, k), n):
seq(seq(T(n, k), k=0..n*(n+1)/2), n=0..7);

Mathematica

h[n_] := h[n] = If[n == 0, 1,
    Sum[h[n-j]*Binomial[n-1, j-1], {j, 2, n}]];
b[n_, i_, m_] := b[n, i, m] = If[n > i*(i + 1)/2, 0,
    If[n == 0, h[m], b[n, i - 1, m] + b[n - i, Min[n - i, i - 1], m - 1]]];
T[n_, k_] := b[k, Min[n, k], n];
Table[Table[T[n, k], { k, 0, n*(n + 1)/2}], {n, 0, 7}] // Flatten (* Jean-François Alcover, Mar 12 2024, after Alois P. Heinz *)

Crossrefs

Column k=0 gives A000296.

Row sums give A000110.

Row lengths give A000124.

Reversed rows converge to A370946.

T(n,n) gives A370947.

Cf. A000217, A053632, A105479, A369596.

Sequence in context: A360916 A360918 A100261 * A016526 A247341 A030747

Adjacent sequences: A370942 A370943 A370944 * A370946 A370947 A370948

Keyword

nonn,tabf

Author

Alois P. Heinz, Mar 06 2024

Status

approved