2
$\begingroup$

The sequence A000137:

1, 2, 6, 18, 58, 186, 614, 2034, 6818, 22970, 77858, 264970, 905294, 3102434, ...

only has the following description on OEIS:

Series-parallel numbers

It offers no explanation as to what that means and a web search doesn't give anything useful (series-parallel numbers gives a bunch of things about circuits and "series-parallel numbers" gives mostly OEIS sequences).

What does this mean, and how are these numbers computed?

$\endgroup$
2
  • $\begingroup$ While the detail on the A000137 page is meager, it lists a simple relation between its GF and that of A000084. Moreover, the page for A000084 is much more detailed. See also line m=1 of this table from Riordan's book (via Google Books): books.google.com/… $\endgroup$ Aug 6, 2017 at 17:48
  • $\begingroup$ @Semiclassical Oh cool, thanks for the info! $\endgroup$ Aug 6, 2017 at 17:50

1 Answer 1

2
$\begingroup$

There are some cross-references at A137 itself, but there is also an entry in the Index to the OEIS that lays out some of those links. Note that the Index has marked A84 with an asterisk. This is because it is the main or core sequence among this related collection of sequences indexed here. A84 defines these networks recursively, as models of two-terminal electrical networks (with no content about the electrical components besides connectivity). You can form these networks from smaller networks by joining two either in series or in parallel.

The only non-OEIS reference in A137 is:

  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.

Therein, series-parallel networks are defined as in A84 (as noted by Semiclassical). These are also discussed elsewhere, like MathWorld or Wikipedia.

Riordan goes on discusses some properties of these networks and the duality between those that are "essentially serial" * and "essentially parallel" -- the two subclasses of graphs that are created by one of the two operations (joining in series, or else in parallel) as the last step in this recursive construction. (One might take a moment to consider why no graph would be both.)

(*Riordan says "essentially series," but I inadvertently found myself auto-correcting it to "essentially serial," which I apparently prefer.)

In particular, on page 140, he defines $a_{n,m}$ to be "the number of essentially parallel networks with $n$ elements, $m$ of which are labeled with distinct labels." The purpose of this definition is to prove some things about the enumeration of these classes.

In context, it is important to remember, "elements" here means edges, since we are thinking of electrical networks, where a component of a circuit would be an edge in the graph, not a vertex. And of course, this count is up to isomorphism, so that the network $o-o=o$ is the same as $o=o-o$, despite being drawn in reverse direction, unless perhaps one or more of those edges is also labeled.

On the following page, Riordan defines $S_{n,m}$ likewise for all two-terminal series-parallel networks. Two pages later, he gives a table of $S_{n,m}$ and by inspection, A137 is the second row of that table, $S_{n,1}$. (n.b. Columns of this table are by definition finite, since it must be that $m\le n$.)

A84, the more basic sequence, is $S_{n,0}$, which is to say, the enumeration of such networks with no labeled elements. It is the first row of the table.

There are probably a number of older sequences that seem to lack exposition that consist mainly of a single external reference and few cross-refs, which would have been more useful in the days when the EIS was a printed text that was used in consultation with a library of other volumes. Entries were much more terse back then.

I think it is a great idea to get a brief, lucid definition of these sequences into their entries in the OEIS, and I appreciate that you've raised the question. I may come back to this section of the Index and try to get these few sequences updated with a bit of this information when I have some extra time.

I will also note for reference that the original Handbook of Integer Sequences cites the following article at N0466 (in addition to Riordan's book):

  • J. Riordan and C. E. Shannon, The number of two-terminal series-parallel networks, J. Math. Phys., 21 (1942), 83-93.

This was reprinted in:

  • Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 560-570.

In The Encyclopedia of Integer Sequences, entry M1207 updates this with the following reference as well:

  • Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.

Those may also be of interest to someone reading this answer.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .