在組合數學中,串並聯網路問題要求計算可以使用給定數量的邊形成的網路的數量。邊可以是可區分的或不可區分的。
當邊不可區分時,考慮列舉在 條邊上拓撲不同的網路的數量問題,其中允許多條邊。 想法是透過將網路分類為本質上是串聯和本質上是並聯網路來分解問題。
1. “本質上是串聯網路”是可以分解為兩個或多個串聯“子網路”的網路。
2. “本質上是並聯網路”是可以分解為兩個或多個並聯“子網路”的網路。
透過網路的對偶性,可以證明本質上是串聯網路的數量等於本質上是並聯網路的數量。 因此,對於所有 ,
條邊中的網路數量是本質上是串聯網路數量的兩倍。 對於
,網路數量為 1。
將 定義為
條不可區分的邊上的串並聯網路的數量,將
定義為本質上是串聯網路的數量。 然後
|
(1)
|
可以透過列舉
的分partitions來找到。 考慮
的一個分partition
,即,
|
(2)
|
那麼,本質上是串聯網路的數量可以計算為 。 因此
|
(3)
|
其中,求和是對 的所有分partitions
進行的,不包括平凡分partition
。 這給出了一個用於計算
的遞迴,由此可以如上計算
。
此外,該序列滿足
|
(4)
|
或更明確地,
|
(5)
|
對於
, 2, ... 的前幾個值是 1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624, ... (OEIS A000084),而
的前幾個值是 1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, ... (OEIS A000669)。
Valdes (1978) 表明,偏序集是串並聯的,當且僅當其可比性圖是 cograph。