A001429 -id:A001429 - cp's OEIS frontend

A343873 Triangle read by rows: T(n,k) is the number of unlabeled connected planar graphs with n edges and k nodes (n >= 0, 1 <= k <= n + 1).

1, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 2, 3, 0, 0, 0, 1, 5, 6, 0, 0, 0, 1, 5, 13, 11, 0, 0, 0, 0, 4, 19, 33, 23, 0, 0, 0, 0, 2, 22, 67, 89, 47, 0, 0, 0, 0, 1, 19, 107, 236, 240, 106, 0, 0, 0, 0, 0, 13, 130, 486, 797, 657, 235, 0, 0, 0, 0, 0, 5, 130, 804, 2075, 2678, 1806, 551

Offset: 0

Andrew Howroyd, May 06 2021

First differs from A054923 in row n=9.

Terms may be computed using the tools geng and planarg in nauty.

			Triangle begins (n edges >= 0, k vertices >= 1):
  1;
  0, 1;
  0, 0, 1;
  0, 0, 1, 2;
  0, 0, 0, 2, 3;
  0, 0, 0, 1, 5,  6;
  0, 0, 0, 1, 5, 13,  11;
  0, 0, 0, 0, 4, 19,  33,  23;
  0, 0, 0, 0, 2, 22,  67,  89,  47;
  0, 0, 0, 0, 1, 19, 107, 236, 240, 106;
  0, 0, 0, 0, 0, 13, 130, 486, 797, 657, 235;
  ...

Georg Grasegger, Table of n, a(n) for n = 0..285 (rows 0..22) (terms 0..209 (rows 0..19) from Andrew Howroyd)
Brendan McKay and Adolfo Piperno, nauty and Traces

Row sums are A046091.
Column sums are A003094.
Main diagonal is A000055.
Subsequent diagonals are A001429, A001435, A001436 (same as for not necessarily planar graphs).
Cf. A049334 (transpose), A054923, A343870.

geng -c $k $n:$n | planarg -q | countg -q # Georg Grasegger, Jul 06 2023

A369289 Number of connected graphs with loops (symmetric relations) on n unlabeled vertices with at most n edges.

Original entry on oeis.org

1, 2, 2, 4, 8, 17, 39, 92, 227, 573, 1482, 3883, 10343, 27786, 75392, 205933, 566166, 1564316, 4342431, 12100382, 33836606, 94903889, 266914438, 752517020, 2126292931, 6020035120, 17075411671, 48514471709, 138051863755, 393397897262, 1122523343690

Offset: 0

Andrew Howroyd, Feb 02 2024

nonn

The graphs considered here can have loops but not parallel edges.

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

Cf. A000055, A000081, A001429, A368983, A369145.

\\ 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)={my(t=TreeGf(n)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec(1 + (sum(d=1, n, eulerphi(d)/d*log(1/(1-g(d)))) + ((1+g(1))^2/(1-g(2))-1)/2 + 2*g(1) - 2*g(1)^2 )/2)  }

a(n) = A000055(n) + A368983(n) = A000055(n) + A000081(n) + A001429(n) for n > 0.

Inverse Euler transform of A369145.

A384966 Number of sensed simple planar maps with n vertices and 2 faces.

Original entry on oeis.org

0, 0, 1, 2, 8, 29, 113, 444, 1763, 6951, 27395, 107672, 422330, 1654180, 6472518, 25308760, 98923442, 386589398, 1510737079, 5904291401, 23079308104, 90236258057, 352908128341, 1380632536468, 5403055984114, 21152009997924, 82835786189975, 324518950873991, 1271797441923614, 4985982054721119

Offset: 1

Andrew Howroyd, Jun 14 2025

nonn

In other words, a(n) is the number of embeddings on the sphere of connected simple unicyclic planar graphs with n nodes up to orientation preserving isomorphisms.

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Column 2 of A384964.

Cf. A001429, A006078 (cycle is loop), A007595 (cycle is digon), A380237 (not necessarily simple), A384967 (unsensed version)..

seq(n)={my(c(d)=(1-sqrt(1-4*x^d + O(x*x^(n+d))))/(2*x^d)); Vec(1/(1 - x*c(2)) - x*(c(1)^2 + c(2)) - x^2*(c(1)^4 + 3*c(2)^2)/2 - 1 - sum(k=1, n, log(2 - c(k))*eulerphi(k)/k), -n)/2}

a(n) = A380237(n) - A007595(n) - A006078(n).

A384967 Number of unsensed simple planar maps with n vertices and 2 faces.

Original entry on oeis.org

0, 0, 1, 2, 7, 22, 76, 271, 1001, 3765, 14381, 55450, 214880, 835663, 3255652, 12698352, 49559793, 193513944, 755852101, 2953214386, 11541989533, 45123241746, 176465152051, 690340349398, 2701579878022, 10576116931462, 41418132927403, 162259989848094, 635899817853002, 2492993368347594

Offset: 1

Andrew Howroyd, Jun 15 2025

nonn

In other words, a(n) is the number of embeddings on the sphere of connected simple unicyclic planar graphs with n nodes.

Column 2 of A384963.
Also subdiagonal of A379430.
Cf. A001429, A006081 (cycle is loop), A380239 (not necessarily simple), A384966 (sensed version).

G1(n)={my(g=(1-sqrt(1-4*x^2 + O(x^(n+2))))/(2*x^2)); ((1 + x/(1-x-x^2*g)^2)^2/(1 - x^2*g^2) - 1)/2 + 1/(1 - x*g) - 1 - x*(g^2/(1 - x*g)^2 + g) - x^2*(g^4/(1 - x*g)^4 + 3*g^2)/2}
G2(n)={my(c(d)=(1-sqrt(1-4*x^d + O(x*x^(n+d))))/(2*x^d)); sum(k=1, n, my(m=1+k%2); -(log(2 - c(k)) + log(1 - x^k*c(m*k)^(2/m)))*eulerphi(k)/k, O(x*x^n)) - x*(c(1)^2 + c(2)) - x^2*(c(1)^4 + 3*c(2)^2)/2}
seq(n)={Vec(G1(n)+G2(n), -n)/4}

A381470 Number of simple connected graphs on n unlabeled nodes with exactly 2 non-overlapping cycles.

Original entry on oeis.org

1, 4, 21, 85, 345, 1289, 4713, 16622, 57535, 195212, 653318, 2158866, 7063333, 22906699, 73742762, 235863378, 750187968, 2374249283, 7481414941, 23482536967, 73449564533, 229016163367, 712044375528, 2208131225648, 6831543467752, 21089958138852, 64978894444220

Offset: 6

Andrew Howroyd, Feb 25 2025

nonn

All such graphs are cactus graphs (with bridges allowed).

			The a(6) = 1 graph is:
    o       o
   / \     / \
  o---o---o---o
.
The a(7) = 4 graphs are:
    o     o---o     o   o   o       o---o   o       o   o   o
   / \    |   |    / \ / \ / \     / \     / \     / \ /   / \
  o---o---o---o   o---o   o---o   o---o---o---o   o---o---o---o

Andrew Howroyd, Table of n, a(n) for n = 6..1000
Wikipedia, Cactus graph.
Index entries for sequences related to cacti.

Column k=2 of A381467.

Cf. A000081, A000083, A001429.

\\ 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)={my(t=TreeGf(n), t2=subst(t,x,x^2), g=t*(t^2/(1-t) + t2*(1+t)/(1-t2))/2, g2=subst(g,x,x^2)); Vec(g^2/(1-t) + g2*(1+t)/(1-t2))/2}

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

