积和式

在数学，特别是线性代数中，积和式是一个与行列式类似的多项式。与行列式类似，积和式可以看作是定义在一个变量矩阵上。积和式在计算机科学，特别是计算复杂性理论中有重要的地位。比如计算一个二分图（bipartite graph）的完美匹配（perfect matching）的数目可以方便的表示为计算积和式的值。

组合上的解释

积和式的定义可以从如下两方面理解，即计算二分图上完美匹配的个数，以及计算一个图上的圈覆盖的权重。

与二分图完美匹配的关系

二分图上的完美匹配是算法理论和计算复杂性理论中的重要问题。对于一个n×n的二分图G=(L, R, E)，其中L={1, 2,..., n}是左边结点的集合，R={1', 2', ..., n'}是右边结点的集合，E为边的集合，G的一个完美匹配是{1, 2, ..., n}到{1', 2', ..., n'}的一个双射f，使得(1, f(1)), (2, f(2)), ..., (n, f(n))都在E中出现。
对G，我们可以建立如下n×n的0-1矩阵，其中当且仅当。不难验证，的值即是G中完美匹配的个数。这样，我们将积和式的值与二分图完美匹配的个数建立了联系。

与图的圈覆盖的关系

对于一个图G=(V,E)，V={1, 2, ..., n}为结点集，E为边集。一个G的圈覆盖是一组G中的不相交的圈的集合，且这些圈覆盖所有的点集。由于一个置换可以做环状分解，可以看出一个置换与一个可能的圈覆盖是一一对应的。特别的，G的邻接矩阵的积和式即是G中圈覆盖的数目。

积和式的计算复杂性

积和式的计算是#P完全的。相对的，行列式可以用高斯消元法等算法在多项式时间内解决。