A006024 -id:A006024 - cp's OEIS frontend

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

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)

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

Original entry on oeis.org

1, 1, 0, 12, 60, 1320, 26880, 898800, 40446000, 2568736800, 225962684640, 27627178692960, 4686229692144000, 1104514965434200320, 361988888631722352000, 165271302775469812521600, 105278651889065640047462400, 93750696652129931568573619200

Offset: 1

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.

For all n >= 3, a(n) is even. For every prime p > 2, a(n) is divisible by p for all n >= p. It follows that, if m is squarefree with largest prime factor q, then a(n) is divisible by m for all n >= q. A similar property appears to hold for prime powers, in which case it would hold for all numbers.

			Consider n = 4.  There are 12 connected point-determining bipartite graphs on 4 vertices: the graph *--*--*--*, with 12 possible labelings. - _Justin M. Troyka_, Nov 27 2013

Andrew Howroyd, Table of n, a(n) for n = 1..100 (terms 1..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. A232699, A218090 (labeled and unlabeled point-determining bipartite graphs).
Cf. A088974 (unlabeled connected point-determining bipartite graphs).

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

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

E.g.f.: x + log(1 + (G(x)-x-1)/(1+x)) where G(x) is the e.g.f. of A232699. - Andrew Howroyd, Sep 09 2018

A088974 Number of (nonisomorphic) connected bipartite graphs with minimum degree at least 2 and with n vertices.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 9, 45, 160, 1018, 6956, 67704, 830392, 13539344, 288643968, 8112651795, 300974046019, 14796399706863, 967194378235406, 84374194347669628, 9856131011755992817, 1546820212559671605395

Offset: 1

Felix Goldberg (felixg(AT)tx.technion.ac.il), Oct 30 2003

nonn

The terms were computed using the program Nauty.

As shown in the Hardt et al. reference, this sequence (for n >= 3) also enumerates the connected point-determining bipartite graphs. - Justin M. Troyka, Nov 27 2013

			Consider n = 4.  There is one connected bipartite graph with minimum degree at least 2: the square graph.  Also there is one connected point-determining bipartite graph: the graph *--*--*--*. - _Justin M. Troyka_, Nov 27 2013

Brendan McKay, Nauty
Andy Hardt, Pete McNeely, Tung Phan, and Justin M. Troyka, Combinatorial species and graph enumeration, arXiv:1312.0542 [math.CO].

Cf. A006024, A004110 (labeled and unlabeled point-determining graphs [the latter is also unlabeled graphs w/ min. degree >= 2]).
Cf. A059167 (labeled graphs w/ min. degree >= 2).
Cf. A092430, A004108 (labeled and unlabeled connected point-determining graphs [the latter is also unlabeled connected graphs w/ min. degree >= 2]).
Cf. A059166 (labeled connected graphs w/ min. degree >= 2).
Cf. A232699, A218090 (labeled and unlabeled point-determining bipartite graphs).
Cf. A232700 (labeled connected point-determining bipartite graphs).

More terms from Andy Hardt, Oct 31 2012

A218090 Number of unlabeled point-determining bipartite graphs on n vertices.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 8, 17, 63, 224, 1248, 8218, 75992, 906635, 14447433, 303100595, 8415834690, 309390830222, 15105805368214, 982300491033887

Offset: 0

Andy Hardt, Oct 20 2012

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.

			Consider n = 3. The triangle graph is point-determining, but it is not bipartite, so it is not counted in a(3). The graph *--*--* 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 *--*  *. - _Justin M. Troyka_, Nov 27 2013

Ira Gessel and Ji Li, Enumeration of point-determining graphs, arXiv:0705.0042 [math.CO]
Andy Hardt, Pete McNeely, Tung Phan, and Justin M. Troyka, Combinatorial species and graph enumeration, arXiv:1312.0542 [math.CO].

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

A327379 Number of labeled non-mating-type graphs with n vertices.

Original entry on oeis.org

0, 1, 4, 32, 436, 11292, 545784, 49826744, 8647819328, 2876819527744, 1848998498567936, 2312324942899031040, 5659406410382924819712, 27230994319259100289485568, 258465217554621196991878652416, 4851552662579126853087143276476928

Offset: 1

Gus Wiseman, Sep 05 2019

nonn

A mating-type graph has all different rows in its adjacency matrix.

Andrew Howroyd, Table of n, a(n) for n = 1..50
Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
Gus Wiseman, The a(4) = 32 non-mating-type graphs.

The unlabeled version is A141580.

Cf. A006024, A006125, A028242, A059167, A245797, A327369, A327370.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!UnsameQ@@AdjacencyMatrix[Graph[Range[n],#]]&]],{n,5}]

a(n) = {2^binomial(n,2) - sum(k=0, n, stirling(n, k, 1)*2^binomial(k,2))} \\ Andrew Howroyd, Sep 11 2019

a(n) = A006125(n) - A006024(n). - Andrew Howroyd, Sep 11 2019

Terms a(7) and beyond from Andrew Howroyd, Sep 11 2019

A160710 E.g.f.: Sum_{n>=0} 2^(n^2)*log(1+x)^n/n!.

Original entry on oeis.org

1, 2, 14, 468, 62628, 32916240, 68221619760, 561512669071200, 18431003537355665760, 2417187863502316739842560, 1267541812947815891035704645120, 2658386273978048637324643356687805440

Offset: 0

Paul D. Hanna, May 25 2009

nonn

			E.g.f.: A(x) = 1 + 2*x + 14*x^2/2! + 468*x^3/3! + 62628*x^4/4! +...
A(x) = 1 + 2*log(1+x) + 2^4*log(1+x)^2/2! + 2^9*log(1+x)^3/3! +...

G. C. Greubel, Table of n, a(n) for n = 0..57

Cf. A006025, A006024.

Table[Sum[StirlingS1[n, k]*2^(k^2), {k, 0, n}], {n, 0, 30}] (* G. C. Greubel, May 02 2018 *)

{a(n)=n!*polcoeff(sum(k=0,n,2^(k^2)*log(1+x+x*O(x^n))^k/k!),n)}

{a(n)=sum(k=0,n,2^(k^2)*n!*polcoeff(binomial(x, n), k))}

a(n) = Sum_{k=0..n} Stirling1(n, k)*2^(k^2) where Stirling1 numbers are described by A008275.

A335390 a(n) = Sum_{k=0..n} Stirling2(n,k) * 2^binomial(k,2).

Original entry on oeis.org

1, 1, 3, 15, 127, 1895, 53071, 2953575, 337064047, 79446381319, 38491200186831, 38046637826801703, 76226441027901385519, 308075833912652114006087, 2503633988838391023366024079, 40826169678526460459483237927271, 1334110729147927667553970495057395439

Offset: 0

Ilya Gutkovskiy, Jun 04 2020

nonn

Stirling transform of A006125.

Alois P. Heinz, Table of n, a(n) for n = 0..82

Cf. A006024, A006125.

a:= n-> add(Stirling2(n, k)*2^(k*(k-1)/2), k=0..n):
seq(a(n), n=0..19);  # Alois P. Heinz, Jun 05 2020

Table[Sum[StirlingS2[n, k] 2^Binomial[k, 2], {k, 0, n}], {n, 0, 16}]

a(n) = sum(k=0, n, stirling(n,k,2) * 2^binomial(k,2)); \\ Michel Marcus, Jun 05 2020

G.f.: Sum_{k>=0} 2^binomial(k,2) * x^k / Product_{j=1..k} (1 - j*x).
E.g.f.: Sum_{k>=0} 2^binomial(k,2) * (exp(x) - 1)^k / k!.
a(n) ~ 2^(n*(n-1)/2). - Vaclav Kotesovec, Jun 05 2020

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A088974 Number of (nonisomorphic) connected bipartite graphs with minimum degree at least 2 and with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A218090 Number of unlabeled point-determining bipartite graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A327379 Number of labeled non-mating-type graphs with n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A160710 E.g.f.: Sum_{n>=0} 2^(n^2)*log(1+x)^n/n!.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A335390 a(n) = Sum_{k=0..n} Stirling2(n,k) * 2^binomial(k,2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula