cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 11-20 of 20 results.

A261919 Number of n-node unlabeled graphs without isolated nodes or endpoints (i.e., no nodes of degree 0 or 1).

Original entry on oeis.org

1, 0, 0, 1, 3, 11, 62, 510, 7459, 197867, 9808968, 902893994, 153723380584, 48443158427276, 28363698856991892, 30996526139142442460, 63502034434187094606966, 244852545450108200518282934, 1783161611521019613186341526720, 24603891216946828886755056314074748
Offset: 0

Views

Author

N. J. A. Sloane, Sep 15 2015

Keywords

Examples

			From _Gus Wiseman_, Aug 15 2019: (Start)
Non-isomorphic representatives of the a(0) = 1 through a(5) = 11 graphs (empty columns not shown):
  {}  {12,13,23}  {12,13,24,34}        {12,13,24,35,45}
                  {13,14,23,24,34}     {12,14,25,34,35,45}
                  {12,13,14,23,24,34}  {12,15,25,34,35,45}
                                       {13,14,23,24,35,45}
                                       {12,13,24,25,34,35,45}
                                       {13,15,24,25,34,35,45}
                                       {14,15,24,25,34,35,45}
                                       {12,13,15,24,25,34,35,45}
                                       {14,15,23,24,25,34,35,45}
                                       {13,14,15,23,24,25,34,35,45}
                                       {12,13,14,15,23,24,25,34,35,45}
(End)
		

References

  • F. Harary, Graph Theory, Wiley, 1969. See illustrations in Appendix 1.

Crossrefs

Cf. A004108 (connected version), A004110 (version allowing isolated nodes).
The labeled version is A100743.

Programs

  • Mathematica
    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, 2]];
    b[n_] := Sum[permcount[p]*2^edges[p]*Coefficient[Product[1-x^p[[i]], {i, 1, Length[p]}], x, n-k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}]; b[0] = 1;
    a[n_] := b[n] - b[n-1];
    a /@ Range[0, 19] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd in A004110 *)

Formula

First differences of A004110: a(n) = A004110(n)-A004110(n-1).
Euler transform of A004108, if we assume A004108(1) = 0. - Gus Wiseman, Aug 15 2019

Extensions

a(1)-a(11) computed by Brendan McKay, Sep 15 2015
a(12)-a(26) computed from A004110 by Max Alekseyev, Sep 16 2015
a(0) = 1 prepended by Gus Wiseman, Aug 15 2019

A327097 BII-numbers of set-systems with non-spanning edge-connectivity 2.

Original entry on oeis.org

5, 6, 17, 20, 24, 34, 36, 40, 48, 53, 54, 55, 60, 61, 62, 63, 65, 66, 68, 71, 72, 80, 86, 87, 89, 92, 93, 94, 95, 96, 101, 103, 106, 108, 109, 110, 111, 113, 114, 115, 121, 122, 123, 257, 260, 272, 308, 309, 310, 311, 316, 317, 318, 319, 320, 326, 327, 342
Offset: 1

Views

Author

Gus Wiseman, Aug 20 2019

Keywords

Comments

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.
The non-spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (along with any isolated vertices) to result in a disconnected or empty set-system.

