在组合数学中,串并联网络问题要求计算可以使用给定数量的边形成的网络的数量。边可以是可区分的或不可区分的。
当边不可区分时,考虑枚举在 条边上拓扑不同的网络的数量问题,其中允许多条边。 想法是通过将网络分类为本质上是串联和本质上是并联网络来分解问题。
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。