A137918 -id:A137918 - cp's OEIS frontend

A138386 The initial values of the m-th row of table T of A137918 as m tends to infinity.

1, 2, 8, 27, 94, 315, 1067, 3545, 11767, 38747, 127061, 414551, 1347442, 4362616, 14078612, 45290929, 145291501, 464864831, 1483759703, 4725204487, 15016441266, 47627848083, 150784504858, 476543143817, 1503631824859

Offset: 0

Washington Bomfim, Mar 18 2008

nonn

It is clear that the first term of the m-th row of table T, a(0) = T(m, 3m) = T(1, 3) = 1.
Let us call an x-partition of n a partition of n that has exactly x parts >= 3.
Below we show that for j >= 1, a(j) = T(m, 3m + j) = T(j, 4j).
An m-partition of n = 3m + j has at least m-j parts 3. Suppose that p is an m-partition of n with m-j-1 parts 3. The sum of the parts of p is at least n+1 since 3(m-j-1) + 4(m - (m-j-1)) = 3(m-j-1) + 4m -4(m-j-1) = 4m - (m-j-1) = 4m-m+j+1 = (3m + j) + 1.
Because any m-partition of n = 3m + j has at least m-j parts 3, we obtain all the m-partitions of 3m + j if we append m-j parts 3 to each one of the j-partitions of 4j. Note that n - 3(m-j) = 4j and m - (m-j) = j.
To complete we note that C(f(3) + K_3 - 1, K_3) = C(K_3, K_3) = 1 and the values taken by the product pi{3 <= i <= n}C(f(i) + K_i - 1, K_i) do not change when we add m-j to K_3. In fact pi{3 <= i <= n}C(f(i) + K_i - 1, K_i) = pi{4 <= i <= n}C(f(i) + K_i - 1, K_i).
Using results found in the Knuth reference on pp. 9, ..., it is not difficult to show that the number of j-partitions of 4j is equal to p(j), (where p(n) is the usual partition function).
The largest part that appears in those partitions is j+3, because j+4+3(j-1) = 4j+1. So the first 27 values of this sequence are showed. Note that f(k) is known for k <= 29 and we work with 1 <= j <= 26.
With small values of 3m+j, the identity T(m, 3m+j) = T(j, 4j) comes closer to permit us to enumerate all the graphs with M components and N vertices, i.e., N >= 3, M >= 1. For example we determine T(M, 100) for M >= 25, T(M, 50) for M >= 8, T(M, 38) for M >= 4, T(M, 35) for M >= 3 and T(M, 32) for M >= 2. All graphs are determined if N <= 29.
It can be shown that the formula computes T(i, 3i+j), i,j >= 1, for the nine values of i: floor((3i+j)/3) - 8 <= i <= floor((3i+j)/3).

			Choosing j = 5 we use p(5) or 7 partitions. The largest part appearing in those partitions is 8, so we need the first 6 values of A001429, given by
...i..|3.4..5...6...7...8
------+------------------
f(i)..|1.2..5..13..33..89
Using the program GAP, the partitions produced by the command "RestrictedPartitions(20, [3..8], 5);" are:
[ [ 4, 4, 4, 4, 4 ], [ 5, 4, 4, 4, 3 ], [ 5, 5, 4, 3, 3 ], [ 6, 4, 4, 3, 3 ], [ 6, 5, 3, 3, 3 ], [ 7, 4, 3, 3, 3 ], [ 8, 3, 3, 3, 3 ] ]
Eliminating parts 3 from those partitions, below we give them in the form 4K_4 +...+ nK_n followed by the corresponding number of graphs:
4*5 -> C(2+5-1, 5) = 6
5 + 4*3 -> 5C(2+3-1, 3) = 20
5*2 + 4 -> 2C(5+2-1, 2) = 30
6 + 4*2 -> 13C(2+2-1, 2) = 39
6 + 5 -> 13 * 5 = 65
7 + 4 -> 33 * 2 = 66
8 -> 89
So a(5) = 6 + 20 + 30 + 39 + 65 + 66 + 89 = 315.
T(333332, 10^6+1) = a(5) = 315. Note that j = 5 and m = 333332 gives 3m+j = 10^6+1.

D. E. Knuth, The Art of Computer Programming, Vol. 4, Pre-Fascicle 3b, see p. 9.

Cf. A137918, A001429.