Original entry on oeis.org

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

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

A214650 Number of distinct connected unicyclic bipartite graphs with n vertices.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 10, 34, 85, 254, 690, 1997, 5582, 15975, 45244, 129254, 368215, 1052961, 3010169, 8622273, 24709964, 70902886, 203594559, 585163116, 1683079071, 4844758076, 13955265122, 40225474849, 116021495035, 334843170810, 966929417619, 2793756318793

Offset: 1

David Bevan, Jul 24 2012

nonn

The graphs also have n edges.

			a(5)=1, a 4-cycle plus a pendant edge.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Unicyclic Graph

Cf. A001429.

\\ 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)={concat([0,0,0], if(n<4, [], 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=2, n\2, sumdiv(2*k, d, eulerphi(d)*g(d)^(2*k/d))/k + (g(1)^2+g(2))*g(2)^(k-1))/4)))} \\ Andrew Howroyd, May 22 2018

Terms a(16) and beyond from Andrew Howroyd, May 22 2018

A138237 Number of unlabeled graphs with at least one cycle in which every connected component has at most one cycle.

Original entry on oeis.org

1, 3, 9, 26, 71, 197, 543, 1507, 4186, 11722, 32883, 92724, 262179, 743792, 2115019, 6028779, 17217093, 49258009, 141142096, 404997704, 1163569094, 3346830818, 9636723582, 27774427243, 80121104084, 231317022483, 668346261557

Offset: 3

Washington Bomfim, May 17 2008

nonn

			a(9)=543 since we have several cases, with one unicyclic graph, or two, or three. Namely,
-One triangle and a forest of order 6, or 20 graphs.
-One unicyclic graph with 4 nodes and a forest of order 5, or 20 graphs.
-One unicyclic graph with 5 nodes and a forest of order 4, or 30 graphs.
-One unicyclic graph with 6 nodes and a forest of order 3, or 39 graphs.
-One unicyclic graph of 7 nodes and a forest of order 2, or 66 graphs.
-One unicyclic graph of 8 nodes and an isolated vertex, or 89 graphs.
-One unicyclic graph of 9 nodes, or 240 graphs.
-Two triangles and a forest of order 3, or 3 graphs.
-One triangle plus one unicyclic graph of 4 nodes plus a forest of order 2, or 4 graphs.
-One triangle plus one unicyclic graph of 5 nodes plus an isolated vertex, or 5 graphs.
-One triangle plus one unicyclic graph of 6 nodes, or 13 graphs.
-Two unicyclic graphs of 4 nodes and an isolated vertex, or C(2+2-1,2)=3 graphs.
-One unicyclic graph of 5 nodes and another of 4 nodes, or 10 graphs.
-Three triangles, or 1 graph.
Total = 543.

Wikipedia, Pseudoforest.

Cf. A001429, A005195, A140145.

a(n) = A134964(n) - A005195(n).

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

A343873 Triangle read by rows: T(n,k) is the number of unlabeled connected planar graphs with n edges and k nodes (n >= 0, 1 <= k <= n + 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

A369289 Number of connected graphs with loops (symmetric relations) on n unlabeled vertices with at most n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A384966 Number of sensed simple planar maps with n vertices and 2 faces.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A384967 Number of unsensed simple planar maps with n vertices and 2 faces.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A381470 Number of simple connected graphs on n unlabeled nodes with exactly 2 non-overlapping cycles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A214650 Number of distinct connected unicyclic bipartite graphs with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A138237 Number of unlabeled graphs with at least one cycle in which every connected component has at most one cycle.