A342557 -id:A342557 - cp's OEIS frontend

A004108 Number of n-node unlabeled connected graphs without endpoints.

1, 1, 0, 1, 3, 11, 61, 507, 7442, 197772, 9808209, 902884343, 153723152913, 48443147912137, 28363697921914475, 30996525982586676021, 63502034385272108655525, 244852545421597419740767106, 1783161611489937453151313949442, 24603891216883233547700609793901996

Offset: 0

N. J. A. Sloane

nonn

Also number of n-node unlabeled connected mating graphs, cf. A006024 and A092430 (conjectured by Vladeta Jovovic, proved by G. Kilibarda). - Vladeta Jovovic, Oct 07 2004

F. Harary and E. Palmer, Graphical Enumeration, (1973), formula (8.7.11).
Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
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 = 0..50 (terms 1..26 from R. W. Robinson)
David Cook II, Nested colourings of graphs, arXiv preprint arXiv:1306.0140 [math.CO], 2013.
Gabe Cunningham and Igor Minevich, Graph Products of Groups, arXiv:2502.05648 [math.GR], 2025. See p. 5.
Hemanshu Kaul and Jeffrey A. Mudrock, Counting List Colorings of Unlabeled Graphs, arXiv:2409.06063 [math.CO], 2024. See p. 6.
Goran Kilibarda, Enumeration of Unlabeled Mating Graphs, Graphs and Combinatorics, Volume 23, Number 2 / April, 2007, pp. 183-199.
R. W. Robinson, Connected graphs without endpoints - computer printout.
Eric Weisstein's World of Mathematics, Connected Graph.

Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004110 (Euler Transform, n-node unlabeled graphs without endpoints).
Cf. A006024, A092430 (n-node labeled connected mating graphs).
See also A261919.
Cf. A342556, A342557.
Counts include those for distance-critical graphs, A349402.

terms = 19;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
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]}];
A004110 = Table[b[n], {n, 1, terms-1}];
Join[{1}, EULERi[A004110]] (* Jean-François Alcover, Jan 21 2019, after Andrew Howroyd *)

Inverse Euler transform of A004110. - Andrew Howroyd, Sep 09 2018

a(0)=1 prepended by Andrew Howroyd, Sep 09 2018

A083920 Number of nontriangular numbers <= n.

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 9, 10, 10, 11, 12, 13, 14, 15, 15, 16, 17, 18, 19, 20, 21, 21, 22, 23, 24, 25, 26, 27, 28, 28, 29, 30, 31, 32, 33, 34, 35, 36, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 55, 56, 57, 58, 59, 60, 61, 62

Offset: 0

Clark Kimberling, May 08 2003

nonn

An alternative description: the sequence of nonnegative integers with the triangular numbers repeated.

a(t(n)) = t(n+1), where t(n)=A000217(n)=n(n+1)/2, the n-th triangular number. For n>=1, a(n)=a(n-1) if and only if n is a triangular number; otherwise, a(n)=1+a(n-1).

			a(7)=4 counts the nontriangular numbers, 2,4,5,7, that are <=7.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982. See Table 1, column (4).

Cf. A000217, A002024, A003056, A005318, A205744.
Essentially partial sums of A023532.
Number of nonzero terms in row n+1 of A342557.

a083920 n = a083920_list !! n
a083920_list = scanl1 (+) $ map (1 -) a010054_list
-- Reinhard Zumkeller, Feb 12 2012

[n-Floor((Sqrt(8*n+1)-1)/2):n in [1..75]]; // Marius A. Burtea, Jun 19 2019

f[n_] := n - Floor[(Sqrt[8n + 1] - 1)/2]; Table[ f[n], {n, 0, 73}] (* Robert G. Wilson v, Oct 22 2005 *)
Accumulate[Table[If[OddQ[Sqrt[8n+1]],0,1],{n,0,120}]] (* Harvey P. Dale, Oct 14 2014 *)

a(n)=n-(sqrtint(8*n+1)-1)\2 \\ Charles R Greathouse IV, Sep 02 2015

from math import isqrt
def A083920(n): return n-(k:=isqrt(m:=n+1<<1))+((m>=k*(k+1)+1)^1) # Chai Wah Wu, Jun 07 2025

a(n) = n-floor((x-1)/2) = n-A003056(n), where x = sqrt(8*n+1).
A005318(n+1) = 2*A005318(n)-A205744(n), A205744(n) = A005318(a(n)), a(n) = n - A002024(n). - N. J. A. Sloane, Feb 11 2012
G.f.: 1/(1 - x)^2 - (1/(1 - x))*Product_{k>=1} (1 - x^(2*k))/(1 - x^(2*k-1)). - Ilya Gutkovskiy, May 30 2017
a(n) = n - floor(sqrt(2*n + 1) - 1/2). - Ridouane Oudra, Jun 19 2019

Added alternative definition and Guy reference. - N. J. A. Sloane, Feb 09 2012

A342556 a(n) is the number of unlabeled connected graphs without endpoints with n edges.

Original entry on oeis.org

1, 0, 0, 1, 1, 2, 5, 9, 22, 60, 164, 494, 1624, 5602, 20600, 79813, 323806, 1371025, 6034105, 27513424, 129641411, 629862824, 3149541908, 16183100922, 85328280263, 461123500894, 2551342936264, 14438734591483, 83506198920054, 493163726073210, 2971858162771887

Offset: 0