a(0) = 1; for j >= 1, a(j) = Sum over the partitions 3K_3 + ... + nK_n of n = 4j with exactly j parts of pi{4 <= i <= n} C(f(i) + K_i - 1, K_i), where f(i) is A001429(i).

Euler transform of 2, 5, 13, 33, ... (A001429). - Vladeta Jovovic, Sep 17 2008

A001429 Number of n-node connected unicyclic graphs.

Original entry on oeis.org

1, 2, 5, 13, 33, 89, 240, 657, 1806, 5026, 13999, 39260, 110381, 311465, 880840, 2497405, 7093751, 20187313, 57537552, 164235501, 469406091, 1343268050, 3848223585, 11035981711, 31679671920, 91021354454, 261741776369, 753265624291, 2169441973139, 6252511838796

Offset: 3

N. J. A. Sloane

Also unlabeled connected simple graphs with n vertices and n edges. The labeled version is A057500. - Gus Wiseman, Feb 12 2024

			From _Gus Wiseman_, Feb 12 2024: (Start)
Representatives of the a(3) = 1 through a(6) = 13 simple graphs:
  {12,13,23}  {12,13,14,23}  {12,13,14,15,23}  {12,13,14,15,16,23}
              {12,13,24,34}  {12,13,14,23,25}  {12,13,14,15,23,26}
                             {12,13,14,23,45}  {12,13,14,15,23,46}
                             {12,13,14,25,35}  {12,13,14,15,26,36}
                             {12,13,24,35,45}  {12,13,14,23,25,36}
                                               {12,13,14,23,25,46}
                                               {12,13,14,23,45,46}
                                               {12,13,14,23,45,56}
                                               {12,13,14,25,26,35}
                                               {12,13,14,25,35,46}
                                               {12,13,14,25,35,56}
                                               {12,13,14,25,36,56}
                                               {12,13,24,35,46,56}
(End)

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 3..500
Washington G. Bomfim, A picture of the twenty one unicycles with 3,4,5 and 6 vertices
Audace A. V. Dossou-Olory, Graphs and unicyclic graphs with extremal connected subgraphs, arXiv:1812.02422 [math.CO], 2018.
R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy) Includes illustrations for n <= 6.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
S. Karim, J. Sawada, Z. Alamgirz and S. M. Husnine, Generating bracelets with fixed content, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 103-112.
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Marko Riedel et al., Non-isomorphic, connected, unicyclic graphs, Math Stackexchange, November 2018. (Derivation of algorithm and Maple implementation using PET.)
Marko Riedel, Maple implementation using PET.
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points, Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967. doi: 10.2172/4180737.
Eric Weisstein's World of Mathematics, Unicyclic Graph

