A318870 -id:A318870 - cp's OEIS frontend

A005142 Number of connected bipartite graphs with n nodes.

1, 1, 1, 1, 3, 5, 17, 44, 182, 730, 4032, 25598, 212780, 2241730, 31193324, 575252112, 14218209962, 472740425319, 21208887576786, 1286099113807999, 105567921675718772, 11743905783670560579, 1772771666309380358809, 363526952035325887859823, 101386021137641794979558045

Offset: 0

N. J. A. Sloane

Also, the number of unlabeled connected bicolored graphs having n nodes; the color classes may be interchanged. - Robert W. Robinson
Also, for n>1, number of connected triangle-free graphs on n nodes with chromatic number 2. - Keith M. Briggs, Mar 21 2006 (cf. A116079).
Also, first diagonal of triangle in A126736.
EULER transform of [1, 1, 1, 3, 5, 17, ...] is A033995 [1, 2, 3, 7, 13, ...]. - Michael Somos, May 13 2019

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50
Jean-François Alcover, Mathematica program
Keith M. Briggs, Combinatorial Graph Theory
CombOS - Combinatorial Object Server, Generate graphs
P. Hanlon, The enumeration of bipartite graphs, Discrete Math. 28 (1979), 49-57.
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Bipartite Graph.
Eric Weisstein's World of Mathematics, n-Chromatic Graph
Eric Weisstein's World of Mathematics, n-Colorable Graph
Jonathan Wurtz and Danylo Lykov, The fixed angle conjecture for QAOA on regular MaxCut graphs, arXiv:2107.00677 [quant-ph], 2021.

Cf. A033995, A116079, A318869, A318870.

Mathematica
```
(* See the links section. *)
```

a(2*n+1) = A318870(2*n+1)/2, a(2*n) = (a(n) + A318869(n) + A318870(2*n) - A318870(n))/2. - Andrew Howroyd, Sep 04 2018

More terms from Ronald C. Read.
a(0)=1 prepended by Max Alekseyev, Jun 24 2013
Terms a(21) and beyond from Andrew Howroyd, Sep 04 2018

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

Original entry on oeis.org

1, 2, 4, 8, 17, 38, 94, 258, 815, 3038, 13804, 78760, 580456, 5647602, 73645352, 1297920850, 31031370360, 1007551636038, 44432872400460, 2661065508648436, 216457998880015366, 23920728651724212120, 3593384834863975164882, 734240676501745813835934

Offset: 0

Peter J. Cameron

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

Inverse Euler transform is A318870.

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

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

Alois P. Heinz, Table of n, a(n) for n = 0..40
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Karen L. Collins, Ann N. Trenk, Finding Balance: Split Graphs and Related Classes, arXiv:1706.03092 [math.CO], June 2017.
M. Guay-Paquet, A. H. Morales and E. Rowland, Structure and enumeration of (3+ 1)-free posets, arXiv preprint arXiv:1212.5356 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Feb 01 2013
J. M. Troyka, Split graphs: combinatorial species and asymptotics, arXiv:1803.07248 [math.CO], 2018-2019.
J. M. Troyka, Split graphs: combinatorial species and asymptotics, Electron. J. Combin., 26 (2019), #P2.42.
E. M. Wright, The k-connectedness of bipartite graphs, J. Lond. Math. Soc. (2), 25 (1982), 7-12.

Row sums of A028657.

Cf. A048194, A318870.

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):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 01 2014

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}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)

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

More terms from Vladeta Jovovic, Jun 17 2000

A007776 Number of connected posets with n elements of height 1.

Original entry on oeis.org

1, 2, 4, 10, 27, 88, 328, 1460, 7799, 51196, 422521, 4483460, 62330116, 1150504224, 28434624153, 945480850638, 42417674401330, 2572198227615998, 211135833162079184, 23487811567341121158, 3545543330739039981738, 727053904070651775719646

Offset: 2

Georg Wambach (gw(AT)informatik.Uni-Koeln.de)

nonn

