A001832 -id:A001832 - cp's OEIS frontend

A000684 Number of colored labeled n-node graphs with 2 interchangeable colors.

1, 3, 13, 81, 721, 9153, 165313, 4244481, 154732801, 8005686273, 587435092993, 61116916981761, 9011561121239041, 1882834327457349633, 557257804202631217153, 233610656002563147038721, 138681207656726645785559041

Offset: 1

N. J. A. Sloane

a(n) = A058872(n) + 1. This sequence counts the empty graph on n nodes which is not allowed in A058872. - Geoffrey Critzer, Oct 07 2012

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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).

Vincenzo Librandi, Table of n, a(n) for n = 1..100 (first 32 terms from R. W. Robinson)
S. R. Finch, Bipartite, k-colorable and k-colored graphs (2*A000684)
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
A. Nymeyer and R. W. Robinson, Tabulation of the Numbers of Labeled Bipartite Blocks and Related Classes of Bicolored Graphs, 1982 [Annotated scanned copy of unpublished MS and letter from R.W.R.]
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976

2 * A000683(n) + 1.

Cf. A058872, A111636, A134531.

With[{nn=20},Rest[CoefficientList[Series[Sum[x^n/(1-2^n x)^n,{n,nn}],{x,0,nn}], x]]] (* Harvey P. Dale, Nov 24 2011 *)

a(n)=polcoeff(sum(k=1,n,x^k/(1-2^k*x +x*O(x^n))^k),n) \\ Paul D. Hanna, Sep 14 2009

G.f.: A(x) = Sum_{n>=1} x^n/(1 - 2^n*x)^n. - Paul D. Hanna, Sep 14 2009
G.f.: 1/(W(0)-x) where W(k) = x*(x*2^k-1)^k - (x*2^(k+1)-1)^(k+1) + x*((2*x*2^k-1)^(2*k+2))/W(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Sep 17 2012
From Peter Bala, Apr 01 2013: (Start)
a(n) = Sum_{k = 0..n-1} binomial(n-1,k)*2^(k*(n-k)).
a(n) = Sum_{k = 0..n} 2^k*A111636(n,k).
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence (but with an offset of 0) is E(x)*E(2*x) = Sum_{n >= 0} a(n+1)*x^n/(n!*2^C(n,2)) = 1 + 3*x + 13*x^2/(2!*2) + 81*x^3/(3!*2^3) + 721*x^4/(4!*2^6) + .... Cf. A134531. (End)

a(15) onwards added by N. J. A. Sloane, Oct 19 2006 from the Robinson reference

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

Original entry on oeis.org

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

A005333 Number of 2-colored connected labeled graphs with n vertices of the first color and n vertices of the second color.

Original entry on oeis.org

1, 5, 205, 36317, 23679901, 56294206205, 502757743028605, 17309316971673776957, 2333508400614646874734621, 1243000239291173897659593056765, 2629967962392578020413552363565293565, 22170252073745058975210005804934596601690557

Offset: 1

N. J. A. Sloane

nonn

Conjecture: if n > 1, then a(n) is the number of labeled digraphs D (allowing self-loops) with n vertices such that D|D' and D'|D are (strongly) connected (see preliminaries of Broere et al.). - Lorenzo Sauras Altuzarra, Sep 17 2022

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 = 1..50
I. Broere, W. Imrich, R. Kalinowski, and M. Pilsniak, Asymmetric colorings of products of graphs and digraphs, Discrete Applied Mathematics 266 (p. 56-64), 2019.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)

Main diagonal of A262307 and A227322.

c[0, 1] = c[1, 0] = 1; c[0, ] = c[, 0] = 0; c[n_, m_] := c[n, m] = 2^(n*m) - Sum[If[k < n || j < m, Binomial[n - 1, k - 1]*Binomial[m, j]* 2^((n - k)*(m - j))*c[k, j], 0], {k, 1, n}, {j, 0, m}];
a[n_] := c[n, n];
Array[a, 12] (* Jean-François Alcover, Sep 03 2019 *)

a(n) = c(n,n) where c(0,1) = 1, c(0,m) = 0, c(n,m) = 2^(n*m) - Sum_{1 <= k <= n, 0 <= j <= m, k < n or j < m} C(n-1, k-1) * C(m, j) * 2^((n-k)*(m-j)) * c(k, j). - Sean A. Irvine, May 11 2016

More precise definition by Pavel Irzhavski, Jul 09 2013

More terms from Sean A. Irvine, May 11 2016

A047864 Number of labeled bipartite graphs with n nodes.

Original entry on oeis.org