For at most one cycle we have A005703, labeled A129271, complement A140637.
Next-to-main diagonal of A054924. Cf. A000055.
The labeled version is A057500, connected case of A137916.
This is the connected case of A137917 and A236570.
Row k = 1 of A137918.
The version with loops is A368983.
A001349 counts unlabeled connected graphs.
A001434 and A006649 count unlabeled graphs with # vertices = # edges.
A006129 counts covering graphs, unlabeled A002494.
Cf. A014068, A054548, A116508, A133686, A140638, A369143, A369201.

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];Apply[Plus,Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,3,nn}]]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
(* Second program: *)
TreeGf[nn_] := Module[{A}, A = Table[1, {nn}]; For[n = 1, n <= nn 1, n++, A[[n + 1]] = 1/n * Sum[Sum[ d*A[[d]], {d, Divisors[k]}]*A[[n - k + 1]], {k, 1, n}]]; x A.x^Range[0, nn-1]];
seq[n_] := Module[{t, g}, If[n < 3, {}, t = TreeGf[n - 2]; g[e_] := Normal[t + O[x]^(Quotient[n, e]+1)] /. x -> x^e  + O[x]^(n+1); Sum[Sum[ EulerPhi[d]*g[d]^(k/d), {d, Divisors[k]}]/k + If[OddQ[k], g[1]* g[2]^Quotient[k, 2], (g[1]^2 + g[2])*g[2]^(k/2-1)/2], {k, 3, n}]]/2 // Drop[CoefficientList[#, x], 3]&];
seq[32] (* Jean-François Alcover, Oct 05 2019, after Andrew Howroyd's PARI code *)

\\ TreeGf gives gf of A000081
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={if(n<3, [], my(t=TreeGf(n-2)); my(g(e)=subst(t + O(x*x^(n\e)),x,x^e) + O(x*x^n)); Vec(sum(k=3, n, sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/2))/2))} \\ Andrew Howroyd, May 05 2018

a(n) = A068051(n) - A027852(n) - A000081(n).

More terms from Ronald C. Read
a(27) corrected, more terms, formula from Christian G. Bower, Feb 12 2002
Edited by Charles R Greathouse IV, Oct 05 2009
Terms a(30) and beyond from Andrew Howroyd, May 05 2018

A137917 a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.

Original entry on oeis.org

1, 0, 0, 1, 2, 5, 14, 35, 97, 264, 733, 2034, 5728, 16101, 45595, 129327, 368093, 1049520, 2999415, 8584857, 24612114, 70652441, 203075740, 584339171, 1683151508, 4852736072, 14003298194, 40441136815, 116880901512, 338040071375, 978314772989, 2833067885748, 8208952443400

Offset: 0

Washington Bomfim, Feb 24 2008

nonn

a(n) is the number of simple unlabeled graphs on n nodes whose components have exactly one cycle. - Geoffrey Critzer, Oct 12 2012

Also the number of unlabeled simple graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. - Gus Wiseman, Jan 25 2024

			From _Gus Wiseman_, Jan 25 2024: (Start)
Representatives of the a(0) = 1 through a(5) = 5 simple graphs:
  {}  .  .  {12,13,23}  {12,13,14,23}  {12,13,14,15,23}
                        {12,13,24,34}  {12,13,14,23,25}
                                       {12,13,14,23,45}
                                       {12,13,14,25,35}
                                       {12,13,24,35,45}
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..500
F. Ruskey, Combinatorial Generation, p. 79, Eq.(4.27), 2003
Eric Weisstein's World of Mathematics, Pseudoforest.
Wikipedia, Pseudoforest.

Cf. A008483, A137918.
The connected case is A001429.
Without the choice condition we have A001434, covering A006649.
For any number of edges we have A134964, complement A140637.
The labeled version is A137916.
The version with loops is A369145, complement A368835.
The complement is counted by A369201, labeled A369143, covering A369144.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable simple graphs, unlabeled A005703.
Cf. A000088, A000612, A007716, A014068, A053530, A116508, A133686, A140638, A368601, A369141, A369146.

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];c=Drop[Apply[Plus,Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,3,nn}]],1];CoefficientList[Series[Product[1/(1-x^i)^c[[i]],{i,1,nn-1}],{x,0,nn}],x]   (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])],{p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n],{2}],{n}],Select[Tuples[#],UnsameQ@@#&]!={}&]]],{n,0,5}] (* Gus Wiseman, Jan 25 2024 *)

a(n) = Sum_{1*j_1 + 2*j_2 + ... = n} (Product_{i=3..n} binomial(A001429(i) + j_i -1, j_i)). [F. Ruskey p. 79, (4.27) with n replaced by n+1, and a_i replaced by A001429(i)].

Euler transform of A001429. - Geoffrey Critzer, Oct 12 2012

Edited by Washington Bomfim, Jun 27 2012
Terms a(30) and beyond from Andrew Howroyd, May 05 2018
Offset changed to 0 by Gus Wiseman, Jan 27 2024

A263340 Triangle read by rows: T(n,k) is the number of graphs with n vertices containing k triangles.

Original entry on oeis.org

1, 1, 2, 3, 1, 7, 2, 1, 0, 1, 14, 7, 5, 2, 3, 1, 0, 1, 0, 0, 1, 38, 23, 28, 14, 18, 9, 7, 5, 4, 1, 4, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 107, 102, 141, 117, 123, 92, 80, 63, 49, 35, 35, 23, 15, 17, 10, 4, 9, 5, 2, 3, 3, 2, 2, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1

Offset: 0

Christian Stump, Oct 15 2015

Row sums give A000088.
First column is A006785.
Row lengths are 1 + binomial(n,3). - Geoffrey Critzer, Apr 13 2017

			Triangle begins:
  1;
  1;
  2;
  3,1;
  7,2,1,0,1;
  14,7,5,2,3,1,0,1,0,0,1;
  38,23,28,14,18,9,7,5,4,1,4,1,1,1,0,0,1,0,0,0,1;
  ...

Pontus von Brömssen, Rows n = 0..10, flattened
FindStat - Combinatorial Statistic Finder, The number of triangles of a graph.
Gus Wiseman, The graphs counted under row n = 5.

Row sums are A000088, labeled A006125.
Column k = 0 is A006785 (lab A213434), covering A372169 (lab A372168).
Counting edges gives A008406 (lab A084546), covering A370167 (lab A054548).
Row lengths are A050407.
The labeled version is A372170, covering A372167.
The covering case is A372173, sums A002494, labeled A006129.
Column k = 1 is A372194 (lab A372172), covering A372174 (lab A372171).
A001858 counts acyclic graphs, unlabeled A005195.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A053530, A137917, A137918, A140637, A144958, A322700, A370169.

Table[Table[Count[Table[Tr[MatrixPower[AdjacencyMatrix[GraphData[{n, i}]], 3]]/6, {i, 1, NumberOfGraphs[n]}], k], {k, 0, Binomial[n, 3]}], {n, 1, 7}] (* Geoffrey Critzer, Apr 13 2017 *)

Row 7 from Geoffrey Critzer, Apr 13 2017

T(0,0)=1 prepended by Alois P. Heinz, Apr 13 2017

A372191 Number of unlabeled simple graphs covering n vertices with a unique undirected cycle of length > 2.

Original entry on oeis.org

0, 0, 0, 1, 2, 6, 16, 43, 117, 319, 875, 2409, 6692, 18614, 52099, 146186, 411720, 1162295, 3289994, 9330913, 26517036, 75481622, 215201178, 614398459, 1756392061, 5026955216, 14403488345, 41311616835, 118601561506, 340795908579, 980078195995

Offset: 0

Gus Wiseman, Apr 27 2024

nonn

An undirected cycle in a graph is a sequence of distinct vertices, up to rotation and reversal, such that there are edges between all consecutive elements, including the last and the first.

Andrew Howroyd, Table of n, a(n) for n = 0..500
Gus Wiseman, The a(3) = 1 through a(6) = 16 covering graphs with a unique cycle.

For no cycles we have A144958 (non-covering A005195), labeled A105784 (non-covering A001858).
Counting triangles instead of cycles gives A372174 (non-covering A372194), labeled A372171 (non-covering A372172).
The non-covering version is A236570, labeled A372193.
The labeled version is A372195, column k = 1 of A372175.
A002807 counts cycles in a complete graph.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A372167 counts graphs by triangles, non-covering A372170.
A372173 counts unlabeled graphs by triangles (non-covering A263340).
A372176 counts labeled graphs by directed cycles.
Cf. A000055, A137916, A137917, A137918, A140637, A370167, A370169.

First differences of A236570.

a(7) onwards from Andrew Howroyd, Jul 31 2024

A372173 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

Original entry on oeis.org

1, 0, 1, 1, 1, 4, 1, 1, 0, 1, 7, 5, 4, 2, 2, 1, 0, 1, 0, 0, 1, 24, 16, 23, 12, 15, 8, 7, 4, 4, 1, 3, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 69, 79, 113, 103, 105, 83, 73, 58, 45, 34, 31, 22, 14, 16, 10, 4, 8, 5, 2, 3, 2, 2, 2, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 23 2024

			Triangle begins:
  1
  0
  1
  1 1
  4 1 1 0 1
  7 5 4 2 2 1 0 1 0 0 1

Andrew Howroyd, Table of n, a(n) for n = 0..340 (rows 0..10)
Gus Wiseman, All unlabeled simple graphs covering 5 vertices, grouped by number of triangles.

Row sums are A002494, labeled A006129.
Row lengths are A050407.
The non-covering version is A263340, labeled A372170.
Counting edges instead of triangles gives A370167, labeled A054548.
The labeled version is A372167.
Column k = 0 is A372169, labeled A372168 (non-covering A213434).
Column k = 1 is A372174, labeled A372171.
Column k = 1 is also the covering case of A372194, labeled A372172.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A053530, A137917, A137918, A140637, A144958, A322700, A370169.

a(21) onwards from Andrew Howroyd, Dec 29 2024

A372174 Number of unlabeled simple graphs covering n vertices with a unique triangle.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 16, 79, 424, 3098, 28616

Offset: 0

Gus Wiseman, Apr 24 2024

The labeled version is A372171.

Gus Wiseman, The a(3) = 1 through a(6) = 16 covering graphs with a unique triangle.

The non-covering version is column k = 1 of A263340, labeled A372170.
Case of A370167 with a unique triangle, labeled A054548.
For no triangles we have A372169, labeled A372168 (non-covering A213434).
The labeled version is A372171, column k = 1 of A372167.
Column k = 1 of A372173, labeled A372167.
For cycles (not just triangles) we have A372191, labeled A372195.
The non-covering version is A372194, labeled A372172.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A002494 counts unlabeled covering graphs, labeled A006129.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A053530, A137917, A137918, A140637, A144958, A370169.

First differences of A372194.

A372194 Number of unlabeled graphs with n vertices and a unique triangle.

Original entry on oeis.org

0, 0, 0, 1, 2, 7, 23, 102, 526, 3624, 32240, 382095, 5986945

Offset: 0

Gus Wiseman, Apr 24 2024

The labeled version is A372172.

			Representatives of the a(3) = 1 through a(6) = 23 graphs:
    12,13,23    12,13,23       12,13,23             12,13,23
                14,23,24,34    12,34,35,45          12,34,35,45
                               14,23,24,34          14,23,24,34
                               12,25,34,35,45       12,25,34,35,45
                               14,25,34,35,45       12,36,45,46,56
                               15,25,34,35,45       13,23,45,46,56
                               12,14,25,34,35,45    14,25,34,35,45
                                                    15,25,34,35,45
                                                    12,14,25,34,35,45
                                                    12,23,36,45,46,56
                                                    13,23,36,45,46,56
                                                    13,25,36,45,46,56
                                                    13,26,36,45,46,56
                                                    14,25,36,45,46,56
                                                    15,26,36,45,46,56
                                                    16,26,36,45,46,56
                                                    12,13,25,36,45,46,56
                                                    12,13,26,36,45,46,56
                                                    13,23,25,36,45,46,56
                                                    14,23,25,36,45,46,56
                                                    16,23,25,36,45,46,56
                                                    13,14,23,25,36,45,46,56
                                                    13,15,23,25,36,45,46,56

Gus Wiseman, The a(3) = 1 through a(6) = 23 graphs with a unique triangle.

For no triangles we have A006785, covering A372169.
Column k = 1 of A263340, covering A372173.
The labeled version is A372172.
The covering case is A372174, labeled A372171.
For all cycles (not just triangles): A236570, A372193, A372191, A372195.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A002494 counts unlabeled covering graphs, labeled A006129.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A137917, A137918, A140637, A144958, A213434, A372168, A372170.

geng $n | countg -T1 # Georg Grasegger, Aug 03 2024

First differences are A372174.

a(11)-a(12) added by Georg Grasegger, Aug 03 2024

A138387 Numbers of unlabeled graphs with n vertices and 2 unicyclic components.

Original entry on oeis.org

1, 2, 8, 23, 74, 220, 674, 2011, 6038, 17980, 53547, 158907, 471225, 1394786, 4124929, 12185636, 35972082, 106111713, 312835608, 921809509, 2715058701, 7993741597, 23527694230, 69228383367, 203648980297, 598945442071

Offset: 6

Washington Bomfim, Mar 18 2008

This sequence is the second row of table T of A137918.

			a(13) = 2,011, since n is odd and the partitions are 3+10, 4+9, 5+8 and 6+7. This gives 657 + 480 + 445 + 429 graphs.
Note that f(4)= 2, f(5) = 5, f(6) = 13, f(7) = 33, f(8) = 89, f(9) = 240 and f(10) = 657.

Cf. A001429, A137918.

nmax = 31;
TreeGf[nn_] := Module[{A}, A = Table[1, {nn}]; For[n = 1, n <= nn - 1, n++, A[[n + 1]] = 1/n * Sum[Sum[ d*A[[d]], {d, Divisors[k]}]*A[[n - k + 1]], {k, 1, n}]]; x A.x^Range[0, nn - 1]];
seq[n_] := Module[{t, g}, If[n < 3, {}, t = TreeGf[n - 2]; g[e_] := Normal[t + O[x]^(Quotient[n, e] + 1)] /. x -> x^e  + O[x]^(n + 1); Sum[Sum[EulerPhi[d]*g[d]^(k/d), {d, Divisors[k]}]/k + If[OddQ[k], g[1]*g[2]^Quotient[k, 2], (g[1]^2 + g[2])*g[2]^(k/2-1)/2], {k, 3, n}]]/2 // Drop[CoefficientList[#, x], 3]&];
A001429 = seq[nmax];
f[k_] := A001429[[k - 2]];
a[n_] := If[OddQ[n], Sum[f[i] * f[n - i], {i, 3, (n - 1)/2}], Sum[f[i] * f[n - i], {i, 3, n/2 - 1 }] + (f[n/2] + 1)*f[n/2]/2];
a /@ Range[6, nmax] (* Jean-François Alcover, Oct 05 2019, using Andrew Howroyd's code for A001429 *)

For n odd, a(n) = Sum(3 <= i <= (n-1)/2){f(i) * f(n-i)}; for n even, a(n) = Sum(3 <= i <= n/2 - 1){f(i) * f(n-i)} + (f(n/2)+1)*f(n/2)/2, where f(k) is A001429(k).

A138388 Numbers of unlabeled graphs with n vertices and 3 unicyclic components.

Original entry on oeis.org

1, 2, 8, 27, 89, 289, 938, 2985, 9456, 29722, 92842, 288509, 892506, 2749940, 8443504, 25845735, 78897469, 240259510, 730040882, 2213910727, 6701939407, 20255424836, 61128717826, 184233427305, 554574518396, 1667491889239

Offset: 9

Washington Bomfim, Mar 18 2008

nonn

This sequence is the third row of table T of A137918.
Let us refer to a partition of n that has exactly x parts as an x-partition of n.
A138387(n-3) counts the graphs corresponding to the 3-partitions of n whose smallest part is 3, so we consider only the 3-partitions of n whose smallest part is 4.
To determine those partitions, we start with k = 4, 5, ..., floor(n/3), and append to each one of these values of k the 2-partitions of n-k whose smallest part is >= k.
For example, if n = 18, we have 4 <= k <= 6. For k = 4, the 3-partitions are 4+(4+10), 4+(5+9), 4+(6+8) and 4+(7+7). To k = 5 correspond 5+(5+8) and 5+(6+7). Finally we have 6+(6+6).
To determine the formula, one must consider that there are partitions having distinct parts, partitions having 2 equal parts and if n mod 3 = 0, there is a unique partition with equal parts. See example.

			a(18) = 29722, since A138387(15) = 17980; nU = 455. The partitions considered by sI are 4+(4+10) and 5+(5+8). Those partitions correspond to 3306 graphs. To sD correspond 4+(5+9), 4+(6+8) and 5+(6+7). This gives 6859 graphs. To sF correspond 4+(7+7), or 1122 graphs.
Note that f(4)= 2, f(5) = 5, f(6) = 13, f(7) = 33, f(8) = 89, f(9) = 240 and f(10) = 657.

D. E. Knuth, The Art of Computer Programming, Vol. 4, Fascicle 4b, p. 20.

Cf. A001429, A137918.

If n <= 11, a(n) = A138387(n-3).
If n > 11, a(n) = A138387(n-3) + nU + sI + sD + sF, where nU = (f(n/3) + 2) * (f(n/3) + 1) * f(n/3)/6, (n mod 3 = 0), 0, (otherwise),
sI = (1/2) * Sum_{4 <= k < n/3}(f(k) + 1) * f(k) * f(n - 2k),
sD = Sum_{4 <= k < (n-2)/3} f(k) * Sum_{k+1 <= i < (n-k)/2} f(i) * f(n-k-i),
sF = (1/2) * Sum_{4 <= k < n/3}f(k) * (f((n-k)/2) + 1) * f((n-k)/2), (even n, k), or (1/2) * Sum_{5 <= k < n/3}f(k) * (f((n-k)/2) + 1) * f((n-k)/2), (odd n, k),
where f(j) is A001429(j).

cp's OEIS Frontend

A138386 The initial values of the m-th row of table T of A137918 as m tends to infinity.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A001429 Number of n-node connected unicyclic graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A137917 a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A263340 Triangle read by rows: T(n,k) is the number of graphs with n vertices containing k triangles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A372191 Number of unlabeled simple graphs covering n vertices with a unique undirected cycle of length > 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A372173 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A372174 Number of unlabeled simple graphs covering n vertices with a unique triangle.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A372194 Number of unlabeled graphs with n vertices and a unique triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs