login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

LINKS

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

FORMULA

T(n,0) = 1, T(n,k) = 0 if k<0 or n<k, else T(n,k) = Sum_{j=0..k} C(n-1,j) (A000272(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*ln(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

EXAMPLE

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;

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<k then 0 else add(binomial(n-1, j) *((j+1)^(j-1) *T(n-j-1, k-j) +cy(j+1) *T(n-j-1, k-j-1)), j=0..k) fi end: seq(seq(T(n, k), k=0..n), n=0..11);

MATHEMATICA

t[_, 0] = 1; t[n_, k_] /; (k<0 || n<k) = 0; t[n_, k_] := t[n, k] = Sum[Binomial[n-1, j]*(t[n-j-1, k-j]*(j+1)^(j-1) + 1/2*j!*Sum[1/((j+1)^m*(j-m+1)!), {m, 3, j+1}]*t[n-j-1, k-j-1]*(j+1)^(j+1)), {j, 0, k}]; Flatten[Table[t[n, k], {n, 0, 11}, {k, 0, n}]] (* Jean-Fran├žois Alcover, Jan 15 2014, after Maple *)

CROSSREFS

Columns 0-3 give: A000012, A000217, A050534, A093566. Diagonal gives: A137916. Row sums give: A133686. Cf. A000272, A057500, A007318, A000142, A129271.

Sequence in context: A232967 A144163 A080858 * A083029 A084546 A174116

Adjacent sequences:  A144225 A144226 A144227 * A144229 A144230 A144231

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Sep 15 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

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

Last modified July 30 05:05 EDT 2014. Contains 245052 sequences.