1, 1, 2, 7, 41, 376, 5177, 103237, 2922446, 116011231, 6433447397, 498234407452, 54007795331921, 8213123246906761, 1756336596363006842, 528975889250504033527, 224688018516023267969441, 134708289561117007261966816

Offset: 0

N. J. A. Sloane

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 406.
H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 80, Eq. 3.11.5.

T. D. Noe, Table of n, a(n) for n = 0..50
Vladislav Bína and Jiří Přibil, Note on enumeration of labeled split graphs, Comment. Math. Univ. Carolin. 56,2 (2015) 133-137.
S. R. Finch, Bipartite, k-colorable and k-colored graphs. [Broken link]
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 32.
Eric Weisstein's World of Mathematics, n-Colorable Graph.
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 89, Eq. 3.11.5.

Row sums of A117279.
The unlabeled version is A033995.
Cf. A001832, A047863.

nn = 20; a = Sum[Sum[Binomial[n, k] 2^(k (n - k)), {k, 0, n}] x^n/n!, {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[a^(1/2), {x, 0, nn}], x]  (* Geoffrey Critzer, Jan 15 2012 *)

N=18; x='x+O('x^N); Vec(serlaplace(sqrt(sum(n=0, N, exp(2^n*x)*x^n/n!)))) \\ Gheorghe Coserea, Nov 13 2017

E.g.f.: sqrt( e.g.f. for A047863 ).

A322278 Triangle read by rows: T(n,k) is the number of k-colored connected graphs on n labeled nodes up to permutation of the colors.

Original entry on oeis.org

1, 0, 1, 0, 3, 4, 0, 19, 84, 38, 0, 195, 2470, 3140, 728, 0, 3031, 108390, 307390, 186360, 26704, 0, 67263, 7192444, 42747460, 52630060, 18926544, 1866256, 0, 2086099, 726782784, 9030799218, 20784069600, 14401134944, 3463311488, 251548592

Offset: 1

Andrew Howroyd, Dec 01 2018

Equivalently, the number of ways to choose a stable partition of a simple connected graph on n labeled nodes with k parts. See A322064 for the definition of stable partition.

			Triangle begins:
  1;
  0,     1;
  0,     3,       4;
  0,    19,      84,       38;
  0,   195,    2470,     3140,      728;
  0,  3031,  108390,   307390,   186360,    26704;
  0, 67263, 7192444, 42747460, 52630060, 18926544, 1866256;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Row sums are A322064.
Columns k=2..4 are A001832(for n > 1), A322330, A322331.
Right diagonal is A001187.
Cf. A058843, A058875, A322279, A322280.

M(n, K=n)={
  my(p=sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n));
  my(q=sum(j=0, n, x^j*2^binomial(j, 2)) + O(x*x^n));
  my(W=vector(K, k, Col(serlaplace(log(serconvol(q, p^k))))));
  Mat(vector(K, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*W[i])/k!));
}
my(T=M(7)); for(n=1, #T, print(T[n, 1..n]))

T(n,k) = (1/k!)*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*A322279(n,j).

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

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 12, 6, 0, 1, 86, 108, 24, 0, 1, 840, 2190, 840, 120, 0, 1, 11642, 55620, 31800, 6840, 720, 0, 1, 227892, 1858206, 1428000, 384720, 60480, 5040, 0, 1, 6285806, 82938828, 80529624, 24509520, 4626720, 584640, 40320

Offset: 0

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.

T(n,k) corresponds to a(k,n) = b(k,n) - b(k-1,n) in the Klarner reference. Figure 2 shows the posets of row n=4.

			Triangle begins:
  1;
  0, 1;
  0, 1,      2;
  0, 1,     12,       6;
  0, 1,     86,     108,      24;
  0, 1,    840,    2190,     840,    120;
  0, 1,  11642,   55620,   31800,   6840,   720;
  0, 1, 227892, 1858206, 1428000, 384720, 60480, 5040;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50).
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.
Wikipedia, Graded poset.

Row sums are A001833.
Column k=2 is A055531.
Partial row sums include A000007, A000012, A001831, A001832.
Main diagonal is A000142.
The unlabeled version is A361953.
Cf. A342587, A361950.

