|
| |
|
|
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, A215861.
|
|
4
|
|
|
|
1, 1, 2, 8, 45, 338, 3304, 40485, 602075, 10576466, 214622874, 4941785261, 127282939615, 3625467047196, 113140481638088, 3838679644895477, 140681280613912089, 5538276165405744140, 233086092164091031114, 10443453353262112373541, 496313160155209940833001
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) ~ c * n^(n-2), where c = 1.66789780037... . - Vaclav Kotesovec, Sep 08 2014
|
|
|
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);
|
|
|
MATHEMATICA
|
f[n_, k_] := f[n, k] = Module[{j}, Which[k == 0, 1, k<0 || n <= k, 0, k == n-1, n^(n-2), True, Sum[Binomial[n-1, j]*f[j+1, j]*f[n-1-j, k-j], {j, 0, k}]]]; c[n_, k_] := c[n, k] = Module[{i, j}, If[k == 0, 1, If[k<0 || n<k, 0, c[n-1, k]+Sum[Product[n-i, {i, 1, j}]*c[n-1-j, k-j-1], {j, 2, k}]/2]]]; T[n_, k_] := f[n, k]+Sum[Binomial[n, j]*f[n-j, k-j]*c[j, j], {j, 3, k}]; a[n_] := Sum[T[n, k], {k, 0, n}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 05 2014, after Alois P. Heinz *)
|
|
|
PROG
|
(Python)
from sympy.core.cache import cacheit
from sympy import binomial, prod
@cacheit
def f(n, k): return 1 if k==0 else 0 if k<0 or n<=k else n**(n - 2) if k == n - 1 else sum(binomial(n - 1, j)*f(j + 1, j)*f(n - 1 - j, k - j) for j in range(k + 1))
@cacheit
def c(n, k): return 1 if k==0 else 0 if k<0 or n<k else c(n - 1, k) + sum(prod(n - i for i in range(1, j + 1)) * c(n - 1 - j, k - j - 1) for j in range(2, k + 1))//2
def T(n, k): return f(n, k) + sum(binomial(n, j)*f(n - j, k - j)*c(j, j) for j in range(3, k + 1))
def a(n): return sum(T(n, k) for k in range(n + 1))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
