A304074 -id:A304074 - cp's OEIS frontend

A338487 a(n) is the number of non-isomorphic, serial/parallel indecomposable resistor networks with n edges, n >= 5, allowing dead ends.

1, 5, 36, 225, 1453, 9228, 58701, 372695, 2370155, 15117459, 96868355, 624326820, 4051597971, 26496771687, 174749567296, 1162909625384, 7812487626519, 53005074235282, 363305517314289, 2516343623698964, 17615995074375601, 124669825295709879, 892060223018406365

Offset: 5

Rainer Rosenthal and Hugo Pfoertner, Oct 30 2020

nonn

A connected multigraph G with a selected pair P of nodes can be used to represent a resistor network. The edges represent resistors, and the total resistance is measured between the selected nodes. It is possible to construct complex networks using only serial or parallel combinations, but the more nodes and edges are involved, the more networks of a different kind can be found. They cannot be decomposed into serial/parallel elements. The sequence is on page 2 of the paper describing the computation of A180414 (see the Joel Karnofsky link).

Karnofsky claims that he systematically increased the number of edges by three basic operations, C, D, and E, defined in A338999, i.e., he claims to have counted the CDE-descendants of the simplest h-graph (the "bridge," see the example section). Numbers given in his paper are 1, 5, 37, 226, 1460, 9235, which is slightly off (see A339386). The difference seems to stem from the "dangling parts," as he calls them in his "addendum," so they don't affect the computation of different resistances in A180414. - Rainer Rosenthal, Dec 02 2020

			a(5) = 1. The only serial/parallel nondecomposable network with 5 resistors:
.
                      (+)-----A
     The "bridge"            / \
     see A337516            B---C
                             \ /
                      (-)-----Z
