A004110 - OEIS

%I M1504 #85 Sep 14 2024 13:26:42

%S 1,1,1,2,5,16,78,588,8047,205914,10014882,912908876,154636289460,

%T 48597794716736,28412296651708628,31024938435794151088,

%U 63533059372622888758054,244916078509480823407040988,1783406527599529094009748567708,24605674623474428415849066062642456

%N Number of n-node unlabeled graphs without endpoints (i.e., no nodes of degree 1).

%C a(n) is also the number of unlabeled mating graphs with n nodes. A mating graph has no two vertices with identical sets of neighbors. - _Tanya Khovanova_, Oct 23 2008

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

%D F. Harary and E. Palmer, Graphical Enumeration, (1973), compare formula (8.7.11).

%D R. W. Robinson, personal communication.

%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Andrew Howroyd, <a href="/A004110/b004110.txt">Table of n, a(n) for n = 0..50</a> (terms 0..26 from R. W. Robinson)

%H David Cook II, <a href="http://arxiv.org/abs/1306.0140">Nested colourings of graphs</a>, arXiv preprint arXiv:1306.0140 [math.CO], 2013.

%H Ira M. Gessel and Ji Li, <a href="https://doi.org/10.1016/j.jcta.2010.03.009">Enumeration of point-determining graphs</a>, J. Combinatorial Theory Ser. A 118 (2011), 591-612.

%H Hemanshu Kaul and Jeffrey A. Mudrock, <a href="https://arxiv.org/abs/2409.06063">Counting List Colorings of Unlabeled Graphs</a>, arXiv:2409.06063 [math.CO], 2024. See p. 6.

%H R. J. Mathar, <a href="/A004110/a004110_1.pdf">Illustrations for n=1..5 nodes</a>.

%H Ronald C. Read, <a href="https://oeis.org/A006023/a006023.pdf">The enumeration of mating-type graphs</a>, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.

%H R. W. Robinson, <a href="/A004110/a004110_2.pdf">Graphs without endpoints - computer printout</a>.

%H N. J. A. Sloane, <a href="/A004110/a004110.pdf">Illustration of a(0)-a(5)</a>.

%t 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];

%t edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];

%t a[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]}]; a[0] = 1;

%t Table[a[n], {n, 0, 18}] (* _Jean-François Alcover_, Oct 27 2018, after _Andrew Howroyd_ *)

%o (PARI) \\ Compare A000088.

%o 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}

%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}

%o a(n) = {my(s=0); sum(k=1, n, forpart(p=k, s+=permcount(p) * 2^edges(p) * polcoef(prod(i=1, #p, 1-x^p[i]), n-k)/k!)); s} \\ _Andrew Howroyd_, Sep 09 2018

%Y Row sums of A123551.

%Y Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004108 (n-node connected unlabeled graphs without endpoints), A006024 (number of labeled mating graphs with n nodes), A129584 (bi-point-determining graphs).

%Y If isolated nodes are forbidden, see A261919.

%Y Cf. A000088.

%K nonn

%O 0,4

%A _N. J. A. Sloane_