\\ Here C(n) gives columns of A361950 as vector of e.g.f.'s.
S(M)={matrix(#M, #M, i, j, sum(k=0,  i-j, 2^((j-1)*k)*M[i-j+1,k+1])/(j-1)! )}
C(n,m=n)={my(M=matrix(n+1, n+1), c=vector(m+1), A=O(x*x^n)); M[1, 1]=1; c[1]=1+A; for(h=1, m, M=S(M); c[h+1]=sum(i=0, n, vecsum(M[i+1, ])*x^i, A)); c}
T(n)={my(c=C(n), b=vector(n+1, h, c[h]/c[max(h-1,1)])); Mat(vector(n+1, h, Col(serlaplace(b[h]-if(h>1, b[h-1])), -n-1)))}
{ my(A=T(7)); for(n=1, #A, print(A[n, 1..n])) }

E.g.f. of column k >=2: C(k,x)/C(k-1,x) - C(k-1,x)/C(k-2,x) where C(k,x) is the e.g.f. of column k of A361950.

A004100 Number of labeled nonseparable bipartite graphs on n nodes.

Original entry on oeis.org

0, 1, 0, 3, 10, 355, 6986, 297619, 15077658, 1120452771, 111765799882, 15350524923547, 2875055248515242, 738416821509929731, 260316039943139322858, 126430202628042630866787, 84814075550928212558332858, 78847417416749666369637926851

Offset: 1

N. J. A. Sloane

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 406.
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 = 1..100 (terms 1..32 from R. W. Robinson)
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)
A. Nymeyer and R. W. Robinson, Tabulation of the Numbers of Labeled Bipartite Blocks and Related Classes of Bicolored Graphs, 1982 [Annotated scanned copy of unpublished MS and letter from R.W.R.]

Cf. A001832, A013922.

b[n_] := Log[Sum[Exp[2^k*x + O[x]^n]*x^k/k!, {k, 0, n}]/2];
seq[n_] := CoefficientList[-Log[2] + Log[x/InverseSeries[x*D[b[n], x]]], x]*Table[(2k)!!, {k, 0, n-2}];
seq[19] (* Jean-François Alcover, Sep 04 2019, after Andrew Howroyd *)

\\ here b(n) is A001832 as e.g.f.
b(n)={log(sum(k=0, n, exp(2^k*x + O(x*x^n))*x^k/k!))/2}
seq(n)={Vec(serlaplace(log(x/serreverse(x*deriv(b(n))))), -n)} \\ Andrew Howroyd, Sep 26 2018

a(16) onwards added by N. J. A. Sloane, Oct 19 2006 from the Robinson reference

A005334 Number of labeled nonseparable (or 2-connected) bicolored graphs with n nodes of the first color and n nodes of the second color.

Original entry on oeis.org

1, 1, 34, 7037, 6317926, 21073662977, 251973418941994, 10878710974408306717, 1727230695707098000548430, 1028983422758641650604161840065, 2342608062302306704492272616530549874, 20683716767972841770515007707311751484424893

Offset: 1

N. J. A. Sloane

nonn

The two color classes are not interchangeable and have separate labels. Nonseparable graphs are also called blocks.

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 = 1..50
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)

Main diagonal of A123301 as an array.

Cf. A005333, A005335, A005336.

Name clarified and more terms added by Andrew Howroyd, Jan 03 2021

A005335 Number of labeled nonseparable (or 2-connected) bipartite graphs with 2n nodes and n nodes in each part.

Original entry on oeis.org

1, 3, 340, 246295, 796058676, 9736032295374, 432386386904461704, 70004505120317453723895, 41988978212639552393332333300, 95055430627597798399511262461524570, 826275345303020411581696428212189429357784, 27965998400207183955394390590886658323558240477654

Offset: 1

N. J. A. Sloane

nonn

Nonseparable graphs are also called blocks.

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 = 1..50
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)

Main diagonal of A123474 as an array.

Cf. A005334.

a(n) = binomial(2*n, n) * A005334(n) / 2. - Andrew Howroyd, Jan 03 2021

Name clarified and more terms added by Andrew Howroyd, Jan 03 2021

A084283 Number of connected labeled 3-colorable (i.e., chromatic number <= 3) graphs on n nodes.

Original entry on oeis.org

1, 1, 4, 37, 667, 21886, 1262719, 125387767, 21009091072, 5809425721381, 2596693747042999, 1844571022305443422

Offset: 1

Eric W. Weisstein, May 25 2003

Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A001832, A084273, A084279, A084283, A084284, A084285, A084286.

Logarithmic transform of A084279. - Andrew Howroyd, Dec 02 2018

a(7)-a(12) from Andrew Howroyd, Dec 02 2018

cp's OEIS Frontend

A000684 Number of colored labeled n-node graphs with 2 interchangeable colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A005333 Number of 2-colored connected labeled graphs with n vertices of the first color and n vertices of the second color.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A047864 Number of labeled bipartite graphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A322278 Triangle read by rows: T(n,k) is the number of k-colored connected graphs on n labeled nodes up to permutation of the colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A004100 Number of labeled nonseparable bipartite graphs on n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs