A007776 -id:A007776 - cp's OEIS frontend

A002031 Number of labeled connected digraphs on n nodes where every node has indegree 0 or outdegree 0 and no isolated nodes.

2, 6, 38, 390, 6062, 134526, 4172198, 178449270, 10508108222, 853219059726, 95965963939958, 15015789392011590, 3282145108526132942, 1005193051984479922206, 432437051675617901246918, 261774334771663762228012950, 223306437526333657726283273822

Offset: 2

N. J. A. Sloane

Also number of labeled connected graphs with 2-colored nodes with no isolated nodes where black nodes are only connected to white nodes and vice versa.

In- or outdegree zero implies loops are not admitted. Multi-arcs are not admitted. - R. J. Mathar, Nov 18 2023

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 2..100
R. C. Read, E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.
N. J. A. Sloane, Transforms

Cf. A001831, A001832, A002032, A047863, A052332, A007776 (unlabeled case). Essentially the same as A002027.

logtr:= proc(p) local b; b:=proc(n) option remember; local k; if n=0 then 1 else p(n)- add(k *binomial(n,k) *p(n-k) *b(k), k=1..n-1)/n fi end end: digr:= n-> add(binomial(n,k) *(2^k-2)^(n-k), k=0..n): a:= logtr(digr): seq(a(n), n=2..25);  # Alois P. Heinz, Sep 14 2008

terms = 17; s = Log[Sum[Exp[(2^n - 2)*x]*(x^n/n!), {n, 0, terms+2}]] + O[x]^(terms+2); Drop[CoefficientList[s, x]*Range[0, terms+1]!, 2] (* Jean-François Alcover, Nov 08 2011, after Vladeta Jovovic, updated Jan 12 2018 *)

Logarithmic transform of A052332.
E.g.f.: log(Sum(exp((2^n-2)*x)*x^n/n!, n=0..infinity)). - Vladeta Jovovic, May 28 2004
a(n) = f(n,2) using functions defined in A002032. - Sean A. Irvine, May 29 2013

More terms, formula and new title from Christian G. Bower, Dec 15 1999

Corrected by Vladeta Jovovic, Apr 12 2003

A048194 Total number of split graphs (chordal + chordal complement) on n vertices.

Original entry on oeis.org

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, 5067146, 67997750, 1224275498, 29733449510, 976520265678, 43425320764422, 2616632636247976, 213796933371366930, 23704270652844196754, 3569464106212250952762, 730647291666881838671052

Offset: 1

Gordon F. Royle

Also number of bipartite graphs with n vertices and no isolated vertices in distinguished bipartite block, up to isomorphism; so a(n) equals first differences of A049312. - Vladeta Jovovic, Jun 17 2000
All split graphs are perfect. - Falk Hüffner, Nov 29 2015
Inverse Euler transform gives A007776 with initial 1. - Andrew Howroyd, Oct 03 2018

Alois P. Heinz, Table of n, a(n) for n = 1..40
B. A. Chat, S. Pirzada, and A. Iványi, Recognition of split-graphic sequences, Acta Universitatis Sapientiae, Informatica, 6, 2 (2014) 252-286.
Karen L. Collins and Ann N. Trenk, Finding Balance: Split Graphs and Related Classes, arXiv:1706.03092 [math.CO], June 2017.
Karen L. Collins and Ann N. Trenk, Finding Balance: Split Graphs and Related Classes, Electron. J. Combin., 25 (2018), #P1.73.
S. Hougardy, Home Page.
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Vladeta Jovovic, Binary matrices up to row and column permutations.
Gordon F. Royle, Counting set covers and split graphs, J. Integer Seqs., Vol. 3 (2000), #00.2.6.
J. M. Troyka, Split graphs: combinatorial species and asymptotics, Electron. J. Combin., 26 (2019), #P2.42.
J. M. Troyka, Split graphs: combinatorial species and asymptotics, arXiv:1803.07248 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Split Graph.
Index entries for sequences related to posets

Cf. A007776, A048192, A048193, A049312, A055080, A263859.

Detlef Pauly remarks that this is the unlabeled analog of A001831.

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}] - Sum[A[n, d - n - 1], {n, 0, d - 1}];
Table[a[n], {n, 1, 25}] (* Jean-François Alcover, May 26 2019, after Alois P. Heinz in A049312 *)

a(n) = A049312(n) - A049312(n-1) (see the Collins and Trenk link, Thms. 5 and 15). - Justin M. Troyka, Oct 29 2018
a(n) ~ A049312(n) ~ (1/n!) * Sum_{k=0..n} binomial(n,k) * 2^(k(n-k)) (see the Troyka link, Thms. 3.7 and 3.10). - Justin M. Troyka, Oct 29 2018
a(n) = A263859(n,1) + 1. - Geoffrey Critzer, Feb 05 2024

A055192 Number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block, up to isomorphism.

Original entry on oeis.org

