login
Number of graphs with a distinguished bipartite block, by number of vertices.
14

%I #55 Jul 06 2019 00:42:14

%S 1,2,4,8,17,38,94,258,815,3038,13804,78760,580456,5647602,73645352,

%T 1297920850,31031370360,1007551636038,44432872400460,2661065508648436,

%U 216457998880015366,23920728651724212120,3593384834863975164882,734240676501745813835934

%N Number of graphs with a distinguished bipartite block, by number of vertices.

%C Calculate number of connected bipartite graphs + number of connected bipartite graphs with no duality automorphism, apply EULER transform.

%C Inverse Euler transform is A318870.

%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

%H Alois P. Heinz, <a href="/A049312/b049312.txt">Table of n, a(n) for n = 0..40</a>

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H Karen L. Collins, Ann N. Trenk, <a href="http://arxiv.org/abs/1706.03092">Finding Balance: Split Graphs and Related Classes</a>, arXiv:1706.03092 [math.CO], June 2017.

%H M. Guay-Paquet, A. H. Morales and E. Rowland, <a href="http://arxiv.org/abs/1212.5356">Structure and enumeration of (3+ 1)-free posets</a>, arXiv preprint arXiv:1212.5356 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Feb 01 2013

%H J. M. Troyka, <a href="https://arxiv.org/abs/1803.07248">Split graphs: combinatorial species and asymptotics</a>, arXiv:1803.07248 [math.CO], 2018-2019.

%H J. M. Troyka, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p42">Split graphs: combinatorial species and asymptotics</a>, Electron. J. Combin., 26 (2019), #P2.42.

%H E. M. Wright, <a href="https://doi.org/10.1112/jlms/s2-25.1.7">The k-connectedness of bipartite graphs</a>, J. Lond. Math. Soc. (2), 25 (1982), 7-12.

%F 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

%e a(2)=4: null graph with 0, 1 or 2 vertices in the distinguished block and complete graph with 1 vertex in distinguished block.

%p b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},

%p {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))

%p end:

%p g:= proc(n, k) option remember; add(add(2^add(add(igcd(i, j)*

%p coeff(s, x, i)* coeff(t, x, j), j=1..degree(t)),

%p i=1..degree(s))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,

%p i=1..degree(s))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,

%p i=1..degree(t)), t=b(n+k$2)), s=b(n$2))

%p end:

%p A:= (n, k)-> g(min(n, k), abs(n-k)):

%p a:= d-> add(A(n, d-n), n=0..d):

%p seq(a(n), n=0..20); # _Alois P. Heinz_, Aug 01 2014

%t 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}]]];

%t 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]}];

%t A[n_, k_] := g[Min[n, k], Abs[n-k]];

%t a[d_] := Sum[A[n, d-n], {n, 0, d}];

%t Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Feb 25 2015, after _Alois P. Heinz_ *)

%Y Row sums of A028657.

%Y Cf. A048194, A318870.

%K nonn,nice

%O 0,2

%A _Peter J. Cameron_

%E More terms from _Vladeta Jovovic_, Jun 17 2000