A318869 -id:A318869 - 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

A318870 Number of connected bipartite graphs on n unlabeled nodes with a distinguished bipartite block.

Original entry on oeis.org

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

Offset: 0

Andrew Howroyd, Sep 04 2018

nonn

Essentially the same as A007776. - Georg Fischer, Oct 02 2018

			a(1) = 2 because the single node can either be in the distinguished bipartite block or not.
a(2) = 1 because the only connected bipartite graph on two nodes is the complete graph on two nodes.
a(3) = 2 because the only connected bipartite graph on three nodes is the path graph on three nodes and there is a choice about which nodes are in the distinguished block.

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

Cf. A005142, A049312, A123549, A318869.

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}];
Join[{1}, EULERi[Array[b, 23]]] (* Jean-François Alcover, Sep 13 2018, after Alois P. Heinz in A049312 *)

Inverse Euler transform of A049312.

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

A318870 Number of connected bipartite graphs on n unlabeled nodes with a distinguished bipartite block.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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