A215861 Number T(n,k) of simple labeled graphs on n nodes with exactly k connected components that are trees or cycles; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 4, 3, 1, 0, 19, 19, 6, 1, 0, 137, 135, 55, 10, 1, 0, 1356, 1267, 540, 125, 15, 1, 0, 17167, 15029, 6412, 1610, 245, 21, 1, 0, 264664, 218627, 90734, 23597, 3990, 434, 28, 1, 0, 4803129, 3783582, 1515097, 394506, 70707, 8694, 714, 36, 1

Offset: 0

Author

Alois P. Heinz, Aug 25 2012

Keywords

• nonn
• tabl

Comments

Also the Bell transform of A215851(n+1). For the definition of the Bell transform see A264428 and the links given there. - Peter Luschny, Jan 21 2016

Examples

			T(4,2) = 19:
  .1 2.  .1 2.  .1-2.  .1-2.  .1 2.  .1 2.  .1 2.  .1 2.  .1 2.  .1 2.
  . /|.  .|\ .  .|/ .  . \|.  . /|.  .  |.  . / .  .|\ .  . \ .  .|  .
  .4-3.  .4-3.  .4 3.  .4 3.  .4 3.  .4-3.  .4-3.  .4 3.  .4-3.  .4-3.
  .
  .1-2.  .1-2.  .1 2.  .1-2.  .1-2.  .1 2.  .1-2.  .1 2.  .1 2.
  .|  .  . / .  .|/ .  . \ .  .  |.  . \|.  .   .  .| |.  . X .
  .4 3.  .4 3.  .4 3.  .4 3.  .4 3.  .4 3.  .4-3.  .4 3.  .4 3.
Triangle T(n,k) begins:
  1;
  0,     1;
  0,     1,     1;
  0,     4,     3,    1;
  0,    19,    19,    6,    1;
  0,   137,   135,   55,   10,   1;
  0,  1356,  1267,  540,  125,  15,   1;
  0, 17167, 15029, 6412, 1610, 245,  21,  1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Columns k=0-10 give: A000007, A215851, A215852, A215853, A215854, A215855, A215856, A215857, A215858, A215859, A215860.

Diagonal and lower diagonals give: A000012, A000217, A215862, A215863, A215864, A215865.

Row sums give: A144164.

T(2n,n) gives A309313.

Programs

Maple

T:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
      `if`(n=0, 1, add(binomial(n-1, i)*T(n-1-i, k-1)*
      `if`(i<2, 1, i!/2 +(i+1)^(i-1)), i=0..n-k)))
    end:
seq(seq(T(n, k), k=0..n), n=0..12);
# Alternatively, with the function BellMatrix defined in A264428:
BellMatrix(n -> `if`(n<2, 1, n!/2+(n+1)^(n-1)), 8); # Peter Luschny, Jan 21 2016

Mathematica

t[0, 0] = 1; t[n_, k_] /; k < 0 || k > n = 0; t[n_, k_] := t[n, k] =Sum[ Binomial[n-1, i]*t[n-1-i, k-1]* If[i < 2, 1, i!/2 + (i+1)^(i-1)], {i, 0, n-k}]; Table[t[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 07 2013 *)
(* Alternatively, with the function BellMatrix defined in A264428: *)
g[n_] =  If[n < 2, 1, n!/2 + (n+1)^(n-1)]; BellMatrix[g, 8] (* Peter Luschny, Jan 21 2016 *)
rows = 11;
t = Table[If[n<2, 1, n!/2 + (n+1)^(n-1)], {n, 0, rows}];
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 0, rows}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)

Sage

# uses[bell_matrix from A264428]
bell_matrix(lambda n: factorial(n)//2 + (n+1)^(n-1) if n>=2 else 1, 8) # Peter Luschny, Jan 21 2016

Formula

T(0,0) = 1, T(n,k) = 0 for k<0 or k>n, and otherwise T(n,k) = Sum_{i=0..n-k} C(n-1,i)*T(n-1-i,k-1)*h(i) with h(i) = 1 for i<2 and h(i) = i!/2 + (i+1)^(i-1) else.