Inverse Euler transform of A048194 and A049312. - Detlef Pauly (dettodet(AT)yahoo.de) and Vladeta Jovovic, Jul 25 2003
Essentially the same as A318870. - Georg Fischer, Oct 02 2018
Number of connected digraphs on n unlabeled nodes where every node has indegree 0 or outdegree 0 and there are no isolated nodes.  - Andrew Howroyd, Oct 03 2018

Andrew Howroyd, Table of n, a(n) for n = 2..50 (terms 2..40 from Alois P. Heinz)
N. J. A. Sloane, Transforms
J. Textor, A. Idelberger, and M. Liskiewicz, Learning from Pairwise Marginal Independencies, arXiv:1508.00280 [cs.AI], 2015.
Index entries for sequences related to posets

Cf. A005142, A002031 (labeled case), A048194, A049312, A055192, A318870, column 1 of A342500.

mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
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]];
b[d_] := Sum[A[n, d - n], {n, 0, d}];
EULERi[Array[b, 30]] // Rest (* Jean-François Alcover, Sep 16 2019, after Alois P. Heinz in A049312 *)

Inverse Euler transform of A055192. - Andrew Howroyd, Oct 03 2018

More terms from Vladeta Jovovic, Jul 25 2003

Offset corrected by Andrew Howroyd, Oct 03 2018

A318869 Inverse Euler transform of A122082.

Original entry on oeis.org

1, 2, 2, 8, 37, 270, 3049, 56576, 1795917, 100752972, 10189362127, 1879720761478, 637617233746767, 400169631649617320, 467115844246535037894, 1018822456144129013291710, 4169121243929999971120036590, 32126195519194538602120203293590

Offset: 0

Andrew Howroyd, Sep 04 2018

nonn

This sequence is an intermediate step in the computation of A005142 and A123549.

The combinatoric interpretation is that of connected bicolored graphs on 2n nodes which are invariant when the two color classes are interchanged plus pairs of identical connected bicolored graphs on n nodes each which are not invariant when the two color classes are interchanged. The former is A123549(n) and the later is A005142(n) for odd n and A005142(n) - A123549(n/2) for even n.

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A005142, A122082, A123549, A318870.

mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m=1, s=0, k=0, t}, For[i=1, i <= Length[v], i++, t = v[[i]]; k = If[i>1 && t == v[[i-1]], k+1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i-1}] + Total @ Quotient[v+1, 2]
b[n_] := (s=0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Join[{1}, EULERi[Array[b, 20]]] (* Jean-François Alcover, Sep 13 2018, after Andrew Howroyd *)

A123549 Number of unlabeled connected bicolored graphs on 2n nodes which are invariant when the two color classes are interchanged.

Original entry on oeis.org

1, 1, 2, 7, 36, 265, 3039, 56532, 1795771, 100752242, 10189358360, 1879720735880, 637617233537026, 400169631647375590, 467115844246503901102, 1018822456144128438039598, 4169121243929999956903622399, 32126195519194538601647462868271

Offset: 0

N. J. A. Sloane, Nov 14 2006

nonn

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

Row sums of A123550.

Cf. A005142, A318869, A318870.

A005142 = Import["https://oeis.org/A005142/b005142.txt", "Table"][[All, 2]];
A318870 = Import["https://oeis.org/A318870/b318870.txt", "Table"][[All, 2]];
a[n_] := 2*A005142[[2*n + 1]] - A318870[[2*n + 1]];
a /@ Range[0, 17] (* Jean-François Alcover, Sep 02 2019 *)

a(n) = 2*A005142(2*n) - A318870(2*n). - Andrew Howroyd, Sep 04 2018

a(0)=1 prepended and terms a(8) and beyond from Andrew Howroyd, Sep 04 2018

cp's OEIS Frontend

A005142 Number of connected bipartite graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A007776 Number of connected posets with n elements of height 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A318869 Inverse Euler transform of A122082.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A123549 Number of unlabeled connected bicolored graphs on 2n nodes which are invariant when the two color classes are interchanged.

Views

Author

Keywords

References

Crossrefs

Programs

Mathematica

Formula

Extensions