Examples

			The sequence of all set-systems with non-spanning edge-connectivity 2 together with their BII-numbers begins:
   5: {{1},{1,2}}
   6: {{2},{1,2}}
  17: {{1},{1,3}}
  20: {{1,2},{1,3}}
  24: {{3},{1,3}}
  34: {{2},{2,3}}
  36: {{1,2},{2,3}}
  40: {{3},{2,3}}
  48: {{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  55: {{1},{2},{1,2},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  61: {{1},{1,2},{3},{1,3},{2,3}}
  62: {{2},{1,2},{3},{1,3},{2,3}}
  63: {{1},{2},{1,2},{3},{1,3},{2,3}}
  65: {{1},{1,2,3}}
  66: {{2},{1,2,3}}
  68: {{1,2},{1,2,3}}
  71: {{1},{2},{1,2},{1,2,3}}
		

Crossrefs

Positions of 2's in A326787.
BII-numbers for vertex-connectivity 2 are A327082.
BII-numbers for non-spanning edge-connectivity 1 are A327099.
BII-numbers for non-spanning edge-connectivity > 1 are A327102.
BII-numbers for spanning edge-connectivity 2 are A327108.

Programs

  • Mathematica
    bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
    csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
    edgeConn[y_]:=If[Length[csm[bpe/@y]]!=1,0,Length[y]-Max@@Length/@Select[Union[Subsets[y]],Length[csm[bpe/@#]]!=1&]];
    Select[Range[0,100],edgeConn[bpe[#]]==2&]

A092430 Number of n-node labeled connected mating graphs, cf. A006024.

Original entry on oeis.org

1, 1, 25, 438, 18388, 1409674, 206682994, 58152537184, 31715884061624, 33827568738189576, 71066571962396085656, 295645506683051376527648, 2444503529745123474354656720, 40269655263141217619453414445968
Offset: 2

Views

Author

Goran Kilibarda, Vladeta Jovovic, Mar 22 2004

Keywords

Comments

Number of n-node unlabeled connected mating graphs = number of n-node unlabeled connected graphs without endpoints, n>2; cf. A004108.
The number of graphs of this type with n>=1 nodes and 1<=k<=n components defines the triangle
0;
1,0;
1,0,0;
25,3,0,0;
438,10,0,0,0;
18388,385,15,0,0,0;
1409674,10073,105,0,0,0,0;
206682994,561267,5530,105,0,0,0,0;
58152537184,53672556,197344,1260,0,0,0,0,0;
with row sums A007833. - R. J. Mathar, Apr 29 2019

References

  • Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.

Crossrefs

Programs

  • PARI
    a(n)={n!*polcoef(log(sum(i=0, n, 2^binomial(i, 2)*log(1+x + O(x*x^n))^i/i!)/(1+x)), n)} \\ Andrew Howroyd, Sep 09 2018

Formula

From Vladeta Jovovic, Mar 28 2004: (Start)
E.g.f.: log((Sum_{n>=0} 2^binomial(n, 2)*log(1+x)^n/n!)/(1+x)).
a(n) = A079306(n) + (-1)^n*(n-1)!. (End)

A327102 BII-numbers of set-systems with non-spanning edge-connectivity >= 2.

Original entry on oeis.org

5, 6, 17, 20, 21, 24, 34, 36, 38, 40, 48, 52, 53, 54, 55, 56, 60, 61, 62, 63, 65, 66, 68, 69, 70, 71, 72, 80, 81, 84, 85, 86, 87, 88, 89, 92, 93, 94, 95, 96, 98, 100, 101, 102, 103, 104, 106, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121
Offset: 1

Views

Author

Gus Wiseman, Aug 23 2019

Keywords

Comments

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.
A set-system has non-spanning 2-edge-connectivity >= 2 if it is connected and any single edge can be removed (along with any non-covered vertices) without making the set-system disconnected or empty. Alternatively, these are connected set-systems whose bridges (edges whose removal disconnects the set-system or leaves isolated vertices) are all endpoints (edges intersecting only one other edge).

Examples

			The sequence of all set-systems with non-spanning edge-connectivity >= 2 together with their BII-numbers begins:
   5: {{1},{1,2}}
   6: {{2},{1,2}}
  17: {{1},{1,3}}
  20: {{1,2},{1,3}}
  21: {{1},{1,2},{1,3}}
  24: {{3},{1,3}}
  34: {{2},{2,3}}
  36: {{1,2},{2,3}}
  38: {{2},{1,2},{2,3}}
  40: {{3},{2,3}}
  48: {{1,3},{2,3}}
  52: {{1,2},{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  55: {{1},{2},{1,2},{1,3},{2,3}}
  56: {{3},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  61: {{1},{1,2},{3},{1,3},{2,3}}
  62: {{2},{1,2},{3},{1,3},{2,3}}
  63: {{1},{2},{1,2},{3},{1,3},{2,3}}
		

Crossrefs

Graphs with spanning edge-connectivity >= 2 are counted by A095983.
Graphs with non-spanning edge-connectivity >= 2 are counted by A322395.
Also positions of terms >=2 in A326787.
BII-numbers for non-spanning edge-connectivity 2 are A327097.
BII-numbers for non-spanning edge-connectivity 1 are A327099.
BII-numbers for spanning edge-connectivity >= 2 are A327109.

Programs

  • Mathematica
    bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
    csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
    edgeConn[y_]:=If[Length[csm[bpe/@y]]!=1,0,Length[y]-Max@@Length/@Select[Union[Subsets[y]],Length[csm[bpe/@#]]!=1&]];
    Select[Range[0,100],edgeConn[bpe[#]]>=2&]

A327072 Triangle read by rows where T(n,k) is the number of labeled simple connected graphs with n vertices and exactly k bridges.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 1, 0, 3, 0, 10, 12, 0, 16, 0, 253, 200, 150, 0, 125, 0, 11968, 7680, 3600, 2160, 0, 1296, 0, 1047613, 506856, 190365, 68600, 36015, 0, 16807, 0, 169181040, 58934848, 16353792, 4695040, 1433600, 688128, 0, 262144, 0, 51017714393, 12205506096, 2397804444, 500828832, 121706550, 33067440, 14880348, 0, 4782969, 0
Offset: 0

Views

Author

Gus Wiseman, Aug 24 2019

Keywords

Comments

A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Connected graphs with no bridges are counted by A095983 (2-edge-connected graphs).
Warning: In order to be consistent with A001187, we have treated the n = 0 and n = 1 cases in ways that are not consistent with A095983.

Examples

			Triangle begins:
    1
    1   0
    0   1   0
    1   0   3   0
   10  12   0  16   0
  253 200 150   0 125   0
		

Crossrefs

Column k = 0 is A095983, if we assume A095983(0) = A095983(1) = 1.
Column k = 1 is A327073.
Column k = n - 1 is A000272.
Row sums are A001187.
The unlabeled version is A327077.
Row sums without the first column are A327071.

Programs

  • Mathematica
    csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
    Table[If[n<=1&&k==0,1,Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]==1&&Count[Table[Length[Union@@Delete[#,i]]1,{i,Length[#]}],True]==k&]]],{n,0,4},{k,0,n}]
  • PARI
    \\ p is e.g.f. of A053549.
    T(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))), v=Vec(1+serreverse(serreverse(log(x/serreverse(x*exp(p))))/exp(x*y+O(x^n))))); vector(#v, k, max(0,k-2)!*Vecrev(v[k], k)) }
    { my(A=T(8)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 28 2020

Extensions

Terms a(21) and beyond from Andrew Howroyd, Dec 28 2020

A327362 Number of labeled connected graphs covering n vertices with at least one endpoint (vertex of degree 1).

Original entry on oeis.org

0, 0, 1, 3, 28, 475, 14646, 813813, 82060392, 15251272983, 5312295240010, 3519126783483377, 4487168285715524124, 11116496280631563128723, 53887232400918561791887118, 513757147287101157620965656285, 9668878162669182924093580075565776
Offset: 0

Views

Author

Gus Wiseman, Sep 04 2019

Keywords

Comments

A graph is covering if the vertex set is the union of the edge set, so there are no isolated vertices.

Crossrefs

The non-connected version is A327227.
The non-covering version is A327364.
Graphs with endpoints are A245797.
Connected covering graphs are A001187.
Connected graphs with bridges are A327071.

Programs

  • Mathematica
    csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
    Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]==1&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]
  • PARI
    seq(n)={Vec(serlaplace(-x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k! + O(x*x^n))) - log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Formula

Inverse binomial transform of A327364.
a(n) = A001187(n) - A059166(n). - Andrew Howroyd, Sep 11 2019

Extensions

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

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

Views

Author

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

Keywords

Comments

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

Examples

			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
		

Crossrefs

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

Extensions

More terms from Andy Hardt, Oct 31 2012

A101388 Number of n-vertex unlabeled digraphs without endpoints.

Original entry on oeis.org

1, 1, 1, 8, 137, 7704, 1413982, 855543836, 1775124241697, 12985137979651848, 340909258684048264585, 32512676857544231506934756, 11365672344040389664750137465767, 14668676509227095069116619104786898732, 70315084528883620836175544247562749711989951
Offset: 0

Views

Author

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 14 2005

Keywords

Crossrefs

Cf. A100548 (labeled case), A004110, A004108, A059166, A059167, A101389.

Programs

  • PARI
    permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
    edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
    seq(n)=Vec(sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, my(d=p[i]); (1-x^d)^3 + O(x*x^(n-k))) ); x^k*s/k!)/(1-x^2)) \\ Andrew Howroyd, Jan 22 2021

Extensions

a(0)=1 prepended and terms a(7) and beyond from Andrew Howroyd, Jan 22 2021

A101389 Number of n-vertex unlabeled oriented graphs without endpoints.

Original entry on oeis.org

1, 1, 1, 3, 21, 369, 16929, 1913682, 546626268, 406959998851, 808598348346150, 4358157210587930509, 64443771774627635711718, 2636248889492487709302815665, 300297332862557660078111708007894, 95764277032243987785712142452776403618, 85885545190811866954428990373255822969983915
Offset: 0

Views

Author

Goran Kilibarda, Vladeta Jovovic, Jan 14 2005

Keywords

Examples

			a(3) = 3 because there are 2 distinct orientations of the triangle K_3 plus the empty graph on 3 vertices.
		

Crossrefs

Programs

  • PARI
    \\ See links in A339645 for combinatorial species functions.
    oedges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
    ographsCycleIndex(n)={my(s=0); forpart(p=n, s+=permcount(p) * 3^oedges(p) * sMonomial(p)); s/n!}
    ographs(n)={sum(k=0, n, ographsCycleIndex(k)*x^k) + O(x*x^n)}
    trees(n,k)={sRevert(x*sv(1)/sExp(k*x*sv(1) + O(x^n)))}
    cycleIndexSeries(n)={my(g=ographs(n), tr=trees(n,2), tu=tr-tr^2); sSolve( g/sExp(tu), tr )*symGroupSeries(n)}
    NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 27 2020
    
  • PARI
    \\ faster stand-alone version
    permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
    edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
    seq(n)={Vec(sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 3^edges(p) * prod(i=1, #p, my(d=p[i]); (1-x^d)^2 + O(x*x^(n-k))) ); x^k*s/k!)/(1-x^2))} \\ Andrew Howroyd, Jan 22 2021

Extensions

a(0)=1 prepended and terms a(9) and beyond from Andrew Howroyd, Dec 27 2020

A257947 Number of connected graphs with minimum degree at least 3 and with n vertices.

Original entry on oeis.org

1, 26, 1858, 236926, 53470032, 21496173692, 15580846842786, 20666722709050752, 50987383226899017116, 237747620610010161018672, 2125708489963555363039732518, 36886187432874074894930307867796, 1253964425811022692146824416678500176
Offset: 4

Views

Author

Vaclav Kotesovec, May 14 2015

Keywords

Comments

Generating function is K(x,1) in the reference, see page 405.

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p.404-405.

Crossrefs

Programs

  • Mathematica
    Table[n!*SeriesCoefficient[Log[Sum[2^(k*(k-1)/2)*x^k*Exp[k*x*(x-1-k)/(2*(1+x))]/k!, {k, 0, n}]] - x*(2+x+x^2)/(4*(1+x)) - Log[1+x]/2, {x, 0, n}], {n, 4, 15}]

Formula

a(n) ~ 2^(n*(n-1)/2).
Previous Showing 11-20 of 20 results.