A144161 Triangle read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges that are node-disjoint unions of undirected cycle subgraphs.

1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 4, 3, 1, 0, 0, 10, 15, 12, 1, 0, 0, 20, 45, 72, 70, 1, 0, 0, 35, 105, 252, 490, 465, 1, 0, 0, 56, 210, 672, 1960, 3720, 3507, 1, 0, 0, 84, 378, 1512, 5880, 16740, 31563, 30016, 1, 0, 0, 120, 630, 3024, 14700, 55800, 157815, 300160, 286884

Offset

0,14

Links

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

Formula

T(n,0) = 1, T(n,k) = 0 if k<0 or n<k, else T(n,k) = T(n-1,k) + 1/2 * Sum_{j=2..k} T(n-1-j,k-j-1) * Product_{i=1..j} (n-i).

Example

T(4,3) = 4, because there are 4 simple graphs with 3 edges that are node-disjoint unions of undirected cycle subgraphs:
  .1.2. .1.2. .1-2. .1-2.
  ../|. .|\.. ..\|. .|/..
  .3-4. .3-4. .3.4. .3.4.
T(6,6) = C(6,3)/2+5!/2 = 70.
Triangle begins:
  1;
  1, 0;
  1, 0, 0;
  1, 0, 0,  1;
  1, 0, 0,  4,  3;
  1, 0, 0, 10, 15, 12;
  1, 0, 0, 20, 45, 72, 70;
  ...

Maple

T:= proc(n, k) option remember; local i, j; if k=0 then 1 elif k<0 or n<k then 0 else T(n-1, k) +add(mul(n-i, i=1..j) *T(n-1-j, k-j-1), j=2..k)/2 fi end: seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

T[n_, k_] := T[n, k] = Module[{i, j}, If[k == 0, 1, If[k < 0 || n < k, 0, T[n - 1, k] + Sum[Product[n - i, {i, 1, j}]*T[n - 1 - j, k - j - 1], {j, 2, k}]/2 ]]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

Prog

(Python)
from sympy.core.cache import cacheit
from operator import mul
from functools import reduce
@cacheit
def T(n, k): return 1 if k==0 else 0 if k<0 or n<k else T(n - 1, k) + sum([reduce(mul, [n - i for i in range(1, j + 1)])*T(n - 1 - j, k - j - 1) for j in range(2, k + 1)])//2
for n in range(21): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Aug 07 2017

Crossrefs

Columns k=0, 1+2, 3-4 give: A000012, A000004, A000292, A050534.

Main diagonal gives A001205.

Row sums give: A108246.

Cf. A007318, A000142.

Sequence in context: A010102 A326477 A285650 * A054669 A131027 A133475

Adjacent sequences: A144158 A144159 A144160 * A144162 A144163 A144164

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 12 2008

Status

approved