A177254 Triangle read by rows: T(n,k) is the number of partitions of the set {1,2,...,n} having k adjacent blocks (0 <= k <= n). An adjacent block is a block of the form (i, i+1, i+2, ...).
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 1, 4, 6, 3, 1, 5, 13, 17, 12, 4, 1, 21, 51, 61, 44, 20, 5, 1, 91, 219, 255, 185, 90, 30, 6, 1, 422, 1019, 1182, 867, 440, 160, 42, 7, 1, 2103, 5108, 5964, 4430, 2322, 896, 259, 56, 8, 1, 11226, 27448, 32373, 24406, 13118, 5292, 1638, 392, 72, 9, 1
Offset: 0
Examples
T(4,2)=6 because we have 1-234, 12-34, 123-4, 13-2-4, 14-2-3, and 1-24-3.
Triangle starts:
1;
0, 1;
0, 1, 1;
0, 2, 2, 1;
1, 4, 6, 3, 1;
5, 13, 17, 12, 4, 1;
21, 51, 61, 44, 20, 5, 1;
91, 219, 255, 185, 90, 30, 6, 1;
422, 1019, 1182, 867, 440, 160, 42, 7, 1;
2103, 5108, 5964, 4430, 2322, 896, 259, 56, 8, 1;
Links
- Alois P. Heinz, Rows n = 0..140, flattened
Programs
-
Maple
Q[0] := 1: for n to 10 do Q[n] := expand(u*subs(w = v, diff(Q[n-1], u))+u*subs(w = v, diff(Q[n-1], v))+w*(diff(Q[n-1], w))+w*subs(w = v, Q[n-1])) end do: for n from 0 to 10 do P[n] := sort(expand(subs({v = t, w = t, u = 1}, Q[n]))) end do; for n from 0 to 10 do seq(coeff(P[n], t, j), j = 0 .. n) end do; # yields sequence in triangular form
Formula
The row generating polynomial P[n](t) is given by P[n](t)=Q[n](1,t,t), where Q[n](u,v,w) is obtained recursively from Q[n](u,v,w) =u(dQ[n-1]/du){w=v} + u(dQ[n-1]/dv){w=v} + w(dQ[n-1]/dw) + w(Q[n-1])_{w=v}, Q[0]=1. Here Q[n](u,v,w) is the trivariate generating polynomial of the partitions of {1,2,...,n}, where u marks blocks that are not adjacent, v marks adjacent blocks not ending with n, and w marks adjacent blocks ending with n.
T(n, 0) = A168444(n).
Sum_{k=0..n} T(n, k) = A000110(n) (row sums).
Sum_{k=0..n} k*T(n, k) = A177255(n).
From G. C. Greubel, May 12 2024: (Start)
T(n, n) = 1.
T(n, n-1) = n-1, for n >= 1.
T(n, n-2) = A002378(n-2), for n >= 2.
T(n, n-3) = A162148(n-3), for n >= 3.
T(n, n-4) = A302560(n-3), for n >= 4. (End)
Comments