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.

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

Author

Geoffrey Critzer, Jul 31 2020

Keywords

• nonn
• tabl

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.

Examples

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

Links

• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 339.

Crossrefs

Cf. A027649 (column k=3, number of edges in the digraph).

Programs

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