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).

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

Author

Emeric Deutsch, May 07 2010

Keywords

• nonn
• tabf

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).

Examples

			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;
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened

Crossrefs

Cf. A000079, A000110, A177254, A177255, A177257.

Programs

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

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.