|
Search: id:A144228
|
|
|
| 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. |
|
+0
3
|
|
| 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; listen)
|
|
|
OFFSET
|
0,8
|
|
|
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). [From Vladeta Jovovic (vladeta(AT)eunet.yu), 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);
|
|
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: A086626 A144163 A080858 this_sequence A083029 A084546 A026515
Adjacent sequences: A144225 A144226 A144227 this_sequence A144229 A144230 A144231
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 15 2008
|
|
|
Search completed in 0.002 seconds
|
