A047864 -id:A047864 - cp's OEIS frontend

A047863 Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.

1, 2, 6, 26, 162, 1442, 18306, 330626, 8488962, 309465602, 16011372546, 1174870185986, 122233833963522, 18023122242478082, 3765668654914699266, 1114515608405262434306, 467221312005126294077442, 277362415313453291571118082, 233150477220213193598856331266

Offset: 0

N. J. A. Sloane

Row sums of A111636. - Peter Bala, Sep 30 2012
Column 2 of Table 2 in Read. - Peter Bala, Apr 11 2013
It appears that 5 does not divide a(n), that a(n) is even for n>0, that 3 divides a(2n) for n>0, that 7 divides a(6n+5), and that 13 divides a(12n+3). - Ralf Stephan, May 18 2013

			For n=2, {1,2 black, not connected}, {1,2 white, not connected}, {1 black, 2 white, not connected}, {1 black, 2 white, connected}, {1 white, 2 black, not connected}, {1 white, 2 black, connected}.
G.f. = 1 + 2*x + 6*x^2 + 26*x^3 + 162*x^4 + 1442*x^5 + 18306*x^6 + ...

H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 79, Eq. 3.11.2.

T. D. Noe, Table of n, a(n) for n = 0..50
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
S. R. Finch, Bipartite, k-colorable and k-colored graphs
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
A. Gainer-Dewar and I. M. Gessel, Enumeration of bipartite graphs and bipartite blocks, arXiv:1304.0139 [math.CO], 2013.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Acyclic orientation of graphs Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Martin Svatoš, Peter Jung, Jan Tóth, Yuyi Wang, and Ondřej Kuželka, On Discovering Interesting Combinatorial Integer Sequences, arXiv:2302.04606 [cs.LO], 2023, p. 17.
Eric Weisstein's World of Mathematics, k-Colorable Graph
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 88, Eq. 3.11.2.

Column k=2 of A322280.
Cf. A135079 (variant).
Cf. A000683, A001831, A002031, A033995, A047864, A052332, A111636, A191371, A223887.

A047863:= func< n | (&+[Binomial(n,k)*2^(k*(n-k)): k in [0..n]]) >;
[A047863(n): n in [0..40]]; // G. C. Greubel, Nov 03 2024

