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.

1, 2, 1, 6, 3, 4, 32, 12, 16, 38, 320, 80, 80, 190, 728, 6144, 960, 640, 1140, 4368, 26704, 229376, 21504, 8960, 10640, 30576, 186928, 1866256, 16777216, 917504, 229376, 170240, 326144, 1495424, 14930048, 251548592, 2415919104, 75497472, 11010048, 4902912, 5870592, 17945088, 134370432, 2263937328, 66296291072

Offset: 1

Author

Geoffrey Critzer, Mar 28 2013

Keywords

• nonn
• tabl

Examples

			Triangle T(n,k) begins:
       1;
       2,     1;
       6,     3,    4;
      32,    12,   16,    38;
     320,    80,   80,   190,   728;
    6144,   960,  640,  1140,  4368,  26704;
  229376, 21504, 8960, 10640, 30576, 186928, 1866256;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..45, flattened

Crossrefs

Cf. A001187, A006125, A123903 (column 1), A125207 (row sums), A182166 (column 2).

Programs

Magma

function b(n) // b = A001187
  if n eq 0 then return 1;
  else return 2^Binomial(n,2) - (&+[Binomial(n-1,j-1)*2^Binomial(n-j,2)*b(j): j in [0..n-1]]);
  end if; return b;
end function;
A223894:= func< n,k | Binomial(n,k)*2^Binomial(n-k,2)*b(k) >;
[A223894(n,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Oct 03 2022

Maple

b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
      add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)
    end:
T:= (n, k)-> binomial(n, k)*b(k)*2^((n-k)*(n-k-1)/2):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Aug 26 2013

Mathematica

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

SageMath

@CachedFunction
def b(n): # b = A001187
    if (n==0): return 1
    else: return 2^binomial(n,2) - sum(binomial(n-1,j-1)*2^binomial(n-j,2)*b(j) for j in range(n))
def A223894(n,k): return binomial(n,k)*2^binomial(n-k,2)*b(k)
flatten([[A223894(n,k) for k in range(1,n+1)] for n in range(1,13)]) # G. C. Greubel, Oct 03 2022

Formula

E.g.f. for column k: A001187(n)*x^n/n!*A(x) where A(x) is the e.g.f. for A006125.

Sum_{k=0..n} T(n, k) = A125207(n).

T(n, 1) = A123903(n).

T(n, 2) = A182166(n).

T(n, n) = A001187(n). - G. C. Greubel, Oct 03 2022