A006125 -id:A006125 - cp's OEIS frontend

A240936 Number of ways to partition the (vertex) set {1,2,...,n} into any number of classes and then select some unordered pairs (edges) such that a and b are in distinct classes of the partition.

1, 1, 3, 21, 337, 11985, 930241, 155643329, 55638770689, 42200814258433, 67536939792143361, 227017234854393949185, 1596674435594864988020737, 23421099407847007850007154689, 714530983411175509576743561314305, 45227689798343820164634911814524846081

Offset: 0

Geoffrey Critzer, Aug 03 2014

nonn

The elements of a class are allowed to be used multiple times to form the unordered pairs.
Equivalently, a(n) is the sum of the number of k-colored graphs on n labeled nodes taken over k colors, 1<=k<=n, where labeled graphs using k colors that differ only by a permutation of the k colors are considered to be the same.
Also the number of ways to choose a stable partition of a simple graph on n vertices. A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. - Gus Wiseman, Nov 24 2018

			a(2)=3 because the empty graph with 2 nodes is counted twice (once for each partition of 2) and the complete graph is counted once. 2+1=3.

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

Cf. A000569, A001187, A006125, A058843, A277203, A321979.

b:= proc(n, k) b(n, k):= `if`(k=1, 1, add(binomial(n, i)*
      2^(i*(n-i))*b(i, k-1)/k, i=1..n-1))
    end:
a:= n-> `if`(n=0, 1, add(b(n, k), k=1..n)):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 04 2014

nn=15;e[x_]:=Sum[x^n/(n!*2^Binomial[n,2]),{n,0,nn}];Table[n!2^Binomial[n,2],{n,0,nn}]CoefficientList[Series[Exp[(e[x]-1)],{x,0,nn}],x]

seq(n)={Vec(serconvol(sum(j=0, n, x^j*j!*2^binomial(j,2)) + O(x*x^n), exp(sum(j=1, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n))))} \\ Andrew Howroyd, Dec 01 2018

a(n) = n! * 2^C(n,2) * [x^n] exp(E(x)-1) where E(x) is Sum_{n>=0} x^n/(n!*2^C(n,2)).

a(n) = Sum_{k=1..n} A058843(n,k) for n>0.

A322395 Number of labeled simple connected graphs with n vertices whose bridges are all leaves, meaning at least one end of any bridge is an endpoint of the graph.

Original entry on oeis.org

1, 1, 1, 4, 26, 548, 22504, 1708336, 241874928, 65285161232, 34305887955616, 35573982726480064, 73308270568902715136, 301210456065963448091072, 2471487759846321319412778624, 40526856087731237340916330352896, 1328570640536613080046570271722309632

Offset: 0

Gus Wiseman, Dec 06 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
Eric Weisstein's World of Mathematics, Graph Bridge
Eric Weisstein's World of Mathematics, Endpoint

Cf. A001187, A006125, A007146, A013922, A054921, A095983, A322338, A322387, A322394.