Table[Sum[Binomial[n,k]2^(k(n-k)),{k,0,n}],{n,0,20}] (* Harvey P. Dale, May 09 2012 *)
nmax = 20; CoefficientList[Series[Sum[E^(2^k*x)*x^k/k!, {k, 0, nmax}], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 05 2019 *)

{a(n)=n!*polcoeff(sum(k=0,n,exp(2^k*x +x*O(x^n))*x^k/k!),n)} \\ Paul D. Hanna, Nov 27 2007

{a(n)=polcoeff(sum(k=0, n, x^k/(1-2^k*x +x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Mar 08 2008

N=66; x='x+O('x^N); egf = sum(n=0, N, exp(2^n*x)*x^n/n!);
Vec(serlaplace(egf))  \\ Joerg Arndt, May 04 2013

from sympy import binomial
def a(n): return sum([binomial(n, k)*2**(k*(n - k)) for k in range(n + 1)]) # Indranil Ghosh, Jun 03 2017

def A047863(n): return sum(binomial(n,k)*2^(k*(n-k)) for k in range(n+1))
[A047863(n) for n in range(41)] # G. C. Greubel, Nov 03 2024

a(n) = Sum_{k=0..n} binomial(n, k)*2^(k*(n-k)).
a(n) = 4 * A000683(n) + 2. - Vladeta Jovovic, Feb 02 2000
E.g.f.: Sum_{n>=0} exp(2^n*x)*x^n/n!. - Paul D. Hanna, Nov 27 2007
O.g.f.: Sum_{n>=0} x^n/(1 - 2^n*x)^(n+1). - Paul D. Hanna, Mar 08 2008
From Peter Bala, Apr 11 2013: (Start)
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then a generating function is E(x)^2 = 1 + 2*x + 6*x^2/(2!*2) + 26*x^3/(3!*2^3) + .... In general, E(x)^k, k = 1, 2, ..., is a generating function for labeled k-colored graphs (see Stanley). For other examples see A191371 (k = 3) and A223887 (k = 4).
If A(x) = 1 + 2*x + 6*x^2/2! + 26*x^3/3! + ... denotes the e.g.f. for this sequence then sqrt(A(x)) = 1 + x + 2*x^2/2! + 7*x^3/3! + ... is the e.g.f. for A047864, which counts labeled 2-colorable graphs. (End)
a(n) ~ c * 2^(n^2/4+n+1/2)/sqrt(Pi*n), where c = Sum_{k = -infinity..infinity} 2^(-k^2) = EllipticTheta[3, 0, 1/2] = 2.128936827211877... if n is even and c = Sum_{k = -infinity..infinity} 2^(-(k+1/2)^2) = EllipticTheta[2, 0, 1/2] = 2.12893125051302... if n is odd. - Vaclav Kotesovec, Jun 24 2013

Better description from Christian G. Bower, Dec 15 1999

A033995 Number of bipartite graphs with n nodes.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 35, 88, 303, 1119, 5479, 32303, 251135, 2527712, 33985853, 611846940, 14864650924, 488222721992, 21712049275198, 1308300679611469, 106897965189674291, 11852113048215107822, 1784730721403509209215, 365323537513403184463273

Offset: 0

Ronald C. Read

All bipartite graphs are perfect. - Falk Hüffner, Nov 27 2015

EULER transform of A005142 [1, 1, 1, 3, 5, 17, ...] is [1, 2, 3, 7, 13, ...]. - Michael Somos, May 13 2019

			For n=1: o; n=2: o o, o-o; n=3: o o o, o o-o, o-o-o; n=4: o o o o, o o o-o, o-o o-o, o o-o-o, o-o-o-o, K_{2,2}, K_{3,1}. - _Michael Somos_, May 13 2019

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

Andrew Howroyd, Table of n, a(n) for n = 0..50
CombOS - Combinatorial Object Server, Generate graphs.
P. Erdős, D. J. Kleitman, and B. L. Rothschild, Asymptotic enumeration of k_n-free graphs. In Colloquio Internazionale sulle Teorie Combinatorie, (Rome, 1973), Tomo II, Atti dei Convegni Lincei, No. 17, pp. 19-27. Accad. Naz. Lincei, Rome.
P. Hanlon, The enumeration of bipartite graphs, Discrete Math. 28 (1979), 49-57.
S. Hougardy, Home Page.
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Sage, Common Graphs (Graph Generators).
Eric Weisstein's World of Mathematics, Bipartite Graph.
Eric Weisstein's World of Mathematics, Bicolorable Graph.
Eric Weisstein's World of Mathematics, n-Colorable Graph.

Row sums of A297877.
The labeled version is A047864.
Equals A076278(n) + 1.
Cf. A005142 (connected).

A005142 = Cases[Import["https://oeis.org/A005142/b005142.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A005142] (* Jean-François Alcover, Mar 18 2020 *)

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

A001832 Number of labeled connected bipartite graphs on n nodes.

Original entry on oeis.org

1, 1, 3, 19, 195, 3031, 67263, 2086099, 89224635, 5254054111, 426609529863, 47982981969979, 7507894696005795, 1641072554263066471, 502596525992239961103, 216218525837808950623459, 130887167385831881114006475, 111653218763166828863141636911

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, 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).

T. D. Noe, 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)
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.]
Eric Weisstein's World of Mathematics, n-Colorable Graph
Eric Weisstein's World of Mathematics, n-Chromatic Graph

Row sums of A228861.
The unlabeled version is A005142.
Cf. A002031, A047863, A047864.

mx = 17; s = Sum[ Binomial[n, k] 2^(k (n - k)) x^n/n!, {n, 0, mx}, {k, 0, n}] ; Range[0, mx]! CoefficientList[ Series[ Log[s]/2, {x, 0, mx}], x] (* Geoffrey Critzer, May 10 2011 *)

seq(n)=Vec(serlaplace(log(sum(k=0, n, exp(2^k*x + O(x*x^n))*x^k/k!))/2)) \\ Andrew Howroyd, Sep 26 2018

E.g.f.: log(A(x))/2 where A(x) is e.g.f. of A047863.

a(n) = A002031(n)/2, for n > 1. - Geoffrey Critzer, May 10 2011

More terms from Vladeta Jovovic, Apr 12 2003

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

Original entry on oeis.org

1, 2, 8, 63, 958, 27554, 1457047, 137144754, 22249524024, 6032417530135, 2663111111716110, 1876540387225350958

Offset: 1

Eric W. Weisstein, May 25 2003

Steven R. Finch, Bipartite, k-colorable and k-colored graphs
Steven R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 8c665c7
Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A047864, A084280, A084281, A084282.

a(7)-a(12) added using tinygraph by Falk Hüffner, Jun 20 2018

A084280 Number of labeled 4-colorable (i.e., chromatic number <= 4) graphs on n nodes.

Original entry on oeis.org

1, 2, 8, 64, 1023, 32596, 2062592, 257798069, 63135260853, 29939766625614, 27055039857514327

Offset: 1

Eric W. Weisstein, May 25 2003

S. R. Finch, Bipartite, k-colorable and k-colored graphs
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 8c665c7
Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A047864, A084279, A084281, A084282.

a(7)-a(11) added using tinygraph by Falk Hüffner, Jun 20 2018

A117279 Triangle read by rows: T(n,k) is number of labeled bipartite graphs with n nodes and k edges.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 3, 1, 6, 15, 16, 3, 1, 10, 45, 110, 140, 60, 10, 1, 15, 105, 435, 1125, 1701, 1200, 480, 105, 10, 1, 21, 210, 1295, 5355, 14952, 26572, 26670, 17535, 7840, 2331, 420, 35, 1, 28, 378, 3220, 19075, 81228, 246414, 507424, 666015, 620900, 431368

Offset: 0

Vladeta Jovovic, Jun 23 2007

			Triangle begins:
  1;
  1;
  1,  1;
  1,  3,  3;
  1,  6, 15,  16,   3;
  1, 10, 45, 110, 140, 60, 10;
  ...

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.5.

Andrew Howroyd, Table of n, a(n) for n = 0..1403 (rows 0..25)

Row sums give A047864,
Columns k=1..5 are A000217(n-1), A050534, A053526, A053527, A053528.
The unlabeled version is A297877.
Cf. A052296, A033995.

nn=10;f[x_,y_]:=Sum[Sum[Binomial[n,k](1+y)^(k(n-k)),{k,0,n}]x^n/n!,{n,0,nn}];Map[Select[#,#>0&]&,Range[0,nn]!CoefficientList[Series[Exp[Log[f[x,y]]/2],{x,0,nn}],{x,y}]]//Grid (* Geoffrey Critzer, Sep 05 2013 *)

T(n)={[Vecrev(p) | p<-Vec(serlaplace(sqrt(sum(k=0, n, exp(x*(1+y)^k + O(x*x^n))*x^k/k! ))))]}
{ my(A=T(6)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 10 2022

E.g.f.: sqrt(Sum_{n>=0} exp(x*(1+q)^n)*x^n/n!).

A084281 Number of labeled 5-colorable (i.e., chromatic number <= 5) graphs on n nodes.

Original entry on oeis.org

1, 2, 8, 64, 1024, 32767, 2096731, 268232643, 68572495926, 35005772219631, 35642624717803839

Offset: 1

Eric W. Weisstein, May 25 2003

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 8c665c7
Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A047864, A084279, A084280, A084282.

a(7)-a(11) added using tinygraph by Falk Hüffner, Jun 20 2018

A084282 Number of labeled 6-colorable (i.e., chromatic number <= 6) graphs on n nodes.

Original entry on oeis.org

1, 2, 8, 64, 1024, 32768, 2097151, 268434467, 68718375600, 35182553667342, 36023832051695607

Offset: 1

Eric W. Weisstein, May 25 2003

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 8c665c7
Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A047864, A084279, A084280, A084281.

a(7) from Charles R Greathouse IV, Apr 09 2012

a(8)-a(11) added using tinygraph by Falk Hüffner, Jun 20 2018

A232699 Number of labeled point-determining bipartite graphs on n vertices.

Original entry on oeis.org

1, 1, 1, 3, 15, 135, 1875, 38745, 1168545, 50017905, 3029330745, 257116925835, 30546104308335, 5065906139629335, 1172940061645387035, 379092680506164049425, 171204492289446788997825, 108139946568584292606269025, 95671942593719946611454522225

Offset: 0

Justin M. Troyka, Nov 27 2013

nonn

A graph is point-determining if no two vertices have the same set of neighbors. This kind of graph is also called a mating graph.
a(n) is always odd.
For every prime p > 2, a(n) is divisible by p for all n >= p.  It follows that, if m is odd and squarefree with largest prime factor q, then a(n) is divisible by m for all n >= q.  A similar property appears to hold for odd prime powers, in which case it would hold for all odd numbers.

			Consider n = 3. The triangle graph is point-determining, but it is not bipartite, so it is not counted in a(3). The graph 1--2--3 is bipartite, but it is not point-determining (the vertices on the two ends have the same neighborhood), so it is also not counted in a(3). The only graph counted in a(3) is the graph *--*  * (with three possible labelings). - _Justin M. Troyka_, Nov 27 2013

Andrew Howroyd, Table of n, a(n) for n = 0..100 (terms 0..20 from Justin M. Troyka)
Ira Gessel and Ji Li, Enumeration of point-determining graphs, arXiv:0705.0042 [math.CO], 2007-2009.
Andy Hardt, Pete McNeely, Tung Phan, and Justin M. Troyka, Combinatorial species and graph enumeration, arXiv:1312.0542 [math.CO], 2013.

Cf. A006024, A004110 (labeled and unlabeled point-determining graphs).
Cf. A092430, A004108 (labeled and unlabeled connected point-determining graphs).
Cf. A218090 (unlabeled point-determining bipartite graphs).
Cf. A232700, A088974 (labeled and unlabeled connected point-determining bipartite graphs).

terms = 20;
CoefficientList[Sqrt[Sum[((1+x)^2^k Log[1+x]^k)/k!, {k, 0, terms}]] + O[x]^terms, x] Range[0, terms-1]! (* Jean-François Alcover, Sep 13 2018, after Andrew Howroyd *)

seq(n)={my(A=log(1+x+O(x*x^n))); Vec(serlaplace(sqrt(sum(k=0, n, exp(2^k*A)*A^k/k!))))} \\ Andrew Howroyd, Sep 09 2018

From Andrew Howroyd, Sep 09 2018: (Start)
a(n) = Sum_{k=0..n} Stirling1(n,k)*A047864(k).
E.g.f: sqrt(Sum_{k=0..n} exp(2^k*log(1+x))*log(1+x)^k/k!). (End)

A084270 Number of labeled 2-chromatic (i.e., chromatic number = 2) graphs on n nodes.

Original entry on oeis.org

0, 1, 6, 40, 375, 5176, 103236, 2922445, 116011230, 6433447396, 498234407451, 54007795331920, 8213123246906760, 1756336596363006841, 528975889250504033526, 224688018516023267969440, 134708289561117007261966815

Offset: 1

Eric W. Weisstein, May 24 2003

nonn

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

Cf. A084271, A084272.

a(n) = A047864(n)-1. - Vladeta Jovovic, Jul 31 2003

More terms from Vladeta Jovovic, Jul 31 2003

One further term from David Wasserman, Dec 13 2004

cp's OEIS Frontend

A047863 Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

Python

SageMath

Formula

Extensions

A033995 Number of bipartite graphs with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A001832 Number of labeled connected bipartite graphs on n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Extensions

A084280 Number of labeled 4-colorable (i.e., chromatic number <= 4) graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A117279 Triangle read by rows: T(n,k) is number of labeled bipartite graphs with n nodes and k edges.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A084281 Number of labeled 5-colorable (i.e., chromatic number <= 5) graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A084282 Number of labeled 6-colorable (i.e., chromatic number <= 6) graphs on n nodes.

Views

Author