A001429 -id:A001429 - cp's OEIS frontend

A054924 Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled connected graphs with n nodes and k edges (n >= 1, 0 <= k <= n(n-1)/2).

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 2, 1, 1, 0, 0, 0, 0, 3, 5, 5, 4, 2, 1, 1, 0, 0, 0, 0, 0, 6, 13, 19, 22, 20, 14, 9, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 23, 89, 236, 486, 814, 1169, 1454, 1579, 1515, 1290, 970, 658, 400, 220, 114

Offset: 1

N. J. A. Sloane

			Triangle begins:
1;
0,1;
0,0,1,1;
0,0,0,2,2,1,1;
0,0,0,0,3,5,5,4,2,1,1;
0,0,0,0,0,6,13,19,22,20,14,9,5,2,1,1;
the last batch giving the numbers of connected graphs with 6 nodes and from 0 to 15 edges.

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

R. W. Robinson, Rows 1 to 20 of triangle, flattened (corrected by Sean A. Irvine, Apr 29 2022)
G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.
Sean A. Irvine, Java code (github)
Gordon Royle, Small graphs
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

Cf. A008406, A054925.
Other versions of this triangle: A046751, A076263, A054923, A046742.
Row sums give A001349, column sums give A002905. A046751 is essentially the same triangle. A054923 and A046742 give same triangle but read by columns.
Main diagonal is A000055. Next diagonal is A001429. Largest entry in each row gives A001437.

A076263 gives a Mathematica program which produces the nonzero entries in each row.
Needs["Combinatorica`"]; Table[Print[row = Join[Array[0&, n-1], Table[ Count[ Combinatorica`ListGraphs[n, k], g_ /; Combinatorica`ConnectedQ[g]], {k, n-1, n*(n-1)/2}]]]; row, {n, 1, 8}] // Flatten (* Jean-François Alcover, Jan 15 2015 *)

A369197 Number of labeled connected loop-graphs with n vertices, none isolated, and at most n edges.

Original entry on oeis.org

1, 1, 3, 13, 95, 972, 12732, 202751, 3795864, 81609030, 1980107840, 53497226337, 1592294308992, 51758060711792, 1824081614046720, 69272000503031475, 2819906639193992192, 122488526636380368714, 5654657850859704139776, 276462849597009068108405, 14270030377126199463936000

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

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

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

The minimal case is A000272.
Connected case of A066383 and A369196, loopless A369192 and A369193.
The loopless case is A129271, connected case of A369191.
The case of equality is A368951, connected case of A368597.
This is the connected case of A369194.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A001187 counts connected graphs, unlabeled A001349.
A006125 counts (simple) graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A062740 counts connected loop-graphs.
A322661 counts covering loop-graphs, unlabeled A322700.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000169, A000666, A001429, A005703, A006649, A057500, A116508, A140638, A143543, A367863, A369145.

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

Logarithmic transform of A368927.
From Andrew Howroyd, Feb 02 2024: (Start)
a(n) = A000169(n) + A129271(n).
E.g.f.: log(1/(1-T(x)))/2 + 3*T(x)/2 - 3*T(x)^2/4 + 1 - x, where T(x) is the e.g.f. of A000169. (End)

a(0) changed to 1 and a(7) onwards from Andrew Howroyd, Feb 02 2024

A001434 Number of graphs with n nodes and n edges.

Original entry on oeis.org

1, 0, 0, 1, 2, 6, 21, 65, 221, 771, 2769, 10250, 39243, 154658, 628635, 2632420, 11353457, 50411413, 230341716, 1082481189, 5228952960, 25945377057, 132140242356, 690238318754, 3694876952577, 20252697246580, 113578669178222, 651178533855913, 3813856010041981

Offset: 0

N. J. A. Sloane

The labeled version is A116508. - Gus Wiseman, Feb 22 2024

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

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
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 = 0..50 (terms 1..40 from Sean A. Irvine)
CombOS - Combinatorial Object Server, Generate graphs
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.