Hugo Pfoertner, May 21 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
Brendan McKay and Adolfo Piperno, Practical Graph Isomorphism, II, Journal of Symbolic Computation, 60 (2014), pp. 94-112.
Brendan McKay and Adolfo Piperno, nauty and Traces, programs for computing automorphism groups of graphs and digraphs.

Row sums of A342557.

Cf. A004108 (n vertices), A307317 (multigraph), A369290 (not necessarily connected).

Inverse Euler transform of A369290.

a(0)=1 prepended and a(25) onwards from Andrew Howroyd, Feb 01 2024

A369932 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n edges and k vertices and without endpoints or isolated vertices.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 3, 2, 0, 0, 0, 0, 3, 5, 2, 0, 0, 0, 0, 2, 11, 9, 3, 0, 0, 0, 0, 1, 15, 32, 16, 4, 0, 0, 0, 0, 1, 12, 63, 76, 25, 5, 0, 0, 0, 0, 0, 8, 89, 234, 162, 39, 6, 0, 0, 0, 0, 0, 5, 97, 515, 730, 332, 60, 9

Offset: 1

Andrew Howroyd, Feb 07 2024

			Triangle begins:
  0;
  0, 0;
  0, 0, 1;
  0, 0, 0, 1;
  0, 0, 0, 1, 1;
  0, 0, 0, 1, 3,  2;
  0, 0, 0, 0, 3,  5,  2;
  0, 0, 0, 0, 2, 11,  9,  3;
  0, 0, 0, 0, 1, 15, 32, 16,  4;
  0, 0, 0, 0, 1, 12, 63, 76, 25, 5;
  ...

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

Row sums are A369290.
Column sums are A261919.
Main diagonal is A008483.
Cf. A342557 (connected), A123551 (without endpoints).

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, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
G(n) = {my(s=O(x*x^n)); sum(k=0, n, forpart(p=k, s+=permcount(p) * edges(p, w->1+y^w+O(y*y^n)) * x^k * prod(i=1, #p, 1-(y*x)^p[i], 1+O(x^(n-k+1))) / k!)); s*(1-x)}
T(n)={my(r=Vec(substvec(G(n),[x,y],[y,x]))); vector(#r-1, i, Vecrev(Pol(r[i+1]/y),i)) }
{ my(A=T(12)); for(i=1, #A, print(A[i])) }

T(n,k) = A123551(k,n) - A123551(k-1,n).

A360030 a(n) is the minimum number of equal resistors needed in an electrical network so that n nodes can be selected in this network such that there are n*(n-1)/2 distinct resistances 0 < R < oo between the selected nodes.

Original entry on oeis.org

1, 3, 5, 8, 10, 11, 12, 14, 15, 16, 18, 19, 21

Offset: 2

Hugo Pfoertner and Rainer Rosenthal, Feb 12 2023

			a(2) = 1, [[1,2]]
.
  1           2
  O----R1R----O
  R_12 = 1
.
a(3) = 3, [[1,2]^2,[2,3]]
.
  1   .---R1R---.   2           3
  O --|         |-- O ---R3R--- O
      .---R2R---.
.
  R_12 = 1/2, R_13 = 3/2,
              R_23 = 1
.
a(4) = 5, node 5 hidden, [[1,2],[2,3]^2,[3,5],[4,5]]
.
  1           2   .---R2R---.   3          (5)          4
  O ---R1R--- O --|         |-- O ---R4R--- O ---R5R--- O
                  .---R3R---.
.
  R_12 = 1, R_13 = 3/2, R_14 = 7/2,
            R_23 = 1/2, R_24 = 5/2,
                        R_34 = 2
.
a(5) = 8, node 6 hidden,
  [[1, 2], [1, 3]^2, [2, 3], [2, 4], [3, 6], [4, 5], [4, 6]]
.
    1             2           4           5
    O-----R1R-----O----R5R----O----R8R----O
    |             |           |
    |            R4R         R7R
    .---R2R---.   |           |
    |         |---O----R6R----O
    .---R3R---.   3          (6)
.
   R_12 = 5/9, R_13 = 7/18, R_14 = 19/18, R_15 = 37/18,
               R_23 = 1/2,  R_24 = 13/18, R_25 = 31/18,
                            R_34 =  8/9,  R_35 = 17/9,
                                          R_45 =  1

IBM Research, Electric networks in graphs, Ponder This Challenge, March 2025, asked for the only network corresponding to a(10)=15 and 4 networks for a(12)=18.
Hugo Pfoertner, Illustrated examples for the terms a(6), a(7), a(8), 17 Feb 2023.
Hugo Pfoertner, Illustrated examples for the terms a(9), a(10), a(11), 3 Apr 2023.
Hugo Pfoertner, Illustration of a(12)=18, 8 Jan 2024, showing 3 planar and 5 non-planar networks, 4 of which were required to solve the bonus question of IBM's Ponder This Challenge.
Hugo Pfoertner and Klaus Nagel, Illustration of a(14)=21, 21 Aug 2025.

Cf. A219158, A342557, A342558, A348020.

a(14) from Klaus Nagel and Hugo Pfoertner, Aug 21 2025

cp's OEIS Frontend

A004108 Number of n-node unlabeled connected graphs without endpoints.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A083920 Number of nontriangular numbers <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Python

Formula

Extensions

A342556 a(n) is the number of unlabeled connected graphs without endpoints with n edges.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A369932 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n edges and k vertices and without endpoints or isolated vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A360030 a(n) is the minimum number of equal resistors needed in an electrical network so that n nodes can be selected in this network such that there are n*(n-1)/2 distinct resistances 0 < R < oo between the selected nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions