A336703 - OEIS

%I #11 Aug 02 2020 01:50:40

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

%T 178,278,146,32,1,0,1,64,634,1666,1454,454,64,1,0,1,128,2258,9998,

%U 14230,7358,1394,128,1,0,1,256,8042,59986,139750,115546,36590,4246,256,1,0

%N 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.

%C 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.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 339.

%e 1, 1, 1,  1,   1,    1,     1,      1,       1,...

%e 0, 1, 2,  4,   8,    16,    32,     64,      128,...

%e 0, 1, 4,  14,  50,   178,   634,    2258,    8042,...

%e 0, 1, 8,  46,  278,  1666,  9998,   59986,   359918,...

%e 0, 1, 16, 146, 1454, 14230, 139750, 1371494, 13461638,...

%t (* gives first 7 rows and 11 columns in about 3 minutes *)

%t Table[a = Subsets[Range[n]];f[list_] := Map[Apply[SubsetQ, #] &, list];

%t   G = Map[f,Table[Table[{a[[i]], a[[j]]}, {i, 1, 2^n}], {j, 1, 2^n}]] //

%t     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

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

%K nonn,tabl

%O 0,8

%A _Geoffrey Critzer_, Jul 31 2020