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
Examples
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; ...
Links
- Alois P. Heinz, Rows n = 0..50, flattened
- Wikipedia, Partition of a set
Crossrefs
Programs
-
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 *)