A123549 -id:A123549 - cp's OEIS frontend

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

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.

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 *)

A363846 Number of connected bipartite graphs on 2n nodes with a marked bipartite set of size n.

Original entry on oeis.org

1, 1, 2, 13, 150, 3529, 194203, 29350896, 13668966399, 20662731749804, 103588456044907944, 1744955436868541083098, 99859125842603176324368784, 19611138475504485904873456937288, 13340730475029359536419515017040194246, 31706419735128559894860278029259121951682970, 265351742295121848168241791689670791068746978140331

Offset: 0

Max Alekseyev, Jun 24 2023

nonn

Also, number of n X n binary matrices up to permutations of rows and columns, representing the reduced adjacency matrices of connected bipartite graphs (cf. A002724).

Max Alekseyev, Table of n, a(n) for n = 0..50

Diagonal of the rectangular array described in A363845.

Cf. A002724, A028657, A123549.

a(n) = A363845(2n, n).

cp's OEIS Frontend

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

A318869 Inverse Euler transform of A122082.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A363846 Number of connected bipartite graphs on 2n nodes with a marked bipartite set of size n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula