cp's OEIS Frontend

A223894 Triangular array read by rows: T(n,k) is the number of connected components with size k summed over all simple labeled graphs on n nodes; n>=1, 1<=k<=n.

%I A223894 #21 Oct 07 2022 05:49:10
%S A223894 1,2,1,6,3,4,32,12,16,38,320,80,80,190,728,6144,960,640,1140,4368,
%T A223894 26704,229376,21504,8960,10640,30576,186928,1866256,16777216,917504,
%U A223894 229376,170240,326144,1495424,14930048,251548592,2415919104,75497472,11010048,4902912,5870592,17945088,134370432,2263937328,66296291072
%N A223894 Triangular array read by rows: T(n,k) is the number of connected components with size k summed over all simple labeled graphs on n nodes; n>=1, 1<=k<=n.
%H A223894 Alois P. Heinz, <a href="/A223894/b223894.txt">Rows n = 1..45, flattened</a>
%F A223894 E.g.f. for column k: A001187(n)*x^n/n!*A(x) where A(x) is the e.g.f. for A006125.
%F A223894 Sum_{k=0..n} T(n, k) = A125207(n).
%F A223894 T(n, 1) = A123903(n).
%F A223894 T(n, 2) = A182166(n).
%F A223894 T(n, n) = A001187(n). - _G. C. Greubel_, Oct 03 2022
%e A223894 Triangle T(n,k) begins:
%e A223894        1;
%e A223894        2,     1;
%e A223894        6,     3,    4;
%e A223894       32,    12,   16,    38;
%e A223894      320,    80,   80,   190,   728;
%e A223894     6144,   960,  640,  1140,  4368,  26704;
%e A223894   229376, 21504, 8960, 10640, 30576, 186928, 1866256;
%e A223894   ...
%p A223894 b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
%p A223894       add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)
%p A223894     end:
%p A223894 T:= (n, k)-> binomial(n, k)*b(k)*2^((n-k)*(n-k-1)/2):
%p A223894 seq(seq(T(n, k), k=1..n), n=1..10);  # _Alois P. Heinz_, Aug 26 2013
%t A223894 nn = 9; f[list_] := Select[list, # > 0 &]; g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; a = Drop[Range[0, nn]! CoefficientList[Series[Log[g] + 1, {x, 0, nn}], x], 1]; Map[f, Drop[Transpose[Table[Range[0, nn]! CoefficientList[Series[a[[n]] x^n/n! g, {x, 0, nn}], x], {n, 1, nn}]], 1]] // Grid
%o A223894 (Magma)
%o A223894 function b(n) // b = A001187
%o A223894   if n eq 0 then return 1;
%o A223894   else return 2^Binomial(n,2) - (&+[Binomial(n-1,j-1)*2^Binomial(n-j,2)*b(j): j in [0..n-1]]);
%o A223894   end if; return b;
%o A223894 end function;
%o A223894 A223894:= func< n,k | Binomial(n,k)*2^Binomial(n-k,2)*b(k) >;
%o A223894 [A223894(n,k): k in [1..n], n in [1..12]]; // _G. C. Greubel_, Oct 03 2022
%o A223894 (SageMath)
%o A223894 @CachedFunction
%o A223894 def b(n): # b = A001187
%o A223894     if (n==0): return 1
%o A223894     else: return 2^binomial(n,2) - sum(binomial(n-1,j-1)*2^binomial(n-j,2)*b(j) for j in range(n))
%o A223894 def A223894(n,k): return binomial(n,k)*2^binomial(n-k,2)*b(k)
%o A223894 flatten([[A223894(n,k) for k in range(1,n+1)] for n in range(1,13)]) # _G. C. Greubel_, Oct 03 2022
%Y A223894 Cf. A001187, A006125, A123903 (column 1), A125207 (row sums), A182166 (column 2).
%K A223894 nonn,tabl
%O A223894 1,2
%A A223894 _Geoffrey Critzer_, Mar 28 2013