cp's OEIS Frontend

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.

%I A336703 #11 Aug 02 2020 01:50:40
%S A336703 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 A336703 178,278,146,32,1,0,1,64,634,1666,1454,454,64,1,0,1,128,2258,9998,
%U A336703 14230,7358,1394,128,1,0,1,256,8042,59986,139750,115546,36590,4246,256,1,0
%N 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.
%C A336703 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 A336703 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 339.
%e A336703 1, 1, 1,  1,   1,    1,     1,      1,       1,...
%e A336703 0, 1, 2,  4,   8,    16,    32,     64,      128,...
%e A336703 0, 1, 4,  14,  50,   178,   634,    2258,    8042,...
%e A336703 0, 1, 8,  46,  278,  1666,  9998,   59986,   359918,...
%e A336703 0, 1, 16, 146, 1454, 14230, 139750, 1371494, 13461638,...
%t A336703 (* gives first 7 rows and 11 columns in about 3 minutes *)
%t A336703 Table[a = Subsets[Range[n]];f[list_] := Map[Apply[SubsetQ, #] &, list];
%t A336703   G = Map[f,Table[Table[{a[[i]], a[[j]]}, {i, 1, 2^n}], {j, 1, 2^n}]] //
%t A336703     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 A336703 Cf. A027649 (column k=3, number of edges in the digraph).
%K A336703 nonn,tabl
%O A336703 0,8
%A A336703 _Geoffrey Critzer_, Jul 31 2020