Series-parallel networks problem

In combinatorial mathematics, the series-parallel networks problem asks for the number of series-parallel networks that can be formed using a given number of edges. The edges can be distinguishable or indistinguishable.

Indistinguishable edges

When the edges are indistinguishable, we look for the number of topologically different networks on n edges.

Solution

The idea is to break-down the problem by classifying the networks as essentially series and essentially parallel networks.

An essentially series network is a network which can be broken down into two or more subnetworks in series.
An essentially parallel network is a network which can be broken down into two or more subnetworks in parallel.

By the duality of networks, it can be proved that the number of essentially series networks is equal to the number of essentially parallel networks. Thus for all n > 1, the number of networks in n edges is twice the number of essentially series networks. For n = 1, the number of networks is 1.

Define

$a_{n}$ as the number of series-parallel networks on n indistinguishable edges.
$b_{n}$ as the number of essentially series networks.

Then

a_{n}=\left\{{\begin{matrix}1,&{\mbox{if }}n{\mbox{ is 1}}\\2b_{n},&{\mbox{otherwise}}\end{matrix}}\right.

$b_{n}$ can be found out by enumerating the partitions of $n$ .

Consider a partition, $\{p_i\}$ of n:

\sum _{i}{ip_{i}}=n.

Consider the essentially series networks whose components correspond to the partition above. That is the number of components with i edges is $p_{i}$ . The number of such networks can be computed as

\prod _{i}{{b_{i}+p_{i}-1} \choose {p_{i}}}.

Hence

b_{n}=\sum _{p_{i}}{\prod _{i}{{b_{i}+p_{i}-1} \choose {p_{i}}}}

where the summation is over all partitions, $p_{i}$ of n except for the trivial partition consisting of only n.

This gives a recurrence for computing $b_{n}$ . Now $a_{n}$ can be computed as above.

[TODO: Generating function for $a_{n}$ and $b_{n}$ are explained in the external links.]

External links

"Sloane's A000084 : Number of series-parallel networks with n unlabeled edges". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
"Sloane's A000669 : Number of series-reduced planted trees with n leaves". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
Asymptotic behavior of two-terminal series-parallel networks

This article is issued from Wikipedia - version of the 11/16/2011. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.