|
|
A049312
|
|
Number of graphs with a distinguished bipartite block, by number of vertices.
|
|
14
|
|
|
1, 2, 4, 8, 17, 38, 94, 258, 815, 3038, 13804, 78760, 580456, 5647602, 73645352, 1297920850, 31031370360, 1007551636038, 44432872400460, 2661065508648436, 216457998880015366, 23920728651724212120, 3593384834863975164882, 734240676501745813835934
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Calculate number of connected bipartite graphs + number of connected bipartite graphs with no duality automorphism, apply EULER transform.
Inverse Euler transform is A318870.
|
|
REFERENCES
|
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
|
|
LINKS
|
|
|
FORMULA
|
a(n) ~ 1/n! A047863(n) = 1/n! Sum_{k=0..n} binomial(n,k) * 2^(k(n-k)) (see Wright; see also Thm. 3.7 of the Troyka link, which cites Wright). - Justin M. Troyka, Oct 29 2018
|
|
EXAMPLE
|
a(2)=4: null graph with 0, 1 or 2 vertices in the distinguished block and complete graph with 1 vertex in distinguished block.
|
|
MAPLE
|
b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
{seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
end:
g:= proc(n, k) option remember; add(add(2^add(add(igcd(i, j)*
coeff(s, x, i)* coeff(t, x, j), j=1..degree(t)),
i=1..degree(s))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,
i=1..degree(s))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,
i=1..degree(t)), t=b(n+k$2)), s=b(n$2))
end:
A:= (n, k)-> g(min(n, k), abs(n-k)):
a:= d-> add(A(n, d-n), n=0..d):
|
|
MATHEMATICA
|
b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i<1, {}, Flatten @ Table[ Map[ Function[ {p}, p+j*x^i], b[n-i*j, i-1]], {j, 0, n/i}]]];
g[n_, k_] := g[n, k] = Sum[ Sum[ 2^Sum[Sum[GCD[i, j]*Coefficient[s, x, i]*Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n+k, n+k]}], {s, b[n, n]}];
A[n_, k_] := g[Min[n, k], Abs[n-k]];
a[d_] := Sum[A[n, d-n], {n, 0, d}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|