login
A336703
Rectangular array read by antidiagonals. T(n,k) is the number of length k walks from {} to [n] in the digraph representation of the superset/subset relation on P([n]) the powerset of [n], n>=0, k>=0.
0
1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 4, 1, 0, 1, 8, 14, 8, 1, 0, 1, 16, 50, 46, 16, 1, 0, 1, 32, 178, 278, 146, 32, 1, 0, 1, 64, 634, 1666, 1454, 454, 64, 1, 0, 1, 128, 2258, 9998, 14230, 7358, 1394, 128, 1, 0, 1, 256, 8042, 59986, 139750, 115546, 36590, 4246, 256, 1, 0
OFFSET
0,8
COMMENTS
The superset/subset relation on P([n]) is defined as: for all A,B in P([n]), A ~ B iff A is a subset of B or B is a subset of A.
LINKS
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 339.
EXAMPLE
1, 1, 1, 1, 1, 1, 1, 1, 1,...
0, 1, 2, 4, 8, 16, 32, 64, 128,...
0, 1, 4, 14, 50, 178, 634, 2258, 8042,...
0, 1, 8, 46, 278, 1666, 9998, 59986, 359918,...
0, 1, 16, 146, 1454, 14230, 139750, 1371494, 13461638,...
MATHEMATICA
(* gives first 7 rows and 11 columns in about 3 minutes *)
Table[a = Subsets[Range[n]]; f[list_] := Map[Apply[SubsetQ, #] &, list];
G = Map[f, Table[Table[{a[[i]], a[[j]]}, {i, 1, 2^n}], {j, 1, 2^n}]] //
Boole; H = (G - IdentityMatrix[2^n]) + Transpose[(G - IdentityMatrix[2^n]) + IdentityMatrix[2^n]]; b = Inverse[IdentityMatrix[2^n] - z H] // Simplify; MatrixForm[b]; nn = 10; CoefficientList[Series[b[[1, 2^n]], {z, 0, nn}], z], {n, 0, 6}] // Grid
CROSSREFS
Cf. A027649 (column k=3, number of edges in the digraph).
Sequence in context: A102728 A262495 A352687 * A323174 A295683 A165519
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Jul 31 2020
STATUS
approved