1, 2, 5, 12, 35, 108, 393, 1666, 8543, 54190, 436740, 4565450, 62930604, 1156277748, 28509174012, 946786816168, 42448800498744, 2573207315483554, 211180300735118954, 23490473719472829824, 3545759835559406756008, 727077827560669587718290

Offset: 2

Vladeta Jovovic, Jun 18 2000

nonn

Also the number of connected split graphs on n vertices (cf. A048194). - Falk Hüffner, Dec 01 2015

Inverse Euler transform is A007776. - Andrew Howroyd, Oct 03 2018

Alois P. Heinz, Table of n, a(n) for n = 2..40

Equals second differences of A049312.
Cf. A007776, A024206, A055609, A055082, A055083, A055084.
Row sums of A056152 and also of A122083.

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]];
A049312[d_] := Sum[A[n, d - n], {n, 0, d}];
Differences[Table[A049312[n], {n, 0, 23}], 2] (* Jean-François Alcover, Sep 05 2019, after Alois P. Heinz in A049312 *)

A342500 T(n,k) is the number of connected unlabeled posets with n elements and rank k: triangle read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 4, 5, 1, 0, 10, 24, 9, 1, 0, 27, 123, 73, 14, 1, 0, 88, 734, 638, 169, 20, 1, 0, 328, 5184, 6460, 2178, 334, 27, 1, 0, 1460, 44518, 78385, 32468, 5880, 594, 35, 1, 0, 7799, 472859, 1164966, 581533, 118933, 13605, 979, 44, 1

Offset: 1

R. J. Mathar, Mar 14 2021

This is a variant of A263859 admitting only connected posets.

			The table starts in row n=1 shows ranks k>=0:
1: 1
2: 0 1
3: 0 2 1
4: 0 4 5 1
5: 0 10 24 9 1
6: 0 27 123 73 14 1
7: 0 88 734 638 169 20 1
8: 0 328 5184 6460 2178 334 27 1
9: 0 1460 44518 78385 32468 5880 594 35 1
10: 0 7799 472859 1164966 581533 118933 13605 979 44 1

Index entries for sequences related to posets
R. J. Mathar, Poset Illustrations

Cf. A000608 (row sums), A007776 (rank 1), A263859, A000096 (subdiagonal), A342501 (labeled).

T(n,0) = 0 for k>0; due to the connectivity constraint.

T(n,n-1) = 1; the poset with elements in a single chain.

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.

A361954 Triangle read by rows: T(n,k) is the number of unlabeled connected weakly graded (ranked) posets with n elements and rank k.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 4, 5, 1, 0, 10, 23, 8, 1, 0, 27, 107, 56, 11, 1, 0, 88, 557, 388, 98, 14, 1, 0, 328, 3271, 2888, 839, 149, 17, 1, 0, 1460, 22424, 23900, 7512, 1470, 209, 20, 1, 0, 7799, 183273, 226807, 73405, 14715, 2308, 278, 23, 1

Offset: 1

Andrew Howroyd, Mar 31 2023

Here weakly graded means that there exists a rank function rk from the poset to the integers such that whenever v covers w in the poset, we have rk(v) = rk(w) + 1.

			Triangle begins:
  1;
  0,   1;
  0,   2,    1;
  0,   4,    5,    1;
  0,  10,   23,    8,   1;
  0,  27,  107,   56,  11,   1;
  0,  88,  557,  388,  98,  14,  1;
  0, 328, 3271, 2888, 839, 149, 17, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..820 (rows 1..40)
Wikipedia, Graded poset.

Column k=2 is A007776.
Row sums are A361955.
Cf. A342500, A361953 (not necessarily connected).

\\ See PARI link in A361953 for program code.
{ my(A=A361954tabl(8)); for(i=1, #A, print(A[i, 1..i])) }

A268522 Connected simple marginal independence graphs (SMIGs) on n nodes having a unique directed acyclic subgraph.

Original entry on oeis.org

0, 1, 1, 2, 4, 10, 27, 90, 366

Offset: 2

N. J. A. Sloane, Feb 11 2016

J. Textor, A. Idelberger, and M. Liskiewicz, Learning from Pairwise Marginal Independencies, arXiv:1508.00280 [cs.AI], 2015.

Cf. A001349, A007776.

cp's OEIS Frontend

A002031 Number of labeled connected digraphs on n nodes where every node has indegree 0 or outdegree 0 and no isolated nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A048194 Total number of split graphs (chordal + chordal complement) on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A055192 Number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block, up to isomorphism.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A342500 T(n,k) is the number of connected unlabeled posets with n elements and rank k: triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A361954 Triangle read by rows: T(n,k) is the number of unlabeled connected weakly graded (ranked) posets with n elements and rank k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A268522 Connected simple marginal independence graphs (SMIGs) on n nodes having a unique directed acyclic subgraph.

Views

Author

Keywords

Links

Crossrefs