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

Author

Alois P. Heinz, Sep 12 2008

Keywords

• nonn
• tabl

Examples

			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;
  ...
		

Links

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

Crossrefs

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

Main diagonal gives A001205.

Row sums give: A108246.

Cf. A007318, A000142.

Programs

Maple

T:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n
				

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 *)

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 nIndranil Ghosh, Aug 07 2017

Formula

T(n,0) = 1, T(n,k) = 0 if k<0 or n

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.