The connected case is A001429, labeled A057500.
The covering case is A006649, labeled A367863.
Diagonal n = k of A008406.
The labeled version is A116508.
The version with loops is A368598, connected A368983.
Allowing up to n edges gives A370315, labeled A369192.
A000088 counts unlabeled graphs, labeled A006125.
A001349 counts unlabeled connected graphs, labeled A001187.
A002494 counts unlabeled covering graphs, labeled A006129.
Cf. A000055, A005703, A014068, A054924, A137916, A137917, A236570, A369201.

(* first do *) Needs["Combinatorica`"] (* then *) Table[ NumberOfGraphs[n, n], {n, 24}] (* Robert G. Wilson v, Mar 22 2011 *)
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 /@ Subsets[Subsets[Range[n],{2}],{n}]]],{n,0,5}] (* Gus Wiseman, Feb 22 2024 *)

a(n) = polcoef(G(n, O(x*x^n)), n) \\ G defined in A008406. - Andrew Howroyd, Feb 02 2024

More terms from Vladeta Jovovic, Jan 07 2000

a(0)=1 prepended by Andrew Howroyd, Feb 02 2024

A369191 Number of labeled simple graphs covering n vertices with at most n edges.

Original entry on oeis.org

1, 0, 1, 4, 34, 387, 5686, 102084, 2162168, 52693975, 1450876804, 44509105965, 1504709144203, 55563209785167, 2224667253972242, 95984473918245388, 4439157388017620554, 219067678811211857307, 11489425098298623161164, 638159082104453330569185

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

Row-sums of left portion of A054548.

			The a(0) = 1 through a(3) = 4 graphs:
  {}  .  {{1,2}}  {{1,2},{1,3}}
                  {{1,2},{2,3}}
                  {{1,3},{2,3}}
                  {{1,2},{1,3},{2,3}}

