A144228 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph has at most one cycle.

1, 1, 0, 1, 1, 0, 1, 3, 3, 1, 1, 6, 15, 20, 15, 1, 10, 45, 120, 210, 222, 1, 15, 105, 455, 1365, 2913, 3670, 1, 21, 210, 1330, 5985, 20139, 49294, 68820, 1, 28, 378, 3276, 20475, 97860, 362670, 976560, 1456875, 1, 36, 630, 7140, 58905, 376236, 1914276, 7663500, 22089870, 34506640

Offset: 0

Author

Alois P. Heinz, Sep 15 2008

Keywords

• nonn
• tabl

Examples

			T(4,4) = 15, because there are 15 simple graphs on 4 labeled nodes with 4 edges where each maximally connected subgraph has at most one cycle:
  1-2  1-2  1-2  1-2  1-2  1-2  1 2  1 2  1-2  1 2  1 2  1-2  1-2  1-2  1 2
  |/|  |X   |/   |\|   X|   \|  |/|   X|   /|  |\|  |X   |\   | |   X   |X|
  4 3  4 3  4-3  4 3  4 3  4-3  4-3  4-3  4-3  4-3  4-3  4-3  4-3  4-3  4 3
Triangle begins:
  1;
  1,  0;
  1,  1,  0;
  1,  3,  3,   1;
  1,  6, 15,  20,  15;
  1, 10, 45, 120, 210, 222;
  ...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..140, flattened

Crossrefs

Columns k=0-3 give: A000012, A000217, A050534, A093566.

Main diagonal gives A137916.

Row sums give: A133686.

T(2n,n) gives A369828.

Cf. A000272, A057500, A007318, A000142, A129271.

Programs

Maple

cy:= proc(n) option remember; local t; binomial(n-1, 2) *add((n-3)! /(n-2-t)! *n^(n-2-t), t=1..n-2) end: T:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n
				

Mathematica

t[, 0] = 1; t[n, k_] /; (k<0 || nJean-François Alcover, Jan 15 2014, after Maple *)

Formula

T(n,0) = 1, T(n,k) = 0 if k<0 or nA000272(j+1) T(n-j-1,k-j) + A057500(j+1) T(n-j-1,k-j-1)).

E.g.f.: exp(B(x,y)), where B(x,y) = Sum(Sum(A062734(n,k)*y^k*x^n/n!, k=0..n), n=1..infinity) = -1/2*log(1+LambertW(-x*y))+1/2*LambertW(-x*y) -1/4*LambertW(-x*y)^2-1/y *(LambertW(-x*y)+1/2 *LambertW(-x*y)^2). - Vladeta Jovovic, Sep 16 2008