nmax = 16;
seq[n_] := Module[{v, p, q, c}, v[_] = 0; p = x*D[#, x]& @ Log[Sum[ 2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n + 1)]; q = x*E^p; p -= q; For[k = 3, k <= n, k++, c = Coefficient[p, x, k]; v[k] = c*(k - 1)!; p -= c*q^k]; Join[{0}, Array[v, n]]];
A095983 = seq[nmax];
a[n_] := If[n<3, 1, n+Sum[Binomial[n, k]*A095983[[k+1]]*k^(n-k), {k, 1, n}]];
a /@ Range[0, nmax] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

a(n) = n + Sum_{k=1..n} binomial(n,k)*A095983(k)*k^(n-k) for n >= 3. - Andrew Howroyd, Dec 07 2018

a(6)-a(16) from Andrew Howroyd, Dec 07 2018

A327334 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and vertex-connectivity k.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 26, 28, 9, 1, 0, 296, 490, 212, 25, 1, 0, 6064, 15336, 9600, 1692, 75, 1, 0, 230896, 851368, 789792, 210140, 14724, 231, 1, 0

Offset: 0

Gus Wiseman, Sep 01 2019

The vertex-connectivity of a graph is the minimum number of vertices that must be removed (along with any incident edges) to obtain a non-connected graph or singleton. Except for complete graphs, this is the same as cut-connectivity (A327125).

			Triangle begins:
    1
    1   0
    1   1   0
    4   3   1   0
   26  28   9   1   0
  296 490 212  25   1   0

Wikipedia, k-vertex-connected graph

The unlabeled version is A259862.
Row sums are A006125.
Column k = 0 is A054592, if we assume A054592(0) = A054592(1) = 1.
Column k = 1 is A327336.
Row sums without the first column are A001187, if we assume A001187(0) = A001187(1) = 0.
Row sums without the first two columns are A013922, if we assume A013922(1) = 0.
Cut-connectivity is A327125.
Spanning edge-connectivity is A327069.
Non-spanning edge-connectivity is A327148.
Cf. A322389, A327051, A327070, A327126, A327127, A327350.

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]]]]]]]]];
vertConnSys[vts_,eds_]:=Min@@Length/@Select[Subsets[vts],Function[del,Length[del]==Length[vts]-1||csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],vertConnSys[Range[n],#]==k&]],{n,0,5},{k,0,n}]

a(21)-a(35) from Robert Price, May 14 2021

A368927 Number of labeled loop-graphs covering a subset of {1..n} such that it is possible to choose a different vertex from each edge.

Original entry on oeis.org

1, 2, 7, 39, 314, 3374, 45630, 744917, 14245978, 312182262, 7708544246, 211688132465, 6397720048692, 210975024924386, 7537162523676076, 289952739051570639, 11949100971787370300, 525142845422124145682, 24515591201199758681892, 1211486045654016217202663

Offset: 0

Gus Wiseman, Jan 15 2024

nonn

These are loop-graphs where every connected component has a number of edges less than or equal to the number of vertices. Also loop-graphs with at most one cycle (unicyclic) in each connected component.

			The a(0) = 1 through a(2) = 7 loop-graphs (loops shown as singletons):
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Without the choice condition we have A006125.
The case of a unique choice is A088957, unlabeled A087803.
The case without loops is A133686, complement A367867, covering A367869.
For exactly n edges and no loops we have A137916, unlabeled A137917.
For exactly n edges we have A333331 (maybe), complement A368596.
For edges of any positive size we have A367902, complement A367903.
The covering case is A369140, complement A369142.
The complement is counted by A369141.
The complement for n edges and no loops is A369143, covering A369144.
The unlabeled version is A369145, complement A369146.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts labeled covering loop-graphs, connected A062740.
Cf. A000169, A000272, A000666, A014068, A057500, A116508, A367863, A368601, A368924, A368984, A369200.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}]

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(exp(3*t/2 - 3*t^2/4)/sqrt(1-t) ))} \\ Andrew Howroyd, Feb 02 2024

Binomial transform of A369140.
Exponential transform of A369197 with A369197(1) = 2.
E.g.f.: exp(3*T(x)/2 - 3*T(x)^2/4)/sqrt(1-T(x)), where T(x) is the e.g.f. of A000169. - Andrew Howroyd, Feb 02 2024

a(7) onwards from Andrew Howroyd, Feb 02 2024

A369141 Number of labeled loop-graphs covering a subset of {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 25, 710, 29394, 2051522, 267690539, 68705230758, 35184059906570, 36028789310419722, 73786976083150073999, 302231454897259573627852, 2475880078570549574773324062, 40564819207303333310731978895956, 1329227995784915872613854321228773937

Offset: 0

Gus Wiseman, Jan 20 2024

nonn

Also labeled loop-graphs having at least one connected component containing more edges than vertices.

			The a(0) = 0 through a(3) = 25 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{1,2}}
                         {{1},{3},{1,3}}
                         {{2},{3},{2,3}}
                         {{1},{2},{3},{1,2}}
                         {{1},{2},{3},{1,3}}
                         {{1},{2},{3},{2,3}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,2},{2,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3}}
                         {{1},{3},{1,2},{2,3}}
                         {{1},{3},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3}}
                         {{2},{3},{1,2},{2,3}}
                         {{2},{3},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{2},{1,2},{1,3},{2,3}}
                         {{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{3},{1,2},{2,3}}
                         {{1},{2},{3},{1,3},{2,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

Without the choice condition we have A006125, unlabeled A000088.
The case of a unique choice is A088957, unlabeled A087803.
The case without loops is A367867, covering A367868.
For edges of any positive size we have A367903, complement A367902.
For exactly n edges we have A368596, complement A333331 (maybe).
The complement is counted by A368927, covering A369140.
The covering case is A369142.
For n edges and no loops we have A369143, covering A369144.
The unlabeled version is A369146 (covering A369147), complement A369145.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable graphs, covering A367869.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
Cf. A000272, A000666, A006649, A062740, A116508, A137916, A368924, A368984, A369194.

Table[Length[Select[Subsets[Subsets[Range[n], {1,2}]],Length[Select[Tuples[#],UnsameQ@@#&]]==0&]],{n,0,5}]

Binomial transform of A369142.

a(n) = A006125(n + 1) - A368927(n). - Andrew Howroyd, Feb 02 2024

a(6) onwards from Andrew Howroyd, Feb 02 2024

A084546 Triangle read by rows: T(n,k) = C( C(n,2), k) for n >= 0, 0 <= k <= C(n,2).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 3, 1, 1, 6, 15, 20, 15, 6, 1, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 1, 21, 210, 1330, 5985, 20349, 54264, 116280, 203490, 293930, 352716, 352716, 293930, 203490, 116280, 54264, 20349, 5985, 1330, 210, 21, 1

Offset: 0

N. J. A. Sloane, Jul 13 2003

T(n,k) gives number of labeled simple graphs with n nodes and k edges.

			Triangle begins:
  1;
  1;
  1, 1;
  1, 3,  3,  1;
  1, 6, 15, 20, 15, 6, 1;
  ...

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 517.

Alois P. Heinz, Rows n = 0..42, flattened
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) table 66.

Cf. A083029. A subset of the rows of Pascal's triangle A007318.
Cf. A006125 (row sums), A008406 (unlabeled graphs).
Main diagonal gives A116508.

C:= binomial:
T:= (n, k)-> C( C(n, 2), k):
seq(seq(T(n, k), k=0..C(n, 2)), n=0..10);  # Alois P. Heinz, Feb 17 2023

Table[Table[Binomial[Binomial[n,2],k],{k,0,Binomial[n,2]}],{n,1,7}]//Grid (* Geoffrey Critzer, Apr 28 2011 *)

T(0,0)=1 prepended by Alois P. Heinz, Feb 17 2023

A333331 Number of integer points in the convex hull in R^n of parking functions of length n.

Original entry on oeis.org

1, 3, 17, 144, 1623, 22804, 383415, 7501422

Offset: 1

Richard Stanley, Mar 15 2020

It is observed by Gus Wiseman in A368596 and A368730 that this sequence appears to be the complement of those sequences. If this is the case, then a(n) is the number of labeled graphs with loops allowed in which each connected component has an equal number of vertices and edges and the conjectured formula holds. Terms for n >= 9 are expected to be 167341283, 4191140394, 116425416531, ... - Andrew Howroyd, Jan 10 2024
From Gus Wiseman, Mar 22 2024: (Start)
An equivalent conjecture is that a(n) is the number of loop-graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. I call these graphs choosable. For example, the a(3) = 17 choosable loop-graphs are the following (loops shown as singletons):
  {{1},{2},{3}}  {{1},{2},{1,3}}  {{1},{1,2},{1,3}}  {{1,2},{1,3},{2,3}}
                 {{1},{2},{2,3}}  {{1},{1,2},{2,3}}
                 {{1},{3},{1,2}}  {{1},{1,3},{2,3}}
                 {{1},{3},{2,3}}  {{2},{1,2},{1,3}}
                 {{2},{3},{1,2}}  {{2},{1,2},{2,3}}
                 {{2},{3},{1,3}}  {{2},{1,3},{2,3}}
                                  {{3},{1,2},{1,3}}
                                  {{3},{1,2},{2,3}}
                                  {{3},{1,3},{2,3}}
(End)

			For n=2 the parking functions are (1,1), (1,2), (2,1). They are the only integer points in their convex hull. For n=3, in addition to the 16 parking functions, there is the additional point (2,2,2).

R. P. Stanley (Proposer), Problem 12191, Amer. Math. Monthly, 127:6 (2020), 563.

Thomas Selig, The stochastic sandpile model on complete graphs, arXiv:2209.07301 [math.PR], 2022.

All of the following relative references pertain to the conjecture:
The case of unique choice A000272.
The version without the choice condition is A014068, covering A368597.
The case of just pairs A137916.
For any number of edges of any positive size we have A367902.
The complement A368596, covering A368730.
Allowing edges of any positive size gives A368601, complement A368600.
Counting by singletons gives A368924.
For any number of edges we have A368927, complement A369141.
The connected case is A368951.
The unlabeled version is A368984, complement A368835.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
Cf. A000169, A000666, A057500, A062740, A129271, A133686, A367863, A367903, A369146, A369199.

Conjectured e.g.f.: exp(-log(1-T(x))/2 + T(x)/2 - T(x)^2/4) where T(x) = -LambertW(-x) is the e.g.f. of A000169. - Andrew Howroyd, Jan 10 2024

A368596 Number of n-element sets of singletons or pairs of distinct elements of {1..n}, or loop graphs with n edges, such that it is not possible to choose a different element from each.

Original entry on oeis.org

0, 0, 0, 3, 66, 1380, 31460, 800625, 22758918, 718821852, 25057509036, 957657379437, 39878893266795, 1799220308202603, 87502582432459584, 4566246347310609247, 254625879822078742956, 15115640124974801925030, 952050565540607423524658, 63425827673509972464868323

Offset: 0

Gus Wiseman, Jan 04 2024

nonn

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The a(3) = 3 set-systems:
  {{1},{2},{1,2}}
  {{1},{3},{1,3}}
  {{2},{3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

The version without the choice condition is A014068, covering A368597.
The complement appears to be A333331.
For covering pairs we have A367868.
Allowing edges of any positive size gives A368600, any length A367903.
The covering case is A368730.
The unlabeled version is A368835.
A000085 counts set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A100861 counts set partitions into singletons or pairs by number of pairs.
A111924 counts set partitions into singletons or pairs by length.
A322661 counts covering half-loop-graphs, connected A062740.
A369141 counts non-choosable loop-graphs, covering A369142.
A369146 counts unlabeled non-choosable loop-graphs, covering A369147.
Cf. A000272, A000666, A057500, A129271, A133686, A367769, A367863, A367867, A367869, A367901, A367907, A368097, A369199.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}], {n}],Length[Select[Tuples[#],UnsameQ@@#&]]==0&]],{n,0,5}]

Terms a(7) and beyond from Andrew Howroyd, Jan 10 2024

A028361 Number of totally isotropic spaces of index n in orthogonal geometry of dimension 2n.

Original entry on oeis.org

1, 2, 6, 30, 270, 4590, 151470, 9845550, 1270075950, 326409519150, 167448083323950, 171634285407048750, 351678650799042888750, 1440827432323678715208750, 11804699153027899713705288750, 193419995622362136809061156168750, 6338179836549184861096125026493768750

Offset: 0

N. J. A. Sloane

These numbers appear in first column of A155103. - Mats Granvik, Jan 20 2009
Equals row sums of unsigned triangle A158474. - Gary W. Adamson, Mar 20 2009
a(n) = (n+2) terms in the sequence (1, 1, 2, 4, 8, 16, ...) dot (n+2) terms in the sequence (1, 1, 2, 6, 30, 270, ...). Example: a(4) = 4590 = (1, 2, 4, 8, 16) dot (1, 1, 2, 6, 30, 270) = (1 + 1 + 4 + 24 + 240 + 4320). - Gary W. Adamson, Aug 02 2010
a(n) is the right-hand side of the mass formula used to classify Type II Self Dual Binary Linear Codes of length 2(n+1). a(n) is the number of distinct Type II Self Dual Binary Linear codes of length 2(n+1) when 2(n+1) = 0 MOD 8.  It is important to note that Type II codes are only possible when the length is a multiple of 8. In short, this sequence only applies to Type II codes when 2(n+1) = 0 MOD 8, else the right hand side of the mass formula is zero. - Nathan J. Russell, Mar 04 2016
This is almost certainly the sequence of number of Carlyle circles needed for the construction of regular polygons using straightedge and compass mentioned on page 107 of DeTemple (1991). - N. J. A. Sloane, Aug 05 2021
a(n) is also the number of Sp(oo, F2)-orbits of V^n, where V is the countable-dimensional symplectic vector space over the two-element field. - Jingjie Yang, Jul 30 2025

W. Cary Huffman and Vera Pless, Fundamentals of Error Correcting Codes, Cambridge University Press, 2003, Page 366. - Nathan J. Russell, Mar 04 2016

T. D. Noe, Table of n, a(n) for n=0..50
C. Bachoc and P. Gaborit, On extremal additive F_4 codes of length 10 to 18, J. Théorie Nombres Bordeaux, 12 (2000), 255-271.
Julien Clément and Antoine Genitrini, Binary Decision Diagrams: from Tree Compaction to Sampling, arXiv:1907.06743 [cs.DS], 2019.
John P. D'Angelo, Counting Tournament Brackets, J. Int. Seq., Vol. 25 (2022), Article 22.6.8.
Duane W. DeTemple, Carlyle circles and the Lemoine simplicity of polygon constructions, The American Mathematical Monthly 98.2 (1991): 97-108.
Davide Gaiotto and Justin Kulp, Orbifold groupoids, arXiv:2008.05960 [hep-th], 2020, page 42.

Cf. A006125, A028362, A155103, A158474, A323716 (product of 3^i+1).

[1] cat [ (&*[1+2^j: j in [0..n-1]]): n in [1..20]]; // G. C. Greubel, Jun 06 2020

seq( mul((1+2^j), j=0..n-1), n = 0..20); # G. C. Greubel, Jun 06 2020

Table[QPochhammer[-1, 2, n], {n, 0, 15}] (* Arkadiusz Wesolowski, Oct 29 2012 *)
Table[Product[2^i + 1, {i, 0, n/2 - 2}], {n, 2, 32, 2}] (* Nathan J. Russell, Mar 04 2016 *)
Table[Product[2^i + 1, {i, 0, n - 1}], {n, 0, 15}] (* Nathan J. Russell, Mar 04 2016 *)
FoldList[Times,1,2^Range[0,20]+1] (* Harvey P. Dale, Apr 11 2016 *)

PARI
```
{a(n) = prod(k=0, n-1, 2^k + 1)};
```

{a(n)=polcoeff(sum(m=0,n,2^(m*(m-1)/2)*x^m/prod(k=0,m,1-2^k*x+x*O(x^n))),n)} /* Paul D. Hanna, May 02 2012 */

for n in range(2,50,2):
  product = 1
  for i in range(0,n//2-2 + 1):
    product *= (2**i+1)
  print(product)
# Nathan J. Russell, Mar 01 2016

[product( 1+2^j for j in (0..n-1)) for n in (0..20)] # G. C. Greubel, Jun 06 2020

a(n) = Product_{i=0..n-1} ( 2^i + 1 ).
Asymptotic to C*2^(n*(n-1)/2) where C = A081845 = 4.76846205806274344829979857... = Product_{k>=0} (1 + 1/2^k). - Benoit Cloitre, Apr 09 2003
It appears that a(n) = 2^((1/2)*(n - 1)*n) * Product_{k>=0} (1 + 1/(2^k)) / Product_{k>=0} (1 + 1/(2^(n + k))). - Peter Moxey (pmoxey(AT)live.com), Mar 21 2010
G.f.: Sum_{n>=0} 2^(n*(n-1)/2) * x^n / Product_{k=0..n} (1 - 2^k*x). - Paul D. Hanna, May 02 2012
a(n) = (a(n-2)^3 + a(n-1) * a(n-3) * (a(n-1) - 2 * a(n-2))) * a(n-1) / (a(n-2)^2 * (a(n-2) - a(n-3))) if n>2. - Michael Somos, Aug 21 2012
0 = a(n)*(+a(n+1) + a(n+2)) + a(n+1)*(-2*a(n+1)) for all n>=0. - Michael Somos, Oct 10 2014
Sum_{k=0..n} 2^k/a(k) = 3-2/a(n) and Sum_{k=0..n} 4^k/a(k) = 9-(4*(1+2^n))/a(n) for n >= 0. - Werner Schulte, Dec 25 2016
G.f. A(x) satisfies: A(x) = (1 + x * A(2*x)) / (1 - x). - Ilya Gutkovskiy, Jun 06 2020
a(n) = Sum_{k=0..n} q_binomial(n, k, q=2) * 2^(k*(k-1)/2). - Jingjie Yang, Jul 30 2025

A057864 Number of simple traceable graphs on n nodes.

Original entry on oeis.org

1, 1, 2, 5, 18, 91, 734, 10030, 248427, 11482572, 1000231510

Offset: 1

Eric W. Weisstein

Number of undirected graphs on n nodes possessing a Hamiltonian path (not circuit).

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version f0eaa32.
Eric Weisstein's World of Mathematics, Traceable Graph
Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
Gus Wiseman, Non-isomorphic representatives of the a(5) = 18 unlabeled simple graphs containing a Hamiltonian path.

Main diagonal of A309524.
The labeled case is A326206.
The directed case is A326221 (with loops).
Unlabeled simple graphs not containing a Hamiltonian path are A283420.
Unlabeled simple graphs containing a Hamiltonian cycle are A003216.
Cf. A000088, A006125, A246446, A283420, A326205, A326217.

A000088(n) = a(n) + A283420(n). - Gus Wiseman, Jun 17 2019

a(8) and a(9) from Eric W. Weisstein, Jun 04 2004
a(10) from Eric W. Weisstein, May 27 2009
a(11) added using tinygraph by Falk Hüffner, Jan 19 2016

cp's OEIS Frontend

A240936 Number of ways to partition the (vertex) set {1,2,...,n} into any number of classes and then select some unordered pairs (edges) such that a and b are in distinct classes of the partition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A322395 Number of labeled simple connected graphs with n vertices whose bridges are all leaves, meaning at least one end of any bridge is an endpoint of the graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327334 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and vertex-connectivity k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A368927 Number of labeled loop-graphs covering a subset of {1..n} such that it is possible to choose a different vertex from each edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A369141 Number of labeled loop-graphs covering a subset of {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A084546 Triangle read by rows: T(n,k) = C( C(n,2), k) for n >= 0, 0 <= k <= C(n,2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A333331 Number of integer points in the convex hull in R^n of parking functions of length n.

Views

Author

Keywords

Comments

Examples

References