The minimal case is A053530.
The connected case is A129271, unlabeled version A005703.
The case of equality is A367863, covering case of A367862.
This is the covering case of A369192, or A369193 for covered vertices.
The version for loop-graphs is A369194.
The unlabeled version is A370316.
A001187 counts connected graphs, unlabeled A001349.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A057500 counts connected graphs with n vertices and n edges.
A133686 counts choosable graphs, covering A367869.
A367867 counts non-choosable graphs, covering A367868.
Cf. A000169, A000272, A000666, A001429, A003465, A006649, A143543, A116508, A140638, A322661.

Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Length[Union@@#]==n&&Length[#]<=n&]],{n,0,5}]

Inverse binomial transform of A369193.

A236570 Number of n-node simple unicyclic graphs.

Original entry on oeis.org

1, 3, 9, 25, 68, 185, 504, 1379, 3788, 10480, 29094, 81193, 227379, 639099, 1801394, 5091388, 14422301, 40939337, 116420959, 331622137, 946020596, 2702412657, 7729367873, 22132856218, 63444473053, 182046034559, 522841943138, 1502920139133

Offset: 3

Eric W. Weisstein, Jan 29 2014

nonn

Andrew Howroyd, Table of n, a(n) for n = 3..500
Eric Weisstein's World of Mathematics, Unicyclic Graph.
Gus Wiseman, The a(6) = 25 graphs with a unique cycle.

The covering version is A372191, labeled A372195.
The labeled version is A372193.
Cf. A001429 (number of connected n-node unicyclic graphs), A005195.

Needs["Combinatorica`"];nn = 20; t[x_] := Sum[a[n] x^n, {n, 1, nn}]; a[0] = 0;
b = Drop[Flatten[
   sol = SolveAlways[
     0 == Series[
       t[x] - x Product[1/(1 - x^i)^ a[i], {i, 1, nn}], {x, 0, nn}],
     x]; Table[a[n], {n, 0, nn}] /. sol], 1];
r[x_] := Sum[b[[n]] x^n, {n, 1, nn}]; c =
Drop[Table[
    CoefficientList[
     Series[CycleIndex[DihedralGroup[n], s] /.
       Table[s[i] -> r[x^i], {i, 1, n}], {x, 0, nn}], x], {n, 3,
     nn}] // Total, 1];
d[x_] := Sum[c[[n]] x^n, {n, 1, nn}]; f =
Drop[CoefficientList[Series[r[x] - (r[x]^2 - r[x^2])/2, {x, 0, nn}],
   x], 1]; Drop[CoefficientList[
Series[d[x] Product[1/(1 - x^i)^f[[i]], {i, 1, nn}], {x, 0, nn}], x],3] (* Geoffrey Critzer, Nov 16 2014 *)

G.f.: A(x)*B(x) where A(x) is the o.g.f. for A001429 and B(x) is the o.g.f. for A005195. - Geoffrey Critzer, Nov 16 2014

Partial sums of A372191. - Gus Wiseman, Apr 27 2024

a(11)-a(30) from Geoffrey Critzer, Nov 16 2014

A054780 Number of n-covers of a labeled n-set.

Original entry on oeis.org

1, 1, 3, 32, 1225, 155106, 63602770, 85538516963, 386246934638991, 6001601072676524540, 327951891446717800997416, 64149416776011080449232990868, 45546527789182522411309599498741023, 118653450898277491435912500458608964207578

Offset: 0

Vladeta Jovovic, May 21 2000

Also, number of n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.

			From _Gus Wiseman_, Dec 19 2023: (Start)
Number of ways to choose n nonempty sets with union {1..n}. For example, the a(3) = 32 covers are:
  {1}{2}{3}  {1}{2}{13}  {1}{2}{123}  {1}{12}{123}  {12}{13}{123}
             {1}{2}{23}  {1}{3}{123}  {1}{13}{123}  {12}{23}{123}
             {1}{3}{12}  {1}{12}{13}  {1}{23}{123}  {13}{23}{123}
             {1}{3}{23}  {1}{12}{23}  {2}{12}{123}
             {2}{3}{12}  {1}{13}{23}  {2}{13}{123}
             {2}{3}{13}  {2}{3}{123}  {2}{23}{123}
                         {2}{12}{13}  {3}{12}{123}
                         {2}{12}{23}  {3}{13}{123}
                         {2}{13}{23}  {3}{23}{123}
                         {3}{12}{13}  {12}{13}{23}
                         {3}{12}{23}
                         {3}{13}{23}
(End)

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

Main diagonal of A055154.
Cf. A048291, A088310, A181230, A259763.
Covers with any number of edges are counted by A003465, unlabeled A055621.
Connected graphs of this type are counted by A057500, unlabeled A001429.
This is the covering case of A136556.
The case of graphs is A367863, covering case of A116508, unlabeled A006649.
Binomial transform is A367916.
These set-systems have ranks A367917.
The unlabeled version is A368186.
A006129 counts covering graphs, connected A001187, unlabeled A002494.
A046165 counts minimal covers, ranks A309326.
Cf. A006126, A058891, A059201, A133686, A323816, A323817, A323818, A326754, A367862, A367901.

Join[{1}, Table[Sum[StirlingS1[n+1, k+1]*(2^k - 1)^n, {k, 0, n}]/n!, {n, 1, 15}]] (* Vaclav Kotesovec, Jun 04 2022 *)
Table[Length[Select[Subsets[Rest[Subsets[Range[n]]],{n}],Union@@#==Range[n]&]],{n,0,4}] (* Gus Wiseman, Dec 19 2023 *)

a(n) = sum(k=0, n, (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n)) \\ Andrew Howroyd, Jan 20 2024

a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n).
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n+1, k+1)*(2^k-1)^n.
G.f.: Sum_{n>=0} log(1+(2^n-1)*x)^n/((1+(2^n-1)*x)*n!). - Paul D. Hanna and Vladeta Jovovic, Jan 16 2008
a(n) ~ 2^(n^2) / n!. - Vaclav Kotesovec, Jun 04 2022
Inverse binomial transform of A367916. - Gus Wiseman, Dec 19 2023

A137918 Array read by columns: T(n,m) = number of unlabeled graphs with n vertices and m unicyclic components.

Original entry on oeis.org

1, 2, 5, 13, 1, 33, 2, 89, 8, 240, 23, 1, 657, 74, 2, 1806, 220, 8, 5026, 674, 27, 1, 13999, 2011, 89, 2, 39260, 6038, 289, 8, 110381, 17980, 938, 27, 1, 311465, 53547, 2985, 94, 2, 880840, 158907, 9456, 309, 8, 2497405, 471225, 29722, 1035, 27, 1, 7093751

Offset: 3

Washington Bomfim, Mar 18 2008

			Array begins:
m/n|3.4.5..6..7..8...9..10...11...12....13....14.....15.....16.....17......18
---|-------------------------------------------------------------------------
1..|1.2.5.13.33.89.240.657.1806.5026.13999.39260.110381.311465.880840.2497405
2..|.......1..2..8..23..74..220..674..2011..6038..17980..53547.158907..471225
3..|.................1...2....8...27....89...289....938...2985...9456...29722
4..|...............................1.....2.....8.....27.....94....309....1035
5..|..................................................1......2......8......27
6..|........................................................................1
-----------------------------------------------------------------------------
m/n|.....19.......20.......21........22........23.........24.........25....
---------------------------------------------------------------------------
1..|7093751.20187313.57537552.164235501.469406091.1343268050.3848223585....
2..|1394786..4124929.12185636..35972082.106111713..312835608..921809509....
3..|..92842...288509...892506...2749940...8443504...25845735...78897469....
4..|...3382....11040....35659....114614....365970....1163167....3678680....
5..|.....94......315.....1060......3507.....11570......37853.....123196....
6..|......2........8.......27........94.......315.......1067.......3537....
7..|........................1.........2.........8.........27.........94....
8..|.......................................................1..........2....
9..|.......................................................................
The first row is A001429. Sums of columns form A137917.
Both the 5th and the 6th rows of table T begin with the same values, 1, 2, 8, 27, 94 and 315.
This happen since the number of graphs with n vertices and m components is equal to the number of graphs with n+3j vertices and m+j components, n >= 3, j >= 1.
So T(5,16) = T(6,19), T(5,17) = T(6,20), T(5,18) = T(6,21) etc.
In the sequence A138386 one can see the first terms of the m-th row of table T as m tends to infinity.
Parts equal to 3 do not change the values taken by the product in the formula since if i = 3, binomial(f(i) + K_i - 1, K_i) = binomial(1 + K_i - 1, Ki) = 1.
Because of that we take i >= 4 in the formula.

Alois P. Heinz, Table of n, a(n) for n = 3..86
Wikimedia commons, The 27 graphs with 12 points and 3 components, plus the 27 graphs with 15 points and 4 components.

Cf. A001429, A137917, A138386.

T(m, n) = sum over the partitions 3K_3 + ... + nK_n of n, whose smallest part is 3, that have exactly m parts of pi{4 <= i <= n}binomial(f(i) + K_i - 1, K_i), where f(i) is A001429(i).
For example, T(3,12) = T(4,15) = 27. The partitions of 12 of the form 3K_3 + ... + nK_n satisfying the restrictions are 4*3, 5+4+3 and 6+3*2. With n = 15 they are 4*3+3, 5+4+3*2 and 6+3*3. The partitions of 12 can be used to count the graphs in both cases, i.e., n = 12 and n = 15.
The partition 4*3 corresponds to binomial(2+3-1, 3), or 4 graphs. The partition 5+4+3 gives binomial(5,1) * binomial(2,1) or 10 graphs. Lastly, 6+3*2 corresponds to 13 graphs. Note that f(3) = 1, f(4) = 2, f(5) = 5 and f(6) = 13.

Edited by N. J. A. Sloane, Mar 21 2008

More terms from Alois P. Heinz, Jun 25 2014

A217781 Triangular array read by rows: T(n,k) is the number of n-node connected graphs with exactly one cycle of length k (and no other cycles) for n >= 1 and 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 9, 6, 3, 1, 1, 20, 16, 7, 4, 1, 1, 48, 37, 18, 9, 4, 1, 1, 115, 96, 44, 28, 10, 5, 1, 1, 286, 239, 117, 71, 32, 13, 5, 1, 1, 719, 622, 299, 202, 89, 45, 14, 6, 1, 1, 1842, 1607, 793, 542, 264, 130, 52, 17, 6, 1, 1

Offset: 1

Geoffrey Critzer, Mar 24 2013

Note that the structures counted in columns 1 and 2 are not simple graphs as we are allowing a self loop (column 1) and a double edge (column 2).

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    4,   3,   1,   1;
    9,   6,   3,   1,   1;
   20,  16,   7,   4,   1,   1;
   48,  37,  18,   9,   4,   1,   1;
  115,  96,  44,  28,  10,   5,   1,   1;
  286, 239, 117,  71,  32,  13,   5,   1,   1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Washington G. Bomfim, A picture of the twenty one unicycles with 3, 4, 5 and 6 vertices.

Cf. A068051 (row sums), A001429 (row sums for columns >= 3).
Cf. A000081 (column 1), A027852 (column 2), A000226 (column 3), A000368 (column 4).
Cf. A339428 (directed cycle).

nn=15;f[list_]:=Select[list,#>0&];t[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0==Series[t[x]-x Product[1/(1-x^i)^a[i],{i,1,nn}],{x,0,nn}],x];b=Table[a[n],{n,1,nn}]/.sol//Flatten;Map[f,Drop[Transpose[Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[b[[i]]x^(i*k),{i,1,nn}],{k,1,nn}][[j]],{j,1,n}],x],nn],{n,1,nn}]],1]]//Grid

\\ TreeGf is A000081 as g.f.
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)}
ColSeq(n,k)={my(t=TreeGf(max(0,n+1-k))); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec(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), -n)/2}
M(n, m=n)={Mat(vector(m, k, ColSeq(n,k)~))}
{ my(T=M(12)); for(n=1, #T~, print(T[n,1..n])) } \\ Andrew Howroyd, Dec 03 2020

O.g.f. for column k is Z(D[k],A(x)). That is, we substitute for each variable s[i] in the cycle index of the dihedral group of order 2k the series A(x^i), where A(x) is the o.g.f. for A000081.

A036671 Number of isomers C_n H_{2n} without double bonds.

Original entry on oeis.org

0, 0, 1, 2, 5, 12, 29, 73, 185, 475, 1231, 3232, 8506, 22565, 60077, 160629, 430724, 1158502, 3122949, 8437289, 22836877, 61918923, 168139339, 457225555, 1244935251, 3393754661, 9261681937, 25301337669, 69184724389, 189349490641

Offset: 1

N. J. A. Sloane

Equivalently, the number of simple unicyclic graphs on n unlabeled vertices with all degrees at most 4. See table 1 in Michael A. Kappler reference. - Jonathan Vos Post, Dec 07 2005, Andrew Howroyd, May 22 2018

Camden A. Parks and James B. Hendrickson, Enumeration of monocyclic and bicyclic carbon skeletons, J. Chem. Inf. Comput. Sci., vol. 31, 334-339 (1991). See page 335 Table 1.
J. B. Hendrikson and C. A. Parks, "Generation and Enumeration of Carbon skeletons", J. Chem. Inf. Comput. Sci, vol. 31 (1991) pp. 101-107. See Table 2, column 3 on page 103.

Andrew Howroyd, Table of n, a(n) for n = 1..500
Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs.
G. Polya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145-254.

Cf. A000598, A000642, A001429.

\\ here G is A000598 as series
G(n)={my(g=O(x)); for(n=1, n, g = 1 + x*(g^3/6 + subst(g,x,x^2)*g/2 + subst(g,x,x^3)/3) + O(x^n)); g}
seq(n)={my(t=G(n-2)); t=x*(t^2+subst(t,x,x^2))/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, -n)} \\ Andrew Howroyd, May 22 2018

Polya reference gives an explicit g.f.; so does Parks et al.

More terms from Vladeta Jovovic, Aug 19 2001

A000226 Number of n-node unlabeled connected graphs with one cycle of length 3.

Original entry on oeis.org

1, 1, 3, 7, 18, 44, 117, 299, 793, 2095, 5607, 15047, 40708, 110499, 301541, 825784, 2270211, 6260800, 17319689, 48042494, 133606943, 372430476, 1040426154, 2912415527, 8167992598, 22947778342, 64577555147, 182009003773, 513729375064, 1452007713130

Offset: 3

N. J. A. Sloane

Number of rooted trees on n+1 nodes where root has degree 3. - Christian G. Bower
Third column of A033185. - Michael Somos, Aug 20 2018
From Washington Bomfim, Dec 22 2020: (Start)
Number of forests of 3 rooted trees with a total of n nodes.
Number of unicyclic graphs with a cycle of length 3 and a total of n nodes.
(End)

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

Alois P. Heinz, Table of n, a(n) for n = 3..1000 (first 198 terms from Vincenzo Librandi)
Sergei Abramovich, Partitions of integers, Ferrers-Young diagrams, and representational efficacy of spreadsheet modeling, Spreadsheets in Education (eJSiE): Vol. 5: Iss. 2, Article 1, p. 5
Washington Bomfim, Illustration of initial terms
F. Ruskey, Combinatorial Generation, Eq.(4.27), 2003
Eric Weisstein's World of Mathematics, Rooted Tree
Index entries for sequences related to rooted trees

Column 3 of A033185 and A217781.
Cf. A000081, A001429.
For n >= 3 a(n) = A217781(n, 3) = A058879(n, n-2) = A033185(n, 3).

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; unapply(add(b(k)*x^k, k=1..n),x) end: a:= n-> coeff(series((B(n-2)(x)^3+ 3*B(n-2)(x)* B(n-2)(x^2)+ 2*B(n-2)(x^3))/6, x=0, n+1), x,n): seq(a(n), n=3..40); # Alois P. Heinz, Aug 21 2008

terms = 30; r[] = 0; Do[r[x] = x *Exp[Sum[r[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms+3}]; A[x_] = (r[x]^3 + 3*r[x]*r[x^2] + 2*r[x^3])/6 + O[x]^(terms+3); Drop[CoefficientList[A[x], x], 3] (* Jean-François Alcover, Nov 23 2011, updated Jan 11 2018 *)

seq(max_n) = {my(a = f = vector(max_n), s, D); f[1]=1;
for(j=1, max_n - 1, f[j+1] = 1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1]));
for(n=3,max_n,s=0;forpart(P=n,D=Set(P);if(#D==3,s+=f[P[1]]*f[P[2]]*f[P[3]];next());
if(#D==1, s+= binomial(f[P[1]]+2, 3); next());
if(P[1] == P[2], s += binomial(f[P[1]]+1, 2) * f[P[3]],
s += binomial(f[P[2]]+1, 2) * f[P[1]]),[1,n],[3,3]); a[n] = s ); a[3..max_n] }; \\ Washington Bomfim, Dec 22 2020

G.f.: (r(x)^3+3*r(x)*r(x^2)+2*r(x^3))/6 where r(x) is g.f. for rooted trees (A000081).
a(n) = Sum_{j1+2j2+···= n} (Product_{i=1..n} binomial(A000081(i) + j_i -1, j_i)) [(4.27) of [F. Ruskey] with n replaced by n+1]. - Washington Bomfim, Dec 22 2020
a(n) ~ (A187770 + A339986) * A051491^n / (2 * n^(3/2)). - Vaclav Kotesovec, Dec 25 2020

More terms from Vladeta Jovovic, Apr 19 2000

cp's OEIS Frontend

A054924 Triangle read by rows: T(n,k) = number of nonisomorphic unlabeled connected graphs with n nodes and k edges (n >= 1, 0 <= k <= n(n-1)/2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

A369197 Number of labeled connected loop-graphs with n vertices, none isolated, and at most n edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A001434 Number of graphs with n nodes and n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A369191 Number of labeled simple graphs covering n vertices with at most n edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A236570 Number of n-node simple unicyclic graphs.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A054780 Number of n-covers of a labeled n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A137918 Array read by columns: T(n,m) = number of unlabeled graphs with n vertices and m unicyclic components.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A217781 Triangular array read by rows: T(n,k) is the number of n-node connected graphs with exactly one cycle of length k (and no other cycles) for n >= 1 and 1 <= k <= n.

Views

Author

Keywords