.
a(6) = 5. Constructed from the bridge with 5 resistors.
Allowed ways of adding a new edge are:
* an existing resistor is replaced by two parallel (N1, N2).
* a new resistor is appended (N3).
* an existing resistor is replaced by two serial (N4, N5).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
                    .                   .
         .-A        .         A         .         A
        / / \       .        / \        .   D    / \
       / /   \      .       /   \       .   |   /   \
      / /     \     .      /     \      .   |  /     \
     | /       \    .     /       \     .   | /       \
     |/         \   .    /.-------.\    .   |/         \
     B-----------C  .   B.         .C   .   B-----------C
      \         /   .    \`-------´/    .    \         /
       \       /    .     \       /     .     \       /
        \     /     .      \     /      .      \     /
         \   /      .       \   /       .       \   /
          \ /       .        \ /        .        \ /
           Z        .         Z         .         Z
                    .                   .
     N1: new edge   .   N2: new edge    .  N3: new node D
           A-B      .         B-C       .   with edge B-D
                    .                   .
  . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
                    .
           A        .         A
          / \       .        / \
         /   \      .       /   \
        D     \     .      /     \
       /       \    .     /       \
      /         \   .    /         \
     B-----------C  .   B-----D-----C
      \         /   .    \         /
       \       /    .     \       /
        \     /     .      \     /
         \   /      .       \   /
          \ /       .        \ /
           Z        .         Z
                    .
    N4: new node D  .  N5: new node D
     A-B now A-D-B  .   B-C now B-D-C
                    .
. . . . . . . . . . . . . . . . . . . . .
a(7) = 36. There are 24 interesting networks without dead ends.
See the pdf document with their description in the link section.

Technology Review's Puzzle Corner, How many different resistances can be obtained by combining 10 one ohm resistors? Oct 3, 2003.

Allan Gottlieb, Oct 3, 2003 addendum (Karnofsky).
Andrew Howroyd, PARI Program
Joel Karnofsky, Solution of problem from Technology Review's Puzzle Corner Oct 3, 2003, Feb 23, 2004.
Rainer Rosenthal, Maple Program, Dec 02 2020.
Rainer Rosenthal, The 24 networks with 7 resistors without dead ends (version 2), Feb 08 2021.

Cf. A180414, A048211, A174283, A337516, A337517.

For graphs with two distinguished nodes see A304074.

SetA338487(5) := {"011111"}: # "bridge" adjacency matrix coded
for n from 6 to MAXEDGES do
   SetA338487(n) := C_D_E(SetA338487(n-1));  # see link section
od:
seq(nops(SetA338487(n)),n=1..MAXEDGES); # Rainer Rosenthal, Dec 02 2020

a(10)-a(27) from Andrew Howroyd, Dec 02 2020

A339040 Number of unlabeled connected simple graphs with n edges rooted at two noninterchangeable vertices.

Original entry on oeis.org

1, 3, 10, 35, 125, 460, 1747, 6830, 27502, 113987, 485971, 2129956, 9591009, 44341610, 210345962, 1023182861, 5100235807, 26035673051, 136023990102, 726877123975, 3970461069738, 22156281667277, 126234185382902, 733899631974167, 4351500789211840

Offset: 1

Andrew Howroyd, Nov 20 2020

nonn

Cf. A000664, A002905, A303832, A304074, A339039, A339041, A339042, A339044, A339063.

\\ See A339063 for G.
seq(n)={my(A=O(x*x^n), g=G(2*n, x+A, [])); Vec(G(2*n, x+A, [1, 1])/g - (G(2*n, x+A, [1])/g)^2)}

G.f.: f(x)/g(x) - r(x)^2 where f(x), g(x) and r(x) are the g.f.'s of A339063, A000664 and A339039.

A304070 Number of simple graphs with n vertices rooted at a pair of distinguished vertices.

Original entry on oeis.org

0, 2, 8, 40, 240, 1992, 24416, 483040, 16343872, 982635280, 106979975168, 21285548190080, 7783083940331520, 5254164116114948480, 6577258363669088914432, 15332656940815954900371968, 66830735142688170751257497600, 546722015615195079134707942219904

Offset: 1

Brendan McKay, May 05 2018

nonn

The graphs do not need to be connected.

			a(3)=8: 1 for the graph with no edge, 3 for the graph with one edge, 3 for the graph with two edges, 1 for the triangle.

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

Cf. A304074 (for connected graphs), A000088 (not rooted).

a(n) = 2*A304069(n).

Terms a(13) and beyond from Andrew Howroyd, May 06 2018

A304072 Number of simple connected graphs with n nodes rooted at one oriented edge.

Original entry on oeis.org

0, 1, 3, 15, 95, 848, 11043, 227978, 7915413, 482871723, 52989880632, 10588770680260, 3880844130502271, 2623179650433475894, 3285998146525888516756, 7663037181052161495721168, 33407697920116540678510839469, 273327584706334343769636571729201

Offset: 1

Brendan McKay, May 05 2018

nonn

			a(3)=3: one choice of orienting an edge in the triangle graph; two choices of orienting an edge in the linear graph (orientation towards or away from the center node).

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

Cf. A000088, A001349 (not rooted), A304069 (not necessarily connected).

nmax = 20;
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]];
a69[n_] := If[n < 2, 0, s = 0; Do[s += permcount[p]*(2^(2*Length[p] + edges[p])), {p, IntegerPartitions[n - 2]}]; s/(n - 2)!];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
gf = Sum[a69[n] x^n, {n, 0, nmax}]/Sum[a88[n] x^n, {n, 0, nmax}]+O[x]^nmax;
CoefficientList[gf, x] // Rest (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)

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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
g(n,r) = {my(s=0); forpart(p=n, s+=permcount(p)*(2^(r*#p+edges(p)))); s/n!}
seq(n)={concat([0], Vec(Ser(vector(n,n,g(n-1,2)))/Ser(vector(n,n,g(n-1,0)))))} \\ Andrew Howroyd, May 06 2018

a(n) + A304073(n) = A304074(n).

G.f.: R(x)/G(x) where R(x) is the g.f. of A304069 and G(x) is the g.f. of A000088. - Andrew Howroyd, May 06 2018

Terms a(13) and beyond from Andrew Howroyd, May 06 2018

A304073 Number of simple connected graphs with n nodes rooted at one oriented non-edge.

Original entry on oeis.org

0, 0, 1, 8, 67, 701, 10047, 218083, 7758105, 478466565, 52762737260, 10566937121191, 3876933205880431, 2621875289142578194, 3285187439267316978728, 7662096100649423384254265, 33405651855362295512020765765, 273319227135047244053866187609854

Offset: 1

Brendan McKay, May 05 2018

nonn

			a(3)=1: no contribution from the triangle graph; one case of joining the leaves of the linear graph.
a(4)=8: we start from the 6 cases of non-oriented non-edges of A304071 and note two geometries where the orientation makes a difference: for the triangular graph with a protruding edge the orientation matters (to or from the leaf), and also for the linear graph with 4 nodes (to or from the leaf).

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

Cf. A001349 (not rooted), A304069 (not necessarily connected).

Cf. A000088, A000666.

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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
cross(u, v) = {sum(i=1, #u, sum(j=1, #v, gcd(u[i], v[j])))}
S(n, r)={my(t=#r+1); vector(n+1, n, if(nAndrew Howroyd, Sep 07 2019

a(n) + A304072(n) = A304074(n).

G.f.: B(x)/G(x) - (x*C(x)/G(x))^2, where B(x) is the g.f. of A304069, C(x) is the g.f. of A000666 and G(x) is the g.f. of A000088. - Andrew Howroyd, Sep 07 2019

Terms a(13) and beyond from Andrew Howroyd, Sep 07 2019

A340028 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of noninterchangeable vertices.

Original entry on oeis.org

0, 1, 1, 7, 55, 655, 11147, 287791, 11787747, 804475261, 94875366649, 19825870580671, 7466490852631207, 5129453728126116131, 6487332587944013948099, 15213161506747424007012971, 66536415576917924594383104139, 545371527333985035460963541248785

Offset: 1

Andrew Howroyd, Jan 02 2021

nonn

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

Cf. A002218, A004115, A241768, A304070, A304074, A340029.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(g=graphsSeries(n), gcr=sPoint(g)/g); x*sPoint(sSolve( sLog( gcr/(x*sv(1)) ), gcr ))}
{ my(N=15); Vec(OgfSeries(cycleIndexSeries(N)), -N) }

cp's OEIS Frontend

A338487 a(n) is the number of non-isomorphic, serial/parallel indecomposable resistor networks with n edges, n >= 5, allowing dead ends.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Extensions

A339040 Number of unlabeled connected simple graphs with n edges rooted at two noninterchangeable vertices.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A304070 Number of simple graphs with n vertices rooted at a pair of distinguished vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A304072 Number of simple connected graphs with n nodes rooted at one oriented edge.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A304073 Number of simple connected graphs with n nodes rooted at one oriented non-edge.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A340028 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of noninterchangeable vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI