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

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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

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 | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 9 06:57 EST 2016. Contains 278963 sequences.