A215771 Number T(n,k) of undirected labeled graphs on n nodes with exactly k cycle graphs as connected components; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 3, 7, 6, 1, 0, 12, 25, 25, 10, 1, 0, 60, 127, 120, 65, 15, 1, 0, 360, 777, 742, 420, 140, 21, 1, 0, 2520, 5547, 5446, 3157, 1190, 266, 28, 1, 0, 20160, 45216, 45559, 27342, 10857, 2898, 462, 36, 1, 0, 181440, 414144, 427275, 264925, 109935, 31899, 6300, 750, 45, 1

Offset

0,9

Comments

Also the Bell transform of A001710. For the definition of the Bell transform see A264428 and the links given there. - Peter Luschny, Jan 21 2016

Links

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

Example

T(4,1) = 3:  .1-2.  .1 2.  .1-2.
.            .| |.  .|X|.  . X .
.            .3-4.  .3 4.  .3-4.
.
T(4,2) = 7:  .1 2.  .1-2.  .1 2.  o1 2.  .1 2o  .1-2.  .1-2.
.            .| |.  .   .  . X .  . /|.  .|\ .  . \|.  .|/ .
.            .3 4.  .3-4.  .3 4.  .3-4.  .3-4.  o3 4.  .3 4o
.
T(4,3) = 6:  .1 2o  .1-2.  o1 2.  o1 2o  o1 2.  .1 2o
.            .|  .  .   .  .  |.  .   .  . / .  . \ .
.            .3 4o  o3 4o  o3 4.  .3-4.  .3 4o  o3 4.
.
T(4,4) = 1:  o1 2o
.            .   .
.            o3 4o
Triangle T(n,k) begins:
  1;
  0,   1;
  0,   1,   1;
  0,   1,   3,   1;
  0,   3,   7,   6,   1;
  0,  12,  25,  25,  10,   1;
  0,  60, 127, 120,  65,  15,  1;
  0, 360, 777, 742, 420, 140, 21,  1;

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)*ceil(i!/2), 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), 8); # Peter Luschny, Jan 21 2016

Mathematica

t[n_, k_] := t[n, k] = If[k < 0 || k > n, 0, If[n == 0, 1, Sum[Binomial[n-1, i]*t[n-1-i, k-1]*Ceiling[i!/2], {i, 0, n-k}]]]; Table[Table[t[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 18 2013, translated from Maple *)
rows = 10;
t = Table[If[n<2, 1, n!/2], {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 *)

Prog

(Sage) # uses[bell_matrix from A264428]
bell_matrix(lambda n: factorial(n)//2 if n>=2 else 1, 8)

Crossrefs

Columns k=0-10 give: A000007, A001710(n-1) for n>0, A215772, A215763, A215764, A215765, A215766, A215767, A215768, A215769, A215770.

Diagonal and lower diagonals give: A000012, A000217, A001296, A215773, A215774.

Row sums give A002135.

T(2n,n) gives A253276.

Sequence in context: A116089 A122016 A067882 * A110033 A213666 A166407

Adjacent sequences: A215768 A215769 A215770 * A215772 A215773 A215774

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 23 2012

Status

approved