|
Search: id:A144164
|
|
|
| A144164 |
|
Number of simple graphs on n labeled nodes, where each maximally connected subgraph is either a tree or a cycle, also row sums of A144163. |
|
+0
2
|
|
| 1, 1, 2, 8, 45, 338, 3304, 40485, 602075, 10576466, 214622874, 4941785261, 127282939615, 3625467047196, 113140481638088, 3838679644895477, 140681280613912089, 5538276165405744140, 233086092164091031114
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
LINKS
|
Index entries for sequences related to trees
|
|
FORMULA
|
a(n) = Sum_{k=0..n} A144163(n,k).
|
|
EXAMPLE
|
a(3) = 8, because there are 8 simple graphs on 3 labeled nodes, where each maximally connected subgraph is either a tree or a cycle, with edge-counts 0(1), 1(3), 2(3), 3(1):
.1.2. .1-2. .1.2. .1.2. .1-2. .1.2. .1-2. .1-2.
..... ..... ../.. .|... ../.. .|/.. .|... .|/..
.3... .3... .3... .3... .3... .3... .3... .3...
|
|
MAPLE
|
f:= proc(n, k) option remember; local j; if k=0 then 1 elif k<0 or n<=k then 0 elif k=n-1 then n^(n-2) else add (binomial (n-1, j) * f(j+1, j) *f(n-1-j, k-j), j=0..k) fi end: c:= proc(n, k) option remember; local i, j; if k=0 then 1 elif k<0 or n<k then 0 else c(n-1, k) +add (mul (n-i, i=1..j) *c(n-1-j, k-j-1), j=2..k)/2 fi end: T:= proc(n, k) f(n, k) +add (binomial(n, j) *f(n-j, k-j) *c(j, j), j=3..k) end: a:= n-> add (T(n, k), k=0..n): seq (a(n), n=0..25);
|
|
CROSSREFS
|
Row sums of triangle A144163. Cf. A138464, A144161, A007318, A000142.
Sequence in context: A152401 A009345 A084553 this_sequence A003091 A119501 A006664
Adjacent sequences: A144161 A144162 A144163 this_sequence A144165 A144166 A144167
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 12 2008
|
|
|
Search completed in 0.002 seconds
|
