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,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

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

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

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

Sequence in context: A217930 A305371 A355018 * A199891 A339417 A351558

Adjacent sequences: A177253 A177254 A177255 * A177257 A177258 A177259

Keyword

nonn,tabf

Author

Emeric Deutsch, May 07 2010

Status

approved