login
A177256
Triangle read by rows: T(n,k) is the number of partitions of the set {1,2,...,n} having exactly k blocks that do not consist of consecutive integers (0<=k<=floor(n/2); a singleton is considered a block of consecutive integers).
4
1, 1, 2, 0, 4, 1, 8, 6, 1, 16, 25, 11, 32, 89, 77, 5, 64, 290, 433, 90, 128, 893, 2132, 951, 36, 256, 2645, 9602, 7710, 934, 512, 7618, 40589, 53137, 13790, 329, 1024, 21489, 163739, 328119, 152600, 11599, 2048, 59665, 637587, 1872748, 1409791, 228103
OFFSET
0,3
COMMENTS
Row n contains 1+ floor(n/2) entries.
Sum of entries in row n = A000110(n) (the Bell numbers).
T(n,0) = 2^{n-1} (A000079).
Sum(k*a(n,k),k>=0) = A177257(n).
LINKS
FORMULA
The row generating polynomial P[n](u) is given by P[n](u)=Q[n](u,1,1), 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 do not consist of consecutive integers, v marks blocks consisting of consecutive integers and not ending with n, and w marks blocks consisting of consecutive integers and ending with n.
EXAMPLE
T(4,1)=6 because we have 134-2, 124-3, 14-23, 1-24-3, 14-2-3, and 13-2-4.
Triangle starts:
1;
1;
2,0;
4,1;
8,6,1;
16,25,11;
32,89,77,5;
MAPLE
Q[0] := 1: for n to 12 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 12 do P[n] := sort(expand(subs({v = 1, w = 1}, Q[n]))) end do: for n from 0 to 12 do seq(coeff(P[n], u, j), j = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, May 07 2010
STATUS
approved